Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach

• DOI: 10.1145/3514221.3526140
• Publication Date: 2022-06-12T02:33:49Z
• Authors: Meihao Liao; Rong-Hua Li; Qiangqiang Dai; Guoren Wang
• Keywords: PageRank

Computing the personalized PageRank vector is a fundamental problem in graph analysis. In this paper, we propose several novel algorithms to efficiently compute with decay factor α based on an interesting connection between values and weights of random spanning forests graph. Such derived newly-developed matrix forest theorem graphs. Based this, present efficient sampling algorithm via simulating loop-erased α-random walks estimate vector. Compared all existing methods, striking feature our approach that its performance insensitive w.r.t. (with respect to) parameter α. As consequence, often much faster than state-of-the-art when small, which demanding case for many analysis tasks. We show technique can significantly improve efficiency answering two well-studied queries, including single source query target query. Extensive experiments seven large real-world graphs demonstrate proposed method.