Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push

Personalized PageRank (PPR) is a critical measure of the importance of a node t to a source node s in a graph. The Single-Source PPR (SSPPR) query computes the PPR's of all the nodes with respect to s on a directed graph G with n nodes and m edges, and it is an essential operation widely used in graph applications. In this paper, we propose novel algorithms for solving two variants of SSPPR: (i) high-precision queries and (ii) approximate queries. For high-precision queries, Power Iteration (PowItr) and Forward Push (FwdPush) are two fundamental approaches. Given an absolute error threshold λ, the only known bound of FwdPush is O(fracmλ), much worse than the O(m log frac1λ)-bound of PowItr. Whether FwdPush can achieve the same running time bound as PowItr does still remains an open question in the research community. We give a positive answer to this question by showing that the running time of a common implementation of FwdPush is actually bounded by O(m · log frac1λ).Based on this finding, we propose a new algorithm, called Power Iteration with Forward Push (PowerPush), which incorporates the strengths of both PowItr and FwdPush. For approximate queries (with a relative error ε), we propose a new algorithm, called SpeedPPR, with overall expected time bounded by O(n · log n · log frac1ε) on scale-free graphs. This bound greatly improves the O(fracn · log nε) bound of a state-of-the-art algorithm FORA.