Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Pros:
+ The size generalization problem in GNN is an important and interesting topic, which has many real-world applications.
+  Though I did not check the proof details, the theoretical results look sound to me.

Cons:
- 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. 
- It is also not clear how the proposed method for improving size-generalization is related to the theorem in Sec 3.
- 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.
- 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.
- In the experiment, it will be better if the authors could show how the performance varies when the graph size becomes larger and larger.

Overall the information and the key message from this paper do not seem to be clear and strong enough. I vote for rejection.

=== after author response ===
I 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. 

As 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.
review_title: Official Blind Review #2

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

This paper is well-written and easy to follow.  There are several major concerns regarding the significance and correctness of the results.

a) 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.

This main result/claim has several problems. 

- 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.
- 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.
- 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).

b) 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.

c) 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.

I encourage authors to propose a more novel method and thoroughly demonstrate its effectiveness before submission to the next venue.


Some references that demonstrate size generalization is a well-known issue.

References

Measuring abstract reasoning in neural networks. Barrett et al 2018.

Learning TSP Requires Rethinking Generalization. Joshi et al 2020.

Learning Combinatorial Optimization Algorithms over Graphs. Dai et al 2017.
review_title: Review

final_score: rating: 7: Good paper, accept
review_content: Summary:
This 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.

Strengths:
* 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 
* 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.

Weaknesses:
* The work only considers constant-depth GNNs and local tasks 
* 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.

Conclusion:
The 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.

update: Thank you to authors for their response to reviewer comments. I acknowledge I have read and reviewed their rebuttals.

Questions:
1. 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)?
2. 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? 

Minor comments and typos:
*  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?
* Top of page 8 “does have node features” should be “does *not* have node features”
* Page 8, “Datasets” paragraph says “and the and 10% largest graphs.” I assume this should read “and the largest 10% of graphs…”
* “The” should be capitalized in the last paragraph (“Results”) at the beginning of the sentence “The accuracy monotonically increases…”
review_title: Novel and well-motivated investigation into GNN size generalization error

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

Understanding 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. 

While 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? 

Following 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. 

In 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? 

In 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? 	

In Figure 3, could you explain the trend when the number of labelled large graph examples is more than 10? 

review_title: Is the train and test d-pattern distributions being "close" to each other (e.g., in total-variation sense) a necessary condition for generalization? 

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