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 𝑡 to a source node 𝑠 in a graph. The Single-Source PPR (SSPPR) query computes the PPR's of all the nodes with respect to 𝑠 on a directed graph 𝐺 with 𝑛 nodes and 𝑚 edges; and it is an essential operation widely used in graph applications. In this paper, we propose novel algorithms for answering two variants of SSPPR queries: (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 𝜆 (which is typically set to as small as 10 -8 ), the only known bound of FwdPush is 𝑂 ( 𝑚 𝜆 ), much worse than the 𝑂 (𝑚 log 1 𝜆 )-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. We show that the running time of a common implementation of FwdPush is actually bounded by 𝑂 (𝑚 • log 1 𝜆 ). 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 𝑂 (𝑛 • log 𝑛 • log 1 𝜖 ) on scale-free graphs. This improves the state-of-the-art 𝑂 ( 𝑛 •log 𝑛 𝜖 ) bound. We conduct extensive experiments on six real datasets. The experimental results show that PowerPush outperforms the stateof-the-art high-precision algorithm BePI by up to an order of magnitude in both efficiency and accuracy. Furthermore, our SpeedPPR also outperforms the state-of-the-art approximate algorithm FORA by up to an order of magnitude in all aspects including query time, accuracy, pre-processing time as well as index size.