Speaker: Yury Polyansky (MIT EECS)

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 or random (but ``unbiased'') 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: $B_v$ equals to $A_v$ with some small probability $\delta$ and otherwise taken to be a uniform +-1 (alternatively,  0).  We show that the distribution of the root spin $A_\rho$ conditioned on values $B_v$ of all vertices $v$ at a large distance from the root is independent of $\delta$ and coincides with $\delta=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:

1) uselessness of global information for a labeled 2-community stochastic block model, or 2-SBM (Kanade-Mossel-Schramm'2014);

2) optimality of local algorithms for 2-SBM under noisy side information (Mossel-Xu'2015);

3) independence of robust reconstruction accuracy to leaf noise in broadcasting on trees (Mossel-Neeman-Sly'2016);

4) boundary irrelevance in BOT (Abbe-Cornacchia-Gu-P.'2021);

5) characterization of entropy of community labels given the graph in 2-SBM (ibid).

Joint work with Qian Yu (Princeton).