Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work studied the research problem of graph data augmentation for supervised graph classification. The authors proposed G-mixup that performs mixup on graph data via graphon generators. Due to the irregular characteristics of graphs, instead of directly mixing up the data objects, G-mixup mix up the graph generators. 
main_review: Pros:
1. The graph-level data augmentation methods have been mainly focusing on augmentation for unsupervised graph learning, and the graph data augmentation for supervised graph classification is rather underexplored. This topic is interesting and worth studying.
2. I like idea of using mixup on graph generators instead of directly on graphs, which is simple yet reasonable.
3. The authors provided good theoretical justification on their proposed method.

Cons:
1. Missing related works: [1][2]
2. The design of G-mixup seems to rely on the assumption of "graph topology between classes are divergent" (point 3 in the end of page 1), the theoratical justification (Thm 1) and observations in Fig 2 both support it. Moreover, other than being able to generate more data to improve the model's generalization, G-mixup also tries to help the model to learn such topological patterns. Therefore, I wonder how much does this information help on the node classification. For example, what if we concate $W_{\mathcal{G}}$ with $\mathbf{h}_G$ for all $G \in \mathcal{G}$ and directly use this new graph representation for node classification? Such ablative experiments would make this work more compelling.
3. In Table 2, I noticed that G-mixup showed significant performance improvement on Reddit-B with GCN, while showing mostly marginal improvements under all other settings. The authors should give more explaination on that.
4. I would recommend the authors to use the term "graph data augmentation" instead of "graph augmentation" to avoid potential confusion with a different problem in graph theory.

[1] Data Augmentation for Graph Neural Networks, AAAI'21\
[2] Graph Contrastive Learning Automated, ICML'21
summary_of_the_review: The proposed method is interesting, but the experiments can be improved.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes to leverage graphon as a graph generator to adapt Mixup from vision and text to graph classification. It works as follows. A graphon, which aims to capture the existence probability of an edge between any two nodes in a graph, is first estimated for each class of the training graphs. Next, two random graphons are mixed with mixing ratio \lambda, forming a mixed graphon. Finally, graphs are sampled from the mixed graphon as synthetic graphs for training.  The proposed method is evaluated using graph classification accuracy and robustness to graph corruption, showing improvement over baseline models. Applying Mixup to graph samples is an interesting and important research topic, but I think the paper in its current form is a bit immature.
main_review: The paper introduces a novel attempt of applying Mixup from vision and text to graph data. The idea of leveraging graphs being sampled from estimated graphons sounds interesting to me. On the other hand, I have the following concerns regarding the paper.

1.	The proposed method bases on a strong assumption which deserves further justification. That is, each class has a graphon and this graphon can be accurately estimated. I would like to see some theoretical proof and/or analysis on that. Such assumption also raises the question whether such graphon estimation can be used for graphs with node and edge features; it would be useful if the authors could shed some lights on that. 

2.	Theorem 2 suggests that in order to allow the synthetic graphs sampled from the mixed graphons to preserve the discriminative motifs, one needs sufficiently large sampled graphs. This assumption of g-Mixup makes me wonder that at the earlier stage of training, the synthetic graphs cannot preserve the discriminative motif of the graphon. I wonder how this guarantees the proposed g-Mixup would work. In other words, the synthetic graphs may be noise at all. Also, since the addition and deletion of graph edge in g-Mixup are based on the learned (imperfect) graphon, I think it may encounter the manifold intrusion issue when mixing graphs (Guo et al. at “mixup as locally linear out-of-manifold regularization”, AAAI2019). 

3.	The experiment section is quite weak in its current form. 

     a.	A critical baseline is missed in the experiment. The proposed g-Mixup is closely related to the MixupGraph approach as proposed by Wang et al. (“Mixup for Node and Graph Classification”, WWW2021). Mixing the embeddings resulting from the READOUT function of GNNs is much easier to be implemented than the g-Mixup method proposed here, so it would be interesting to see the comparison between the two approaches. 

     b.	It would be useful to provide ablation studies to show how accurate are the graphons estimated for the datasets (namely Equation 3), and how such estimation impacts the performance of the g-Mixup.

     c.	There is a parameter n, i.e., the number of nodes to be generate by the graphon. How this number impacts the performance of g-Mixup?

     d.	When estimating graphons from training data, K is used as the average number of nodes in all graphs. How the K was set in testing is not clear to me, and how different Ks impact the g-Mixup performance?

     e.	The datasets used are without nature node features, I wonder how the proposed method would perform on graphs with node features. 

      f.	From Table2. The accuracy improvement over vanilla baselines is minor, in particular for the powerful model GIN. This makes me wonder why one needs extra computation cost for g-Mixup?

     g.	Also, for dropEdge, 4 layer GCN and 5 Layer GIN seem a bit too shallow to me. DropEdge typically performs well on deeper GNNs such as six to eight layers. 

     h.	In Table3, it would be useful to also compare with dropEdge and GraphMixup. 


