# Consistency of Spectral Hypergraph Partitioning under Planted Partition Model

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2015.

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

- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition](https://mlsanity.com/paper/2106.16042/) (2021)
- [Community Detection in General Hypergraph via Graph Embedding](https://mlsanity.com/paper/2103.15035/) (2021)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [Hypergraph Artificial Benchmark for Community Detection (h-ABCD)](https://mlsanity.com/paper/2210.15009/) (2022)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Sharp detection boundaries on testing dense subhypergraph](https://mlsanity.com/paper/2101.04584/) (2021)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Dynamic Representation Learning with Temporal Point Processes for Higher-Order Interaction Forecasting](https://mlsanity.com/paper/2112.10154/) (2021)
- [Multiway Spherical Clustering via Degree-Corrected Tensor Block Models](https://mlsanity.com/paper/2201.07401/) (2022)
- [Nonbacktracking spectral clustering of nonuniform hypergraphs](https://mlsanity.com/paper/2204.13586/) (2022)
- [Heterogeneous Dense Subhypergraph Detection](https://mlsanity.com/paper/2104.04047/) (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)
- [Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph boldsymbolβ-Model](https://mlsanity.com/paper/2307.02818/) (2023)
- [Community detection in censored hypergraph](https://mlsanity.com/paper/2111.03179/) (2021)
- [Tensorized Hypergraph Neural Networks](https://mlsanity.com/paper/2306.02560/) (2023)
- [On consistency of constrained spectral clustering under representation-aware stochastic block model](https://mlsanity.com/paper/2203.02005/) (2022)
- [Learning Multi-Order Block Structure in Higher-Order Networks](https://mlsanity.com/paper/2511.21350/) (2025)
- [Hypergraph Generation via Structured Stochastic Diffusion](https://mlsanity.com/paper/2605.05024/) (2026)

## Abstract (arXiv)

Hypergraph partitioning lies at the heart of a number of problems in machine learning and network sciences. Many algorithms for hypergraph partitioning have been proposed that extend standard approaches for graph partitioning to the case of hypergraphs. However, theoretical aspects of such methods have seldom received attention in the literature as compared to the extensive studies on the guarantees of graph partitioning. For instance, consistency results of spectral graph partitioning under the stochastic block model are well known. In this paper, we present a planted partition model for sparse random non-uniform hypergraphs that generalizes the stochastic block model. We derive an error bound for a spectral hypergraph partitioning algorithm under this model using matrix concentration inequalities. To the best of our knowledge, this is the first consistency result related to partitioning non-uniform hypergraphs.