On the Expressiveness and Generalization of Hypergraph Neural Networks
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.
Zhezheng Luo, Jiayuan Mao, Joshua B. Tenenbaum, Leslie Pack Kaelbling
# On the Expressiveness and Generalization of

###### Abstract

This extended abstract describes a framework for analyzing the expressiveness, learning, and (structural) generalization of hypergraph neural networks (Hyper-GNNs). 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 entries. 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.

## 1 Introduction

Reasoning over graph-structured data is an important task in many applications, including molecule analysis, social network modeling, and knowledge graph reasoning [1; 2; 3]. While we have seen great success of various relational neural networks, such as Graph Neural Networks [GNNs; 4] and Neural Logical Machines [NLM; 5] in a variety of applications [6; 7; 8], we do not yet have a full understanding of how different design parameters, such as the depth of the neural network, affects the expressiveness of these models, or how effectively these models generalize from limited data.

This paper analyzes the _expressiveness_ and _generalization_ of relational neural networks applied to _hypergraphs_, which are graphs with edges connecting more than two nodes. Literature has shown that even when the inputs and outputs of models have only unary and binary relations, allowing intermediate hyperedge representations increases the expressiveness [9; 10]. In this paper, we further formally show the "if and only if" conditions for the expressive power with respect to the edge arity. That is, \(k\)-ary hyper-graph neural networks are sufficient and necessary for realizing FOC-\(k\), a fragment of first-order logic with counting quantification which involves at most \(k\) variables. This is a helpful result because now we can determine whether a specific hypergraph neural network can solve a problem by understanding what form of logic formula can represent the solution to this problem. Next, we formally described the relationship between expressiveness and non-constant-depth networks. We state a conjecture about the "depth hierarchy," and connect the potential proof of this conjecture to the distributed computing literature.

Furthermore, we prove, under certain assumptions, it is possible to train a hypergraph neural networks on a finite set of small graphs, and it will generalize to arbitrarily large graphs. This ability results from the weight-sharing nature of hypergraph neural networks. We hope our work can serve as a foundation for designing hypergraph neural networks: to solve a specific problem, what arity do you need? What depth do you need? Will my model have structural generalization (i.e., to larger graphs)? Our theoretical results are further supported by experiments, for empirical demonstrations.
## 2 Hypergraph Reasoning Problems and Hypergraph Neural Networks

A _hypergraph representation_\(G\) is a tuple \((V,X)\), where \(V\) is a set of entities (nodes), and \(X\) is a set of _hypergraph representation functions_. Specifically, \(X=\{X_{0},X_{1},X_{2},\cdots,X_{k}\}\), where \(X_{j}:(v_{1},v_{2},\cdots,v_{j})\rightarrow\mathcal{S}\) is a function mapping every tuple of \(j\) nodes to a value. We call \(j\) the _arity_ of the hyperedge and \(k\) is the max arity of input hyperedges. The range \(\mathcal{S}\) can be any set of discrete labels that describes relation type, or a scalar number (e.g., the length of an edge), or a vector. We will use the arity 0 representation \(X_{0}(\emptyset)\rightarrow\mathcal{S}\) to represent any global properties of the graph.

A _graph reasoning function_\(f\) is a mapping from a hypergraph representation \(G=(V,X)\) to another hyperedge representation function \(Y\) on \(V\). As concrete examples, asking whether a graph is fully connected is a graph classification problem, where the output \(Y=\{Y_{0}\}\) and \(Y_{0}(\emptyset)\rightarrow\mathcal{S}^{\prime}=\{0,1\}\) is a global label; finding the set of disconnected subgraphs of size \(k\) is a \(k\)-ary hyperedge classification problem, where the output \(Y=\{Y_{k}\}\) is a label for each \(k\)-ary hyperedges.

There are two main motivations and constructions of a neural network applied to graph reasoning problems: message-passing-based and first-order-logic-inspired. Both approaches construct the computation graph layer by layer. The input is the features of nodes and hyperedges, while the output is the per-node or per-edge prediction of desired properties, depending on the task.

