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 ≤ q p ≤ 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 × 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 = Θ ( n ) .