On the Minimax Misclassification Ratio of Hypergraph Community Detection

Understand

Community detection in hypergraphs is explored.

• Under a generative hypergraph model called "d-wise hypergraph stochastic block model" (d-hSBM) which naturally extends the Stochastic Block Model from graphs to d-uniform hypergraphs, the asymptotic minimax mismatch ratio is characterized.
• For proving the achievability, we propose a two-step polynomial time algorithm that achieves the fundamental limit.
• The first step of the algorithm is a hypergraph spectral clustering method which achieves partial recovery to a certain precision level.