On Size Generalization in Graph Neural Networks
Authors: Gilad Yehudai
Ethan Fetaya
Eli Meirom
Gal Chechik
Haggai Maron
Venue:  (2021)
Keywords: graph neural networks
gnn
generalization
Weisfeiler-Lehman

Abstract: Graph neural networks (GNNs) can process graphs of different sizes but their capacity to generalize across sizes is still not well understood. Size generalization is key to numerous GNN applications, from solving combinatorial optimization problems to learning in molecular biology. In such problems, obtaining labels and training on large graphs can be prohibitively expensive, but training on smaller graphs is possible. 

This paper puts forward the size-generalization question and characterizes important aspects of that problem theoretically and empirically.
We prove that even for very simple tasks, such as counting the number of nodes or edges in a graph, GNNs do not naturally generalize to graphs of larger size. Instead, their generalization performance is closely related to the distribution of local patterns of connectivity and features and how that distribution changes from small to large graphs. Specifically, we prove that for many tasks, there are weight assignments for GNNs that can perfectly solve the task on small graphs but fail on large graphs, if there is a discrepancy between their local patterns. We further demonstrate on several tasks, that training GNNs on small graphs results in solutions which do not generalize to larger graphs. We then formalize size generalization as a domain-adaption problem and describe two learning setups where size generalization can be improved. First, as a self-supervised learning problem (SSL) over the target domain of large graphs. Second as a semi-supervised learning problem when few samples are available in the target domain. We demonstrate the efficacy of these solutions on a diverse set of benchmark graph datasets. 

Under review as a conference paper at ICLR 2021
ON SIZE GENERALIZATION IN GRAPH NEURAL NET- WORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) process graphs of different sizes but their capacity to generalize across sizes is still not well understood. Size generalization is key to numerous GNN applications, from solving combinatorial optimization problems to learning in molecular biology. In such problems, obtaining labels and training large graphs can be prohibitively expensive, but training smaller graphs is possible.
This paper puts forward the size-generalization question and characterizes impor- tant aspects of that problem theoretically and empirically. We prove that even for very simple tasks, such as counting the number of nodes or edges in a graph, graphs of larger size. Instead, their gen-
GNNs do not naturally generalize eralization performance is closely related to the distribution of local patterns of connectivity and features and how that distribution changes from small to large graphs. Specifically, we prove that for many tasks, there are weight assignments for GNNs that can perfectly solve the task on small graphs but fail on large graphs, if there is discrepancy between their local patterns. We further demonstrate on several tasks, that training GNNs on small graphs results in solutions which do not generalize larger graphs. We then formalize size generalization adaption problem and describe two learning setups where size generalization can be improved. First, as self-supervised learning problem (SSL) over the target domain of large graphs. Second as a semi-supervised learning problem when few samples are available in the target domain. We demonstrate the efficacy of these solutions on a diverse set of benchmark graph datasets.
domain-
INTRODUCTION
Graphs are flexible representation, widely used for representing diverse data and phenomena. Graph neural networks (GNNs) Deep models that operate over graphs - have emerged as a promi- nent learning model (Bruna et al. 2013 Kipf and Welling, 2016 Veličković et 2017). They are used in natural sciences (Gilmer et al. 2017). social network analysis (Fan et al. 2019). for solving difficult mathematical problems (Luz al. 2020) and for approximating solutions combinatorial
optimization problems (Li et al. 2018).
In many domains, graphs data vary significantly in size. This is the case for molecular biology, where molecules represented as graphs over atoms as nodes span from small compounds to proteins with many thousands of nodes. It is even more severe in social networks, which can reach billions of nodes. The success of GNNs for such data stems from the fact that the same GNN model can process input graphs regardless of their size. Indeed, it has been proposed that GNNs can generalize to graphs whose size is different from what they were trained on. but it is largely unknown in what problems such generalization occurs. Empirically, several papers report good generalization performance Veličković et al. (2019), show that size generalization can fail on several simple graph algorithms, and can be improved by using task-specific training procedures and specific architectures.
specific tasks (Li al.) 2018 Luz et al. 2020). Other papers, like
Given their flexibility to operate on variable-sized graphs, A fundamental question arises about generalization in GNNs: "When do GNNs trained on small graphs generalize to large graphs?"
Aside from being an intriguing theoretical question, this problem has important practical implica- tions. In many domains, is hard to label large graphs. For instance, in combinatorial optimization

---

Under review as a conference paper at ICLR 2021
problems, labeling large graph boils down to solving large and hard optimization problems. In other domains, it is often very hard for human raters to correctly label complex networks. One approach to this problem could have been to resize graphs into homogeneous size. This is the strategy taken in computer vision, where it is well understood how to resize an image while keeping its content. Unfortunately, there are effective resizing procedures for graphs. It would therefore be extremely valuable to develop techniques that can generalize from training on small graphs.
As we discuss below, a theoretical analysis of size generalization is very challenging because it depends on several different factors, including the task, the architecture, and the data. For tasks, we argue that it important to distinguish two types of tasks, local and global. Local tasks can be solved by GNNs whose depth does not depend on the size of the input graph. For example, the task of finding a constant-size pattern. Global tasks require that the depth of the GNN grows with the size of the input graph. For example, calculating the diameter of a graph. While there are a few previous works that explore are by far the most widely used GNN models today and are therefore the focus of this paper.
GNNs (e.g.. [Tang et al. (2020), constant depth GNNs
In this paper, we focus on GNNs with constant depth and study the ability of the most expressive message passing neural networks (Xu et al., 2018 MMrris et al.) 2019) to generalize to unseen sizes. Our key observation is that generalization to graphs of different sizes is strongly related to the distribution of patterns around nodes in the graphs of interest. These patterns, dubbed d-patterns (where d is the radius of the local neighborhood), describe the local feature-comnectivtty structure around each node, as seen by message- passssgggninngggg neural networks and are defined in Section
We study the role of d-patterns both empirically and theoretically. First, we theoretically show that when there is significant discrepancy between the d-pattern distributions, GNNs have multiple global minima for graphs of a specific size range, out of which only a subset of models can generalize well larger graphs. We complement our theoretical analysis with an experimental study and show that GNNs tend to converge to non gonggeeerali global minima, when d-patterns from the large graph distribution are not well-represented in the small graph distribution. Furthermore we demonstrate that the size generalization problem is accentuated in deeper GNNs.
Following these observations, in the final part of this paper, we discuss two learning setups that help improve size- teaeeenneraizztion by formulating the learning problem as a domain adaptation problem: (1) Training the GNNs on self-supervised tasks aimed at learning the dl-pattern distribution of both the target (large graphs) and source (small graphs) domains. We also propose a novel SSL task that addresses over-fitting of d d-patterns. (2) A sumi-supervised learning setup with a limited number of labeled examples from the target domain. The idea behind both setups is to promote convergence of GNNs to local/glohal minima with good size generalization properties. We show that both setups useful in series of experiments on synthetic and real data.
To summarize, this paper makes the following contributions. (1) We identify a size generalization problem when learning local tasks with GNNs and analyze it empirically and theoretically. (2) We link the size-generalization problem with the distribution of d-patterms and suggest to approach it as domain adaptation problem (3) We empirically show how several learning setups help improve size generalization.
2 RELATED WORK
Size generalization in set and graph learning. Several papers observed successful generalization across graph sizes, but the underlying reasons were not investigated (Li et al.) 2018 Maron al. 2018 Luz et al. 2020). More recently, (Veličković et al. 2019) showed that when training GNNs to perform simple graph algorithms step by step they generalize better to graphs of different sizes. Unfortunately, such training procedures cannot be easily applied to general tasks. Knyazev et al. (019) studied the relationship between generalization and attention mechanisms. (Tang et al. (2020) observed two issues that can harm generalization: (1) There are tasks for which constant number of layers is not sufficient. (2) Some graph learning tasks are homogeneous functions. They then suggest new GNN architecture to deal with these issues. Our work is complementary to these works as it explores another fundamental size generalization problem, focusing on constant depth GNNs. For more details on the distinction between constant depth and variable depth tasks Appendix A Several works also studied size generalization and expressivity when learning set-structured inputs (Zweig and Bruna 2020: Bueno and Hylton 2020). On the more practical side, Joshi et al. 2019
2

---

Under review as a conference paper at ICLR 2021
Joshi et al. 2 study the combinatorial problem of traveling salesman and whether it is possible to generalize to larger sizes. [Corso et al. (222)) study several multitask learning problems on graphs and evaluate how the performance changes as the size of the graphs change.
Expressivity and generalization in graph neural networks. (Xu et al, 2018 Morris et al.) 2019) established fundamental connection between message-passing neural networks and the Weisfeiler- Leman (WL) wraph-isomorphism test. We use similar arguments to show that GNNs have enough
expressive power to solve task on set of small graphs and fail on it a set of large graphs.
Several works studied generalization bounds for certain classes of GNNs (Garg et al. 2020 Puny
al. 2020 Verma and Zhang 2019), but did not discuss size- mizz-genrralization [Sinha al. (2020) proposed a benchmark for assessing the logical generalization abilities of GNNs.
3 THE SIZE GENERALIZATION PROBLEM
We now present the main problem discussed in the paper, that is, what determines if a GNN gener- alizes well graphs of sizes not seen during training. We start with simple motivating example showing the problem on single layer GNNs. We then show that the question of size generalization actually depends on d-patterns, the local patterns of connectivity and features of the graphs, and not only on their actual size.
Setup. We are given two distributions over graphs P1, Pg that contain small and large graphs ac- cordingly, and a task that can be solved with 0 error for all graph sizes using a constant depth GNN. We train a GNN on a training set S sampled i.i.d from P1 and study its performance on P2.
GNN model. We focus on the first order GNN (I-GNN) architecture from Morris al. (019)) defined in the following way:
W 1
h( +
Σ (EN(0)
w (t-1) + b
Here, h1 is the feature vector of node after t layers, ((()) w E ER 1xd, ((t) E Rd denotes the parameters of the t-th layer of the GNN, and o is some non-linear activation (e.g ReLU). It was shown in Morris et al. (2019) that GNNs composed from these layers have maximal expressive power with respect to all message-passing neural networks. In the experimental section we also experiment with Graph Isomorphism Network (GIN) (Xu et al. 2018). For further details on GNNs see Appendix A In this work we use the most expressive GNN variants that use the "sum" aggre- gation function. Using a "max" or "mean" reduces the expressive power of the network, making not powerful enough to solve simple counting problems (e.g. counting edges or computing node degrees). On the other hand, these networks give rise to slightly different definitions of patterns and can generalize better some cases as shown (Veličković et al. 2019). yet still suffer from size overfit. Exploring these networks is beyond the scope of this work.
3.1 SIZE GENERALIZATION IN SINGLE-LAYER GNNS
We start our discussion on size generalization with a theoretical analysis of a simple setup. We consider a single-layer GNN and an easy task and show that: (1) The training objective has many different solutions, but only small subset of these solutions generalizes to larger graphs (2) Simple regularization techniques cannot mitigate the problem. This subsection serves as a warm-up for the next subsections that contain our main results.
Assume we train on distribution of graphs with a fixed number of nodes n and a fixed num- ber of edges m. Our goal is to predict the number of edges in the graph using a I-GNN with a single linear layer and additive readout function, for simplicity also consider the squared loss. The objective boils down to the following function for any graph G in the training set::
[(w1, W2, G) (Euevia) [w] F. + EvEN(w) W2 Fy + b) v) Here, G is an input graph, V(G) are the nodes of G, (D)) are all the neighbors of node v. W1, wy and b are the train- able parameters, y is the target (m in this case) and x, is the node feature for node v. Further, assume that have additional information on the nodes, so we can just embed each node
3

---

Under review as a conference paper at ICLR 2021
one-dimensional feature vector with fixed value of 1. In this simple case, the trainable parameters are also one-dimenii We note that the training objective can also be written in the follow- ing form L(w1, W2, b; G) = (nws + 2mar + nb - m) and that one can easily find its solutions space, which is an affine subspace defined by wy m mm--(wr +8) In particular, the solutions with b+ wi = O, W2 = 1/2 are the only ones which do not depend on the specific training set graph size n, and generalize graphs of any size. It can be readily seen that when training the model graphs of fixed size (fixed m, n). gradient descent will have no reason to favor one solution over another and we will not be able to generalize. We also note that the generalizing solution is not always the least norm solution (with respect to both L1 and L2 norms) so simple regularization will not help here. On the other hand, it easy show that training on graphs with different number of edges will favor the generalizing solution. As we will see next, the problem gets worse when considering GNNs with multiple non-linear layers, and this simple solution will not help in this case: we can train deeper GNNs on wide variety of sizes and the solution will not generalize to other sizes.
2tma
3.2 d-PATTERNS
We wish to understand theoretically when does a GNN which was trained on on graphs with a small number of nodes can generalize to graphs with a large number of nodes. To answer that question, we first analyze what information is received by each node in the graph from its neighboring nodes after a graph processed by a GNN with T layers. is easy to see that every node can receive information about its neighbors which are at most T hops away. We also know that nodes do not have full information about their order T environment. For example, GNNs cannot determine if a triangle is present in a neighborhood of a given node Chen et al. (2020). In order to characterize the exact information that can be found in each node after a ' layer GNN, we use the definition of the WL test, specifically its iteration structure, which has the same representational power as GNNs (see Xu et al. (2018); ) Morris et al.) (2019),, For more details on the WL test see Appendix A
Definition 3.1 (d-patterns). Let C be finite set of node features and N E N. For d 2 0 we define the set of d-patterns Pa on graphs with maximal degree N and node features from C. The definition is recursive in the following way: For d = 0, Po C. We define Pa to be the set of all tuples (a, b) where a E Pa-1 and b is in multisets of size at most N consisting of elements from Pa-1-
Les G = (V, be a graph with maximal degree N and node feature Co E C for every node v E EV. We define the d-pattern of a node v E V for d 2 0 recursively: For d = O, its O- pattern is Cy. For > we say that with é neighboring d d patterns has a d-pattern p = (pe, ((ii, Mp.,) .................. (Pie, mp.,) }}) iff node v has (d - 1)-pattern Pe and for every j E {l..... e} the number of neighbors of u with (d - 1)-patterm Piş is exactly mp..'
The d-pattern of node is encoding of the (d 1) --pptttenss of itself and of its neighbors. For example, assume a graph has a maximal degree of N and all the nodes start with the same node feature. The 1-pattern of each node is its degree. The 2-pattern of each node is for each possible degree E (1...., N} the number of neighbors with degree i. In the same manner, the 3-pattern of a node is for each possible 2-pattern, the number of its neighbors with this exact 2-pattern. The definition of d-patterns can naturally be extended to the case of unbounded degrees. We have the following theorem which connects the d-patterns with the expressive power of GNNs:
Theorem 3.2. Any function that can be represented by a d-layer GNN is constant on d-patterns. In particular, the theorem shows that for any two graphs (of any size) and two nodes, one in each graph, if the nodes have the exact same d-pattern, then any d-layer GNN will output the same result for the two nodes. The full proof can be found in Appendix BJ and follows directly from the analogy between the WL algorithm (see Appendix A and d d-patterss. Thm. [322 implies that d d-patterns don't t represent more expressive power than GNN. In the next subsection, we prove that GNNs can exactly compute d-patterns, and show that this capacity is tightly related to size generalization. It is also easy to see from the definition of d-patterns and the proof of Theorem 2 from Morris et al. (2019) that d' d-patterns exactly represent the expressive power of GNNs (with additive aggregation). thus this definition is natural tool to study the properties of GNNs, such as size generalization.
3.3
GNNS MAY OVERFIT d-PATTERNS
We can now connect the size generalization problem to the concept of d-patterns. We start with an example: consider a node prediction task in which output is specified for each node in an input
4

---

Under review as a conference paper at ICLR 2021
graph, and is solvable by a d-layer GNN. To perfectly solve this task, the model should produce the correct output for the d-patter of all the nodes in the training set. Testing this GNN on a different set of graphs will succeed if the test set has graphs with similar d-patterns to those in the training set. Note that this requirement is not related to the size of the graphs but to the distribution of the d-patterns of the nodes in the test set.
In the following theorem we show rigorously, that given a set of d-patterns and output for each such pattern, there an assignment of weights to a GNN with (d) layers that perfectly fits the output for each pattern. We will then use this theorem in order to show that, under certain assumptions on the distribution of d-patterns of the large graphs, GNNs can perfectly solve task on a set of small graphs, and completely fail on a set on large graphs. In other words, we show that there are multiple global minima for the training objective that do not generalize to larger graphs.
Theorem 3.3. Let C be a finite set of node features. P be a finite set of d-patterns on graphs with maximal degree N E N, and for each pattern p E P let yp E 1-1,,]] be some target label.
Then there exists a I-GNN F with d + layers, width bounded by max (NN + 1)a 1C1.2 and ReLU activation such that for every graph G with nodes vi..... Una corresponding d-patterns P1.....P2 S P and node features from C, the output of F on node U; is exactly Up..
The full proof is in Appendix B Note that the width of the required GNN from the theorem is not very large if d is small, where d represents the depth of the I-GNN. In practice, shallow GNNs are very commonly used and are proven empirically successful, while training deep GNNs was shown to be hard due to many problems like over-smoothing (Zhao and Akoglu 2019).
Using the above theorem we claim that there are assignments of weights to GNN that cannot sezzegenerallize,. that is, given a specific task, the GNN succeeds on the task for small graphs (up to some bound) and fails larger graphs, as long there is notable discrepancy between their d-patterns distributions:
Corollary 3.4. Let P1 and P2 be distributions of small and large graphs respectively with finite support, and let pe-pat be the distribution of d-patterns over small graphs and similarly pd-pat pat for large graphs. For any node prediction task which is solvable by I-GNN with depth d and e > 0 there exists a I-GNN with depth at most + that has 0-1 loss smaller then on P1 and 0-1 loss A on P2, where
(Cc)
max A:P put
Pd pat (A).
pd-pat
(1)
(A)<c
Here, A is a set of d-patterns and P(A) is the total probability mass for that set under P.
Intuitively, large A means that there exists a set of d-patterns that have a low probability for small graphs and high probability for large graphs. Corollary 3.4 implies that the major factor in the success of GNN to generalize to larger graphs is not the graph size, but the distribution of the d- patterns. Different distributions of d-patterns lead to large A and thus to bad generalization to larger graphs. On the other hand, from Thm. 3.2 we immediately get that similar distributions of d-patterns imply that every GNN model that succeeds on small graphs will also succeed on large graphs, since GNNs are constant on d-patterns:
Corollary 3.5. In the setting of Corollary 3.4 also assume that all the patterns that have a positive probability in Pd pdl-pat also have a positive probability in pd-vat, Then, for any node prediction task solvable by depth d GNN, any 1 - GNN that have O loss (wort the O- 1 loss) on P1 will also have O loss on Pg.
Examples. Corollary 3.4 shows that even for simple tasks, GNN may fail, here are two simple examples. (i) Consider the task of calculating the node degree. From Corollary (344 there is a GNN that successfully output the degree of nodes with max degree up to N and fails nodes with larger degrees. Note that this problem can easily be solved for any node degree with a 1-layer GNN. (ii) Consider some node regression task, when the training set consists of graphs sampled i.i.d from an Frdos-Renyy graph G(n. p) [ and the test set contains graphs sampled i.i.d from G(2n, p). In this case, GNN trained on the training set will be trained on graphs with an average degree np, while the test set contains graphs with an average degree 2np. This means that the di d-patterns in the train and test set are very different, and by Corollary 3.4 the GNN may overfit.
Graphs with nodes such that each edge exists with probability p.
5

---

Under review as a conference paper at ICLR 2021
Graph prediction tasks. Our theoretical results discuss node prediction tasks. We note that they are also relevant for graph prediction tasks where there is a single output to each imput graph. The reason for that is that in order to solve graph prediction tasks, a GNN first calculates node features and then pools them into a single global graph feature. Our analysis shows that the first part of the GNN, which is responsible for calculating the node features, might not generalize large graphs. As result, the GNN will generate an uninformative global graph feature and the GNN will fail on the original graph prediction task. In the experimental sections, we show that the size generalization problem is indeed relevant for both node and graph prediction tasks. Here is formal statement regarding graph prediction tasks, the full proof can be found in Appendix B
Corollary 3.6. Let P1 and P2 be distributions of small and large graphs respectively with finite support. Let Pf- pat be the distribution of d d-patterns over small graphs and similarly Pa pd-pat for large graphs, and assume that the supports of Pf-pat and Pa-pat are disjoint. For any graph prediction task solvable by a I-GNN with depth d and summation readout function, there exists a 1-GNN with depth at most d 4-3 3 that perfectly solves the task on P1 and fails on all graphs from Pa.
Relation to Morris et al. (2019; : Xu et al. (2018). We note that Theorem 3.3 and Corollary are somewhat related to the expressivity results in (Xu et al., 2018, Morris et al. 2019) that show that GNNs can be as powerful as the WL test. Here, we show that the expressive power of GNNs can cause negative effects when there is a discrepancy between the training and test sets.
3.4 EMPIRICAL VALIDATION
In the previous subsection we have shown that for any node task, and any two datasets of graphs with different sizes that significantly differ in their d-patterns distributions, there is a I-GNN that successfully solves the task one dataset but fails on the second. In this subsection, we show empirically that reaching these "overfitting" GNNs is actually very common. Specifically, the size- overfit phenomenon is prevalent when the d-patterns of in the large graph distribution are not found in the small graph distribution. We also show that GNNs can generalize to larger graphs if the distribution of d-patterns remains similar to the distribution of patterns in the small graphs.
To show this, we use a controlled regression task in a student-teacher setting. In this setting, we sample "teacher" GNN with random weights, freeze the network, and label each graph in the dataset using the output of the "teacher" network. Our goal is to train a "student" network, which has the same architecture as the "teacher" network, to fit the labels of the teacher network. The advantages of this setting are two-fold: (1) A solution is guaranteed to exist: We know that there is weight assignment of the student network which perfectly solve the task for graphs of any size. (2) Generality: It includes all tasks solvable by constant depth GNNs. We discuss more settings below.
Architecture and training protocol. We use I-GNN as defined in (Morris et al. 2019). The number of GNN layers in the network we use is either 1, or 3; the width of the teacher network is 32, and of the student network 64, providing more expressive power to the student network. We obtained similar results when testing with width of 32, same the teacher network. We use summation readout function followed by a two-layer fully connected suffix. We use ADAM with learning rate 10-3. We performed a hyper-parameters search on the learning rate and weight decay and use validation-based early stopping on the source domain (small graphs). The results are averaged over 10 random seeds. All runs used Pytorch Geometric (Fey and Lenssen 2019) on NVIDIA DGX-1.
Results. Fig. D compares the loss of GNNs as the distribution of d-patterns changes, for the task of teacher-student graph level regression. The model was trained on graphs generated using the G(n, p) model. We show the normalized L2 loss computed on test, where output is normalized by the average test-set (target) output. The left panel shows the test loss when training on n E [40, 50] and p 0.3 and testing on G(n, p) graphs with = 100 and p varying from 0.05 to 0.5. In this experiment, the expected node degree is np, hence the distribution of d-patterns is most similar to the one observed in the training set when p 0.15. Indced, this is the value of p where the test loss is minimized. The right panel is discussed in the caption. These results are consistent with Corollary 3.4 since when the distributions of d-patterns are far the model is not able to generalize well, and it does generalize well when these distributions are similar.
To give further confirmation to the effect of the local distributions the generalization capabilities of GNN we conducted the following two experiments: (1) We tested on the teacher-student setup with 3-layer GNN on graphs of sizes uniformly from 40, -. 50 and sampled from G(n, 0.3).

---

Under review as a conference paper at ICLR 2021
byee layers
ayer lnyers three layers
Average loss (log scale)
Average locs
-1-
-1
-2
-3
-4
0.05 0.10
0.20 0.25 0.30 0.40 6.45 0.50 test
60
120
Train graph size
Figure The effect of graph size and d-pattern distribution on generalization in G(n.p) graphs. (left) The effect of distribution of d-patterns. Train on n drawn uniformly from [40, 50) and p 0.3 test on n 100 and varying p (right) The effect train-graph size. Train on drawn uniformly from [40, xr where r varies and p 0.3; test on 150, p = 0.3.
Average loss (log scale)
2-
loss
0
-1
-1-
-2
60
80
100
120
140
50
75
100
125
150
175
200
225
250
Test graph
graph
Figure 2: Constant training size and varying test size with and without normalization. Left: constant p which leads to different d-patterns. Right: p is normalized to keep d d-patterns distribution similar.
We tested on graphs sampled from G(N, 0.3) where N varies from up to 150. is evident that as the graph size in the test set increases, the model performs worse. (2) We did the same test as in (1), but this time we normalize p on the test set so that p N 15, which the approximate ratio for the training set. Here we even went further to train up sizes N 250. In this experiment, the GNN successfully generalized to larger graphs, since the local distributions of train and test set are indeed very similar. For the results see Fig.
We also tested on the tasks of finding the max clique in a graph, calculating the number of edges, and the node prediction tasks of calculating the node degree, and the student-teacher task at the node level. In addition, we tested on the popular GIN architecture (Xu al. 2018). and show that the size generalization problem also occurs there. We also tested ReLU, Tanh, and sigmoid activations. See additional experiments in Appendix C
TOWARDS IMPROVING SIZE- SIZE-GENERALIZATIOON
The results from the previous section show that the problem of size generalization to the size of the graph in terms of the number of nodes edges but to the distribution of d-patterns induced by the distributions from which the graphs are sampled. Based on this observation, we now formulate the size generalization problem techniques from domain adaptation and suggest two approaches to improve size generalization. (I) Self-supervised learning the target domain (large graphs) and (2) Semi-supervised learning with a few labeled target samples. We consider the DA setting where we are given two distributions over graphs: source distribution Ds (say, for small graphs) and target distribution Dr (say, for large graphs). We consider two settings. First, the unlabeled DA setting, where we have access to labeled samples from the source D3 but the target data from Dy is unlabeled. Our goal is to infer labels
only related
domain adaptation (DA) problem. We then build on

---

Under review as a conference paper at ICLR 2021
test dataset sampled from the target Dy. Second, we consider a semi-supervised setup, where also have access to a small number of labeled examples from the target Dr.
Size generalization with Self-supervised learning. In Self-supervised learning (SSL) for DA, a model is trained on unlabeled data to learn a pretext task, which is different from the main task at hand. If the pretext task is chosen wisely, the model learns useful representations (Doer- scc et al.] 2015; Gidaris et al.] 2018) that can help with the main task. Here, we train the pre- text task on both the source and target domains,
was done for images and point clouds (Sun)
eet al. 2019 Achituve et al.] 2020). The idea is that the pretext task aligns the representations of the source and target domains leading to better predictions of the main task for target graphs. (For a detailed review of the training procedures and the losses see Appendix E Given pretext task we consider two different train- ing procedures: (1) Multi-task learning (MTL): parallel training of the main task on a source domain and a pretext task on both the source of target domain ( YYuu et al. 2020). In this case, the architec- main GNN that acts as a feature extractor and two
ture consists secondary networks (heads) that operate on the extracted features and try to predict the main task and the pretext task. (2) Pretraining (PT): in this procedure (Hu al. 2019), the GNN feature extractor is trained until convergence on the pretext task on both the source and target examples. Then, the GNN part is frozen, and only the head of the model is trained on labeled examples from the source.
Figure 3: Left: a graph with node features represented by colors. Right: A tree that rep- resents the d-patterns for the black node. The tree descrip- tor is the number of nodes from each class in each layer of the tree.
Pattern-tree pretext task. We propose novel pretext task which is motivated by the definition of d-patterns. We do that by con- structing a tree that fully represents the d d-patterns of each node (see e.g.,uu Xu et al. (2018)). ). We then calculate a descriptor of the tree, which is vector containing counts of the number of nodes from each class in each layer of the tree. We treat this descriptor as the target label to be reconstructed by the SSL task. For more details see Figure 3 Intuitively, in order to be successful on a task on graphs, the GNN needs to correctly represent the pattern trees of the nodes of the graphs. This means, that to generalize to the target domain D,, the GNN needs to be forced to represent pattern trees from both the source and the target distributions. For more details about the construction of the pattern tree see Appendix [D] In short, each tree corresponds to a d- d-pattern in the following way: the d-pattem tree of a node can be seen as a multiset of the children of the root, and each child is multiset of its children, etc. The pattern tree is different description of the d-pattern of a node. This means that a GNN that successfully represent a pattern tree also represents its corresponding d-pattern, thus connecting this SSL task to the theory from Sec.
Semi-supervised setup. We also consider a case where small number of labeled samples are available for the target domain. A natural approach is to train an SSL pretext task on samples from both the source and target domain, and train the main task on all the labeled samples available. We tested this setup with 1, 5, or 10 labeled examples from the target domain.
4.1 EXPERIMENTS
Architecture and training protocol. The setup is the same in Subsection 3.4 with the following changes. We use a three-layer GNN in all experiments. Multi-task learning is used with equal weight to the main and SSL tasks. In the semi-supervised setup, we used an equal weight for the main task and the labeled examples from the target domain.
Baselines. We compare our new pretext task to the following baselines: (1) Vanilla: standard training on the source domain; (2) HomoGNN (Tang et al.) 2020) a homogeneous GNN without the bias term trained on the source domain; (3) Graph autoencoder (GAE) pretext task (Kipf and Welling, 2016); (4) Node masking (NM) pretext task from Hu et al.) (2019) where at each training iteration we mask 10% of the node features and the goal is to reconstruct them. In case the graph does not have node features then the task was to predict the degree of the masked nodes. (5) Node metric learning (NML): we use metric learning to learn useful node representations. We use a corruption function that given graph and corruption parameter p E [0. [0. replaces pl of the edges with random edges, and thus can generate positive (p = 0.1) and negative (p = 0.3) examples for all nodes of the graph. we train with the triplet loss (Weinberger and Saul 2009
8

---

Under review as a conference paper at ICLR 2021
DATASETS
DREZER
IMDB-1 15
NCTT
NCT109
PROTEINS
TWITCH
DD
AVERAGE
SMALL GRAPHS
56.5 0.8
63.2
75.5
78.4
3..4
69.7 0.2
71.1
70.0%
VANILLL
41.1 + 6.8
66.9
4 7.8
65.9
4.3
68.9
+ 3.8
76.0 + 8.5
60.5
+ 3.6
76.3
3.2
63.5 63.3%
HOMO-GNN
40.5 6.6
56.3
+
66.0 3.7
68.8
+ 3.2
77.1
10
60.8
+ 2.3
76.8 4
63.8%
NM MIL
8.5
55.6
+ 6.8
19.9
+ 7.8
61.7
+ 5.7
78.8
+ 8.4
19.5
+ 2.8
67.4 + 5.4
59.2%
PT
50.1 7.5
51.7
6.6
55.8 1
8.2
48.4
1
60.3
57.1%
GAE MTL
19.4=114
55.5
+ 6.0
51.2
9.9
57.6
+ 9.4
79.5
11.7
62.5
5.1
67.8
+ 10.0
60.5%
GAE PT
47.1 = 10.0
54.1
6.8
58.9
1: 7.6
67.2
5.6
70.5
1 9.4
53.6
1 4.7
69
7.1
60.1%
NML MTL
46.4 9.5
54.4
4 7.0
52.3
6.3
56.2
1 6.5
78.7
6.8
57.4
1
4.1
64.7
11.9
58.6%
NML PT
48.4 = 10.7
53.8
4 6.
54.6
6.2
56.
+ 8.1
76.3
+ 8.0
54.9
2
4.7
61
15.1
57.9%
PATTERN MTL
45.6
60.5
7.5
67.9
75.8
61.6
3.5
76.8
PATTERN PT
44
4477.
61.9 +
3.2
67.8
+
11.7
74.8
+
5.7
84.7 +
5.1
64.5
2
3.3
74.9 - 5.2
67.5%
Table 1: Test accuracy of compared methods in binary classification tasks. The Pattern task with pretraining achieves the highest accuracy in most tasks and has 4% higher average accuracy than the second-best method. High variance due to the domain shift between the source and target domain.
Datasets. We datasets from Morris al. (2020) and RRozeberczzii al. (2020) (Twitch egos and Deezer egos). We selected datasets that have a sufficient number of graphs (more than 1,000) and with a non-trivial split to small and large graphs detailed in Appendix F.I In total we used 7 datasets, 4 in molecular biology (NCII, NC1109, D&D, Proteins), and of social networks (Twitch ego nets. Deezer ego nets, IMDB- MiDD-Binary). In all datasets, 50% smallest graphs were assigned to the training set, and the largest 10% of graphs assigned to the test set. We further split a random 10% of the small graphs as a validation set.
Results. Table I compares the effect of using the Pattern- tree pretext task to the baselines described above. The small graphs row presents vanilla results on a validation small graphs. The small graph accuracy on 5 out of 7 datasets larger by 15.5% than on large graphs, indi- cating that the generalization problem is indeed preva- lent real datasets. Pretraining with the d-patterns pretext task outperforms other baselines in 5 out 7 datasets, with an average 4% improved accuracy on all datasets. HOMO- GNN slightly improves over the vanilla while other pretext tasks do not improve average accuracy. Naturally, the ac- curacy here is much lower than SOTA these datasets be- cause the domain shift makes the problem much harder. In Appendix F22 show the 1-pattern distribution discrep- ancy between large and small graphs in two real datasets: IMDB (large discrepancy) and D&D (small discrepancy). task improved performance on the IMDB dataset, while not improving performance on the D& D dataset. This gives further evidence that discrepancy between the d d-patterns leads to bad general- ization, and that correctly representing the patterns of the test set can improve performance.
with
M1002 sccurn over all catarats
70-
Pattem PT
Vanilia
TEA2
049
68
66
64-
10
Num of labeled large graph examples
Mean accuracy over all datasets in Tab. [ for d-pattern pre training and no SSL (Vanilla). Correspondingly. the pattern tree SSL
Figure 4:
Tiguree4comparee the performance of vanilla training versus pretraining with the pattern-tree tree pretext task in the semi-supervised setup. The accuracy monotonically increases with respect to the number of labeled examples in both cases. Moreover, pretraining with the pretext task yields better results in the case of 0,1,5 labeled examples and comparable results in the case we use 10 labeled examples. We additionally tested on the synthetic tasks discussed in Sec. 3 and show that the pattern-tree pretext task improves in the student-teacher setting, while it does not solve the edge count or degree prediction tasks. On the other hand, adding even a single labeled sample from the target distribution significantly improves performance the synthetic tasks we tested on. For more details see Sec.
CONCLUSION AND DISCUSSION
This paper is a first step towards understanding the size generalization problem in graph neural networks. We showed that GNNs do not naturally generalize to larger graphs even on simple tasks, characterized how this failure depends d-patterss, and suggested two approaches that can improve generalization. Our characterization of d-patterns is likely to have implications to other problems where generalization is harmed by distribution shifts, and offer a way to mitigate those problems.

---

Under review as a conference paper at ICLR 2021
REFERENCES
[1] I. Achituve, H. Maron, and G. Chechik. Self-supervised learning for domain adaptation on point-clouds. arXiv preprint arXiv:2003. 12641, 2020.
[2] Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks graphs. arXiv preprint arXiv: 13/2. 2013.
[3] C. Bueno and A. G. Hylton. Limitations for learning from point clouds, 2020. URL https: 7/openrevi ew net www//tfoooaee for://ormmmm?/mm (itpmmmmiirrlll d=r x
[4] Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures? arXiv preprini urXiv:2002.040223 2020.
[5] G. Corso, L. Cavalleri, D. Beaini, P. Liò, and P. Veličković. Principal neighbourhood aggrega- tion for graph nets. arXiv preprint arXiv:2004.05718, 2020.
[6] C. Doersch, A. Gupta, and A. A. Efros. Unsupervised visual representation learning by context prediction. In Proceedings of the IEEE international conference on computer vision, pages 2015.
[7] V. P. Dwivedi, C. K. Joshi, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. arXiv preprint AxXiv:2003.0098: 2020.
[8] W. Fan, Y. Ma, Q. Li, Y. He, E. Zhao, J. Tang, and D. Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pages 417-426, 2019.
[9] M. Fey and J. E. Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1903. 02428, 2019.
[10] V. K. Garg, S. Jegelka, and Jaakkola. Generalization and representational limits of graph neural networks. arXiv preprint
2020.
[11] S. Gidaris. P. Singh, and N. Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint arXiv: /803.07728, 2018.
[12] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. arXiv preprint arXiv: 174.v0170..01222 2017.
[13] M. Grohe. Descriptive complexity, canonisation, and definable graph structure theory, vol- ume 47, Cambridge University Press, 2017.
[14] W. Hu, B. Liu, J. Gomes, M. Zitnik, P. Liang, V. Pande, and J. Leskovec. Strategies for pre- training graph neural networks. arXiv preprint arXiv:1905. 12265, 2019.
[15] C. K. Joshi, T. Laurent, and X. Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint
2019.
[16] C. K. Joshi, Q. Cappart, L.-M. Rousseau, T. Laurent, and X. Bresson. Learning tsp requires rethinking generalization. arXiv preprint arXiv:2006.07054, 2020.
[17] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: / 6009002907 2016.
[18] T. N. Kipf and M. Welling. Variational graph auto-encoders. arXiv preprint 2016.
[19] B. Knyazev, G. W. Taylor, and M. Amer. Understanding attention and generalization in graph neural networks. In Advances in Neural Information Processing Systems, pages 4202-4212, 2019.
[20] Z. Li, Q. Chen, and V. Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pages 539- 548, 2018.
10

---

Under review as a conference paper at ICLR 2021
[21] A. Loukas. What graph neural networks cannot leam: depth vs width. arXiv preprint arXiv:1907.03199, 2019.
[22] I. Luz, M. Galun, H. Maron, R. Basri, and I. Yavneh. Learning algebraic multigrid using graph neural networks. arXiv preprint arXiv:2003.05744 2020.
[23] H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman. Invariant and equivariant graph networks arXiv preprint arXiv:1812.0990 2018
[24] C. Morris and P. Mutzel. Towards a practical k-dimensional weisfeiler-leman algorithm. arXiv preprint arXiv; 1rrXiv:1004.0111 01543, 2019.
[25] C. Morris, M. Ritzert, M. Fey. W. L. Hamilton, E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602-4609, 2019.
[26] 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 on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www. gww.phlearningg....
ic
[27] E. Nachmani and L. Wolf. Molecule property prediction and classification with graph hyper- networks. arXiv preprint arXiv:2002.0022 002400, 2020.
[28] O. Puny, H. Ben-Hamu, and Y. Lipman. From graph low-rank global attention to 2-fwl ap- proximation. arXiv preprint 20Xxv:00060078455 2020.
[29] B. Rozemberczki, O. Kiss, and R. Sarkar. Karate Club:
An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs. In Proceedings of the 29th ACM Interna- tional Conference on Information and Knowledge Management (CIKM '20), page 3125-3132. ACM, 2020.
[30] K. Sinha, S. Sodhani, J. Pineau, and W. L. Hamilton. Evaluating logical generalization in graph neural networks. arXiv preprint arXiv:2003.0653 2020.
[31] Y. Sun, E. Tzeng, T. Darrell, and A. A. Efros. Unsupervised domain adaptation through self- supervision. arXiv preprint arXiv: 1825, 2019.
[32] H. Tang, Huang, J. Gu, B.-L. Lu, and H. Su. Towards scale-invariant graph-related problem solving by iterative homogeneous graph neural networks. ICML 2020 Workshop on Graph Neural Networks Beyond, 2020.
[33] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv preprint 17X1v:1710.100003, 2017.
[34] P. Veličković, R. Ying, M. Padovano, R. Hadsell, and C. Blundell. Neural execution of graph algorithms. arXiv preprint arXiv: 2019.
[35] S. Verma and Z.-L. Zhang. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1539-1548, 2019.
[36] K. Q Weinberger and L. K. Saul. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 10(2), 2009.
[37] B. Weisfeiler and A. A. Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Ten Thuchho--Tcchiichskkaya Informatsia, 209):22-16, 1968.
[38] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 1xX.:18100000226 00866 2018.
[39] Y. You, T. Chen, Z. Wang, and Y. Shen. When does self self-supervision help graph convolutional networks? arXiv preprint 201133006009136 2020.

---

Under review as a conference paper at ICLR 2021
[40] C. Yun, S. Sra, and A. Jadbabaie. Small relu networks are powerful memorizers: tight analysis of memorization capacity. In Advances in Neural Information Processing Systems, pages 15558-15569, 2019.
[41] L. Zhao and L. Akoglu. arXiv: 1909. 12223, 2019.
Pairorm: Tackling oversmoothing in gnns. arXiv preprint
[42] A. Zweig and J. Bruna. A functional perspective on learning symmetric functions with neural networks, arXiv preprint arXiv:2008.069) 06952, 2020.
A PRELIMINARIES
This section discusses two key concepts that throughout the paper: (1) Graph Neural Net- works; (2) The Weisfeiler-Lemman graph isomorphism test. At the end of the section, we also discuss the setup of constant GNN depth that we in this paper.
Notation. We denote by {(a1, Ma.)................)))) ...., (an, Ma,)) }} multiset, that is a set where we allow multi- ple instances of the element. Here d1,-.., On distinet elements, and ma, is the number of times a; appears the multiset. bold-face letters represent vectors.
A.1 GRAPH NEURAL NETWORKS
We consider the common message-passing GNN architecture 38 defined as follows: Let G
(V, E) be graph, and for each node E let (0) E IRdo be node feature vector. Then for every
t we define:
( UPDATE (1(11) (h!-"),AGG AgG (fn--D::EE (uE-D)))N()))))
Here, AGG an permutation invariant aggregation function such as summation, averaging or taking UPDATE is an update function such as MLP, and (M)) denotes the set of neighbors of node v. case the graph is directed then (wv) denotes the set of nodes with edges incoming to v. For
node prediction tasks, the output of T-layer GNN for node is h!?) while for graph prediction tasks an additional readout layer is used:
(T) READOUT h V ue vev].
where READOUT some invariant function such as summation, averaging or taking the max, pos- sibly followed by fully connected network.
In our theoretical results, we focus on the first order GNN architecture from (25) defined in following way:
h 10 =
W
W (1-1) +
Σ w(' (t-1) + ((0)
uEN(o)
Here, w((t) w E xdd, (()) Rd denotes the parameters of the f-th layer of the GNN, and is non-linear activation (e.g ReLU).. It was shown in (25) that GNNs composed from these layers have maximal expressive power with respect to all message passing neural networks. has maximal expressive
In general, focus GNNs that the popular sum aggregation power with respect to other aggregations used in message passing GNNs (38). We discuss other aggregation functions and the trade-of they present in Section 5
A.2 THE WEISFEILER-LEHNE TEST
The definition of d-patterns, which are used frequently in this paper, is closely related to the Weisfeiler-Lehman (WL) test (37 (3). The WL test is an algorithm to test whether two graphs isomorphic and recently coupled with the expressive power of GNNs. 258. It is easiest to describe WL by using an equivalent algorithm called the color-refimmment algorithm (B3) The color refinement algorithm is executed sequentially, wherein each stage the algorithm generates
12

---

Under review as a conference paper at ICLR 2021
descriptor for each node according to the descriptors of its direct neighbors. The features in each stage can be used to define equivalence classes of nodes and the process continues until these equiv- alence classes cannot be refined anymore. The final graph descriptor is histogram of the node features, and is closely related to the definition of d-patterns.
A.3 CONSTANT DEPTH VS. ADAPTIVE DEPTH TASKS
As stated earlier, multiple factors control size generalization. One important factor is the type of task: We make distinction between two types of graph tasks. (1) Tasks that can be solved by constant depth GNN; A good example for such task is determining whether a certain, constant size connectivity pattern is found in the graph (2) Tasks that require the depth of the GNN to be related to different parameters of the problem, such as the diameter of the graph. To exemplify, the task of calculating the diameter of graph
be solved with GNN only if its depth depends on the size of the graph (For more details see (32) 21)) On the other hand, tasks that require local information about each node can be solved with a constant depth GNN. We note that although there are several recent works about adaptive depth GNN, e.g. (32 27). most currently used GNNs have constant and relatively small depth (7). In this paper, we focus on the first kind of tasks that require a constant number of GNN layers. We note that the size- taee-enerraizztion problem we discuss in this paper is also relevant for the second type of tasks, but we chose to discuss the problem in the simpler setup for clarity.
B PROOFS FROM SEC. 3
Proof of Thm. 3.2
We show that from the definition of d- d-patterns, and the 1-WL algorithm (see (7)), the color given by the WL algorithm to two nodes is equal iff their d-pattern is equal. For the clear. Suppose
case of
true for d 1, the WI. algorithm at iteration give node a new color based on the colors given in iteration d - to the neighbors of v. This means, that the color of e at iteration d depends on the multiset of colors at iteration d- 1 its neighbors, which by induction is the d 1-pattern of the neighbors of v. To conclude, we use Theorem I from (25) which shows that GNNs are constant on the colors of WL, hence also constant on the d- d-patterns.
To prove Thm. 3.3 we will first need to following claim from (40) about the memorization power of ReLU networks:
Theorem B.1. Let ye Rd x R such that all the x; are distinct and ys E [--1, 1] for all Then there exists 3-layer connected ReLU neural network f ; 12d - IR with width 2 N such that fxx:) yi for every
We will also need the following lemma which will be used in the construction of each layer of the 1-GNN:
NNN- + R be function defined by f(n) = w. (win n b) where W1, W2, N and a is the ReL.U function. function Then for every y1.-..: UN E there exists W1, W2, such that (n) yn for n & N and f(n) (n N 1)yN (n N) for > N.
Lemma B.2. Let N E N and :
0
1
Proof. Define W1
b
Let as be the i-th coordinate of w2, we will define
N
a; recursively in the following way: Let 01 = yı, suppose we defined a1,- a:-1, then define a, y1 20 iaj. Now have for every n S N:
f(n) = b) nan (n 1)az ... + an Yn
13

---

Under review as a conference paper at ICLR 2021
For N write N + k for lo 2 then have:
f(n) = w2 o(w, (N + k) b) = (N + k)a1 + (N k 1)02 + .......... (I: 1)aN
yN + k(a1 + 02 + aN = Nn + k(yN aN-1 2aN (N - 1)a1)
(k + 1)yN kyN-1
Now we are ready to prove the main theorem:
Proof of Thm. 3.3 We assume w.l.o.g that at the first iteration each node is represented as a one- hot vector h of dimension |C], with its corresponding node feature. Otherwise, since there are |C] node features we can use one GNN layer that ignores neighbors and only represent each node as one-hot vector. We construct the first d layers of the 1-GNN FF by induction d. Denote by a, = |C| (N' + N the dimension the i-th layer the GNN for S i S d, and du = |C%.
The mapping has two parts, one takes the neighbors information and maps it into feature representing the multiset of d-patterns, the other part is simply the identity saving information regarding the d- d-pattern of the node itself.
The d layer structure is
h!4 = v(d+1)
w Σ uEN(1)
w:(0 b(d)
We set wil) = 10, TJ. W(() [ Oj and U(d+1) = [((++I)T o0T with I X and ((d+1) E xoNaa- For wi(0) we set w( its i-th row, [ Let 6()) be the i-th coordinate of b(d), be equal to i - (mod N) for i S N 0d-1 and zero otherwise. What this does for the first d elements of wh
Wa(d)
to be equal to en where
h(a) + EneN(w) (((n) that each dimension i hold the number of neighbors with a specific (d-1)-pattern. We then replicate this vector times, and for each replica we subtract different bias integer ranging from 0 to N - 1. To that output we concatenate the original h, (d-1)
Next we construct (d++)) R Nag Nx in the following way: Let u, (d+ be its i-th row, and Wi,j
(d+1) its j-th coordinate, We set Ui be equal to the vector W2 from Lemma B.2 with labels yı = for & (N,...,NNM[ mod N)+1}
(d+1) for every with j + & and the rest N coordinates to
and y 1 for é (i mod N) + 1.
Using the above construction we encoded the output on node e the first layer of as vector:
This encoding is such that the i-th coordinate of h. (d+1) for S i N ad-1 is equal to 1 iff node have (i mod N) + neighbors with node feature [ E {1..... [C]). The last ad-1 rows are copy of h! (d-1)
Construction of the suffix. Next, we construct the last two layers. First we note that for a node with d-pattern p there is unique vector Zp such that the output of the 1-GNN node h equal to Zp. From our previous construction one can reconstruct exactly the (d-l)-pattern of each node, and the exact number of neighbors with each (d-1)-pattem and therefore can recover the d-pattern correctly from the (d) embedding.
Finally, we use Thm. B. to construct the 3-layer fully connected neural network with width at most 2 such that for every pattern pt E P with corresponding unique representation 2p, and label y: the output of the network on Zp. is equal to ye- We construct the last two layers of the 1-GNN such that w-(++) Wild) 0, and W-(d+1) (d++)) W-(d22) b(d+2) (/d43) the matrices produced from Thm. B.1 Note that (dd+3) is the linear output layer constructed from the theorem, thus the
14

---

Under review as a conference paper at ICLR 2021
final output of the 1-GNN for node v is W(d+3) . (d+2) where to (d+2) is the output after d layers.
Proof of Corollary 3.4 By the assumption, the output of the task is determined by the d-patterns of the nodes. For each node with pattern pi let ys be the output of the node prediction task. Define
A arg
Pe Pa- (A')
(2)
A'PT pot (A')cc
By Thm. 3:3 there exists a 1-GNN such that for any d-pattern Pt E gives a wrong label and for every pattern outside A. Pj A gives the correct label. Note that we can use Thm. 3.3 since both A and A are finite, because we assumed that distributions on the graphs have finite supports. The 0-1 loss for small and large graphs is exactly P pul-pat (A) and Pa pu-pat (A) respectively.
Proof of Corollary 3.6 Let Dj and D2 be all the d-patterns that appear in graphs from P1 and Pa respectively. By the assumption that the task is solvable by a d-layer GNN, and the same reasoning as in the proof of Corollary 3.4 the output the GNN which solves the task depends only on the d d-patterns. Thus, by Thm. 3.3 there exists d 2-layer GNN that perfectly solves the task graphs with patterns from D2 and in addition sends every pattern from D2 to zero. If zero is not solution of the task for any graph from P2 are finished. Otherwise, if zero is solution of graph from Pa but not for a graph from Pi we can add an MI. after the summation readout function that outputs the identity on every input except zero, for which it outputs value which is not a solution for the task for any graph in P2. Note that this is possible since P2 has finite support. In the case that zero also solution of the task on a graph from P1. let ......... Fig be the sizes of graphs from Pz. We pick some y E R such that y since the distributions have a finite support. Now, we can change the proof so that the output of the
is not an output of any graph from P1 and P2, there is such
GNN on all patterns from D2 is equal to y. Note that now the output of any graph from P2 after the summation readout function not the correct output. In case there is an MI. after the readout function, the proof can be readily changed to account for that.
Proof or Corollary 3.5 Let h be a 1-GNN that have 0 loss on P1. In particular, for any pattern in pa-pott successfully predict the correct label. By the assumption, the patterns that appear in pol pdlpot are contained in the pattern that appear in pel-pat Using Thm. 3.2 that any 1-GNN is constant d-patterns, get that h will also succeed on the pattern from P pat hence will have 0 loss on Pg.
C ADDITIONAL EXPERIMENTS FROM SEC. 3.4
First, we consider the max-clique problem. The goal of this problem is given graph, to output the size of the maximal clique. This in general an NP-hard problem, hence a constant depth GNN will not be able to solve it for graphs of all sizes. For this task we sampled both the train and test graphs from a geometrical distribution defined as follows: given number of nodes and radius p we draw points uniformly in [0. 1j2, each point correspond to a node in the graph, and two nodes are connected if their corresponding points have a distance less than p. We further analyzed the effects of how the network depth and architecture affect size generalization.
Table 2 presents the test loss on the max-clique problem. Deeper networks are substantially more stricken due to the domain shift. If the test domain has similar pattern distribution, increasing the neural network depth from one layer to three layers results in a small decrement of at most 20% to the loss. However, if the pattern distribution is different than the train pattern distribution. such change may increase the loss by more than x. We also show that the problem is consistent in both 1-GNN and GIN architectures.
15

---

Under review as a conference paper at ICLR 2021
LGNN
GEN
Peroin /Ptcal
I-layer
2-agers
S-ayers
2-ayers
3-ayya
22.5
41.6
50.7 70.4
3.6
15.6
134.2 217.1
v2
9.6 0.4
10.6
11.7 = 1.2
9.2 9.2.100.3 0.5
10.5
0.3
11.3 133::00 0.5
Table 2: The difference is the predicted max clique size under size generalization domain shift. The train domain graphs were constructed by drawing n E [40, 50] points uniformly in the unit square, and connecting two point if their distance is less than Ptrain contain n = 100 nodes, effectively increasing their density by 2. We tested with two different values of Ptrain/ Ptest- the ratio between the train and test connectivity radius. proper scaling that keeps the expected degree of each node is P 22. Here, although proper scaling does not help solve the problem completely, it does improve performance.
0.3. The test set domain graphs
Node regression
regression
2
Stndent Tescher
Degree
Stndent Teacher
Edge count
0.3
187 + 392
11.9 = 19.4
60.4 = 01.8
(1.2 1.6) 10"
1-GNN
D.15
(3.7 +: 5.1)
(7.2 + 3.7) 10
(9 10) (100)-100
(6.9 + 3.8)
GIN
0.3
125 4: 370
2.37 =: 2,88
33.5 4 84.9
284 # 286
0.15
1.85
(2.2 + 0.3) 10
(5 17)
(9.1 7.1)
Comparing performance on different local distributions (a) A student-teacher graph re- gression task; (b) A graph regression task, where the graph label the number of edges; (c) A student-teacher node regression task; (d) A node regression task, where the node label is its degree. In the edge count/degree tasks the loss the mean difference from the ground-truths, divided by the average degree/number of edges. In the student-teacher tasks the loss is the mean L2 loss between the teacher's 's value and the student's prediction, divided by the averaged student's prediction. Both the student and teacher share the same 3-layer architecture
Table 3:
Next, we tested on the student-teacher task, on both graph and node levels, on the degree prediction task of each node, and the task predicting the number of edges in the graph. The goal these experiments is to show that the size generalization problem persists architectures, and its intensity is increased for deeper GNN. In all the experiments we draw the graphs from G(n, p) distribution, wherein the test set is drawn uniformly between 40 and 50, and p = 0.3, and in the test set n = 100 and is either 0.3 or 0.15. We note that when = 0.15, the average degree of the test graph is equal (approximately) the average degree of the train graph, while when p = 0.3 it is twice as large. We would expect that the model will generalize better when the average degree in the train and test is similar, because then their d-patterns will also be more similar.
different tasks, different
Table compares the performance of these tasks when changing the graph size of the test data, We tested the performance with normalized test loss, where we normalized the output by the average output of the test set. This metric allows to estimate the percentage of mistakes from the average output.
D SSL TASK ON WL TREE
First, we will need the following definition which constructs a tree out of the d-pattern introduced in the previous section. This tree enables us to extract certain properties for each node which can, later on, be learned using a GNN. This definition is similar to the definition of "unrolled tree" from (24).
=V, EV,E) a graph, C a finite set of node features, where each E V have corresponding feature Co, and d 2 0. For node E V, its d-pattern tree T!d) (V! E(d)) is directed tree where each node corresponds to some node in G. It is defined recursively in the following way: For d = 0, (!))) = u(,,)), and E(!) Ø. Suppose we defined T!d-1), and let (ddd-) be all the leaf nodes in vg (d-1) (i.e. nodes without incoming edges). We define:
Definition D.1 (d-pattern tree). Let Let -
16

---

Under review as a conference paper at ICLR 2021
Vi v(d-1) U u(doo) o' EN(("), w/a-1,0n E p(d-1)) E(/ = E Edd-1) u (ulaw)))ka-1,aa alo) : of E N(u"), 1/ E {
and for every node u(d,v') E Vila) its node feature is Cy the node feature of v'
The main advantage of pattern trees is that they encode all the information that a GNN can produce for given node by running the same GNN the pattern tree.
This tree corresponds to the local patterns in the following way: the d-pattern tree of a node can be seen multiset of the children of the root, and each child is multiset of its children, etc. This completely describes the d-pattern of a node. In other words, there is a one-to-one correspondence between d-patterns and pattern trees of depth d. Thus, GNN that successfully represents the pattern trees of the target distribution will also successfully represent the d-patterns of the target distribution.
Using the d-pattern tree we construct simple regression SSL task where its goal is for each node to count the number of nodes in each layer of its d-pattern tree. This is a simple descriptor of the tree, which although loses some information about connectivity, does hold information about the structure of the layers.
For example, in Fig. 3 descriptor for the tree would be that the root (zero) layer has single black node, the first layer has two yellow nodes, the second layer has two yellow, two gray, and two black nodes, and the third layer has ten yellow, two black and two gray nodes.
E TRAINING PROCEDURE
In this section we explain in details the training procedure used in the experiments of Sec. 4 Let X Maain and Xsst. be two labeled datasets, the first contains the labeled examples for the main task from the source distribution, and the second contains examples labeled by the SSL task from both the source and target distributions. Let & I x R + R be a loss function, in all our experiments we use cross entropy loss for classification tasks and squared loss for regression tasks. We construct the following models:
(1) fANN is a GNN feature extractor. Its input is graph and its output is feature vector for each node in the graph. (2) Main is head (a small neural network) for the main task. Its inputs are the node feature and it outputs a prediction (for graph prediction tasks this head contains global pooling layer), (3) hsst. is the head for the SSL task. Its inputs are node features, and it outputs prediction for each node of the graph, depending on the specific SSL used.
Pretraining. Here, there are two phases for the learning procedure. In the first phase, at each iteration we sample batch (11,y1) from XSSL. and train ny minimizing the objective: E(hsst o faNx(xI) y1). In this phase both hESL and faNN are trained. In the second phase, at each iteration we sample (X2, from Xmain and train on the loss M(hMain o (x2) (X2). Y2), where only train the head haminn while the weights of faNN are fixed.
Multitask training, Here we train all the functions at the same time. At each iteration we sample a batch y1) from Xsst. and batch (x2, y2) from Main and train by minimizing the objective:
al(sss (x)N(x1). + (1 a)){(haaia o faNN
Here [0, 1] is the weight for the SSL task, in all our experiments used 1/2.
For an illustration of the training procedures see Fig. 5 These procedures are common practices for training with SSL tasks (see e.g. (39).
We additionally use a semi supervipe setup in which we are given a dataset XFS of few-shot examples from the target distribution with their correct label. In both training procedures, each iteration we sample a batch (x,,ys) from Xrs and add a loss term 36 o fGNN (xx)), y) where E [0, 1] is the weight of the few-shot loss. In pretraining this term is only added to the
17

---

Under review as a conference paper at ICLR 2021
mode fantares
nutput
Emiiaiding GMN
ML.
Isats MLP
Freasu ofter pretmining
Akaral GNM
SSE iegees
Two training procedures for learning with SSL tasks. Left: Learning with pretraining: Here, a GNN is trained on the SSL task with specific SSL head. After training, the weights of the GNN are fixed, and only the main head is trained on the main task. Right: Multitask learning: Here, there is shared GNN and two separate heads, one for the SSL task and one for the main task. The GNN and both heads are trained in simultancously.
Figure 5:
Vanilla
Puttern
Average (log scale)
0.25 0.10 0.15 0.20 0.25 0.50 D.35 0:40 0.45 0.50 of test Gin,p)
Figure 6: Teacher-student setup with a 3-layer GNN. Training is on graphs drawn i.i.d from G(n. p) with n E {40, 50} uniformly and p 0.3. Testing done on graphs with n = 100 and p vary (x- axis). The "Pattern tree" plot represent training with our pattern tree SSL task, using the pretraining setup.
second phase, with weight 1/2 and adjust the weight of the main task to 1/2 as well (equal weight to the main task). In the multitask setup, we add this term with a weight 1/3 and adjust the weights of the two other losses to 1/3 well, so all the losses have the same weight.
F MORE EXPERIMENTS FROM SEC. A
For synthetic datasets, we used the setting of Section 3.4 Source graphs were generated with G(n, p) with n sampled uniformly in [40, 50] and = 0.3. Target graphs were sampled from G(n, p) with n 100 and 0.3.
debiicssspicts the results of using the d d-paaterns SSL tasks, in addition to using the semi semi-supervised setting. can be seen that adding the d d-patterns SSL task significantly improves the performance on the teacher-student task, although it does not completely solve it. We also observe that adding labeled examples from the target domain significantly improves the performance of all tasks. Note that adding even single example significantly improves performance. In all the experiments, the network was successful learning the task on the source domain with less than 0.15 averaged error, and in most cases much less.
Fig. 6 depicts a bide-by-side plot of the 3-layer case of Fig. (left), where training is done on graphs sampled from G(n, with 40 50 nodes and p 0.3, and testing graphs with 100 nodes and p varies. We compare Vanilla training, and our pattern tree SSL task with pretraining. clear that for all values of p our SSL task improves over vanilla training.
F.1 DATASETS STATISTICS
Table E.I shows the statistics of the datasets that were used in the paper. In particular the table presents the split that was used in the experiments, we trained on graphs with sizes smaller or equal to the 50-th percentile and tested graphs with sizes larger equal to the 90-th percentile. In all
18

---

Under review as a conference paper at ICLR 2021
TASKS
FARGET SAMPLES
EDGR COUNT
DEGREE
TEACHER STUDENT
TEACHER STUDENT
PER NODE
1318 1 1398
12.22 15.35
43.1 1. 38.1
30.47 1. 64.85
0.46 = 0.68
0.01 = 0.01
0.13 0.22
0.06 + 0.15
VANILLA
0.06 1: 0.07
<1E:3
0.08 1 0.28
0.02 1 0.05
10
0.03 +: 0.03
<1R-3
0.01 0.01
0.01 +: 0.03
1.7 +: 1.05
0.07 + 0.04
<
11E.4
d-PATTERN PT
0.09 0.19
0.02 0.003
<1B-3
<1E-4
10
0.05 0.05
0.02 0.01
<1R.3
<1E.4
Table 4: Test results est of synthetic datasets. Values are the loss divided by the mean over the test set of target output.
Table 5: Dataset statistics.
NUTII
Largest
Largest
Largosi
Class A
49.95%
62.30%
19.17%
49.62%
62.0F5
21.3%%
58.65%
35,47%
79.66%
50.37%
37.95%
Num of graphs
4130
2157
412
4127
2019
1178
392
118
Avg graph size
29
20
61
264
144
746
Twitich 4gos
Deener 4gos
IMIDI-Dinary Smalled 50%
Smallesd 50
Larged 10%
all
Smalled 50%
Larges 10%
Larged 10%
58.07%
56,009
Class 15
53.76%
64.94%
41.92%
43.19%
55.21%
35.00%
500090
$1.01%
44,44%
graphs
4894
543
Avg graph size
13
68
PROTRINS
Largest
Class A
41.97W
9017%%
Class B
2041%
graphs
112
Aug graph
the datasets there a significant difference between the graph sizes the train and test sets, and in some datasets there is also a difference between the distribution of the output class in the small and large graphs.
F.2 DEGREE DISCREPANCY CORRESPONDS SIZE DISCREPANCY
In this subsection we calculated the degree histogram of two of the real datasets that we tested on: IMDB-Binary and D & D. For the degree histogram see Fig. 7 Recall the the degree is the 1-pattern of node. It is clear from the plots that for the IMDB dataset there is difference in the distribution of degrees between small and large graphs. while D & the distributions look almost the same. Correspondingly, In our experiments the pattern tree SSL task significantly improved performance on the IMDB dataset, while not improving performance on D& dataset. This gives further evidence that discrepancy between the d-patterns leads to bad generalization, and that correctly representing the patterns the test set can improve performance. While in this simple experiment we only considered I- 1-patterns it is worth mentioning that the discrepancy is can only be accentuated when considering deeper patterns.
19

---

Under review as a conference paper at ICLR 2021
INDB SINARY
small pripfo
Perco/fogg
0.29
25
13
Node Degree
Node Degroe
Figure 7: Histogram in percentage of degrees of graphs. We used the 10% smallest and largest graphs in each dataset.
20


Reviews:
[{"review_id": "z8mlCO0LqhK", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the important problem of lack of generalization of GNNs to graphs whose sizes are much larger than the graphs on which they were trained on. The authors propose a theoretical explanation by arguing that this lack of generalization is due to a mismatch in the “d-patterns” (essentially the pattern of neighborhood around nodes) between the training and test graphs. To improve generalization performance, they borrow ideas from domain adaptation and propose a pattern-tree based pretext learning task which improves classification accuracy compared to baseline pretext tasks in a range of datasets and tasks. \n\nUnderstanding and improving size generalization in GNNs is an important and timely topic. I appreciate the authors considering this problem and their efforts towards solving it. Overall the paper is well written, and I enjoyed reading it. \n\nWhile I do agree that a mismatch in the d-pattern distribution can lead to poor generalization (Corollary 3.3 and Equation 1), there are a few aspects to this claim that I do not understand. For instance, suppose my training set consists of graphs whose avg. degrees are 2, 3, …, 100. And suppose the test set consists of only graphs whose avg. degree is 50. Clearly there is a huge mismatch in the d-patterns between the training and test sets (in the sense of Equation 1 in the paper). However intuitively I would expect the GNN to do well on the test set since it would have encountered degree 50 graphs while training. Could you explain this apparent inconsistency? \n\nFollowing Corollary 3.3., the proposed solutions (d-pattern pretext training or semi-supervised learning) attempt to bring the training pattern distributions closer to the test distribution. This makes sense because if the training distribution got closer to the test distribution, the generalization would be better. However, in the case of SSL adding only a few labelled examples (1, 5 or 10) from the target domain already provides a sizeable improvement in performance. Similarly, in Appendix E the authors report that “adding just a single labelled example from the target distribution significantly improves performance”. Intuitively adding a small number of examples from the target domain should not change the training distribution by much, and yet the performance gains are substantial. I again cannot see how Corollary 3.3 can explain this phenomenon. \n\nIn the proof of Corollary 3.3 (in Appendix B), it states that “by thm 3.2 there exists a 1-GNN such that for any d-pattern p_i \\in A gives a wrong label and for every pattern outside A, p_j \\in A^c gives the correct label”. As far as I understand, thm 3.2 says there exists a GNN that can predict the labels correctly for every p_j \\in A^c. I do not follow how thm 3.2 says that for patterns outside of A^c the GNN would predict the labels incorrectly. Could you please clarify? \n\nIn Figure 1, why do GNNs with more layers tend to do worse compared to GNNs with just one layer? It would be good to have a similar plot where you use your proposed DA solution. While you do have some results in Appendix E, having a side-by-side comparing before and after pretraining or SSL would help highlight the effectiveness of the solution better. Have you tried regularization to improve generalization? \t\n\nIn Figure 3, could you explain the trend when the number of labelled large graph examples is more than 10? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "lEa9viabW5", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper investigates the issue of generalizability of GNNs when trained on small graphs and tested on larger graphs, a common setting in graph learning. The paper argues that the ability of constant-depth GNNs to generalize is not dependent on the size difference, but on the difference in distributions of nodes' neighborhood features, which authors call \"d-patterns.\" The paper shows theoretically that a GNN can be trained to achieve zero loss on small graphs, yet fail to generalize to larger graphs and the loss on these graphs will be dependent on the difference in d-pattern distributions.\n\nStrengths:\n* Shows strong theoretical and empirical evidence of GNNs inability to generalize to graphs larger than those seen in training when the distribution of d-patterns of the graphs differ, showing that techniques like regularization will not help in these cases \n* Provides a first step to mitigate problem by using domain adaptation methods and in particular using an intermediate task of identifying the d-patterns in each graph.\n\nWeaknesses:\n* The work only considers constant-depth GNNs and local tasks \n* Generalization error is shown only for 0-1 loss, limiting the graph problems that it applies to to node live binary classification and functions thereof.\n\nConclusion:\nThe failures of GNNs to generalize to larger graphs in many cases is a known phenomenon. This paper's investigation of this issue and a clear explanation of at least one reason for it is clear and well supported. Though a more minor contribution to the paper, the proposal for some mitigating techniques (DA and in particular the pattern tree labeling task) can serve as motivation for further investigation of models robust to these generalization errors. I recommend acceptance based on the clear motivation and development of the investigation presented in the work.\n\nupdate: Thank you to authors for their response to reviewer comments. I acknowledge I have read and reviewed their rebuttals.\n\nQuestions:\n1. The claim made is that the distribution shift in d-patterns is the driving factor in generalization error. The experiments in 3.4 support this, but one experiment similar to those shown in Figure 1 that would illustrate this further is training on sizes n=[40,x] and p=0.3 as in Figure 1 (right) and testing on n=150 and p=0.002*[40,x]. If the size difference between train and test is not the driving factor, but rather d-patters, should we expect such an experiment would yield a mostly-flat loss curve? Would the value of the loss on the test graphs be similar to the loss achieved on graphs from the original distribution (n=[40, x] with p=0.03)?\n2. The focus of the work is on size generalization and in particular small-to-large graph domain shift. The claims appear to also hold for evaluating generalization on similarly sized graphs with differences in node attributes and/or connectivity patterns. Is this the case, why or why not? \n\nMinor comments and typos:\n*  In the definition of d-patterns, the integer $\\ell$ is not defined. Is this the number of neighbors, or the number of possible d-patterns?\n* Top of page 8 “does have node features” should be “does *not* have node features”\n* Page 8, “Datasets” paragraph says “and the and 10% largest graphs.” I assume this should read “and the largest 10% of graphs…”\n* “The” should be capitalized in the last paragraph (“Results”) at the beginning of the sentence “The accuracy monotonically increases…”", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZR3_lybFfWg", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a notion of ''d-patterns'' for graphs -- 1-pattern corresponds to the degree of each node; 2-pattern is for each possible degree i the number of neighbors with degree i; 3-pattern is for each possible 2-pattern, the number of its neighbors with the exact 2-pattern; N-pattern are defined similarly. The paper shows that given a set of d-patterns, there exists an assignment of GNN weight that fits this d-pattern output, so there exist some assignments of weights to GNNs that cannot generalize to larger graphs. Based on the existence of a set of bad parameters, authors claim that GNNs will fail to size generalize. Authors also claim that d-pattern is the determine factor of whether a GNN can size generalize. In the last two pages, the paper proposes to improve size generalization ability of GNNs by self-supervised training on unlabelled/labeled data with a d-pattern / pattern-tree task. Some experiments are conducted to demonstrate pattern-tree task slightly improves vanilla GNNs.\n\nThis paper is well-written and easy to follow.  There are several major concerns regarding the significance and correctness of the results.\n\na) In the main result Corollary 3.3, authors claim that because there exists a weight assignment of GNN that cannot generalize to lager graphs given discrepancy on d-pattern, then GNN will fail to generalize to larger graphs given d-pattern discrepancy. Authors also claim d-pattern should be the determining factor for size generalization.\n\nThis main result/claim has several problems. \n\n- The existence of a bad set of weight parameters does not imply training GNN will necessarily converge to this parameter. Hence you cannot use this to claim GNN will fail to size generalize.\n- I am not convinced d-pattern is the determining factor for size generalization. The d-pattern definition is quite complicated and it is not necessarily an important factor in many tasks. In fact, your argument of the existence of a set of bad parameters can be easily constructed with other measures, not just d-pattern.\n- To claim d-pattern is the main factor, you need to prove that when there is no d-pattern discrepancy, GNN will always size generalize. Moreover, you need to prove when there is d-pattern discrepancy, GNNs will definitely fail (note that the existence proof is not valid for this purpose).\n\nb) Authors claim one of their main contributions is to find out size generalization is difficult. But size generalization is hard is already well-known and not surprising. Many previous works have demonstrated this.\n\nc) The proposed method (self-supervised training with pattern tree task) is incremental. Self-supervised training of GNNs is not new, the fact that pre-training can improve robustness to larger graphs is also not new and have been shown in previous works. The pattern tree task is not significant either.\n\nI encourage authors to propose a more novel method and thoroughly demonstrate its effectiveness before submission to the next venue.\n\n\nSome references that demonstrate size generalization is a well-known issue.\n\nReferences\n\nMeasuring abstract reasoning in neural networks. Barrett et al 2018.\n\nLearning TSP Requires Rethinking Generalization. Joshi et al 2020.\n\nLearning Combinatorial Optimization Algorithms over Graphs. Dai et al 2017.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PNI7jLyj3M", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper theoretically discusses the size generalization problem in GNNs. It introduces the concept of d-patterns and shows how generalization is related to the distribution of d-patterns.\n\nPros:\n+ The size generalization problem in GNN is an important and interesting topic, which has many real-world applications.\n+  Though I did not check the proof details, the theoretical results look sound to me.\n\nCons:\n- The proposed method for improving size-generalization is not clearly stated. In Sec 4, it will be better if the authors could clearly write down the training procedure and loss, instead of describing them in words. \n- It is also not clear how the proposed method for improving size-generalization is related to the theorem in Sec 3.\n- The focus of this paper is on local tasks that can be solved by GNNs with fixed depths, no matter what the graph size is. This is quite a strong assumption, especially on node prediction tasks. Based on this strong assumption, it is clear that the node prediction is only related to its local d-hop subgraph, no matter what the graph size is. Suppose we view each the prediction on each node as a single task, and the input is the d-hop subgraph. Then (1) it is clear that the generalization will depend on the distribution of the d-hop subgraphs only and (2) this problem becomes irrelevant to the size of the original graph. It is then not clear what new information, insight, or conclusion we could draw from the theorem.\n- The discussion in this paper does not reveal to be very relevant to the 'size' of the graph. It is not clear how the 'size' plays the role in the generalization. Given two distributions of graphs of the SAME SIZE, the same results will hold, depending on the distributions of the d-patterns.\n- In the experiment, it will be better if the authors could show how the performance varies when the graph size becomes larger and larger.\n\nOverall the information and the key message from this paper do not seem to be clear and strong enough. I vote for rejection.\n\n=== after author response ===\nI would like to thank the authors for their detailed response. My major concern is the strong assumption in this paper - that the function to be approximated is a fixed-depth GNN. This assumption makes the problem less relevant to the actual size of the graph, and avoids a major challenge in size-generalization - that larger graphs are expected to require deeper operations. \n\nAs pointed out in the author's response, some efforts are made to **experimentally** (1) demonstrate the effectiveness of the proposed method on a real dataset which might not be solvable by constant depth GNN, and (2) demonstrate in real datasets there is a discrepancy between the degrees of small and large graphs. I would be happy to raise my score from 4 to 5 given these experiments. However, the theory part could still be further improved so I do not further raise the score.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper seeks to point out the difficulty of size generalization in GNNs for node prediction and analyze why this happens. The analysis is anchored on the construction of so called d-patterns. The main argument is presented in Corollary 3.4 which shows that discrepancy in d-patters between small and large graphs introduces the possibility of finding a GNN that fits the d-patterns well in a small graph while yielding poor answers on a large graph (assuming the task is solvable by a constant depth GNN). While good to show, the existence of bad parameters does not necessarily suggest that this setting is likely to arise after training. As pointed out by AnonReviewer1, size generalization is also not a new issue but has already been introduced / highlighted in previous publications (Barrett et al 2018, Joshi et al 2020, Dai et al 2017). The authors do provide an algorithm and empirical arguments to mitigate the effect of d-pattern discrepancy. A revised version of the manuscript can hopefully make a stronger case for d-patterns, constant depth computation, and the relevance of these for size generalization. 
Decision: Reject