Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the PAC-Bayes generalization bound for both IID and OOD generalization on graphs, with a focus on homophilic graphs and graph size shifts. In particular, the authors reduce an exponential dependency on the node degree to a linear dependency for the IID generalization bound. Then they further apply the generalization bound to study random walk sampled graphs with different sizes. Besides, they conduct some experiments to support the derived bounds.
strength_and_weaknesses: While I appreciate the completeness and clarity of the paper, I find the scope of the paper is rather limited, or even overclaimed by the authors.

**Overclaimed improvements in IID generalization bound.**
The authors claimed that reduce an exponential dependency on the node degree to a linear dependency for the IID generalization bound. However, they also exacerbate the dependency on **hidden dimensions $h$** from log scale to linear. This essentially establishes a trade-off between their bound and that from [1]. The advantages only exist for graphs with high degrees and GNNs with deep layers. In contrast, many of realistic graphs (e.g., molecules) tend to have a lower degree. Practitioners tend to adopt a shallower and wider GNN due to the memory cost, especially for homophilic graphs where simple MLP with some post-hoc modifications can achieve top performances (cf. leaderboard results in OGB).

When demonstrating the advances of the established generalization bound over [1], the authors seem to be conducting **misleading comparisons**. Since the advances only exist for graphs with high degrees and GNNs with deep layers, the authors are using a deeper GNN (4, 6, 10 layers compared to 2, 4, 6, 8 layers in [1]), and small hidden dimension (5, 32 compared to 128 in [1]). This makes the improvements and significance of the IID generalization bound limited.

**Overclaims in assumptions for OOD generalization bound.**
When it comes to the OOD generalization bound, the authors claimed their setup has advantages over some OOD setups in the literature where a generative model of graphs and labels is explicitly assumed [2,3,4,5,6,7,8,9]. In particular, in the paragraph of Size Generalization Assumptions in the paper, the authors are essentially making assumptions about the data generation process. The graphs are sampled from random walks with different lengths, which forms a specific graph family just like graphon [2,3,6,8,9]. The labels are determined by the majority of labels in the training graphs, which essentially have little difference from the causal assumptions made in [2,3,4,5,6,7,8]. I didn’t see the advantages of the assumptions made in the paper. 

However, this paper introduces additional assumptions that require the graphs to be homophilic, which makes the random walk sampling over the large graphs trivial. As [10] already found that random walks with more steps will converge to some stationary distributions over the original graphs. Therefore, analyzing homophilic graphs sampled using random walks with more steps seems to be less interesting. 


**Limited scope and poor coverage of the literature.**
Although, as pointed out by other reviewers that this work is limited to graph size shifts and missed discussion with many related works, I still find many missing discussions and comparisons in [2,3,4,5,6,7,8,9]. In particular, [2,3,6,8] studied graph size shifts as well, but I can’t find any discussions in work. Both the theoretical and empirical parts of the work lack a comparison with these works.

References:

[1] A PAC-Bayesian approach to generalization bounds for graph neural networks, ICLR21.

[2] From Local Structures to Size Generalization in Graph Neural Networks, ICML21.

[3] Size-Invariant Graph Representations for Graph Classification Extrapolations, ICML21.

[4] Handling distribution shifts on graphs: an invariance perspective, ICLR22.

[5] Discovering Invariant Rationales for Graph Neural Networks, ICLR22.

[6] Invariance Principle Meets Out-of-Distribution Generalization on Graphs, ICML22: Workshop on Spurious Correlations, Invariance and Stability.

[7] Learning Substructure Invariance for Out-of-Distribution Molecular Representations, NeurIPS22.

[8] OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs, NeurIPS22.

[9] Generalization Analysis of Message Passing Neural Networks on Large Random Graphs, arXiv22.

[10] Representation Learning on Graphs with Jumping Knowledge Networks, ICML18.

clarity,_quality,_novelty_and_reproducibility: This work is well-written and easy to follow. However, many overclaims and misleading experiments, plus the limited scope of the paper, make the novelty of the work limited.
summary_of_the_review: Although I appreciate the completeness and clarity of the paper, many overclaims and misleading experiments, plus the limited scope of the paper, make the paper a clear reject.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on the generalization ability of graph neural networks and derives the generalization error bound based on PAC-Bayes framework. The new theoretical bound improves the state-of-the-art result, and empirical studies show that the proposed model can help to address size generalization problem on graphs.
strength_and_weaknesses: Pros:

The paper is well motivated and focuses on an important and active research problem in the graph ML community. The theory results seem correct and reasonable though I didn't carefully check the proof in the appendix. The experiment results verify the theoretical argument.

Cons:

1. The analysis is built on several assumptions that may violate the practical settings, like the graph data generation assumption. More discussions and justification are needed.

2. The proposed theory seems to require the homophily assumption of graph structures. How it behaves for heterophilic graphs?

3. The discussed distribution shifts only cover the size variation, which is quite limited in contrast with the various distribution shift types in practice. For example, cross-domain transfer in multi-graph generalization and temporal generalization in dynamic graphs [1], subgroup generalization across majority and minority feature groups [2], motif-structure bias of spurious correlation [3], and substructure-aware distribution shift in molecular property prediction [4], etc. More discussions on how the theory in this paper could shed lights on these practical OOD learning settings can definitely help to strenghthen the paper.

4. The experiments are only conducted on the size generalization task. And, similarly, more experiments to cover the more OOD types, such as the above-mentioned settings, which can be more challenging and closer to the real cases could increase the diversity and strengthen the contributions.

[1] Handling distribution shifts on graphs: an invariance perspective, ICLR22

[2] Subgroup generalization and fairness of graph neural networks, NeurIPS21

[3] Discovering Invariant Rationales for Graph Neural Networks, ICLR22

[4] Learning Substructure Invariance for Out-of-Distribution Molecular Representations, NeurIPS22
clarity,_quality,_novelty_and_reproducibility: Clarify: this paper is well written and organized

Quality: the quality is overall good though I didn't carefully check the proof

Novelty: the algorithmic novelty is limited especially the scope is limited in size generalization which is a particular and simple OOD setting on graphs
summary_of_the_review: Overall, I think this paper is well motivated and written. The theoretical results are interesting and reasonable. However, I believe there still exists much room for improvement based on the current version. For example, more discussions on other out-of-distribution settings and distribution shift types are needed to strengthen the contributions. And, more experiments with other OOD settings could also help to increase the impact of this work.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose theoretical analyses for the generalization of GNNs. For the in-distribution case, the authors propose an improved bound regarding graph classification compared to the existing PAC-Bayes results. For the out-of-distribution generalization, the authors propose an analysis for node classification by using random walks instead of assuming a ground-truth generative model.
strength_and_weaknesses: **Pros:**  
1. The generalization, specifically out-of-distribution generalization, of GNNs, is an important and trending research direction, and its theoretical analysis is not well studied.  
2. The proposed in-distribution bound seems to improve over the existing analysis.  

**Cons and questions:**  
1. For OOD generalization, this paper focuses on a specific setup, i.e., graph classification where the graphs are sampled from a giant graph, and the graph label is determined by homophily. Though I acknowledge that such an assumption may be unavoidable for rigorous theoretical analysis, it seems to be impractical and thus greatly limits the scope of the proposed analysis. For example, many works on OOD generalization for graph classification focus on molecule classification, where training and testing molecules are collected in different environments/with different backbone structures, which is a completely different scenario and the proposed method seems unable to fit.  
2. Following the above comment, the authors observe in experiments that “the GCN model achieves OOD test accuracy on large-subgraph that was comparable to ID accuracy on small-subgraph if not outright better”, which contradicts previous works such as Yehudai et al. (2021). This may also suggest that the assumed setting is not practical.  
3. A previous analysis shows that the GNN architectures and downstream graph tasks can greatly affect the generalization of GNNs [1]. I think this work is highly related and a proper discussion should be added.   
[1] How Neural Networks Extrapolate From Feedforward to Graph Neural Networks, ICLR 2021.  
4. It would also make the paper stronger if the authors can briefly point out how the proposed analysis can inspire improving GNNs, which is crucial for GNN practitioners.  

Minor:
(1) Figure 2 is a bit vague (vector graphics are recommended).

===after rebuttal===  
I have read the rebuttal and thank the authors for the clarifications. Similar to other reviewers, I think the paper makes interesting theoretical analyeses, but rely on very strong assumptions, so I am not entirely sure whether such contributions meet the bar of ICLR. All things considered, I have increased my score to 6, i.e., slightly positive. 
clarity,_quality,_novelty_and_reproducibility: The clarity and quality of the paper are good, but the novelty seems limited (see comments above). The authors have provided detailed hyper-parameters in the appendix, so the reproducibility should be okay (though providing the source codes will be better).
summary_of_the_review: This paper proposes theoretical analyses for the generalization of GNNs, which is an important topic. My main concerns lie in the reasonability of the assumptions and the paper's relationships compared to the literature.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The objective of this paper is to provided bounds on the generalization of GNNs in both the in-distribution and out-of-distribution setting. For the in-distribution case, the authors tighten the bounds provided in Liao et al. (2020) by scaling down two separate terms in the PAC-Bayes bound. For the out of distribution setting, the authors analyze the specific issue of size generalization (GNNs trained and tested on subgraphs of differing sizes); the authors provide a bound on the generalization error motivated by the fact that for homophilous graphs, an increase in size does not affect the graph classification with a certain probability. 

