# Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs

arXiv: https://arxiv.org/abs/2103.03561 · HTML: https://mlsanity.com/paper/2103.03561/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 66 references that are in the map.
- First posted on arXiv 5 Mar 2021.

## Builds on (most cited first, 16 of 16)

- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs](https://mlsanity.com/paper/1501.06087/) (2015)
- [Spectral Clustering of Graphs with the Bethe Hessian](https://mlsanity.com/paper/1406.1880/) (2014)
- [Sparse Quantized Spectral Clustering](https://mlsanity.com/paper/2010.01376/) (2020)
- [A unified framework for spectral clustering in sparse graphs](https://mlsanity.com/paper/2003.09198/) (2020)
- [Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering](https://mlsanity.com/paper/2102.12293/) (2021)
- [Unsupervised feature learning from finite data by message passing: discontinuous versus continuous phase transition](https://mlsanity.com/paper/1608.03714/) (2016)
- [Optimal Laplacian regularization for sparse spectral community detection](https://mlsanity.com/paper/1912.01419/) (2019)
- [Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian](https://mlsanity.com/paper/2006.04510/) (2020)
- [Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/1609.02487/) (2016)
- [Weighted Community Detection and Data Clustering Using Message Passing](https://mlsanity.com/paper/1801.09829/) (2018)
- [Clustering from Sparse Pairwise Measurements](https://mlsanity.com/paper/1601.06683/) (2016)
- [Kernel Spectral Clustering and applications](https://mlsanity.com/paper/1505.00477/) (2015)
- [Node Immunization with Non-backtracking Eigenvalues](https://mlsanity.com/paper/2002.12309/) (2020)

## Built on by (most cited first, 6 of 6)

- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024)
- [When Does Bottom-up Beat Top-down in Hierarchical Community Detection?](https://mlsanity.com/paper/2306.00833/) (2023)
- [Spherical and Hyperbolic Toric Topology-Based Codes On Graph Embedding for Ising MRF Models: Classical and Quantum Topology Machine Learning](https://mlsanity.com/paper/2307.15778/) (2023)
- [Synthetic Image Detection via Spectral Gaps of QC-RBIM Nishimori Bethe-Hessian Operators](https://mlsanity.com/paper/2508.19698/) (2025)
- [Kohn-Sham Spectral Embedding on Sparse Graphs at the Nishimori Temperature for Image Classification](https://mlsanity.com/paper/2607.28428/) (2026)

## Abstract (arXiv)

This article unveils a new relation between the Nishimori temperature parametrizing a distribution P and the Bethe free energy on random Erdos-Renyi graphs with edge weights distributed according to P. Estimating the Nishimori temperature being a task of major importance in Bayesian inference problems, as a practical corollary of this new relation, a numerical method is proposed to accurately estimate the Nishimori temperature from the eigenvalues of the Bethe Hessian matrix of the weighted graph. The algorithm, in turn, is used to propose a new spectral method for node classification in weighted (possibly sparse) graphs. The superiority of the method over competing state-of-the-art approaches is demonstrated both through theoretical arguments and real-world data experiments.