Paper Info
Title
Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach
Abstract
Computing the personalized PageRank vector is a fundamental problem in graph analysis. In this paper, we propose several novel algorithms to efficiently compute the personalized PageRank vector with a decay factor a based on an interesting connection between the personalized PageRank values and the weights of random spanning forests of the graph. Such a connection is derived based on a newly-developed matrix forest theorem on graphs. Based on this, we present an efficient spanning forest sampling algorithm via simulating loop-erased a-random walks to estimate the personalized PageRank vector. Compared to all existing methods, a striking feature of our approach is that its performance is insensitive w.r.t. (with respect to) the parameter alpha. As a consequence, our algorithm is often much faster than the state-of-the-art algorithms when alpha is small, which is the demanding case for many graph analysis tasks. We show that our technique can significantly improve the efficiency of the state-of-the-art algorithms for answering two well-studied personalized PageRank queries, including single source query and single target query. Extensive experiments on seven large real-world graphs demonstrate the efficiency of the proposed method.
Year
DOI
Venue
2022
10.1145/3514221.3526140
PROCEEDINGS OF THE 2022 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA (SIGMOD '22)
Keywords
DocType
ISSN
Personalized PageRank, Spanning Forest
Conference
0730-8078
Citations 
PageRank 
References 
0
0.34
0
Authors
4
Name
Order
Citations
PageRank
Meihao Liao100.68
Rong-Hua Li238133.77
Qiangqiang Dai302.03
Guoren Wang41366159.46