Abstract
We consider the exact recovery problem in the hypergraph stochastic blockmodel (HSBM) with $k$ blocks of equal size. More precisely, we consider arandom $d$-uniform hypergraph $H$ with $n$ vertices partitioned into $k$clusters of size $s = n / k$. Hyperedges $e$ are added independently withprobability $p$ if $e$ is contained within a single cluster and $q$ otherwise,where $0 \leq q < p \leq 1$. We present a spectral algorithm which recovers theclusters 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 we defineto be the symmetric $n \times n$ matrix whose $(u, v)$-th entry is the numberof hyperedges containing both $u$ and $v$. To the best of our knowledge, ouralgorithm is the first to guarantee exact recovery when the number of clusters$k=\Theta(\sqrt{n})$.