Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
This addresses the problem of community detection in hypergraphs for researchers in network analysis, offering a novel solution for a broader range of cluster counts.
The paper tackles the exact recovery problem in the hypergraph stochastic block model (HSBM) by presenting a spectral algorithm that recovers clusters exactly with high probability under mild conditions, achieving this for up to k = Θ(√n) clusters.
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 \leq q < p \leq 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=Θ(\sqrt{n})$.