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: h2c41d272de318a3f
Venue: SIGMOD
Year: 2019
Pagerank: 5.9093593e-05
Overall Rank: 6,033 | 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,236	Edge-based Local Push for Personalized PageRank	2022	VLDB	6.2171816e-05
5,273	Efficient Estimation of Pairwise Effective Resistance	2023	SIGMOD	6.2007708e-05
6,289	QTCS: Efficient Query-Centered Temporal Community Search	2024	VLDB	5.8224604e-05
8,227	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB	5.3740319e-05
8,629	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.2994494e-05
9,220	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD	5.2056825e-05
9,635	Optimal Dynamic Parameterized Subset Sampling	2024	PODS	5.146966e-05
10,442	Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance	2026	SIGMOD	4.9793485e-05
10,742	Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs	2026	VLDB	4.9793485e-05
11,438	Finding Time-Proximity Communities in Temporal Heterogeneous Information Networks	2025	VLDB	4.9793485e-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,258	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.7385422e-05
2,601	Community Detection in Social Networks: An In-depth Benchmarking Study with a Procedure-Oriented Framework	2015	VLDB	8.2335436e-05
3,688	Parallel Local Graph Clustering	2016	VLDB	7.095356e-05
4,101	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.8073016e-05

Semantically Similar Papers

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