Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies generalisation bounds of GNNs from the classical statistical learning point of view. Under some specific distribution assumptions, the authors show that, while VC Dimension does result in trivial generalisation error bounds,  transductive Rademacher complexity can explain the generalisation properties of graph convolutional networks for the specific case of stochastic block models. Experimental results on synthetic data generated from SBM graphs, and the CORA dataset quantify the validity of the bound. Finally, the influence of depth and residual connections is studied.  
main_review: This is a very interesting and well-presented paper, with respect to different aspects. 

Originality: Generalisation bounds of GNNs are definitely worth investigating, and it is a topic of great interest to the research community. The proposed approach is relevant and interesting. Specifically, the authors focus on transduction settings that have been largely underlooked in the literature. Studying Rademacher complexity seems to provide some insight on the generalisation properties, at least on stochastic block models.   

Quality: The paper is of very good quality, and technically sound. Proofs are provided. Experimental results are informative. A more extensive evaluation on different type of graph models and well as different feature distribution would significantly increase the contribution. 

Clarity: The paper is well written. Despite being a heavy and very technical paper, the authors did a good job in terms of the presentation of the results. A few comments are the following: 

Typos: 
Line 50: is on 'a' learning: remove 'a'
Line 58: deep learning 'learning' repeated twice
Line 112: to be instead of is
Line 145: 'can' is repeated twice 
Line 198: it suggests instead of suggest 
Figure 1: first subfigure: alignment instead of allignment 
Line 256: loose instead of loos
Line 294: remove a
Line 311: more than 

Explain a bit definition 1. 
Remind what K is in the conclusions. 

Significance: The obtain results are theoretically interesting and I expect them to generate more research in the topic. Although the current results are specific to some cases of graph models and feature distributions, they are definitely relevant and a useful step towards understanding theoretically GNNs. I would expect the authors to extend the bounds to terms that are related to the graph characteristics/distribution, as well as some more interpretable features. 

After rebuttal: 
The authors should include a more extensive discussion about the existing literature (e.g.,Oono&Suzuki (2020)) and position their work with respect to that. 

limitations_and_societal_impact: The authors clearly state the limitations of their framework in the conclusion part. One additional limitation is the extension to weighted graphs and more labels (not simply binary classification).
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper analyzed the generalization performance of GNNs based on statistical learning theory. First, this paper derived the VC dimension-based generalization error bounds. It showed that graph structures affected the upper bound of the generalization performance gap via the rank of the adjacency matrix (and its normalized version). This paper also argued that these gaps are vacuous for some random graphs. For a more precise evaluation, this paper next derived generalization error bounds based on the notion of Transductive Rademacher Complexity (TRC). The effect of the normalization of the adjacency matrix S on the generalization bounds is explained for the general and planted model case. Finally, this paper derived the generalization bounds based on TRC for GNNs with residual connections. It argued that residual connections reduced the generalization gap.
main_review: ### Soundness (Do theorems and experiments answer research questions, assuming they are correct?)

- [So1] The research question of this paper is to analyze the generalization performance of GNNs in a transductive problem setting (l.43) from the viewpoint of statistical learning theory. This paper claimed that although classical learning theory cannot explain the behavior of deep learning models for FNNs, while it can, to some extent, for GNNs. I think this paper certainly answers this question for the following reasons.
  - [So1.1] This paper analyzed how the empirical generalization performance of GNNs behaves when we change several parameters such as miss alignment value of labels, graph size, and the number of observed points. This paper confirmed that the empirical generalization performance is consistent with theoretically derived generalization bounds.
  - [So1.2] In addition, the generalization bounds explain the benefit of the normalization of adjacency matrices.
- [So2] I have a question about the soundness of the experiment in Figure 1. The motivation for the TRC-based generalization bounds was that the VC-dimension-based bounds could be vacuous (l.179). However, in Figure 1, the theoretical bounds are outside (0, 1) (l.277). It raised the question of whether TRC bounds can truly also overcome the shortcomings of the VC-dimension-based bounds.

### Correctness (Are derivation of theorems and experiments correct?)

- [C1] I have questions about the correctness of Theorem 3 and Corollary 1 due to the lack of proof. In particular, I could not understand how I can derive Corollary 1. Since Theorem 3 derived only the "upper bound" of the generalization bound, it is unclear how we can compare generalization errors.

### Novelty and Significance (Do the paper have novel points? If so, are they significant?)