The setup for the in-distribution generalization error is as follows: there exists a distribution over the set of graphs, node features and graph labels. A GCN is trained on m samples from the distribution, and then the task is to bound the gap between the true risk (probability the graph label is off by a margin gamma) and the empirical risk (the training error). 

Liao et al. (2020) provides a bound for the above gap. The present paper tightens two terms. First, the authors claim that the gap does not grow exponentially with the maximum degree but linearly. The authors show that when performing induction over the layers of the GCN, due to normalization, it is possible to maintain a linear dependency on degree (pages 13-14). Second, the authors tighten a separate term by utilizing a random matrix theory theorem from (Vershynin, 2018).

The setup for size generalization (out of distribution) is as follows: there exists a very large graph G. For training, a GCN is trained on subgraphs of G generated by performing random walks of length N and taking the induced subgraph. For testing, however, the test subgraph is generated by a random walk of length M >> N. The goal is still to perform graph classification. Every node in the graph has a label and the subgraph label is simply the most common ground truth or predicted node label. 

The core tool needed to bound the size generalization error is the observation that due to homophily it is possible to bound the probability that a random walk of size M reaches a node of a label differing from the label of the initial node. In the case where the random walk does not reach a node of a differing label, the length of the random walk does not impact the subgraph label. 
strength_and_weaknesses: Pros:
* The paper tackles an important topic in better understanding the theoretical generalization bounds of GNNs. Further, the paper is comprehensive in looking at both in and out of distribution generalization. 
* The paper is clearly written and understandable for a reader familiar with GNN/GCNs but not with theoretical generalization bounds of these models. 

Cons:
* For the in-distribution bounds it is not fully clear what is the significance / level of contribution of tightening the bounds in Liao et al. To me this could be better shown with a more detailed analysis of the experimental results in sec. 5.1 in particular for the real-world graphs. As is the log-generalization gap values are difficult to interpret and put into perspective.
* It would be helpful to have more specification for when the expression for M in Theorem 4.3 is compatible with the condition that M >> N.  
* In analyzing the size generalization, it can be argued that the paper translates an out-of-distribution question into an in-distribution one. Specifically the paper largely side steps situations in which it is desirable to test the GNN on the large subgraph itself instead of sampling from the test subgraph, for instance the setting considered in “From Local Structures to Size Generalization in Graph Neural Networks”. 
* It is helpful that the authors explain the surprising findings in Figures 2c and 2f; however, it would be helpful to also include cases where the test accuracy is not higher than the training accuracy. When the test accuracy is always higher the results preclude the need to understand out-of-distribution generalization.

Minor comments: 
* On page five when describing the size generalization setup in the following sentence: “In testing, we assume a procedure where a length-N random walk induced subgraph is sampled from the large subgraph”, it was not clear to me that the large subgraph is the length-M random-walk induced graph until later. 
clarity,_quality,_novelty_and_reproducibility: I can attest to the clarity and novelty of the work. The paper is written without many assumptions of prior knowledge of GNN generalizability. The improved in-distribution bounds are an original contribution building on recent work in the literature. My major concerns are the size of contribution which are detailed in the main review.
summary_of_the_review: Overall the paper tackles an important GNN issue and moves the community toward understanding the theoretical generalizability of such models. The paper is also comprehensive in considering both in-distribution and out-of-distribution generalization. The largest areas of improvement, in my opinion, are better placing the significance of these results in context and more thorough experiments. The exact benefit of the tightened in-distribution bounds is not clear (would recommend a more detailed experiment isolating the benefit of the linear degree term) and for out-of-distribution, it is not clear when it would be appropriate to sample the large testing subgraph.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies in-distribution and out-of-distribution generalization with graph convolutional networks. In the former setting, the paper improves on an existing bound in the literature by reducing dependency on maximum node degree to a linear factor. In the latter setting, the paper builds on in-distribution results, and considers the case of homophilic (but arbitrary) graph structures. More specifically, the out-of-distribution setup considers a single very large graph from which smaller training graphs and larger testing graphs are sampled using random walks. Then, the paper considers the majority voting problem, in which the binary label of a graph is the binary label of the majority of its constituent nodes. Using a probabilistic argument, the paper then shows that, for homophilic graphs, the probability of conducting a random walk that crosses the label divide, i.e., from label 0 to label 1 or vice versa, in the original large input graph can be thresholded to a quantity delta with reasonable bounds on the test graph size M and training graph size N. This probability can then be considered jointly with the probability error in the in-distribution theorem to yield an overall error probability for this out-of-distribution setting. Finally, the paper conducts an empirical analysis on a variety of synthetic and real-world datasets, showing performance levels consistent with the theory, and even demonstrating strong performance when certain assumptions are violated (degree regularity for example).
strength_and_weaknesses: # Strengths: 
- The improvement of the in-distribution bound is significant and meaningful. The proof of this theorem also appears to be sound
- The setting proposed for out-of-distribution analysis is interesting and avoids making assumptions on the inherent graph structure, and thus offers a novel approach to studying how graph convolutional networks can generalize to larger graphs. 

