Exact Recovery in the General Hypergraph Stochastic Block Model
arXiv:2105.04770
Abstract
This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph stochastic block model (d-HSBM), wherein n nodes are partitioned into k disjoint communities with relative sizes (p1,..., pk). Each subset of nodes with cardinality d is generated independently as an order-d hyperedge with a certain probability that depends on the ground-truth communities that the d nodes belong to. The goal is to exactly recover the k hidden communities based on the observed hypergraph. We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below the threshold (apart from a small regime of parameters that will be specified precisely). This threshold is represented in terms of a quantity which we term as the generalized Chernoff-Hellinger divergence between communities. Our result for this general model recovers prior results for the standard SBM and d-HSBM with two symmetric communities as special cases. En route to proving our achievability results, we develop a polynomial-time two-stage algorithm that meets the threshold. The first stage adopts a certain hypergraph spectral clustering method to obtain a coarse estimate of communities, and the second stage refines each node individually via local refinement steps to ensure exact recovery.
Accepted by IEEE Transactions on Information Theory
References in corpus (7)
- Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
- Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
- Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
- Community Detection with Side Information: Exact Recovery under the Stochastic Block Model
- Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
- Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
- MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs