On the Expressiveness and Learning of Relational Neural Networks on Hypergraphs
Authors: Zhezheng Luo
Jiayuan Mao
Joshua B. Tenenbaum
Leslie Pack Kaelbling
Venue: ICLR 2022 Submitted (2022)
Keywords: graph neural networks
deep learning theory

Abstract: This paper presents a framework for analyzing the expressiveness and learning of relational models applied to hypergraph reasoning tasks. We start with a general framework that unifies several relational neural network architectures: graph neural networks, neural logical machines, and transformers. Our first contribution is a fine-grained analysis of the expressiveness of these neural networks, that is, the set of functions that they can realize and the set of problems that they can solve. Our result is a hierarchy of problems they can solve, defined in terms of various hyperparameters such as depth and width. Next, we analyze the learning properties of these neural networks, especially focusing on how they can be trained on a small graphs and generalize to larger graphs. Our theoretical results are further supported by the empirical results illustrating the optimization and generalization of these models based on gradient-descent training.

Under review as a conference paper at ICLR 2022
ON THE EXPRESSIVENESS AND LEARNING OF RELA- TIONAL NEURAL NETWORKS ON HYPERGRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
This paper presents a framework for analyzing the expressiveness and learning of relational models applied to hypergraph reasoning tasks. We start with general framework that unifies several relational neural network architectures: graph neural networks, neural logical machines, and transformers. Our first contribution is a fine-grained analysis of the expressiveness of these neural networks, that is, the set of functions that they can realize and the set of problems that they can solve. Our result is a hierarchy of problems they can solve, defined in terms of various hyperparameters such as depth and width. Next, we analyze the learning properties of these neural networks, especially focusing on how they can be trained on small graphs and generalize to larger graphs. Our theoretical results are further supported by the empirical results illustrating the optimization and generalization of these models based on gradient-descent training.
INTRODUCTION
Reasoning over graph-structured data is an important task in various applications, including molecule analysis, social network modeling, and knowledge graph reasoning (Gilmer et al., 2017; Schlichtkrull et al., 2018; Liu et al., 2017). While we have seen great success of various relational neural networks, such as Graph Neural Networks (GNNs; Scarselli et al., 2008), Neural Logical Machines (NLM; Dong et al., 2019), and Transformers (Vaswani et al., 2017) in a variety of applications (Battaglia et al., 2018; Merkwirth & Lengauer, 2005; Veličković et al., 2020), we 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 data.
In this paper, we develop general framework, generalized relational neural networks (ReINNs), that unifies large class of relational neural networks including GNNs, NLMs, and Transformers. Unlike previous work that analyzes the expressiveness of graph neural networks (Xu al., 2019; 2020; Barceló et al., 2020), our framework applies to hypergraphs, i.c., graphs that have representations that directly relate groups of more than two nodes.
Next, we quantify the expressiveness of generalized relational neural networks in terms of their structural parameters; in particular, the maximum arity of hyperedges and the depth of the network. We formally proved the "if and only if" conditions for the expressive power w.r.t. the arity. That is, k-ary hyper-graph relational neural networks are sufficient and necessary for realizing FOC- k. a fragment of first-order logic which involves at most k variables. This is helpful result because now we can determine whether a ReINN can solve a problem by thinking whether logic formula can represent the solution to this problem. Next, we formally described the relationship between expressiveness and non-constant-depth ReINNs. We proposed a conjecture about the "depth hierarchy." and we connect the potential proof of this conjecture to distributed computing literature. We also develope an upper bound for ReINNs. This is a very interesting result: applying a k-ary hyper-graph ReINN for more than 0 iterations has no effect on the expressiveness.
Finally, we study the learning capabilities of ReINNs. We prove, under certain realistic assumptions, is possible to train ReINN on a finite set of graphs, and it will generalize arbitrarily large graphs. This is an outcome due to the weight-sharing nature of ReINNs. Next, we proved a finer-grained cample-complxxtty bound for ReINNs. This result theoretically suggests that using max aggregation function is provably better than sum aggregation function when realizing first-order logic formula.
We hope our work can serve specific problem, what arity do you need? What depth do you need? What aggregation function should you use? Will my model have structural generalization (i.e., larger graphs)? Our theoretical
foundation for designing relational neural networks: to solve

---

Under review as a conference paper at ICLR 2022
results on learning further supported by experiments, for empirical demonstration of the theorems and for exploring the tightness of the sample-come complexxty bounds and effectiveness of different aggregation functions. Specifically, we show that ReINNs with sufficient expressiveness power can be trained using gradient descent to realize the desired function. Meanwhile, when the training data distribution is uniformly distributed, ReINNs do demonstrate strong generalization larger graphs than those seen during training. Finally, we also empirically show the generalization of ReINNs with different aggregation functions.
GRAPH REASONING AND RELATIONAL. NEURAL NETWORKS
In this section, we define very general class of relational networks and show that can represent several important classes of relational neural networks, including graph neural networks, neural logic machines, and transformers.
2.1 GRAPH REASONING PROBLEM
A graph reasoning problem is prediction task on a hypergraph G. It can predict discrete or real-valued property of the whole graph, of individual nodes, or tuples of nodes.
Much of the work graph-structured edges, but many important problems are best modeled using hypergruphs, in which a hyperedge can connect multiple nodes. A further generalization is to labeled hypergraphs, in which each hyperedge can have one of a discrete set of labels. We will make use of a still more general structure, in which hyperedges can have real and/or vector-valued labels.
models has focused cases with only binary
A hypergraph representation G a tuple (V, X), where V is a set of entities (nodes), and X is set of hypergraph representation functions. Specifically, X {Xu, X2, .X,). where X, : (V), U2.... ) + a function mapping every tuple of j nodes to a value. We call j the arity of the hyperedge and l is the max arity of input hyperedges. The range S can be any set of discrete labels that describes relation rype, or a scalar number (e.g., the length of an edge), or a vector. In general, we will use the arity representation function (0) + to represent any global properties of the graph as a whole.
graph reasoning function f is a mapping from hypergraph representation G XV, to another hyperedge representation function Y on V. There are several important types:
graph classification function: computes global label, Y = (Yo): Yo(0) + S' = [0,11 1} for the whole graph.
graph regression function: computes global real output, Y = (Yo}. where Yo + R. node classfficttonnregrresionn function: computes Y {Yi}, where Y1 (v()) + {0, 1} a binary
label for each individual node.
edge classification function: extends previous prediction notions to higher-arity hyperedges.
For example, asking whether a graph fully connected is graph classification problem; computing its diameter is graph regression problem; finding the set of disconnected subgraphs of size l is k-ary hyperedge classification problem.
Example (undirected graph connectivity). The input is G = (V, where X = (Xo, X1, X2). in which X₂ is mapping from each pair of nodes v1, 122 E V to {0. 1}. indicating whether (11, u2) are connected. The input is an undirected graph; thus, X2(11, (2) that Xo and X, are constant functions and not used for describing the undirected graph. The output is Y = (Yo). where Y0(0) + {0, }} is a binary classification label. The desired label is 1 when the graph is connected, and otherwise.
X22(2, v1) for every U1, U2. Note
2.2 RELATIONAL NEURAL NETWORKS
We now introduce introduce generalized relational neural networks (ReINNs), a general framework that unifies set of important relational neural network models that can be trained to solve graph reasoning problems. In particular, we will describe relational neural networks following the notation and computation neural logic machines (NLMs; Dong et al., 2019). We choose NLM as a base model because it naturally generalizes to hyperedges with arities greater than 2. As we will see later, other relational neural networks such as graph neural networks (GNNs; Scarselli et al., 2008) and transformers ( (Vaswani et al., 2017) are equivalent to NLMs and each other in terms of expressiveness. Showing this equivalence allows us to focus the rest of the paper on analyzing a single model type, with the understanding that the conclusions generalize broader class of relational neural networks.
2

---

Under review as a conference paper at ICLR 2022
RRL40
Ti---1
Expand
RRLy
B
RRLo.
D
Ti-1
Permute
NN,
Tu
2
Reduce
RRLpa
D3
Nonlineurity
(a) The overall computation graph of ReINN. (b) The computation graph of single ReINN block. Figure I: The overall architecture of our generalized relational neural network (ReINNs). It follows the computation graph of NLM (Dong et al., 2019) and can be applied to hypergraphs.
A ReINN is multi-layer neural network that operates on hypergraph representations, in which the hypergraph representation functions are represented as tensors. The input a hypergraph representation XV.. There are then several computational layers, each of which produces hypergraph representation with nodes V and a new set of representation functions. Specifically, a B-ary ReINN produces hypergraph representation functions with arities from 0 up to maximum hyperedge arity of B. We let Tig denote the tensor representation for the output at layer i and arity Each entry in the tensor is mapping from set of node indices (#1, 02, 12)) vector in latent space RW, Thus, Ti, a tensor of j ++ dimensions, with the first dimensions corresponding to j-tuple of nodes, and the last feature dimension. For convenience, we write ho. for the input hypergraph representation and h. for the output of the ReINN.
Fig. Ia shows the overall architecture of ReINNs. It has D x B computation blocks, namely relational reasoming layers (RRLs). Each block RRL, illustrated in Fig. 1b, takes the output from neighboring arities in the previous layer, 1, Ti-1 and T111--1, and produces Ti.. Below we show the computation of each primitive operation in an RRL.
The expand operation takes tensor 1,51- (arity j 1) and produces a new tensor T of arity The reduce operation takes tensor T:11++1 (arity j 1) and produces new tensor T.R. 1-1,1+1 of arity j + 1. Mathematically,
T. 1--1--1(01 12 my} T1-15-1(U1- 02 ... u--1]:
T. [0), 02
Uy] = Agg (Ti-1.+11 [Vi, 02,"" ... Ui "y+1]
Here, Agg is called the aggregation function of a ReINN. For example, a sum aggregation function takes the summation along the dimension + 1 of the tensor, and max aggregation function takes the max along that dimension.
The concat (concatenate) operation + is applied at the "vector representation" dimension. The permule operation generates new tensor of the same arity, but fuses the representations of hyperedges that share the same set of entities but in different order, such as (2)) and m1). Mathematically, for tensor X of arity j. Y permute(X) then
Y|U1, ... my] Concat {X(vo, "ozs'" ,o,1]. 1] oES; where a E Sy iterates over all permuations of [1, 2, j}. NN, is a multi-layer perceptron (MLP) applied to each entry in the tensor produced after permutation, with nonlinearity (c.g.. ReLU).
It is important to note that we intentionally name the MLPs NN, instead of NN In generalized rela- tional neural networks, for given arity j. all MLPs across all layers are shared. is straightforward to see that this "weight-shared" model can realize a "non- weight- shaghd- ReINN that uses different weights for MLPs at different layers when the number layers a constant. With a sufficiently large length of the representation vector, we can simulate the computation of applying different transformations by constructing block matrix weights. (A more formal proof is in Appendix B. The advantage of this weight sharing is that the network can be easily extended to a "recurrent" model. For example, we can apply the ReINN for a number of layers that is a function of n, where n is the the number of nodes in the input graph. Thus, will use the term layers and iterations interchangeably.
Handling high-arity features and using deeper models usually increase the computational cost. In appendix B.6, we show that the time and space complexity of ReINN [D, B) is O(Dnn)..
Exanple (GNN). The graph neural network (GNN) of Scarselli et al. (2008) can be described as a specific type of ReINN. First, GNNs work graphs with maximum arity 2. In single iteration in
3

---

Under review as a conference paper at ICLR 2022
B 4
4-Clique Detection ReINN(O(1), 41
4-Clique Count ReINNIO(1), 41
Triangle Detection REI)
All-Pair Distance ReINN[O((ogn)) 3]"
Bipartiteness ReINN[O n). 31"
B = 3
All-Pair Connectivity ReINN[O n..
All-Pair Connectivity-k ReINN[O(log 3]"
3 3-Link Detection ReINN[O(1), 2]
S-T Distance ReINN]O(n). 2]
4- Link Detection ReINN[O(1), 2]
Max Degree ReINN[O(1),2)
B 2
S-T Connectivity ReINN]O(n).
Max Flow ReINN[O( 2]"
S-T Connectivity-k ReINN[O(E),
FOC₂ Realization ReINN[: 2] (Barceló et al., 2020)
B = 1 Node Color Majority: ReINN[O(L). 1J
Count Red Nodes: ReINN[O IJ
Classification Tasks
Regression Tasks
Table 1:
The minimum depth and arity of ReINNs for solving graph classification and regression tasks. The symbol indicates that these are conjectured lower bounds.
GNN, we use two message-passingg subroutines: (edge update) the representation associated with each edge is updated by representations of its both ends, and (node update): the representation of each node is updated by all edge presentations connected to it. This message passing scheme can easily fit in the ReINN: edge update can be realized by the expand and permute operations, while node update can be realized by the reduce operation.
In general, hypergraph GNNs (Morris al., 2019) are also equivalent to ReINNs. Specifically, GNN applied to B-ary hyperedges is equivalent to an NLM applied to B + 1-ary hyperedges. We provide proof details in Appendix B.2.
There are other approaches of realizing GNN on hypergraphs such as hypergraph convolution(Feng al., 2019; Yadati et al., 2019; Bai al., 2021), attention(Ding al., 2020) and message pass- ing(Huang & Yang, 2021). These approaches can be viewed as instances of ReINNs, but are less expressive than ReINNs with equal max arity. We provide proof details in Appendix B.3.
Example (Transformer). The key difference between Transformers (Vaswani et al., 2017) and GNNs is the "self-attention" opeartion, which can be viewed as a special aggregation function. In self-attention, each "sender" computes the key and value, and each "receiver" computes the query. Xu et al. (2019) proved such aggregation can be simulated with sum aggregation function.
We will use calligraphic letters M2, to name ReINNs. Because even when hyperparameters such as the maximum arity and the number of iterations are fixed, a ReINN is still a model family M: the weights for MLPs will be trained on some data. Furthermore, each model M e M is ReINN with a specific set of MLP weights.
EXPRESSIVENESS OF RELATIONAL NEURAL NETWORKS
ReINN is characterized by hyperparameters D (depth), and B maximum arity. In this section, we will focus on /) and B, quantifying how they affect the expressiveness of model; i.e., the set of graph reasoning functions a model family can realize. The W parameter affects the precise details of what functions can be realized, as does regular neural network, but does not affect the structural constraints that are our focus in this paper. When considering D, we will focus on the distinction between any constant depth vs. adaptive depth, in which D depends on the number n of nodes in the input graph. We will use the notation ReINN[D, B] to represent a ReINN family with depth D and max arity B. A summary some concrete results in table and discussed detail Appendix A.
Many frameworks for characterizing the expressiveness of neural networks make distinction between models that have the capacity to use unbounded precision intermediate representations. In all results state below, we will indicate whether they apply to the fixed or unbounded precision case.
Definition 3.1 (Expressiveness). We say a model family Mj is at least expressive as M2, written as Mi M2, if for all M2 M2, there exists M1 M1 such that M1 can realize My. A model family M, is more expressive than M2, written as Mn > M2, if Mi > M2 and 3M, e M,, VM2 E M2, M2 can not realize Mi.
4

---

Under review as a conference paper at ICLR 2022
3.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, the higher the maximum arity, the more expressive the relational neural network is. A majority of the results in this section are based on the Weisfeiler-Leman graph isomophism test (WL-test) (Leman & Weisfeiler, 1968; Xu et al., 2019).
Theorem 3.1 (Arity Hierarchy). For any maximum arity B, there exists a depth D such that: VD 2 D Re B + 1] is more expressive than ReINNID, BJ. This theorem applies to both fixed shed-precision and unbounded ppreciiiiiidriionnnonoo networks.
sketch: Our proof slightly extends the proof of Morris et al. (2019). First, the set of graphs distinguishable by ReINN( D. B] is bounded by graphs distinguishable by D-round order- WL. test. If models in ReINNDD, B] cannot generate different outputs for two distinct hypergraphs G1 and G2, but there exists M Re B + 1] that can generate different outputs for G1 and Gg. then we can construct graph classification function f that ReINN[D, B + 1] can realize but ReINN[D, B] cannot. The full proof is described in Appendix B.4.
It is also important to quantify the minimum arity for realizing certain graph reasoning functions.
Theorem 3.2 (FOL realization bounds). Let FOCg denote a fragment of first order logic with at most B variables, extended with counting quantifiers of the form 32m Φ, which state that there are least n nodes satisfying formula & (Cai et al., 1992).
(Upper Bound) Any function f in FOC can be realized by ReINN[D, B] for some D. (Lower Bound) There exists function f FOCB such that for all D, f cannot be realized by ReINN[D,BB - 1].
Proof: The upper bound part of the claim has been proved by Barceló et al. (2020) 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 Cai et al. (1992), in which they show that FOC equivalent non-isomorphic graphs. Given that ReINN[D, B - 1] is equivalent to the (B 2) 2)-dimensional WL test of graph isomorphism, there must be an FOLg formula that distinguishes two non-isomorphic graphs that D, B 1] cannot. Hence, FOL. cannot be realized by ReINN[- B 1].
(B 1)-dimensional WL test in distinguishing
3.2 DEPTH HIERARCHY
We now study the dependence of the expressiveness of ReINNs on depth D.
ReINNs are generally defined to have a fixed depth, but allowing them to have depth that is dependent on the number of nodes n = [V] in the graph can substantially increase their expressive power. In the following, we define a depth hierarchy by analogy to the time hierarchy in computational complexity theory (Hartmanis & Stearns, 1965), and we extend our notation to let ReINN(O(((m)) B) denote the class of adaptive-depth ReINNs in which the growth-rate of depth D is bounded by ((f()).
Conjecture 3.3 (Depth hierarchy). For any maximum arity B, for any two functions f and g, if g(n) = off (m) log n). that is, grows logarithmically more quickly than g. then fixed-precision (f)) B] more expressive than fixed- exed-precision ReINN[O(g(n)).. B).
There is a closely related result for the congested clique model in distributed computing, where Korhonen & Suomela (2018) proved that CLIQUE(g(n)) & CLIQUE([(x)) if g(n) = (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 exee-iicoision ReINN allows only a constant number of bits. The reason why the result on congested clique can not be applied to fixed-precision ReINNs is that congested clique assumes unbounded precision representation for each individual node.
However, Conjecture 3.3 is not true for ReINNs with unbounded precision, because there is an upper bound depth B-1) for a model's expressiveness power. That is, an unbounded-precision ReINN can not achieve stronger expressiveness by increasing its depth beyond O(n
Theorem 3.4 (Upper depth bound for unbounded -precisioon ReINN). For any maximum arity B, (n B-11, B] > (e)),(O(((m),, B] for any function f()...
Proof sketch. Theorem 3.4 can be proved by combining the fact that the B-dimensional WL test is equivalent to differentiating graphs using FOC,+1 (Cai et al., 1992), and the O(n () upper bound on the computation depth for B-dimensional WL-test (Kiefer & Schweitzer, 2016). This upper
5

---

Under review as a conference paper at ICLR 2022
bound indicates that (n²)) depth is sufficient for B-dimensional WL-test to reach its maximum discriminative power, and thus any two graphs distinguishable by the WL-test can be distinguished by some FOL#+1 formula with quantifier depth O(n (n The full proof is described in Appendix B.5.
is important to point out that, to realize a specific graph reasoning function, ReINNs with different maximum arity B may require different depth D. Fürer (2001) provides general construction for problems that higher-dimensional ReINNs can solve in asymptotically smaller depth than lower- dimensional ReINNs. In the following we give a concrete example for computing S-T Connectivity-k; which asks whether there is path of from nodes S and T in a graph, with length < k.
Theorem 3.5 (S-T Connectivity-k with Different Max Arity). For any function f()), if f(k) = o(k), Re 2] cannot realize S-T Connectivity-k: That is, S-T Connectivity-k requires depth least (kk) for relational neural network with an maximum arity of B 2. However, S-T Connectivity-k can be realized by ReINN[O k), 3].
Proof sketch. For any integer k, we can construct graph with two chains of length k, so that if we mark two of the four ends as S or T, any ReINNIK - 1, 2] cannot tell whether S and T are on the same chain. The full proof is described in Appendix A.7.
There are many important graph reasoning tasks that do not have known depth lower bounds, including all- all-pair connectivity and shortest distance (Karchmer & Wigderson, 1990; Pai & Pemmaraju, 2019).
4 LEARNING AND GENERALIZATION IN RELATIONAL NEURAL NETWORKS
Given our understanding of what functions can be realized by relational neural networks, we move on to the problems of learning them: Can effectively learn relational neural network to solve desired task given sufficient number of input-output examples? What is the sample complexity? How do they generalize? These questions are very difficult to address in full for ReINNs, but there still some interesting things to be said. In this section we state and prove two theorems that illuminate their learning and generalization properties.
In a some fixed size can ensure that the trained neural network will generalize all graphs larger than those appearing in the training set. In an unbounded precision setting, we can show that, if we use gradient descent to train models that use certain aggregation functions from randomly sampled data, then with a number of training examples that scales with log(N), the learned ReINN will generalize to all hypergraphs of size smaller than N.
setting, we can show that applying enumerative training with examples up to
anbounded--recciioon
4.1 GENERALIZATION OF FIXED- PRECISION RELATIONAL NEURAL NETWORKS
Machine learning studies of generalization focus on cases where input and output space are fixed- dimensional, and on how well the learned hypothesis can predict outputs for inputs that were not observed in the training set. Although learning specific graph reasoning functions in ReINNs are susceptible to this same type of analysis, we focus on an important type of generalization ability that not present in the classical models: the ability to train on example graphs with up to N nodes, and then generalize to make correct predictions on graphs with larger numbers of nodes.
critical determinant of the generalization ability for ReINNs is the aggregation function they use. Specifically, Xu et al. (2019) have shown that using sum as the aggregation function provides maxi- mum expressiveness for graph neural networks. However, sum aggregation cannot be implemented in fixed- sxed-precision models with arbitrary number of nodes, because the graph size increases, the range of the sum aggregation also increases.
aggregation function). An aggregation function is fixed precision 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.
Definition 4.1
Two useful fixed- exed-precision aggregation functions are max, which computes the dimension-wise mean, which approximates the dimension-
maximum over the set of input values, and wise mean to fixed decimal place.
Definition 4.2 (Fixed-precision ReINN), A ReINN is fixed precision its aggregation function is fixed precision and all of the component MLPs, NN,, j. are also fixed precision, in the same sense as for aggregation functions above. This guarantees that the cardinality of the range of the hypergraph representation functions cannot grow with the number of nodes in the hypergraph.

