betaFeedback

WorksMathematics

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>1d>1. This extends previous recovery guarantees, which required dd 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×nn\times 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.

Introduction

The stochastic block model is a canonical test case for partitioning algorithms. Vertices are assigned planted community labels, and edges are generated independently with probabilities based on the relationship between communities [16]. Studying recovery of the different communities has a rich history, with applications in many areas, including social network analysis, computational biology, and neuroscience [3, 15, 16].

In the sparse regime, a central question has been when the planted communities can be detected at fixed expected degree. Here we focus on weak recovery, that is, having a strictly non-negligible advantage over random guessing. Exact recovery is information-theoretically impossible, as, for example, some vertices are isolated. A natural benchmark is given by the Kesten–Stigum threshold (see Theorem 2.1), above which linear estimators using the planted labels on distant generations of the limiting tree retain nonvanishing correlation with a label statistic at the root [21]. This threshold is information-theoretically sharp for weak recovery in the symmetric two-community model [19, 21, 22], and it is conjectured to be tight for efficient algorithms for any fixed number of symmetric communities [1, 11, 21], although information-theoretic recovery can be possible below it [2, 10].

Following predictions from statistical physics [11], efficient algorithms for weak recovery were developed that reach the Kesten–Stigum threshold in the symmetric two-community model [19, 22]. In parallel, the idea of spectral redemption showed how the non-backtracking operator could overcome the limitations of standard spectral methods in sparse graphs, and planted communities could be recovered from its eigenvectors [18]. Its ability to reach the Kesten–Stigum threshold was subsequently established rigorously [9].

The non-backtracking operator is non-Hermitian, however, and is indexed by directed edges rather than vertices, meaning it can be much larger. These features motivated the study of a smaller Hermitian alternative, the Bethe Hessian, coming from statistical physics [24].

For a graph GG with adjacency matrix AA and degree matrix DD, the Bethe Hessian is

H(t,G):=(t2−1)I+D−tA.H(t,G) := (t^2 - 1)I + D - tA.

From a physical perspective, the Bethe Hessian describes the change in the Bethe free energy when we add a small bias to the random variables. Negative eigenvalues therefore give directions in which adding a bias decreases the Bethe free energy [24]. Moreover, the Ihara–Bass formula gives a relationship between the determinants of the non-backtracking operator and the Bethe Hessian [7].

Early numerical experiments suggested that the negative eigenvalues and corresponding eigenvectors of the Bethe Hessian reveal the latent structure of the stochastic block model [24]. Rigorous analysis subsequently established that the negative outliers count the informative directions when the common expected degree satisfies d≥2d \ge2, and that their eigenvectors yield weak recovery for sufficiently large dd [26]. The outlier count was later extended to every fixed d>1d > 1, while weak recovery from the corresponding eigenvectors remained open throughout this full range [12]. Bethe Hessian methods have also been used to obtain robust recovery above the Kesten–Stigum threshold [20], through a method combining degree truncation with a “boosted” version of the Bethe Hessian given by multiplying the Bethe Hessian on both sides by a matrix counting non-backtracking walks, and additional subspace processing. In comparison, our result concerns the informative eigenspaces of the matrices H(d,G)H(\sqrt{d},G) and H(−d,G)H(-\sqrt{d},G) themselves.

In this work, we identify the Bethe Hessian’s limiting outlier eigenvalue locations and prove that their eigenvectors retain the planted signal. We describe the informative eigenvectors and use them to prove weak recovery throughout the fixed-degree regime. Consider a stochastic block model with fixed parameters, common expected degree d>1d > 1, and mean offspring matrix QQ. A planted eigenvalue μ\mu is called informative when ∣μ∣>d|\mu| > \sqrt{d}; positive and negative informative directions correspond to H(d,G)H(\sqrt{d},G) and H(−d,G)H(-\sqrt{d},G), respectively. The following is an informal version of what we are able to show; the full versions are given as Theorem 2.2 and Theorem 2.3.

Theorem 1.1 (Informal). For every fixed d>1d > 1, informative Bethe Hessian eigenspaces have nonvanishing overlap with the corresponding planted eigenspaces. Whenever a nonconstant planted direction is informative, a randomized rounding of the informative spectral coordinates achieves weak recovery.

The construction also gives a recursive formula for the limiting outlier locations. This closes the gap between counting informative outliers and using their eigenvectors for recovery, showing that a spectral algorithm based on n×nn \times n Hermitian matrices reaches the Kesten–Stigum threshold without requiring the expected degree to tend to infinity. Weak recovery is only information theoretically possible when d>1d > 1 [21, 23], as otherwise the local limit Poisson tree is finite almost surely.

The main difficulty in passing to the sparse regime is that large fluctuations cause the eigenvector to have highly irregular structure. Previous works found well-behaved test vectors that identified negative quadratic forms, but still relied on some level of local approximation [12, 26]. Such approximations were too rough to guarantee the structure of true eigenvectors. We instead construct approximate eigenvectors with vanishing residual and nonvanishing planted correlation. Together with the outlier count, these properties identify the informative eigenspaces throughout the fixed-degree regime.

The key point is that a planted direction above the Kesten–Stigum threshold gives rise to a negative outlier of the finite-graph Bethe Hessian. Therefore, we are looking for a solution to

(H(t,G)+δI)ϕ=0,δ>0.(H(t,G) + \delta I)\phi= 0,\qquad\delta> 0.

Because this outlier is created by the global planted structure, it is absent from the spectrum of the operator on the local limit. Rather than inverting the singular finite-graph matrix at this eigenvalue, we create weights using the well-defined limiting resolvent (H(t,T)+δI)−1(H(t,T) + \delta I)^{-1}. For the equal-expected-degree model considered here, the unmarked local limit TT is a Poisson Galton–Watson tree with mean offspring dd.

The second insight is that these Green’s function weights, together with the planted label field on the tree, can be used to identify the informative eigenspace. The tree resolvent supplies weights adapted to the local geometry, while the label field supplies the planted direction. Iterating this construction gives approximations that are consistent across neighboring vertices and satisfy the eigenvector equation in the limit.

To explain the weights, suppose ϕ\phi is an eigenvector of H(t,G)H(t,G) with eigenvalue −δ-\delta. Then, for every u∈V(G)u \in V(G),

(t2−1+deg⁡(u)+δ)ϕ(u)=t∑w∼uϕ(w).(t^2 - 1 + \operatorname{deg}(u) + \delta)\phi(u) = t \sum_{w \sim u} \phi(w).

For every v∼uv \sim u, whenever the relevant entries are nonzero, writing formally Γu(v)=ϕ(u)/ϕ(v)\Gamma_u^{(v)} = \phi(u)/\phi(v) gives

Γu(v)=1t+t−1(deg⁡(u)−1+δ)−∑w∼uw≠vΓw(u).(1)\Gamma_u^{(v)} = \frac{1}{t + t^{-1}(\operatorname{deg}(u) - 1 + \delta) - \sum_{\substack{w \sim u \\ w \ne v}} \Gamma_w^{(u)}}. \tag*{(1)}

We then perform this same recursion on the infinite local limit. There, the weights are defined by the Green’s function rather than by ratios of a pre-existing eigenvector:

Γu(v)=t⟨eu,(H(t,Tu(v))+δI)−1eu⟩,\Gamma_u^{(v)} = t \left\langle e_u, \left(H(t,T_u^{(v)}) + \delta I\right)^{-1} e_u \right\rangle,

where Tu(v)T_u^{(v)} is the branch containing uu after removing the edge {u,v}\{u,v\}. Here H(t,Tu(v))H(t,T_u^{(v)}) denotes the restriction of H(t,T)H(t,T) to that branch, so its diagonal retains the degrees in TT. With this convention, (1) is exactly the Schur complement formula. Starting with Γu(v)=0\Gamma_u^{(v)} = 0 at a finite-depth boundary and recursively updating gives finite-neighborhood approximations to these weights.

The local limit is a Poisson tree, which has branching structure and independence properties we can exploit. The independence between forward subtrees makes the Green’s function recursion a closed distributional system, known as a recursive distributional equation (RDE). Such equations have been used to characterize limiting Stieltjes transforms and prove convergence of empirical spectral measures for locally convergent random graphs [8]. Related Green’s function methods have also been developed to study absolutely continuous spectrum on trees [4, 6, 17]. Here we use individual Green’s function entries to construct approximate eigenvectors, with decay estimates allowing the weights to be approximated from finite neighborhoods.

Another advantage of considering the infinite tree is that H(t,T)H(t,T) is positive semidefinite for t∈(−∞,−1]∪[1,∞)t \in(-\infty,-1] \cup[1,\infty). Therefore, for δ>0\delta> 0, its shifted inverse is well defined and bounded. This provides a canonical choice of weights; the further decay and approximation estimates are what allow us to use them on the finite graph.

Given the weights Γu(v)\Gamma_u^{(v)}, we want to convert them into an eigenvector induced by the graph. To do this, we consider the planted labels as a Markov random field on the limiting tree. We go to some fixed depth LL and take a weighted sum of the planted values that we see there, with each weight given by a product of weights along the path to that vertex. Our goal is to show that this estimation is stable. We therefore introduce an operator L\mathcal{L}, which describes the change in the weighted construction when we pass from level LL to level L+1L+1. For a suitable δ\delta, the relevant weighted average is preserved across levels. This stability allows the local approximations to satisfy the eigenvector equation in the limit.

In terms of the correct δ\delta, we have two conflicting parts that must balance out. The first is the rate of decay of covariance in the planted label field. Specifically, for a normalized planted label function associated with an eigenvalue μ\mu, the covariance on the broadcast tree is (μ/d)dist⁡(x,y)(\mu/d)^{\operatorname{dist}(x,y)}. To counteract this, we choose the Green’s function weights so that the weighted signal remains at a stable scale. Heuristically, if the geometric average of edge weights is gg, then the dℓd^\ell vertices in expectation at depth ℓ\ell would contribute a signal of order

dℓ(μd)ℓgℓ=(μg)ℓ.d^\ell\left(\frac{\mu}{d}\right)^\ell g^\ell= (\mu g)^\ell.

Thus the matching weight would be g=1/μg = 1/\mu. If δ\delta were smaller, the positive Green’s function weights would be larger and the local formula for the eigenvector would not converge. If δ\delta were larger, the Green’s function would decay too quickly and the planted signal would disappear in the limit. At the correct δ\delta, the signal survives at a stable scale, allowing the approximations at neighboring vertices to describe the same eigenvector.

Previous analyses have used vectors derived from the Ihara-Bass formula and known structure of outlier eigenvectors of the non-backtracking operator, either directly [26] or adapted to the outlier eigenvalue [12]. In this work, we allow the weights to depend on both the local geometry and the spectral shift δ\delta. An appealing part of this approach is that it suggests a route to other models: construct the Green’s function weights on the local limit, and the outlier eigenvalue corresponds to the shift that matches the planted signal.

AI Acknowledgment: OpenAI’s GPT-6 introduced the key analytic tools used in this argument. Specifically, the authors recently wrote a paper [12] that recovered the number of outlier eigenvalues using a test function based on the local Markov random field. They gave this paper to GPT 6-Astra and asked whether these ideas could be used to achieve eigenvector recovery. The response was a version of the general argument suggested here: to build a recursion based on the eigenvector equation and build test vectors based on this recursion. The authors realized that this was a Green’s function recursion and, taking the GPT-6 argument as a preliminary draft, substantially restructured the paper with the relevant history and techniques given this interpretation. GPT-6 was further used to provide feedback on the manuscript and simplify explication.

Main Results

The Stochastic Block Model

Given a symmetric nonnegative matrix P∈Rr×rP \in\mathbb{R}^{r \times r} and a distribution π\pi over [r][r] for r≥2r \ge2 fixed, the stochastic block model SBMn(P,π)\mathrm{SBM}_n(P,\pi) generates a random graph GG on nn vertices as follows:

  1. Fix a label map σ:[n]→[r]\sigma: [n] \to[r] such that ∣σ−1(i)∣=πin|\sigma^{-1}(i)| = \pi_i n for every i∈[r]i \in[r].

  1. For every pair of vertices u,v∈[n]u,v \in[n], include the edge uvuv independently with probability 1nPσ(u),σ(v)\frac{1}{n}P_{\sigma(u),\sigma(v)}.

The goal is to show when it is possible to detect the original communities. Specifically, we will focus on the sparse regime, where the expected degree of each vertex is constant.

Throughout, we assume that all vertices in GG have the same expected degree d>1d > 1, i.e.,

d:=∑j=1rPijπj>1is the same for all i∈[r].(2)d := \sum_{j=1}^{r} P_{ij}\pi_j > 1 \qquad\text{is the same for all } i \in[r]. \tag*{(2)}

The restriction d>1d > 1 is necessary, as the weak-recovery threshold is at least 1.

Informative eigenvalues

Given SBMn(P,π)\mathrm{SBM}_n(P,\pi), define the signal matrix Q:=PΠQ := P\Pi, where Π:=diag⁡(π1,…,πr)\Pi:= \operatorname{diag}(\pi_1,\ldots,\pi_r). Note that Qij=PijπjQ_{ij} = P_{ij}\pi_j represents the expected number of neighbors in community jj of a vertex in community ii.

As QQ is similar to Π1/2PΠ1/2\Pi^{1/2}P\Pi^{1/2}, it has real eigenvalues. We order the eigenvalues of QQ by absolute value as

d=μ1≥∣μ2∣≥⋯≥∣μr∣.(3)d = \mu_1 \ge|\mu_2| \ge\cdots\ge|\mu_r|. \tag*{(3)}

Definition 2.1. An eigenvalue μ\mu of the signal matrix QQ is informative if μ2>d\mu^2 > d. The model is above the Kesten–Stigum threshold if there is an informative eigenfunction orthogonal to the constant function in L2(π)L^2(\pi).

This is the natural threshold for linear reconstruction on the local Galton–Watson tree. For a nonzero eigenvalue μi\mu_i, the corresponding eigenfunction sums at depth ℓ\ell, normalized by μiℓ\mu_i^\ell, form a martingale whose increment variances are proportional to (d/μi2)ℓ(d/\mu_i^2)^\ell. These variances are summable precisely when μi2>d\mu_i^2>d, so the normalized signal has bounded second moment exactly above this threshold. Thus, r+r_+ and r−r_- are the numbers of positive and negative informative eigenvalues, respectively.

Our result

Let Gn∼SBMn(P,π)G_n\sim\mathrm{SBM}_n(P,\pi), where the fixed parameters satisfy (2). Let QQ be the mean offspring matrix, and choose real eigenfunctions Qφi=μiφiQ\varphi_i=\mu_i\varphi_i orthonormal in L2(π)L^2(\pi), with φ1∝1\varphi_1\propto1. Write

Xi(u):=φi(σ(u)).X_i(u):=\varphi_i(\sigma(u)).

Thus ⟨Xi,Xj⟩=n1{i=j}\langle X_i,X_j\rangle=n\mathbf{1}_{\{i=j\}} under our deterministic community-size convention. Positive and negative planted eigenvalues are treated using H(d,Gn)H(\sqrt{d},G_n) and H(−d,Gn)H(-\sqrt{d},G_n), respectively.

The number of negative outliers is known throughout the fixed-degree regime d>1d>1 [12], while weak recovery from the eigenvectors was previously established for sufficiently large dd [26]. Our first result identifies the corresponding eigenspaces throughout the fixed-degree regime. We construct vectors from the planted labels in local neighborhoods, with weights given by the Green’s function on the limiting tree, and show that these vectors approximate the actual Bethe-Hessian eigenspaces. This also gives the limiting outlier locations and the overlap with the planted directions.

References

  1. [1]Emmanuel Abbe, Community detection and stochastic block models: recent developments, Journal of Machine Learning Research 18 (2018), no. 177, 1–86.
  2. [2]Emmanuel Abbe and Colin Sandon, Proof of the achievability conjectures for the general stochastic block model, Communications on Pure and Applied Mathematics 71 (2018), no. 7, 1334–1406.DOI
  3. [3]Edoardo M Airoldi, David M Blei, Stephen E Fienberg, and Eric P Xing, Mixed membership stochastic blockmodels, Journal of Machine Learning Research 9 (2008), no. 65, 1981–2014.
  4. [4]Michael Aizenman, Robert Sims, and Simone Warzel, Stability of the absolutely continuous spectrum of random Schrödinger operators on tree graphs, Probability Theory and Related Fields 136 (2006), no. 3, 363–394.DOI
  5. [5]Michael Aizenman and Simone Warzel, Resonant delocalization for random Schrödinger operators on tree graphs, Journal of the European Mathematical Society 15 (2013), no. 4, 1167–1222.
  6. [6]Adam Arras and Charles Bordenave, Existence of absolutely continuous spectrum for Galton–Watson random trees, Communications in Mathematical Physics 403 (2023), no. 1, 495–527.arxiv.org/abs/2105.10177
  7. [7]Hyman Bass, The Ihara–Selberg zeta function of a tree lattice, International Journal of Mathematics 3 (1992), no. 6, 717–797.DOI
  8. [8]Charles Bordenave and Marc Lelarge, Resolvent of large random graphs, Random Structures & Algorithms 37 (2010), no. 3, 332–352.
  9. [9]Charles Bordenave, Marc Lelarge, and Laurent Massoulié, Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs, Ann. Probab. 46 (2018), no. 1, 1–71. MR 3758726
  10. [10]Byron Chin, Elchanan Mossel, Youngtak Sohn, and Alexander S. Wein, Stochastic block models with many communities and the Kesten–Stigum bound—extended abstract, Proceedings of Thirty Eighth Conference on Learning Theory (Nika Haghtalab and Ankur Moitra, eds.), Proceedings of Machine Learning Research, vol. 291, PMLR, 2025, pp. 1253–1258.arxiv.org/abs/2503.03047
  11. [11]Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Physical Review E 84 (2011), no. 6, 066106.DOI
  12. [12]Dingding Dong and Theo McKenzie, The Bethe–Hessian down to the percolation threshold, arXiv preprint arXiv:2608.16672 (2026).arxiv.org/abs/2608.16672
  13. [13]László Erdős and Horng-Tzer Yau, A dynamical approach to random matrix theory, Courant Lecture Notes in Mathematics, vol. 28, Courant Institute of Mathematical Sciences and American Mathematical Society, 2017.DOI
  14. [14]Stewart N. Ethier and Thomas G. Kurtz, Markov processes: Characterization and convergence, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, 1986.
  15. [15]Joshua Faskowitz, Xiaoran Yan, Xi-Nian Zuo, and Olaf Sporns, Weighted stochastic block models of the human connectome across the life span, Scientific Reports 8 (2018), no. 1, 12997.DOI
  16. [16]Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Lein​​hardt, Stochastic blockmodels: First steps, Social Networks 5 (1983), no. 2, 109–137.DOI
  17. [17]Matthias Keller, Daniel Lenz, and Simone Warzel, Absolutely continuous spectrum for random operators on trees of finite cone type, Journal d’Analyse Mathématique 118 (2012), no. 1, 363–396.arxiv.org/abs/1108.0057
  18. [18]Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang, Spectral redemption in clustering sparse networks, Proceedings of the National Academy of Sciences 110 (2013), no. 52, 20935–20940.DOI
  19. [19]Laurent Massoulié, Community detection thresholds and the weak Ramanujan property, Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2014, pp. 694–703.arxiv.org/abs/1311.3085
  20. [20]Sidhant Mohanty, Prasad Raghavendra, and David X. Wu, Robust recovery for stochastic block models, simplified and generalized, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2024, pp. 367–374.arxiv.org/abs/2402.13921
  21. [21]Elchanan Mossel, Joe Neeman, and Allan Sly, Reconstruction and estimation in the planted partition model, Probability Theory and Related Fields 162 (2015), no. 3–4, 431–461.DOI
  22. [22]———, A proof of the block model threshold conjecture, Combinatorica 38 (2018), no. 3, 665–708.arxiv.org/abs/1311.4115
  23. [23]Elchanan Mossel, Allan Sly, and Youngtak Sohn, Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 2062–2073.arxiv.org/abs/2406.15957
  24. [24]Alaa Saade, Florent Krzakala, and Lenka Zdeborová, Spectral clustering of graphs with the Bethe Hessian, Advances in Neural Information Processing Systems, vol. 27, 2014, pp. 406–414.DOI
  25. [25]Helmut H. Schaefer and Manfred P. Wolff, Topological vector spaces, 2 ed., Graduate Texts in Mathematics, vol. 3, Springer, 1999.
  26. [26]Ludovic Stephan and Yizhe Zhu, Community detection with the Bethe-Hessian, Proceedings of Thirty Eighth Conference on Learning Theory (Nika Haghtalab and Ankur Moitra, eds.), Proceedings of Machine Learning Research, vol. 291, PMLR, 2025, pp. 5352–5353.arxiv.org/abs/2411.02835

Paper details

vlnc:W_xn7afmm9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents