In the study of sparse stochastic block model (SBM) one needs to analyze a distributional recursion, known as belief propagation (BP) on a tree. Uniqueness of the fixed point of this recursion implies several results about the SBM, including optimal recovery algorithms for SBM (Mossel et al. (2016)) and SBM with side information (Mossel and Xu (2016)), and a formula for SBM mutual information (Abbe et al. (2021)). The 2-community case corresponds to an Ising model, for which Yu and Polyanskiy (2022) established uniqueness for all cases. Here, we analyze broadcasting of $q$-ary spins on a Galton-Watson tree with expected offspring degree $d$ and Potts channels with second-largest eigenvalue $\lambda$. We allow for the intermediate vertices to be observed through noisy channels (side information) We prove BP uniqueness holds with and without side information when $d\lambda^2 \ge 1 + C \max\{\lambda, q^{-1}\}\log q$ for some absolute constant $C>0$ independent of $q,d,\lambda$. For large $q$ and $\lambda = o(1/\log q)$, this is asymptotically achieving the Kesten-Stigum threshold $d\lambda^2=1$. These results imply mutual information formula and optimal recovery algorithms for the $q$-community SBM in the corresponding ranges. For $q\ge 4$, Sly (2011); Mossel et al. (2022) shows that there exist choices of $q,d,\lambda$ below Kesten-Stigum (i.e. $d\lambda^2 < 1$) but reconstruction is possible. Somewhat surprisingly, we show that in such regimes BP uniqueness \textit{does not hold} at least in the presence of weak side information. Our technical tool is a theory of q-ary symmetric channels, that we initiate here, generalizing the classical and widely-utilized information-theoretic characterization of BMS (binary memoryless symmetric) channels.
翻译:Potts模型BP固定点的唯一性及其在社区检测中的应用
翻译后的摘要:
本文研究了在稀疏随机块模型(SBM)中的信念传播(BP)分布递归问题。BP固定点的唯一性证明了关于SBM的几个结果,包括SBM的最佳恢复算法(Mossel等人(2016年))和带边信息的SBM(Mossel和Xu(2016年)),以及SBM互信息的公式(Abbe等人(2021年))。2个社区的情况对应于Ising模型,对其,Yu和Polyanskiy(2022年)证明了所有情况下的唯一性。本文分析了在Galton-Watson树上通过具有次大特征值$\lambda$的Potts通道广播$q$元自旋的情况,其中允许通过噪声信道(边缘信息)观测中间节点。我们证明,当$d\lambda^2 \ge 1 + C \max\{\lambda, q^{-1}\}\log q$时,无论是否有边缘信息,BP唯一性都成立,其中$C>0$是独立于$q,d,\lambda$的某个绝对常数。对于大的$q$,且$\lambda = o(1/\log q)$,这是达到Kesten-Stigum阈值$d\lambda^2=1$的渐进结果。这些结果意味着相应范围内的$q$元社区SBM的互信息公式和最佳恢复算法。对于$q\ge 4$,Sly (2011); Mossel等人(2022)表明,存在低于Kesten-Stigum(即$d\lambda^2 < 1$)的$q,d,\lambda$的选择,但仍可以进行重建。令人惊讶的是,我们证明在此类情况下至少在存在弱边缘信息时,BP唯一性不成立。我们引入了一个q元对称信道理论,这是一个新的通用工具,是对基础的、被广泛应用的二元记忆递减对称(BMS)信道的信息理论刻画的推广。