The Bethe–Hessian matrix, introduced by Saade, Krzakala, and Zdeborová (2014), is a Hermitian operator tailored for spectral clustering on sparse networks. Unlike the non-symmetric, high-dimensional non-backtracking operator, this matrix is conjectured to reach the Kesten–Stigum threshold in the sparse stochastic block model (SBM), yet a fully rigorous analysis of the method has remained open. Beyond its practical utility, this sparse random matrix exhibits a surprising phenomenon called "one-sided eigenvector localization" that has not been fully explained.

We present the first rigorous analysis of the Bethe–Hessian spectral method for the SBM and partially answer some open questions in Saade, Krzakala, and Zdeborová (2014).  Joint work with Ludovic Stephan.