# Heat kernel based community detection

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2014.

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

- [Local Clustering in Contextual Multi-Armed Bandits](https://mlsanity.com/paper/2103.00063/) (2021)
- [Geometric Knowledge Distillation: Topology Compression for Graph Neural Networks](https://mlsanity.com/paper/2210.13014/) (2022)
- [A Survey on Echo Chambers on Social Media: Description, Detection and Mitigation](https://mlsanity.com/paper/2112.05084/) (2021)
- [General Graph Random Features](https://mlsanity.com/paper/2310.04859/) (2023)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Linear Transformer Topological Masking with Graph Random Features](https://mlsanity.com/paper/2410.03462/) (2024)
- [Repelling Random Walks](https://mlsanity.com/paper/2310.04854/) (2023)
- [A Compressed Sensing Based Least Squares Approach to Semi-supervised Local Cluster Extraction](https://mlsanity.com/paper/2202.02904/) (2022)
- [Finding Bipartite Components in Hypergraphs](https://mlsanity.com/paper/2205.02771/) (2022)
- [Differentially Private Graph Diffusion with Applications in Personalized PageRanks](https://mlsanity.com/paper/2407.00077/) (2024)
- [Efficient Estimation of Kernel Surrogate Models for Task Attribution](https://mlsanity.com/paper/2602.03783/) (2026)
- [Graph-based Semi-supervised Local Clustering with Few Labeled Nodes](https://mlsanity.com/paper/2211.11114/) (2022)
- [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)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Adaptive Local Clustering over Attributed Graphs](https://mlsanity.com/paper/2503.20488/) (2025)
- [Graph Neural Network Surrogates of Fair Graph Filtering](https://mlsanity.com/paper/2303.08157/) (2023)
- [Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods](https://mlsanity.com/paper/2504.19419/) (2025)
- [Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning](https://mlsanity.com/paper/2512.01113/) (2025)
- [Structure Amplification on Multi-layer Stochastic Block Models](https://mlsanity.com/paper/2108.00127/) (2021)
- [Uncovering the Local Hidden Community Structure in Social Networks](https://mlsanity.com/paper/2112.04100/) (2021)
- [Stratified Graph Spectra](https://mlsanity.com/paper/2201.03696/) (2022)
- [A flexible PageRank-based graph embedding framework closely related to spectral eigenvector embeddings](https://mlsanity.com/paper/2207.11321/) (2022)
- [Bayesian Inference of Transition Matrices from Incomplete Graph Data with a Topological Prior](https://mlsanity.com/paper/2210.15410/) (2022)
- [On Learning the Structure of Clusters in Graphs](https://mlsanity.com/paper/2212.14345/) (2022)
- [An Evolution Kernel Method for Graph Classification through Heat Diffusion Dynamics](https://mlsanity.com/paper/2306.14688/) (2023)
- [Random Walk on Multiple Networks](https://mlsanity.com/paper/2307.01637/) (2023)
- [Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach](https://mlsanity.com/paper/2412.10789/) (2024)
- [Cohesive Group Discovery in Interaction Graphs under Explicit Density Constraints](https://mlsanity.com/paper/2508.04174/) (2025)
- [Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models](https://mlsanity.com/paper/2605.28488/) (2026)

## Abstract (arXiv)

The heat kernel is a particular type of graph diffusion that, like the much-used personalized PageRank diffusion, is useful in identifying a community nearby a starting seed node. We present the first deterministic, local algorithm to compute this diffusion and use that algorithm to study the communities that it produces. Our algorithm is formally a relaxation method for solving a linear system to estimate the matrix exponential in a degree-weighted norm. We prove that this algorithm stays localized in a large graph and has a worst-case constant runtime that depends only on the parameters of the diffusion, not the size of the graph. Our experiments on real-world networks indicate that the communities produced by this method have better conductance than those produced by PageRank, although they take slightly longer to compute on large graphs. On a real-world community identification task, the heat kernel communities perform better than those from the PageRank diffusion.