Near-Optimality for Single-Source Personalized PageRank

Summary: Closes much of the SSPPR complexity gap with O(1/ε²) absolute-error and near-matching relative-error upper/lower bounds, achieving optimality across broad graph regimes. A general lower-bound framework also establishes optimal STPPR bounds. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 2036
Venue: PODS
Year: 2026
Pagerank: 5.0723324e-05
Overall Rank: 10,203 | 30.24%
DOI: 10.1145/3801906

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Xinpeng Jiang (Nanyang Technological University)
2. Haoyu Liu (Nanyang Technological University)
3. Siqiang Luo (Nanyang Technological University)
4. Xiaokui Xiao (National University of Singapore)

BibTeX Citation

@inproceedings{jiang_pods26,
        address = {New York, NY, USA},
        series = {{PODS} '26},
        title = {{Near-Optimality for Single-Source Personalized PageRank}},
        url = {https://dl.acm.org/doi/10.1145/3801906},
        doi = {10.1145/3801906},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Jiang, Xinpeng and Liu, Haoyu and Luo, Siqiang and Xiao, Xiaokui},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
1,980	Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank	2020	VLDB	9.3381964e-05
2,177	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	9.0095882e-05
3,907	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	7.0135689e-05
4,025	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.929094e-05
4,645	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.5688425e-05
5,999	SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization	2022	VLDB	5.9996493e-05
6,314	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.9022259e-05
7,693	The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs	2022	PODS	5.5504921e-05
8,102	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.4719707e-05
8,103	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB	5.4719707e-05
8,136	Optimal Algorithms for Multiway Search on Partial Orders	2022	PODS	5.4651774e-05
9,080	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD	5.302893e-05
11,299	BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank	2024	VLDB	5.0723324e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,228	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB
2	5,139	Edge-based Local Push for Personalized PageRank	2022	VLDB
3	1,346	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB
4	3,907	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB
5	2,368	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB
6	4,218	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB
7	4,645	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD
8	4,025	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD
9	2,177	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD
10	9,080	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD