mlsanityData to 7 Oct 2026

Heat kernel based community detection

arXiv 1403.3148 ↗First posted 13 Mar 2014cs.SI cs.DS physics.soc-phcited by 30

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 9; 2023: 6; 2024: 4; 2025: 4; 2026: 2.

30 papers.

Sort:

By area:

  1. 2021Local Clustering in Contextual Multi-Armed Banditscited by 29
  2. 2022Geometric Knowledge Distillation: Topology Compression for Graph Neural Networkscited by 22
  3. 2021A Survey on Echo Chambers on Social Media: Description, Detection and Mitigationcited by 11
  4. 2023General Graph Random Featurescited by 10
  5. 2023Quasi-Monte Carlo Graph Random Featurescited by 9
  6. 2024Linear Transformer Topological Masking with Graph Random Featurescited by 7
  7. 2023Repelling Random Walkscited by 6
  8. 2022A Compressed Sensing Based Least Squares Approach to Semi-supervised Local Cluster Extractioncited by 4
  9. 2022Finding Bipartite Components in Hypergraphscited by 4
  10. 2024Differentially Private Graph Diffusion with Applications in Personalized PageRankscited by 4
  11. 2026Efficient Estimation of Kernel Surrogate Models for Task Attributioncited by 4
  12. 2022Graph-based Semi-supervised Local Clustering with Few Labeled Nodescited by 3
18 more
  1. 2021Scalable Deep Graph Clustering with Random-walk based Self-supervised Learningcited by 2
  2. 2022Scalable and Effective Conductance-based Graph Clusteringcited by 2
  3. 2024Faster Local Solvers for Graph Diffusion Equationscited by 2
  4. 2025Adaptive Local Clustering over Attributed Graphscited by 2
  5. 2023Graph Neural Network Surrogates of Fair Graph Filteringcited by 1
  6. 2025Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methodscited by 1
  7. 2021Structure Amplification on Multi-layer Stochastic Block Modelscited by 0
  8. 2021Uncovering the Local Hidden Community Structure in Social Networkscited by 0
  9. 2022Stratified Graph Spectracited by 0
  10. 2022A flexible PageRank-based graph embedding framework closely related to spectral eigenvector embeddingscited by 0
  11. 2022Bayesian Inference of Transition Matrices from Incomplete Graph Data with a Topological Priorcited by 0
  12. 2022On Learning the Structure of Clusters in Graphscited by 0
  13. 2023An Evolution Kernel Method for Graph Classification through Heat Diffusion Dynamicscited by 0
  14. 2023Random Walk on Multiple Networkscited by 0
  15. 2024Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approachcited by 0
  16. 2025Cohesive Group Discovery in Interaction Graphs under Explicit Density Constraintscited by 0
  17. 2025Efficiently Learning Branching Networks for Multitask Algorithmic Reasoningcited by 0
  18. 2026Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Modelscited by 0