The WidthWall: A Strict Expressivity Hierarchy for Hypergraph Neural Networks

Problem
This preprint addresses a significant gap in the understanding of hypergraph neural networks (HGNNs) regarding their expressivity and the higher-order structures they can represent. While HGNNs are designed to model complex interactions in various domains, the limitations of their architectural capabilities in capturing specific structural motifs have not been thoroughly explored. The authors propose a formal framework to characterize these limitations, which they term the “Width Wall,” providing a systematic approach to understanding the expressivity of different HGNN architectures.

Method
The core technical contribution of this work is the introduction of homomorphism densities as a means to quantify the expressivity of HGNNs. The authors establish a connection between homomorphism-count completeness and invariant approximation, demonstrating that homomorphism densities can generate all continuous hypergraph invariants. They organize these invariants into a strict hierarchy indexed by hypertree width, which serves as a critical threshold for expressivity. The authors analyze 15 existing HGNN architectures within this framework, identifying the specific information loss associated with clique expansion. They advocate for the development of density-aware models that can extend expressivity beyond the limitations imposed by bounded-width message passing. The experimental validation is conducted on an application node classification suite using real-world hypergraphs, where the Width Wall’s predictions are tested against graph-reduction baselines.

Results
The experimental results indicate that the Width Wall effectively predicts the performance of various HGNN architectures on the application node classification suite. Specifically, the authors report that models operating below the Width Wall exhibit significant performance degradation when faced with hypergraphs requiring wider patterns for accurate representation. In contrast, density-aware models that leverage the identified structural motifs demonstrate improved expressivity and classification accuracy. The results show that the proposed framework can accurately forecast when traditional graph-reduction methods fail, highlighting the importance of considering hypergraph density features in model design.

Limitations
The authors acknowledge that their framework primarily focuses on the theoretical aspects of hypergraph expressivity and may not account for all practical considerations in HGNN design. They do not extensively explore the computational complexity associated with implementing density-aware models, which could pose challenges in real-world applications. Additionally, the study is limited to the specific architectures analyzed, and the generalizability of the findings to other HGNN designs remains to be validated. The reliance on homomorphism densities may also overlook other potential factors influencing expressivity.

Why it matters
This work has significant implications for the design and evaluation of HGNNs, as it provides a rigorous theoretical foundation for understanding their expressivity limitations. By formalizing the concept of the Width Wall, the authors encourage researchers to consider higher-order structures in their models, potentially leading to more effective applications in complex domains such as social networks, biological systems, and scientific data analysis. The insights gained from this study can guide future research in developing more expressive HGNN architectures and inform the design of algorithms that leverage hypergraph structures more effectively.

Authors: Fengqing Jiang, Yuetai Li, Yichen Feng, Kaiyuan Zheng, Luyao Niu, Bhaskar Ramasubramanian, Basel Alomair, Linda Bushnell et al.
Source: arXiv:2605.13690
URL: https://arxiv.org/abs/2605.13690v1