# Efficient Estimation of Heat Kernel PageRank for Local Clustering

arXiv: https://arxiv.org/abs/1904.02707 · HTML: https://mlsanity.com/paper/1904.02707/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2019.

## Built on by (most cited first, 9 of 9)

- [Effective and Scalable Clustering on Massive Attributed Graphs](https://mlsanity.com/paper/2102.03826/) (2021)
- [Learning Based Proximity Matrix Factorization for Node Embedding](https://mlsanity.com/paper/2106.05476/) (2021)
- [Scalable Deep Graph Clustering with Random-walk based Self-supervised Learning](https://mlsanity.com/paper/2112.15530/) (2021)
- [Scalable and Effective Conductance-based Graph Clustering](https://mlsanity.com/paper/2211.12511/) (2022)
- [Adaptive Local Clustering over Attributed Graphs](https://mlsanity.com/paper/2503.20488/) (2025)
- [Optimal Propagation for Graph Neural Networks](https://mlsanity.com/paper/2205.02998/) (2022)
- [Unified Multi-View Orthonormal Non-Negative Graph Based Clustering Framework](https://mlsanity.com/paper/2211.02883/) (2022)
- [Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach](https://mlsanity.com/paper/2412.10789/) (2024)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)

## Abstract (arXiv)

Given an undirected graph G and a seed node s, the local clustering problem aims to identify a high-quality cluster containing s in time roughly proportional to the size of the cluster, regardless of the size of G. This problem finds numerous applications on large-scale graphs. Recently, heat kernel PageRank (HKPR), which is a measure of the proximity of nodes in graphs, is applied to this problem and found to be more efficient compared with prior methods. However, existing solutions for computing HKPR either are prohibitively expensive or provide unsatisfactory error approximation on HKPR values, rendering them impractical especially on billion-edge graphs. In this paper, we present TEA and TEA+, two novel local graph clustering algorithms based on HKPR, to address the aforementioned limitations. Specifically, these algorithms provide non-trivial theoretical guarantees in relative error of HKPR values and the time complexity. The basic idea is to utilize deterministic graph traversal to produce a rough estimation of exact HKPR vector, and then exploit Monte-Carlo random walks to refine the results in an optimized and non-trivial way. In particular, TEA+ offers practical efficiency and effectiveness due to non-trivial optimizations. Extensive experiments on real-world datasets demonstrate that TEA+ outperforms the state-of-the-art algorithm by more than four times on most benchmark datasets in terms of computational time when achieving the same clustering quality, and in particular, is an order of magnitude faster on large graphs including the widely studied Twitter and Friendster datasets.