Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm

Abstract

We consider the exact recovery problem in the hypergraph stochastic block model (HSBM) with $k$ blocks of equal size. More precisely, we consider a random $d$-uniform hypergraph $H$ with $n$ vertices partitioned into $k$ clusters of size $s=n/k$. Hyperedges $e$ are added independently with probability $p$ if $e$ is contained within a single cluster and $q$ otherwise, where $0\le q<p\le 1$. We present a spectral algorithm which recovers the clusters exactly with high probability, given mild conditions on $n,k,p,q$, and $d$. Our algorithm is based on the adjacency matrix of $H$, which is a symmetric $n\times n$ matrix whose $(u,v)$-th entry is the number of hyperedges containing both $u$ and $v$. To the best of our knowledge, our algorithm is the first to guarantee exact recovery when the number of clusters $k=\Theta (\sqrt{n})$.

References in corpus (14)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited
• Guaranteed clustering and biclustering via semidefinite programming
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Finding Dense Clusters via "Low Rank + Sparse" Decomposition
• Improved Graph Clustering
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Steering Social Activity: A Stochastic Optimal Control Point Of View
• Consistency Thresholds for the Planted Bisection Model
• On the Minimax Misclassification Ratio of Hypergraph Community Detection
• Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models

Cited by in corpus (12)

• Community detection in the sparse hypergraph stochastic block model
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
• Opinion disparity in hypergraphs with community structure
• Sparse random tensors: Concentration, regularization and applications
• A useful criterion on studying consistent estimation in community detection
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
• Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
• Model-based clustering in simple hypergraphs through a stochastic blockmodel
• Multilayer hypergraph clustering using the aggregate similarity matrix
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
• Exact Recovery in the General Hypergraph Stochastic Block Model
• Information Theoretic Limits of Exact Recovery in Sub-hypergraph Models for Community Detection