The Bethe-Hessian down to the Percolation Threshold

Abstract

The Bethe-Hessian is a symmetric matrix for which the negative spectrum has been observed to encode the informative structure of sparse stochastic block models. We prove that, in the stochastic block model where all vertices have expected degree $d>1$, the number of negative eigenvalues of the Bethe-Hessian is exactly the number predicted by the eigenvalues of the planted model lying outside the bulk spectrum. The condition $d>1$ is optimal, and matches a regime in which existing spectral approaches based on larger non-Hermitian matrices apply. Our result extends a theorem of Stephan and Zhu, who established the same conclusion under the assumption $d\geq 2$. Our improvement relies on two main ideas. First, we construct test vectors on the $2$-core, where degree fluctuations are substantially smaller, and then extend them to the entire graph while controlling the quadratic form. Second, we construct the test vectors using an isotropic basis of the underlying Markov random field, with coefficients adapted to each relevant planted eigenvalue. This allows us to control the fluctuations of the test vectors throughout the sparse regime.

Disclosure

“onically to the full graph. Acknowledgements. T.M. was supported by a Stanford Science Fellowship. The main idea of the test vectors and analysis were developed by the authors, building upon the prior work [8] as well as methods from [6]. OpenAI’s ChatGPT 5.6 Sol was used to check for errors, simplify explication, and give feedback on the manuscript. 2 Main result 2.1 The Stochastic Block Model Given a symmetric nonnegative matrix P ∈ Rr×r and a distribution π over [r], the stocha”

PDF page 3

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-23T05:20:26.945135Z

Structural counts