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

arXiv: https://arxiv.org/abs/1811.06931 · HTML: https://mlsanity.com/paper/1811.06931/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2018.

## Built on by (most cited first, 9 of 9)

- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [A useful criterion on studying consistent estimation in community detection](https://mlsanity.com/paper/2109.14950/) (2021)
- [Information Theoretic Limits of Exact Recovery in Sub-hypergraph Models for Community Detection](https://mlsanity.com/paper/2101.12369/) (2021)
- [Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix](https://mlsanity.com/paper/2208.12227/) (2022)
- [Multilayer hypergraph clustering using the aggregate similarity matrix](https://mlsanity.com/paper/2301.11657/) (2023)
- [Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models](https://mlsanity.com/paper/2306.06845/) (2023)
- [Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms](https://mlsanity.com/paper/2501.11139/) (2025)

## Abstract (arXiv)

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