Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper shows a very simple technique for performing input-space mixup on graphs, in which the vertices are put into an arbitrary order and dummy vertices are added to make the two graphs being mixed have the same number of vertices.  Mixing is then performed on the vertices and edges.  The improvements are excellent and seem to be SOTA on all benchmarks considered, often by nice margins.  

Detailed Notes from reading paper: 
  -Mixing on graphs.  Theoretical guarantee that mixed graphs avoid intrusions.  
  -Example of intrusion on mixed graphs is interesting, simple, and logical.  
  -Proposed algorithm is "Intrusion-Free Mixup" ifMixup.  
  -Edges and nodes take interpolated values.  Labels are interpolated based on edges.  
  -Can recover source graphs from mixed graphs.  
  -Task is to convert each graph into a single class (as opposed to each node having a class label).  
  -Each node is assigned a distinct index, dummy nodes are created to make each "graph" same size.  Dummy nodes have no edges.  
  -First construct "soft" edges by mixing edges between two graphs.  Network needs to be able to take soft edges.  
  -Proof that this graph mixing operation is invertible.  
  -ifMixup also shows benefit from more depth, as compared to baseline (which is probably badly overfitting).  

main_review: This paper proposes a very simple and logical algorithm for performing input mixup on graphs, and achieves excellent results with this technique across a wide variety of datasets.  It is also shown that this logically allows one to gain improvements from larger models and also from larger mixing rates.  It suggests many natural and interesting follow-ups, such as doing this same mixing in random layers, yet I feel this is a healthy and useful contribution for the field.  

Small Comments: 
  -Improvements are pretty nice and the table is very readable!  
  -Additionally, improvement's stability as we increase mixing rate is nice to see.  
  

summary_of_the_review: The paper shows a way of interpolating graphs for graph classification and achieves excellent empirical results while showing that the interpolated graphs are invertible functions of the original graphs, avoiding the underfitting issues that may occur with other techniques for applying input mixup to graphs.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a mixing strategy for graph structured samples. This strategy is works as follows : 1) take a pair of graphs 2) assign a node index from 1 to N to each node in the graphs, where N is the number of nodes in the larger graph. 3) for the smaller graph, create dummy nodes so that the total number of nodes in smaller graph becomes N. 4) Mix (interpolate) the node features and edge connectivity of the nodes with same indexes from the two graphs.

The main claim of this paper is that, such kind of mixing avoids the "manifold intrusion" problem.
main_review: Strength:

1. Extending Mixup for Graph structured data is an important open problem and this paper attempts to address this.
2. Paper is written clearly at most places, however the mathematical notation in Section 3.3 can be simplified. This section is presenting a very simple argument which can be given without using so much mathematical notations.

Weakness:

The main claim of the paper that the proposed method avoids Manifold Intrusion, is unsubstantiated. It is correct that the edge connectivity of the individual graphs can be recovered from the mixed graph if the edges are unweighted, but how does it mean that the mixed graph  will not collide with some other existing graph or some other mixed graph. In the words of the authors "By this lemma, we see that in ifMixup, the two source graphs can be uniquely recovered from the mixed graph, without the knowledge of the mixing coefficient. Thus it is impossible for the graph resulting from mixing to coincide with any other graph in the training set or with a mixed graph from any other graph pairs" This is the main claim of the paper but there is no attempt to explain this."

Unless, I am missing something very trivial, the above claim is not straightforward to deduce from the fact that the edge connectivity of the individual graphs can be recovered from the mixed graph. Moreover, the edge connectivity can not be recovered from the mixed graph if the edges are weighted. Similarly the node features of the individual graphs can not be recovered from the mixed graph. If the authors can address this in the rebuttal, I am willing to increase the score.

The results are marginally better than the baseline that does the mixing in the representation space, and other baselines such as DropNode and DropEdge.

summary_of_the_review: The paper proposes a mixing strategy for the graph structured datasets, but the main claim of the paper that the method is "Intrusion Free" is not correct in my opinion.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This manuscript develops a mixup strategy for graphs. Specifically, as claimed by the authors, the proposed method is manifold intrusion-free. This is achieved by mixing two input graph pairs (some dummy nodes are needed, see Figure2) based on the standard mixup formulation. 
main_review: Strengths 
- the proposed mixup strategy is simple
- motivation for alleviating the manifold intrusion issue is clear  
- I am satisfied with the parts on page 8 (the last sentence before section 4.2.3) and Figure 5, as the over-smoothing problem has been well-discussed. They demonstrate the proposed mixup method can work better when the over-smoothing issue is serious.  
- eight graph classification benchmark datasets are used for evaluation. 