In a nutshell, within each layer, _message-passing-based_ hypergraph neural networks, Higher-Order GNNs [11], perform message passing between each hyperedge and its neighbours. Specifically, we say the j-th neighbour set of a hyperedge \(u=(x_{1},x_{2},\cdots,x_{i})\) of arity \(i\) is \(N_{j}(u)=\{(x_{1},x_{2},\cdots,x_{j-1},r,x_{j+1},\cdots,x_{i})\}\), where \(r\in V\). Then, the all neighbours of node \(u\) is the union of all \(N_{j}\)'s, where \(j=1,2,\cdots,i\).

On the other hand, first-order-logic-inspired hypergraph neural networks consider building neural networks that can emulate first logic formulas. Neural Logic Machines [NLM; 5] are defined in terms of a set of input hyperedges; each hyperedge of arity \(k\) is represented by a vector of (possibly real) values obtained by applying all of the k-ary predicates in the domain to the tuple of vertices it connects. Each layer in an NLM learns to apply a linear transformation with nonlinear activation and quantification operators (analogous to the for all \(\forall\) and exists \(\exists\) quantifiers in first-order logic), on these values. It is easy to prove, by construction, that given a sufficient number of layers and maximum arity, NLMs can learn to realize any first-order-logic formula. For readers who are not familiar with HO-GNNs [11] and NLMs [5], we include a mathematical summary of their computation graph in Appendix A. Our analysis starts from the following theorem.

**Theorem 2.1**.: HO-GNNs [11] are equivalent to NLMs in terms of expressiveness. Specifically, a \(B\)-ary HO-GNN is equivalent to an NLM applied to \(B+1\)-ary hyperedges. Proofs are in Appendix A.3.

Given Theorem 2.1, we can focus on just one single type of hypergraph neural network. Specifically, we will focus on Neural Logic Machines [NLM; 5] because its architecture naturally aligns with first-order logic formula structures, whilst will aid some of our analysis. An NLM is characterized by hyperparameters \(D\) (depth), and \(B\) maximum arity. We are going to assume that \(B\) is a constant, but \(D\) can be dependent on the size of the input graph. We will use NLM[\(D\), \(B\)] to denote an NLM family with depth \(D\) and max arity \(B\). Other parameters such as the width of neural networks affects the precise details of what functions can be realized, as it does in a regular neural network, but does not affect the analyses in this extended abstract. Furthermore, we will be focusing on neural networks with bounded precision, and briefly discuss how our results generalize to unbounded precision cases.

## 3 Expressiveness of Relational Neural Networks

We start from a formal definition of hypergraph neural network expressiveness.

**Definition 3.1** (Expressiveness).: We say a model family \(\mathcal{M}_{1}\) is _at least expressive as \(\mathcal{M}_{2}\)_, written as \(\mathcal{M}_{1}\succcurlyeq\mathcal{M}_{2}\), if for all \(M_{2}\in\mathcal{M}_{2}\), there exists \(M_{1}\in\mathcal{M}_{1}\) such that \(M_{1}\) can realize \(M_{2}\). A model family \(\mathcal{M}_{1}\) is _more expressive than \(\mathcal{M}_{2}\)_, written as \(\mathcal{M}_{1}\succ\mathcal{M}_{2}\), if \(\mathcal{M}_{1}\succcurlyeq\mathcal{M}_{2}\) and \(\exists M_{1}\in\mathcal{M}_{1}\), \(\forall M_{2}\in\mathcal{M}_{2}\), \(M_{2}\) can not realize \(M_{1}\).

**Arity Hierarchy** We first aim to quantify how the maximum arity \(B\) of the network's representation affects its expressiveness and find that, in short, even if the inputs and outputs of neural networks are of low arity, the higher the maximum arity for intermediate layers, the more expressive the NLM is.

**Corollary 3.1** (Arity Hierarchy).: For any maximum arity \(B\), there exists a depth \(D^{*}\) such that: \(\forall D\geq D^{*}\), NLM[\(D\), \(B+1\)] is more expressive than NLM[\(D\), \(B\)]. This theorem applies to both
fixed-precision and unbounded-precision networks. Here, by fixed-precision, we mean that the results of intermediate layers (tensors) are constant-sized (e.g., \(W\) bits per entry). Practical GNNs are all fixed-precision because real number types in modern computers have finite precision.

