# Generative hypergraph clustering: from blockmodels to modularity

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 124 references that are in the map.
- First posted on arXiv 24 Jan 2021.

## Builds on (most cited first, 30 of 38)

- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [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)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [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)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Inhomogeneous Hypergraph Clustering with Applications](https://mlsanity.com/paper/1709.01249/) (2017)
- [Clustering in graphs and hypergraphs with categorical edge labels](https://mlsanity.com/paper/1910.09943/) (2019)
- [Bayesian stochastic blockmodeling](https://mlsanity.com/paper/1705.10225/) (2017)
- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [A network approach to topic models](https://mlsanity.com/paper/1708.01677/) (2017)
- [Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering](https://mlsanity.com/paper/1803.03833/) (2018)
- [Consistency of Spectral Hypergraph Partitioning under Planted Partition Model](https://mlsanity.com/paper/1505.01582/) (2015)
- [The why, how, and when of representations for complex systems](https://mlsanity.com/paper/2006.02870/) (2020)
- [Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach](https://mlsanity.com/paper/1807.02884/) (2018)
- [Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity](https://mlsanity.com/paper/1403.5787/) (2014)
- [Configuring Random Graph Models with Fixed Degree Sequences](https://mlsanity.com/paper/1608.00607/) (2016)
- [Scalable motif-aware graph clustering](https://mlsanity.com/paper/1606.06235/) (2016)
- [Spectral Detection on Sparse Hypergraphs](https://mlsanity.com/paper/1507.04113/) (2015)
- [Configuration Models of Random Hypergraphs](https://mlsanity.com/paper/1902.09302/) (2019)
- [Hypergraph Cuts with General Splitting Functions](https://mlsanity.com/paper/2001.02817/) (2020)
- [Cheeger Inequalities for Submodular Transformations](https://mlsanity.com/paper/1708.08781/) (2017)
- [Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering](https://mlsanity.com/paper/1712.05825/) (2017)
- [Community detection in networks: Modularity optimization and maximum likelihood are equivalent](https://mlsanity.com/paper/1606.02319/) (2016)
- [Merge-split Markov chain Monte Carlo for community detection](https://mlsanity.com/paper/2003.07070/) (2020)
- [Efficiently inferring community structure in bipartite networks](https://mlsanity.com/paper/1403.2933/) (2014)

## Built on by (most cited first, 30 of 49)

- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks](https://mlsanity.com/paper/2106.13264/) (2021)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [Sheaf Hypergraph Networks](https://mlsanity.com/paper/2309.17116/) (2023)
- [From Hypergraph Energy Functions to Hypergraph Neural Networks](https://mlsanity.com/paper/2306.09623/) (2023)
- [Scalable Spectral Clustering with Group Fairness Constraints](https://mlsanity.com/paper/2210.16435/) (2022)
- [Inference of hyperedges and overlapping communities in hypergraphs](https://mlsanity.com/paper/2204.05646/) (2022)
- [Hypergraph Artificial Benchmark for Community Detection (h-ABCD)](https://mlsanity.com/paper/2210.15009/) (2022)
- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [Structure and inference in hypergraphs with node attributes](https://mlsanity.com/paper/2311.03857/) (2023)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Nonbacktracking spectral clustering of nonuniform hypergraphs](https://mlsanity.com/paper/2204.13586/) (2022)
- [A Comprehensive Survey on Graph Summarization with Graph Neural Networks](https://mlsanity.com/paper/2302.06114/) (2023)
- [Local Clustering on Complex Graphs and Complex Hypergraphs](https://mlsanity.com/paper/2412.03008/) (2024)
- [Hyperedge Prediction using Tensor Eigenvalue Decomposition](https://mlsanity.com/paper/2102.04986/) (2021)
- [Learning the effective order of a hypergraph dynamical system](https://mlsanity.com/paper/2306.01813/) (2023)
- [Modularity Based Community Detection in Hypergraphs](https://mlsanity.com/paper/2406.17556/) (2024)
- [Broad Spectrum Structure Discovery in Large-Scale Higher-Order Networks](https://mlsanity.com/paper/2505.21748/) (2025)
- [Tackling Over-smoothing on Hypergraphs: A Ricci Flow-guided Neural Diffusion Approach](https://mlsanity.com/paper/2603.15696/) (2026)
- [Hypergraph Neural Diffusion: A PDE-Inspired Framework for Hypergraph Message Passing](https://mlsanity.com/paper/2604.10955/) (2026)
- [Hybrid Graph: A Unified Graph Representation with Datasets and Benchmarks for Complex Graphs](https://mlsanity.com/paper/2306.05108/) (2023)
- [Continuous Simplicial Neural Networks](https://mlsanity.com/paper/2503.12919/) (2025)
- [BHyGNN+: Unsupervised Representation Learning for Heterophilic Hypergraphs](https://mlsanity.com/paper/2602.14919/) (2026)
- [Heterophily-Agnostic Hypergraph Neural Networks with Riemannian Local Exchanger](https://mlsanity.com/paper/2603.00599/) (2026)
- [Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components](https://mlsanity.com/paper/2110.14859/) (2021)
- [Hypergraph Modeling via Spectral Embedding Connection: Hypergraph Cut, Weighted Kernel k-means, and Heat Kernel](https://mlsanity.com/paper/2203.09888/) (2022)
- [Scalable tensor methods for nonuniform hypergraphs](https://mlsanity.com/paper/2306.17825/) (2023)
- [Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models](https://mlsanity.com/paper/2401.00688/) (2024)
- [Laplacian-based Semi-Supervised Learning in Multilayer Hypergraphs by Coordinate Descent](https://mlsanity.com/paper/2301.12184/) (2023)
- [HyperS2V: A Framework for Structural Representation of Nodes in Hyper Networks](https://mlsanity.com/paper/2311.04149/) (2023)

## Abstract (arXiv)

Hypergraphs are a natural modeling paradigm for a wide range of complex relational systems. A standard analysis task is to identify clusters of closely related or densely interconnected nodes. Many graph algorithms for this task are based on variants of the stochastic blockmodel, a random graph with flexible cluster structure. However, there are few models and algorithms for hypergraph clustering. Here, we propose a Poisson degree-corrected hypergraph stochastic blockmodel (DCHSBM), a generative model of clustered hypergraphs with heterogeneous node degrees and edge sizes. Approximate maximum-likelihood inference in the DCHSBM naturally leads to a clustering objective that generalizes the popular modularity objective for graphs. We derive a general Louvain-type algorithm for this objective, as well as a a faster, specialized "All-Or-Nothing" (AON) variant in which edges are expected to lie fully within clusters. This special case encompasses a recent proposal for modularity in hypergraphs, while also incorporating flexible resolution and edge-size parameters. We show that AON hypergraph Louvain is highly scalable, including as an example an experiment on a synthetic hypergraph of one million nodes. We also demonstrate through synthetic experiments that the detectability regimes for hypergraph community detection differ from methods based on dyadic graph projections. We use our generative model to analyze different patterns of higher-order structure in school contact networks, U.S. congressional bill cosponsorship, U.S. congressional committees, product categories in co-purchasing behavior, and hotel locations from web browsing sessions, finding interpretable higher-order structure. We then study the behavior of our AON hypergraph Louvain algorithm, finding that it is able to recover ground truth clusters in empirical data sets exhibiting the corresponding higher-order structure.