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. Previously this was only known for sufficiently “lowtemperature” models. Our proof consists of constructing a metric under which the BP operator is a contraction (albeit non-multiplicative). This is achieved
by introducing a concept of degradation index and proving a strengthening of the stringy tree lemma from [9]. This simultaneously closes the following 6
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) uniqueness of BP fixed point in broadcasting on trees with large degree limit (ibid);
4) independence of robust reconstruction accuracy to leaf noise in broadcasting on trees (Mossel-Neeman-Slyʼ2016);
5) boundary irrelevance in BOT (Abbe-Cornacchia-Gu-P.ʼ2021);
6) characterization of entropy of community labels given the graph in 2-SBM (ibid).