Back to papers
TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs
Summary: TopPPR delivers top-k PPR queries with rho-precision guarantees (at least rho of the true top-k) and 1-1/n probability. No preprocessing, handles dynamic graphs, and scales to large graphs, e.g., 15s for top-500 on a billion-edge Twitter graph with rho=1.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 5566
- Venue
- SIGMOD
- Year
- 2018
- Pagerank
- 5.9631943e-05
- Overall Rank
- 4,733 | 67.08%
- DOI
-
10.1145/3183713.3196920
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 19 of 19 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 1,474 |
Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank |
2020 |
VLDB |
0.00011825229 |
| 2,827 |
Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push |
2021 |
SIGMOD |
8.0551884e-05 |
| 3,709 |
Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank |
2023 |
VLDB |
6.8242482e-05 |
| 4,562 |
Massively Parallel Algorithms for Personalized PageRank |
2021 |
VLDB |
6.0846728e-05 |
| 4,671 |
Realtime Top-k Personalized PageRank over Large Graphs on GPUs |
2020 |
VLDB |
6.0085645e-05 |
| 5,147 |
Efficient Tree-SVD for Subset Node Embedding over Large Dynamic Graphs |
2023 |
SIGMOD |
5.6643767e-05 |
| 5,655 |
Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme |
2023 |
SIGMOD |
5.387631e-05 |
| 5,702 |
Efficient Estimation of Heat Kernel PageRank for Local Clustering |
2019 |
SIGMOD |
5.36473e-05 |
| 6,058 |
ThunderRW: An In-Memory Graph Random Walk Engine |
2021 |
VLDB |
5.2310254e-05 |
| 6,381 |
Edge-based Local Push for Personalized PageRank |
2022 |
VLDB |
5.0890757e-05 |
| 7,086 |
Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach |
2022 |
SIGMOD |
4.8381004e-05 |
| 7,394 |
Efficient Estimation of Pairwise Effective Resistance |
2023 |
SIGMOD |
4.7427524e-05 |
| 7,446 |
QTCS: Efficient Query-Centered Temporal Community Search |
2024 |
VLDB |
4.727813e-05 |
| 8,236 |
PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs |
2019 |
SIGMOD |
4.553296e-05 |
| 9,325 |
Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches |
2023 |
SIGMOD |
4.3556432e-05 |
| 9,328 |
Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time |
2023 |
VLDB |
4.3556432e-05 |
| 9,360 |
MITra: A Framework for Multi-Instance Graph Traversal |
2023 |
VLDB |
4.350809e-05 |
| 10,957 |
Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach |
2024 |
SIGMOD |
4.1945683e-05 |
| 11,027 |
BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank |
2024 |
VLDB |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 12 of 12 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 486 |
Fast Incremental and Personalized PageRank |
2011 |
VLDB |
0.00022068545 |
| 886 |
Fast Personalized PageRank on MapReduce |
2011 |
SIGMOD |
0.00015597161 |
| 1,641 |
Fast and Exact Top-k Search for Random Walk with Restart |
2012 |
VLDB |
0.00011047924 |
| 1,821 |
Computing Personalized PageRank Quickly by Exploiting Graph Structures |
2014 |
VLDB |
0.00010423565 |
| 1,920 |
Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs |
2014 |
SIGMOD |
0.00010090791 |
| 2,098 |
Efficient Ad-hoc Search for Personalized PageRank |
2013 |
SIGMOD |
9.5480012e-05 |
| 2,210 |
BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs |
2015 |
SIGMOD |
9.2856573e-05 |
| 2,242 |
HubPPR: Effective Indexing for Approximate Personalized PageRank |
2017 |
VLDB |
9.218875e-05 |
| 2,537 |
BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart |
2017 |
SIGMOD |
8.5834428e-05 |
| 2,780 |
Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation |
2013 |
VLDB |
8.1317773e-05 |
| 3,872 |
Distributed Algorithms on Exact Personalized PageRank |
2017 |
SIGMOD |
6.6785582e-05 |
| 6,974 |
ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks |
2016 |
SIGMOD |
4.8780906e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,780 |
Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation |
2013 |
VLDB |
8.1317773e-05 |
| 8,236 |
PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs |
2019 |
SIGMOD |
4.553296e-05 |
| 4,562 |
Massively Parallel Algorithms for Personalized PageRank |
2021 |
VLDB |
6.0846728e-05 |
| 6,381 |
Edge-based Local Push for Personalized PageRank |
2022 |
VLDB |
5.0890757e-05 |
| 10,028 |
One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor |
2026 |
SIGMOD |
4.1945683e-05 |
| 1,821 |
Computing Personalized PageRank Quickly by Exploiting Graph Structures |
2014 |
VLDB |
0.00010423565 |
| 5,655 |
Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme |
2023 |
SIGMOD |
5.387631e-05 |
| 2,827 |
Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push |
2021 |
SIGMOD |
8.0551884e-05 |
| 2,242 |
HubPPR: Effective Indexing for Approximate Personalized PageRank |
2017 |
VLDB |
9.218875e-05 |
| 4,671 |
Realtime Top-k Personalized PageRank over Large Graphs on GPUs |
2020 |
VLDB |
6.0085645e-05 |