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: 11983
Venue: VLDB
Year: 2018
Pagerank: 6.2992176e-05
Overall Rank: 5,250 | 63.99%
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,607	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	8.3489531e-05
4,157	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD	6.8629037e-05
4,171	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.8537202e-05
4,225	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB	6.821373e-05
4,714	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.5497309e-05
5,741	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	6.1029326e-05
6,003	ThunderRW: An In-Memory Graph Random Walk Engine	2021	VLDB	6.0130964e-05
6,456	LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR	2024	SIGMOD	5.8741786e-05
7,011	GPU-Accelerated Graph Label Propagation for Real-Time Fraud Detection	2021	SIGMOD	5.7263348e-05
7,491	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD	5.6059269e-05
7,573	Accelerating Exact Constrained Shortest Paths on GPUs	2021	VLDB	5.5938767e-05
8,062	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.4949527e-05
10,609	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	5.093636e-05
11,097	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB	5.093636e-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.00016564032
945	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00013066956
1,339	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.00011112799
1,432	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.0001080346
2,225	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.9183159e-05
2,874	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	8.0094569e-05
3,315	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.5274958e-05
3,616	Parallel Local Graph Clustering	2016	VLDB	7.2559471e-05
4,171	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.8537202e-05
4,695	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	6.5587201e-05

Semantically Similar Papers

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