# FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2014.

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

- [LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration](https://mlsanity.com/paper/2411.05844/) (2024)
- [Local Algorithms for Estimating Effective Resistance](https://mlsanity.com/paper/2106.03476/) (2021)
- [Randomized Algorithms for Scientific Computing (RASC)](https://mlsanity.com/paper/2104.11079/) (2021)
- [Bonsai: Gradient-free Graph Condensation for Node Classification](https://mlsanity.com/paper/2410.17579/) (2024)
- [Detecting Complex Money Laundering Patterns with Incremental and Distributed Graph Modeling](https://mlsanity.com/paper/2604.01315/) (2026)
- [On Statistical Estimation of Edge-Reinforced Random Walks](https://mlsanity.com/paper/2503.06115/) (2025)

## Abstract (arXiv)

We propose a new algorithm, FAST-PPR, for estimating personalized PageRank: given start node s and target node t in a directed graph, and given a threshold δ, FAST-PPR estimates the Personalized PageRank πs(t) from s to t, guaranteeing a small relative error as long πs(t)>δ. Existing algorithms for this problem have a running-time of Omega(1/δ); in comparison, FAST-PPR has a provable average running-time guarantee of O(√d/δ) (where d is the average in-degree of the graph). This is a significant improvement, since δ is often O(1/n) (where n is the number of nodes) for applications. We also complement the algorithm with an Omega(1/√δ) lower bound for PageRank estimation, showing that the dependence on δ cannot be improved. We perform a detailed empirical study on numerous massive graphs, showing that FAST-PPR dramatically outperforms existing algorithms. For example, on the 2010 Twitter graph with 1.5 billion edges, for target nodes sampled by popularity, FAST-PPR has a 20 factor speedup over the state of the art. Furthermore, an enhanced version of FAST-PPR has a 160 factor speedup on the Twitter graph, and is at least 20 times faster on all our candidate graphs.