Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs. (24th September 2021)

• Record Type: Journal Article
• Authors: Dall'Amico, Lorenzo; Couillet, Romain; Tremblay, Nicolas
• Is Part Of: Journal of statistical mechanics. (2021:Sep.)
• Publication Date: 2021-09-24
• Subjects: clustering techniques -- inference of graphical models -- machine learning -- random matrix theory and extensions; Statistical mechanics -- Periodicals; Mechanics -- Statistical methods -- Periodicals; 530.1305
• DOI: 10.1088/1742-5468/ac21d3
• Languages: English
• ISSNs: 1742-5468

Abstract

Abstract: This article unveils a new relation between the Nishimori temperature parametrizing a distribution P and the Bethe free energy on random Erdős–Rényi 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.