Other comments:
1.	The sentence at the end of page one: “thus prohibit us from directly adopting the Mixup strategy to graph data”. “Prohibit” here is a bit strong to me, although I think it is quite challenge to applying Mixup to graph input. 
2.	Last paragraph in section 1. “Since directly mixing up graphs is intractable,”. It would be helpful to make it specific why and how the intractable occurs here?
3.	Notations are inconsistent. Such as N(v_{i}) vs. N(i); k and n refer to nodes and graphs in different places (see end of section4.2). 
4.	Typos: first sentence of section 4.2 “propose the following the theorem.”; middle of second paragraph in section 4.3: “on a estimated…”.

summary_of_the_review: Some key assumptions of the proposed method are not well justified. Also, the experimental study is quite weak in its current form.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes the mixup method for graphs which is based on the concept of the graphon. Specifically, G-mixup first estimates the graphon for each class of graphs with the same label then interpolates the graphons of different classes of graphs. Finally, they generate the new graphs from the interpolated graphons to produce the mixed graph with a mixed label.

The authors theoretically show that G-mixup can preserve the different motifs of the two different graphs into one mixed graphon. In experiments, they empirically show that the G-mixup improve the generalization and the performance of existing GNNs on several graph classification task.

main_review: ## Strengths

* Clear contribution that generalizes the mixup [1] to the graph data. Although mixup has shown to be an effective data augmentation method in the image and text domain, it has not been applied to the graph domain due to the non-Euclidean characteristic of a graph. Therefore, the contribution of this work is clear since this work makes the mixup be applicable to the graph-structured data by introducing the concept of the graphon. 
* Well-written. Especially, it is easy to understand the concept of this paper through the figures and examples. The theoretical justification of the method clearly shows the G-mixup is effective to generate the mixup of two graphs of different classes on the theoretical side. In addition, the analysis in Section 5.2 empirically shows that the G-mixup can generate a well-mixed graph of different classes.

## Weaknesses
The empirical results are not sufficient to show the effectiveness of G-mixup.
* Baselines are not enough. I wonder that why the authors did not include the experiments against Manifold Mixup [2] although the authors refer to it in the discussion.
* Besides, several other baselines [3,4,5] including simple augmentations should be compared against the G-mixup.
* Experimental setting is too limited. Since the G-mixup mainly focuses on the improvement of graph neural networks on the graph classification task, it is important to show its effectiveness in various settings including dataset and base models. For instance, I recommend authors include the experiments on the classification task of a biomedical graph (e.g. molhiv dataset in Open Graph Benchmark [6]).
* In terms of the base GNN model, I believe the experiments on the GNN with the recent pooling [7,8] method will also be helpful to show the effectiveness of G-mixup for the performance improvement on the classification task.

Overall, the experiment part should be improved.



### References
[1] Zhang et al., mixup: Beyond Empirical Risk Minimization, ICLR 2018.

[2] Wang et al., Mixup for Node and Graph Classification, WWW 2021.

[3] Zhao et al., Data Augmentation for Graph Neural Networks, AAAI 2021.

[4] You et al., Graph Contrastive Learning with Augmentations, NeurIPS 2020.

[5] Zhou et al., Data Augmentation for Graph Classification, CIKM 2020.

[6] Hu et al., Open Graph Benchmark: Datasets for Machine Learning on Graphs, NeurIPS 2020.

[7] Bianchi et al., Spectral Clustering with Graph Neural Networks, ICML 2020.

[8] Baek et al., Accurate Learning of Graph Representations with Graph Multiset Pooling, ICLR 2021.

summary_of_the_review: This is an impressive paper but there is a lack of experiments.
I am willing to upraise my score if the authors successfully address my concerns regarding experiments in the rebuttal.

------------
After rebuttal: In this version, the experimental results seem convincing. I raise my score from 5 to 8.
review_title: null

Meta-review: This work tries to extend mixup to graph structured data, where graphs can differ in the number of nodes, and the space is not Euclidean.  This is achieved by G-Mixup, which interpolates the generator (graphon) of different classes of graphs through the latent Euclidean space.  Experimental results show some promise.

Several concerns have been raised by the reviewers, and although the rebuttal helped, some concerns remain.  For example, how to confirm that the graphon can be accurate estimated.  Several weakness in experiment is also raised, and a revision is needed before the paper can be published.
Decision: Reject