Venue: NeurIPS 2022 Conference

Reviews:

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: The paper focuses on how to generalize GNNs to graphs of different sizes in graph classification. Previous works either add an ad-hoc strategy or require access to test graphs. In this work, the authors propose a regularization method based on graph coarsening techniques to improve the size-generalization of GNNs for graph classification. Empirical results show that the performance will be improved up to 30% with the proposed regularization method. 
strengths_and_weaknesses: Strengths:
* The paper proposes a regularization strategy that improves the size-generalization ability of GNNs for graph classification. 
* Empirical results show that GNN models with the proposed regularization strategy achieve comparable or better size-generalization performance than baselines. 

Weaknesses:
* The method is straightforward and the novelty is limited. The paper combines existing coarsening techniques and an existing metric (i.e. CMD) for the regularization. 
questions: The paper uses the SGC coarsening algorithm in the experiments. Do the authors try other coarsening methods and evaluate how the coarsening algorithm affects the regularization performance?
limitations: The authors discuss the limitation in Sec 3.1 about the assumption that there are some size-invariant properties that determine the label.
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: The paper proposes a new regularization strategy for improving size generalization in GNNs. The high-level idea consists of applying coarsening algorithms to original training data and then enforcing node embeddings from the original graph and coarsened ones to be closer. The paper considers four benchmarks for graph classification to assess the effectiveness of the proposal.


strengths_and_weaknesses: Overall, the paper reads well and the proposed method is rather simple and general. Also, the problem of interest seems relevant. 

However, the paper lacks stronger motivation behind some design choices, such as graph coarsening algorithms and discrepancy metrics. For instance, CMD is chosen because "it has proven to be successful and stable as a regularization term for non-linear models".  Also, the experimental setup is weak as it only includes four molecular datasets, and follows an existing setup (Bevilacqua et. al., 2021). Moreover, the analysis section provides no principled assessment of the method, mostly showing that the proposed regularization somehow affects node representations.  

Strengths
- Simplicity: the idea is somehow intuitive even though it is not theoretically grounded.
- Promising results

Weaknesses 
- Limited evaluation setup
- Poor understanding regarding the applicability of the proposal (only general comments are made in Section 3.1 --- Limitations) 

questions: - As stated in Section 3.1, the proposal assumes labels are not too sensitive to size. Is there any connection between this assumption and the chosen benchmarks? Why is the proposed method only validated using four molecular datasets?
- It would be helpful to have an ablation study considering different discrepancy metrics. For instance, would simple distance-based metrics obtain good results? 
- The proposal seems to have the potential for improving pre-training. When evaluating existing strategies, people often split molecules according to their scaffold [1]. Showing gains to that task would increase the impact of the proposal.
- Accuracy results could go in the appendix.
- Showing training times would support the claim that the proposal incurs a 50% overhead.

[1] https://arxiv.org/pdf/1905.12265.pdf
limitations: The paper briefly describes the limitations of the proposal.
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 presents a simple and intuitive regularization technique to make graph networks generalize better to graphs with different sizes, by employing coarsened representations of the same graph and encouraging alignment of node embeddings between such graphs.

**EDIT after rebuttal:**

I thank the authors for clarifying important aspects of the evaluation procedure. It appears my assumptions were incorrect. I therefore recommend that the paper is accepted, as it provides a simple, clear, novel and effective mechanism to tackle an interesting problem for the graph machine learning community, something which is rare these days.
strengths_and_weaknesses: It is rare to find and review a paper which clearly presents a simple, intuitive and sensible idea to this kind of conferences. Overall, it was a pleasure to read and very clear under all aspects. The paper seems technically sound, although it is not clear how the specific choice of CKA influences the results, as it compares graph representations of original and coarsened graphs which have different dimensions (if my understanding is correct). The underlying motivations of the paper is clear and the proposed solution seems simple enough to be used in everyday research/industrial contexts. Perhaps it is not very clear what is the computational complexity of the regularization loss, and the authors may want to consider Section 4 after the experimental setup is introduced (see my first question below).

Despite the paper being of high quality in many respects, I have serious concerns about the experimental protocol which led to the creation of Table 3, the main empirical evaluation of the paper. From lines 219-234, it emerges that most hyper-parameters where chosen from [6], which is reasonable as long as the empirical setup stays the very same. 

What appears definitely less reasonable and fundamentally wrong seems to be:
- using the same settings of $\lambda$ and $C$ for all datasets and models after looking at a single dataset (see lines 224-225) and Table 3 in the appendix B
- lack of information, either in the appendix or in the main paper, about the values of $\lambda$ cross-validated against the $\textbf{validation}$ set
- Evidence, by looking at Table 4 (caption, main paper) and Tables 2,3 (appendix B) that the hyper-parameters have been set after looking at the MCC performances on the $\textbf{test}$ set. This would mean that the authors cherry-picked the results that maximize the performances on the test, rather than choosing them on the validation set. The authors are strongly encouraged to honestly and openly comment on this; it is possible that my evaluation is incorrect, but the combination of lines 275-277 with 224-225, together with the caption of Table 4, seems to point in this direction.

Minor comments:

- while one usually assumes that the coarsening ratio reflects the percentage of retained nodes, it may be helpful to explicitly write this in the paper.
- It is known that a structure-agnostic baseline can produce state of the art results on PROTEINS, whereas it struggles on NCI1 for instance. It may have been a good idea to make an hyper-parameter study on the latter rather than the former dataset (but on the validation set)
questions: - Section 4: we have no details about the experimental procedure used here. Which lambda values have been used here to produce Table 1? Maybe it would be better to include this analysis in Section 5, so as to improve the overall organization of the paper.
- How does the distribution over the sizes of the graphs changes after pre-processing? This analysis could be interesting in datasets where graphs' sizes greatly vary, e.g. social datasets from TUDataset benchmarks page.
- From Section 3.1., why not trying a single experiment with much higher coarsening ratios? This could be a nice addition to the paper. Social datasets could be a good option here as well.
limitations: Limitations of the paper mainly lie in the experimental results, which may be invalid if my argument is correct.
review_title: null

Meta-review: metareview: This work proposes a regularization approach (based on graph coarsening and alignment) to allowing graph neural networks to generalize across different graph sizes. The approach proposed here is simple, yet shown to be effective. While the reviewers had some concerns regarding this paper and the results in it, these were alleviated to a sufficient extent in rebuttal so that currently one reviewer outright supports acceptance, and the others lean towards acceptance. I agree with the opinion supporting acceptance of the paper, especially given the remark about the value (and rarity) of simple, clear, and effective solutions to important problems, which I agree is the case here. Therefore, I recommend accepting the paper, and I would like to encourage the authors to take into account the reviewers' comments (and the additional points included in the responses to them) when preparing the camera ready version.
confidence: Certain
Decision: Accept