The WidthWall: A Strict Expressivity Hierarchy for Hypergraph Neural Networks
For researchers designing HGNNs, this work provides a theoretical foundation for understanding and comparing expressivity, identifying fundamental limitations of current architectures.
The paper establishes a strict expressivity hierarchy for hypergraph neural networks (HGNNs) based on hypertree width, showing that homomorphism densities generate all continuous hypergraph invariants and that there is a fundamental limit (Width Wall) beyond which no fixed-depth HGNN can represent invariants requiring wider patterns. The framework characterizes 15 HGNN architectures and is validated on node classification tasks, where the Width Wall predicts when graph-reduction baselines fail and density features help.
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.