DBScholar

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
h11b16c748f35e2fe
Venue
SIGMOD
Year
2018
Pagerank
6.8040813e-05
Overall Rank
4,103 | 72.43%
DOI
10.1145/3183713.3196920

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{wei_sigmod18,
        title = {{TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs}},
        author = {Wei, Zhewei and He, Xiaodong and Xiao, Xiaokui and Wang, Sibo and Shang, Shuo and Wen, Ji-Rong},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3196920},
        url = {https://dl.acm.org/doi/10.1145/3183713.3196920},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank Citing Paper Year Venue Pagerank
1,836 Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank 2020 VLDB 9.53235e-05
2,185 Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push 2021 SIGMOD 8.8920069e-05
3,018 Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank 2023 VLDB 7.743467e-05
3,655 Realtime Top-k Personalized PageRank over Large Graphs on GPUs 2020 VLDB 7.1254436e-05
3,978 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB 6.8818094e-05
4,264 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD 6.6947069e-05
5,241 Edge-based Local Push for Personalized PageRank 2022 VLDB 6.2142384e-05
5,277 Efficient Estimation of Pairwise Effective Resistance 2023 SIGMOD 6.1978354e-05
5,728 Efficient Tree-SVD for Subset Node Embedding over Large Dynamic Graphs 2023 SIGMOD 6.0138645e-05
6,035 Efficient Estimation of Heat Kernel PageRank for Local Clustering 2019 SIGMOD 5.9065619e-05
6,093 ThunderRW: An In-Memory Graph Random Walk Engine 2021 VLDB 5.8870862e-05
6,292 QTCS: Efficient Query-Centered Temporal Community Search 2024 VLDB 5.8197041e-05
6,405 Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach 2022 SIGMOD 5.7936558e-05
8,232 Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches 2023 SIGMOD 5.3714879e-05
8,233 Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time 2023 VLDB 5.3714879e-05
8,384 PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs 2019 SIGMOD 5.3406945e-05
8,636 Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach 2024 SIGMOD 5.2969407e-05
9,620 MITra: A Framework for Multi-Instance Graph Traversal 2023 VLDB 5.1494633e-05
10,269 BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank 2024 VLDB 5.0480912e-05
10,390 Near-Optimality for Single-Source Personalized PageRank 2026 PODS 4.9769913e-05
Previous Page 1 / 1 Next

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
556 Fast Incremental and Personalized PageRank 2011 VLDB 0.00016492651
964 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00012814643
1,368 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB 0.00010901078
1,420 Fast and Exact Top-k Search for Random Walk with Restart 2012 VLDB 0.00010724642
1,602 Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs 2014 SIGMOD 0.00010100314
1,798 BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs 2015 SIGMOD 9.6123666e-05
1,861 Efficient Ad-hoc Search for Personalized PageRank 2013 SIGMOD 9.4839542e-05
2,103 BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart 2017 SIGMOD 9.0420935e-05
2,259 HubPPR: Effective Indexing for Approximate Personalized PageRank 2017 VLDB 8.7344054e-05
2,395 Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation 2013 VLDB 8.5281025e-05
3,267 Distributed Algorithms on Exact Personalized PageRank 2017 SIGMOD 7.4739604e-05
6,943 ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks 2016 SIGMOD 5.6364384e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,384 PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs 2019 SIGMOD
2 3,978 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB
3 5,241 Edge-based Local Push for Personalized PageRank 2022 VLDB
4 9,230 One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor 2026 SIGMOD
5 1,368 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB
6 4,264 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD
7 2,185 Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push 2021 SIGMOD
8 10,390 Near-Optimality for Single-Source Personalized PageRank 2026 PODS
9 2,259 HubPPR: Effective Indexing for Approximate Personalized PageRank 2017 VLDB
10 3,655 Realtime Top-k Personalized PageRank over Large Graphs on GPUs 2020 VLDB