- [N1] The derivation is based on the theory of TRC in [EY09]. The central part of the proofs was to evaluate TRC. I would say that the proof did not have much technical novelty because it is a combination of characteristics of TRC. We can prove the characteristics similar to those of the usual Rademacher complexity.
- [N2] In addition, since [Oono and Suzuki, 20] derived the TRC-based generalization bounds for GNNs
- [N3] However, this paper differs from [Oono and Suzuki, 20] in the following three points. First, [Oono and Suzuki, 20] analyzed multi-scale GNNs, while the target of this paper was single-scale GNNs with possibly residual connections. Second, [Oono and Suzuki, 20] evaluated the SX norm but did not go further than that. On the contrary, this paper explained the effect of normalization by evaluating its order (eq. 10, 11). Third, this paper derived the dependence of generalization bound for the Planted model on the cluster-label miss-alignment ratio (Theorem 2). In addition, this paper verified the dependence experimentally. Considering these points, although these derivations are a combination of classical tools, I can recognize the significance of the results of this paper.

[Oono and Suzuki, 20] https://proceedings.neurips.cc/paper/2020/hash/dab49080d80c724aad5ebf158d63df41-Abstract.html

### Clarity (Is the paper clearly written?)

- [Cl1] The organization of this paper is OK. I can understand this paper without much difficulty.


### Other Comments

- l.54: derive→derives
- l.55: provide→provides
- l.79: This paper wrote that the situation considered in Section 2.2 is a "realistic case." However, I think it is somewhat difficult to say that the Erdos-Renyi graph and SBM are realistic. That being said, I agree with this paper in that being vacuous is a problem of the VC dimension-based bounds.
- l.105 I have a question about the problem setting. When this paper described the transductive learning setting, it took over the notation from the supervised learning setting. Therefore, it looks to me at first sight that we i.i.d. draw $m$ points from $\mathcal{D}_X = {\rm Unif}[n]$. However, it is not true as we draw data points without replacement in a transductive setting. So, I would like to suggest to reconsider the description.
- l.249: μ should be capitalized.
- Figure 1: In the figure, 90% quantile is shown. Since the experiment was run 5 times, does it mean that 90 % quantile is in fact the second value from the top?
- Figure 1 (Bottom center): In Cora, the sample size n is varied.
- l.256: In the following we can show ... → In the following, we can show ...
- l.258: loos → lose
- l.261: I think the notation $\rho=O(p), O(q)$ is not appropriate. Does it mean $\rho=O(\min(p, q))$ ?
- l.285: vary → verify
- l.299: Cite the over-smoothing effect, as it was coined by existing works e.g., [Li et al., AAAI2019].

[Li et al., AAAI2019] https://aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16098


### Post-rebuttal comments

I thank the authors for answering my questions sincerely. The approach of this paper is classical as the main tool is the (transductive version of) Rademacher complexity. Therefore, the novelty is limited in that respect (cf. [N1] of my review comment.) Considering that, I keep my score. However, However, since I acknowledge the significance of the conclusions drawn from the analysis (cf. [N3] of my review comment), I will not oppose to accepting the paper.

limitations_and_societal_impact: - [L1] This paper discussed the limitation of the analysis in terms of model architectures (e.g., not applicable to the models with dropout or batch normalization)
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The problem addressed in this paper is an important area in theoretical understanding graph convolution networks. This paper discusses the transductive learning using the Rademacher complexity analysis with VC-dimensions and data dependent bounds. Further, the paper analyzes the special setting of the GCNII which is known to be robust against oversmoothing. Overall, a good paper, however, some of the interpretations of bounds are not clear, which require further clarifications.  
main_review: The study of generalization bounds for GCN is an important problem which has been recently studied by several researchers. This paper further adds insights to the study of generalization bounds using tranductive Rademacher complexity, VC dimensions, and residual networks. 

The study of transductvie Rademacher complexity for GCN has also been studied under restricted conditions in  Kenta Oono, and Taiji Suzuki: Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks (NeurIPS 2020). This reference is missing in the paper. It would be helpful to have some insight into how the  bounds given in the above paper are related to the proposed work. 

In general, the paper is written well. However, there are several typos. 
It is very useful to have a notations section to introduce mathematical notations. Otherwise, it is difficult to follow notations without searching through the paper. 
In line 684: Should dual be  \| \sigma S X\|_1 ?
Line 797: Line before the eq. 30, is it  s1?
Line 840 d_m in ?

Oversmoothing is an important aspect of GCN model that has gained theoretical attention. This paper also addresses this problem with the setting of GCNII. It is not convincing to use depth of 4 to explain the effect of oversmoothing in figure 2. It would be more clear if larger depths are considered as in [Che+20] where they considered depth from 2,4,...,64.
Further, it is not clear about the interpretation of the effect of oversmoothing from the bounds for plain GCN or the GCNII [Che+20] setting since the theory and experiments disagree as depth increases. Can authors elaborate possible improvements to bounds that can be made to obtain better interpretation in oversmoothing? 

