Bethe Hessian Recovery through the Kesten-Stigum Regime
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\times n$ matrices. To do this, we…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.41802
curl -X POST /api/v1/records/arxiv/2610.41802/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.41802/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'