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

2018/07/08 by Kim, Chiheon, Bandeira, Afonso S., Goemans, Michel X. · 3 citations
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Probability (math.PR)

paper · doi:10.48550/arxiv.1807.02884

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.

Cited by

• Differentially Private Community Detection in h-uniform Hypergraphs
• Hypergraph Contrastive Learning for both Homophilic and Heterophilic Hypergraphs
• Quartic quantum speedups for community detection

Related

• Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model
• Community detection in the hypergraph stochastic block model and reconstruction on hypertrees
• Exact Recovery in the General Hypergraph Stochastic Block Model
• Community Detection and Stochastic Block Models
• Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery