FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs

Abstract

We propose a new algorithm, FAST-PPR, for estimating personalized PageRank: given start node $s$ and target node $t$ in a directed graph, and given a threshold $\hat{I}´$, FAST-PPR estimates the Personalized PageRank $\ddot{I}{€}_s(t)$ from $s$ to $t$, guaranteeing a small relative error as long $\ddot{I}{€}_s(t)>\hat{I}´$. Existing algorithms for this problem have a running-time of $\hat{I}\text{c◯}(1/\hat{I}´)$; in comparison, FAST-PPR has a provable average running-time guarantee of $O(\sqrt{d/\hat{I}´})$ (where $d$ is the average in-degree of the graph). This is a significant improvement, since $\hat{I}´$ is often $O(1/n)$ (where $n$ is the number of nodes) for applications. We also complement the algorithm with an $\hat{I}\text{c◯}(1/\sqrt{\hat{I}}´)$ lower bound for PageRank estimation, showing that the dependence on $\hat{I}´$ 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.

KDD 2014