SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks
Authors: Davide Buffelli
Pietro Lio
Fabio Vandin
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Networks
Graph Representation Learning
Deep Learning
Graph Classification

Abstract: In the past few years, graph neural networks (GNNs) have become the de facto model of choice for graph classification. While, from the theoretical viewpoint, most GNNs can operate on graphs of any size, it is empirically observed that their classification performance degrades when they are applied on graphs with sizes that differ from those in the training data. Previous works have tried to tackle this issue in graph classification by providing the model with inductive biases derived from assumptions on the generative process of the graphs, or by requiring access to graphs from the test domain. The first strategy is tied to the quality of the assumptions made for the generative process, and requires the use of specific models designed after the explicit definition of the generative process of the data, leaving open the question of how to improve the performance of generic GNN models in general settings. On the other hand, the second strategy can be applied to any GNN, but requires access to information that is not always easy to obtain. In this work we consider the scenario in which we only have access to the training data, and we propose a regularization strategy that can be applied to any GNN to improve its generalization capabilities from smaller to larger graphs without requiring access to the test data. Our regularization is based on the idea of simulating a shift in the size of the training graphs using coarsening techniques, and enforcing the model to be robust to such a shift. Experimental results on standard datasets show that popular GNN models, trained on the 50% smallest graphs in the dataset and tested on the 10% largest graphs, obtain performance improvements of up to 30% when trained with our regularization strategy.

SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks
Davide Buffelli
Pietro Liò
Department of Information Engineering University of Padova
Department of Computer Science and Technology University of Cambridge Cambridge, United Kingdom CB3 OFD pietro. lio@cl. cam ac.
Padova, Italy 35131
davide. bwffellffeeeeee Pitfeell@umipp.ii.
Fabio Vandin
Department of Information Engineering University of Padova Padova, Italy 35131
fabio. vandin@unipd. it
Abstract
In the past few years, graph neural networks (GNNs) have become the de facto model of choice for graph classification. While, from the theoretical viewpoint, most GNNs can operate on graphs of any size, empirically observed that their classification performance degrades when they are applied on graphs with sizes that differ from those in the training data. Previous works have tried tackle this issue in graph classification by providing the model with inductive biases derived from assumptions on the generative process of the graphs, or by requiring access graphs from the test domain. The first strategy is tied to the quality of the assumptions made for the generative process, and requires the use specific models designed after the explicit definition of the generative process of the data, leaving open the question of how to improve the performance of generic GNN models in general settings. On the other hand, the second strategy be applied to any GNN, but requires access to information that is not always easy obtain. In this work consider the scenario in which we only have access the training data, and we propose a regularization strategy that can be applied to any GNN improve its generalization capabilities from smaller larger graphs without requiring access to the test data. Our regularization is based on the idea of simulating shift in the size of the training graphs using coarsening techniques, and enforcing the model to be robust to such shift, Experimental results on standard datasets show that popular GNN models, trained on the 50% smallest graphs in the dataset and tested on the 10% largest graphs, obtain performance improvements of up 30% when trained with our regularization strategy.
1 Introduction
Graph structured data are found in large variety of domains, ranging from social networks, to molecules and transportation networks. When dealing with graph data in machine learning settings, it is common to resort graph representation learning (29] Graph representation learning is the task of learning to generate vector representations of the nodes, or of entire graphs, that encode structural and feature-related information that can be used for downstream tasks. this area, Graph Neural
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Label
Predicted Label
Supervised Loss
GNN
Node Emboddlngs
G
Regularization Loss
GNN
Node Embeddiine
Gho.1
(G,,,, 0.8)
GNN
Node Embeddinge
Gb..A
Figure 1: Overview of method: given training of labelled graphs, simulate size shift by applying a coarsening function G and we regularize the model to be robust towards this shift. The regularization enforces the distribution of node embeddings generated by the model for the original graph and its coarsened versions to be similar.
Networks (GNNs) are deep learning model for graph representation learning that has become the de facto standard for many tasks, including graph classification, which is the focus of this work.
GNNs are designed to be able work on graphs of any size. However, empirical results show that they struggle at generalizing to graphs of sizes that differ from those in the training data (33) 25
6 68]
Obtaining good generalzacliinnnnnn performance from smaller larger graphs crucial for several reasons. First, it is common for graphs in the same domain to vary in size. For example, social networks can range from tens millions of nodes, and molecular graphs can go from few atoms, to large compounds with thousands of atoms. Second, in many scenarios, obtaining labels for smaller graphs is cheaper than for larger graphs. For example, recently deep learning being used in combinatorial optimization problems [5] and GNNs are heavily used in this area many problems can be formulated as graph classification instances [53 24 IT]. Combinatorial optimization often deals with Na-hard problems, and obtaining ground truth labels can be extremely expensive for large scale graphs. Third, training on smaller graphs requires less computational resources.
Two approaches have been proposed in literature to tackle the poor size-generalization of GNNs. The first approach makes assumptions on the causal graph describing the generative process behind the graphs in the dataset, and then designs a model that is tailored towards such causal graph (6] This strategy requires an explicit definition the generative process behind the data, which, in the case of Bevilacqua et al. [6], leads to model requiring the computation of induced homomorphism densities over connected k-vertex subgraphs in order to make prediction. While this strategy shows great results on synthetic graphs produced by the assumed generative process, its benefits are reduced on real-world graphs, for which the underlying generative process is unknown. The second approach assumes access graphs coming from different domains, or from the test distribution, and applies domain adaptation techniques to transfer knowledge across domains [68] [7]. These methods do not require ad-hoc models, but require knowledge about each graph's 's domain, access to the test distribution, both of which are not always available or easily obtainable advance.
In this work we consider the graph classification scenario in which we only have access to the training data (as the first approach described above). However, in contrast to prior work, we do not try to improve the iize-generalization capabilities (from smaller to larger graphs) of GNNs by handcrafting models on the base of specific knowledge or assumptions, but we study a general form of regularization that can be applied to any GNN, and that aims at letting the model learn to

---

be robust to size-shifts. The idea behind our regularization is to simulate a shift in the size of the training graphs, and to regularize the model be robust towards this shift. The size-shift simulation is obtained using graph coarsening techniques, while the regularization is performed by minimizing the discrepancy between the distributions of the node embeddings generated by the GNN model for the original training graphs and their coarsened versions (an overview is shown in Figure I.
In the experimental section we evaluate GNN models on popular benchmark datasets using a particular train/test split designed to test for aize-gnnrralizaion. In particular, following [68 6 we train on
the 50% smallest graphs and test on the 10% largest. This split leads an average size of the test graphs which is 3 to 9 times larger than the average size of the training graphs. Our results show that our regularization method applied to standard GNN models (GCN [36]. PNA [15], GIN (65) leads to an average performance improvement on the test set of up to 30% across datasets. Furthermore, these performance improvements show that standard GNN models trained with our regularization can achieve better size-generalization performance than more expensive models. The latter more expensive models were designed after making explicit assumptions on the generative process behind the graphs in the dataset [6], while our method relies on learning to be robust towards size-shifts.
Our contributions. Our contributions are threefold. (1) We propose a regularization strategy that can be applied to any GNN to improve its size-generalization capabilities on the task of graph classification. (2) We analyze the impact that our strategy has on the embeddings generated by a GNN. (3) We test our strategy on popular GNN models, and compare against previously proposed methods, showing that "standard" GNN models augmented with our regularization strategy achieve comparable or better sizegennrralization performance than more complex models designed after explicit assumptions on the generative process behind the data.
2 Preliminaries
Notation. Let G = (V, B) be a graph, where is the set of nodes with size n, and E S V x V is the set of edges. For a node E V. we use N2 to indicate the set of its one-hop neighbours (i.e., the nodes connected to u by an edge). We represent an attributed graph G with a tuple (A, X), where A E {0, 1)nxn is the adjacency matrix (i.e., the element in position i is equal to if there is an edge between nodes i and j. and zero otherwise), and X E RRa is the feature matrix, where the i-th row, X,, contains the d-dimensional feature vector for node i.
2.1
Graph Neural Networks
models follow the message-passing paradigm Let (()) E Roxd' be the matrix containing the node representations at layer (i.e., the representation for node i is contained in the i-th row H!")), with ( X. Given aggregation function . which is permutation invariant, and a learnable update function V (usually a neural network), message passing layer updates the representation of every node u as follows:
Most popular Graph Neural Networks (GNNs) 12 14
26
(1) where my represents the aggregated message received by node v from its neighbours. After L message-pan saasagg-passing layers, the final node embeddings H are used to perform given task (e.g., they the input network performing the task), and the whole system is trained end-to-end.
H((+1) V (H (!)),, with m! ((H Vu E N..))
2.2 Graph Coarsening
Given graph G = (V, E), coarsened version G (V", is obtained by partitioning V and grouping together the nodes that belong to the same subset of the partition. More for- mally, given partition p {S,, .....,,. S.r) where S, C V. S, n we associate a node s; to each subset S; and let Ve {S1, $2........ Snr} and E {(s 83) there is node in St connected to least one node in S,). The goal of graph coarsening to gen- erate coarsened version of a graph (i.e., n/ < n) such that specific properties are preserved. For instance, Loukas and Vandergheynst 45 aim at preserving the principal eigenvalues and eigenspaces, while Jin et al. 32 aim at minimizing a distance function that measures the changes in the structure and connectivity that occur in the coarsening process. Jin et al. [32] further prove that their algorithm bounds the spectral distance
0. U, V.
35 between the original and a "lifted" version of the coarsened graph.
3

---

2.3 Central Moment Discrepancy
The Central Moment Discrepancy (CMD) 70 is a metric used measure the discrepancy between the distribution of high-dimensional random variables. Let p and q be two probability distributions with support in the interval [a, 6)º and let c₁ be the k-th order moment, then the CMD between p and q is defined as:
CMD(P, - 1b [B(p)) E(Dlll + Σ Ib- (cca(p) cc) cx)ll)22
k=2
At a practical level, we follow Zhu et al. 72.. and limit the number of considered moments to 5. To align with the definition of CMD it is possible to treat node embeddings as realizations of bounded high dimensional distributions by applying bounded activation functions like tanh or sigmoid at the embeddings layer (as done in [70 72)).
Our Method
The high level idea behind our method is to "simulate" a size-shift in the training dataset, and to regularize the GNN to robust to this shift (an overview is shown Figure [.. While previous works rely on models that incorporate domain-speciff inductive biases and/or are tied to assumptions on the generative process of the data, our method aims at learning to be robust towards size-shifts.
Simulating the shift. Let go (G.r) G. be coarsening function, that takes as input graph G with n nodes and a ratio r E (0, 1), and returns coarsened version of the graph, GØ, which has Ir nd nodes. Our method is not bound to specific coarsening function G any existing method
43 32). Our method then proceeds in the following way: given dataset of graphs D (G1, Gg...., Ge). coarsening function Go and set of l: coarsening ratios C = fri. r2,..., we create a coarsened dataset D,, for each ratio by applying the coarsening function (G
can used, e.g. 45
.....
r,), G. (G,, (t)rr;)), 1,2 1.......A. A: When the graph is attributed, we obtain the features for each node of the coarsened version of the graph by aggregating the features of the corresponding nodes in the original graph using simple aggregations (e.g., mean, max, sum), as commonly done in readout functions for GNNs [64].
to each graph the dataset: Dr,
(G2,,yy), G
Regularizing the GNN. Given the graph dataset D, its coarsened versions D,,, : Dr., Dru and GNN fe, where 9 are the parameters, aim at regularizing the GNN that the distribution of the node embeddings generated by the model for the graphs in the original dataset and their coarsened version is similar. In other words, for given graph, want the model to generate distribution of node embeddings that is robust across different coarsened versions of the graph. In more detail, we regularize GNN by minimizing the CMD (70] between the distribution of the node embeddings generated by the GNN for the original graph and the distribution of the node embeddings generated by the GNN for the coarsened version(s) of the graph. We choose CMD has proven be successful and stable as regularization term for non-linear models [42 72). Formally, let L be the supervised loss function that is used to train the model (e.g. cross entropy for classification), and let À be a term measuring the strength of the regularization. Our optimization problem is
argmin ASiize, where Laize
ΣΣ folC
(3)
Our method is model-agnostic, and can hence be applied to any GNN.
Pseudocode and practical aspect. Algorithm presents the pseudocode for computing our regular- ization loss for batch of graphs during training. The pseudocode is presented in an extended manner for clarity, but at a practical level, the coarsened versions of the training graphs are pre-computed before training, and the computation of the loss is done in vectored manner so it is computed concurrently for all graphs in the batch in one pass (i.e., we do not iterate through the graphs the batch). At a practical level, in our experiments we notice that training model with our regularization introduces a 50% overhead in the running time for a training epoch w.r.t. training the same model without regularization.

---

3.1 Limitations
Similarly to previous works [ 688 we are assuming that there are some properties that determine the label of graph and that do not depend on the size of the graph. In scenario in which small graphs do not carry information that is relevant for solving the task on larger graphs, we not expect our regularization to provide substantial benefits, and the best option would be include larger graphs in the training set. In our experiments, the ratio between the average size of the graphs in the test set and the average size of the graphs in the training set is between 3 and 9. While our method shows significant performance improvements this setting, it may show lower performance improvements when this ratio reaches much higher values.
Algorithm Computing Regularization Loss for an Input Batch during Training
Require: Coarsening ratios C, coarsening function (graph, ratio) Batch B of size vig, GNN model Jo
Input:
coarsened batches t- 0
y in C do
Create new batch of coarsened graphs for each ratio
Batch B, + for G in H do
G + (G, (G,)
end
coarsened_batte batches + coarsened batches U Br end for 4-00 0 B, in coursened batches do
Initialize loss
for in {1, ... 7 do
embs_og og (i(
Compute node embeddings for original graph
Compute node embeddings for coarsened version of graph f 2- L CMD(embs og, embs coarse) end end
embs coarse = fo BB :))
b. Compute CMD between node embeddings
Return
4 Analysis of Node Embeddings
Before evaluating how regularization im- pacts the size- iizeggnneralization performance model, analyze the effects that regular- ization has on the embeddings generated by the model. In order to do this, we consider two iden- tical GIN (65] models and we train one with regularization and without. We then use these models to generate node embeddings and use the Central Kernel Alignment (CKA) [38] to study the generated representations, similarly
Table I: Average CKA values between the node embeddings generated by two models, one trained with and one without our regularization, across the graphs in a dataset and their coarsened versions.
Dataset
NCI1
NC1109
PROTEINS
DD
Original
0.43 Loo
0.58 1
0.45
0.47 1 no1
Coursened
0.12 0.05
D.38 1 0.13
0.34 1 cass
0.40 2 0.1
to 34 CKAA takes as input two matrices A RR B E mmxd" of representations and provides value between and quantifying how aligned the representations are (allowing for d' & d"). CKA quantifies the similarity of representations learned by (possibly) different models and gives us way to study the effects of our regularization. We report results averaged over 10 different random seeds. We show only results for the DD dataset for space limitations, but the same trends are observed for the other datasets (see Appendix).
First, we ask if model trained with our regularization and a model trained without our regularization produce similar node embeddings. To compare the node embeddings between the two models we obtain a representation for each graph by concatenating the node embeddings for that graph. We then compute the CKA between the representations generated by the model trained with regularization and the representations from model trained without regularization. We do this for the original graphs and the coarsened versions of the graphs, and report the average CKA. Results shown Table [ highlight that there is low alignment between the embeddings generated by model trained with regularization and one trained without regularization (the average CKA across datasets is 0.48 for the original graphs). This is even more apparent for the coarsened graphs, showing that our regularization
5

---

Original
wilhod regutie cntiion
Coarse Simphs
0.9
Model Ims nod with regura cotion
0.478
0.7
0.428
0.5
0.400
0.375
0.3
0.8
0.7
Coarsonin
Coarsening Rato
(a)
(b)
Figure 2: (a) Average CKA values between the node embeddings from two models, one trained with regularization and one without, across the original graphs in the DD dataset and their coarsened versions for different ratios. The models produce representations which are not aligned (values are far from 1.0), specially for coarsened graphs. (b) Average CKA values between the node embeddings generated by the same model for the original graphs DD and their coarsened versions. A model trained with regularization produces representations of the coarsened graphs that are more aligned to the representations produced for the original graphs (i.e. it learns to be robust to size shifts).
impacting the way a model generates embeddings, especially for size-shifted versions of the graphs. To analyze the trend more in detail, we also plot the CKA values across coarsening ratios in Figure (a). Here we notice that the CKA between the embeddings generated by a model trained with our regularization and model trained without, decreases significantly with ratios lower than 0.8. This shows that, while the alignment between the representations learned by the models trained with and without regularization is low even for coarsening ratio of 0.9 (average CKA value is 0.47), it becomes 15% lower (on average) for ratios smaller than 0.7, indicating that when the size shift is strong, there a stronger misalignment between models trained with and without regularization.
Second, we ask a model trained with our regularization is in fact being more robust to size shifts with respect to model trained without regularization. To answer this question the alignment between the representations generated by the same model, trained with or without regularization, original graphs and coarsened versions of the graphs. In Figure (b) we plot the average CKA between the node embeddings for the original graphs and the node embeddings for the coarsened versions of the graphs, both generated by the learning to be more robust to size shifts, as its
analyze
model, for different ratios. The plot
shows that a model trained with our regularization representation for coarsened versions of the graphs are much more aligned to the representations for the original graphs compared to a model trained without regularization. This is even more apparent for low coarsening ratios (i.e., when the shift stronger), indicating that our regularization faat making the model more robust to size shifts.
Evaluation
Following prior works 66 68), we evaluate on datasets from the TUDataset library with train/test split explicitly designed to test for iize-gnneralzzation In particular, the training split contains the graphs with size smaller or equal than the 50-th percentile, and the test split contains graphs with size larger equal than the 90-th percentile. With this split, the average size of the test graphs 3 to 9 times larger than the average size of the training graphs (in more detail, it is for NCII and NCI109, 9 for PROTEINS, and for DD). We use 10% of the training graphs validation set. More details on the datasets can be found in the Appendix.
Datasets.
48
Models. As in Bevilacqua et al. [6), we consider three standard GNN models: GCN 36). GIN 653. and PNA [15), more expressive GNN: RPGNN
49 and two graph kernels: the Graphlet Counting kernel (GC Kernel) (58), and the WI. Kernel 59 We further apply the Invariant Risk
Minimization (IRM) [ penalty to the standard GNN models, and compare against the E-Invarrinnt models (I' 1hot L'GNN RPGGIN) introduced in Bevilacqua al. (6]. For IRM, we follow (6), and

---

Table 2: Average Matthews Correlation Coefficient (MCC) for standard GNN models over the sezeaeeneaalizttoon test set. The models have been trained with (v) and without (X) our regularization method. The right-most column shows the average improvement brought by our regularization.
Dataset
NCII
NC1109
PROTEINS
Avg.
Reg.
X
X
X
X
Impr.
PNA
0.19
0.22 + 0.07
0.23 0.07
0
0.22
0.33
0.09
0.23 - 0.09
0.27 0.08
+22%
GCN
0.17 0.00
0.25
- 0.06
0.15 = 0.00
0.19 + 0.96
0.21
0.10
0.29 =
0.18
0.24
+ 0.07
0.26
0.07
+30%
GIN
0.06
0.23 + 0.08
0.18
0.20 + 0.05
0.25
0.36
0.23
+ 0.00
0.25
+21%
Table 3:
Comparison of average Matthews Correlation Coefficient (MCC) over the size-generalization test data between the standard GNN models trained with our proposed regularization and previously proposed methods. Highlighted are the first, second, and third best performing models per dataset.
Dataset
NCI1
NCT109
PROTEINS
DD
PNA (reg) [ours]
0.22 + 0.07
0.24 0.07
0.33 + 0.09
0.27 + 0.08
GCN (reg) [ours]
0.25 + 0.08
0.19 0.86
0.29 0.13
0.26 + 0.07
GIN (reg) [ours]
0.23 + 0.08
0.20 0.06
0.36 + 0.11
0.25 + 0.09
PNA + IRM 1
0.17 + 0.07
0.20 + 0.07
0.21 0.12
0.24 + 0.08
GCN + IRM
0,22 + 0,08
0.20 + 0.06
0.23 0.16
0.23 : 0.08
GIN IRM 0
0,18 + 0.08
0,15 + 0.04
0.24 1 0.08
0.21 + 0.10
WL kernel
59
0.39 +: 0.00
0.21
0.00 0.00
0,00
GC kemee
58
0.02 + 0.00
0.01 + 0.90
0.29 + 0.00
0.00
RPGIN 49
0.18 + 0.08
0.16 + 0.04
0.22 1 0.08
0.13 : 0.04
I' hot 6
0.15 + 0.05
0.22
0.18 + 0.08
0.22 +
I GIN 6
0.24 + 0.05
0.16 + 0.07
0.28 + 0.10
0.27 + 0.05
[ RPGIN 6
0.26 + 0.05
0.19 + 0.06
0.26 + 0.07
0.20 = 0.05
artificially create two environments: one with graphs with size smaller than the median size of the graphs in the training set, and one with graphs with size larger than the median size in the training set.
Hyperparameters and Evaluation Protocol. For the standard GNN models we adopt the same hyperaarameters of Bevilacqua al. [6, which were obtained from tuning procedure involving number of layers, learning rate, batch size, hidden layers dimension, and regularization terms. All models are trained with early stopping (i.e., taking the weights at the epoch with best performance on the validation set). We do not modify the original hyperparameters when we apply our regularization. We tune the regularization coefficient À and the coarse ratios C' for GIN on the PROTEINS dataset (we found X= = 0.1 and C = {0.8, 0.9} to be the best on the validation set), and we apply these settings to all models and datasets when using our regularization, to show that our method can work without extensive (and expensive) hyperparameter tuning. We use the SGC coarsening algorithm 32 to obtain the coarsened versions of the graphs (chosen for its theoretical properties). The only hyperparameter that is tuned on per-dataset basis is the aggregation strategy used to obtain the features for the nodes in the coarsened versions of the graphs (in particular we take the best performing between 'sum', 'max', and 'mean'), ) For all other models we use the hyperparameters introduced by their respective papers. Bevilacqua al. 66] presented results by averaging over 10 runs (each time with different random seed), but given the high variance observed, we re-run the experiments for all the models and present the results averaged over 50 runs. More details on the hyperparameters can be found in the Appendix and source code is publicly available
5.1 Results
Table 2 shows how the three considered standard GNN models perform on the test set, containing the 10% largest graphs in the dataset, when trained with and without our regularization on the 50% smallest graphs in the dataset. As this split leads to an imbalanced dataset, we follow previous works and report the results in terms of Matthews correlation coefficient (MCC), which has been shown
7

---

to be more reliable in imbalanced settings with respect to other common metrics [4]. MCC gives value between -1 and 1. where -1 indicates perfect disagreement, is the value for a random guesser, and 1 indicates perfect agreement between the predictions and the true labels. The results show that the use of the proposed regularization is always beneficial to the performance of the models, and that it leads to an average improvement across datasets of 21 to 30%.
In Table 3 we compare the standard GNNs trained with our regularization strategy against more expressive models (RPGNN), graph kernels, models trained with the IRM strategy, and the E-invariant models. We notice that on 3 out of 4 datasets, a "standard" GNN trained with our regularization obtains the best performance on the test set composed of graphs with size larger than those present in the training set. Furthermore on all datasets there is at least one model trained with our regularization in the top-3 best performing models. We also confirm previous results [6. 17 showing that IRM not effective the graph domain, and that using theoretically more expressive models, like RPGNN, does not necessarily lead to good size- size-genrralization performance. Graph kernels are highly detaset-dependent, and, while they can perform well for some datasets, in many cases they fail to perform better than a random classifier. Perhaps more surprisingly, on out of datasets there is at least one "standard" GNN trained with our regularization that performs comparably or better than the best E-Invariant model. In fact, E-invariant models are tied to the assumed causal model for the generation of graphs, which is not guaranteed to hold reliably for real-world datasets for which we do not have this kind of information. Futhermore, E-invariant models require the computation of induced homomorphism densities over all possible connected k-vertex subgraphs both at training time and at test time. Our method instead tries to learn to be robust to size-shifts, does not require any additional computation at inference time, and yet can lead even simple models like GCN to have size-gent generalization performance comparable to E-invariant models.
Table 4: Average MCC results on the Deezer dataset for models trained with (V) and without (X) our regularization.
Dataset
Deezer
Reg.
x
PNA
0.59 + 0.06
0.64 + 0.07
GCN
0.49 0.10
0.59 = 0.06
GIN
0.55 + 0.08
0.61 + 0.07
Finally, in addition to the benchmarks considered by Bevilacqua et al. [6), we also experiment dataset from a different domain. In particular, we consider social network dataset obtained from Deezer (53). We follow the same evaluation strategy before: train the 50% smallest and test on the 10% largest, and we apply our regularization with X = 0.1 and C = {0.8, 0.9) without any additional hyperparameter tuning. Results shown in Table 4 confirm the effectiveness of our method.
5.2 Ablation Study
In this section we use PNA model to study the contribution and importance of the different components of our regularization. We choose PNA because of its performance in the previous analysis, but similar conclusions are observed for GIN and GCN (as we report in the Appendix).
Changing Size of Coarsened Graphs. In Ta- ble [ we train PNA model with our regular- ization strategy using different coarsening ra- tios C. We notice overall trend in which the performance decreases as the coarsening ra- tio decreases. This follows intuitively as very low coarsening ratios may lead to uninformative graphs. Furthermore
Table 5: Average MCC results on the size- generalization test set for a PNA model trained with our regularization strategy using different coarsening ratios.
Datasets Ratio(s)
NCI1
NC1109
PROTEINS
DD
notice that using all ratios (from 0.1 to 0.9) is usually not effective and setting C {0.8, 0.9) seems good default option, leading to the best performance on out of 4 datasets.
0.07 +
0.19+...00
0.12
0.07
0.2
0.11 1 0.13
0.20 1 6.08
0.18 1 0.16
0.20
1 1.11
0.3
0.15 1
0.22
0.17 2
0.22
1:
0.4
0.18 - 0.08
0.22 2 0.08
0.23 = 0.14
0.26
+ 0.11
0.5
0.22 0.00
0.24 0.00
0.29 +
0.22 + 0.00
0.23 0.0e
0.07
0.08
0.10
0.7
0.22 1 0.17
0.24
1 0.06
(1.30 1: 0.34
0.24 1: 0.05
0.21 + 0.06
0.23
0.9
0.19 1. 0.00
0.21
1 0.00
0.28 1L 0.32
0.25 L. 1.
Changing Coarsening Method. In Figure
3
(0.1.0.9)
0.12 + 0.10
0.20
0.14
0.14 +:
we show how the performance of PNA model change when it is regularized with our method using graphs coming from different coarsening functions. We consider Spectral Graph Coarsen-
[0.5, 0.9
0.23 + 0.0s
0.22 0.07
0.32 + 0.12
0.27 + 0.05
(0.8.09)
0.22 1 0.17
0.24 6.07
0.33 1
0.27 1
[0.3. 0.73
0.22 : 0.00
0.21 1 0.06
0.21 = 0.11
0.25 + 0.00
ALL
0.18 0.00
0.18
0.17 0.14
0.23 0.
8

---

6.9
531
130
Eem
530
306
18.55
(a) NCT1
(b) NCT109
(c) PROTEINS
(d) DD
Figure 3: Average MCC the test set of PNA model trained with regularization strategy using
different coarsening methods: Spectral Graph Coarsening (SGC), Multi-level Graph Coarsening
(MLGC), Spectral Clustering (SC), K-Means (KMEANS).
ing (SGC) and Multi-level Graph Coarsening (MLGC) introduced by Jin et al. [32) and two baselines,
referred as SC and KMEANS, based on standard spectral clustering [28] and K-Means clustering
[4] For the baselines we apply the clustering algorithm, merge the nodes belonging to the same
cluster into single super-node, and create an edge between two super-nodes if there is at least one
edge in the original graph going from node in one cluster to the other. For all coarsening methods we use the same coarsening ratios as above (i.e., C {0.8, 0.9)), and we apply the same training procedure and regularization weight X, keeping all hyperparameters equal across methods. We notice that our regularization strategy is quite robust towards the choice the coarsening method, but, on average, specialised methods like SGC and MLGC tend to provide the best results.
Related Work
Graph neural networks and size-generalization. Since the first instances of graph neural networks have appeared 57), the field has exploded in recent years with a plethora of different architectures 15 62] ) applications (e.g.. [69 67 37 23 R) and studies on their expressivity and 9). For a complete review of the field, we refer to the excellent surveys by Chami al. and by Wu al. 644. Many works have noticed poor gereraalizztiinn in 68 For instance, Joshi et al. [33] consider the task of learning solutions for the traveling salesman problem, and show that GNNs struggle at generalizing to graphs larger than those appearing in the training set. Similarly, Gasteiger et al. [25] observe that GNNs applied to the molecular domain can be very sensible to several shifts in the data, including shifts the size of the graphs. Some works have reported good lizeggeneralizationn by creating ad-hoc models that leverage the properties of the domain constraints dictated by the physical properties of their data, and report good size-generalization in predicting the energy of a molecule. While these works show that placing the right inductive biases can help the size-generalization capabilities of GNNs, the current literature is lacking a general method that can be applied on generic GNNs.
(e.g.. [36 65
properties (e.g., 65
GNNs B3 25
3 56, 61 [2]. For example, Tsubaki and Mizoguchi [6] impose
Bevilacqua et al. [6] tackle the issue of poor size- generalization by assuming a causal model describing the generative process for the graphs in the dataset, and designing specific model which can be invariant to the size of the graphs obtained through this causal model. While this strategy shows great rerggeenrrlliztionn capabilities on synthetic graphs generated according to their causal model, its benefits decrease when applied to real-world graphs where there are no guarantees that the causal model is correct. This method requires an ad-hoc model and additional computations at both train and test time, while our method can be applied any GNN and does not require pre-computations at test time. Yehudai et al. (68) provide a theoretical and empirical analysis showing that, even for simple tasks, it is not trivial to obtain GNN with good size- trre-eeneraalzation properties. Yehudai et al. [68] consider a different scenario from ours, as, together with the labelled training graphs, they assume access to graphs from the test distribution, and treat the task domain- comain-adaptation scenario.
Graph coarsening. While there is no consensus what is the best metric to consider for coarsening a graph, many methods and metrics have been proposed recent years (45
43
18
7
32
There
have also been some attempts at using GNNs for the task of graph coarsening 10 46 Orthogonally,
graph coarsening has been used to reduce the computational resources needed for training GNNs on
large graphs [1 31). For a detailed presentation of graph coarsening refer to Chen et al. [13]

---

Invariant risk minimization, domain adaptation, and regularization with discrepancy measures. Our method conceptually related to Invariant Risk Minimization (IRM) M. which aims at learning representations that are invariant across training environments (where different training environments are intended as sets of data points collected under different conditions). IRM has been shown to have several shortcomings, specially when the data comes from single environment (e.g. when there is access only to small graphs) [54] 6]. Our method does not require access to different training environments, which may not be easy obtain in practical scenarios, and our results show that, as also observed in [6 17,, IRM seems ineffective for improving size-generalization in GNNs.
Similarly to IRM, the field of domain adaptation [4] subsumes access to (unlabelled) external data, in addition labelled training data, and aims at transferring knowledge between domains. Domain adaptation has been used in large variety of fields, and many surveys are available 63 [2]] Ding al. analyze how existing domain adaptation algorithms perform on graph data, and observe that these tend to not be effective, indicating that new methods specific for graph data are needed.
Discrepancy measures that have been used for regularizing deep learning models are the Maximum mean discrepancy (MMD) 119 41 66, (2) and the central moment discrepancy (CMD) [52] 70, (2). which has been shown to be empirically more effective. We further mention the work by Zhu et al. [2] which, similarly to ours, uses CMD to obtain a GNN that is robust to biases in the sampling process that is used to select the nodes for the training set in node classification scenarios. Finally, we mention the work by Joshi et al. 34 which uses CMD to study the representations of GNNs.
Conclusions
GNNs are heavily used models for the task of graph classification. In many domains is typical for graphs to vary in size, and while GNNs designed to be able to process graphs of any size, empirical results across literature have highlighted that GNNs struggle at generalizing to sizes unseen during training. In this work introduce regularization strategy that be applied on any GNN, and that improves size-generalization performance from smaller to larger graphs by up to 30%.
Acknowledgments and Disclosure of Funding
The authors thank Chaitanya Joshi and Iulia Duta for the great feedback provided on earlier versions of the paper.
This work is supported. part, by the Italian Ministry of Education, University and Research (MIUR), under PRIN Project 20174LF3T8 "AHeAD" and the initiative "Departments of Excellence" (Law 232/2016), and by University Padova under project "SID 2020: RATED-X".
References
[1] M. Arjovsky, L. Bottou, I. Gulrajani, and D. Lopez-Pazz Invariant risk minimization. arXiv preprint arXiv: 2019.
[2] Battaglia, R. Pascanu, M. Lai, D. Jimenez Rezende, al. Interaction networks for learning about objects, relations and physics. Advances in neural information processing systems, 29, 2016.
[3] I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 1111111199900 1.09940, 2016.
[4] S. Ben-David, Blitzer, K. Crammer, A. Kulesza, Percira, and J. W. Vaughan. A theory of learning from different domains. Machine learning, 79(1):151-175 2010.
[5] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: A methodological tour d' d'horizon. European Journal of Operational Reseurch, 290(2):405 421, apr 2021. doi: 10. 1016/6)ejor .73063..... URI. httptttsss/...og/pp/ttaeoooooo/e 2020. 07.063
10

---

[6] B. Bevilacqua, Y. Zhou, and B. Ribeiro. Size-invariant graph representations for graph clas- sification extrapolations. In M. Meila and T. Zhang, editors. Proceedings of the 38th In- lernational Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 Proceedings of Machine Learning Research, pages 837-851. PMLR, 2021. URL http://proceeddi mlr. wwwppprssssseee (teess//13///bbvaacquuu
html
[7] G. DermsoHermsdorff and L. M. Gunderson. A Unifying Framework for Epectrum-Preservvin Graph Sparsification and Coarsening. Curran Associates Inc., Red Hook, NY, USA, 2019.
[8] D. Buffelli and F. Vandin. Graph representation learning for multi-task settings: meta-learning approach. In 2022 International Joint Conference on Neural Networks (IJCNN), pages 1-8,
2022. doi: 10. WWW.UJCCNNS004422222880000000000
[9] D. Buffelli and F. Vandin. The impact of global structural information in graph neural networks applications. applicattoo Data, 7(1), 2022. ISSN 2306-5729,
doi: 10.3390/data7010000. URL https
7/www. mdp1. www.cccw.mmcc.e... 5729 5729/7/1/10
[10] C. Cai, D. Wang, and Y. Wang. Graph coarsening with neural networks. In International Conference on Learning Representations, 2021. URL idxuppiitPEooJ
wwtprrvviiieeeeefrrrnnree. net/forum?
[11] Q Cappart, D. Chételat, E. B. Khalil, A. Lodi, C. Morris, and P. Veličković. Combinatorial optimization and reasoning with graph neural networks. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, aug 2021. doi: 2/44966///cai.2221/5500 URL https
7/doi. org/10 24963 jaiii.iiiiaii....i 2021222595
[12] I. Chami, S. Abu-EI-Haija, B. Perozzi, C. Ré, and K. Murphy, Machine learning on graphs: A model and comprehensive taxonomy. arXiv preprint arXiv:2005.03673 2020.
[13] Chen, Y. Saad, and Z. Zhang. Graph coarsening: from scientific computing to machine learning. SeMA Journal, 79(1):187-22)) jan 2022. doi: 10. 10.11007/440244:0110022222 URL
https://doi.. http::::/doi.ogg11....11 10701000000020020001----1- 020--03-------0000 00282-x
[14] D. Chicco and G. Jurman. The advantages of the matthews correlation coefficient (MCC) over fl score and accuracy in binary classification evaluation. BMC Genomics, 21(1), jan 2020. doi: 10.1 1866//1864--01--1111 -11-6-1---11----7--7
htRhhtts::// //doi htt////ii.rg///////
[15] G. Corso, L. Cavalleri, D. Beaini, P. Liò, and P. Veličković. Principal neighbourhood ag- gregation for graph nets. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages Curran Associates, Inc., 2020. URL httpps::pproceeeinnnge htwpoooeeddingn..uuu......... /ttp://aaa6511166622200010010000
Paper pdf
[16] G. Csurka. A Comprehensive Survey on Domain Adaptation for Visual Applications, pages 1-35. Springer International Publishing, Cham, 2017. ISBN 978-3-319-58347-11 doi: 10.1007/ 978-3-319-58347-1
[17] M. Ding, K. Kong. J. Chen, Kirchenbauer, M. Goldblum, D. Wipf. Huang, and T. Goldstein. A closer look at distribution shifts and out-of-distribution generalization on graphs. In NeurlPS 202 Workshop on Distribution Shifts: Connecting Methods and Applications, 2021. URL https: /stps:///pperevieet nwt orrum 7id xd=XygPGWzzqRi
[18] D. Durfee, Y. Gao. G. Goranci, and R. Peng. Fully dynamic spectral vertex sparsifiers and applications. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages
2019.
[19] G. K. Dziugaite, D. M. Roy, and Z. Ghahramani. Training generative neural networks via maximum mean discrepancy optimization. In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, pages 258-267, 2015.
[20] W. Falcon et Pytorch lightning. GitHub. Note: lightning, 3, 2019.
11

---

[21] M. Fey and J. E. Lenssen. Fast graph representation learning with pytorch geometric, 2019. URL https: wwt.aaawww......a.araaaaaaaaaaee htte/bbb/1900 02428
[22] Z.-H. Fu, K.-B. Qiu, and H. Zha. Generalize a small pre-trained model arbitrarily large tsp instances. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8):7474 7482, May 2021. URL https:/ aaai axgg/ndex..o hatp:/AAAAArttilllvee/ee////
[23] V. Fung, Zhang, E. Juarez, and B. G. Sumpter. Benchmarking graph neural networks for materials chemistry. upj Computational Materials, 7(1):1-8, 2021.
[24] M. Gasse, D. Chételat, N. Ferroni, I. Charlin, and A. Lodi. Exact Combinatorial Optimization with Graph Convolutional Neural Networks. Curran Associates Inc., Red Hook, NY, USA, 2019.
[25] J. Gasteiger, M. Shuaibi, A. Sriram, S. Günnemann, Z. Ulissi, C. L. Zitnick, and A. Das. How graph networks generalize to large and diverse molecular systems?, 2022. URL
https://arxie org/ abs/2204 02782
[26] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, pages
JMLR.org, 2017.
[27] H. Guan and M. Liu. Domain adaptation for medical image analysis: a survey, IEEE Transac- tions on Biomedical Engineering, 2021.
[28] C. Guo, S. Zheng, Y. Xie, and W. Hao. A survey on spectral clustering, World Automation Congress 2012, pages 53-56, 2012.
[29] W. L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1-199, 2020.
[30] C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, F. del Río, M. Wiebe, Peterson, P. Gérard-Marchant, K. Sheppard, Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant. Arry programming with NumPy. Nature, 585(7825):357-362 Sept. 2020. doi: (0.10388/441586-0222266666 https://ddot org. http::://do..or//II..0000 0000:000228880000022202
T.
URL
[31] W. Jin, Zhao, S. Zhang, Y. Liu, J. Tang, and N. Shah. Graph condensation for graph neural networks. In International Conference on Learning Representations, 2022. URL
httpp://openreevier. htw.:/eeeefffoeoee hett//forummidd-Ml3333000000
[32] Y. Jin, A. Loukas, and JaJa. Graph coarsening with preserved spectral properties. In S. Chiappa and R. Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4452 4462. PMLR, 26-28 Aug 2020. URL httpp:://rrceeddiggg mlr press/v108/ jin20a. html
[33] K. Joshi, Q Cappart, L.-M. Rousseau, and T. Laurent. Learning TSP Requires Rethinking Generalization. In L. D. Michel, editor, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). volume 210 Leibniz International Proceed- ings in Informatics (LIPlcs), pages 33:1-33:211 Dagstuhl, Germany, 2021. Schloss Dagstuhl- Leibniz-Zentruum für Informatik. ISBN 978-3-95977-211-22 doi: 10.42300LIPPcs.CCP. .P..cc......0...33. URI. U httph:ttt:::/e/ //ttops//ddoss.... dagstuhl httpa///////pp//aleeeeeee///0/00
[34] C. K. Joshi, F. Liu, X. Xun, J. Lin, and C.-S. Foo. On representation knowledge distillation for graph neural networks. arXiv preprint arXiv:2111.04964 2021.
[35] JJovanović and Z. Stanić. Spectral distances of graphs. Linear Algebra and its Applications,
2011.00.011 0.0.019. URL httpts://ww. htt.ip/////w..ccienneeteeee..c. cow http:///aaaa/aattte///////////..
14255)::425-14355 2012. ISSN 0024-3795. doi: http:///do..org/0.0016///
[36] N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks.
In International Conference on Learning Representations (ICLR), 2017.
12

---

[37] J. Klicpera, F. Becker, and S. Günnemann. Gemnet: Universal directional graph neural networks for molecules. In Advances in Neural Information Processing Systems, 2021.
[38] S. Kormblith, M. Norouzi, H. Lee, and G. Hinton. Similarity of neural network representations revisited. In International Conference on Machine Learning, pages 3519-3529, PMLR, 2019.
[39] R. Liaw, E. Liang, R. Nishihara, Moritz, J. E. Gonzalez, and I. Stoica. Tune: A research platform for distributed model selection and training. arXiv preprint
08, 2018.
[40] Lloyd. Least squares quantization in pem. IEEE Transactions on Information Theory, 28(2): 129-137, 1982. doi: 10. 19110/0TT.99922155555555
[41] M. Long, Y. Cao, J. Wang, and M. Jordan. Learning transferable features with deep adaptation networks. In International conference on machine learning, pages 97-105. PMLR, 2015.
[42] M. Long, H. Zhu, J. Wang, and M. I. Jordan. Deep transfer learning with joint adaptation networks. In Proceedings of the 34th International Conference on Machine Learning Volume JMLR.org, 2017.
70, ICML' 17, pages
[43] A. Loukas. Graph reduction with spectral and eut guarantees. Journal of Machine Learning Research, 20(116):1-44 42, 2019. //tp:/
http:/ppppss//////// 680. .hmll
[44] A. Loukas. What graph neural networks cannot learn: depth vs width. In International Conference Learning Representations, 2019.
[45] A. Loukas and P. Vandergheynst. Spectrally approximating large graphs with smaller graphs. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3237-3246. PMLR, 10-15 Jul 2018. UuR.htttss//prrceediii
mlr. wal..pprss//e wwtppppesssssssoeee //0///00011/aa/ .8t.mmml
[46] T. Ma and J. Chen. Unsupervised learning of graph hierarchical abstractions with differen- tiable coarsening and optimal transport. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8856-8864, 2021.
[47] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the 2019.
AAAI conference on artificial intelligence, volume 33, pages
[48] C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop Graph Representation Learning and Beyond (GRL+ 2020). 2020. URL www www.hhearainanng....
[49] R. Murphy, B. Srinivasan, Rao, and B. Ribeiro. Relational pooling for graph representations. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4663 4673. PMIR, 09-15 Jun 2019. URL httpstts::// httttps://proceeednng mlr wtw.sppess////e v97
pttpess/vv//mm///// //rr/murppyl 19m 19a
html
[50] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. Vito, M. Raison, A. Tejani, S. S.Chilamkurthy, B. Steiner, L.. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019. URL URL Utt/http://ppprrrrr nwwripw..i...e wwweeriis.cccppppppp cc/paper/ pdf
hntt:orch-a--ingeene htg.aa/eeeeeeeeeeeeeerrrerreeeee library
[51] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning Python, Journal of Machine Learning Research, 12:2825-2834 2.1
13

---

[52] M. Peng, Q. Zhang, Y.-. Jiang, and X.-J. Huang. Cross-domain sentiment classification with target domain specific information. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 2505-2513, 2018.
[53] M. Prates, P. H. C. Avelar, H. Lemos, L. C. Lamb, and M. Y. Vardi. Learning to solve NP- complete problems: A graph neural network for decision TSP. Proceedings of the AAAI Conference on Artificial Intelligence, 33:4731 4738, jul 2019. doi: 10. (16609/aaai.v3300000 33014731. BtR.https:///ol. org/10 10. 1609% v33101 33014731
[54] E. Rosenfeld, P. Ravikumar, and A. Risteski. The risks of invariant risk minimization. In International Conference on Learning Reprexentations, volume 9, 2021.
[55] B. Rozemberczki, O. Kiss, and R. Sarkar. Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs. Proceedings of the 29th ACM International Conference Information and Knowledge Management (CIKM '20), page 5125-3132. ACM, 2020.
[56] A. Sanchez-Gonzalez, N. Heess, T. Springenberg, Merel, M. Riedmiller, R. Hadsell, and P. Battaglia. Graph networks as learnable physics engines for inference and control. In International Conference on Machine Learning, pages
PMLR, 2018.
[57] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009. doi: 10. 109/ TNN.2008.2005605.
[58] N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borgwardt. Efficient graphlet kernels for large graph comparison. In D. van Dyk and M. Welling, editors, Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, volume 5 of Proceedings of Machine Learning Research, pages 488-495, Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA, 16-18 Apr 2009. PMLR. URU/ttps://prroeediiia mlr pross//t/shervashitcese html
[59] N. Shervashidze, P. Schweitzer, E. J. van Leeuwen, K. Mehlhom, and K. M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(77):559-2561, 2011. URL http://jmmm http:///pppeeeeeeee////eaaaaaaaa htmml
[60] A. Sperduti and A. Starita. Supervised neural networks for the classification of structures. IEEE Transactions Neural Networks, 8(3):714-735, 1997. doi: 10. 10.1109/72.572108.
[61] M. Tsubaki and T. Mizoguchi. On the equivalence of molecular graph convolution and molecular wave function with poor basis set. Advances Neural Information Processing Systems, 33: 1982-1993, 2020.
[62] Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
[63] G. Wilson and J. Cook. A survey of unsupervised deep domain adaptation. ACM Transactions on Intelligent Systems and Technology, 11(5):1-46, oct 2020. doi: 10.1145/3400066. URL
1145/2F3400066 https://doi. http::///ooo.rrrr....1.01////00/
[64] Z. Wu, Pan, Chen, G. Long, C. Zhang, and Yu. A comprehensive survey on graph neural networks. IEEE Trunsactions Neural Networks and Learning Systems, 32(1):4-24, 2021. doi: 10. 10.11060 20009//NNSS..020.22999999.
[65] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL htt.htttt///peeeeee het//forumiidrrrCGsiikKKK
[66] H. Yan, Y. Ding, P. Li, Q Wang, Y. Xu, and W. Zuo. Mind the class weight bias: Weighted maximum mean discrepancy for unsupervised domain adaptation. Proceedings of the IEEE conference computer vision and pattern recognition, pages 2272-2281, 2017.
14

---

[67] M. Yasunaga, H. Ren, A. Bosselut, P. Liang, and J. Leskovec. Qa-gnn: Reasoning with language models and knowledge graphs for question answering. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 535-546, 2021.
[68] G. Yehudai, E. Fetaya, E. Meirom, G. Chechik, and H. Maron. From local structures to size generalization in graph neural networks. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11975-11986. PMLR, 18-24 Jul 2021. URL https //proceedings.it www.mmlr..rreessee wttpppeeee/sepeepe https//1////eeeea1laa.. html
[69] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec. Graph convolu- tional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983, 2018.
[70] W. Zellinger, A. Moser, T. Grubinger, Lughofer, T. Natschläger, and S. Saminger-Platz. Robust unsupervised domain adaptation for neural networks via moment alignment. Information Sciences, 483:1744-191, 2019. ISSN 0020-0255. doi: http:://oi.orrg.g. 1016/ 2019.01 .255. http://www..iiencnerrre....... com/ wcweecceeatiicceoo 00000000000000000000000000000000
[71] C. X. T. L. Zengfeng Huang, Shengzhong Zhang and M. Zhou. Scaling up graph neural networks via graph coarsening. In In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD '21), 2021.
[72] Q. Zhu, N. Ponomareva, J. Han, and B. Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 27965-27977. Curran Associates, Inc., 2021. URL / new.eeeddnnnn.uuipp...... newrips cc/
15


Reviews:
[{"review_id": "bHTn3dS_qV-", "reviewer": "Reviewer_k3VB", "summary": "This paper presents a simple and intuitive regularization technique to make graph networks generalize better to graphs with different sizes, by employing coarsened representations of the same graph and encouraging alignment of node embeddings between such graphs.\n\n**EDIT after rebuttal:**\n\nI thank the authors for clarifying important aspects of the evaluation procedure. It appears my assumptions were incorrect. I therefore recommend that the paper is accepted, as it provides a simple, clear, novel and effective mechanism to tackle an interesting problem for the graph machine learning community, something which is rare these days.", "questions": "- Section 4: we have no details about the experimental procedure used here. Which lambda values have been used here to produce Table 1? Maybe it would be better to include this analysis in Section 5, so as to improve the overall organization of the paper.\n- How does the distribution over the sizes of the graphs changes after pre-processing? This analysis could be interesting in datasets where graphs' sizes greatly vary, e.g. social datasets from TUDataset benchmarks page.\n- From Section 3.1., why not trying a single experiment with much higher coarsening ratios? This could be a nice addition to the paper. Social datasets could be a good option here as well.", "limitations": "Limitations of the paper mainly lie in the experimental results, which may be invalid if my argument is correct.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It is rare to find and review a paper which clearly presents a simple, intuitive and sensible idea to this kind of conferences. Overall, it was a pleasure to read and very clear under all aspects. The paper seems technically sound, although it is not clear how the specific choice of CKA influences the results, as it compares graph representations of original and coarsened graphs which have different dimensions (if my understanding is correct). The underlying motivations of the paper is clear and the proposed solution seems simple enough to be used in everyday research/industrial contexts. Perhaps it is not very clear what is the computational complexity of the regularization loss, and the authors may want to consider Section 4 after the experimental setup is introduced (see my first question below).\n\nDespite the paper being of high quality in many respects, I have serious concerns about the experimental protocol which led to the creation of Table 3, the main empirical evaluation of the paper. From lines 219-234, it emerges that most hyper-parameters where chosen from [6], which is reasonable as long as the empirical setup stays the very same. \n\nWhat appears definitely less reasonable and fundamentally wrong seems to be:\n- using the same settings of $\\lambda$ and $C$ for all datasets and models after looking at a single dataset (see lines 224-225) and Table 3 in the appendix B\n- lack of information, either in the appendix or in the main paper, about the values of $\\lambda$ cross-validated against the $\\textbf{validation}$ set\n- Evidence, by looking at Table 4 (caption, main paper) and Tables 2,3 (appendix B) that the hyper-parameters have been set after looking at the MCC performances on the $\\textbf{test}$ set. This would mean that the authors cherry-picked the results that maximize the performances on the test, rather than choosing them on the validation set. The authors are strongly encouraged to honestly and openly comment on this; it is possible that my evaluation is incorrect, but the combination of lines 275-277 with 224-225, together with the caption of Table 4, seems to point in this direction.\n\nMinor comments:\n\n- while one usually assumes that the coarsening ratio reflects the percentage of retained nodes, it may be helpful to explicitly write this in the paper.\n- It is known that a structure-agnostic baseline can produce state of the art results on PROTEINS, whereas it struggles on NCI1 for instance. It may have been a good idea to make an hyper-parameter study on the latter rather than the former dataset (but on the validation set)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "T6LZ8EJaoxP", "reviewer": "Reviewer_MVo5", "summary": "The paper proposes a new regularization strategy for improving size generalization in GNNs. The high-level idea consists of applying coarsening algorithms to original training data and then enforcing node embeddings from the original graph and coarsened ones to be closer. The paper considers four benchmarks for graph classification to assess the effectiveness of the proposal.\n\n", "questions": "- As stated in Section 3.1, the proposal assumes labels are not too sensitive to size. Is there any connection between this assumption and the chosen benchmarks? Why is the proposed method only validated using four molecular datasets?\n- It would be helpful to have an ablation study considering different discrepancy metrics. For instance, would simple distance-based metrics obtain good results? \n- The proposal seems to have the potential for improving pre-training. When evaluating existing strategies, people often split molecules according to their scaffold [1]. Showing gains to that task would increase the impact of the proposal.\n- Accuracy results could go in the appendix.\n- Showing training times would support the claim that the proposal incurs a 50% overhead.\n\n[1] https://arxiv.org/pdf/1905.12265.pdf", "limitations": "The paper briefly describes the limitations of the proposal. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper reads well and the proposed method is rather simple and general. Also, the problem of interest seems relevant. \n\nHowever, the paper lacks stronger motivation behind some design choices, such as graph coarsening algorithms and discrepancy metrics. For instance, CMD is chosen because \"it has proven to be successful and stable as a regularization term for non-linear models\".  Also, the experimental setup is weak as it only includes four molecular datasets, and follows an existing setup (Bevilacqua et. al., 2021). Moreover, the analysis section provides no principled assessment of the method, mostly showing that the proposed regularization somehow affects node representations.  \n\nStrengths\n- Simplicity: the idea is somehow intuitive even though it is not theoretically grounded.\n- Promising results\n\nWeaknesses \n- Limited evaluation setup\n- Poor understanding regarding the applicability of the proposal (only general comments are made in Section 3.1 --- Limitations) \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9Bxcs1YmGip", "reviewer": "Reviewer_1c5i", "summary": "The paper focuses on how to generalize GNNs to graphs of different sizes in graph classification. Previous works either add an ad-hoc strategy or require access to test graphs. In this work, the authors propose a regularization method based on graph coarsening techniques to improve the size-generalization of GNNs for graph classification. Empirical results show that the performance will be improved up to 30% with the proposed regularization method. ", "questions": "The paper uses the SGC coarsening algorithm in the experiments. Do the authors try other coarsening methods and evaluate how the coarsening algorithm affects the regularization performance?", "limitations": "The authors discuss the limitation in Sec 3.1 about the assumption that there are some size-invariant properties that determine the label. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper proposes a regularization strategy that improves the size-generalization ability of GNNs for graph classification. \n* Empirical results show that GNN models with the proposed regularization strategy achieve comparable or better size-generalization performance than baselines. \n\nWeaknesses:\n* The method is straightforward and the novelty is limited. The paper combines existing coarsening techniques and an existing metric (i.e. CMD) for the regularization. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept