Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces S-Mixup. It is a graph Mixup method, that can better utilize the node-level information between the pair-wise graph.

strength_and_weaknesses: ## Strengths
1. The problem is well-motivated. Indeed, graph data is highly structured, and the standard augmentation methods can easily destroy the key substructures, which can lead to unexpected biases.
2. The method is quite simple and straightforward. It first applies a graph pair-wise attention to learn a soft alignment score matrix. Then it utilizes this matrix to map graph 2 to the space of graph 1 for alignment.


## Weaknesses
1. Some key notations can be polished up. For example, in eq(5), authors are using A_2 to mix A_1, so the notations can be changed to $X_1’, A_1’, y_1’$.
2. Another question I want to confirm with the authors is, how this S-Mixup can be better than previous methods? I am aware that intuitively, it makes sense, but empirically, I think more qualitative results are required. Also in table 1, why S-Mixup can preserve motif? Can authors also help explain this further?
3. The logic of the placement of Sec 5 is a little confusing to me. Why do the authors want to study the node-level correspondence and graph transformation problems? They seem to jump out without any introduction. Besides, though the conclusion of graph transformation seems correct to me, but I don’t quite follow on why only the graph transformation is studied here? (the first sentence in Sec 5.2) A more common case is when the graph pairs have different number of nodes right?
4. Sec 5.1 and 6.4 can be merged.

clarity,_quality,_novelty_and_reproducibility: There are some sentences not clearly explained to me:
1. In the abstract, can authors explain what is “... any pair of graphs can be mixed directly to generate an augmented graph”?
2. In the introduction, what is “...  and perform mixup as in the case of images”?
3. The last sentence in te introduction can be polished up.

summary_of_the_review: I’m not an expert on graph with muxip. So I may leave the comments on this point (baselines and experiments) to the other reviewers. The other comments are put above.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper presents a new way of graph mixup by enforcing the mixed-up graphs to be softly aligned, via a node-level graph matching network. The graph matching network is based on graph-level similarity learning supervision, whereby its node-level features are utilized to compute the node-wise similarity, followed by a softmax normalization. The authors conduct extensive experiments with different datasets and different mix-up methods, and the improvements brought by the graph alignment step seem convincing
strength_and_weaknesses: **Strengths**

1. Enforcing node-level alignment in graph mixup tasks is an interesting and convincing effort.
2. The empirical improvements brought by the proposed alignment method seem significant and consistent w.r.t. other mixup strategies. 

**Weaknesses**

1. My major concern about this paper is that one of the main technical contributions of this paper, which is the node-level graph matching network, does not seem novel. The proposed graph matching network is simply adapted from Li et al. 2019, adding a softmax-based output after node-feature similarity computation. However, graph matching has been a research topic lasting for decades, and there exists both traditional algorithms and learning-based networks for the matching task. The authors seem to have not fully survived the graph-matching literature, and I believe there exist many papers that offer well-developed solutions for the alignment task in graph mixup. 

    For example, I suggest the authors try traditional graph matching methods, for example, RRWM (Cho et al. 2020), IPFP (Leordeanu et al. 2009), or FGM (Zhou et al. 2016), if the previous two methods cannot handle your problem because your graphs are too large. There are also recent deep graph matching neural networks (support node-matching) that are better motivated than the proposed approach, for example, nearly all deep graph matching networks use the Sinkhorn method instead of the proposed softmax method for normalization. The following two deep graph matching papers are suggested for the authors: (Wang et al. 2022) and (Fey et al. 2020).

2. Some graph mixup methods are introduced and discussed in the related work, but they seem to be not compared in experiments, such as SubMix, ifMixUp.  Can the authors explain why they are not compared?

