Massively Parallel Algorithms for Personalized PageRank

Summary: Delta-Push computes single-source and top-k personalized PageRank under MPC with bounded per-round load and communication rounds. Pre-sampled walks accelerate parallel push, while elastic batching uses extra executors for multiple queries. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12541
Venue: VLDB
Year: 2021
Pagerank: 7.0430255e-05
Overall Rank: 3,892 | 73.30%
DOI: 10.14778/3461535.3461554

Incoming Non-self Citations Over Time

Authors

1. Guanhao Hou (Chinese University of Hong Kong)
2. Xingguang Chen (Chinese University of Hong Kong)
3. Sibo Wang (Chinese University of Hong Kong)
4. Zhewei Wei (Renmin University of China)

BibTeX Citation

@article{hou_vldb21,
        title = {{Massively Parallel Algorithms for Personalized PageRank}},
        author = {Hou, Guanhao and Chen, Xingguang and Wang, Sibo and Wei, Zhewei},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {9},
        pages = {1668--1680},
        doi = {10.14778/3461535.3461554},
        url = {https://doi.org/10.14778/3461535.3461554},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,714	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.5497309e-05
5,139	Edge-based Local Push for Personalized PageRank	2022	VLDB	6.3495351e-05
5,596	Efficient Tree-SVD for Subset Node Embedding over Large Dynamic Graphs	2023	SIGMOD	6.1548101e-05
8,062	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.4949527e-05
9,373	Efficient and Accurate PageRank Approximation on Large Graphs	2024	SIGMOD	5.2755515e-05
9,616	ACGraph: An Efficient Asynchronous Out-of-Core Graph Processing Framework	2026	SIGMOD	5.2434488e-05
10,161	Near-Optimality for Single-Source Personalized PageRank	2026	PODS	5.093636e-05
11,132	Topology-aware Parallel Joins	2024	PODS	5.093636e-05
11,145	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	5.093636e-05
11,172	Efficient Approximation of Kemeny’s Constant for Large Graphs	2024	SIGMOD	5.093636e-05
11,390	Effective and Efficient PageRank-based Positioning for Graph Visualization	2023	SIGMOD	5.093636e-05
11,418	Efficient Approximation Framework for Attribute Recommendation	2023	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
945	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00013066956
1,207	Communication Steps for Parallel Query Processing	2013	PODS	0.00011663155
1,339	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.00011112799
1,769	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.7969398e-05
1,838	Efficient Ad-hoc Search for Personalized PageRank	2013	SIGMOD	9.6436348e-05
2,073	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.2209912e-05
2,225	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.9183159e-05
2,362	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB	8.6889619e-05
3,315	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.5274958e-05
4,024	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.9479974e-05
5,031	Link Spam Detection Based on Mass Estimation	2006	VLDB	6.3953025e-05
5,741	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	6.1029326e-05
8,212	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	5.4658632e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,284	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD
2	8,062	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD
3	2,173	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD
4	5,139	Edge-based Local Push for Personalized PageRank	2022	VLDB
5	4,024	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD
6	945	Fast Personalized PageRank on MapReduce	2011	SIGMOD
7	556	Fast Incremental and Personalized PageRank	2011	VLDB
8	5,250	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB
9	4,225	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB
10	3,315	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD