Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme

Summary: Incremental PPR index-update for evolving graphs; fuses forward-push with a random-walk index for fast SSPPR. Achieves O(1) update time with compact structures; a sampling scheme removes vertex data while preserving updates and query quality. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h98638d61b797ebb9
Venue: SIGMOD
Year: 2023
Pagerank: 6.8626164e-05
Overall Rank: 3,988 | 73.27%
DOI: 10.1145/3588705

Incoming Non-self Citations Over Time

Authors

1. Guanhao Hou (Chinese University of Hong Kong)
2. Qintian Guo (Chinese University of Hong Kong)
3. Fangyuan Zhang (Chinese University of Hong Kong)
4. Sibo Wang (Chinese University of Hong Kong)
5. Zhewei Wei (Renmin University of China)

BibTeX Citation

@inproceedings{hou_sigmod23,
        title = {{Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme}},
        author = {Hou, Guanhao and Guo, Qintian and Zhang, Fangyuan and Wang, Sibo and Wei, Zhewei},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588705},
        url = {https://dl.acm.org/doi/10.1145/3588705},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,488	LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration	2025	VLDB	7.2425679e-05
5,741	Efficient Tree-SVD for Subset Node Embedding over Large Dynamic Graphs	2023	SIGMOD	5.9939789e-05
7,267	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	5.5539363e-05
7,624	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	5.4661079e-05
8,440	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	5.3148581e-05
9,254	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD	5.1860131e-05
9,685	Efficient Approximation of Kemeny’s Constant for Large Graphs	2024	SIGMOD	5.1258854e-05
9,768	Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs	2025	VLDB	5.115551e-05
9,836	ACGraph: An Efficient Asynchronous Out-of-Core Graph Processing Framework	2026	SIGMOD	5.1064323e-05
9,988	Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs	2025	SIGMOD	5.0845476e-05
10,296	BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank	2024	VLDB	5.031399e-05
10,414	Tree+DAG: An Efficient Index for Resistance Distance Computation on Core-Periphery Graphs	2027	SIGMOD	4.9605343e-05
10,456	Near-Optimality for Single-Source Personalized PageRank	2026	PODS	4.9605343e-05
10,906	Sankofa: Online Query-adaptive Dynamic Graph Summaries	2026	VLDB	4.9605343e-05
11,782	Efficient Approximation Framework for Attribute Recommendation	2023	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
555	Fast Incremental and Personalized PageRank	2011	VLDB	0.00016476141
1,303	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.00011089258
1,796	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.6106766e-05
1,843	Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank	2020	VLDB	9.512431e-05
1,855	Efficient Ad-hoc Search for Personalized PageRank	2013	SIGMOD	9.4850141e-05
2,089	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	9.0473016e-05
2,103	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.0280807e-05
2,188	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.8879472e-05
2,382	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB	8.5296758e-05
3,239	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.483901e-05
3,657	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB	7.1105244e-05
3,985	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	6.8649592e-05
4,097	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.7946571e-05
5,130	Link Spam Detection Based on Mass Estimation	2006	VLDB	6.2471873e-05
5,308	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB	6.1739397e-05
5,741	Efficient Tree-SVD for Subset Node Embedding over Large Dynamic Graphs	2023	SIGMOD	5.9939789e-05
5,874	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	5.9456951e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,456	Near-Optimality for Single-Source Personalized PageRank	2026	PODS
2	1,303	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB
3	8,251	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD
4	5,308	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB
5	2,089	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD
6	2,188	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB
7	6,416	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD
8	5,244	Edge-based Local Push for Personalized PageRank	2022	VLDB
9	2,382	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB
10	9,254	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD