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

Abstract

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.

References in corpus (23)

• Emergence of scaling in random networks
• Large Scale GAN Training for High Fidelity Natural Image Synthesis
• Spectral redemption: clustering sparse networks
• Statistical physics of inference: Thresholds and algorithms
• The Nishimori line and Bayesian Statistics
• Random-bond Ising model in two dimensions, the Nishimori line, and supersymmetry
• Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
• Strong-disorder paramagnetic-ferromagnetic fixed point in the square-lattice +- J Ising model
• Spectral Clustering of Graphs with the Bethe Hessian
• Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation
• Absence of Replica Symmetry Breaking in a Region of the Phase Diagram of the Ising Spin Glass
• Unsupervised feature learning from finite data by message passing: discontinuous versus continuous phase transition
• Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
• Clustering from Sparse Pairwise Measurements
• Node Immunization with Non-backtracking Eigenvalues
• Weighted Community Detection and Data Clustering Using Message Passing
• A unified framework for spectral clustering in sparse graphs
• Loopy Belief Propagation, Bethe Free Energy and Graph Zeta Function
• Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
• Sparse Quantized Spectral Clustering
• Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering
• Non-backtracking spectra of weighted inhomogeneous random graphs
• Construction of optimal spectral methods in phase retrieval

Cited by in corpus (5)

• Political Context of the European Vaccine Debate on Twitter
• A unified framework for spectral clustering in sparse graphs
• Analyticity of the energy in an Ising spin glass with correlated disorder
• When Does Bottom-up Beat Top-down in Hierarchical Community Detection?
• Construction of optimal spectral methods in phase retrieval