Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches

Summary: Two variance-reduction techniques for Personalized PageRank: power-iteration variance reduction and progressive sampling. Integrates these with random-walk and spanning-forest Monte Carlo PPR to achieve higher accuracy at equal or lower runtime than state-of-the-art bidirectional algorithms, leveraging historical sampling. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h4b874390f820b070
Venue: SIGMOD
Year: 2023
Pagerank: 5.3714879e-05
Overall Rank: 8,232 | 44.68%
DOI: 10.1145/3589305

Incoming Non-self Citations Over Time

Authors

1. Meihao Liao (Beijing Institute of Technology)
2. Rong-Hua Li (Beijing Institute of Technology)
3. Qiangqiang Dai (Beijing Institute of Technology)
4. Hongyang Chen (Zhejiang Lab)
5. Hongchao Qin (Beijing Institute of Technology)
6. Guoren Wang (Beijing Institute of Technology)

BibTeX Citation

@inproceedings{liao_sigmod23,
        title = {{Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches}},
        author = {Liao, Meihao and Li, Rong-Hua and Dai, Qiangqiang and Chen, Hongyang and Qin, Hongchao and Wang, Guoren},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3589305},
        url = {https://dl.acm.org/doi/10.1145/3589305},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,636	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.2969407e-05
9,230	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD	5.2032182e-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

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
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,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,185	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.8920069e-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
3,690	Parallel Local Graph Clustering	2016	VLDB	7.0919971e-05
3,978	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	6.8818094e-05
4,103	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.8040813e-05
5,303	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB	6.1867551e-05
5,861	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	5.9654205e-05
6,405	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.7936558e-05
6,791	Indexed Fast Network Proximity Querying	2018	VLDB	5.6796169e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,978	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB
2	5,861	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD
3	9,230	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD
4	2,395	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB
5	5,303	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB
6	1,368	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB
7	556	Fast Incremental and Personalized PageRank	2011	VLDB
8	4,264	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD
9	964	Fast Personalized PageRank on MapReduce	2011	SIGMOD
10	6,405	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD