# Accelerating Personalized PageRank Vector Computation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2023.

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

- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Knowledge Authoring with Factual English, Rules, and Actions](https://mlsanity.com/paper/2411.06253/) (2024)
- [Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach](https://mlsanity.com/paper/2412.10789/) (2024)
- [Leveraging Personalized PageRank and Higher-Order Topological Structures for Heterophily Mitigation in Graph Neural Networks](https://mlsanity.com/paper/2507.16347/) (2025)

## Abstract (arXiv)

Personalized PageRank Vectors are widely used as fundamental graph-learning tools for detecting anomalous spammers, learning graph embeddings, and training graph neural networks. The well-known local FwdPush algorithm approximates PPVs and has a sublinear rate of Obig(frac1αεbig). A recent study found that when high precision is required, FwdPush is similar to the power iteration method, and its run time is pessimistically bounded by Obig(fracmα logfrac1εbig). This paper looks closely at calculating PPVs for both directed and undirected graphs. By leveraging the linear invariant property, we show that FwdPush is a variant of Gauss-Seidel and propose a Successive Over-Relaxation based method, FwdPushSOR to speed it up by slightly modifying FwdPush. Additionally, we prove FwdPush has local linear convergence rate Obig(tfracvol(S)α logtfrac1εbig) enjoying advantages of two existing bounds. We also design a new local heuristic push method that reduces the number of operations by 10-50 percent compared to FwdPush. For undirected graphs, we propose two momentum-based acceleration methods that can be expressed as one-line updates and speed up non-acceleration methods byObig(tfrac1√αbig). Our experiments on six real-world graph datasets confirm the efficiency of FwdPushSOR and the acceleration methods for directed and undirected graphs, respectively.