Parallel Personalized PageRank on Dynamic Graphs

Summary: Parallel dynamic PPR on graphs with batch updates to reduce synchronization and enable iterative parallelism. Same asymptotic cost as the sequential local-update scheme, with optimizations; GPU/CPU experiments yield orders-of-magnitude speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h76fbf92044afcca9
Venue: VLDB
Year: 2018
Pagerank: 6.1896851e-05
Overall Rank: 5,300 | 64.37%
DOI: 10.14778/3136610.3136618

Incoming Non-self Citations Over Time

Authors

1. Wentian Guo (National University of Singapore)
2. Yuchen Li (National University of Singapore)
3. Mo Sha (National University of Singapore)
4. Kian-Lee Tan (National University of Singapore)

BibTeX Citation

@article{guo_vldb18,
        title = {{Parallel Personalized PageRank on Dynamic Graphs}},
        author = {Guo, Wentian and Li, Yuchen and Sha, Mo and Tan, Kian-Lee},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {1},
        pages = {93--106},
        doi = {10.14778/3136610.3136618},
        url = {https://doi.org/10.14778/3136610.3136618},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,468	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	8.4178183e-05
3,653	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB	7.1288161e-05
4,207	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD	6.7343908e-05
4,237	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.7107028e-05
4,264	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.6978776e-05
5,859	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	5.9682458e-05
6,091	ThunderRW: An In-Memory Graph Random Walk Engine	2021	VLDB	5.8898055e-05
6,120	LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR	2024	SIGMOD	5.880693e-05
6,249	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD	5.8358127e-05
6,509	GPU-Accelerated Graph Label Propagation for Real-Time Fraud Detection	2021	SIGMOD	5.7601316e-05
7,716	Accelerating Exact Constrained Shortest Paths on GPUs	2021	VLDB	5.4683652e-05
8,226	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.3740319e-05
11,056	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	4.9793485e-05
11,449	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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.00016500392
962	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00012820478
1,368	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.0001090624
1,442	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.00010639351
2,258	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.7385422e-05
2,789	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	8.0116036e-05
3,266	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.4775e-05
3,688	Parallel Local Graph Clustering	2016	VLDB	7.095356e-05
4,237	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.7107028e-05
4,788	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	6.4141952e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,183	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD
2	962	Fast Personalized PageRank on MapReduce	2011	SIGMOD
3	8,226	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD
4	9,220	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD
5	2,393	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB
6	3,977	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB
7	4,264	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD
8	3,266	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD
9	1,368	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB
10	3,653	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB