FAST-PPR: scaling personalized pagerank estimation for large graphs
By Peter Lofgren, Siddhartha Banerjee, Ashish Goel, Seshadhri Comandur. 2014
131 citations recorded by the source corpus.
We propose a new algorithm, FAST-PPR, for computing personalized PageRank: given start node s and target node t in a directed graph, and given a threshold δ, it computes the Personalized PageRank π_s(t) from s to t, guaranteeing that the relative error is small as long πs(t) > δ. Existing algorithms for this problem have a running-time of Ω(1/δ in comparison, FAST-PPR has a provable average running-time guarantee of O(√d/δ) (where d is the average in-degree of the graph). This is a significant improvement, since δ is often O(1/n) (where n is the number of nodes) for applications. We also complement the algorithm with an Ω(1/√δ) lower bound for PageRank estimation, showing that the dependence on δ cannot be improved. We perform a detailed empirical study on numerous massive graphs, showing that FAST-PPR dramatically outperforms existing algorithms. For example, on the 2010 Twitter graph with 1.5 billion edges, for target nodes sampled by popularity, FAST-PPR has a 20 factor speedup over the state of the art. Furthermore, an enhanced version of FAST-PPR has a 160 factor speedup on the Twitter graph, and is at least 20 times faster on all our candidate graphs.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Aleksandar Bojchevski
- Stephan Günnemann
- Johannes Klicpera
- Rok Sosic
- Jure Leskovec
- Daniel Zügner
- Matthias Fey
- William L. Hamilton
Citations in the corpus
- Predict then Propagate: Graph Neural Networks meet Personalized PageRank (2018, background): “Furthermore, faster or incremental approximations of personalized PageRank (Bahmani et al., 2010; 2011; Lofgren et al., 2014) and more sophisticated propagation schemes would also benefit the method.”
- SNAP: A General Purpose Network Analysis and Graph Mining Library (2016, methodology): “In personalized PageRank, we want to identify important nodes from the point of view of a given node [Benczur et al. 2005; Lofgren et al. 2014; Page et al. 1999].”