---

Under review as a conference paper at ICLR 2022
In order to focus on structural generalization in this section, consider enumerative training paradigm. When the input hypergraph representation domain S is a finite set, we can enumerate the set GgN of all possible input hypergraph representations of size bounded by N. We first enumerate all graph sizes n I 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 GCN, 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- in machine learning. In the simplest binary graph classification case, enumerative training allows us to identify the optimal model in the hypothesis space. In practice, this can be upproximated well when the input domain S is small and the input data distribution is approximately uniformly distributed. The enumerative learning setting studied by the language identification in the limit community (Gold, 1967), 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.
training mechanisms
Theorem 4.1 Frixed-precision generalization under complete presentation). For any hypergraph reasoning function f. if it can be realized by a iixe-prrcision relational neural network model M, then there exists an integer N, such that if we train the model with complete presentation all input hypergraph representations with size smaller than N, GEN, then for all M E M,
Σ MMM(G) * (()
VG 9 M(G) S(G).
GE9
That is, as long as M fits all training examples, it will generalize to all possible hypergraphs in 9oo-
Proof. The key observation is that for any fixed vector representation length W, there are only finite number of distinctive models in a fixed-precision ReINN family, independent of the graph size n. Let Wi be the number of bits in each intermediate representation of exxedppreisiio ReINN. There are at most (2W, different mappings from inputs to outputs. Hence, if N sufficiently large to enumerate all input hypergraphs,
always identify the correct model in the hypothesis space.
In future, we hope to extend this result to encompass sampling-base based rather than enumerative training. In addition, models approximating the finite muiie-precision assumption with sigmoid activation and max aggregation have empirically demonstrated the strong generalization properties this theorem predicts.
4.2 GENERALIZATION OF UNBOUNDED-PRECISSON RELATIONAL NEURAL NETWORKS
Intuitively, relational neural networks with unbounded precision may not generalize to larger graphs because an aggregation function such as sum may accumulate through the layers. However, interest- ingly, this еитог can remain reasonably well-bounded for max mean aggregation function. In this section, we will derive a bound for sample complexity in a more standard PAC-learning setting, in which there are no precision bounds the inputs and computation of the model. It is difficult to characterize the VC dimension of an entire ReINN, but following Xu et al. (2021), we characterize the properties of a sequential training paradigm that considers the components independently.
Theorem 4.2 (PAC sample complexity of unbounded- sebbundee-pprccision ReINNs). Let M be family of unbounded-precissin relational neural networks with hidden dimension W, depth D, and maximum arity B. Let f be a graph function that can be realized by M, and M M be a sequentially- trained model. If the following two conditions are true:
(a) There exists an instance M' E .M such that M' realizes f and MI.Ps in M are (c, 0)-
approximations of those in M' " and
& A||T1 x2ll (b) The MLPs NN, in M are Lipschite-cominnouss i.c. (I,N - NN₃
for some constant and for all j.
Then on graphs of size n, M is a (O (eXP ((6Dn)))) approximation of f if M uses max aggregation, and (O (<XP). O(DDn ( of f M uses mean aggregation.
Theorem 4.2 indicates that when using max or mean aggregation, the generalization error does not scale with the graph size n (which is the case for sum). while the failure probability 8 scales with B) In the PAC-learning framework, the sample complexity for achieving error e with failure probability 8 is bounded by O (1 (log (VC(H)) + log (f))), where VC(H) the VC-dimension
"That is, Pra*x(]| M((=)] s e) 2 (1 8), where X' is the data distribution
7

---

Under review as a conference paper at ICLR 2022
3-link
4-link
triangle
4-clique
Model
Agg.
71 = 10
n = 30
n = 10
n = 30
n = 10
n = 30
n n= 10
n = 30
Max 70.0=a.v
82.7
92.0+a.o
91.7=t.0
73.7+a.2
50.2+1.8
55.3+4.0
46.2+113
1-ary GNN
Sum
100.0
89.4
100.0
86.1
+7.7
48. 48.641.6
53.7
55.2+0.8
Max
65.3
54.0+0.6
93.0+0.0
95.7+0.0
51.0+1.7
49.2+0.4
55,0+0.0
45.7+a.0
2-ary NLM
Sum
100.0go.0
88.3
100.01:.0
67.4216.4
82.0+2.6
48.3
53.040.0
54.411.5
Max 78.7=0.6
76.0+17.3
97.7
98.6
100.0
100.0+0.0
55,040.0
45.7+0.0
2-ary GNN
Sum 100.0.o.0
51.247.9
100.0
45.7
100.0
49.2+1.0
61.0+6.8
54.34a.0
Max
100.0.0.0
100.0
100.010.0
100.0.0.0
100.0
100.010.0
59.0
45.910.4
3-ary NLM
Sum
100.0
87.6111.0
100.01...
65.4
100.0
80.618.8
73.7
53.318.8
Max 79.0=a.0
86.0so.o
100.0
100.0
100.0
100.04..0
84.0
93.340.0
3-ary GNN
Sum
100.0
14.1
100.0
61.1
100.0
95.1
80.5
66.2
Max 100.0
100.0
100.04e.o
100.0
100.0
100.04a.0
82,0+1.7
93.1
4-ary NLM
Sum 100.0zo.0 59.1
100.040.0
67.7
100.0.0.0
82.1
84.0+0.0
67.0=16.9
Table 2: Overall accuracy on relational reasoning problems. All models are trained on n = 10, and tested on = 30. The standard error of all values are computed based on three random seeds.
of the hypothesis space. Hence, scaling to graphs with size requires additional O log n) samples when considering W. D, À as constants. The proof of Theorem 4.2 can be found in Appendix B.7.
The sample complexity does not depend on the graph size, because under the sequential learning setting the MLPs are trained with direct supervision. Though this setting can not be implemented in practice, in our experiments we observe good generalization of models trained end-to-end.
Theorem 4.2 is interesting because it shows that using max or mean aggregation has provably better sample complexity than using sum aggregation. Combined with the fact that using max aggregation, ReINNI B] can realize FOCg with only 3 and V quantifiers (Dong et al., 2019), RelNN with max aggregation a strong model class.
EXPERIMENTS
We now study how our theoretical results on model expressiveness and learning apply to relational neural networks trained with gradient descent on practically meaningful problems. We begin by describing two synthetic benchmarks: graph substructure detection and relational reasoning.
In the graph substructure detection dataset, there are several tasks of predicting whether there input graph containd a sub-graph with specific structure. The tasks are: 3-link (length-3 path), 4-link, triangle, and 4-clique. These are important graph properties with many potential applications.
The relational reasoning dataset is composed of two ramily-relationship prediction tasks and two connectivity prediiciio tasks. They are all binary edge classification tasks. In the family-relationshi prediction task, the input contains the mother and father relationships, and the task is to predict the grandparent and uncle relationships between all pairs of entities. In the connectivity-predicii the input is the edges in an undirected graph and the task is to predict, for all pairs of nodes, whether they are connected with a path of length I 4 (connectivity-4) and whether they are connected with a path of arbitrary length (connectivity). The data generation for all datasets is included in Appendix C.
tasks,
5.1 RESULTS
Our main results on all datasets are shown in Table and Table We empirically compare relational neural networks with different maximum arity B, different model architecture (GNN and NLM), and different aggregation functions (max and sum). All models use sigmoidal activation for all MLPs. For each task on both datasets we train on a set of small graphs (n = 10) and test the trained model on both small graphs and large graphs (n = 10 and n = 30). We summarize the findings below.
Expressiveness. We have seen thcoretical equal expressiveness between GNNs and NLMs applied to hypergraphs. That is, a GNN applied to B-ary hyperedges is equivalent to (B + 1)-ary NLM. Table 2 and 3 further suggest their similar performance tasks when trained with gradient descent.
Formally, triangle detection requires ReINNs with at least B = to solve. Thus, we see that all ReINNs with arity B fail on this task, but models with B = perform well. Formally, 4-clique is realizable by ReINNs with maximum arity B = 4, but we failed to reliably train models to reach perfect accuracy on this problem. It is not yet clear what the cause of this behavior is.
8

---

Under review as a conference paper at ICLR 2022
grand parent
uncle
connectivity-44 -4'
connectivity
Model
Agg.
n = 20
n = 80
20
80
= 10
71 = 80
7 10
n = 80
Max
84.0zo.s
64.8
93.610.3
=6.1=0.0
72.6+3.6
75. 85.620.3 67.5
1-ary GNN
Sum
84.7=0.1
64.4
94.340.2
66.2-u.b
79.6+0.1
68.3
75.0+u.2 87. 40.3
Max
82.3
65.6
+3.1
66.6
91.2+00.2
51.0+0.6
67.1
2-ary NLM
Sum
82.9
64.6
93.44a.0
66.7-u.2
96.0+o.4
68.3
84.0=u.v
71.9
Max 100.0.o.0
100.0
100.0
100.0
100.0
100.0.0.0
84.0
71.9
2-ary GNN
Sum 100.0=o.v
35.7
100.0ga.o
33.9_u.D
100.0
51.3+t..
84.0=a.o
71.9
Max 100.0.o.b
100.0
100.0ga.o
100.0go.0
100.0
100.0
100.0+0.0
100.0
3-ary NLM
Sum 100.0=0.0
35.7.0.0
100.010.0
50.8
100.010.0
77.8=11.8
100.0
88.218.0
Max 100.0
100.010.0
100.0.0.0
100.0.0.0
N/A
N/A
N/A
N/A
3-ary NLMRE
Sum 100.0 35.7
100.0.0.0 33.8
N/A
N/A
N/A
N/A
Table 3: Overall accuracy on relational reasoning problems. Models for family relationshp prediction are trained on n = 20, while models for connectivity problems are trained on n = 10. All model are tested n 80. The standard error of all values are computed based on three random seeds. The 3-ary NLMs marked with "HE" have hyperedges in inputs, where each family is represented by a 3-ary hyperedge instead of two parent-child edges, and the results are similar to binary edges.
Structural generalization. We discussed the structural generalization properties of ReINNs in networks and enumerative training. This setting can be approximated by training ReINNs with max aggregation and sigmoidal activation on sufficient data. In both Table and Table 3 we see that, when models can realize the desired function and are trained to 100% accuracy on the training split, they also generalize well to larger graphs. In appendix C, we provide a more detailed study on the generalization performance.
Section 4.1, in learning setting based on
Sample complexity (case study). In Section 4.2, we discussed the sampling complexity differences induced by different aggregation functions in the sequential learning setting. The primary conclusion is that models with max aggregation are expected to have better sample complexity than models with sum aggregation. We test this hypothesis in the end-to-end learning setting. For the triangle detection problem, we train 3D-NLM with sum and max aggregation with fewer training samples. We observe that sum aggregation requires about 300 training samples to reach nearly perfect accuracy, while max aggregation requires only 30 training samples. More details are included in appendix C.
6 RELATED WORK
Solving problems on graphs of arbitrary size is studied in many fields. ReINNs can be viewed as circuit families with constrained architecture. In distributed computation, the congested clique model can be viewed as 2-arity ReINNs, where nodes have identities as extra information. Common graph problems including sub-structure detection(Li et al., 2017; Rossman, 2010) and connectivity(Karchn) & Wigderson, 1990) are studied for lower bounds in terms of depth, width and communication, This has been connected GNNs for deriving expressiveness bounds (Loukas, 2020).
Studies have been conducted on the expressiveness of GNNs and their variants. Xu et al. (2019) pro- vide an illuminating characterization of GNN expressiveness in terms of the WL. graph isomorphism test. Barceló et al. (2020) reviewed GNNs from the logical perspective and rigorously refined their logical expressiveness with respect to fragments of first-order logic. Dong et al. (2019) 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. (2019) dynamic halting in transformers.
interesting that GNNs may generalize to larger graphs. Xu et al. (2020; 2021) have studied the notion of algorithmic alignment to quantify such structural generalization. Dong et al. (2019) provided empirical results showing that NI.Ms generalize to much larger graphs on certain tasks.
7 CONCLUSION
We have provided framework for unifying several powerful classes of relational neural networks and characterized aspects of their representational and generalization power, both theoretically and empirically. In particular, 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. 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 variety of problems.
9

---

Under review as a conference paper at ICLR 2022
Reproducibility statement.
The proof details for theorems in this paper have been included in the
appendix.
REFERENCES
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. International Conference on Machine Learning, 2019. 19
Song Bai, Feihu Zhang, and Philip HS Torr. Hypergraph convolution and hypergraph attention.
Pattern Recognition, 110: 107637,, 2021. 4, 17
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In ICLR, 2020. 1, 5,
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Lanchez-Gonzabee Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.00 1806,01261, 2018.
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. 5, 18
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal
transformers. In ICLR, 2019. 9
Kaize Ding, Jianling Wang, Jundong Li, Dingcheng Li, and Huan Liu. Be more with less: Hypergraph attention networks for inductive text classification. In EMNLP, 2020. 4, 17
Efim A Dinic. Algorithm for solution of problem of maximum flow in networks with power estimation. In Soviet Math. Doklady, volume 11, pp. 1277-1280, 1970. 14
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In ICLR, 2019. 1, 2, 3, 8, 9, 20
Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In AAAI, 2019, 4, 17
Martin Fürer. Weisfeiler-lhhman refinement requires at least linear number of iterations. In ICALP,
2001. 6
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, 2017. 1
E Mark Gold. Language identification in the limit. Inf. Control., 10(5):447-474 1967. 7
Juris Hartmanis and Richard E Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285-306, 1965.
Jing Huang and Jie Yang. Unignn: a unified framework for graph and hypergraph neural networks. In IJCAI, 2021. 4, 17
Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math., 3(2):255-265, 1990. 6, 9
Sandra Kiefer and Pascal Schweitzer. Upper bounds the quantifier depth for graph differentiation in first order logic. In LICS, 2016. 5, 18
Janne H Korhonen and Jukka Suomela. Towards a complexity theory for the congested clique. In SPAA, 2018.
AA Leman and B Weisfeiler. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-TTechniceese Informatsiya, 129)1 1968. 5
10

---

Under review as a conference paper at ICLR 2022
Yuan Li, Alexander Razborov, and Benjamin Rossman. On the ac"O complexity of subgraph isomorphism. SIAM J. Comput., 46(3))933-99))) 9711, 2017. 9
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2017.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. International
Conference on Learning Representations, 2020. 9
Christian Merkwirth and Thomas Lengauer. Automatic generation of complementary descriptors with molecular graph networks. Journal of chemical information and modeling, 45(5):1159-1168, 2005.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019, 4, 15, 17
Shreyas Pai and Sriram V Pemmaraju. Connectivity lower bounds in broadcast congested clique. In PODC, 2019. 6
Benjamin Rossman. Average-case complexity of detecting cliques. PhD thesis, Massachusetts Institute of Technology, 2010. 9
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008. 1, 15
Michael Schlichtkrull, Thomas Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In ESWC, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NeurlPS, 2017. 2,
Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In ICLR, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019. 1, 4, 5, 6,
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? ICLR, 2020. 1, 9, 19
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward graph neural networks. In ICLR, 2021.
Naganand Yadati, Madhav Nimishakavi, Prateck Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar, Hypergen: new method of training graph convolutional networks on hypergraphs. In NeurlPS, 2019. 4, 17

---

Under review as a conference paper at ICLR 2022
A GRAPH PROBLEMS
We listed a number of examples for graph classification and regression tasks, and we provide the definitions and the current best known ReINNs for learning these tasks from data. For some of the problems, we will also show why they can not be solved by simpler problems, or indicate them as open problems.
A.1 NODE COLOR MAJORITY
Each node is assigned color E C where C' is finite set of all colors. The model needs to predict which color the most nodes have.
Using a single layer with sum aggregation, the model can count the number of nodes of color e for each c on its global representation.
A.2 COUNT RED NODES
Each node is assigned color of red or blue. The model needs to count the number of red nodes.
Similarly, using a single layer with sum aggregation, the model can count the number of red nodes on its global representation.
A.3 3-LINK DETECTION
Given unweighted, undirected graph, the model needs detect whether there triple of nodes (a, b, c) such that a o and (a, b) and (b, c) are edges.
This is equivalent check whether there exists node with degree least 2. We can use a Reduction operation with sum aggregation to compute the degree for each node, and then use a Reduction operation with max aggregation to check whether the maximum degree of nodes greater than or equal to 2.
Note that this can not done with layer, because the edge information necessary for the problem, and they require at least 2 layers to be passed to the global representation.
A.4
4- LINI DETECTION
Given an unweighted undirected graph, the model needs to detect whether there a 4-tuple of nodes (a, b, e, d) such that a + c. b * d and (a, b). (b, c), (c, d) are edges (note that triangle is also 4-link).
This problem is equivalent to check whether there is an edge between two nodes with degrees 2 2. We can first reduce the edge information to compute the degree for each node, and then expand back to 2-dimensional representations, so we can check for each edge if the degrees of its ends are 2 2. Then the results are reduced to the global representation with existential quantifier (realized by max aggregation) in 2 layers.
A.S TRIANGLE DETECTION
Given a unweighted undirected graph, the model is asked to determine whether there is a triangle in the graph i.e. a tuple (a, b, c) so that (a, b), (b, c), (c, a) are all edges.
This problem can be solved by ReINN [4.3]: we first expand the edge to 3-dimensional representations, and determine for each 3-tuple if they form triangle. The results of 3-tuples require 3 layers to be passed to the global representation.
We can prove that Triangle Detection indeed requires breadth at least Let k-regular graphs be graphs where each node has degree k. Consider two k-regular graphs both with n nodes, so that exactly one of them contains triangle*. However, ReINNs of breadth 2 has been proven not to be stronger than WL test on distinguish graphs, and thus can not distinguish these two graphs (WL test can not distinguish any two k-regular graphs with equal size).
A.6 4 4-CLIQUE DETECTION AND COUNTING
Given an undirected graph, check existence of, or count the number of tuples (a, b, d) so that there are edges between every pair of nodes in the tuple.
SScc construction is common. One example is l 2, n 6, and the graph may consist of two separated triangles hexagon
12

---

Under review as a conference paper at ICLR 2022
This problem be easily solved by ReINN with breadth 4 that first expand the edge information to the 4-dimensional representations, and for each tuple determine whether its is a 4-clique. Then the information of all 4-tuples are reduced 4 times to the global representation (sum aggregation can be used for counting those).
Though we did not find explicit counter-example construction detecting 4-cliques with ReINNNs of breadth 3, we suggest that this problem can not be solved with ReINNs with 3 or lower breadth.
A.7 CONNECTIVITY
The connectivity problems are defined on unweighted undirected graphs. S-T connectivity problems provides two nodes S and T (labeled with specific colors), and the model needs to predict they are connected by some edges. All pair connectivity problem require the model to answer for every pair of nodes. Connectivity-E problems have an additional requirement that the distance between the pair of nodes can not exceed k.
S-T connectivity-k -k can be solved by ReINN of breadth 2 with iterations. Assume S is colored with color at every iteration, every node with color will spread the color to its neighbors. Then, after I iterations, is sufficient to check whether has the color c.
With ReINNs of breadth 3, we can use Ollog k) matrix multiplications to solve connectivity-k between every pair of nodes. Since the matrix multiplication can naturally be realized by ReINNs of breadth 3 with two layers. All-pair connectivity problems can all be solved with Ollog k) layers.
Theorem A.1 (S-T connectivity-k with ReINN[o(k),, 2). S-T connectivity-k can not be solved by ReINN of maximum arity within o(k) iterations.
Proof. We construct two graphs each has 2k nodes u1 u.. uks 1.. edges (u,, 14+1) and (ui: Ui+11 ) for 1 < i < k i.e. there are two links of length k. We then set u1 = Un and 5 = u1, T U, the the two graphs.
... Uk- In both graph, there are
We will analysis GNNs ReINNs proved be equivalent them by scaling the depth by constant factor. Now consider the node refinement process where each node x is refined by the multiset of labels of æ's neighbots and the multiiset of labels of x's non-neighbors.
Let c/ (x) be the label of x in graph j after i iterations, at the beginning, WLOG, we have
(un) = 1, c (u,,) (u,, = 20( (uz) = 1, c, 2
and all other nodes are labeled as O.
Then we can prove by induction: after i < t iterations, for St i we have
c(ur) = c₂ (wx) (f.) = (1))
c(ux-e+1) = c (0)) (vx G (v+-e+1)
= ((i) (ux-241)
and i we have
= (f)) -ch00 (v.)
( (vx)
This is true because before iterations are run, the multiset of all node labels are identical for the two graphs (say (())). Hence each node is actually refined by its neighbors and s(i) where S(i) & the same for all nodes. Hence, before running 2 iterations when the message between and T finally meets in the first graph, GNN can not distinguish the two graphs, and thus can not solve the connectivity with distance k
A.8
MAX DEGREE
The max degree problem gives graph and ask the model output the maximum degree of its nodes.
Like we mentioned in 3-link detection, one layer for computing the degree for each node, and another layer for taking the operation over nodes should be sufficient.
13

---

Under review as a conference paper at ICLR 2022
A.9 MAX FLOW
The Max Flow problem gives a directional graph with capacities on edges, and indicate two nodes S and T. The models is then asked compute the amount of max-flow from S to T.
Notice that the Breadth First Search (BFS) component in Dinic's algorithm(Dinic, 1970) can be implemented ReINNS as they does not require node identities (all new-visited nodes can augment to their non-visited neighbors in parallel), Since the BFS runs for O(n) iteration, and the Dinic's algorithm runs BFS Onn²) times, the max-flow be solved by ReINNs with in (n²) iterations.
A. DISTANCE
Given a graph with weighted edges, compute the length of the shortest between specified node pair (S-T Distance) all node pairs (All-pair Distance).
Similar to Connectivity problems, but Distance problems now additionally record the minimum distance from S (for S-T) or between every node pairs (for All-pair), which can be updated using min operator (using Min-plus matrix multiplication for All-pair case).
B PROOFS AND ANALYSIS
B. CONSTANT-LAYER RELNNS AND RECURRENT RELNNS
Theorem B.1. A neural network with representation width W that has D different layers NN1, ... NND can be realized by a neural network that applies single layer NN' for D iter- ations with width (D 1)(W + 1).
Proof. The representation for NN' can be partitioned into D + segments each of length W 1. Each segment consist of "flag" element and a W Welement representation, which are all 0 initially, except for the first segment, where the flag is set to 1, and the representation is the input.
NN' has the weights for all N....... NND, where weights NN; are used compute the representa- tion segment
from the representation in segment Additionally, each iteration, segment i can only be computed if the flag in segment is 1, in which case the flag of segment + 1
set to 1. Clearly, after D iterations, the output NN₃ should be the representation in segment D +
Due to Theorem B.I, we consider the neural networks that recurrently apply the same layer because they are expressive as those using layers of different weights, b) it is easier to analyze single neural network layer than D layers, and c) they naturally generalize to neural networks that runs for adaptive number of iterations (e.g. GNNs that run O(log n. iterations where the size of the input graph).
B.2 EXPRESSIVENESS EQUIVALENCE OF RELATIONAL NEURAL NETWORKS
We first describe a framework for quantifying if two ReINN models are equally expressive on regression tasks. The framework view the expressiveness from the perspective of computation. Specifically, we will prove the expressiveness equivalence between models by showing that their computation can be aligned.
In complexity, we usually show problem is at least as hard as the other one by showing a reduction from the other problem to the problem. Similarly, on the expressiveness of ReINNs, we can construct reduction from model family A to model family B to show that B can realize all computation that A does, or even more. Formally, we have the following definition.
Definition B.1 (Expressiveness reduction). For two model families A and B, we say A can be reduced to 13 if and only if there is function r A B such that for each model instance A A, r(A) E B and have the same outputs on all inputs. In this case, we say B is at least as expressive as A.
Definition B.2 (Expressivenesss equivalence). For two model families A and B, if AA and B can be reduced to each other, then A and B are equally expressive. Note that this definition of expressiveness equivalence generalizes to both classification and regression tasks.
14

---

Under review as a conference paper at ICLR 2022
Graph Neural Networks. GNNs (Scarselli et al., 2008) is defined based on two message passing operations.
Edge update: the feature of each edge updated by features of ends.
Note update: the feature of each node is updated by features of all edges adjacent it.
This message passing scheme easily fit in ReINN architecture by storing edge features tuples of two nodes. In this case, updating edges by its ends can he realized by the expand and the permute operation. The message aggregation at each node be realized by reduce operation. Hence, GNNs can be realized by ReINN of maximum arity B = 2.
Higgh-dimensional GNNs. Computing only node-wise and edge-wise features does not handle higher-order relations, such as triangles in the graph. In order to obtain more expressive power, GNNs have be extend to hypergraphs of hier arity (Morris et al., 2019). Specifically, GNNs on B-ary hypergraph maintains features for all B-tuple of nodes, and the neighborhood is extended to B-tuples accordingly: the feature of tuple (#1, P2,"" ... (B) updated by the [V] element multiset (contain [V] elements for each u E V) of B-tuples of features
(Hilu, v2,- up], (11, u, ... UB),
111-101,. UB-1, uI)
(B.1)
where Hc-1vv) is the feature of tuple v from the previous iteration.
We now introduce the formal definition of the high-dimensional message passing. We denote as a B-tuple of nodes (1), U2, ... ). and generalize the neighborhood to a higher dimension by defining the neighborhood of as all node tuples that differ from v at one position.
Neighbors(e) v, u) ((,,v,, UB) (01, .. UB)) (U1, .B-1.u)) (B.2) N(w) = (Neighbors(e; u)lu E v
(B.3)
Then message passing scheme naturally generalizes to high-dimensional features using the high- dimensional neighborhood.
Received,(e]
Σ (NN, (H:-1[o);
Eneighbors((.au) H, H1-1(0')))
(B.4)
Recall that the normal GNNs can be realize by ReINNI 2]. Similarly, since features of B-tuples can be stored in ReINNs with arity B and the high-dimensional message passing involves at most B ++1 nodes at the same time, (v), vn and w), we can extend the previous result to that GNNs on B-arity hypergraphs can be realized by ReINNs with maximum arity B B+1
Equivalence between hypergraph GNNs and ReINNs. We will prove the equivalence between hypergraph GNNs and ReINNs by making reductions in both directions.
Lemma B.2. A GNN on B-ary hypergraphs and depth D can be realized by ReINN with maximum arity + and depth 2D.
Proof. We prove lemma B.2 by showing that layer of GNNs B-ary hypergraphs can be realized by two ReINN with maximum arity +
Firstly, GNN layer maintain features of B-tuples which stored in correspondingly in an ReINN layer at dimension B. Then we will realize the message passing scheme using the ReINN features of dimension B and B + 1 in two steps.
Recall the message passing scheme generalized to high dimensions (to distinguish, we use for GNN features and T' for ReINN features.)
Received, (v) - (NN, (Hu] C wneighhosss) H,-1
(B.5)
15

---

Under review as a conference paper at ICLR 2022
At the first step, the Expand operation first raise the dimension B + 1 by expanding non-related variable u to the end, and the Permute operation can then swap u with each of the elements (or no swap). Particularly, Ti,n(2h 0 Up) will be expand to
UB vnl. T T++1.+1 (11 02 BB- u, B. 1++1.++1 (1, 02, 1: UB,
[+11,41.7 U2, 0.. UB
1, u, V3, .., UB, 22),
Hence, T,41, /8+ (1), 02, va. un, u receives the features from
Ti, ",, ,u): Ti,lu, U2, Us ... , [er, u, ".."" "u,, .., Ti,B(1,, "2,'" ,B u)
These features matches the input of NN, in equation B.5, and in this layer NN, can be applied to compute things inside the summation.
Then at the second step, the last element is reduced to get what tuple should receive, so a can be updated. Since each GNN layer can be realized by such two ReINN layers, each GNN on B-ary hypergraphs with depth D can be realized by ReINN of maximum arity (B + 1) and depth 2D. D
To complete the proof we need to find a reduction from ReINNs of maximum arity B + 1 to GNNs on B-ary hypergraphs. The key observation here is that the features of (B + 1--upels in ReINNs can only be expanded from sub-tuples, and the expansion and reduction involving (B + 1) -ttuless can be simulated by the message passing process.
Lemma B.3. The features of (B tt-tup feature T.,++I ". UB+1l can be computed from the following tuples
(Ti,alv2, " UB+1 Tr,al Tr, us,"" " "BBt), Ti,a(m, "2.
Proof. Lemma B.3 is true because (B + 1--dimensional representations can either be computed from themselves at the previous iteration, expanded from B-dimensional representations. Since representations at all previous iterations j < i can be contained Ti, B, it is sufficient to compute Ti,++1[11, " UB+1 from all its B-ary sub-tuples.
Then let's construct the GNN for given ReINN to show the existence of the reduction.
Lemma B.4. A ReINN of maximum arity B + and depth D can be realized by a GNN on B-ary hypergraphs with no more than D iterations.
Proof. We can realize the Expand and Reduce operation with only the B-dimensional features using the broadcast message passing scheme. Note that Expand and Reduce between B-dimensional features and (B -ddimennsioaal features in the ReINN is a special case where claim B.3 is applied.
Let's start with Expand and Reduce operations between features of dimension B or lower. For the b-dimensional feature in the ReINN, we keep "- copies of and store them the representation of every B-tuple who has a sub-tuple" that is permutation of the b-tuple. That is, for each B-tuple in the GNN on B-ary hypergraphs, for its every sub-tuple of length b, we store representations corresponding to every permutation of the b-tuple in the ReINN. Keeping representation for all sub-tuple permutations make it possible to realize the Permute operation. Also, it easy to notice that Expand operation is realized already, as all features with dimension lower than B are naturally expanded to B dimension by filling in all possible combinations of the rest elements. Finally, the Reduce operation be realized using broadcast casting message passing certain position of the tuple.
Now let's move to the special case the Expand and Reduce operation between features of dimensions B and B + 1. Claim B.3 suggests how the (B + d)ddimensional features are stored in B-dimensionnl representations in GNNs, and now show how the Reduce be realized by message passing.
$ 5,25 = n (n- - 1) x ... (n - 1).
"The sub-tuple does not have to he consecutive, but instead can be any subset of the tuple that keeps the element order.
16

---

Under review as a conference paper at ICLR 2022
We first bring in claim B.3 to the GNN message passing, where we have Received, [a] to be
Σ (NN1 (Ti-1,B(02; ".. ,B, u), T:-1,B(11 Us, ".... ,B, "B,u)," u., .. 1) u2, uBl))
Note that the last term 7: 1.-1. u2," ... uB| contained in (v) in equation B.5, and other terms are contained in (v') for of neighbors(v, u). Hence, equation B.5 is sufficient to simulate the Reduce operation.
Theorem B.5. GNNs on B-ary hypergraphs are equally expressive as ReINNs with maximum arity B 1.
Proof. This is direct conclusion by combining Lemma B.2 and Lemma B.4.
B.3 EXPRESSIVENESS OF HYPERGRAPH CONVOLUTION AND ATTENTION
Hypergraph convolution(Feng et al., 2019; Yadati et al., 2019; Bai et al., 2021), attention(Dinn et al., 2020) and message passing(Huang Yang. 2021) focus on updating node features through hyperedges instead of hyperedges. These approaches can be viewed as instances of ReINNs, and they have smaller time complexity because they do not model all high-arity tuples. However, they are less expressive than ReINNs with equal max arity.
These approaches can be formulated to two steps at each iteration. At the first step, each hyperedge updated by the features of nodes it connects.
hie AGGueefi-LL.
(B.6)
At the second step, each node updated by the features of hyperedges connecting it.
fu.e = AGGueehi,
(B.7)
where f.v is the feature of node at iteration i, and he is the aggregated message passing through hyperedge at iteration i + 1.
is not hard to see that B.6 can be realized by B iterations of ReINN layers with Expand operations where B is the max arity of hyperedges. This can be done by expanding each node feature to every high arity features that contain the node, and aggregate them at the tuple corresponding to each hyperedge. Then, B.7 can also be realized by B iterations of ReINN layers with Reduce operations, as the tuple feature will finally be reduced to single node contained in the tuple.
This approach has lower complexity compared to the GNNs study applied on hyperedges, because it only requires communication between nodes and hyperedges connecting to them, which takes O(VV (El) time each iteration. Compared them, ReINNs takes ((IV)²) time because ReINNs keep features of every tuple with max arity B, and allow communication from tuples to tuples instead of between tuples and single nodes. An example is provided below that this approach not solve while ReINNs can.
Consider graph with 6 nodes and 6 edges forming two triangles 21,2,3) and (4,5, 6). Because of the symmetry, the representation of each node should be identical throughout hypergraph message passing rounds. Hence, it is impossible for these models conclude that (1, 2, 3) is a triangle but (4, 2, 3) is not, based only on the node representations, because they are identical. In contrast, ReINNs with max arity can solve them (as standard triangle detection problem Table 1).
B.4 PROOF OF THEOREM 3.1: 1: ARITY HIERARCHY.
Morris et al. (2019) have connected high-dimensional GNNs with high-dimensional WL tests. Specifi- cally, they showed that the GNNs on B-arry hypergraphs are equally expressive as B-dimensional WL test on graph isomorphism test problem. In Theorem B.5 we proved that GNNs on B-ary hypergraphs equivalent to ReINN of maximum arity B + 1 in terms of expressiveness. Hence, ReINN of maximum arity B + 1 can distinguish if two non non-isomorphic graphs if and only if B B-dimensional WL. test can distinguish them.
17

---

Under review as a conference paper at ICLR 2022
However, Cai et al. (1992) provided construction that can generate a pair of non-isomorphic graphs for every B, which can not be distinguished by (B - -i-diemnnio WL test but can be distinguished by B-dimensional WL test. Let G'g and G be such pair of graph.
Since ReINN of maximum arity B + 1 is equally expressive as GNNs on B-ary hypergraphs, there must be such ReINN that classify G/B and G3 into different label. However, such ReINN can not be realized by any ReINN of maximum arity B because they are proven to have identical outputs on G3 and CB..
In the other direction, ReINNs of maximum arity B + 1 can directly realize ReINNs of maximum arity B, which completes the proof.
B.5 PROOF OF THEOREM 3.4: UPPER DEPTH BOUND FOR UNBOUNDED- PRECIISION RELNN.
The idea for proving an upper bound on depth is to connect ReINNs to WL-test, and use the On upper bound on number of iterations for B-dimensional test (Kiefer & Schweitzer, 2016), and FOC formula is the key connection.
For any fixed n, B-dimensional WL test divide all graphs of size n, G=n, into set of equivalence classes {C1, C2 ,.. J. where two graphs belong to the same class if they can not be distinguished by the WL test. We have shown that ReINNs of maximum arity (B + 1) must have the same input for all graphs in the same equivalence class. Thus, any ReINN of maximum arity B + 1 can be view as a labeling over CI.... CCm.
Stated by Cai et al. (1992), B B-dimensional WL test are as powerful as FOC in differentiating graphs graphs. Combined with the (n upper bound of WL. test iterations, for each C, there must be an FOCB+1 formula of quantifier depth (nn)) that exactly recognize C, over 9=n-
Finally, with unbounded precision, for any f(n), ReINN of maximum arity B ++1 1 and depth (n) can compute all FOC formulas with quantifier depth [mm Note that there are finite number of such formula because the supscript of counting quantifiers is bounded by n.
For any graph in some class C., the class can be determined by evaluating these FOC formulas, and then the label is determined. Therefore, any ReINN of maximum arity B + 1 can be realized by a ReINN of maximum arity B + 1 and depth (
B.6 THE TIME AND SPACE COMPLEXITY OF RELNNS
Handling high-arity features and using deeper models usually increase the computational cost in terms of time and space. As an instance that use the architecture of ReINN, NLMs with depth D and max arity B takes O(Dm B) time when applying to graphs with size This is because both Expand and Reduce operation have linear time complexity with respect to the input size (which is O(nB) each iteration). If we need to record the computational history (which is typically the case when training the network using back propagation), the space complexity is the same as the time complexity.
GNNs applied to (B - 1)-y hyperedges and depth D are equally expressive as ReINNs with depth O(D) and max arity B. Though up to 1)-ary features are kept in their architecture, the broadcast message passing scheme scale up the complexity by a factor of O(n), so they also have time and space complexity O(DBB) Here the length of feature tensors W is treated as a constant.
B.7 PROOF OF THEOREM 4.2: PAC BOUNDS FOR RELNNS
We first formally define the (e, 5) approximation on functions mapping real number factors.
Definition B.3, We say Mi is (e, 6) approximmtionn of M2 R& RW if and only if with probability at least (1 - 6), M1(x) - M2 <.
The proof builds on bounding the error between the representations computed by M and M'. Assuming the Lipschitz continuity with constant X, we will show four facts that are sufficient to bound the error between M and M', and thus claim the approximation of M on f.
(a) forward networks increase the error by at most factor of X.
(b) The min-max aggregation increase the error by at most a factor v W.
(c) The mean aggregation keeps the error bounded.
18

---

Under review as a conference paper at ICLR 2022
(d) The probability avoid any failures is lower bounded by - O(Dn"8))
Fact (a) guaranteed under the definition of Lipschitz continuity. For fact (b), we denote t be the error bound on the representations before aggregation, and f also bounds the error at each position. In the worst case, min-max aggregation will get the error at positions, which implies new error bound vWt on the aggregated representation on the 2-norm. Fact (c) guaranteed by the convexity of 2-norm. Fact (d) can be derived by a simple union bound on the failure probability all internal representations (they are O(Dn representations to compute when applying the layer for D iterations).
Note that at each iteration we will run feed-forward network parallel for all representations, and aggregate some n-tuple of representations. These operations increase the error bound by factor of at most λv W for min-max aggregation and À for mean aggregation.
Sample complexity for ReINNs with gradient decent. Arora et al. (2019) have derived a more fine-grained analysis on the of two-layer neural networks optimized by gradient decent, which is later extended by Xu et (2020) under the sequential learning setting i.e. we use a correct network instance M' to generate the ground-truth outputs to supervise all feed-forward networks each layer. Theorem B.6 (Xu al. (2020), sample complexity for over-parameterized MLP modules). Let M be an over-parameterized and random initialized two-layer MLP trained with gradient decent for suffi-
cient number of iterations. Suppose RWW R with components ((x) E, a (ef 2)35 where 8 E RRW. E Ih and Pj
21 (1 N+). The sample complexity Cmlg,e, is (6) or pj (6)
115 (9)
max, ag (6)
+ +lg((W/))
(B.8)
(c/W)²
We combine Theorem B.6 with theorem 4.2 to derive the sample complexity in order to get (e, 8) apprroxximaaion. We can compute ENN = O( (T)
/ and ôNN = 0 Di for feed-forward
network in the ReINN, and bring them as to Theorém B.6 to get the following equation
C = max; E, Σソ 1a
(0) (0) -13
P.
+ (lgg(nDW/))
(B.9)
(20W012)
l0 (8( 2)p, and B, W are the where RW + RW has components g(x)(() = E, at dimension, number iterations, width for specifying the model family M.
The sample complexity does not have requirement of the sample graph size, because under the sequential learning setting the feed-forward networks are trained under supervision on each node and tuple at each layer. Though this setting can not be implemented in practice, in our experiments observe good generalization of models trained on small graphs.
C EXPERIMENTS
C.I EXPERIMENT SETUP
For all problems, we have 800 training samples, 100 validation samples, and 300 test samples for each different n we are testing the models on.
We then provide the details on how we synthesize the data. For most of the problems, we generate the graph by randomly selecting from all potential edges i.e. the Erdös-Rényí model. We sample the number of edges around n, 2n, n log and n² /2. For all problems, with 50% probability the graph will first be divided into 3,3,4 4 or 5 parts with equal number components, where we use the first generated component to fill the edges for rest of the components. Some random edges added afterwards. This make the data contain more isomorphic uub-graphs, which we found challenging empirically.
19

---

Under review as a conference paper at ICLR 2022
Substructure Detection. To generate graph that does not contain certain substructure, randomly add edges when reaching a maximal graph not containing the substructure or reaching the edge limit. For generating graph that does contain the certain substructure, we first generate one that does not contain, and then randomly replace present edges with missing edges until we detect the substructure in the graph. This aim to change the label from "No" "Yes" while minimizing the change to the overall graph properties, and we found that data generated using edge replacing is much more difficult for neural networks compared random generated graphs from scratch.
Family Tree. We generate the family trees using the algorithm modified from Dong al. (2019). We add people to the family one by one. When person is added, with probability we will try to find a single woman and single man, get them married and let the new children be their child, and otherwise the new person is introduced and set the gender with a coin flip.
non-related person. Every new person is marked as single
We adjusty based on the ratio of single population: p 0.7 when more than 40% of the population are single, and = 0.3 when less than 20% the population are single, and p = 0.5 otherwise.
Connectivity. For connectivity problems, we use the similar generation method as the substructure detection. We sample the query pairs that the labels are balanced.
C.2 MODEL IMPLEMENTATION DETAILS
For all models, we use a hidden dimension 128 except for 3-dimensional HD-GNN and d-dimensional NLM where we use hidden dimension 64.
All model have 4 layers that each has its own parameters, except for connectivity where we use the recurrent models that apply the second layer & times, where i is sampled from integers in [og n, 3 log n]. The depths are proven to be sufficient for solving these problems (unless the model itself can not solve).
All models are trained for 100 epochs using adam optimizer with learning rate 10 decaying at epoch 50 and 80.
We have varied the depth, the hidden dimension, and the activation function of different models. We select sufficient hidden dimension and depth for every model and problem (i.e., stop when increasing depth or hidden dimension doesn't it increase the accuracy). We tried linear, ReLU, and Sigmoid activation functions, and ReLU performed the best overall combinations of models and tasks.
Generalization on Connectivity-4
100%
90%
80%
Accuracy
70%
ID-GNN-MAK
60%
IDM
3D-NLM-MAY
2D-NLM-SUM
50%
2D-GNN-MAX
2D-GNN-SUM
40%
3D-NLM-MAX
30-NLM-SUM
30%
10
20
30
40
50
60
70
80
Test graph sizes, trained on n 10
Figure 2: How the performance of models drop when generalizing larger graphs the problem connectivity-4 (trained on graphs with size 10).
20

---

Under review as a conference paper at ICLR 2022
Sample Complexity (case study on triangle detection)
100%
90%
Accuracy
80%
70%
60%
50%
3D-NLM-MAX
D-N
40%
10
15
20
30
50
80
120
200 300
500
800
#Training Samples
Figure 3: The test accuracy when the number of training samples varies between 10 and 300. All numbers are averaged over three runs with randomly selected training sets. Note that we do not test structural generalization here, so 10 for both training and testing).
C.3 ADDITIONAL ABLATION STUDIES
Case study on structure generalize. We run case study on the problem connectivity-4 about how the generalization performance changes when the test graph size gradually becomes larger. Figure 2 how how these models generalize to gradually larger graphs with size increasing from 10to80. From the curves same size graphs, and among them the models using max aggregation generalize to larger graphs with performance drop. 2-ary GNN and 3-ary NLM that use max aggregation have sufficient expressiveness and better generalization property. They achieve 100% accuracy on the original graph size and generalize perfectly to larger graphs.
that only models with sufficient expressiveness
get 100% accuracy on the
Case study on sample complexity. order to better visualize how using max and sum aggregation functions affect the sample complexity. We run an ablation study on the triangle detection problem where we try different numbers of training samples from 10 to 800. We test 3-ary NLM with max and sum aggregation which both reach 100% accuracy on the same graph size (we do test generalization here since max aggregation is shown to be more generalizable than sum aggregation). Figure indicates that the NLM model with max aggregation require much fewer training samples (~> 30) to reach the perfect accuracy compare to sum aggregation (~~ 300.)
21


Reviews:
[{"review_id": "qF7V9BD-dvx", "reviewer": "Reviewer_d5Yc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper offers an interesting perspective on relational models in that it studies them via a unifying framework. Moreover, it generalizes existing results beyond the binary setting into arbitrary arity settings. However, the results presented in the paper are not significant enough. Indeed, the proposed arity hierarchy is a simple generalization of existing expressiveness results as well as results on the WL hierarchy, and such results are not surprising, as they are already established, e.g., for higher-order GNNs [1], which study the higher-arity setting. Moreover, the depth and arity requirements provided in Table 1 follow easily from the FOC^k characterization, and thus do not offer any new insights in my opinion. To illustrate, connectedness can clearly be captured with B=3, as the general connectedness task can be written as a formula in FOC^3 (even just FO^3). By contrast, FOC^2 is not sufficient to capture connectedness, and this propagates to RelNN with B=2 and fixed depth. Moreover, all S-T problems can be easily solved with a depth n GNN, simply by propagating a ``beacon'' from S to N and seeing whether this reaches T after n hops. The proposed conjectures are also not rigorous enough, and do not provide further insights as to the power of RelNN models.\n\nI also find that the RelNN framework does not produce any novel understanding of relational models. Indeed, the connection between, e.g., GNNs and Transformers is already well-established and studied in the literature [2], and the current study does not propose any novelty here. Furthermore, the experimental analysis is not convincing, and merely confirms the aforementioned simple results, and does not study the learning bounds part of the paper with sufficient detail. \n\nAll in all, the paper makes a series of small contributions which, in my opinion, are not sufficient for publication. \n\n[1] Nicolas Keriven and Gabriel Peyre. Universal Invariant and Equivariant Graph Neural Networks, NeurIPS 2019.\n\n[2] William L. Hamilton. Graph Representation Learning. Morgan and Claypool Publishers, 2020.", "summary_of_the_paper": "The paper proposes a unifying study of models for relational learning, namely Transformers, Graph Neural Networks (GNNs), and Neural Logic Machines (NLM), under the RelNN framework, and provides a series of results pertaining to their expressiveness relative to the arity of relations they support, as well as the depth, i.e., the number of iterations, they use during computation. In particular, arity and depth hierarchies are studied, and a set of arity and depth requirements are stated for a set of computational problems. Furthermore, the generalization ability of RelNN models is studied in the fixed-precision and infinite-precision settings. In the former setting, it is shown that there exists a finite size N for input graphs at which perfectly fitting all possible input graphs yields perfect generalization onto graphs of size greater than N. In the latter case, the sample complexity required to achieve certain error bounds is studied, and it is shown that more range-restricted aggregation function such as max and mean enable improved sample complexity. Finally, the paper conducts an experimental analysis on several synthetic problems, and achieves results validating the earlier provided arity and depth results for RelNN.", "summary_of_the_review": "The paper's main contributions and results, especially on the expressiveness side, are simple and already well-studied in the literature, and thus are not insightful or novel enough to warrant publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "pwPuK6CoqPW", "reviewer": "Reviewer_6v52", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1.\tThe proposed hierarchical architecture of RelNN presents a novel angel to understand relational neural networks.\n2.\tIts proof on RelNN’s improved expressiveness with larger D and B seems correct, and it brings meaningfully new knowledge.\n\nCons:\n1.\tQuestionable claim. RelNN’s claimed unification of GNN, Transformers, NLM seems far-fetched and lacks justification. It is true that most GNNs can be conceptually viewed as a message passing process involving successive updates of edge features and then of node features. While I have no problem with the resemblance, how GNN’s computation graph can be rigorously expressed using RelNN’s framework is completely unjustified. It would be very helpful to explicitly explain what each T_{i,j} in Fig. 1 refers to for at least two concrete instances of GNN (GCN and GAT for example), as is also the case with Transformer. The correctness of this claim on unification appears questionable to me before more details are confirmed.\n2.\tLimited Readability. Besides the first point, there are many other places where the reasoning seems ambiguous or even arbitrary with abused terms and typos. For example in Sec.2.1, it first defines hypergraph representation functions as X = {X_0, X_1, X_2 …} and then in the example right below it uses X = {X_2}, which contradicts; in the same subsection it mentions “hyperedge representation function Y on V”, which should be “hypergraph representation function Y on the set of all size-k tuples of V’s nodes”; In the third bullet point,  Y = {X_1} should be Y = {Y_1}. In sec. 2.2, the \"j+1 dimension\" should be (j+1)st and it should be clarified that the feature dimension is the last dimension of the tensor. There are many other such places throughout the paper. While some are easy to sort out the actual meaning based on context, some others take readers significant time to figure out or even to realize. Therefore, the general readability is very limited.  \n3.\tExperiments and Scalability. The paper claims main contribution on hypergraphs, but the experiments are limited to graph datasets only. Meanwhile, only n=80 is tested. Can RelNN work when n is large? It seems that RelNN struggles seriously with slightly larger graphs or hypergraphs with large hyperedges because of its node tuple definition. A thorough analysis here is very necessary. It also appears unclear what a 3-ary GNN is. Is that a realization of RelNN with B = 3? That also comes down to my first point what GNN is instantiated using RelNN.\n", "summary_of_the_paper": "This paper presents a new generic framework of relational neural network defined over hypergraphs, which they call RelNN. RelNNs take an architecture which hierarchically operates on representation functions of node tuples of different sizes and can be stacked into multiple layers. The framework is claimed to have unified graph neural network, neural logical machines and tranformers. The authors conduct analysis of RelNNs and show that its expressiveness increases as the artity or the number of RelNN layers grows sufficiently large. The paper also characterizes the generalizability of RelNN under certain conditions. ", "summary_of_the_review": "In summary, I appreciate that the authors make a great effort to unify several important relational neural networks. However, the paper suffers from its weak justification (on the claimed unification), lack of scalability, insufficient experiment, and ambiguous writing style in general. Therefore, I do not vote for its acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fg-t5gVeJKA", "reviewer": "Reviewer_4AVA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe studied problem of improving the representation and model generalization ability is important for many relational learning tasks.\n\nThe theoretical discussion of the unified relational learning framework is provided with theoretical analysis results.\n\nWeaknesses:\n\nState-of-the-art relational learning models are missing in the performance comparison, which can hardly demonstrate the effectiveness of the new learning framework. For example, the new framework should be compared against state-of-the-art graph neural models for capturing graph structural relationships, and the Transformer-based sequence learning.\n\nThe model scalability should be investigated in the experiments. Since the new model is built over the hypergraph structure, how is the time complexity of the hypergraph-guided relational learning should be investigated.\n\nLack of detailed description with respect to hyperparameter tuning strategies on the new proposed framework. Different hyperparameter selection may provide different prediction performance, which has been demonstrated in previous research work on graph neural networks and Transformer. It is necessary to present how the models are tuned to achieve good performance under a fair experimental setting.", "summary_of_the_paper": "This paper explores the expressiveness of neural network-based relational learning models, such as graph neural networks and Transformer. To this end, a rational neural network is built upon the hypergraph structures to unify different models. Synthetic datasets are used for performance evaluation.", "summary_of_the_review": "Several concerns for this work: (1) Key experimental setting information is missing in the evaluation section. (2) Many state-of-the-art relational learning methods are missing. (3) For fair evaluation, it is better to present the hyperparameter tuning for the new method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Xjp1OlzCTDj", "reviewer": "Reviewer_NLAa", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On the positive side: 1) the authors introduce quite a general class of trainable models, and 2) they characterise the expressiveness and the generalisation capacity of these models. Noteworthy is the notion of quantifying the generalisation as a function of the size of the input test graphs. \nOn the negative side: the theoretical analysis is not accompanied by an adequate empirical investigation. \nFirst of all, it is not clear if the graphs in the experiments are labelled or unlabelled: if they are labelled it would be of interest to report the label alphabet size and distribution; if the results refer to unlabelled graphs, it should be of interest to extend the experimentation to the more realistic case of labelled graphs.\nSince one of the main contribution is the characterisation of the sample complexity and the generalisation to larger graphs, it would be appropriate to report an extensive experimental analysis of the alignment between theory and practice; it would therefore be of interest to report: 1) learning curves (i.e. reporting on the horizontal axis the training set size) to analyse the sample complexity behaviour in various scenarios  and 2) an analysis of the performance as the test set graphs size increases.\nPresenting result on some more challenging tasks would also be of interest, e.g. a graph diameter regression task.\nPlease consider using an adequate testing of the significance of the result differences (e.g. following [Benavoli, Alessio, Giorgio Corani, Janez Demšar, and Marco Zaffalon. \"Time for a change: a tutorial for comparing multiple classifiers through Bayesian analysis.\" The Journal of Machine Learning Research 18, no. 1 (2017): 2653-2688.] or using the library [https://github.com/sherbold/autorank]).\n ", "summary_of_the_paper": "The authors present a framework to study the expressiveness and the generalisation capacity of a class of forward message passing algorithms that encompass graph neural networks, transformers and neural logic machines.   ", "summary_of_the_review": "The theoretical analysis is not accompanied by an adequate empirical investigation. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "E4qzVhuHJ5", "reviewer": "Reviewer_m5XE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n### **Strengths**\n\n1) The paper is well organised.\n2) RelNNs unify three neural network architectures on relational data (GNNs, NLMs, Transformers).\n3) The paper studies expressiveness and generalisability of RelNNs.\n\n\n### **Weaknesses**\n\n1) An important contribution claimed in the paper is that RelNNs can be applied to hypergraph reasoning tasks. However, all tasks in the experiments are graph-related (i.e., without hyperedges of size more than two). \n2) The experiments seem to not compare with existing methods, e.g., [Barcelo et al., ICLR'20]. Adding such a comparison would help making an empirical argument for why the results are significant.\n3) All datasets are synthetically generated and it is unclear how the results of the paper can be generalised to real-world relational data (e.g., real-world graph classification problems such as molecule property prediction).\n4) The synthetic datasets are tiny: all graphs contain fewer than 100 nodes.\n5) There is no discussion of important prior work and it is unclear if RelNNs can generalise neural networks defined on hypergraphs. Some publications are listed below:\n    1) Hypergraph Neural Networks, AAAI'19,\n    2) HyperGCN: A New Method for Training Graph Convolutional Networks on Hypergraphs, NeurIPS'19,\n    3) Hypergraph Convolution and Hypergraph Attention, Pattern Recognition'21,\n    4) Hyper-SAGNN: a self-attention based graph neural network for hypergraphs, ICLR'20,\n    5) Be More with Less: Hypergraph Attention Networks for Inductive Text Classification, EMNLP'20,\n    6) UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks, IJCAI'21.", "summary_of_the_paper": "Neural Networks for relational data have been an active topic of research interest in recent years. There is still a lack of full understanding of the expressivity, generalisability of these models. The contributions of the paper are:\n1) Development of relational neural networks (RelNNs) for (hyper)graphs that unify graph neural networks (GNNs), neural logical machines (NLMs), and transformers,\n2) Analysis of the expressivity of RelNNs in terms of (i) maximum hyperedge size and (ii) depth of RelNN, and\n3) A study of the generalisability of RelNNs to unseen test data.", "summary_of_the_review": "Overall the paper is well organised with good theory. \nHowever, the main claims made in the paper need rigorous empirical evaluation.\nPositioning with missing prior work and empirical evaluation on real-world hypergraph reasoning tasks would greatly improve the quality of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper aims to improve our understanding of GNNs for relational reasoning. In this regard, authors develop a conceptual framework unifying popular models (GNNs, Transformers, etc.) for analyzing their expressiveness and learning capacity. We thank the reviewers and authors for engaging in an active discussion. Based on author comments, the goal of the paper was more of a conceptual exposition, however this did not come across to the reviewers from the manuscript at first. Thus, a better presentation would definitely make the paper much more accessible and useful to the community. Moreover, there were some concerns about the significance of the exposition and better positioning would help (e.g., how the results help improve our understanding of GNNs). Thus, unfortunately I cannot recommend an acceptance of the paper in its current form.
Decision: Reject