# The WidthWall: A Strict Expressivity Hierarchy for Hypergraph Neural Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 57 references that are in the map.
- First posted on arXiv 13 May 2026.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Hypergraph Neural Networks](https://mlsanity.com/paper/1809.09401/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Networks beyond pairwise interactions: structure and dynamics](https://mlsanity.com/paper/2006.01764/) (2020)
- [UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks](https://mlsanity.com/paper/2105.00956/) (2021)
- [You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks](https://mlsanity.com/paper/2106.13264/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [HNHN: Hypergraph Networks with Hyperedge Neurons](https://mlsanity.com/paper/2006.12278/) (2020)
- [Topological Deep Learning: Going Beyond Graph Data](https://mlsanity.com/paper/2206.00606/) (2022)
- [HyperSAGE: Generalizing Inductive Representation Learning on Hypergraphs](https://mlsanity.com/paper/2010.04558/) (2020)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [Sheaf Hypergraph Networks](https://mlsanity.com/paper/2309.17116/) (2023)
- [Lov'asz Meets Weisfeiler and Leman](https://mlsanity.com/paper/1802.08876/) (2018)
- [Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering](https://mlsanity.com/paper/1803.03833/) (2018)
- [Equivariant Hypergraph Neural Networks](https://mlsanity.com/paper/2208.10428/) (2022)
- [Training-Free Message Passing for Learning on Hypergraphs](https://mlsanity.com/paper/2402.05569/) (2024)
- [Implicit Hypergraph Neural Networks: A Stable Framework for Higher-Order Relational Learning with Provable Guarantees](https://mlsanity.com/paper/2508.09427/) (2025)
- [A recursive theta body for hypergraphs](https://mlsanity.com/paper/2206.03929/) (2022)
- [Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation](https://mlsanity.com/paper/2303.10980/) (2023)
- [On Homomorphism Indistinguishability and Hypertree Depth](https://mlsanity.com/paper/2404.10637/) (2024)
- [Parameter-Free Hypergraph Neural Network for Few-Shot Node Classification](https://mlsanity.com/paper/2510.21462/) (2025)

## Abstract (arXiv)

Hypergraphs provide a natural framework to model higher-order interactions in scientific, social, and biological systems. Hypergraph neural networks (HGNNs) aim to learn from such data, yet it remains unclear which higher-order structures these models can represent. We show that hypergraph expressivity is governed by which small patterns an architecture can detect and count. We formalize this via homomorphism densities, which measure how often a structural motif appears in a hypergraph. Combining classical homomorphism-count completeness with invariant approximation, we show that homomorphism densities generate all continuous hypergraph invariants and organize them into a strict hierarchy indexed by hypertree width. This yields a Width Wall: a fundamental architectural limit beyond which no hidden dimension, training procedure or fixed-depth HGNN can represent invariants requiring wider patterns. Our framework provides a unified characterization of 15 HGNN architectures, precisely identifies information lost by clique expansion, and motivates density-aware models that extend expressivity beyond bounded-width message passing. We experimentally validate this finding on an APPLICATION NODE CLASSIFICATION SUITE of real-world hypergraphs, where the Width Wall predicts when graph-reduction baselines fail and when density features help.