论文标题
在本地树状图上的ISING模型：腔方程解决方案的独特性
Ising Model on Locally Tree-like Graphs: Uniqueness of Solutions to Cavity Equations
论文作者
论文摘要
在对大型局部树状图上的Ising模型的研究中，在严格和非符合性的方法中，人们通常会理解所谓的信仰传播分布分布递归及其固定点。我们证明，对于具有零或某些随机外部字段的ISING模型，最多有一个非平凡的固定点。以前，这仅以足够的``低温''模型而闻名。我们的主要创新是应用渠道比较的信息理论思想，从而导致二进制输入对称（BMS）渠道之间的新指标（退化指数），在该渠道下，信念传播（BP）操作员是严格的收缩（尽管是非杂质）。我们证明的关键要素是加强（Evans-Kenyon-peres-Schulman'00）的经典丝状树。 我们的结果同时结束了文献中的以下6个猜想：1）在树上广播中，强大的重建精度独立于叶噪声（Mossel-neeman-sly'16）； 2）标记为2个社区随机块模型或2-SBM的全局信息无用（Kanade-Mossel-Schramm'16）； 3）在嘈杂的侧面信息（Mossel-XU'16）下，2-SBM的局部算法的最佳性； 4）BP固定点在高斯（大）限制（同上）的树木上广播中的唯一性； 5）在树木上广播的边界无关（Abbe-Cornacchia-gu-polyanskiy'21）； 6）鉴于2-SBM（同上）的图表的熵（和互信息）的表征。
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 (Evans-Kenyon-Peres-Schulman'00). Our result simultaneously closes the following 6 conjectures in the literature: 1) independence of robust reconstruction accuracy to leaf noise in broadcasting on trees (Mossel-Neeman-Sly'16); 2) uselessness of global information for a labeled 2-community stochastic block model, or 2-SBM (Kanade-Mossel-Schramm'16); 3) optimality of local algorithms for 2-SBM under noisy side information (Mossel-Xu'16); 4) uniqueness of BP fixed point in broadcasting on trees in the Gaussian (large degree) limit (ibid); 5) boundary irrelevance in broadcasting on trees (Abbe-Cornacchia-Gu-Polyanskiy'21); 6) characterization of entropy (and mutual information) of community labels given the graph in 2-SBM (ibid).