Weaknesses
- in section 3.3, the authors proved the invertibility and concluded that the proposed method is manifold intrusion-free. 
> 1) The proof of invertibility assumes the graph edge’s weight must be 0 or 1. Can the proposed method be used for the graph with real-value edges [0,1]? 
> 2) When using a graph with real-value edge weights, does the proposed method still satisfy the invertibility?  
> 3)The proof also requires the lambda not to be 0.5. But in standard mixup, the mixed sample can be generated in the case of lambda being 0.5. Thus, the assumption in this proof may not be correct. 
> 4)The most important question in this part is how the invertibility can induce “manifold intrusion free”? The connection between them is unclear. Assume your mixed sample can recover two original interpolation graphs, how to ensure that there is no conflict between the mixed sample’s representation and other training samples’ ones. Please explain this connection.
- As you used 5- and 8-layer GNNs in experiments, why not consider shallower GNNs? As seen in Figure 5, baselines show better performance when using a shallower structure. 
- it is unclear what do you want to prove in section 4.3.1 as there are no connections to the proposed method. 
- there are several existing related papers that all use mixup for graph node-classification tasks. As your proposed method can be used for mixing two graphs, it can also mix one graph with itself. Besides, as in your title, it should be a general mixup method for graphs, right? For these reasons, it will be good to also do the evaluation on node-classification tasks. 
Then SOTA graph mixup method should be [1]. I would like to see a comparison between the proposed method and baseline [1]. ([2] should be a weak baseline as it does not work significantly better than the basic baseline GNN, see Table3.)  
[1] 2021AAAI GraphMix: Improved Training of GNNs for Semi-Supervised Learning
[2]2021 WWW MixupGrpah: Mixup for node and graph classification
summary_of_the_review: Overall, the proposed method is simple. Its main limitation is their theory on invertibility and their experiments. In their experiments, as a general data augmentation method for graphs, node-classification tasks are also needed. The baseline of MixupGrpah is a bit weak. Stronger baseline - GraphMix is encouraged to be used for comparison.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work studied the research problem of data augmentation for supervised graph classification. The authors proposed ifMixup, which is a Mixup-based data augmentation method on graph data. The authors also showed that ifMixup is free of the known manifold intrusion problem of Mixup-based methods.
main_review: Pros:
1. The research problem of data augmentation for graph classification is interesting and woth studying. 
2. This paper is overall easy to follow.
3. The authors theoratically showed that the proposed ifMixup method is intrusion free.

Cons:
1. The performance improvements shown in Tables 2 and 3 are quite marginal.
2. The technical novelty is marginal considering the proposed ifMixup is basically a direct usage of Mixup on graphs.
3. From my point of view, one of the main challenges of applying Mixup on graphs is that the nodes in different graphs are not aligned. For example, the first feature of two different data objects indicates the same physical feature in regular data. However, the nodes in graph data are not nicely aligned like the features in regular data. Therefore, the way that the authors arbitrarily assign the node indeces (as stated in Sec3.2) is not very reasonable to me. I would appreciate if the authors can give more explaination and motivation on why they choose this random index and why this is a good solution.
4. Typos. e.g., A->B in Fig2; mixed usage of neighbor and neighbour.
summary_of_the_review: This work is very interesting, but I have slight concerns about part of the model design.
review_title: null

Meta-review: This paper proposes a “Mixup” type of data augmentation for graphs that accounts for the difficulty of mixing graphs of different number of nodes. The authors show that the mixed graphs are invertible functions of the original graphs.

Reviewer d3Ri liked the simplicity and effectiveness of the technique. They called it a “healthy and useful contribution for the field”. Reviewer n1Dk thought that the paper explored an important problem and thought the paper was clear, though some of the math could have been simplified. This reviewer was concerned that a central claim of the paper, that the method avoids “Manifold Intrusion” was unsubstantiated. Specifically that it could not be deduced from the fact that edge connectivity could be recovered from the mixed graphs. The reviewer claimed that node features of the individual graphs were unrecoverable. The authors responded in detail to the reviewer’s criticism, adding two new lemmas which purportedly guaranteed node feature vectors could be uniquely recovered. The authors admitted to some conversion between “Manifold intrusion” and invertibility and added a Theorem and its proof that invertibility guarantees no manifold intrusion. The authors also responded to reviewer n1Dk’s concern about the significance of the reported improvements. Reviewer n1Dk responded to the author rebuttal with concerns about the strong and unrealistic assumption of linear independence of the feature matrix. They had further concerns that for the case of weighted edges the “Intrusion-free” property could not be enforced. Discussion ensued, with the authors arguing that the independence assumption was not as strong as the reviewer claimed and that the “Intrusion-free” property was only every for graphs with binary edge weights. 

Reviewer 7hBS and q8bs were both on the fence. 7hBS also raised some concern with the case of non-binary weighted edges. They also raised the same issue with respect to the connection b/w invertibility and the “Intrusion-free” property, which the authors addressed. Reviewer q8bs also thought the problem was interesting, the paper was clear, yet like n1Dk thought the performance improvement was marginal and had concerns with technical novelty of the work.

This was a tough call, so I engaged the reviewers in further discussion. 7hBS agreed with n1Dk’s opinion that the central claim of the paper (the method being intrusion-free) was not presented with strong evidence. They also raised another concern, which was that the paper didn’t evaluate on node classification like most other graph mixup-style models. Q8bs agreed with n1Dk’s concerns and felt that post discussion the technical novelty of the work was limited. Without strong support from the reviewers, I think that this paper could use further development, either lightening the “intrusion-free” claim or presenting evidence for it in other settings.
Decision: Reject