Ising Model on Locally Tree-like Graphs: Uniqueness of Solutions to Cavity Equations

In the study of Ising models on large locally tree-like graphs, in both rigorous and non-rigorous methods one is often led to understanding the so-called belief propagation distributional recursions and its fixed points. We prove that there is at most one non-trivial fixed point for Ising models wit...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2024-03, Vol.70 (3), p.1-1
Main Authors: Yu, Qian, Polyanskiy, Yury
Format: Article
Language:English
Subjects:
Algorithms
Belief propagation
Broadcasting
broadcasting on trees
cavity equations
Convergence
Degradation
Graphs
Information theory
Ising model
Low temperature
Mathematical models
Noise measurement
stochastic block model
Stochastic processes
Surveys
Trees
Uniqueness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the study of Ising models on large locally tree-like graphs, in both rigorous and non-rigorous methods one is often led to understanding the so-called belief propagation distributional recursions and its fixed points. We prove that there is at most one non-trivial fixed point for Ising models with zero or certain random external fields. Previously this was only known for sufficiently "low-temperature" models. Our main innovation is in applying information-theoretic ideas of channel comparison leading to a new metric (degradation index) between binary-input-symmetric (BMS) channels under which the Belief Propagation (BP) operator is a strict contraction (albeit non-multiplicative). A key ingredient of our proof is a strengthening of the classical stringy tree lemma of [1]. Our result simultaneously closes the following 6 conjectures in the literature: 1) independence of robust reconstruction accuracy to leaf noise in broadcasting on trees [2]; 2) uselessness of global information for a labeled 2-community stochastic block model, or 2-SBM [3]; 3) optimality of local algorithms for 2-SBM under noisy side information [4]; 4) uniqueness of BP fixed point in broadcasting on trees in the Gaussian (large degree) limit [4]; 5) boundary irrelevance in broadcasting on trees [5]; 6) characterization of entropy (and mutual information) of community labels given the graph in 2-SBM [5].
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2023.3316795