Efficient and Accurate PageRank Approximation on Large Graphs
Summary: CUR-Trans lowers PageRank time with tighter error bounds via matrix-approximation. T^2-Approx further reduces runtime while providing PageRank estimates for all vertices with competitive accuracy, validated on three large graphs. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Siyue Wu (Shenzhen University)
- 2. Dingming Wu (Shenzhen University)
- 3. Junyi Quan (Shenzhen University)
- 4. Tsz Nam Chan (Shenzhen University)
- 5. Kezhong Lu (Shenzhen University)
BibTeX Citation
@inproceedings{wu_sigmod24,
title = {{Efficient and Accurate PageRank Approximation on Large Graphs}},
author = {Wu, Siyue and Wu, Dingming and Quan, Junyi and Chan, Tsz Nam and Lu, Kezhong},
series = {{SIGMOD} '24},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3677132},
url = {https://dl.acm.org/doi/10.1145/3677132},
year = {2024}
}Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,247 | Optimal Approximate Matrix Multiplication over Sliding Windows | 2026 | VLDB | 5.4574671e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 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 |
| 3,892 | Massively Parallel Algorithms for Personalized PageRank | 2021 | VLDB | 7.0430255e-05 |
| 5,139 | Edge-based Local Push for Personalized PageRank | 2022 | VLDB | 6.3495351e-05 |
| 5,741 | Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks | 2018 | SIGMOD | 6.1029326e-05 |
| 6,284 | Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach | 2022 | SIGMOD | 5.927015e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 945 | Fast Personalized PageRank on MapReduce | 2011 | SIGMOD |
| 2 | 8,062 | Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches | 2023 | SIGMOD |
| 3 | 5,741 | Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks | 2018 | SIGMOD |
| 4 | 5,913 | Efficient Estimation of Heat Kernel PageRank for Local Clustering | 2019 | SIGMOD |
| 5 | 1,339 | Computing Personalized PageRank Quickly by Exploiting Graph Structures | 2014 | VLDB |
| 6 | 8,063 | Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time | 2023 | VLDB |
| 7 | 8,212 | PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs | 2019 | SIGMOD |
| 8 | 6,284 | Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach | 2022 | SIGMOD |
| 9 | 1,396 | Estimating PageRank on Graph Streams | 2008 | PODS |
| 10 | 2,362 | Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation | 2013 | VLDB |