mlsanityData to 7 Oct 2026

On the Expressiveness and Generalization of Hypergraph Neural Networks

arXiv 2303.05490 ↗First posted 9 Mar 2023cs.LG cs.AI stat.MLcited by 5

Not on the map. Why?

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.

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

Builds on

21 of 35 references.

References · 21

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  3. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,684
  4. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  6. 2018Universal Transformerscited by 613
  7. 2018Hypergraph Neural Networkscited by 482
  8. 2019Hyperbolic Graph Neural Networkscited by 244
  9. 2019Hypergraph Convolution and Hypergraph Attentioncited by 226
  10. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  11. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  12. 2019What Can Neural Networks Reason About?cited by 155
9 more
  1. 2019Neural Logic Machinescited by 144
  2. 2021UniGNN: a Unified Framework for Graph and Hypergraph Neural Networkscited by 127
  3. 2019Neural Execution of Graph Algorithmscited by 118
  4. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  5. 2020Be More with Less: Hypergraph Attention Networks for Inductive Text Classificationcited by 73
  6. 2022SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networkscited by 36
  7. 2016Upper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logiccited by 7
  8. 2017Towards a complexity theory for the congested cliquecited by 1
  9. 2019Connectivity Lower Bounds in Broadcast Congested Cliquecited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 1; 2026: 1.

5 papers.

  1. 2024A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guidecited by 22
  2. 2023What Planning Problems Can A Relational Neural Network Solve?cited by 8
  3. 2024Learning Linear Attention in Polynomial Timecited by 5
  4. 2026Weisfeiler and Lehman Go Categoricalcited by 1
  5. 2025Enhancing the Utility of Higher-Order Information in Relational Learningcited by 0