Efficient Estimation of Heat Kernel PageRank for Local Clustering

Summary: TEA and TEA+: HKPR-based local clustering with relative-error guarantees and near-linear time in cluster size, via deterministic rough HKPR and Monte Carlo refinement. TEA+ beats prior methods ~4x on real graphs (Twitter, Friendster), enabling scalable clustering on billion-edge networks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5760
Venue: SIGMOD
Year: 2019
Pagerank: 6.0439971e-05
Overall Rank: 5,913 | 59.44%
DOI: 10.1145/3299869.3319886

Incoming Non-self Citations Over Time

Authors

1. Renchi Yang (Nanyang Technological University)
2. Xiaokui Xiao (National University of Singapore)
3. Zhewei Wei (Renmin University of China)
4. Sourav S Bhowmick (Nanyang Technological University)
5. Jun Zhao (Nanyang Technological University)
6. Rong-Hua Li (Beijing Institute of Technology)

BibTeX Citation

@inproceedings{yang_sigmod19,
        title = {{Efficient Estimation of Heat Kernel PageRank for Local Clustering}},
        author = {Yang, Renchi and Xiao, Xiaokui and Wei, Zhewei and Bhowmick, Sourav S and Zhao, Jun and Li, Rong-Hua},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3319886},
        url = {https://dl.acm.org/doi/10.1145/3299869.3319886},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,139	Edge-based Local Push for Personalized PageRank	2022	VLDB	6.3495351e-05
5,157	Efficient Estimation of Pairwise Effective Resistance	2023	SIGMOD	6.3409526e-05
6,156	QTCS: Efficient Query-Centered Temporal Community Search	2024	VLDB	5.9560993e-05
8,063	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB	5.4949527e-05
8,911	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.3483178e-05
9,046	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD	5.3251649e-05
9,513	Optimal Dynamic Parameterized Subset Sampling	2024	PODS	5.2571354e-05
10,226	Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance	2026	SIGMOD	5.093636e-05
10,560	Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs	2026	VLDB	5.093636e-05
11,085	Finding Time-Proximity Communities in Temporal Heterogeneous Information Networks	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2,225	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.9183159e-05
2,580	Community Detection in Social Networks: An In-depth Benchmarking Study with a Procedure-Oriented Framework	2015	VLDB	8.3887788e-05
3,616	Parallel Local Graph Clustering	2016	VLDB	7.2559471e-05
4,024	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.9479974e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,497	Leveraging History for Faster Sampling of Online Social Networks	2015	VLDB
2	1,163	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD
3	5,741	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD
4	945	Fast Personalized PageRank on MapReduce	2011	SIGMOD
5	1,396	Estimating PageRank on Graph Streams	2008	PODS
6	6,284	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD
7	8,063	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB
8	556	Fast Incremental and Personalized PageRank	2011	VLDB
9	9,373	Efficient and Accurate PageRank Approximation on Large Graphs	2024	SIGMOD
10	8,062	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD