Weak Recovery Threshold for the Hypergraph Stochastic Block Model
From MaRDI portal
Abstract: We study the weak recovery problem on the -uniform hypergraph stochastic block model (-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 , or a strength parameter is at least . 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 , surprisingly, we demonstrate that for reconstruction is possible also below KS. This shows an interesting phase transition in the parameter , and suggests that for , there might be an information-computation gap for the HSBM. For and large degree we propose an approach for showing non-reconstruction below KS, suggesting that is the correct threshold for onset of the new phase.
This page was built for publication: Weak Recovery Threshold for the Hypergraph Stochastic Block Model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6430882)
