On the Expressiveness and Generalization of Hypergraph Neural Networks
This work addresses the theoretical understanding of HyperGNNs for graph reasoning problems, but it is incremental as it builds on existing neural network frameworks.
The paper analyzes the expressiveness and structural generalization of hypergraph neural networks (HyperGNNs), establishing a hierarchy of solvable problems based on hyperparameters and showing they can be trained on small graphs and generalize to larger ones, with empirical validation.
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.