# Spectral Clustering of Graphs with the Bethe Hessian

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2014.

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

- [A Neural Collapse Perspective on Feature Evolution in Graph Neural Networks](https://mlsanity.com/paper/2307.01951/) (2023)
- [Learning Parametrised Graph Shift Operators](https://mlsanity.com/paper/2101.10050/) (2021)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Optimal Algorithms for the Inhomogeneous Spiked Wigner Model](https://mlsanity.com/paper/2302.06665/) (2023)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs](https://mlsanity.com/paper/2103.03561/) (2021)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Spectral Phase Transition and Optimal PCA in Block-Structured Spiked models](https://mlsanity.com/paper/2403.03695/) (2024)
- [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024)
- [Explainable Graph Spectral Clustering of Text Documents](https://mlsanity.com/paper/2308.00504/) (2023)
- [Consistency between ordering and clustering methods for graphs](https://mlsanity.com/paper/2208.12933/) (2022)
- [Understanding the Behavior of Belief Propagation](https://mlsanity.com/paper/2209.05464/) (2022)
- [When Does Bottom-up Beat Top-down in Hierarchical Community Detection?](https://mlsanity.com/paper/2306.00833/) (2023)
- [Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering](https://mlsanity.com/paper/2207.14589/) (2022)
- [A Spectral Framework for Tracking Communities in Evolving Networks](https://mlsanity.com/paper/2412.07378/) (2024)
- [Complex non-backtracking matrix for directed graphs](https://mlsanity.com/paper/2507.12503/) (2025)
- [Synthetic Image Detection via Spectral Gaps of QC-RBIM Nishimori Bethe-Hessian Operators](https://mlsanity.com/paper/2508.19698/) (2025)
- [Diffusion-Guided Feature Selection via Nishimori Temperature: Noise-Based Spectral Embedding](https://mlsanity.com/paper/2604.24692/) (2026)
- [Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models](https://mlsanity.com/paper/2605.28488/) (2026)
- [Kohn-Sham Spectral Embedding on Sparse Graphs at the Nishimori Temperature for Image Classification](https://mlsanity.com/paper/2607.28428/) (2026)
- [Accelerating Dynamic Graph Clustering on GPU Architectures with cuGraph](https://mlsanity.com/paper/2608.03695/) (2026)
- [Learning and Clustering on Temporal Graphs: Principles, Primitives, and Pooling](https://mlsanity.com/paper/2608.03696/) (2026)
- [The Limits of Query Monitoring against Distributed Model Extraction](https://mlsanity.com/paper/2610.13083/) (2026)

## Abstract (arXiv)

Spectral clustering is a standard approach to label nodes on a graph by studying the (largest or lowest) eigenvalues of a symmetric real matrix such as e.g. the adjacency or the Laplacian. Recently, it has been argued that using instead a more complicated, non-symmetric and higher dimensional operator, related to the non-backtracking walk on the graph, leads to improved performance in detecting clusters, and even to optimal performance for the stochastic block model. Here, we propose to use instead a simpler object, a symmetric real matrix known as the Bethe Hessian operator, or deformed Laplacian. We show that this approach combines the performances of the non-backtracking operator, thus detecting clusters all the way down to the theoretical limit in the stochastic block model, with the computational, theoretical and memory advantages of real symmetric matrices.