Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach

Abstract

We study the problem of community detection in a random hypergraph model which we call the stochastic block model for $k$-uniform hypergraphs ($k$-SBM). We investigate the exact recovery problem in $k$-SBM and show that a sharp phase transition occurs around a threshold: below the threshold it is impossible to recover the communities with non-vanishing probability, yet above the threshold there is an estimator which recovers the communities almost asymptotically surely. We also consider a simple, efficient algorithm for the exact recovery problem which is based on a semidefinite relaxation technique.

References in corpus (9)

• Random hypergraphs and their applications
• Stochastic Block Models and Reconstruction
• Phase Transitions in Semidefinite Relaxations
• Hypergraph topological quantities for tagged social networks
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Inference via Message Passing on Partially Labeled Stochastic Block Models
• Evolution of high-order connected components in random hypergraphs
• On the Minimax Misclassification Ratio of Hypergraph Community Detection

Cited by in corpus (10)

• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Multiway Spherical Clustering via Degree-Corrected Tensor Block Models
• Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition
• Exact Recovery in the General Hypergraph Stochastic Block Model
• $H{S}^2$: Active Learning over Hypergraphs
• Information Theoretic Limits of Exact Recovery in Sub-hypergraph Models for Community Detection