Uniqueness of BP fixed point for the Potts model and applications to community detection
share
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 λ. 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λ^2 ≥ 1 + C max{λ, q^-1}log q for some absolute constant C>0 independent of q,d,λ. For large q and λ = o(1/log q), this is asymptotically achieving the Kesten-Stigum threshold dλ^2=1. These results imply mutual information formula and optimal recovery algorithms for the q-community SBM in the corresponding ranges. For q≥ 4, Sly (2011); Mossel et al. (2022) shows that there exist choices of q,d,λ below Kesten-Stigum (i.e. dλ^2 < 1) but reconstruction is possible. Somewhat surprisingly, we show that in such regimes BP uniqueness 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.
READ FULL TEXT