# On the Expressiveness and Generalization of Hypergraph Neural Networks

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 35 references that are in the map.
- First posted on arXiv 9 Mar 2023.

## Builds on (most cited first, 21 of 21)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Hypergraph Neural Networks](https://mlsanity.com/paper/1809.09401/) (2018)
- [Hyperbolic Graph Neural Networks](https://mlsanity.com/paper/1910.12892/) (2019)
- [Hypergraph Convolution and Hypergraph Attention](https://mlsanity.com/paper/1901.08150/) (2019)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Neural Logic Machines](https://mlsanity.com/paper/1904.11694/) (2019)
- [UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks](https://mlsanity.com/paper/2105.00956/) (2021)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Be More with Less: Hypergraph Attention Networks for Inductive Text Classification](https://mlsanity.com/paper/2011.00387/) (2020)
- [SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks](https://mlsanity.com/paper/2207.07888/) (2022)
- [Upper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logic](https://mlsanity.com/paper/1605.03480/) (2016)
- [Towards a complexity theory for the congested clique](https://mlsanity.com/paper/1705.03284/) (2017)
- [Connectivity Lower Bounds in Broadcast Congested Clique](https://mlsanity.com/paper/1905.09016/) (2019)

## Built on by (most cited first, 5 of 5)

- [A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guide](https://mlsanity.com/paper/2404.01039/) (2024)
- [What Planning Problems Can A Relational Neural Network Solve?](https://mlsanity.com/paper/2312.03682/) (2023)
- [Learning Linear Attention in Polynomial Time](https://mlsanity.com/paper/2410.10101/) (2024)
- [Weisfeiler and Lehman Go Categorical](https://mlsanity.com/paper/2602.06787/) (2026)
- [Enhancing the Utility of Higher-Order Information in Relational Learning](https://mlsanity.com/paper/2502.09570/) (2025)

## Abstract (arXiv)

This extended abstract describes a framework for analyzing the expressiveness, learning, and (structural) generalization of hypergraph neural networks (HyperGNNs). Specifically, we focus on how HyperGNNs can learn from finite datasets and generalize structurally to graph reasoning problems of arbitrary input sizes. Our first contribution is a fine-grained analysis of the expressiveness of HyperGNNs, that is, the set of functions that they can realize. Our result is a hierarchy of problems they can solve, defined in terms of various hyperparameters such as depths and edge arities. Next, we analyze the learning properties of these neural networks, especially focusing on how they can be trained on a finite set of small graphs and generalize to larger graphs, which we term structural generalization. Our theoretical results are further supported by the empirical results.