Ising Model on Locally Tree-like Graphs: Uniqueness of Solutions to Cavity Equations, Qian Yu, Post Doc (3000000)
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 . 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).