Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: # Summary

The paper presents PAC-Bayesian generalization bounds for two classes of graph neural networks: graph convolutional neural networks and message passing graph neural networks. The paper essentially adapts Neyshabur et al. (2017) PAC-Bayesian margin bounds for neural networks to graph neural networks and expectedly the bounds contain terms that depend on the degree of the underlying graph. The main technical contribution of the paper is a perturbation bound for GNNs from which the main results follow. 

# Strengths

1. The paper presents the first PAC-Bayesian generalization bound for GNNs and the authors show that their bounds are tighter than the Rademacher based generalization bounds developed by Garg et al (2020) ignoring constants.

# Weakness

1. The bounds do not necessarily give important insights into generalization performance of GNNs. Bounds are still vacuous: bounds become exponentially large with number of layers and degree.
2. For a theory paper that purely focuses on obtaining generalization bounds for GNNs, the technical contributions are weak. The only technical contribution is the derivation of perturbation bounds for GNNs which are pretty easy to obtain. If this is not the case, then this needs to be highlighted.
3. It is not sufficient to compare bounds on real world data at some fixed sample size for empirical comparison with Rademacher based bounds, especially given that constants are dropped. Synthetic experiments with varying samples, graph families (e.g. Erdos Renyi graphs) and different degree distribution are needed to show how the bounds compare against Rademacher based bounds.

# Justification for rating

The generalization bounds themselves provide very limited insights into generalization performance of GNNs especially given recent results that show that uniform convergence bounds may not be able to explain generalization of deep neural networks. While this is an issue with existing theoretical results for deep neural networks, the paper does not significantly improve the state-of-the-art in theoretical understanding of GNNs in terms of new tools and proof techniques. For a theory paper that purely focuses on generalization bounds, this is a significant shortcoming.

# Other comments

1. Misleading use of the word "statistics" throughout the paper. Statistics are quantities that can be computed only from the data. The paper repeatedly refers to functionals of parameters as "statistics".
2. What do you mean by: "actual posterior distribution induced by learning process may be very different from Gaussians" ? PAC-Bayesian analysis is done for Gibbs classifiers and Neyshabur et al. provide a way to convert these convergence bounds for deterministic classifiers. The learning process does not induce a posterior distribution over weights (assuming deterministic initialization and removing randomness like dropout).
3. D is overloaded to denote both data distribution and diagonal degree matrix.
review_title: Weak theoretical contributions

final_score: rating: 7: Good paper, accept
review_content: In this paper, the authors propose generalization bounds for GNNs, both convolutional and standard message passing variants. The result is a generalization of those for CNN/MLP architectures with relu activation functions. The analysis method closely follows those established in the former settings as well. The specific setting they consider is where each sample in the dataset is a graph. The proof relies on ensuring small perturbations in the GNN weights don't cause large deviations in output distributions. The resulting PAC-Bayes bound is shown to be tighter than corresponding Rademacher Complexity bounds. 

The paper is well written and the results look reasonable (though I didn't check the proofs). A couple of minor comments/questions:

1. Does assumption A4 cause things to be a lot looser than needed? Consider a star graph, then d ~ number of nodes in the graph. But this is just for one node. 

2. How would things change if your data is actually not iid ~ D, but the entire dataset is the graph (so you just have one graph), and you need to classify the nodes? I'm guessing there's parts in the proof where the iid assumption is necessary. 
review_title: Official Blind Review #2

final_score: rating: 7: Good paper, accept
review_content: ##########################################################################
Summary:
This paper provides results of generalization bounds for two types of GNNs: GCN and MPGNN. The presented analysis follows the framework of Neyshabur 2017 to construct posterior by adding random perturbations so that the PAC-Bayesian technique can be applied. The main contributions are the perturbation analysis for GCN and MPGNN, which results in a bound depending on the graph statistics. The paper compares the derived bounds with existing results, and examines the bounds numerically through experiments.  

##########################################################################
I find the paper well-written and overall technically sound. I vote for accept.
##########################################################################

Strength:

This paper studies an important problem, as GNNs are popular learning models.

While the overall idea follows directly from Neyshabur 2017, the presented perturbation analysis is not trivial, making the current work a good advance.

This paper is well-organized, with nice discussions on the state-of-the-art as well as on the overall technical review. It is appreciated that the paper is self-contained, and the preliminary results are provided in the appendix (though they can be found in earlier papers).

The paper provides a detailed comparison between the derived bounds with the existing bounds. The results of this paper are natural in the sense they generalize that the results in Neyshabur 2017 for MLPs.


Some concerns:

For the proofs of Theorem 3.2 and 3.4, I would suggest decomposing it into several lemmas, by first identifying the covering (and the weight-independent variance) and then plugging the values into Lemma 3.3 (and Lemma 3.1) and further into Lemma 2.2

To avoid ambiguity, using D_KL(u+w||P) is better than D_KL(Q||P) in this paper.

Given the heavy notations, having a notation table in the appendix could be very helpful.

What are the key difficulties in applying the proposed framework to other GNN architectures? 

review_title: A good theory paper.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper, by PAC-Bayesian approach, proves the generalization bounds for the two primary classes of graph neural networks—graph convolutional networks and message passing GNNs. By experiments on four datasets, it shows that the generalization bound in this paper is tighter than the existing Rademacher complexity bound. 

This is an interesting question about generalization bound, especially, such a discussion by  PAC-bayesian approach for graph neural networks is lacking. However, there are a few issues/comments with the work:

1.The proof techniques in this paper are mainly from Neyshabur et al., 2017. The theoretical contribution and novelty are limited;

2.For the generalization bounds, they are exponential dependence on depth. So for $d>1$, it means that the deeper it is, the worse it is for the graphical neural network. Is that so?

3.It will be better to use more empirical experiments  to verify the relationship between the generalization bounds, node degrees, and depth;

4.For Assumption 4 in this paper, it assumes that “no loop”, for the practical application of graph neural networks, loop generally exists. This will limit the potential application of this theory. in this paper;

5.According to the theory established in this paper and the # graphs and max # nodes of the datasets provided in APPENDIX, PROTEINS and IMDB-BINARY should have more similar log bound value than IMDB-BINARY and MDB-MULTI. In Figure 1, it seems to be the opposite, why? Is it because the feature dimension also plays an important role in the log bound value? 

6.The format of mathematical equations is inconsistent, for example, equation (1) without punctuation,  but equation (3) with punctuation.

Overall, I think this is an interesting piece of work that might interest researchers to explore the  questions around graph neural networks. However, I think the results need to be analyzed more carefully, especially on the depth. Moreover, the novelty of the technology is relatively limited.
review_title: Generalization Bounds for Graph Neural Networks

Meta-review: This paper gives a new PAC-Bayesian generalization error bound for graph neural networks (GCN and MPGNN). The bound improves the previously known Rademacher complexity based bound given by Garg et al. (2020). In particular, its dependency on the maximum node degree and the maximum hidden dimension is improved.

This paper gives an interesting improvement on the generalization analysis of GNNs. The writing is clear, where its connection to existing work and its technical contribution are well discussed. 
The biggest concern is its technical novelty. Indeed, the proof follows the out-line of Neyshabur et al. (2017). Given that the technical novelty would be a bit limited, however, the analysis should properly deal with the complicated structure specific to GNNs which makes the analysis more difficult than usual CNN/MLP and requires subtle and careful manipulations. 
In addition to that, the improvement of the generalization bound is valuable for the literature (while the improvement seems a bit minor for graphs with small maximum degree). 

For these reasons, I recommend acceptance for this paper.
Decision: Accept (Poster)