Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model
The Annals of Statistics · 2026 · Volume 54 · Issue 1
Abstract
Consider the community detection problem in random hypergraphs under the nonuniform hypergraph stochastic block model (HSBM), where each hyperedge appears independently with some given probability depending only on the labels of its vertices. We establish, for the first time in the literature, a sharp threshold for exact recovery for the nonuniform, multiple-community case, subject to only minor constraints. One crucial point here is that, by aggregating information from all the uniform layers, we may obtain exact recovery, even in cases when this is impossible if each layer were considered alone. In addition, for the almost exact recovery regime, we prove a wide-ranging, information-theoretic lower bound on the number of misclassified vertices for any algorithm. The bound depends on a generalized Chernoff–Hellinger divergence involving model parameters. We provide two efficient algorithms (one for the minimal information case, another for the full information case) which successfully achieve exact recovery when above the threshold and attain the lowest possible mismatch ratio when the exact recovery is impossible. The theoretical analysis of our algorithms relies on the concentration and regularization of the adjacency matrix for nonuniform random hypergraphs, which could be of independent interest. We also address some open problems regarding parameter knowledge and estimation.
Keywords
05C80; 60B20; Random hypergraphs; random matrices; Stochastic block model; strong consistency;
Enable JavaScript for citation tools and additional paper interactions.