_Proof sketch:_ Our proof slightly extends the proof of Morris et al. [11]. First, the set of graphs distinguishable by NLM[\(D\), \(B\)] is bounded by graphs distinguishable by a \(D\)-round order-\(B\) Weisfeiler-Leman test [12]. If models in NLM[\(D\), \(B\)] cannot generate different outputs for two distinct hypergraphs \(G_{1}\) and \(G_{2}\), but there exists \(M\in\) NLM[\(D,B+1\)] that _can_ generate different outputs for \(G_{1}\) and \(G_{2}\), then we can construct a graph classification function \(f\) that NLM[\(D\), \(B+1\)] (with some fixed precision) can realize but NLM[\(D\), \(B\)] (even with unbounded precision) cannot.* The full proof is described in Appendix B.1.

Footnote *: Note that the arity hierarchy is applied to fixed-precision and unbounded-precision separately. For example, NLM[\(D\), \(B\)] with unbounded precision is incomparable with NLM[\(D\), \(B+1\)] with fixed precision.

It is also important to quantify the minimum arity for realizing certain graph reasoning functions.

**Corollary 3.2** (FOL realization bounds).: Let \(\text{FOC}_{B}\) denote a fragment of first order logic with at most \(B\) variables, extended with counting quantifiers of the form \(\exists^{\geq n}\phi\), which state that there are at least \(n\) nodes satisfying formula \(\phi\)[13].

* (Upper Bound) Any function \(f\) in \(\text{FOC}_{B}\) can be realized by NLM[\(D\), \(B\)] for some \(D\).
* (Lower Bound) There exists a function \(f\in\text{FOC}_{B}\) such that for all \(D\), \(f\) cannot be realized by NLM[\(D\),\(B-1\)].

_Proof:_ The upper bound part of the claim has been proved by Barcelo et al. [14] for \(B=2\). The results generalize easily to arbitrary \(B\) because the counting quantifiers can be realized by sum aggregation. The lower bound part can be proved by applying Section 5 of [13], in which they show that \(\text{FOC}_{B}\) is equivalent to a \((B-1)\)-dimensional WL test in distinguishing non-isomorphic graphs. Given that NLM[\(D\), \(B-1\)] is equivalent to the \((B-2)\)-dimensional WL test of graph isomorphism, there must be an FOL\({}_{B}\) formula that distinguishes two non-isomorphic graphs that NLM[\(D\), \(B-1\)] cannot. Hence, FOL\({}_{B}\) cannot be realized by NLM[\(\cdot\), \(B-1\)].

**Depth Hierarchy** We now study the dependence of the expressiveness of NLMs on depth \(D\). Neural networks are generally defined to have a fixed depth, but allowing them to have a depth that is dependent on the number of nodes \(n=|V|\) in the graph, in many cases, can substantially increase their expressive power [15, see also Theorem 3.4 and Appendix B for examples]. In the following, we define a _depth hierarchy_ by analogy to the _time hierarchy_ in computational complexity theory [16], and we extend our notation to let NLM[\(O(f(n)),B\)] denote the class of adaptive-depth NLMs in which the growth-rate of depth \(D\) is bounded by \(O(f(n))\).

**Conjecture 3.3** (Depth hierarchy).: For any maximum arity \(B\), for any two functions \(f\) and \(g\), if \(g(n)=o(f(n)/\log n)\), that is, \(f\) grows logarithmically more quickly than \(g\), then fixed-precision NLM[\(O(f(n)),B\)] is more expressive than fixed-precision NLM[\(O(g(n)),B\)].

There is a closely related result for the _congested clique_ model in distributed computing, where [17] proved that \(\text{CLIQUE}(g(n))\subsetneqq\text{CLIQUE}(f(n))\) if \(g(n)=o(f(n))\). This result does not have the \(\log n\) gap because the congested clique model allows \(\log n\) bits to transmit between nodes at each iteration, while fixed-precision NLM allows only a constant number of bits. The reason why the result on congested clique can not be applied to fixed-precision NLMs is that congested clique assumes unbounded precision representation for each individual node.

