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})$.