Community Detection in Hypergraphs: Optimal Statistical Limit and Efficient Algorithms
[edit]
Proceedings of the TwentyFirst International Conference on Artificial Intelligence and Statistics, PMLR 84:871879, 2018.
Abstract
In this paper, community detection in hypergraphs is explored. Under a generative hypergraph model called "dwise hypergraph stochastic block model" (dhSBM) which naturally extends the Stochastic Block Model (SBM) from graphs to duniform hypergraphs, the fundamental limit on the asymptotic minimax misclassified ratio is characterized. For proving the achievability, we propose a twostep polynomial time algorithm that provably achieves the fundamental limit in the sparse hypergraph regime. For proving the optimality, the lower bound of the minimax risk is set by finding a smaller parameter space which contains the most dominant error events, inspired by the analysis in the achievability part. It turns out that the minimax risk decays exponentially fast to zero as the number of nodes tends to infinity, and the rate function is a weighted combination of several divergence terms, each of which is the Renyi divergence of order 1/2 between two Bernoulli distributions. The Bernoulli distributions involved in the characterization of the rate function are those governing the random instantiation of hyperedges in dhSBM. Experimental results on both synthetic and realworld data validate our theoretical finding.
Related Material