Spectral analysis has been employed to explain oversmoothing in Kenta Oono and Taiji Suzuki: Graph Neural Networks Exponentially Lose Expressive Power for Node Classification, ICLR2020. In their paper, it has been shown that as the number of layers increases higher orders of eigenvalues quickly decrease to zeros leading to information losses. Can the generalization bounds be expressed with spectral components (e.g. eigenvalues)?

Finally, it is nice if the inductive setting can also be included in the paper. Is it possible to extend generalization bounds in the paper for the inductive setting?
limitations_and_societal_impact: Lack of usage of spectral analysis could be a limitation in interpretations of oversmoothing.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The aim of the paper is to provide generalization bounds for graph neural networks (GNNs) in the transductive setting. Several results are presented where the deviation between the expected loss on unlabeled data and empirical loss on labeled data is bounded using the Rademacher complexity of GNN hypothesis classes. 
main_review: The paper is well-written and rigorous. While the presented results seem helpful towards obtaining a better understanding of the performance of GNNs, the authors may find it useful to discuss the following points more clearly:

1. My major concern about the results in this paper is about the bound in Theorem 1. 

a. The result in Theorem 1 (and the following results) suggest that the generalization error should increase with the number of unlabeled samples n, due to the terms of O(n^2/(m(n-m))) and O(sqrt(log(n))) in the Rademacher complexity expression. However, none of the experimental results indicate an increase in the generalization error as n increases. I'm wondering whether the increase in the error with n as predicted by the theorems is a side effect of the proof techniques used in the paper, or there may potentially be certain graph topologies where such an increase can indeed be experimentally observed. 

b. In the bound in Theorem 1 and the following bounds, the error is seen to include a term of O(n^2/(m(n-m))). Regarding the distribution of labeled vs. unlabeled samples, this result implies that the error takes its smallest value when half of the samples are labeled (m=0.5n). This seems surprising, as one would expect the generalization error to be smaller if more samples are labeled. Is there an intuitive interpretation of this?

2. Theorem 2 suggests that the Rademacher complexity tends to increase with Gamma, which is also supported by the experimental results. Given that Gamma represents the alignment between the graph and the feature information, could the authors provide some interpretation about why the complexity of the GNN hypothesis family is higher when the information provided by the graph topology and the graph features are more aligned? I would intuitively expect the hypothesis function complexity to be smaller when the "intrinsic dimensionality" of the data space is smaller.

3. Corollary 1 and the results in Figure 2 suggest that as alpha increases, the generalization error decreases. However, considering the balance between the feature information propagating from the previous layers and the residual feature information coming from the first layer, one would normally expect the optimal value of alpha to be an intermediate value between 0 and 1 (i.e. one would not expect to obtain the best results at alpha=1). Some additional explanations would be useful here. 


4. Minor comments:
- In the bound in Proposition 1, what does the parameter "em" mean?
- I recommend that the authors proofread their paper to check for typos. There are several typos in the paper (e.g. "Randemacher complexity" in Theorem 1, "In the broader deep learning learning" in page 2, and several others).
limitations_and_societal_impact: The limitations of the work could be discussed in more detail.
review_title: null

Meta-review: This paper analyzed the generalization gap of GNNs based on statistical learning theory. First, this paper gives an upper bound of the generalization gap by using the VC dimension of the model, which is characterized by the rank of the adjacency matrix. However, it is shown that such a bound is vacuous. To overcome this issue, the authors give a tighter Transductive Rademacher Complexity (TRC) which is bounded by norms of $S$ and $SX$. They gave detailed discussions about the derived bound in some specific situations. They also discussed benefit of residual connections which reduce the generalization gap. 

Overall, this paper is well written, and the problems that the paper is analyzing is indeed important. This paper gives a detailed analysis on the issue of generalization ability of graph neural networks, which is valuable to the community.  
One of the biggest weakness of this study is that evaluating TRC is not new because it has already been addressed by Oono and Suzuki (2020). Unfortunately, this paper does not cite Oono and Suzuki (2020) nor give discuss relation to it. On the other hand, there are several interesting insights that were not indicated by Oono and Suzuki (2020). In that sense, this paper has novelty.

In summary, this paper gives an instructive theoretical analysis for GNNs and it can be accepted by NeurIPS.   
On the other hand, I definitely recommend the authors to include Oono and Suzuki (2020) and discuss relation to it.  
Decision: Accept (Poster)