However, Conjecture 3.3 is not true for NLMs with unbounded precision, because there is an upper bound depth \(O(n^{B-1})\) for a model's expressiveness power (see appendix B.2 for a formal statement and the proof). That is, an unbounded-precision NLM can not achieve stronger expressiveness by increasing its depth beyond \(O(n^{B-1})\).

It is important to point out that, to realize a specific graph reasoning function, NLMs with different maximum arity \(B\) may require different depth \(D\). Furer [18] provides a general construction for problems that higher-dimensional NLMs can solve in asymptotically smaller depth than lower-dimensional NLMs. In the following we give a concrete example for computing _S-T Connectivity-\(k\)_, which asks whether there is a path of nodes from \(S\) and \(T\) in a graph, with length \(\leq k\).

**Theorem 3.4** (S-T Connectivity-\(k\) with Different Max Arity).: For any function \(f(k)\), if \(f(k)=o(k)\), NLM[\(O(f(k))\), \(2\)] cannot realize S-T Connectivity-\(k\). That is, S-T Connectivity-\(k\) requires depth at least \(O(k)\) for a relational neural network with an maximum arity of \(B=2\). However, S-T Connectivity-\(k\)_can_ be realized by NLM[\(O(\log k)\), \(3\)].
Proof sketch.: For any integer \(k\), we can construct a graph with two chains of length \(k\), so that if we mark two of the four ends as \(S\) or \(T\), any NLM\([k-1,2]\) cannot tell whether \(S\) and \(T\) are on the same chain. The full proof is described in Appendix B.3.

There are many important graph reasoning tasks that do not have known depth lower bounds, including all-pair connectivity and shortest distance [19, 20]. In Appendix B.3, we discuss the concrete complexity bounds for a series of graph reasoning problems.

## 4 Learning and Generalization in Relational Neural Networks

Given our understanding of what functions can be realized by NLMs, we move on to the problems of learning them: Can we effectively learn a NLMs to solve a desired task given a sufficient number of input-output examples? In this paper, we show that applying _enumerative training_ with examples up to some fixed graph size can ensure that the trained neural network will generalize to all graphs _larger_ than those appearing in the training set.

A critical determinant of the generalization ability for NLMs is the aggregation function. Specifically, Xu et al. [21] have shown that using _sum_ as the aggregation function provides maximum expressiveness for graph neural networks. However, sum aggregation cannot be implemented in fixed-precision models, because as the graph size \(n\) increases, the range of the sum aggregation also increases.

**Definition 4.1** (Fixed-precision aggregation function).: An aggregation function is _fixed precision_ if it maps from any finite _set_ of inputs with values drawn from _finite domains_ to a _fixed finite_ set of possible output values; that is, the cardinality of the range of the function cannot grow with the number of elements in the input set. Two useful fixed-precision aggregation functions are _max_, which computes the dimension-wise maximum over the set of input values, and _fixed-precision mean_, which approximates the dimension-wise mean to a fixed decimal place.

In order to focus on structural generalization in this section, we consider an _enumerative_ training paradigm. When the input hypergraph representation domain \(\mathcal{S}\) is a finite set, we can enumerate the set \(\mathcal{G}_{\leq N}\) of all possible input hypergraph representations of size bounded by \(N\). We first enumerate all graph sizes \(n\leq N\); for each \(n\), we enumerate all possible values assigned to the hyperedges in the input. Given training size \(N\), we enumerate all inputs in \(\mathcal{G}_{\leq N}\), associate with each one the corresponding ground-truth output representation, and train the model with these input-output pairs.

This has much stronger data requirements than the standard sampling-based training mechanisms in machine learning. In practice, this can be approximated well when the input domain \(\mathcal{S}\) is small and the input data distribution is approximately uniformly distributed. The enumerative learning setting is studied by the _language identification in the limit_ community [22], in which it is called _complete presentation_. This is an interesting learning setting because even if the domain for each individual hyperedge representation is finite, as the graph size can go arbitrarily large, the number of possible inputs is enumerable but unbounded.

**Theorem 4.1** (Fixed-precision generalization under complete presentation).: For any hypergraph reasoning function \(f\), if it can be realized by a fixed-precision relational neural network model \(\mathcal{M}\), then there exists an integer \(N\), such that if we train the model with complete presentation on all input hypergraph representations with size smaller than \(N\), \(\mathcal{G}_{\leq N}\), then for all \(M\in\mathcal{M}\),

\[\sum_{G\in\mathcal{G}_{\leq N}}1[M(G)\neq f(G)]=0\implies\forall G\in\mathcal{ G}_{\infty}:M(G)=f(G).\]

That is, as long as \(M\) fits all training examples, it will generalize to all possible hypergraphs in \(\mathcal{G}_{\infty}\).

Proof.: The key observation is that for any fixed vector representation length \(W\), there are only a finite number of distinctive models in a fixed-precision NLM family, _independent of the graph size \(n\)_. Let \(W_{b}\) be the number of bits in each intermediate representation of a fixed-precision NLM. There are at most \((2^{W_{b}})^{2^{W_{b}}}\) different mappings from inputs to outputs. Hence, if \(N\) is sufficiently large to enumerate all input hypergraphs, we can always identify the correct model in the hypothesis space.

Our results are related to the _algorithmic alignment_ approach [23, 24]. In contrast to their Probably Approximately Correct (PAC) Learning bounds for sample efficiency, our expressiveness results directly quantifies whether a hypergraph neural network can be trained to realize a specific function.
## 5 Related Work

Solving problems on graphs of arbitrary size is studied in many fields. NLMs can be viewed as circuit families with constrained architecture. In distributed computation, the congested clique model can be viewed as 2-arity NLMs, where nodes have identities as extra information. Common graph problems including sub-structure detection[25, 26] and connectivity[19] are studied for lower bounds in terms of depth, width and communication. This has been connected to GNNs for deriving expressiveness bounds [27].

Studies have been conducted on the expressiveness of GNNs and their variants. Xu et al. [21] provide an illuminating characterization of GNN expressiveness in terms of the WL graph isomorphism test. Azizian and Lelarge [9] analyze the expressiveness of higher-order Folklore GNNs by connecting them with high-dimensional WL-tests. We have the similar results in the arity hierarchy. Barcelo et al. [14] reviewed GNNs from the logical perspective and rigorously refined their logical expressiveness with respect to fragments of first-order logic. Dong et al. [5] proposed Neural Logical Machines (NLMs) to reason about higher-order relations, and showed that increasing order inreases expressiveness. It is also possible to gain expressiveness using unbounded computation time, as shown by the work of Dehghani et al. [15] on dynamic halting in transformers.

It is interesting that GNNs may generalize to larger graphs. Xu et al. [23, 24] have studied the notion of _algorithmic alignment_ to quantify such structural generalization. Dong et al. [5] provided empirical results showing that NLMs generalize to much larger graphs on certain tasks. Buffelli et al. [28] introduced a regularization technique to improve GNNs' generalization to larger graphs and demonstrated its effectiveness empirically. In Xu et al. [23], they analyzed and compared the sample complexity of Graph Neural Networks. This is different from our notion of expressiveness for realizing functions. In Xu et al. [24], they showed emperically on some problems (e.g., MaxDegree, Shortest Path, and n-body problem) that algorithm alignment helps GNNs to extrapolate, and theoretically proved the improvement by algorithm alignment on the Max-Degree problem. In this extended abstract, instead of focusing on computing specific graph problems, we analyzed how GNNs can extrapolate to larger graphs in a general case, based on the assumption of fixed precision computation.

## 6 Conclusion

In this extended abstract, we have shown the substantial increase of expressive power due to higher-arity relations and increasing depth, and have characterized very powerful structural generalization from training on small graphs to performance on larger ones. All theoretical results are further supported by the empirical results, discussed in Appendix C. Although many questions remain open about the overall generalization capacity of these models in continuous and noisy domains, we believe this work has shed some light on their utility and potential for application in a variety of problems.

**Acknowledgement.** We thank anonymous reviewers for their comments. This work is in part supported by ONR MURI N00014-16-1-2007, the Center for Brain, Minds, and Machines (CBMM, funded by NSF STC award CCF-1231216), NSF grant 2214177, AFOSR grant FA9550-22-1-0249, ONR grant N00014-18-1-2847, the MIT Quest for Intelligence, MIT-IBM Watson Lab. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of our sponsors.
