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

arXiv: https://arxiv.org/abs/2101.03652 · HTML: https://mlsanity.com/paper/2101.03652/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jan 2021.

## Built on by (most cited first, 8 of 8)

- [SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization](https://mlsanity.com/paper/2207.09179/) (2022)
- [LPNL: Scalable Link Prediction with Large Language Models](https://mlsanity.com/paper/2401.13227/) (2024)
- [Fast Online Node Labeling for Very Large Graphs](https://mlsanity.com/paper/2305.16257/) (2023)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Improving Graph Neural Networks at Scale: Combining Approximate PageRank and CoreRank](https://mlsanity.com/paper/2211.04248/) (2022)
- [Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective](https://mlsanity.com/paper/2405.19649/) (2024)
- [Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach](https://mlsanity.com/paper/2412.10789/) (2024)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)

## Abstract (arXiv)

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.