# Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2018.

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

- [You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks](https://mlsanity.com/paper/2106.13264/) (2021)
- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [I'm Me, We're Us, and I'm Us: Tri-directional Contrastive Learning on Hypergraphs](https://mlsanity.com/paper/2206.04739/) (2022)
- [Dynamic Hypergraph Structure Learning for Traffic Flow Forecasting](https://mlsanity.com/paper/2309.12028/) (2023)
- [A nonlinear diffusion method for semi-supervised learning on hypergraphs](https://mlsanity.com/paper/2103.14867/) (2021)
- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [CAT-Walk: Inductive Hypergraph Learning via Set Walks](https://mlsanity.com/paper/2306.11147/) (2023)
- [Finding Bipartite Components in Hypergraphs](https://mlsanity.com/paper/2205.02771/) (2022)
- [Ada-HGNN: Adaptive Sampling for Scalable Hypergraph Neural Networks](https://mlsanity.com/paper/2405.13372/) (2024)
- [Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality](https://mlsanity.com/paper/2411.03331/) (2024)
- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues](https://mlsanity.com/paper/2211.09776/) (2022)
- [Hypergraph Neural Diffusion: A PDE-Inspired Framework for Hypergraph Message Passing](https://mlsanity.com/paper/2604.10955/) (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)
- [Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering](https://mlsanity.com/paper/2208.07457/) (2022)
- [Exact Inference in High-order Structured Prediction](https://mlsanity.com/paper/2302.03236/) (2023)
- [Seven open problems in applied combinatorics](https://mlsanity.com/paper/2303.11464/) (2023)
- [Hypergraphs with Edge-Dependent Vertex Weights: Spectral Clustering based on the 1-Laplacian](https://mlsanity.com/paper/2305.00462/) (2023)
- [Hypergraph p-Laplacian regularization on point clouds for data interpolation](https://mlsanity.com/paper/2405.01109/) (2024)
- [Higher-Order Regularization Learning on Hypergraphs](https://mlsanity.com/paper/2510.26533/) (2025)
- [The WidthWall: A Strict Expressivity Hierarchy for Hypergraph Neural Networks](https://mlsanity.com/paper/2605.13690/) (2026)

## Abstract (arXiv)

We introduce submodular hypergraphs, a family of hypergraphs that have different submodular weights associated with different cuts of hyperedges. Submodular hypergraphs arise in clustering applications in which higher-order structures carry relevant information. For such hypergraphs, we define the notion of p-Laplacians and derive corresponding nodal domain theorems and k-way Cheeger inequalities. We conclude with the description of algorithms for computing the spectra of 1- and 2-Laplacians that constitute the basis of new spectral hypergraph clustering methods.