On the fundamental statistical limit of community detection in random hypergraphs

摘要

The problem of community detection in random hypergraphs is considered. We extend the Stochastic Block Model (SBM) from graphs to hypergraphs with d-uniform hyperedges, which we term “d-wise hyper stochastic block model” (d-hSBM) and consider a homogeneous and approximately equal-sized K community case. For d = 3, we fully characterize the exponentially decaying rate of the minimax risk in recovering the underlying communities, where the loss function is the mis-match ratio between the true community assignment and the recovered one. It turns out that the rate function is a weighted combination of several divergence terms, each of which is the Renyi divergence of order 1 between two Bernoulli distributions. The Bernoulli distributions involved in the characterization of the rate function are those governing the random instantiation of hyperedges in d-hSBM. The lower bound is set by finding a smaller parameter space where we can analyze the risk, while the upper bound is achieved with the Maximum Likelihood estimator. The technical contribution is to show that upper bound has the same decaying rate as the lower bound, which involves careful bounding of the various probabilities of errors. Finally, we relate the minimax risk to the recovery criterion under the Bayesian framework and derive a threshold condition for exact recovery.