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

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=Theta(√n).