The Width Wall: An Expressivity Framework for Hypergraph Neural Networks

Hypergraphs provide a natural framework for modeling 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 structural distinctions their representations preserve. We study this question through homomorphism densities, which measure how often finite patterns map into a hypergraph. Combining homomorphism-count completeness with invariant approximation, we show that finite pattern densities generate a dense algebra of continuous hypergraph invariants and organize them into a filtration indexed by generalized hypertree width. This yields the notion of a Width Wall: when an architecture is provably restricted to width-$r$ information, no increase in hidden dimension, readout complexity, or optimization can recover distinctions erased beyond that representation. Our framework precisely characterizes information lost by clique expansion, with a Steiner–Pasch construction giving an explicit width-2 separator. We further study exact pattern-alignment invariants and introduce DensNet-D, which augments an incidence-based backbone with Monte Carlo estimates of local pattern densities. Experiments on four real-world node-classification benchmarks show that these structural features can recover information lost by projection and improve a matched AllDeepSets backbone.