The WidthWall: A Strict Expressivity Hierarchy for Hypergraph Neural Networks

• URL: http://arxiv.org/abs/2605.13690v1
• Date: Wed, 13 May 2026 15:43:31 GMT
• Title: The WidthWall: A Strict Expressivity Hierarchy for Hypergraph Neural Networks
• Abstract summary: We show that hypergraph expressivity is governed by which small patterns an architecture can detect and count.<n>We show that homomorphism densities generate all continuous hypergraph invariants and organize them into a strict hierarchy indexed by hypertree width.<n>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.
• Score: 23.46151626569377
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Hypergraph as Language [49.35033483821496]
  We propose a hypergraph-native alignment framework for large language models.<n>For hypergraph structures, existing methods often fail to preserve the native semantics that multiple objects are jointly connected by the same high-order relation.<n>We show that Hyper-Align significantly outperforms existing methods across in-domain and zero-shot evaluations.
  arXiv  Detail & Related papers  (2026-05-21T01:09:48Z)
• Can we ease the Injectivity Bottleneck on Lorentzian Manifolds for Graph Neural Networks? [0.0]
  Lorentzian Graph Isomorphic Network (LGIN) is a novel HGNN designed for enhanced discrimination within the Lorentzian model.<n>LGIN is the first to adapt principles of powerful, highly discriminative GNN architectures to a Riemannian manifold.
  arXiv  Detail & Related papers  (2025-03-31T18:49:34Z)
• SPHINX: Structural Prediction using Hypergraph Inference Network [19.853413818941608]
  We introduce Structural Prediction using Hypergraph Inference Network (SPHINX), a model that learns to infer a latent hypergraph structure in an unsupervised way.<n>We show that the recent advancement in $k$-subset sampling represents a suitable tool for producing discrete hypergraph structures.<n>The resulting model can generate the higher-order structure necessary for any modern hypergraph neural network.
  arXiv  Detail & Related papers  (2024-10-04T07:49:57Z)
• Topology-guided Hypergraph Transformer Network: Unveiling Structural Insights for Improved Representation [1.1606619391009658]
  We propose a Topology-guided Hypergraph Transformer Network (THTN) In this model, we first formulate a hypergraph from a graph while retaining its structural essence to learn higher-order relations within the graph. We present a structure-aware self-attention mechanism that discovers the important nodes and hyperedges from both semantic and structural viewpoints.
  arXiv  Detail & Related papers  (2023-10-14T20:08:54Z)
• Sheaf Hypergraph Networks [20.91851106383122]
  We introduce cellular sheaves for hypergraphs, a mathematical construction that adds extra structure to the conventional hypergraph.<n> Drawing inspiration from existing Laplacians in the literature, we develop two unique formulations of sheaf hypergraph Laplacians.<n>We employ these sheaf hypergraph Laplacians to design two categories of models: Sheaf Hypergraph Neural Networks and Sheaf Hypergraph Convolutional Networks.
  arXiv  Detail & Related papers  (2023-09-29T10:25:43Z)
• From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
  We present an expressive family of parameterized, hypergraph-regularized energy functions. We then demonstrate how minimizers of these energies effectively serve as node embeddings. We draw parallels between the proposed bilevel hypergraph optimization, and existing GNN architectures in common use.
  arXiv  Detail & Related papers  (2023-06-16T04:40:59Z)
• Tensorized Hypergraph Neural Networks [69.65385474777031]
  We propose a novel adjacency-tensor-based textbfTensorized textbfHypergraph textbfNeural textbfNetwork (THNN) THNN is faithful hypergraph modeling framework through high-order outer product feature passing message. Results from experiments on two widely used hypergraph datasets for 3-D visual object classification show the model's promising performance.
  arXiv  Detail & Related papers  (2023-06-05T03:26:06Z)
• Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs [59.71134113268709]
  We present General Hypergraph Spectral Convolution(GHSC), a general learning framework that can handle EDVW and EIVW hypergraphs. In this paper, we show that the proposed framework can achieve state-of-the-art performance. Experiments from various domains including social network analysis, visual objective classification, protein learning demonstrate that the proposed framework can achieve state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-03-31T10:46:47Z)
• ACE-HGNN: Adaptive Curvature Exploration Hyperbolic Graph Neural Network [72.16255675586089]
  We propose an Adaptive Curvature Exploration Hyperbolic Graph NeuralNetwork named ACE-HGNN to adaptively learn the optimal curvature according to the input graph and downstream tasks. Experiments on multiple real-world graph datasets demonstrate a significant and consistent performance improvement in model quality with competitive performance and good generalization ability.
  arXiv  Detail & Related papers  (2021-10-15T07:18:57Z)
• Generative hypergraph clustering: from blockmodels to modularity [26.99290024958576]
  We propose an expressive generative model of clustered hypergraphs with heterogeneous node degrees and edge sizes. We show that hypergraph Louvain is highly scalable, including as an example an experiment on a synthetic hypergraph of one million nodes. We use our model to analyze different patterns of higher-order structure in school contact networks, U.S. congressional bill cosponsorship, U.S. congressional committees, product categories in co-purchasing behavior, and hotel locations.
  arXiv  Detail & Related papers  (2021-01-24T00:25:22Z)
• Learning over Families of Sets -- Hypergraph Representation Learning for Higher Order Tasks [12.28143554382742]
  We develop a hypergraph neural network to learn provably expressive representations of variable sized hyperedges. We evaluate performance on multiple real-world hypergraph datasets and demonstrate consistent, significant improvement in accuracy, over state-of-the-art models.
  arXiv  Detail & Related papers  (2021-01-19T18:37:50Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.