# Efficient Algorithms for Personalized PageRank

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2015.

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

- [LLM-Rec: Personalized Recommendation via Prompting Large Language Models](https://mlsanity.com/paper/2307.15780/) (2023)
- [Mixture-of-PageRanks: Replacing Long-Context with Real-Time, Sparse GraphRAG](https://mlsanity.com/paper/2412.06078/) (2024)
- [xNeuSM: Explainable Neural Subgraph Matching with Graph Learnable Multi-hop Attention Networks](https://mlsanity.com/paper/2312.01612/) (2023)
- [Accelerated Evolving Set Processes for Local PageRank Computation](https://mlsanity.com/paper/2510.08010/) (2025)

## Abstract (arXiv)

We present new, more efficient algorithms for estimating random walk scores such as Personalized PageRank from a given source node to one or several target nodes. These scores are useful for personalized search and recommendations on networks including social networks, user-item networks, and the web. Past work has proposed using Monte Carlo or using linear algebra to estimate scores from a single source to every target, making them inefficient for a single pair. Our contribution is a new bidirectional algorithm which combines linear algebra and Monte Carlo to achieve significant speed improvements. On a diverse set of six graphs, our algorithm is 70x faster than past state-of-the-art algorithms. We also present theoretical analysis: while past algorithms require Omega(n) time to estimate a random walk score of typical size frac1n on an n-node graph to a given constant accuracy, our algorithm requires only O(√m) expected time for an average target, where m is the number of edges, and is provably accurate. In addition to our core bidirectional estimator for personalized PageRank, we present an alternative algorithm for undirected graphs, a generalization to arbitrary walk lengths and Markov Chains, an algorithm for personalized search ranking, and an algorithm for sampling random paths from a given source to a given set of targets. We expect our bidirectional methods can be extended in other ways and will be useful subroutines in other graph analysis problems.