Weak Recovery Threshold for the Hypergraph Stochastic Block Model
share
We study the problem of weak recovery for the r-uniform hypergraph stochastic block model (r-HSBM) with two balanced communities. In HSBM a random graph is constructed by placing hyperedges with higher density if all vertices of a hyperedge share the same binary label. By analyzing contraction of a non-Shannon (symmetric-KL) information measure, we prove that for r=3,4, weak recovery is impossible below the Kesten-Stigum threshold. Prior work Pal and Zhu (2021) established that weak recovery in HSBM is always possible above the Kesten-Stigum threshold. Consequently, there is no information-computation gap for these r, which (partially) resolves a conjecture of Angelini et al. (2015). To our knowledge this is the first impossibility result for HSBM weak recovery. As usual, we reduce the study of non-recovery of HSBM to the study of non-reconstruction in a related broadcasting on hypertrees (BOHT) model. While we show that BOHT's reconstruction threshold coincides with Kesten-Stigum for r=3,4, surprisingly, we demonstrate that for r≥ 7 reconstruction is possible also below the Kesten-Stigum. This shows an interesting phase transition in the parameter r, and suggests that for r≥ 7, there might be an information-computation gap for the HSBM. For r=5,6 and large degree we propose an approach for showing non-reconstruction below Kesten-Stigum threshold, suggesting that r=7 is the correct threshold for onset of the new phase. We admit that our analysis of the r=4 case depends on a numerically-verified inequality.
READ FULL TEXT