Community detection in the hypergraph stochastic block model and reconstruction on hypertrees

We study the weak recovery problem on the r-uniform hypergraph stochastic block model (r-HSBM) with two balanced communities. In this model, n vertices are randomly divided into two communities, and size-r hyperedges are added randomly depending on whether all vertices in the hyperedge are in the same community. The goal of the weak recovery problem is to recover a non-trivial fraction of the communities given the hypergraph. Previously, Pal and Zhu (2021) established that weak recovery is always possible above a natural threshold called the Kesten-Stigum (KS) threshold. Gu and Polyanskiy (2023) proved that the KS threshold is tight if r 4 or the expected degree d is small. It remained open whether the KS threshold is tight for r 5 and large d. In this paper we determine the tightness of the KS threshold for any fixed r and large d. We prove that for r 6 and d large enough, the KS threshold is tight. This shows that there is no information-computation gap in this regime. This partially confirms a conjecture of Angelini et al. (2015). For r 7, we prove that for d large enough, the KS threshold is not tight, providing more evidence supporting the existence of an information-computation gap in this regime. Furthermore, we establish asymptotic bounds on the weak recovery threshold for fixed r and large d. We also obtain a number of results regarding the closely-related broadcasting on hypertrees (BOHT) model, including the asymptotics of the reconstruction threshold for r 7 and impossibility of robust reconstruction at criticality.