References:
1. Li et al. Graph Matching Networks for Learning the Similarity of Graph Structured Objects. ICML 2019.
1. Cho et al. Reweighted random walks for graph matching. ECCV 2010.
1. Leordeanu et al. An integer projected fixed point method for graph matching and map inference. NIPS 2009. 
1. Zhou et al. Factorized Graph Matching. PAMI 2016.
1. Wang et al. Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching. PAMI 2022.
1. Fey et al. Deep Graph Matching Consensus. ICLR 2020.
clarity,_quality,_novelty_and_reproducibility: This paper is well-written and easy to follow. 
summary_of_the_review: This paper presents a graph node alignment-based graph mixup method, and the empirical results seem to be better than non-aligned graph mixup methods. The graph node matching network, which is one of the major technical contributions of this paper, does not seem novel considering the existence of both learning-free traditional graph matching solvers and learning-based graph matching networks that supports node matching. I suggest the authors to further survey the graph matching literature and improve the technical contributions of this paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a node assignmet based technique for graph data mixup, as mixup is a standard, popular and effective way of data augmentation for images, and its effectiveness is also recently explored in the graph area. The experimental results are convincing.
strength_and_weaknesses: Pros:

1) The paper is clearly written and the idea is interesting and novel.
2) The experimental results are convincing with state-of-the-art performance on public benchmarks.
3) The current setting is basically supervised learning, while I believe it can be extended to general cases like self-supervised learning (see the following suggestion on related works ECCV22, SIGKDD22).

Cons:

I did not find any specific concerns about the technical part of the paper. While the paper may acknowledge some more existing works to better position this work. 

I have some suggestions on expanding the related work part (if space permits or put some to the appendix).

In the related work part, the authors may also briefly discuss:
1) the works on graph matching, whose purpose is finding node correspondence either softly or in a hard manner. The authors may not be aware a recent ECCV22 paper [a] on graph augmentation for self-supervised graph matching, which I think is worth mentioning as it also augments multiple copies of graph with node correspondence.

[a] Self-supervised Learning of Visual Graph Matching, ECCV 2022

2) As graph edit distance (which is a more flexible technique to expand the mixup space) is also used in the paper, such related works are also needed to discuss in related work part. There are some recent papers on learning-based graph edit distance computing.

3) For mix-up based graph augmentation, there is another missed reference:
[b] m-mix: Generating Hard Negatives via Multi-sample Mixing for Contrastive Learning, SIGKDD 2022
clarity,_quality,_novelty_and_reproducibility: Good.
summary_of_the_review: See above comments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new data augmentation method for graph-structured data. Unlike Euclidean spaces, on graphs, it is difficult to define interpolation due to the lack of mapping between two different spaces. Using soft alignments, the authors map one graph to the other and perform Mixup. The authors claim that the proposed method preserves important subgraphs (motifs) and the graph size. Also, unlike manifold Mixup, it performs data augmentation in the input data space at an instance level.
strength_and_weaknesses: Strengths:
* The paper is well-written, and it has a comprehensive discussion about related work and the important aspects of data augmentation for graph-structured datasets.
* This paper theoretically analyzes the discrepancy between the Mixup ratio and graph edit distance. It is not clear whether data augmentation (or Mixup) respecting Graph Edit Distance will be more effective or not. But it is a start to explore Mixup with graph-related distance measures.
* The proposed method is simple and effective, and easy to implement. Compared to strong/recent baselines, the proposed method shows competitive performance. 
		
Weaknesses:
* In data augmentation, controlling the strength and diversity of augmentation is crucial. In this sense, preserving graph size and motif may limit the diversity of augmentation. Graph size preserving is not always desirable. In some applications, one may want to generate samples with diverse graph sizes. This paper needs discussion about it.
* The proposed method needs to be compared with broader related work such Hu et al. [1] GraphMix [2], Gaug [3] etc.
* Figure 2, (c) has links between red and blue nodes. It can be viewed that the cycle motif is broken. Does motif preserving mean here keep all the edges of one of the original graphs? So, unlike standard Mixup, in this framework, the information from other graphs can be added to the target sample as additive noise on the adjacency matrix and features. So, then is no edge/node drop of the target graph possible in this framework?

