# Community detection with the Bethe-Hessian

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 62 references that are in the map.
- First posted on arXiv 5 Nov 2024.

## Builds on (most cited first, 24 of 24)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Concentration and regularization of random graphs](https://mlsanity.com/paper/1506.00669/) (2015)
- [Spectral Clustering of Graphs with the Bethe Hessian](https://mlsanity.com/paper/1406.1880/) (2014)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery](https://mlsanity.com/paper/1501.05021/) (2015)
- [The Kikuchi Hierarchy and Tensor PCA](https://mlsanity.com/paper/1904.03858/) (2019)
- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [Fundamental Limits of Spectral Clustering in Stochastic Block Models](https://mlsanity.com/paper/2301.09289/) (2023)
- [Graph powering and spectral robustness](https://mlsanity.com/paper/1809.04818/) (2018)
- [Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices](https://mlsanity.com/paper/1811.12804/) (2018)
- [Estimating the number of communities in networks by spectral methods](https://mlsanity.com/paper/1507.00827/) (2015)
- [A unified framework for spectral clustering in sparse graphs](https://mlsanity.com/paper/2003.09198/) (2020)
- [Robustness of spectral methods for community detection](https://mlsanity.com/paper/1811.05808/) (2018)
- [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)
- [Robust recovery for stochastic block models, simplified and generalized](https://mlsanity.com/paper/2402.13921/) (2024)
- [Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold](https://mlsanity.com/paper/2006.07695/) (2020)
- [Matrix Completion from Fewer Entries: Spectral Detectability and Rank Estimation](https://mlsanity.com/paper/1506.03498/) (2015)
- [Spectral Inference Methods on Sparse Graphs: Theory and Applications](https://mlsanity.com/paper/1610.04337/) (2016)
- [Determining the Number of Communities in Sparse and Imbalanced Settings](https://mlsanity.com/paper/2406.04423/) (2024)

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

- [Phase Transition for Stochastic Block Model with more than √n Communities (II)](https://mlsanity.com/paper/2511.21526/) (2025)
- [Phase Transition for Stochastic Block Model with more than √n Communities](https://mlsanity.com/paper/2509.15822/) (2025)
- [Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model](https://mlsanity.com/paper/2604.20907/) (2026)

## Abstract (arXiv)

The Bethe-Hessian matrix, introduced by Saade, Krzakala, and Zdeborov'a (2014), is a Hermitian matrix designed for applying spectral clustering algorithms to sparse networks. Rather than employing a non-symmetric and high-dimensional non-backtracking operator, a spectral method based on the Bethe-Hessian matrix is conjectured to also reach the Kesten-Stigum detection threshold in the sparse stochastic block model (SBM). We provide the first rigorous analysis of the Bethe-Hessian spectral method in the SBM under both the bounded expected degree and the growing degree regimes. Specifically, we demonstrate that: (i) When the expected degree d≥ 2, the number of negative outliers of the Bethe-Hessian matrix can consistently estimate the number of blocks above the Kesten-Stigum threshold, thus confirming a conjecture from Saade, Krzakala, and Zdeborov'a (2014) for d≥ 2. (ii) For sufficiently large d, its eigenvectors can be used to achieve weak recovery. (iii) As d→∞, we establish the concentration of the locations of its negative outlier eigenvalues, and weak consistency can be achieved via a spectral method based on the Bethe-Hessian matrix.