2023/03/26 by Yuzhou Gu, Yury Polyanskiy, Gu, Yuzhou +1 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2303.14689
openalex publication_date 2023/03/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the weak recovery problem on 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, and weak recovery asks to recover a non-trivial fraction of the labels. We introduce a multi-terminal version of strong data processing inequalities (SDPIs), which we call the multi-terminal SDPI, and use it to prove a variety of impossibility results for weak recovery. In particular, we prove that weak recovery is impossible below the Kesten-Stigum (KS) threshold if r=3,4, or a strength parameter λ is at least \frac 15. Prior work Pal and Zhu (2021) established that weak recovery in HSBM is always possible above the KS threshold. Consequently, there is no information-computation gap for these cases, 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 KS for r=3,4, surprisingly, we demonstrate that for r≥ 7 reconstruction is possible also below KS. 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 KS, suggesting that r=7 is the correct threshold for onset of the new phase.