Bethe Hessian Recovery through the Kesten-Stigum Regime
Abstract
We show that outlier eigenvectors of the Bethe Hessian achieve weak recovery in the stochastic block model down to the Kesten-Stigum threshold, for every fixed common expected degree d>1. This extends previous recovery guarantees, which required d to be sufficiently large. This threshold is information-theoretically optimal for the symmetric two-community model and is conjectured to mark the limit of efficient recovery in broader symmetric models. Our result matches the recovery guarantees of non-backtracking spectral methods while using Hermitian n× n matrices. To do this, we identify recursive formulas for the negative outlier eigenvalues and show that their eigenspaces have nonvanishing overlap with the corresponding planted eigenspaces. The proof constructs approximate eigenvectors from the planted labels on the limiting Poisson tree, with weights given by its Green's function, and transfers these approximations to the finite graph.
Related
- On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
- The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy
- Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models
- The oriented Kesten--McKay law for random regular digraphs
- Interior Hessian estimates for the quadratic Hessian equation
BibTeX
@misc{dong2026bethe,
title = {{Bethe Hessian Recovery through the Kesten-Stigum Regime}},
author = {Dingding Dong and Theo McKenzie},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41802},
eprint = {2610.41802},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41802},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bethe Hessian Recovery through the Kesten-Stigum Regime
AU - Dingding Dong
AU - Theo McKenzie
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41802
UR - https://arxiv.org/abs/2610.41802
AB - We show that outlier eigenvectors of the Bethe Hessian achieve weak recovery in the stochastic block model down to the Kesten-Stigum threshold, for every fixed common expected degree d>1. This extends previous recovery guarantees, which required d to be sufficiently large. This threshold is information-theoretically optimal for the symmetric two-community model and is conjectured to mark the limit of efficient recovery in broader symmetric models. Our result matches the recovery guarantees of non-backtracking spectral methods while using Hermitian n× n matrices. To do this, we identify recursive formulas for the negative outlier eigenvalues and show that their eigenspaces have nonvanishing overlap with the corresponding planted eigenspaces. The proof constructs approximate eigenvectors from the planted labels on the limiting Poisson tree, with weights given by its Green's function, and transfers these approximations to the finite graph.
ER -