# Nonbacktracking spectral clustering of nonuniform hypergraphs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 83 references that are in the map.
- First posted on arXiv 27 Apr 2022.

## Builds on (most cited first, 29 of 29)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Networks beyond pairwise interactions: structure and dynamics](https://mlsanity.com/paper/2006.01764/) (2020)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [What are higher-order networks?](https://mlsanity.com/paper/2104.11329/) (2021)
- [The physics of higher-order interactions in complex systems](https://mlsanity.com/paper/2110.06023/) (2021)
- [Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys](https://mlsanity.com/paper/1506.03645/) (2015)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs](https://mlsanity.com/paper/1501.06087/) (2015)
- [Consistency of Spectral Hypergraph Partitioning under Planted Partition Model](https://mlsanity.com/paper/1505.01582/) (2015)
- [Spectral Detection on Sparse Hypergraphs](https://mlsanity.com/paper/1507.04113/) (2015)
- [Configuration Models of Random Hypergraphs](https://mlsanity.com/paper/1902.09302/) (2019)
- [The extent and drivers of gender imbalance in neuroscience reference lists](https://mlsanity.com/paper/2001.01002/) (2020)
- [Quantitative Evaluation of Gender Bias in Astronomical Publications from Citation Counts](https://mlsanity.com/paper/1610.08984/) (2016)
- [Localization and centrality in networks](https://mlsanity.com/paper/1401.5093/) (2014)
- [A unified framework for spectral clustering in sparse graphs](https://mlsanity.com/paper/2003.09198/) (2020)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Identifying critical higher-order interactions in complex networks](https://mlsanity.com/paper/2105.02763/) (2021)
- [Citation inequity and gendered citation practices in contemporary physics](https://mlsanity.com/paper/2112.09047/) (2021)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Multiway Spherical Clustering via Degree-Corrected Tensor Block Models](https://mlsanity.com/paper/2201.07401/) (2022)
- [Coin-flipping, ball-dropping, and grass-hopping for generating random graphs from matrices of edge probabilities](https://mlsanity.com/paper/1709.03438/) (2017)
- [Algorithmic detectability threshold of the stochastic block model](https://mlsanity.com/paper/1710.08841/) (2017)
- [Graph Comparison via the Non-backtracking Spectrum](https://mlsanity.com/paper/1812.05457/) (2018)

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

- [Geometric Scattering on Measure Spaces](https://mlsanity.com/paper/2208.08561/) (2022)
- [Hypergraph Artificial Benchmark for Community Detection (h-ABCD)](https://mlsanity.com/paper/2210.15009/) (2022)
- [Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models](https://mlsanity.com/paper/2412.21155/) (2024)
- [Perfect Clustering in Nonuniform Hypergraphs](https://mlsanity.com/paper/2504.08980/) (2025)

## Abstract (arXiv)

Spectral methods offer a tractable, global framework for clustering in graphs via eigenvector computations on graph matrices. Hypergraph data, in which entities interact on edges of arbitrary size, poses challenges for matrix representations and therefore for spectral clustering. We study spectral clustering for nonuniform hypergraphs based on the hypergraph nonbacktracking operator. After reviewing the definition of this operator and its basic properties, we prove a theorem of Ihara-Bass type which allows eigenpair computations to take place on a smaller matrix, often enabling faster computation. We then propose an alternating algorithm for inference in a hypergraph stochastic blockmodel via linearized belief-propagation which involves a spectral clustering step again using nonbacktracking operators. We provide proofs related to this algorithm that both formalize and extend several previous results. We pose several conjectures about the limits of spectral methods and detectability in hypergraph stochastic blockmodels in general, supporting these with in-expectation analysis of the eigeinpairs of our studied operators. We perform experiments in real and synthetic data that demonstrate the benefits of hypergraph methods over graph-based ones when interactions of different sizes carry different information about cluster structure.