Speaker: Yury Polyanskiy (MIT)
Title: Uniqueness of BP fixed point for Ising models
Abstract: 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 point (also known as Bethe fixed point, cavity equation etc). In this work we prove there is at most one non-trivial fixed point for Ising models with zero and certain random external fields.

As a concrete example, consider a sample A of Ising model on a rooted tree (regular, Galton-Watson, etc). Let B be a noisy version of A obtained by independently perturbing each spin as follows: Bv equals to Av with some small probability δ and otherwise taken to be a uniform +-1 (alternatively, 0). We show that the distribution of the root spin Aρ conditioned on values Bv of all vertices v at a large distance from the root is independent of δ and coincides with δ=0. Previously this was only known for sufficiently ``low-temperature'' models. Our proof consists of constructing a metric under which the BP operator is a contraction (albeit non-multiplicative). I hope to convince you our proof is technically rather simple.

This simultaneously closes the following 5 conjectures in the literature: uselessness of global information for a labeled 2-community stochastic block model, or 2-SBM (Kanade-Mossel-Schramm'2014); optimality of local algorithms for 2-SBM under noisy side information (Mossel-Xu'2015); independence of robust reconstruction accuracy to leaf noise in broadcasting on trees (Mossel-Neeman-Sly'2016); boundary irrelevance in BOT (Abbe-Cornacchia-Gu-P.'2021); characterization of entropy of community labels given the graph in 2-SBM (ibid).
Joint work with Qian Yu (Princeton).