[1] Hu, Weihua, et al. "Strategies for pre-training graph neural networks." arXiv preprint arXiv:1905.12265 (2019).
[2] Verma, Vikas, et al. "Graphmix: Improved training of gnns for semi-supervised learning." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 11. 2021.
[3] Zhao, Tong, et al. "Data augmentation for graph neural networks." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 12. 2021.

Questions:
1.  In figure 3, the IMDB-BINARY case, vanilla achieved the best performance at the 100th epoch. How was the model selection performed? One purpose of data augmentation is regularization to prevent overfitting, but early stopping or model selection are handy ways to address this problem. If the model at the last epoch was selected for evaluation, it might be misleading.
2. The proposed method is limited to class-level tasks. Is it extensible to other tasks on graphs beyond graph classification?
3. In eq (4), M is used. Did you consider the square root of M as in the normalized graph Laplacian matrix?
4. What alpha was used for the beta distribution? How did you tune the hyperparameter? How sensitive is the performance gain to the hyperparameter tuning?
5. How do you make sure that the augmented samples have the same labels? Or do you interpolate labels as well?

clarity,_quality,_novelty_and_reproducibility: * Clarity: Overall, the method is simple, and the paper reads well.
* Quality: The paper compares the proposed method with mixup techniques for graphs. The main idea is simple, interesting, and more importantly, effective. 
* Novelty: It has some interesting contributions, although the framework is not general enough to apply other tasks on graphs.
* Reproducibility: The pipeline clearly was introduced, and I believe that it is reproducible. 
summary_of_the_review: Overall, this paper is well-written and studies the less-explored problem, data augmentation for graphs. The framework is simple and effective. The properties and behaviors of the proposed method have been well analyzed. More qualitative analyses comparing augmented samples by baselines will be useful to understand the value of this work. Also, the limitation of this work is not well discussed like when this work fails and when this work is effective. With some minor updates incorporating reviewers' comments, this paper can be further improved.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes S-mixup, an approach for using the well-known mixup methods on graphs. The authors present calculating an assignment matrix for the corresponding nodes between the two graphs so that they can use the image-like mixup approach in this domain. 
strength_and_weaknesses: **Strengths**:
- The paper is well-written and clear.
- The method is straightforward and easy to implement.


**Weaknesses**:
- Pairwise node correspondence calculation of the graphs is expensive. There should be a thorough time and computation complexity analysis between the proposed method and the baselines.
- The performance improvement is incremental with respect to the baseline method, especially when the encoder is slightly more powerful (GIN instead of GCN). This raises the question that with large graphs and more powerful graph encoders, how much S-mixup can be practically useful.  


clarity,_quality,_novelty_and_reproducibility: The paper is well-written and clear.\
The novelty is limited and since the method is straightforward, I believe reproducibility wouldn't be an issue here. 
summary_of_the_review: Most of the points are mentioned in the strength and weaknesses section but in summary, although S-mixup shows performance improvements by considering the calculation cost and the limited novelty, I think that the method isn't ready for being published at this stage.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents a data augmentation method for graphs by mixup. It enforces the mixed-up graphs to be softly aligned, via a node-level graph matching network to create a convex combination of a pair of inputs. Extensive experiments are conducted on different datasets and comparing different mix-up methods, the proposed approach seems to consistently improve performance.
I personally believe that more work on data augmentation for graph structured data is needed and this work definitely goes in the right direction. It seems, unfortunately, that few comparisons are simply left out -- i.e. ifMixup -- and that the claim on novelty regarding the soft alignment triggered some concerns with the reviewers. The contributions need to be clearly defined and all the relevant prior art should be included whenever necessary, and it seems reviewers pointed at this problem with the current manuscript. If the matching step is not novel then the overall contribution weakens a lot in my opinion.
For the above reasons I am afraid I have to ask the authors to strengthen their contribution and to resubmit.


justification_for_why_not_higher_score: Considering other papers in my batch and the comments of the reviewers, especially the polarizing negative ones, I think some work is still necessary before accepting this work. In particular for what concerns novelty.
Decision: Reject