Incremental and accuracy-aware personalized pagerank through scheduled approximation

As Personalized PageRank has been widely leveraged for ranking on a graph, the efficient computation of Personalized PageRank Vector (PPV) becomes a prominent issue. In this paper, we pro-pose FastPPV, an approximate PPV computation algorithm that is incremental and accuracy-aware. Our approach hinges on a novel paradigm of scheduled approximation: the computation is parti-tioned and scheduled for processing in an “organized ” way, such that we can gradually improve our PPV estimation in an incremen-tal manner, and quantify the accuracy of our approximation at query time. Guided by this principle, we develop an efficient hub based realization, where we adopt the metric of hub-length to partition and schedule random walk tours so that the approximation error re-duces exponentially over iterations. Furthermore, as tours are seg-mented by hubs, the shared substructures between different tours (around the same hub) can be reused to speed up query process-ing both within and across iterations. Finally, we evaluate FastPPV over two real-world graphs, and show that it not only significantly outperforms two state-of-the-art baselines in both online and of-fline phrases, but also scale well on larger graphs. In particular, we are able to achieve near-constant time online query processing irrespective of graph size. 1