# Efficient Algorithms for Personalized PageRank Computation: A Survey

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2024.

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

- [Graph-of-Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills](https://mlsanity.com/paper/2604.05333/) (2026)
- [Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier](https://mlsanity.com/paper/2408.09212/) (2024)
- [Beyond Over-smoothing: Uncovering the Trainability Challenges in Deep Graph Neural Networks](https://mlsanity.com/paper/2408.03669/) (2024)
- [LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration](https://mlsanity.com/paper/2411.05844/) (2024)
- [CURE:Circuit-Aware Unlearning for LLM-based Recommendation](https://mlsanity.com/paper/2604.04982/) (2026)
- [Local Clustering on Complex Graphs and Complex Hypergraphs](https://mlsanity.com/paper/2412.03008/) (2024)
- [<SOG_k>: One LLM Token for Explicit Graph Structural Understanding](https://mlsanity.com/paper/2602.01771/) (2026)
- [LightPAL: Lightweight Passage Retrieval for Open Domain Multi-Document Summarization](https://mlsanity.com/paper/2406.12494/) (2024)
- [KG-ViP: Bridging Knowledge Grounding and Visual Perception in Multi-modal LLMs for Visual Question Answering](https://mlsanity.com/paper/2601.11632/) (2026)
- [HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG](https://mlsanity.com/paper/2602.20926/) (2026)
- [SkillTrace: Traversing a Query-Skill Graph for Composable LLM Agents](https://mlsanity.com/paper/2608.02356/) (2026)
- [SE-GoS: Self-Evolving Graph-of-Skills for Skill Library at Scale](https://mlsanity.com/paper/2609.08228/) (2026)
- [Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach](https://mlsanity.com/paper/2412.10789/) (2024)
- [Game of Trust: How Trustworthy Does Your Blockchain Think You Are?](https://mlsanity.com/paper/2505.14551/) (2025)
- [Leveraging Personalized PageRank and Higher-Order Topological Structures for Heterophily Mitigation in Graph Neural Networks](https://mlsanity.com/paper/2507.16347/) (2025)
- [Matching Game Preferences Through Dialogical Large Language Models: A Perspective](https://mlsanity.com/paper/2507.20000/) (2025)
- [Accelerated Evolving Set Processes for Local PageRank Computation](https://mlsanity.com/paper/2510.08010/) (2025)
- [RankGraph-2: Lifecycle Co-Design for Billion-Node Graph Learning in Recommendation](https://mlsanity.com/paper/2606.18379/) (2026)
- [Where to Look and What to Use: Retrieve-Localize-Generate for Long-Term Conversational Memory Question Answering](https://mlsanity.com/paper/2609.07093/) (2026)
- [Beyond Similarity through Zero-Token Geometric Graphs for Multi-Hop RAG](https://mlsanity.com/paper/2609.19622/) (2026)
- [BizSage: A Self-Evolving Multi-Agent Framework for Business Research with Efficient Knowledge Retrieval](https://mlsanity.com/paper/2609.22235/) (2026)

## Abstract (arXiv)

Personalized PageRank (PPR) is a traditional measure for node proximity on large graphs. For a pair of nodes s and t, the PPR value πs(t) equals the probability that an α-discounted random walk from s terminates at t and reflects the importance between s and t in a bidirectional way. As a generalization of Google's celebrated PageRank centrality, PPR has been extensively studied and has found multifaceted applications in many fields, such as network analysis, graph mining, and graph machine learning. Despite numerous studies devoted to PPR over the decades, efficient computation of PPR remains a challenging problem, and there is a dearth of systematic summaries and comparisons of existing algorithms. In this paper, we recap several frequently used techniques for PPR computation and conduct a comprehensive survey of various recent PPR algorithms from an algorithmic perspective. We classify these approaches based on the types of queries they address and review their methodologies and contributions. We also discuss some representative algorithms for computing PPR on dynamic graphs and in parallel or distributed environments.