# Weaknesses: 
- Though the out-of-distribution setup is interesting and avoids assumptions on the structure of the train and test graphs, the assumptions it introduces instead appear to be limiting. In particular, the graph labelling objective seems restrictive and specialized. Typically, graph classification objectives go far beyond node statistics (majority of labels) and explore structural graph properties, which lies outside the scope of this analysis. It is also not at all clear to me how one can move beyond this limitation: The very essence of the probabilistic argument in the paper relies on aggregating over node classes, and thresholding the probability of transitioning between classes in a random walk: Without a node-based objective, such an analysis is not relevant. Therefore, I am afraid this approach cannot be used to develop a more general (objective-agnostic) framework for out-of-distribution generalization. I understand that assumptions inevitably must be made about a connection between the train and test sets (shared structure, or in this case similar walk outcomes with respect to the objective), however I feel that simplifying assumptions on the objective function will not lead to general insights on out-of-distribution learning, as claimed in the paper. I therefore suggest that the authors clarify the limitations and scope of their analysis more extensively.

- On a more minor note, it would be interesting to mention how/if the results extend beyond the GCN architecture. Currently, the result and proof requires a GCN, but it would be useful to provide an intuition as to how such a framework can be applied to other models.
clarity,_quality,_novelty_and_reproducibility: # Clarity: 
The intuitions provided in the main paper are clear and the arguments and intuitions are well-explained. In the appendix, the proof of Theorem 3.1 is a bit hard to follow. I regularly had to refer back to different parts of the proof to understand the respective quantities and variables. Moreover, some steps in the proof (namely, the inequality sequences) can be better explained. 

# Quality: 
The paper's contributions are meaningful and its arguments all appear sound and well-motivated. 

# Novelty: 
The results and perspective on out-of-distribution generalization are novel.

# Reproducibility: 
N/A to proofs. Experimental results appear to be easily reproducible. 
summary_of_the_review: All in all, I believe that the paper makes a useful contribution for studying the generalization performance of GCNs. I find the in-distribution result to be strong and potentially impactful. I also appreciate the perspective offered in the out-of-distribution analysis, and how this avoids making assumptions on the graph structure. However, I have concerns about the restriction to the objective function, which in my opinion casts doubts on the general applicability of the approach, particularly its probabilistic argument for scaling the in-distribution theorem to the out-of-distribution setting. All in all, I am learning towards supporting the paper. I am also happy to hear back from the authors about my concerns, and am willing to support the paper more strongly should my concerns be addressed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper describes in-distribution and out-of-distribution generalization with graph convolutional networks. In the former setting, the paper improves on an existing bound in the literature by reducing dependency on maximum node degree to a linear factor. In the latter setting, the paper builds on in-distribution results, and considers the case of homophilic and random walk sampled graph structures. Meanwhile, the paper conducts an empirical analysis on a variety of synthetic and real-world datasets, showing performance levels consistent with the theory, and even demonstrating strong performance when certain assumptions are violated (degree regularity for example). Therefore, the paper makes a useful contribution for studying the generalization performance of GNNs.

This paper has some merits, and I personally like the idea of this paper. However, most of reviewers and I have some concerns about the assumptions for OOD generalization bound. When deriving the OOD generalization bound, the authors claimed their setup has advantages over some OOD setups in the literature where a generative model of graphs and labels is explicitly assumed. Yet the assumptions could be too strong to guidance the practice. The considered distribution shifts are limited to graph size shifts as well. According to the top-tier conference criteria in the ML community, this is a boarderline paper with mixed opinions. The next version must be a strong paper if authors can take comments into consideration.
justification_for_why_not_higher_score: According to my expertise and reviewing process, this paper should belong to a Reject.
justification_for_why_not_lower_score: According to my expertise and reviewing process, this paper should belong to a Reject.
Decision: Reject