Towards Better Generalization with Flexible Representation of Multi-Module Graph Neural Networks
Authors: HyunGeun Lee
Kijung Yoon
Venue: Accepted by TMLR ()

Abstract: Graph neural networks (GNNs) have become compelling models designed to perform learning and inference on graph-structured data. However, little work has been done to understand the fundamental limitations of GNNs for scaling to larger graphs and generalizing to out-of-distribution (OOD) inputs. In this paper, we use a random graph generator to systematically investigate how the graph size and structural properties affect the predictive performance of GNNs. We present specific evidence that the average node degree is a key feature in determining whether GNNs can generalize to unseen graphs, and that the use of multiple node update functions can improve the generalization performance of GNNs when dealing with graphs of multimodal degree distributions. Accordingly, we propose a multi-module GNN framework that allows the network to adapt flexibly to new graphs by generalizing a single canonical nonlinear transformation over aggregated inputs. Our results show that the multi-module GNNs improve the OOD generalization on a variety of inference tasks in the direction of diverse structural features.

Published in Transactions on Machine Learning Research (07/2023)
Towards Better Generalization with Flexible Representation of Multi-Module Graph Neural Networks
Hyungeun Lee
didls 1228 Ghanyongg oc.kr
Deportment of Electronic Engineering Hongang University
Kijung Yoon
kiyoonChanyang.ook ac.
Department of Electronic Engineering Honyang University
Reviewed on OpenReview:
openreveee. net/ pert/foum?? id= EY
Abstract
Graph neural networks (GNNs) have become compelling models designed to perform learning and inference on graph-structured data. However, little work has been done to understand the fundamental limitations of GNNs for scaling to larger graphs and generalizing to out-of- distribution (OOD) imputs. In this paper, we use a random graph generator to systematically investigate how the graph size and structural propertics affect the prodictive performance of GNNs. We present specific evidence that the average node degree is key feature in determining whether GNNs generalize to unseen graphs, and that the of multiple node update functions improve the generalization performance of GNNs when dealing with graphs of multimodal degree distributions. Accordingly, we propose multi-module GNN framework that allows the network to adapt flexibly to new graphs by generalizing a single canonical nonlinear transformation over aggregated inputs. Our results show that the multi-module GNNs improve the OOD generalization on a variety of inference tasks the direction of diverse structural features.
1
Introduction
Graph neural networks (GNNs) have recently boen established as an effective machine lcarning models for representation learning on grapl-structured data (Scarselli et al. 2008
Hamilton et al., 2017b Bronstein et al. 2017 Battaglia et al. 2018). Graph is a powerful mathematical abstraction that can represent the structure of many complex data, and learning on graphs has been widely explored in many scientific domains
DDuvenaud et al. 2015 Gilmer al. 2017: Sanzaez-Gonzaeez et al. 2018 2020 Gainza et al. 2020
Despite the growing empirical success of GNNs in various fields, the necessity of a deeper understanding of this model framework has arisen due to the inconsistent model efficiency across different tasks and experimental settings. Building large-scale graph benchmarks (Dwivedi et al.) 2020: Hu et al.] 20200 one recent attempt
to address this challenge, and there have also been significant theoretical studies on the expressivity of GNNs
focused on the isomorphism task (Xu et al. 2019; Morris et al., 2019 Garg et al. 2020 Sato 2020 Morris
eet al. 2021). However, little work has been conducted on understanding the fundamental limitations of GNNs for adapting to distribution shifts graphs, where systematic differences between training and test data significantly degrade model performance.
Recent approaches to OOD generalization (Oadia et al. 2019 Arjovsky et al. 2019 Ahuja et al. 2021 Lu et al. 2021] concentrate primarily on images or structural equation models. However, the nature of the graph domain is fundamentally different from these works in that the inputs are not simple image features or variables, but full of complex irregularities and connectivity in topology. We hypothesize that the difference in underlying graph properties of training and testing datasets (i.e. structural distribution shift) presents

---

Published in Transactions on Machine Learning Research (07 (07/2023)
fundamental challenge to the extrapolation beyond the range of input distribution. We are particularly interested in the conditions under which we can expect GNNs to (not) perform well in predicting targets for unseen graphs. To study this question, we use a random graph generator that allows us to systematically investigate how the graph size and structural propertics affect the prodictive performance GNNs.
We argue that, among the many graph properties, the average node degree within each mode of the degree distribution is a key factor that determine whether GNNs can generalize unseen graphs. Then, we propose and explore methods for using multiple node update functions nonlinear transformation over aggregated imputs. This approach enhances the flexibility of the network to handle shifts in graph propertics, resulting in better control over structural distribution shifts. We evaluate the performance of the multi-module GNN framework on the task of approximating marginal inference for general graphs (Pearl 1988), solving graph theory multi-task problems (Corso et al. 2020), conducting CLRS algorithmic reasoning tasks (Veličković et al. 2022), and benchmarking against OOD scenarios for real-world
way to generalize single canonical
graphs (Gui et al. 2022 Our key contributions are as follows:
1. In Section 3.1 we present diverse and densely populated random graph benchmark that enables the identification of visually recognizable and spatially characterized generalization patterns of GNNs. The random graphs offered in this study can be utilized as a useful testbed for graph OOD benchmark, as they allow for the integration of task-specific hode/edge/ graph--evee input features and target outputs.
2. In Section 5.1 we identily strong generalization pattern in OOD scenarios that is strongly correlated with the average node degree of in-distribution (ID) training graphs. This pattern remains consistent across various graph sizes, tasks, and bascline GNN models.
3. In Section 5.2 we demonstrate that having multiple modes in the degree distribution can impede OOD generalization, as it alters the distribution of incoming messages. Therefore, when evaluating generalization on unknown graphs, we suggest that it is important to consider the average node degree for each mode of the degree distribution separately instead of evaluating the distribution as a whole.
4. In Section we propose a multi-module GNN framework designed to leverage multiple update modules to process complex messages aggregated from nodes in far modes of the degree distribution, leading to improved OOD generalization for several inference tasks (Section 5.3
2 Preliminaries
The defining feature of GNNs is the form of neural message passing where vector messages are exchanged between nodes and updated on arbitrary graph structure using neural networks (Gilmer et al. 2017). The message passing operation that underlies variants of GNNs follows a common strategy: at each iteration, every node computes incoming MESSAGES (M) from its local neighborhood, AGGREGATES (4) |them, and UPDATEs (L) its node state h, by
h (++)
= U
(1) h
+ (1,DEE
(2) M [h .n.) 2i.s)
(1)
where Zijj represents the feature embedding vectors for input nodes i, in the node set V and for the edge (i, i) in the edge set E, and M and Ut are arbitrary differentiable functions (ie., neural networks). The iterative scheme relies on reusing and sharing the three main mathematical operations (i.e., MESSAGE, AGGREGATE, and UPDATE) across computational graphs, where functional modules can operate on graphs of varied sizes and structures. Such a flexible design principle allows GNNs to be related to standard neural network layers (Battagii et al. 2018
As an illustrative example, multilayer perceptron (MLP) layers, where each node takes in the sum (AGGREGATE) of weighted inputs (MESSAGEs) from previous layer and passes (UPDATEs) it through fixed nonlinear
2

---

Published in Transactions on Machine Learning Research (07 (07/2023 /023)
spdatt
ubddat
upddate
updste
layer
MLP layer
layer
MLP layer
Figure 1: Overview of the proposed model structures. (a) GNN layer (left) and MLP layer (right) with a fixed nonlinear update/activation /ativvaiiiivin function (gray triangles). nonlinearities (green and orange triangles).
(b) The same layers with two different
activation function, are comparable to GNN layers (Figure [b), although the all-to-all relations between MLP layers are different from the GNN relations defined by the edges. As conceptual extensions from scalar vector-valued inputs, a shared UPDATE function in GNNs can be viewed the same elementary building block a canonical activation function such ReLU in MLPs, in the sense that they all perform nonlinear transformations over aggregated imputs (Figure D From this point of view, the proposed idea of using multiple update functions in GNNs is analogous to the use of multiple activations in MLPs (Figure b).
The motivation behind the use of multiple nonlinearities is to simulate the effect of diverse nonlinear cell properties in the brain (Douglas Martin 1991 Shepherd 2004). Recent work has demonstrated that the task-dependent relative proportion of two distinct cell types allows sample-efficient learning and improves the generalization performance on orientation discrimination tasks (Bordelon & Pehlevan 2022). The fact that optimal mixture of two different cell lypes exists suggests that more than one nonlinear function type might be required for better generalization. The benefits for machine learning this level of collective nonlinear input-output relationships remain unclear, and to the best of our knowledge, this is the first study to characterize the impact of multi-module nonlinear functions and their usefulness in the generalization of GNNs.
3
Experimental Setup
In this section, we present our approach for generating random graphs and analyzing their graph properties through visualization. Then we detail how these random graphs will be applied to specific graph benchmarks.
3.1 Random graph benchmark
Random graph generator. Our goal is to create random graph generator that produce diverse set of graphs with wide range of graph properties. Building previous work (You et al. 2020 have relaxed the constraint of the Watts-Strogatz model to allow for different node degrees before random rewiring. To generate a graph with n nodes and an average node degree of k, we first set the number of edges to L= Then, we construct a ring graph in which each node connected to its L subsequent neighbors. After that, we randomly select e mod n nodes and connect them to their nearest unconnected neighbors. Finally, we randomly rewire all edges with probability p. By repeating this process with different random seeds for each parameter setting, we have generated total of 3,600,000 random graphs (more information is provided in Appendix A.1). This method, although it appears to be single model, can generate variety of graphs that encompass those produced by classic random graph generators like Erdős-Rényi (Erdos et al. 1960), Watts-Strogatz [Watts & Strogatz 1998), Airabési-Albert (Albert & Barabási] 2002 and Harary Harary 1962 models, including ring and complete graphs (Figure A1).
Visualizing structural propertics of random graphs. We next compute six graph propertics for all samples. These include the average shortest distance between nodes (average path length), the fraction of connected triangles in graph (clustering coefficient), the average, mazimum, minimum, and standard
3

---

Published in Transactions on Machine Learning Research (07/2023)
a
avg degree
degree
min degree
training graphs
test graphs
G.
G 6
G. 6
std degree
clustering coeff
avg path length
1000 graphs
P2
Pii randorn graph space
13
sub-sempling
Figure 2: Random and real-world graph benchmarks. (a) Illustaaionn of random graph space where each axis pt represents a graph measure. Inset: Three examples of 100-node graphs (stars) with different connectivity levels. (b) 2D scatter plots showing the distribution of each of the six graph properties across the entire dataset (N-3.6M graphs). (c) Left: The graphs (gray dots) in red circles constitute five distinct sets G:=1s of training graphs, Right: Uniformly sub-sampled test graphs (gray dots). (d) Seven distinct real-world graph benchmarks are displayed with different colors, and they are superimposed on each other. To avoid confusion arising from overlapping distributions, each dataset is independently re-visualized along the orthogonal direction in 2D space.
deviation of node degrees. Each graph is then characterized by six measures, and the value of these variables can be naturally mapped to a point (vector) in a six-dimensional (6D) space where each axis represents one of the variables (Figure 2p). there are a large number of graphs and the points are close to one another, they can form a cluster with distinct components in this space (Figure 2a). To better understand the distribution of sampled graph properties, we use principal component analysis to reduce the 6D space to 2D and visualize them by presenting the recorded measures for each sampled graph color-coded scatter plots (Figure 2b). The visualized results demonstrate the development of the structural properties of the sampled graphs in a low-dimensional space (Figure 2b). The progression in these patterns will be used as a means for evaluating the generalization capabilities of GNNs.
Data split for OOD tasks. This set of large random graphs serves as a test bed for assessing the generalization performance of proposed models in OOD settings. Specifically, we choose five evenly spaced locations 2D scatter plot, shown in Figure 2 We then collect all samples within circle of half-unit radius centered on each position and consider only non-isomorphic graphs. The resulting set Gj of non-isomorphic graphs obtained from the i-th location composes a distinct set of training graphs (Figure ) The number of training samples in each group may differ slightly; thus, we ensure that the sample count is consistently 1,000 across the five groups G==1:5 by providing different input features to the graphs. For the test graphs Grest, we uniformly sub-sample 1,0000 graphs from the entire sample space (N=3.6M) as in Figure 2 (more details in Appendix A.1p. Since the training split occupies a small portion of the sample space compared to the test split, this data split is appropriate for studying OOD generalization in the presence of structure shift. In our experiments for the presented benchmark, we use graphs with small to medium sizes ranging from 16 to 100 nodes.
3.2 Specific tasks for input features and targets
Our random graph dataset can be used for various tasks in graph representation learning simply by assigning node and edge features with corresponding targets to the predefined graph structures. We first consider two specific tasks in this work: (1) an approximate marginal inference task that intractable for general graphs and (2) multi-lask graph theory problem consisting of three node-level and three graph-level prediction tasks. Since these two tasks are defined on the previously created random graphs, manually generate synthetic input fcatures and target outputs for each task.
Marginal inference task. Computing marginal probability distributions of task-relevant variables at each node of a graph is often computationally intractable, and thus relies on approximate methods PPaarl 1988 Wainwright et al. 2003). We follow the sctup of recent work improving message-pant paasgggggpninggggg algorithms by GNNss Yoon al. 2018 Satorras Welling 2021). Specifically, we evaluate the generalization performance in Markov random fields (Ising model) comprising binary variables x E {+1,- (+],, each with associated
4

---

Published in Transactions on Machine Learning Research (07/2023)
bias b, and coupling strength Jız via the following parameterization:
p(x 0) = Z(0)
exp
Σ icV
be +
Σ (K,)ES
Jazzz
(2)
The collective model parameters 0 = (be U (RasEE determine the state of each variable node, given the state of other connected nodes. The number of nodes [V] and the connectivity structure are determined by our random graph benchmark. The Ising model parameter A is sampled from standard normal distribution (N, 1), where the sampled bias {b:} and coupling weight {Jiz} are provided as input node and edge features of GNNs, respectively. For the sake of the targets, we calculate marginal probabilities p(æ;) for each node i E V of small graphs (IV) = 16) using brute-force emumeration, whereas we run a Markov Chain Monte Carlo (MCMC) algorithm, the Gibbs sampler (Goman & Geman 1984). on larger graphs (DVI= =6, 100). We accept the approximate marginals as ground truth targets when the mean absolute error of the estimates from the Gibbs sampler with respect to the counterpart of the binary Hamiltonian Monte Carlo (Pakman & Paninski 2013) falls below 0.02, suggesting that convergence is reached for the MCMC (IPGubbe PHMC 2. eevev S 0.02.
chains:
Graph theory multi-task. We also investigate classical graph theory problems at both the node and graph levels. At the node level, we focus on predicting single-source shortest path lengths, eccentricity, and Laplacian features]] while at the graph level, we aim to determine diameter, spectral radius, and whether the graph is connected. These tasks were initially addressed by Corso et al. (2020), but in this work, we evaluate them on 100-node random graphs that are more diverse in structure and larger in size than in previous studies. As input features, the graph is provided with two lypes of position indices for each node: one-hot vector representing the source for the shortest path task and random scalar uniformly sampled from the range of [0,1].
3.3 Real-world graph benchmark
In order to explore the practical implications of our proposed model framework beyond the random graph benchmark, we have also considered real graph benchmark datasets and visualized their graph properties in the 2D scatter plot (Figure 2t). Our aim is to gain a better understanding of how real-world graphs are distributed and assess whether they accurately represent the full range of graph properties. Interestingly, we discover that most of these datasets have limitations either by sparsely populating or occupying only a small portion of the graph space (Figure 1)). This supports the idea that our random graph benchmnakk is beneficial for studying structural shifts in distribution, rather than solely relying on real-world scenarios. Nevertheless, intend to experiment with the proposed ideas using real-world datasets and then evaluate the outcomes by comparing them with our observations from studying the random graph benchmark. Ultimately, this will enable us to validate the practical utility of our approach.
CLRS algorithmic reasoning tasks. The CLRS benchmark is a recent comprehensive dataset that includes 30 highly complex classical algorithmic reasoning tasks (Veličković et al. 2022 Although most algorithms in CLRS are based on smaller graphe? generated from a single Réndis--enniii model, we have opted to evaluate our proposed methods using CLRS because it leading benchmark for investigating OOD generalization in graph domains. The summary of dataset configuration is provided in Table A3
GOOD: Graph OOD benchmark. GOOD (Gui et al. 2022) is the latest real-world graph OOD benchmark
designed to be challenging by making distinct shifts in input or target distribution (i.e. covariate and concept shifts). It provides 6 graph-level and node-level prediction tasks, covering a range of datasets from molccular graphs and citation networks to colored MNIST datasets. Our focus on graph prediction tasks exclusively (more details in Table A4), as the node-level tasks are all based on a single graph (i.c., transductive setting), which falls outside the scope of our study that aims to explore generalization to unseen graphs across multiple graphs.
L.e. L.X where I. D A is the Laplaciaan matrix and X the node feature vector. 2Th size of the training and validation graphs 16 nodes, while the graphs have 64 nodes.
5

---

Published in Transactions on Machine Learning Research (07 (07/2023)
4 Multi-module GNNs
We next present various strategies for building multi-module GNNs. The GNN architecture that we examine utilizes an encooe-process-deeodee framework (Battaglia et al. 2018) as depicted in F Figure 3a, and the baseline processor is based on the message-passing neural network (MPNN; Gilmer et al. 2017], as outlined in Equation I Additionally, we incorporate the graph attention mechanism (GAT; Veličković et al.) 2018) when appropriate to improve gencralization performance. The update function in the processor is crucial component of the proposed methods and plays vital role in the performance of GNNs. Thus, outline three different strategies for leveraging two update modules within our framework
4.1 Multi-module sigmoid gating
The first approach is to use a sigmoid gating mechanism (Figure 3p, left), where the values of the learned gates determine the utilization of multiple update modules. Specifically, the next hidden state h (1+1) is computed by taking a linear combination of two intermediate node states h and h as follows:
h (++1) = -a; h
(0) (1) + +1 a1-a;;)) 1
a;
(3)
where the two intermediate representations h and h are the outputs of Equation using distinct update functions U1 and U2 respectively. The value of the gating variable ag (1) is obtained from another processor but replacing U with a gating function Φg. which is a neural network with a sigmoid activation for the scalar output.
4.2 Multi-module binary gating
The second approach for updating the node states in our model involves using a binary gating mechanism (Figure b, middle), where a binary decision is made between two different update modules using the Gumbel reparameterizatioo trick (Jang et al.) 2017 Maddison el. al. 2017). Unlike the sigmoid gating method, this approach allows to only applics one specific update module to each node. To accomplish this, we set a." a random variable with a Bernoulli distribution, parameterized by गे E [0, 1], such that a ~ (er(m;;)) (1)). However, this parameterization poses challenge in terms of differentiability, through a in a typical Bernoulli sampling. To overcome this issue, we apply the Gumbel reparameterization trick as follows:
the gradient does not flow
log(TT (1-(((((11((()) ( 9222
(+) a;
T
where (8) (t)
(t) is the output of eg. and at = 1 with probability T.") as the temperature 91,2 ~ Gumbel(0, 1), T.
approaches O. In this way, the next node state h (++1) becomes one of two intermediate representations h[] and h. The binary gating strategy can be considered sitting in the middle of the spectrum among the three strategies we introduce. During the forward pass, binary gating employs discrete sampling similar to the approach described next in multi-module meta-learning, while during the backward pass, computations are carried out on a computational graph defined by multiple modules, akin to sigmoid gating.
4.3 Multi-module meta-learning
The last stralegy is to learn a set of update modules that can be inserted in various combinations at different. nodes within the processor (Figure 30, right). This method significantly different from the previous gating mechanism as the selection of the modules and the updating of their parameters take place at different phases through meta-learning (Schmidhuber 1987 Thrun & Pratt 2012). In particular, the goal is to distribute two
Ttt should be noted that the methods described for modules can easily generalized to multiple modules greater than two. For comprehensive account of the model and optimization hyperparameters, please refer Appendix A.2

---

Published in Transactions on Machine Learning Research (07 (07/202) 2022)
mesiage poosing
sggroe gaing learygiing
indo latoloareng
modile modkeeweght
update module
Figure 3: Multi-module GNNs. (a) Illustration of an snccoe--pocesss-eecooe framework with the emphasis on the processor as passsing neural network. Every node (black dot) computes incoming messages (black arrows), aggregate (vertical line) them, and updates (triangle) its node state. (b) Three different ways of leveraging two update modules (orange and blue triangles): sigmoid gating (left), binary gating (middle), and multi-module meta-learning (right). (c) The multi-module GNN meta-learns set of update modules, and meta-test time, the system only needs to determine which modules should be replaced to make the most accurate predictions based on the observed data.
update modules across all nodes of a graph and search over the set possible structures to find the one that best generalizes in OOD settings. The idea behind this composition is flexibly reuse and recombine a finite number of update modules to ultimately achieve combinatorial generalization (Tenenbaum et al. 2011
Andreas et al. 2016 Ellis et al. 2018 Alet et al. 2018
To be specific, let θ (01. 02. rrest) ) be the weights of update modules U1, 12, and the rest of a multi- GNN. During meta-training, an optimal assignment. A of two modules is determined for each node in training graphs grrain, given a fixed set of model paramcters @. We then update θ using test graphs grest, while maintaining the previously determined module allocation for each graph (Figure 3p). This achieved by using the BounceGrad algorithm (Alet et al., 2018), which alternates between steps of simulated annealing for improving A and gradient descent for optimizing θ to minimize the prodictive loss L:
Σe E2(gee arg min / (garain .A,, A), 0) A.EA
(())
In meta-testing phase, we assume the presence of a small number of final training graphs, Gueit These are not OOD samples, but rather a limited number of ID graphs. In general, meta-learning algorithuss do not share the same task between the meta-tran teatt-training and meea-testing datasets. However, in our approach, we define a task as finding an optimal module assignment for cach individual graph in the meta-training phase, while a new lask in the meta-testing phase is defined finding single module structure that is applicable Queta-test- The objective is search for final optimal assignment of update modules over all possible arrangements A given Gtrain
to all graphs in girain
meta-test with fixed O:
A" = arg min l (gtrain
(mmtaattest: A, A)
(6)
AEA
The generalization performance is then evaluated on OOD test split, using the optimal structure A is important to note that, contrast to the gating mechanism, the type of update function selected for each node no longer influenced by the test dataset at the final evaluation.
5 Results
We now presents a series of controlled experiments on the random graph benchmark to evaluate the generalization capability of GNNs. Our main objective is to pinpoint key factors that can consistently determine the ability of GNNs to generalize well on OOD inference tasks. We then procood examine how the incorporation of multiple update modules within a general GNN framework can enhance their OOD generalization across these tasks.
7

---

Published in Transactions on Machine Learning Research (07 (07/2023 2203)
M--100 a M--36 M--i6
T
node degree
node degine
unde-degire
node tee
nade degine
nodde degine
mode degive
node degies
node degrne
Figure 4: Structural distribution shift and size generalization (a) Generalization performance a 2D subspace as training graphs change from 91 to G5. Blue indicates lower KL divergence (more accurate prediction), while red denotes a higher KL divergence (less accurate prediction). (b) Normalized node degree histograms generated from the training graphs (yellow) and the test graphs with the top 30% prodictive performance (blue). (c) Same as Figure fa except that the model is trained and evaluated on smaller graphs with | = 16. (d-e) Testing on larger graphs, [V] 36 and [V] = 100, respectively. The inset in (e) depicts the magnified region of interest.
5.1 Degree matters in OOD generalization
To gain insight into the predictive performance of GNNs, we first consider the marginal inference task. In this task, the models are trainod on each group 9, with a size of | 100, and are tested on 9test of the same size but with different structures. We use the Kullback-Leibler (KL) divergence as validation metric and present. the results in heat map (Figure 4b). To do this, down-sample and aggregate the test graphs in Figure 2 into coarse resolution of 900 (=30x30) 2D spatial bins, where each bin records the average KL divergence of the graphs within it. For display purpose, we compute the average values in log scale and present them with contrasting colors, with blue indicating a lower KL, divergence (or more accurate predieted marginals) and red indicating the opposite. If GNNs only learned representations of the training graphs, we would expect to see a small blue region around the training set G.. However, all experiments produce a non-trivial vertical band-like pattern translated by the location of G4 (Figure 4h). It noteworthy that this vertical pattern aligns with the distribution of similar average node degrees in 2D scatter plot shown in Figure 2b
To further investigate the role of average node degree in the generalization pattern of GNNs, we generate a normalized histogram of the degrees of every node in the test graphs with the top 30% predictive performance (Figure 4b, blue) and of all training graphs (Figure fp, yellow). The histograms should have the same peak location the band-like pallern results from the average degree of training graphs. We observe that the histogram from the testing graphs is unimodal, and the peak location closely coincides with the counterpart of the training graphs (Figure Ap), indicating that the average node degree is critical fcature in predicting GNNs' generalization capabilities to unseen graphs. It is worth noting that this generalization pattern is not ura only seen in the marginal inference task, but is consistently observed across other tasks and baseline GNN models (Figure A2) This suggests that the pattern is not influenced by the specific task and type of GNN architecture employed.
We next examine the size generalization problem by keeping the size of the training graphs small, with [V] 16, and gradually increasing the size of the test graphs to [V] E {16, 36, 1003. To achieve this, we generate new set of 3.6M random graphs with size of [V] 16, create four sets of training graphs Gi-14, sub-sample Grest, and perform the same marginal inference task as previously described. If the average degree were still a crucial factor, we would expect to see band-like pattern that is not affected by the size of the training and Lesting graphs. Additionally, the corresponding histograms of node degrees should also appear superimposed. Indeed, we find that GNNs trained on G. with a size of | = 16 produce a pattern like a vertical band aligned with the center of 9,, and the normalized histogram from G. provides excellent matches to the peak of the histogram obtained from Grest consistently across the same size (Figure 4D) and larger (Figure [1le) test. graphs. This result, suggests that the graph size may not be fundamental Timiting factor
8

---

Published in Transactions on Machine Learning Research (07/202) 2222)
d
x1
[M|1000
broe the Ohiinee on 61
trace covariance
10
bittar Unitter
20 or
count
100
20
40
6
90
100
20 40
20
100
28 00 50
10
node degree
node degree
node degree
magnitude of message
Figure 5: Effect of bimodal degree distribution on the predictive performance. (a) OOD performance of GNNs when trained on 92 (left), G2&G, (middle), and 94 (right). (b) Node degree histograms. The number of well-predicted graphs decreases substantially (red arrows) when jointly trained on G2&G,, (c) The magnitude and (c) the total variance of message voctors gathered from both the bascline and multi-module GNNs.
for the generalization in GNNs when the average node degree remains invariant across the training and testing distributions.
5.2 Multimode degree distribution as an impediment to OOD generalization
In the previous section, observe that the degree distribution of graphs which GNNs generalize well is characterized by single mode, due to the relatively uniform degrees of the training graphs. However, it is still unclear if the average degree continues to be a significant factor in generalization when training on graphs with highly distinct node degrees. To address this, we create a new training split Gerain by combining two existing sets of 100-node graphs, G2 and G4, resulting
sample size (N=2000) twice larger than before.
In Figure 5h, the test performance of GNNs trained on Grean compared to those trained on G2 and G1, respectively. The generalization pattern now becomes dual band-like, with separation determined by the gap between G2 and G4 (Figure 5k, middle). This is also reflected in the bimodal appearance of the degree histogram (Figure 5p, middle). These results indicate that the average node degree is not the sole determining factor for generalization, but rather it plays role in each mode of the degree distribution when evaluating OOD gencralization for unknown graphs. Notably, the overall predictive performance for graphs within the pattern decreases significantly when trained simultaneously on G2 and G4 compared to when trained individually (Figure 5b-b)) This finding suggests that even within fixed set of graphs, the change in graph composition from singlo-mode to multi-mode degree distribution hinders the OOD generalization of GNNs.
We speculate that the degraded performance might be due to the change in the statistics of aggregated messages from nodes with multi-mode degree distributions. To test this hypothesis, an additional experiment is performed where the aggregated message is initially collected from each node in a graph from the GNN models trained on G2, G1, and Guraiz respectively. This procedure is then repeated for all test graphs to acquire a large message sample. We then compute (1) the magnitude and (2) the spread of messages by computing the trace of the covariance matrix of messages (iguure5-d)) The results reveal that the magnitude of messages significantly increases, and the trace of covariance, which is the total variance of messages, becomes much larger when the baseline model is trained on G2 and G1 simultaneously compared to when it is trained soparately (Figure 5 and Figure A3 The findings indicate that switch from a unimodal to a multimodal degree distribution leads to a corresponding shift in the summary statistics of the message distribution, which may have created difficulties in the training of GNNs. This situation similar to the one where several techniques for network initialization (Glorot & Bengio 2010 He al.) 2015) or normalization
[Iffe & Szegedy 20155 Ba et al., 2016) have been developed maintain the mean or variance of activations during the training of deep neural networks.

---

Published in Transactions on Machine Learning Research (07/2023)
beseline
sigmold goting
goting
mete loamingg
baseline
sigmoid gotng
Einaly
meta leaming
vol lay?
mode
mode
mode
Eagss
0kg
Jagau
Figure 6: Performance of different multi-module GNN strategies on (a-c) marginal inference task and (d-f) graph theory multi-task. Each column is arranged in the following order: a single module baseline, and multi-module GNNs using sigmoid gating, binary gating, and meta-learning, (a,d) Test performance GNNs when trained on G2&94. (b,e) Test KI-divergence loss in log scale (mean + sd) (c.f) Node degree histogram from the test graphs with the top 40% predictive performance. For ease of comparison, the peak/bottom of each mode/ mode/valley in the rightmost column (best model) is highlighted by dashed lines.
Table 1: Test performance of singlemoodle baseline and three different multi-modul GNN strategies over 2 benchmark tasks.
EVALUATION METRIC
METHOD
BASELINE
SIGMOID GATING
BINARY GATING
META LEARNING
MARGINAL INFERENCE
LOSS
(-1.68, -1.28) (1480, 698)
(-1.73, -1.52) (1598, 1099)
(-1.75, -1.38)
(-1.74, -1.51)
# OF NODES & (Mone soon 2)
(1477, 848)
(1707, 1245)
GRAPH THEORY MULTI-TASK
LOSS (VALARY VALLAY
(-2.94, -2.93)
(-3.36, -3.24)
(-3.38, -3.22)
(-3.53, -3.54)
# OF NODES & (Mops. MODE
(1522, 723)
(1714, 1742)
(1853, 1679)
(1825, 1945)
5.3 Multi-module GNN framework for improving OOD generalization
Our multi-module training framework is proposed to address the issue and achieve improved generalization performance. The framework provides complementary update functions for processing those messages and exploring a diverse set of module combinations during training, which could potentially benefit from an ensemble effect in complex scenarios where the distribution of aggregated messages becomes more intricate. The message analysis applied to this now model framework shows that incorporating multiple update modules in a multimodal degree scenario reduces both the magnitude and variance of incoming messages. This reduction remains significant in some cascs, even when comparod the single-module bascline trained on Gz or Go (Figure 5p-d). The results from the previous section and the current analysis lead us to consider these training and test splits a favorable OOD scenario, as it provides ample opportunity for improving OOD performance. Thus, we aim to address how multi-module GNNs are generalized to this OOD setting for the problems of marginal inference and graph theory multi-task, and show that the multi-module framework brings performance gains over the single-module baseline.
Marginal inference task. As presented Figure bh, all variations of multi-module GNNs exhibit a similar dual band-like pattern, resulting from the composition of training data including both G2 and G1. These patterns, however, are more prominent. than that of the single-module baseline (Figure 0a; the outcome of
10

---

Published in Transactions on Machine Learning Research (07/2023)
Table 2: OOD performance on 27 datasets. All numerical results are averages across 3 random runs. Numbers in bold represent the bost results. Additional results and descriptions are in Appondix A.6 and A.7
Dalasel
CLRS
GOOD-CMNIST
GOOD- Motif
GOOD ZINC
Metcic
Accunccy
Accuracy
Accuracy
MAB
Domnin
color
base
size
scaffold
size
Dist. shifs
covatiate
concept
no shift
covariate
concept
to shift
covariate
concept aU.
covariate
conrept
no shift
covariate
concepp
Aggregotion
I1aX
50m
suIa
IBAX
128X
MPNN
35.34
77.57
63.68
86.
0.33U7
0.2186
0.1731
0.6297
0.2185
Sigmold-G
06.68
34.71
66.99
91.90
58.43
87:17
92.57
53.29
72.19
0:3163
0.2182
0.1684
0.6421
0.2452
Binary-G
70.16
74.23
59:22
87.77
02:24
71.91
0.3146
0.2178
0.1719
0.6467
0.2506
Meta-l.
67.38
43.61
77.53
92.61
76.48
87.17
92.45
58.69
733.38
0.3298
0.2285
0.1791
0.0006
0.2603
Dataset
G
GOOD.PCBA
GOOD-HIV 7
Motole
Accuracy
Avernge Precision
ROC-AUC
of tasks
Domain
length
aloo
soalfold
sizn
with the best restalts
Dist. shifs
covoriate
concegt
shif
covurinte
conceggt
shift
cownriate
concogt
oowariste
comcegyt
shift
conceggt
Aggregation
sum
InaX
55331
10A0X
55mm1
1013X
MPNN
S0.74
68:27
90.03
11.71
17.71
26,51
11:74
12.04
68.93
63.00
79.70
57.53
70.90
8/27
8/27
Siguaodd-G
66.79
17.89
27.02
10.55
11.06
65.20
153.4
78.73
69.05
71.02
6/27
RiuoryG
50.83
66.69
00.14
11.84
17.98
25.56
10.87
11.95
64.83
03.82
78.15
67.03
70.00
6/27
19/27
Mota-L
81.26
67.60
90.22
12.13
16.99
25.81
10.80
11.01
67.79
66.91
79.24
06.50
09.47
7/27
the baseline is identical to Figure 5a (middle), but the color range has been adjusted to match that of the multi-module GNNs), indicating that the multi-module framework is more effective in predicting marginals in comparison to the baseline. To quantify this consistency across multi-module strategies, we compute the average KT. divergence loss by projecting the heat map onto the first principal axis, and plot the population level test loss with spline kernel smoothing (Figure Gp). The loss curves are characterized by two local minima (valleys) that correspond to the well-predicted test graphs, but the improved performance by the proposed methods is further supported by the lower KL divergence at each valley of the loss landscapes (Figure (b) and higher peaks at each mode of the degree histograms (Figure c Gb), when compared to the baseline GNN. We note that the superiority is particularly noticeable in the second valley and mode where the mingle-module GNN struggles to generalize (Table D].
Graph theory multi-task. Up until now, all quantitative observations have been derived from the task of estimating marginal probabilities. A subsequent question that arises is whether these findings can be generalized to other tasks. Here, we extend our analysis to the multi-task graph theory problem. The first notable experimental result is that the vertical band-shaped pattern observed in our previous analysis is still present in this multi-task scenario (Figure G1). This supports our hypothosis that the average node degree in each mode of degree distribution should be considered as crucial factor when assessing the generalizabilit of GNNs across different graph benchmark tasks. Secondly, we observe a significant gap in generalization performance between single and multi-module GNNs (Figure 0 which is in stark contrast to the results from the marginal inference task. The higher effectiveness of multi-module GNNs over the baseline (Table suggests that using a multi-module framework could be more beneficial when the task is not computationally complex (i.e. NP-hard) and ground-truth targets can be generated reliably.
Finally, our analysis also reveals that there is a marked difference in performance between GNNs that use a gating mechanism and one that employs meta-learning. Our experimental findings presented Table suggest that the meta-learning approach could be more effective in dealing with the multimodal degree scenario. This raises the question of what makes the meta-learning approach superior even though all strategies use the same number of update modules, and the gating mechanism requires an additional processor for the gating variable. One potential explanation for this improved performance is that the meta-learning approach endows GNNs with multiple learning processes of different phases. Furthermore, our inner-loop optimization does not require changing the weights of the update modules, which sets it apart from most cradicnt-basod meta-learning algorithms (Finn et al. 2017 Nichol ct al. 2018). This distinction enables the GNN to combine multiple modules more flexibly and may contribute to the enhanced learning effect for combinatorial generalization.
11

---

Published in Transactions on Machine Learning Research (07/2023)
5.4 Multi-module GNNs real-world graphs
So far, our experimentation has centered on utilizing our random graph benchmark. However, we will now redirect our attention towards real-world graphs. In Scction 3.3 we explored how rcal-world graphs are represented on 2D scatter plot and found that the majority of real graph benchmarks display a relatively low degree and are characterized by single elongated cluster. To gain a better understanding of the distribution shifts among the training, validation, and testing graphs, we plot their node degree distributions from cach real benchmark dataset and confirm that there is no specific shift in the average degree, except for the CLRS benchmark (Figure A4). This indicates that real-world graphs do not often conform to our multi-mode degree distribution hypothesis, making it difficult to confidently assert that our proposed framework will work well in real-woe wolld situations. Despite this limitation, we evaluate our multi-module GNNs using the CLRS and GOOD benchmarks.
In CLRS, we use random scalars in conjunction with deterministic positional indices as node features to facilitate training and expedite convergence (Veličković et al. 2022 Mahdavi et al. 2023), while we employ original node features and targets from the GOOD benchmark without any modifications. We use two different. aggregators (max or sum) across all tasks and report the best outcome achieved among these two aggregations. Every experiment is repeated three times and averaged over three random seeds. Table 2 illustrates the average performance of the baseline and multi-module GNNs across a variety of real-world graph tasks. Despite some variations in performance across different prediction tasks, our proposed framework surpasses the baseline in 11 additional tasks (with 19 wins compared to 8), demonstrating the practical applicability of our proposed methods and findings. Moreover, we also include two well-established OOD generalization methods, namely invariant risk minimization (IRM) (Arjovsky et al.) 2019) and variance risk extrapolation (VREx) (Krueger et al.) 2021), in Table A6 In this experiment, the bascline, multi-module GNNs, and existing OOD generalization methods perform the best on 6, 13, and 8 tasks, respectively. Although these additional experiments yield mixed results, they continue to provide encouragement by demonstrating the predictive power of multi-module GNNs in specific tasks. Additional details on the tasks, results and analysis
can be found in Appendices A.5 A.8
6 Related Work
OOD generalization on graphs. The field of OOD generalization in graph domains has only recently gained attention from rescarchers. To address Graph OOD problems, four different approaches have been explored. The first. involves using graph augmentation methods to increase the quantity and diversity of
training samples (Zhao et al.) 2021 Park et al. 2021 Wu et al. 2022a Feng et al. 2020 Kong et al. 2022 Liu et al. 2022), including various forms of Mixup (Zhag ct al. 2018 Verma et al. 2019 specifically tailored
to the graph domain. These generate new instances by feature or graph structure interpolation (Verma
et al. 2021 Wang et al. 2021 2020: Han et al. 2022). The second approach aims to create disentangled representations with properties that enhance OOD generalization, such as GNNs with neighborhood routing mechanisms (Ma et al.]
2019: Liu et al. 2020) learnable edge masks (Fan et al. 2022). Self-supervised
contrastive learning (Li et al. 2021 2022a) is also used to eliminate the need for computat computationally expensive graph reconstruction steps. The third strategy considers the structural causal model in model design to
capture the causal relations between input graph data and stable label distributions under distribution shifts
(Sui et al. 2022 Chen et al.) 2022 Bevilacqua et al., 2021 Zhou et al., 2022 A few initial studies have
examined OOD generalization using graphon models (Bevilacqua et al., 2021 Maskey et al. 2022: Zhou et al. 2022). but they rely on the implicit assumption that subgraphs created by a subset of a graph's 's nodes will have unchanged labels, which may not always hold true. Finally, the invariant learning approach aims to leverage invariant relationships between features and labels across different distributions while ignoring variant spurious correlations (Li ct al.) 2022b Wu et al., 2022c Miao et al.) 2022 Wu et al.) 2022b Zhang et al., 2022). This approach treats the cause of distribution shifts as an unknown environmental variable. Within our study, we view the mode of degree distribution as an environmental variable that can pose challenges for generalization, while graph size and other graph measures, except for the average degree, are regarded as invariant features. Consequently, our objective was to enhance generalization specifically with regard to these invariant features, rather than striving for uniform performance across multiple environments.
12

---

Published in Transactions on Machine Learning Research (07/2023)
Update module in GNNs. The update function in GNNs has received relatively less attention from
researchers than the aggregate function (Kipf & Welling 2016 Zaheer et al. 2017: Hamilton et al. 201 7a
Veličković et al., 2018 Murphy et al. 2018 Corso et al., 2020p, although it plays an equally important role in defining the inductive bias GNNs. Previous work on improving the expressive power of the update function can be distinguished by how the past node representations are used when updating themselves. [Hamilton ct al. (2017b) concatenated the output of the base update function with the past node representation, whereas Pham al. (2017) linearly interpolated them to preserve node information from previous rounds of message passing during the update step. In parallel line of work, the gated updates through recurrent neural network (RNN) based architectures have also been proposed to facilitate the learning of deep GNN models (Li et al. 2015 Selsam et al. 2019). These studies generally share the parameters of the update function across nodes and message-passing layers. However, such a single lype of update module could result in restricted expressivity, and the effect of using multiple update modules are not explored in those works.
In a related rescarch direction, Luan et al. (2020) 2022) suggested employing multiple channel filter banks to enrich node representations. This concept aligns with the idea of utilizing multiple message functions within the MPNN framework to generate different types of incoming messages. In this case, the node representation is obtained by combining multiple aggregated messages through a weighted sum, followed by a simple activation function. Both Luan et al. (2020) 2022) and our proposed method employ multiple nonlinear transformations; however, the dissimilarity lies in whether the nonlinear transformation is applied to the message function or the update function. Furthermore, Luan et al. 2020 2022) specifically focuses on improving node classification tasks on heterophilic graphs using a sigmoid gating strategy, whereas our approach avoids limiting itself to particular task types and explores various ways of leveraging multiple modules. While previous approaches have primarily concentrated
mothodologics within single GNN layer, Chien et al. (2021): ; Eliasof et al. (2022) have shifted their focus towards enhancing the quality of the final node representations by adaptively leveraging the outputs of each propagation step, rather than solely relying on the final layer output.
7 Conclusion
In this work, we investigated the influence of the graph structure on the generalization performance of graph neural networks. Specifically, we used random graph generators to examine the impact of the different graph properties, such as degree, clustering coefficient, and path length, which led to useful findings such that OOD gencralization ability of GNN is highly correlated with the average degree of the graphs. To address the challenges posed by multi-mode degree distribution, we proposed a novel GNN architecture with multiple update modules and a meta-learning method to select the optimal aggregation strategy to improve OOD gencralization, whose effectiveness have been validated on synthetic and real-world graph datasets.
Acknowledgments
This work was supported in part by the National Research Foundation of Korea (NRF) under Grant NRF- 101155111006000 and Grant NRF-2021RIFIA 11045300, in part by the Brain Convergence Research Program of the National Research Foundation (NRF) through the Korean Government Ministry of Science and ICT (MSIT) under Grant NRF- PRRF2222M3355D22000022377 in part by Samsung Electronics Co., Ltd.
13

---

Published in Transactions on Machine Learning Research (07 2023))
References
Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, ChriiChristophe Gagnon-Audet, Yoshua Bengio, loannis Mitliagkas, and Irina Rish. Invariance principle meets information bottleneck for out-of-distribution generalization. Advances in Neural Information Processing Systems, 34:3438 3450, 2021.
Réka Albert and Albert-Lászle Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Ferran Alet, Tomás Lozano-Pérez, and Leslie Kaelbling. Modular meta-learning. In Conference on Robot Learning, pp. 856 868, 2018.
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 39 48, 2016.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. ar preprint ar (xXt::907.00890) 2019.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. ar preprinl 1.Xiv1607.064000 2016.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gouzaler Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiw:1806.01900 2018.
Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribciro. Sizc-invariant graph representations for graph classification extrapolations. In International Conference on Machine Learning, pp. 837 851. PMLR, 2021.
Blake Bordelon and Cengiz Pehlevan. Population codes enable learning from few examples by shaping inductive bias. Elife, 11:e78606, 2022.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergleynsst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Mogazine, 34(4):18 42, 2017.
Yongqiang Chen, Yonggang Zhang, Yatao Bian, Han Yang, MA Kaili, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Learning causally invariant representations for out-of-distributio generalization on graphs. Advonces in Neural Information Processing Systems, 95:22131-22145 2022.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In International Conference Learning Representations, 2021.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:1 18:13260-13271 2020.
Rodney J Douglas and KA Martin. A functional microcircuit. for cat visual cortex. The Journal of Physiology- 440(1):735 769, 1991.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru- Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems, pp. 2232, 2015.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Bench- marking graph neural networks. arXie preprint orXiv:2003.0090 2020.
Moshe Eliasof, Eldad Haber, and Eran Treister. pathgen: Learning general graph spatial operators from paths. In International Conference on Machine Learning, pp. 5878-5891, 2022.
Kevin Ellis, Lucas Morales, Mathias Sabl6-Meyer, Armando Solar-Lezama, and Josh Tenenbaum. Learning libraries of subroutines for sourall--guided bayesian program induction. In Advances in Neural Information Processing Systems, volume 31, 2018.
14

---

Published in Transactions on Machine Learning Research (07/2023)
Paul Erdos, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1): 17-60, 1960.
Shaohua. Fan, Xiao Wang, Yanhu Mo, Chuan Shi, and Jian Tang. Debiasing graph neural networks via learning disentangled causal substructure, In Advances in Neural Information Processing Systems, 2022.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random ncural networks for semi-supervised learning on graphs. Advances in Neural Information Processing Systemseural information processing systems, 33:22092 22103, 2020.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning, pp- 1126-1 1135. PMLR, 2017.
Pablo Gainza, Freyr Sverrisson, Frederico Monti, Emanuele Rodola, D Boscaini, MM Bronstein, and BE Correia. Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning. Nature Methods, 17(2):184-192 2020.
Vikas Garg, Stefanic Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pp. 3419 3430. PMLR, 2020.
Stuart Geman and Donald Geman Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on pollern analysis and machine intelligence, (6):721-744) 1984.
Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry, arXiv preprint arXiv:1704.00111, 2017.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS, pp. 249- 256, 2010.
Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. GOOD: A graph out-of-distribution benchmark. In Thirty-siath Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30, 2017a.
William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 2017b.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In International Conference Machine Learning, pp.
PMLR, 2022.
Frank Harary. The maximum connectivity of a graph. Proceedings of the National Academy of Sciences, 48 (7):1142 1146, 1962.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- level performance inagenet classification. In Proceedings of the IEEE international conference computer vision, pp. 1026-1034, 2015.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 33:22118 22133, 2020.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448-456. pmlr, 2015.
Eric Jang, Shixiang Gu, and Ben Poolc. Categorical reparameterization with gumbel-softmax. In International Conference on Learning Representations, 2017.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2016.
15

---

Published in Transactions on Machine Learning Research (07 (203))
Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. Robust optimization as data augmentation for large-scale graphs. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 60 69, 2022.
David Krueger, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrapolation (rex). In International Conference on Machine Learning, pp.
PMLR, 2021.
Haoyang Li, Xin Wang, Ziwei Zhang, Zehuan Yuan, Hang Li, and Wenwu Zhu. Disentangled contrastive learning on graphs. Advances in Neural Information Processing Systems, 34:21872 21884, 2021.
Haoyang Li, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Disentangled graph contrastive learning with independence promotion. IEEE Transactions Knowledge and Data Engineering, 2022a.
Haoyang Li, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning invariant, graph representations for out-of-distribution generalization. In Advances in Newral Information Processing Systems, 2022b.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. Xrviv preprial ar 151 054499, 2015.
Songtao Liu, Rex Ying, Hanze Dong, Lanqing Li, Tingyang Xu, Yu Rong, Peilin Zhao, Junzhou Huang, and Dinghao Wu. Local augmentation for graph neural networks. In International Conference on Machine Learning, pp. 14054 14072. PMLR, 2022.
Yanbei Liu, Xiao Wang, Shu Wu, and Zhitao Xiao. Independence promoted graph discntangled networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4916-4923, 2020.
Chaochao Lu, Yuhuai Wu, José Miguel Hernández-Lobate and Bernhard Schölkopf. Invariant causal representation learning for dutto--disti generalization. In International Conference on Learning Representations, 2021.
Sitao Luan, Mingde Zhao, Chenqing Hua, Kiao-Wen Chang, and Doina Precup. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. arXiv preprint urXiiv2208.088. 2020.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Newral Information Processing Systems, volume 35, pp. 1362-1376 2022.
Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. Disentangled graph convolutional networks. In International Conference on Machine Learning, pp. 4212 1212-4221. PMLR, 2019.
Chris J. Maddison, Andriy Mnih, and Yee whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. In International Conference on Learning Representations, 2017.
Sadegh Mahdavi, Kevin Swersky, Thomas Kipf, Milad Hashemi, Christos Thrampoulidis, and Renjie Liao.
Towards better out-of-distribution generalization of neural algorithmic reasoning tasks. Transactions Machine Learning Research, 2023. ISSN 2835-8856.
Sohir Maskey, Ron Levie, Yunseok Lee, and Gilta Kutyniok. Generalization analysis message passing neural networks on large random graphs. In Advances in Neural Information Processing Systems, 2022.
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pp. 15524-15543, PMLR, 2022.
Christopher Morris, Martin Ritzert, Matthias Foy, William Hamilton, Jan Eric Lensson, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAT Conference Arlificial Inteligence, volume 33, pp. 4602-440 04609, 2019.
16

---

Published in Transactions on Machine Learning Research (07/2023)
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. arXiv preprinl arXiv:2112.0999 2021.
Ryan L Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pooling: Learning deep permutation--inaaiiat functions for variable-size inputs. In International Conference on Learning Representations, 2018.
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. In CoRR, abs/1803.02999, 2018.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Advances in Neural Information Processing Systems, 32, 2019.
Ari Pakman and Liam Paninski. Auxiliary-variable exact hamiltonian monte carlo samplers for binary distributions. In Advances in Neural Information Processing Systems, pp. 2490-2498, 2013.
Hyeonjin Park, Seunghun Lee, Sihyeon Kim, Jinyoung Park, Jisu Jeong, Kyung-Min Kim, Jung- Woo Ha, and Hyunwoo J Kim. Metropolis-hastee data augmentation for graph neural networks. Advances in Neural Information Processing Systems, 34:19010 19020, 2021.
Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.
Trang Pham, Truyen Tran, Dinh Phung, and Svetha Venkatesh. Column networks for collective classification. Tirsty-frrst AAAI Conference on Artificial Intelligence, 2017.
Alvaro Sanchez- Gonzalz, Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Baltaglia. Graph networks as learnable physics engines for inference and control. In International Conference on Machine Learning, pp. 4470 4479. PMLR, 2018.
Alvaro
Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Peter Battaglia. Learning to simulate complex physics with graph networks. In International Conference on Machine Learning, pp. 8459-8468. PMLR, 2020.
Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint :xXi:2003304078 2020.
Victor Garcia Satorras and Max Welling, Neural enhanced belief propagation on factor graphs In International Conference on Artificial Intelligence and Statistics, pp. 685-693. PMLR, 2021.
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.
Jürgen Schmidhuber. Evolutionary principles in self-referential learning, or on learning how to learn: the mela-mela-... hook: PhD thesis, Technische Universität München, 1987.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill. Learning a sat solver from single-bit supervision. In International Conference on Learning Representations, 2019.
Gordon M Shepherd. The synaplic organization of the bruin. Oxford universily press, 2004.
Yongduo Sui, Xiang Wang, Jiancan Wu, Min Lin, Xiangnan He, and Tat-Seng Chua. Causal attention for interpretable and generalizable graph classification. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp- 1696-1705, 2022.
Joshua B Tenenbaum, Charles Kemp, Thomas L Griffiths, and Noah D Goodman. How to grow mind: Statistics, structure, and abstraction. Science, 331 (2022))22799-1225 2011.
Sebastian Thrun and Lorien Pratt. Learning to learn. Springer Science & Business Media, 2012.
17

---

Published in Transactions on Machine Learning Research (07/2023)
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. In International Conference. on Learning Represenlations, 2018.
Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The clrs algorithmic reasoning benchmark. In International Conference on Machine Learnöng, pp. 22084-22102. PMLR, 2022.
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, loannis Mitliagkas, David Lopez-Pas and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states. In International Conference on Machine Learning, pp. 6438-644 6447. PMLR, 2019.
Vikas Verma, Meng Qu, Kenji Kawaguchi, Alex Lamb, Yoshua Bengio, Juho Kannala, and Jian Tang. Graphmix: Improved training of gnns for semi-supervised learning, In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 10024-10032, 2021.
Martin J Wainwright, Tommi S Jaakkola, and Alan S Willsky. Tree-based reparameterization framework for analysis of sun- uun-product and related algorithms. IEEE Transactions on Information Theory, 49(5):
1120-1146, 2003.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi. Nodeaug: Semi-supervised node classification with data augmentation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 207-217, 2020.
Yiwei Wang. Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 2021, pp. 3663 3674, 2021.
Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world 440-442, 1998.
networks. ssmal--oorddnetworsss. Nature, 393(6684):
Lirong Wu, Haitao Lin, Yufei Huang, and Stan Z Li. Knowledge distillation improves graph structure augmentation for graph neural networks. In Advances in Neural Information Processing Systems, 2022a.
Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. In International Conference Learning Represenlations, 2022b.
Yingxin Wu, Xiang Wang, An Zhang, Xiangnan Hc, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. In International Conference on Learning Representations, 2022c.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
KiJung Yoon, Renjic Liao, Yuwen Xiong, Lisa Zhang, Ethan Fetaya, Raquel Urtasun, Richard Zemel, and Xaq Pitkow. Inference in probabilistic graphical models by graph neural networks. In ar preprinl arXiv:1803.07710. 2018.
Jiaxuan You, Jure Leskovec, Kaiming He, and Saining Xie. Graph structure of neural networks. In International Conference on Machine Learning, pp. 10881-10891. PMLR, 2020.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. Advances in Neural Information Processing Systems, 30, 2017.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018.
Zeyang Zhang, Xin Wang, Ziwei Zhang, Haoyang Li, Zhou Qin, and Wenwu Zhu. Dynamic graph neural networks under spatio-temporal distribution shift. In Advances in Neural Information Processing Systems, 2022.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Ncil Shah. Data augmentation for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence conference on artificial intelligence, volume 35, pp. 11025- 2021.
18

---

Published in Transactions on Machine Learning Research (07/2023)
Yangze Zhou, Gitta Kutyniok, and Bruno Ribeiro. OOD link prediction generalization capabilities of message- passing GNNs in larger test graphs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
19

---

Published in Transactions on Machine Learning Research (07 (07/202) 2023)
a
WS graphs
4.5
Ours
graphs
4.--
Hatary graphs
graphs
4.0
Ring graphs
3.5
Complete
Average Path Length
3.5
3.--
3.0
Average Path
2.5
15-
1.5
10-
10
0.2
0.8
0.0
1.0
Clustering Coefficient
Clustering Coefficient
Figure A1: Coverage of random graphs. (a) Graphs sampled from four distinct random graph generators, along with ring and complete graphs having size of [V] 100. (b) Random graphs generated through our method, which covers a more extensive area of the graph space.
A Appendix
A.1 Details for generating random graphs
The relaxed Watts-Strogatz (WS) graphs parameterized by: (1) number of nodes n, (2) average node degree k (real number), and (3)
Here we provide more dotails for how we generated random graphs in Scction 3.1
edge rewiring probability (randomness) p. We search over:
degree E np (2,
randomness np. wwnspacceeeeccc (0, 1,,,,,,,00000 1,300) *+2
40 random seeds
To create more evenly distributed samples, we square and generale 300x300xx0 3,600,000 random graphs in total. This helps to mitigate the significant irregularities in graph properties that occur when p is small. Then we create 2-dimensional square bins on the two principal axes of 2D scatter plot (Figure 2 and sample one graph from each bin, if any. These sampled graphs are then used for testing as described below:
V = 16: 3.6M to 1,282 graphs (# bins = 250x250)
IV| 36: 3.6M to 1,443 graphs (# bins 80x80)
[V| 100: 3.6M to 1,584 graphs (# bins = 50x50)
A.2 Model and optimization hyperparameters
Our baseline GNN processor utilizes the message-passing neural network (MPNN) and integrates the graph attention mechanism when suitable for enhancing generalization performance. While there are numerous types of GNN layers available, we chose MPNN due to its adaptable architecture that consists of different functional modules. Thus, the pertinent message, update, and aggregate functions are determined by one of the fundamental neural network modules, depending on the requirement that the processor is capable of reasonably solving the given task. Apart from these components, we used the same model (Table A1 and optimization (Table A2 hyperparameters as in prior research.
20

---

Published in Transactions on Machine Learning Research (07 (022))
Table A1: Model hyperparameters for synthetic and real-world graph benchmarks.
processor
inesesige Function
update finction
gating finction
aggregation
cinbedding dimensson
layers
Marginal inference
GAT
MLP
GRU
MLP
SHII
64
Graph theory mulitask
MPNN
Linear
GRU
MLP
CLRS benchmaakk
MPNN
MLP
GRU
MLP
128
GOOD beuchmack
MPNN
MLP
MLP
MLP
IDRK, / SILI
300
varied on each task
Table A2: Optimization hyperparameters for synthetic and real-world graph benchmarks.
nott spoch
learsing Edte
aton
qptiuber
weight decay
femctiio
peopagation
compue to metacreting
Graph waliiek
Adam
CLR8 leachund
Adam
0OOD beatlanck
(00CSNNIST)
MABaaiiza's Chos-otinuo/aatoggrei
vicied deinec
Table A3: Summary of CLRS dataset configurations.
# graph nodes train/val
# graphs
Datasct
Graph generator
test
train
val/test
CLRS
64
1000
Brdös-Rényi graphs with fixed p
Table A4: Number of graphs in training, ID validation, ID testing, and OOD testing sets for graph-level tasks in GOOD benchmark.
Dataset
Shift
Train
ID validation ID test
OOD) test.
Train
ID validation
ID test 0OD) test
Scaffold
Size
covariate
24682
4112
4108
26169
4112
3961
GOOD-HIV
concept
15209
3258
10037
14454
3096
10525
no shift.
24676
8225
8226
25676
8225
8226
Dataset
Shift
Train
ID validation
ID test
OOD test
Train
ID validation
ID test
OOD test
Scaffold
Size
covariate
262764
43792
43562
269990
43792
31925
GOOD-PCBA
concept
159158
34105
119821
150121
32168
115205
shift
262737
87586
87586
262757
87586
87586
Dataset
Shift
Train
ID validation
ID test
OOD lest.
Train
ID validation
ID test
OOD test
Scaffold
Size
covariate
149674
24945
24946
161893
24945
17402
GOOD-ZINC
concept
101867
21828
60393
89418
19161
70306
shift.
149673
49891
49891
196733
49891
49891
Dataset
Shift
Train
ID validation
ID
OOD test
Train
ID validation
ID test
OOD test
Length
covariate
24744
5301
17490
GOOD-S8T2
concept.
27270
5843
15944
no shift.
42025
14008
14009
Datasct
Shift
Train
ID validation
ID test
OOD test
Train validation
ID test
OOD test
Color
covariate
42000
7000
7000
GOOD-CMNIST
concept 29400
6300
14000
no shift
42000
14000
14000
Dataset
Shift
Train
ID validation
II test
OOD test
Train
validation
ID test
OOD test
Base
Size
covariate
18000
3000
3000
18000
3000
3000
GOOD-Motif
concept.
12600
2700
6000
12600
2700
6000
no shin.
18000
6000
6000
18000
6000
6000
21

---

Published in Transactions on Machine Learning Research (07 2022))
Baseline
GCN
GIN
GraphSAGE
PNA
(avg, test loss)
-1.629
-1.636
-1.638
-1.657
10
-5
-2
-40
Figure A2: Generalization pattern in graph theory multitask observed from other GNN baseline models, when trained on G2-
A.3 Effect of GNN processors on generalization patterns
To explore how other variants of GNNs generalize, we conducted an additional graph thoory multitask experiment by training them on G2. The results depicted in Figure [2 indicate that GNNs' ability to generalize is consistently correlated with the average degree of the graphs, regardless of whether GCN, GIN, GraphSAGE, or PNA is used:
GCN
Kipf Welling 2016
h2
max VI(())IN(u)
h ("w())
(7)
GIN
Xu et al.
2019
h o
(1+ + max h weN(o)
(8)
GraphSAGE (Hamilton et al.
2017a
h'
W, h(9
W2 (E)
max h())
(9)
PPNA
Corso et al. 2020
h,
MLP (1) h(4)
(10)
(EA((w)
where
S(D, a 1)
(11)
5(D.
max
min
scalers
aggregators
22

---

Published in Transactions on Machine Learning Research (07 (07/2023)
x10
3.0
2
baseline GNN trained on
6.
3
baseline GNN trained on
{92. Gc]
2.5
4
sigmold-gatinnn GNN trained on
trace of covariance
binary-gating GNN trained on
(62. Gc}
meta- Preta-learning trained on
(9..9c)
2.0
count
2
0.5
10
10
10"
10
①
magnitude of message
Figure A3: Message analysis from graph theory multitask.
A.4 BOUNCEGRAD algorithm
When implementing the meta-learning method, it is essential to employ algorithm that effectively find approximately optimal update module assignment vectors. In this work, we implement modified version of the BounceGrad algorithm (Alet et al.) 2018) for the graph structured data, which takes the following inputs: a sample space A of update modulc assignments, a set of graphs G, a set of network weights θ, a learning rale y, a uemperature T, and rate of change lemperature a E 1). As the paper (Alet et al. 2018), we use simulated annealing, local search algorithm involving stochasticity.
The algorithm begins with initializing the Simulated Anncaling rumning accuracy rate (SA,) and factor (SA,). In the main loop, the temperature is updated by the ScheduleTems procedure based on the current step, the rate of change in temperature a, the SA,, and the SA,. Next, the BOUNCE procedure is called for updating the assignment A. During this step, new assignments ''' are proposed for graphs in the mini-batch, and their performance are compared to that the current assignment using Accept function. The new assignment is accepted when it decreases the loss on the task or, with some probability based on current temperature, even if it does not. Finally, we call the Grad using the assignment to update the network parameters O via the backpropagation algorithm.
To explore the optimal structure of the modules and adapt to new graphs, run 1000 iterations of meta-test phases for small number of final training graphs, dcnoted as Giran meta-testt During the meta-testing phase, we rely on the Bounce procedure given a fixed O. This approach enables us to find the optimal assignment of the update modules for fho- meta-tes test graphs.
23

---

Published in Transactions on Machine Learning Research (07 (072))23)
Algorithm BounceGrad
1: procedure BOUNCEGRAD(A, Gtroin Geest SA,, SA,,7,
2: Initialize SA,, SA, for <- to epoch max do
T' SCIEDCLETEMP(( s/epoch a, SA,, SA,)
A I:N, SA, S BOUNCE(AimENN Pi T, A, O,SA,,SAy) + f GRAD(O, i Piest m1)
Algorithm ScheduleTemp
1: procedure SCHEDULETEMPP(, step, a, SA,,
2: ACC +- exp (-5 step)
if S < ACC then
T
else
6: T < T-T/o
return T
Algorithm Bounce
procedure BOUNCE((A=I:.N P 1i
T, A, S,S,,,SA))
for 1 to N do
A/, PROPOSE&(A, θ)
4:
l' t e(glrain: Az. O)
< (Girain A,, Q)
f + min(10 -2, ?,SA,/SAf)
if Accept(E (, then A, s Ai if l' >= f then
10:
SA,- + (1 1--f) SSA + I
11:
SA, < (1 (1- SA, +
12:
else
13:
SA, (1 - [1-f)xx SA, + SA, + (1 -1-ff SA,
14:
15:
return AJ, SA,
Algorithm Accept
1: procedure ACCEPT(E, (,,
2: return < or rand(0, 1) < (xp(((-F)/11)
24

---

Published in Transactions on Machine Learning Research (07 (07/2023) /223)
Algorithm 5 Grad
1: procedure GRAD(O, I:N Piest 17
2:
A =
for f- 1 do
(I,y) rand elt (Glest)
A A VeL(Ajo(z))))
- 7/A
7: return θ
def accept (loss_ (loss_prev. prev, losa_new *""Decide whether accept proposal based losa. .**
delta loss_new lose_prev
if less_new loss_prev mp.randon. up. ex.exp(-dee) d-delta return True
else: return False
def schedule_tempps_22 s_f, t):
"""Update temperature adaptively using geonetric progression. acc (-5 epoch max max_epoch)
if s_r / s_f acc:
t *= alpha
else: /- alphs return
def update_ppaaneeeeeeeeepppp par.metere s_f, acceptance):
n Updatee parameters based the success ***
a_r acceptance True (1.0 s_r ff (1.0 +efftt return s.r, s_
8_ (1.0
def bounce (assignment__ree """Expiore more optimal update module structures using simulated annealing. x, y train_data.x, train_data.y assignment_new = outi, out2 model (x, a_prev), model(x, a_new) Evaluate the current and proposed structures.
train_data, т, s.r. s.f, 1)
Propose new update module structure.
if accept (loss (out1, y), lost2, y), T):
if loss (out2, y) >= loss (out1, y):
of ppratee.prraeteersss... e_f, f, True)
else:
assignment sr,, assigament_nevt s_r. 8_1
assignnent.pree
paraateeppraneterae.... s_f, False)
def graeinmmgm,, test_data):
"""Update model weights based on the test graphs. x, y test_data.x, test_data.y out model (x, assignment) lost so.ut.y..bb.eeee backvard
# Initialize update module assignment.
assignment up. randon. ([oice((0, 1], size=(n, nun_nodes))
# Loop over minibatches for train_data, test_data in
test_loader):
T Baaedule_temp(s_r_ s_f, T) # Update SA temperature.
Explore alternative module atructures (bounce) and assess their effectiveness (grad).
assignment, s_r, e_ bounce (assignment, patin,atta, т, s_r, s.f, min(0.01, / 8_f)) (aasiggmmn,,, test_data)
25

---

Published in Transactions on Machine Learning Research (07/2022 0072)
node-dagee
Figure A4: Normalized node degree histograms from CLRS and GOOD benchmarks.
A.5 Details for real-world graph benchmark
The configurations for the CLRS and GOOD benchmark datasets are presented in Tables A3 and A4 respectively. Additionally, the average node degree distributions are compared among the training, validation, and testing graphs for each real-world graph benchmark (Figure A4). It is worth noting that the structural properties of most benchmark graphs not clearly distinguishable, shown in Figure 21.
A.6 Complete numerical results for CLRS benchmark
Prior rescarch (Mahdavi al.) 2023) has boen referred create our experimental sctup, which suggests that disabling hint trajectories can lead improved performance. When hints are disabled, two algorithms from the same category exhibit. identical behavior. As result, the number of tasks has been reduced from 30 to
26

---

Published in Transactions on Machine Learning Research (07 (07/2023)
24 by choosing one from each algorithmic category. To expedite convergence and facilitate training, random scalars in conjunction with deterministic positional indices as node features. Our experiments are repeated three times, and the results are averaged over three random seeds. Table 2 presents the average test scores for all 24 algorithmic tasks, while Table A5 provides the mean and standard deviation for individual tasks.
Table A5: Complete lest accuracy (%) of MPNN and three multi-module GNN strategies on CLRS benchmark over 24 algorithmic reasoning tasks.
hugo
MPNN
Sigmoid-G
Binary-G
Meta-L
Activity Selector
69.11 + 14.67
65.68 + 13.56
87.74 + 4.90
71.02 + 1.69
Articulation Points
95.82 + 0.58
96.41 + 0.79
97.01 + 0.38
96.75 + 0.48
Bellman-Ford
98.60 = 0.33
98.70 + 0.39
98.36 = 0.33
71.02 + 0.00
BFS
99.97 0.03
99.93 + 0.03
99.98 + 0.03
100.00 + 0.00
Binary Search
92.46 1.56
91.88 + 1.12
93.88 + 2.13
89.79 + 2.13
Bridges
59.51 + 11.75
56.67 + 4.52
87.36 + 6.02
75.41 + 8.60
DAG Shortest Paths
99.22 0.27
99.28 0.20
99.54 = 0.20
99.17 = 0.08
DFS
25.46 1.27
24.66 + 2.83
27.65 + 1.67
25.63 + 2.75
Find Max. Subarray
28.74 = 5.94
24.48 + 1.82
27.05 + 1.29
23.76 + 2.54
Floyd-Warshal
31.28 + 1.55
29.29 + 1.02
31.18 1.49
27.78 + 0.63
Graham Scan
99.00 + 0.07
99.04 + 0.31
98.90 + 0.12
98.80 + 0.52
LCS Length
58.45 1.55
58.92 + 1.30
60.08 + 2.29
58.53 + 0.93
Matrix Chain Order
81.13 3.99
77.10 + 3.92
81.55 + 5.61
79.74 + 2.81
Minimum
99.64 = 0.20
99.59 0.11
99.40 = 0.10
99.04 + 0.30
MST-Kruskal
59.82 1.13
61.65 1.95
61.71 3.03
59.49 + 0.87
MST-Prim
83.28 = 0.71
82.88 + 1.37
82.88 + 1.59
79.67 + 1.54
Naïve String Match
10.69 + 1.95
10.71 4.04
21.70 + 8.88
5.31 + 1.40
Optimal BST
73.92 = 2.10
73.20 1.29
1
70.14 2.35
Quickselect
0.00 = 0.00
2.1 4.34
8.61 8.21
0.00 0.00
Quicksort
8.15 2.74
8.38 + 4.42
12.68 + 2.45
19.06 = 4.92
Segments Intersoct
98.52 + 0.10
98.47 0.29
98.52 + 0.16
98.18 0.11
SCC
72.49 0.60
73.81 + 1.18
71.26 1.30
72.79 1 0.56
Task Scheduling
83.98 = 0.82
83.33 + 0.47
83.87 = 0.40
83.50 - 0.46
Topological Sort
83.92 = 1.21
83.85 + 0.65
81.65 + 2.81
85.08 + 1.66
Overall average
67.22
66.68
70.16
67.38
27

---

Published in Transactions on Machine Learning Research (07 (07/2023)
A.7 Complete numerical results for Graph Ditt----Distiitttion (GOOD) benchmark
The GOOD benchmark comprises several real-world graph datasets that exhibit unique domain shifts. It provides covariate and concept shifts by altering the imput distributions and target distribution, respectively, between the training and testing data. Each dataset contains domain-specific shifts, such as graph size and scaffold in molecular graphs, that cover both types of distribution shifts. Some datasets have no shift, representing the original dataset. Our study focuses solely on graph prediction tasks, as the node-level tasks are based on single graph (i.e., transductive setting), which is beyond the scope of our research aimed investigating the ability to generalize to unseen graphs across multiple graphs. The tables A6 A16 below provide in information shift from the MPNN baseline, multi-module GNNs, and existing OOD methods (TRM and VREx). For more detailed information, please refer to Gui et al. (2022
the mean and standard deviation of OOD generalization performance for each domain
Table A6: OOD performance on 27 datasets. All numerical results are averages across 3 random runs.
Numbers in bold represent the best results.
CLRS
GOOD-CMNISTE
GOOD Moti-Motif
GOOD ZINC
Metric
Accuracy
Accuracy
Accuracy
MAE
Dist. shifs
covntiate
conrept
no shift
covariate
concept
no shift
covariate
concept
commriate 10RX
connept
no shift
covariate
concept
Aggregation
MPNN
67.22
35.31
77.57
92.93
63.68
66.91
92.53
57.32
72.87
0.3311
0.2186
0.1731
0.6297
0,2188
Sipmoid-G
34.71
66.59
0.2182
0.1684
Binary-G
70.16
19.22
71.23
02.56
59.22
87.77
92.52
52:21
71.91
0.31
0.2178
0.1719
0.6167
0,2506
Meta-L
0.2225
IRM
41.97
76.45
92.61
68.07
87:33
92.48
56.14
73.61
0.3088
0.2207
0.1717
0.6338
0.2480
VREx
45.58
73.53
92.80
73.73
87.69
92.53
59.72
74.07
0.3158
0.2182
0.1723
0,6300
0.2429
Dataset
GOOD SST2
GOOD PCBA 1
GOOD HIV
Metciic
Accuracy length
Aveenge Precision
ROC AUC
of tasies
Damaia
seadoold
scallold
with best rostlts
Dist.
covaclate
concept
covoriate
conceejt
coveriate
concept
covariate
colceopt
covarinte
concept 100X
Aggreatton
sum
mna
sum
51223
5tmn
10AX
MPNN
S0.74
68.27
17.71
26.51
11.74
79.70
57.53
70.90
6:27
6/27
Signood-CC
11.70
17.59
27.02
11.56
18.73
71.82
4,27
B
50.83
66.60
00.14
11.54
17.98
25.56
10.87
11.98
64.83
63.82
70.15
57.03
70:00
5/27
13/27
L
81.26
67.60
90.22
12.13
18.99
25.81
10.50
67.79
65.91
79.24
55.50
69.47
6/27
VREs
70.79
78.96
67.30
00.00
90.14
12.24
11.52
16.25
26.91
26.31
11:75
11.05
11.95
65.07
68.02
63.25
79.97
T8.42
56.73
70.30
6/25
8/26
Table A7: Performance on GOOD-CMNIST with color domain
Accuracy
Aggrogation
MPNN
Sigmoid-G
Binary-G
Meta-L
IRM
VREx
covariate concept
35.34 + 15.01
34.71
11.14
49.22 + 3.85
43.61
29.35
41.97 + 18.06
45.58 12.32
sum
77.57 0.72
66.99
6.78
74.23 0.74
77.53 + 0.61
76.45 1.38
73.83 + 4.61
no shift
sum
92.93 + 0.11
91.90 + 0.83
92.56 + 0.09
92.61 + 0.15
92.61 0.46
92.80 + 0.17
28

---

Published in Transactions on Machine Learning Research (07/2023)
Table A8: Performance on GOOD-Motti with base domain
Accuracy
Aggregation
MPNN
Sigmoid-G
Binary-G
Meta-L
IRM
VREx
covariate
63.68 + 2.50
58.43 0.76
59.22 + 1.75
76.48 3.61
68.07 + 2.48
73.73 + 6,48
concept
8Um
86.94 + 0.69
87.17 = 0.62
87.77 1.14
87.17 + 1.62
87.33 0.25
87.69 1.0
Table A9: Performance on GOOD-Motif with size domain
Accuracy
Aggregation
MPNN
Sigmoid-G
Binary-G
Meta-L
IRM
VREx
covariate concept
57.32 + 4.55
53.29 + 4.06
52.24 + 2.76
58.69
12.37
56.14 - 4.57
59.72 + 3.78
sum
72.87 0.88
72.19 2.45
71.91 + 0.34
73.38
2.43
73.61
1.94
74.07
2.M
no shift
sum
92.53 + 0.01
92.57 + 0.00
92.52 + 0.08
92.45 + 0.08
92.48 + 0.07
92.53 + 0.04
Table A10: Performance on GOOD-ZINC with scaffold domain
MAE
Aggregation
MPNN
Sigmuid
Binary G
Meta-L.
IRM
VREx
covariate
max
0.3300 + 0.0076
0.3163
0.0041
0.3146
0.0043
0.3158
0.0034
concept
max
0,2186 + 0.0004
0.2182
0.0036
0.2178
0.0016
0.2285
0.0041
0,2207 + 0.0001
0.2182
0.0001
shift
0.1731 + 0.0020
0.1684 0.0027
0.1719 + 0.0019
0.1791 0.0010
0.1711 + 0.0001
0.1723
0.00L1
Table All: Performance GOOD-ZING with size domain
Aggregation
MPNN
Sigmoid-G
Binary-G
Meta-L
IRM
VREx
covariate
max
0.6297 + 0.0144
0.6421 + 0.0026
0.6467 + 0.0045
0.6696 + 0.0107 0.6338 + 0.0092
0.6300 +: 0.0001
concept
max
0.2488 0.0040
0.2452 + 0.0027
0,2506 + 0.0030
0.2603 + 0.0079 0.2480 + 0.0034
0.2429 + 0.0001
Table A12: Performance on GOOD-SST2 with length domain
Accuracy
Aggregation
MPNN
Sigmoid-G
Binary-G
Meta-T.
IRM
VRFx
covariate concept
8um
80.74 0.44
80.45 + 0.87
80.83
1.28
81.26
1.19
79.79
0.56
78.98
2.99
68.27 +:2 1.76
65.79 + 0.64
66.69 + 0.95
67.60 + 1.86
65.82 4 0.00
67.30 +: 0.40
no shift.
90.03 0.18
90.16 0.14
90.14 0.01
90.22 0.18
90.09
0.00
90.14 + 0.08
Table A13: Performance on GOOD-PCBA with scaffold domain
AP
Aggregation
MPNN
Sigmoid-G
Binary-G
Meta-L
IRM
VREx
covariate
11.71 = 0.09
11.70
0.35
11.84 i 0.26
12.13 + 0.07
11.92 + 0.22
12.24 + 0.16
concept no shift
sum
17.71 + 0.55
17.89
0.54
17.98 + 1.08
16.99 + 0.71
17.41
0.63
16.25
1.21
sum
26.51 = 0.96
27.02 + 0.50
25.56 + 1.28
25.81 + 0.51
26.31 + 0.68
26.91 = 0.87
Table A14: Performance on GOOD-PCBA with size domain
AP
Aggregation
MPNN
Sigmoid-G
Binary-G
Meta-L
IRM
VREx
covariate
max
11.74 + 0.40
10.95 0.30
10.87 + 0.38
10.80 + 0.31
11.64 + 0.00
11.75 + 0.64
concept
12.04 4 0.31
11.56 0.63
11.98 + 0.29
11.11 + 0.34
11.65 10.68
11.95 + 0.30
Table A15: Performance on GOOD-HIV with scaffold domain
ROC-AUC
Aggregation
MPNN
Sigmoid-G
Binary-G
Meta-I,
IRM
VREx
covariate
concept max
68.93 + 2.15
65.20 + 2.65
64.83 t 2.17
67.79 + 1.97
65.07 + 1.60
68.02 + 2.51
63.09 + 3.11
63.54 + 1.59
63.82 + 1.31
65.91 - 0.83
62.15 + 1.73
63.23 + 3.99
no shift
max
79.70 + 0.46
78.73 + 0.27
79.15 0.31
79.24 = 1.11
78.42 + 0.74
79.97 0.97
Table A16: Performance on GOOD-HIV with size domain
ROC-AUG
Aggregation
MPNN
Sigmoid-G
Binary-G
Meta-L
IRM
VREx
covariate concept
57.53 + 1.89
59.05 + 0.92
57.03 + 7.18
55.50 + 0.33
62.22 + 5.02
56.73 + 1.47
max
70.90 2.39
71.32 + 1.12
70.00 0.73
69.47 0.52
70.27
2.04
70.20 0.75
29

---

Published in Transactions on Machine Learning Research (07 (07/202) /023)
***
3.08
0.00
with orrolie
Inbabbyybol Deedy
mutddt Eandy Dandy
0.04
0.04
0.02
0.2
20
Degroe
100
20
Dogros
60
80 100
Figure A5: The degree distribution of high-performing test graphs when GNNs are trained on 92 is analyzed by fitting a Mixture of Gaussians. The resulting curves are presented in varying colors corresponding to the type of GNNs used. The curves on the left indicate rejection of the null hypothesis at a 5% significance level according to two-sample F-test. On the right, is shown that the variance of the node degree distributions obtained by sataallearnnn--aseee GNNs differs from the baseline.
Table A17: p-value and test. decision for two-sample F-test for each model configuration.
Two-sample
sigmoid gating
sigmoid-gating binary-gating (2 modules)
binary-gating
meta-learning (3 modules)
meta-learning
F-test
(2 modules)
(3 modules)
(2 modules)
(3 modules)
p-value
0.47
1.0
0.48
0.48 True
1. 1.66e-29
6.69e-13 13
H :2 = o
True
True
True
False
False
A.8 Effect of module counts and few-shot OOD samples generalization ability
All experiments in this paper were based on GNNs consisting of two update functions. To explore the impact of an additional update function and exposure to few-shol OOD samples, we trained the multi-module GNNs on G2 in graph theory multitask problem. Our results indicate that although the overall prediction accuracy remained unchanged, the generalization range could become wider. Consequently, we used a two-sample F-test to evaluate there was a statistically significant difference the variance the average degree histogram between the single-module GNN baseline and the multi-module GNN histogram. Table A17 confirms that only the meta-learning- baaed GNN model increases the generalization scope, possibly because of the mela-testing phase's s ability to reuse and restructure module assigument to adapt new environment. This finding suggests that molti-module GNNs with meta-learning more advantageous when given access to few instances from novel environment, even if they do not match the OOD setting completely.
30


Reviews:
[{"review_id": "cgAery2QOl", "reviewer": "Reviewer_8Lyz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The papers combine multiple update modules and meta-learning method for neural message passing to solve the challenge when multi-mode degree distribution is involved. The performance of the proposed model is verified by both synthetic and real-world data.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper is concerned with how the graph structure influences the generalization of GNNs. OOD of GNNs is considered and is verified to have high correlation with the average degree of graphs by the random graph generators. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.\tWill other topological properties (such as higher-order topology from the populated graph) of graph besides the notion from network science affect the OOD and predictive performance of the GNNs and how?\n2.\tWhat is the benefit of using Gumbel reparameterization trick?\n3.\tDespite the empirical study, is there any theoretical justification and guarantee for the performance improvement of introducing multi-module meta-learning?", "broader_impact_concerns": "NO", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5kRWACyrrU", "reviewer": "Reviewer_9i1U", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. According to Section 3.1 and Figure 2, a new random graph benchmark covers much more space compared to other established graph datasets (at least in terms of the structural graph characteristics discussed in this work). This approach to sample graphs might be particularly interesting for the research areas focused on the methods for generating unique graphs with diverse structural properties;\n2. In Section 4, the authors propose various different methods to design multi-module MPNNs, including binary / sigmoid gating and meta-learning technique, that share the same motivation about how it may be useful to have different update functions in MPNN. This allows one to choose the architecture for their needs, which is especially useful since the most complex architectures do not always show the best performance, as shown in Section 5.4;\n3. In Section 5.1, the proposed method of investigating the impact of each structural property by comparing the directions of changes in the structural properties of nodes with the direction of changes in the predictive performance on the constructed 2D plane seems clever and intuitive;\n4. As shown in Section 5, the importance of average node degree of the input graphs is proved by consistent results of numerous experiments. In particular, the authors consider synthetic data from the proposed random graph generator and CLRS benchmark, as well as natural graphs from GOOD benchmark; the investigated problems include marginal inference, graph theory multi-task prediction, standard graph classification, and algorithmic reasoning.\n\n## Weaknesses\n1. In Section 3.2, it remains unclear how the proposed method for generating the input features on nodes and edges for making marginal inference and solving graph theory affects the main conclusions of the empirical study about the importance of average node degree. In other words, do these claims hold for any other approach to generate features on nodes and edges, and whether this question is important to discuss at all;\n2. In Section 4.3, the description of a multi-module meta-learning is somewhat hard to follow, especially with regard to the data used and the combination of loss functions applied. As a suggestion, the authors may provide a pseudo-code for their meta-learning algorithm that clearly describes the alternating procedure to obtain the optimal assignment of update module;\n3. As shown in Section 5.4, there may be notable variations in the performance of the proposed meta-learning framework across different prediction tasks on real-world datasets, and this does not allow one to draw clear conclusions as to whether it is really worth using a complex procedure for constructing update modules instead of simple methods like sigmoid or binary gating.\n4. According to Figure A4, the structural properties of most real-world datasets do not reveal the same transition of average node degree across train, validation, test subsets as simulated by the proposed random graph benchmark. It means that there is no such distributional shift for which the multi-module MPNN architecture has been proposed. This fact may explain the inconsistent results with high variation on real-world datasets. For the sake of fairness, it should be noted that the authors discuss the limitations of the proposed random graph benchmark in Section 5.4. In particular, they mention that while it allows to cover a multi-modal distribution of graphs in terms of their structural properties, it does not necessarily reproduce the same properties as in real-world datasets.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work, the authors investigate how structural properties of graphs affect the OOD generalization of GNNs. Using a novel random graph benchmark, they find that the average node degree is a crucial factor for scaling to OOD graphs. To overcome the performance drops caused by the distributional shift in this structural property, they design a multi-module MPNN framework that combines various update functions for node representations. The experimental results show that the proposed framework improves the predictive performance on most considered problems of graph learning.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. If I understand correctly, the assignment of yellow and blue colors in the caption of Figure 4 should be swapped;\n2. If possible, I suggest to add a pseudocode (or more compact description) that clearly explains how the proposed meta-learning procedure works.", "broader_impact_concerns": "I do not have any concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8CjaF6TIto", "reviewer": "Reviewer_QihW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is well motivated\n2. The authors propose both qualitative (i.e., analyses), quantitative (empirical comparison), and software/date (the proposed framework and dataset) contributions.\n3. The results show the importance and empirical contribution of using several node aggregation rules and the influence of the mean node degree on performance.\n\nWeaknesses:\n\n1. The experimental comparisons are lacking. While comparing the proposed method to a baseline MPNN, it is also essential to compare it with other OOD GNN works.\n2. The authors propose to use multiple aggregation rules. It seems to me that the authors focus on the activation part of the network. I would like to ask the authors if they can relate to the use of various (whether pre defined or learned) node propagation rules. Some examples to such ideas are present in [1],[2],[3],[4]. \n3. The authors widely discuss the effect of different motifs and underlying structures found in the input graphs and their influence on the generalization of GNNs. In this context, can the authors elaborate on the relation to recent positional/structural encoding methods? (PE/SE). Some examples are [5],[6].\n\n[1] Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks\n\n[2] Revisiting heterophily for graph neural networks\n\n[3] Adaptive Universal Generalized PageRank Graph Neural Network\n\n[4] pathGCN: Learning General Graph Spatial Operators from Paths\n\n[5] GRAPH NEURAL NETWORKS WITH LEARNABLE STRUCTURAL AND POSITIONAL REPRESENTATIONS\n\n[6] Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors inspect the behavior of GNNs under out of distribution (OOD) settings, focusing on the generalization ability of GNNs.\n\nTo do so, the authors propose two main steps:\n1. Generate a large random graph dataset with varying parameters, such that graphs with a large range of mean degree are obtained and with different motifs. The authors use this dataset to evaluate the generalization of GNNs.\n\n2. The authors propose a multi-module GNN framework that is supposed to capture different node feature aggregation rules, based on their hypothesis and observation that in cases where underlying graph properties may vary between train and inference stages (e.g., the mean node degree), using a single aggregation rule results in worse performance.\n\nThe authors evaluate their method on several synthetic and real-world datasets, where they compare the performance of different variants of their method with a standard MPNN.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see my questions in the weaknesses section in my review. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qGd8C5qP0H", "reviewer": "Reviewer_JK6m", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\ni) The experiments with the random graph generator are comprehensive.\n\nii) The figures are elegant and informative.\n\n\n**Weakness**\n\ni) The discussion regarding the influence of average node degree seems to be limited and uninteresting.\n\nii) The proposed multi-module network is not new.\n\niii) The experimental improvements are limited and no experimental comparison with existing OOD methods on graphs.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies OOD generalization on graphs under graph size and structural distribution shifts. The authors present a random graph generator to study the effects of different graph properties to the OOD generalization of GNNs, and find the average node degree is the key factor. They propose multi module GNNs to handle multiple degree modes and provide certain experiments to show the effectiveness of their proposal.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "While I acknowledge the considerable effort put into the experiments, I believe there is room for improvement in the work, specifically in addressing the following weaknesses:\n\ni) The discussions regarding the influence of average node degree and the Multimode degree distribution are limited:\n- The phenomena that GNNs only generalize well to graphs that have similar degree distributions as the training data is straightforward and not interesting. It is believed that the other graph properties can also have the same effects. In other words, one could also count other graph properties such as graph size, clustering coefficients, and also find similar phenomena. \n\n- Besides, the observation of average node degree is limited to synthetic datasets.\n\n- Although the discussion regarding 5.2 seems to be interesting, it is unclear whether the OOD performance degeneration is caused by the shifts of average degrees or the existence of multimode degree distribution. And it is also unclear whether the same phenomenon exists in real world applications.\n\nii) The proposed multi-module network is not new. Some existing works such as PNA also adopts multiple aggregation functions. It is also unclear how multi module could resolve multimodal degree issue.\n\niii) The experiments are limited:\n- First, in Figure 6, it seems none of the gating choices consistently outperform vanilla MPNN at all degree distributions. For example, in Figure 6e, the vanilla baseline performs better than the meta learning one at the largest degree.\n\n- The performances of MPNN at Table 2 on GOOD benchmark have huge gaps than those reported by GOOD benchmark. The proposed multi-module method can not always outperform MPNNs. \n\n- None of the previous OOD generalization methods are compared in experiments.\n\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission tackles the important and timely problem of OOD generalisation of graph neural networks. The authors have performed several thorough controlled experiments on synthetic graphs and have exploited the conclusions to design a more generalisable model. Three reviewers are positive about the submission, and I also recommend acceptance.
Decision: Accept (poster)