Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: A novel generalization bound for a class of message passing neural networks (MPNNs) on graphs is derived. The generalization gap decreases with the average number of nodes of graphs sampled from the data distribution. This is in contrast to other generalization gaps in the literature, which typically increase in the number of nodes or degree. This result relies in part on a convergence result that the authors prove, which bounds the expected difference of an MPNN output on sampled graphs and the output of a newly-defined continuous MPNN on the underlying random graph model.

strengths_and_weaknesses: Strengths:
1. The derived generalization error contains a term that decreases in the size of the  graph, in contrast to previous results in which error increases in the size of the graph. This is novel, and may have important implications.
2. The paper defines a continuous analogue of message passing neural networks with mean aggregation, an important class of GNNs. Previous work has done this for spectral GNNs that use polynomial filters of the normalized graph Laplacian. Unlike previous work, this work develops convergence bounds that are uniform in the choice of model, which is important for deriving useful generalization bounds.
3. The assumptions and data distribution mostly seem reasonable to me.

Weaknesses:
1. Minor:  numerical experiments are a bit lacking, and it may be interesting to consider things like Lipschitz continuous graphons of varying constants, or other GNNs. See also the questions section.

Note: I did not have time to check the proofs of this paper, which are very long and full of calculations.


questions: 1. In Appendix D, it is mentioned that you approximate the continuous MPNN with an MPNN on a large graph (lets call this output $Y \in \mathbf{R}^F$), which is then subsampled to smaller graphs, for which the ''finite'' MPNN outputs (call these $Z_1, \ldots, Z_{50} \in \mathbf{R}^F$) are compared. This may make it easier for the ''finite'' MPNNs to be close to $Y$. Perhaps it would be better to sample several large graphs, giving outputs $Y_1, \ldots, Y_{a} \in \mathbf{R}^F$, and then measure how close ''finite'' MPNNs are to $\frac{1}{a} \sum_{i=1}^a Y_i$ on independently sampled small graphs.

2. Perhaps mention in Section 1 that your analysis holds for mean aggregation (apologies if I have missed the mention).

limitations: Yes, limitations are mentioned in the conclusion.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper talks about the generalization error of message passing neural networks. 

By assuming graphs are sampled from random graph models (RGM), the authors define continuous MPNN (cMPNN), and prove in Theorem 3.1 that the error between cMPNN and the corresponding graph MPNN decreases as the number of nodes in the graph increases, which is the main contrinution of this paper. With such results, the paper further proves a generalization bound in Theorem 3.3. 

Numerical results confirm the correctness of the theoretical analysis. 
strengths_and_weaknesses: Strengths:

* The theoretical analysis in this paper is quite solid, which first builds the relationship between graph MPNN and continuous MPNN, then states the convergence and generalization results. Even though this paper is very theoretical and not easy to read, the definitions and preliminary knowledges in this paper are written clearly, which provides backgrounds to readers not very familiar with the theory involved in this paper. 

* The convergence bound, which decreases as number of nodes increases, seems novel compared with previous bounds. 


Weakness:

* One of the main contributions of the paper is that the generalization bounds becomes smaller as the number of nodes in the graphs becomes larger. This is indeed an improvement over previous bounds. However, as a practitioner, it is not clear to me what insights such theoretical work could bring to reality. For example, how could we utilize the theories in this paper to guide the design of MPNNs with lower generalization error? 


questions: * Citation format is not consistent with NeurIPS 2022, need to follow the template provided. 

* This paper builds its theoretical results with several assumptions. It would be great to see some discussions about which assumptions are reasonable, and which assumptions might be too strong to deviate from reality. 
limitations: As mentioned by the authors, this is a theoretical work with no clear negative social impact.

The two limitations in this work are concluded in section 5 of the paper.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this work, a new generalisation bound for MPNNs is proposed. Specifically, studying MPNNs over graphs and their continuous-space counterparts, it is showed that the uniform generalisation error can be upper-bounded by a formula that improves, not only by increasing the number of training graphs, but also by increasing the number of nodes in these graphs. This forms the foundation of a useful 'peace-of-mind' result: a MPNN-based graph classifier should generalise well even over small numbers of training graphs, provided those graphs are sufficiently large. The bound is verified empirically by training MPNNs on a random geometric graph model.
strengths_and_weaknesses: **Originality**:
The derived bounds appear novel, and compared to prior art (Table 1), they feature for the first time a term that decays as the graph size increases. This is enabled through an original Monte Carlo lens of analysis, which allows to treat individual nodes as samples, even though the task is specified on the graph level. Specially, a novel mathematical apparatus is developed to handle the correlations between the nodes' neighbourhoods (since the nodes cannot be assumed to be provided i.i.d.).

**Quality**:
I find the mathematical results in this work to be solid. However, I believe the experimental evaluation could benefit from some aspects of real-world analysis -- see the significance section for more details.

**Clarity**:
The paper is, for the most part, well-written and somewhat easy to follow. However, I find that the paper could really benefit with making its aims (and practical implications) clear significantly earlier. As it stands, it takes until halfway of page 2 before it is even slightly clear what the implications of this work would be for the GNN practitioner, and even then the link feels a bit loose and 'left to the reader'. It would be highly beneficial to provide a clearer discussion on what the work's main contributions and its implications are, way earlier in the paper.

**Significance**:
While the obtained bounds are clearly of significance compared to earlier work in the area, I find the experimental evaluation to be fairly limited in comparison---focusing only on one specific generative model of graphs. It will strengthen the results of the paper significantly if we could connect them to 'real-world' distributions of graphs.

For example, one might perform a similar experiment to Section 4, over the various graph classification datasets in the TU Dataset benchmark (https://chrsmrrs.github.io/datasets/). For any one of those datasets, we can observe the (average) number of nodes, and compare the observed generalisation error w.r.t. an (empirically built) RGM over the graphs in the dataset. This would correspond to a particular 'point on the curve' of Figure 2, specialised on a particular dataset's generative distribution.

**Overall**:
All things taken into account, I think this has potential to be a strong paper, and a few more improvements would be needed before it would pass the bar of acceptance. Theoretically, it appears very solid (though I will remark I did not check the proofs in the Appendix at great length), but practically it is somewhat lacking in evaluation and motivation.
questions: Q1. Could you concisely clarify the practical implications of your work? Could you make this discussion clear in your paper from an early stage?

Q2. Could you provide additional experimental evidence for your bounds? Either on a wider variety of generative distributions, or (ideally) on several 'points' corresponding to sizes / distributions of existing graph classification datasets in the literature.
limitations: No concerns.
review_title: null

Meta-review: metareview: This paper gives a new approximation and generalization error bound for a class of MPNN (Message Passing Neural Networks) in a setting where the underlying graph is randomly generated. First, a discretization error from the continuous limit is given, and second the generalization error on a finite training set is given. Some numerical experiments are also given as an empirical evaluation of the theory.

Overall, this is a solid theoretical work with sufficient novelty. The rate of convergence is new and the community would benefit from the analysis. The presentation is also good. The readers can grasp the overall contribution rather easily and the theoretical results are also clearly described.
The major weakness of this paper is the numerical experiments. However, combined with the theoretical contribution, this paper has enough value. 

The authors properly responded to the reviewers' questions. An additional experimental result is also given. I recommend the authors to include the additional experiment properly to enhance the empirical evaluation.

In summary, this paper gives a good contribution and can be accepted. 

# minor point: (1) The citation style is not of NeurIPS standard. Please look at author instruction. (2) The abstract is presented in the Italic style. However, the standard format is the Roman style. I recommend to fix it. 


confidence: Certain
Decision: Accept