Graph Mixup with Soft Alignments
Authors: Hongyi Ling
Zhimeng Jiang
Meng Liu
Shuiwang Ji
Na Zou
Venue: Submitted to ICLR 2023 (2023)

Abstract: We study graph data augmentation by mixup, which has been used successfully on images. A key operation of mixup is to compute a convex combination of a pair of inputs. This operation is straightforward for grid-like data, such as images, but challenging for graph data. The key difficulty lies in the fact that different graphs typically have different numbers of nodes, and thus there lacks a node-level correspondence between graphs. In this work, we propose a simple yet effective mixup method for graph classification by soft alignments. Specifically, given a pair of graphs, we explicitly obtain node-level correspondence via computing a soft assignment matrix to match the nodes between two graphs. Based on the soft assignments, we transform the adjacency and node feature matrices of one graph, so that the transformed graph is aligned with the other graph. In this way, any pair of graphs can be mixed directly to generate an augmented graph. We conduct systematic experiments to show that our method can improve the performance and generalization of graph neural networks (GNNs) on various graph classification tasks. In addition, we show that our method can increase the robustness of GNNs against noisy labels.

Under review as a conference paper at ICLR 2023
GRAPH MIXUP WITH SOFT ALIGNMENTS
Anonymous authors
Paper under double-blind review
ABSTRACT
We study graph data augmentation by mixup, which has been used successfully on images. A key operation of mixup is to compute a convex combination of a pair of inputs. This operation is straightforward for grid-like data, such as images, but challenging for graph data. The key difficulty lies in the fact that different graphs typically have different numbers of nodes, and thus there lacks a node-level correspondence between graphs. In this work, we propose a simple yet effective mixup method for graph classification by soft alignments. Specifically, given a pair of graphs, we explicitly obtain node-level correspondence via computing a soft assignment matrix to match the nodes between two graphs. Based on the soft assignments, transform the adjacency and node feature matrices of one graph, so that the transformed graph is aligned with the other graph. In this way, any pair of graphs can be mixed directly to generate augmented graph. We conduct systematic experiments to show that our method can improve the performance and generalization of graph neural networks (GNNs) on various graph classification tasks. In addition, we show that our method can increase the robustness of GNNs against noisy labels.
INTRODUCTION
Data augmentations aim at generating new training samples by applying certain transformations on the original samples. For example, applying rotations and flipping on images generates new images with the same labels. Many empirical results have shown that data augmentations can help improve the invariance and thus the generalization abilities of deep learning models. While data augmentations are relatively straightforward for grid-like data, such as images, they are particularly challenging for graph data. key difficulty lies in the lack of simple graph operations that preserve the original labels, such as rotations on images. Most existing graph augmentation methods, such as DropEdge (Rong et al. 2019), DropNode (Feng et al. 2020) and Subgraph YYou et al. 2020). assume labels are the same after simple operations, such as drop random node or edge, on training graphs. On one hand, such simple operations may not be able to generate sufficiently diverse new samples. On the other hand, although the operations are simple, they not guaranteed to preserve the original labels.
Recently, mixup (Zhang et al. 2017) has been shown to be an effective method for image data augmentation. In particular, mixup generates new samples and corresponding labels by performing convex combinations of a pair of original samples and labels. A key challenge of applying mixup on graphs lies in the fact that different graphs typically have different numbers of nodes. Even for graphs with the same number of nodes, there lacks node-level correspondence that is required to perform mixup. Several existing graph mixup methods (Han et al.) 2022, Park et al. 2022 Yoo al.) 2022) Guo & Mao 202T) use various tricks to sidestep this problem. For example, itMixup (Guo & Mao (021)) uses random node order to align graphs and then interpolate node feature matrices and adjacency matrices. |Han et al. (2022) proposes to learn Graphon for each class and performs mixup in Graphon space. Graph Transplant (Park et al. (022) and SubMix (Yoo et al.) 2022) connect subgraphs from different input graphs to generate new graphs. However, none of these methods explicitly models the node-level correspondence among different graphs and perform mixup as in the case of images. A natural question is raised: Can we conduct image-like mixup for graphs with node-level correspondence to preserve critical information?
In this work, we provide an affirmative answer to this question and propose a simple yet effective graph mixup approach via soft alignments. A key design principle of our method is to explicitly

---

Under review as a conference paper at ICLR 2023
and automatically model the node-level correspondence (i.e., soft alignment matrix) between two graphs when performing mixup, thereby avoiding random matching noise and preserving critical graph components in the augmented data. Given pair of graphs, we first obtain node-level corre- spondence by computing a soft assignment matrix that measures the similarity of nodes across two graphs based node features and graph topology. Then this soft alignment matrix guides the graph transformation, including adjacency matrix and node feature matrix transformation, to generate the aligned graph with the same number of nodes and node order as the other graph. In this way, we can interpolate the adjacency matrices and node feature matrices of any graph pairs to generate synthetic graphs for training. We conduct comprehensive experiments to evaluate our method. Results show that our method can improve the performance and generalization of GNNs on various graph classi- fication tasks. In addition, results show that our method increases the robustness of GNNs against noisy labels.
2 PRELIMINARIES
2.1 GRAPH CLASSIFICATION WITH GRAPH NEURAL NETWORKS
In this work, we study the problem of graph classification. Let 9 = -A, represent a graph with n nodes, Here, A E {0, _ is the adjacency matrix, and A.,; 1 if and only if there exists an edge between nodes i and j. X [æ)..... =,.J"' Rnxd is the node feature matrix, where each row 2; E Rd represents the d-dimensional feature of node i. Given a set of labeled graphs, graph classification tasks aim to learn model that predicts the class label y of each graph G. Recently, GNNs have shown remarkable performance in various graph classification problems. GNNs usually use a message passing scheme to learn node representations in graphs. Let H (1) [h] (.... 1T Raxdi denote the node representations at the I-th layer of a message passing GNN model, where each row h E IRdt is the dy-dimensional representation of node i. Formally, one message passing layer be described as
H ()) UPDATE( (t-1),, US- A)),
(I)
where MSG(-) is message propagation function that aggregates the messages from neighbors of each node, and UPDATE(.) is a function that updates (1-1)) to H using the aggregated mes- sages. The node representations (9) are initialized as X. After L layers of such message passing, the graph representation hg is obtained by applying a global pooling function READOUT over node representations as
hg (EADOUT(H())
Given the graph representation hg, a multi-layer perceptron (MLP) model computes the probability that graph G belongs to each class.
Despite the success of GNNs, a primary challenge in graph classification tasks is the lack of labeled data due to expensive annotations. In this paper, we focus on designing pairwise graph data augmentation method generate more training data, thereby improving the performance of GNNs.
2.2 MIXUP
Mixup (Zhang et al.] 2017) is data augmentation method for regular, grid-like, and Euclidean data such as images and tabular data. The idea of mixup is to linearly interpolate random pairs of data samples and their corresponding labels. Given random pair of samples æ; and æ, and their corresponding one-hot class labels y: and yj. Mixup constructs training data as
t Aæ; + (1 A)ae
ÿ Xy: + (1 \)yı,
(3)
where À ~ Beta(a, a: is a random variable drawn from the Beta distribution parameterized with a.
Mixup and its variants (Yang et al.) 2020: Yun et al. 2019 Berthelot al. 2019) have shown great success in improving the generalization and robustness of deep neural networks in image recognition and natural language processing. However, mixing graphs is a challenging problem due to the irregular and non- non-Eunhe Euclidean structure of graph data. Specifically, the number of nodes varies in different graphs, making it infeasible to apply the mixing rule in Eq. (3) directly. Even if two
2

---

Under review as a conference paper at ICLR 2023
graphs have the same number of nodes, graphs have inherent node order. If we don't consider the node-level correspondence between graphs and use an arbitrary node order to mix graphs, the generated graphs are noisy.
3 METHODOLOGY
In this work, we propose S-Mixup, a novel and effective mixup method for graph classification, which addresses the challenges of mixing graph data. We compute soft assignment matrix to match the nodes between a pair of graphs. The assignment matrix guides the graph transformation well align graph pairs based on node attributes and graph topology, such that the augmented new graph can preserve the critical information and avoid random matching noise.
3.1 MIXUP WITH AN ASSIGNMENT MATRIX
Assuming that already have the desired soft assignment matrix, first describe how mix graphs based on a soft assignment matrix. Given a pair of graphs G1 = (A1, X1) and G2 = (A2, X2), we use M E g"1x" to denote the soft assignment matrix, where n1 and n2 are the number of nodes in 91 and G2, respectively. Each row of M corresponds to node in G1 and each column of M corresponds to a node in G2. The soft assignment matrix M represents the node-level correspondence between Gi and G2. In other words, the entry M,, denotes the likeness that the node j in G2 is matched to the node in G1.
Given the assignment matrix M, we transform G2 (A2, X2) to G2 (A2, X²) as
A² = MA,M"
MX
(4)
After transformation, 9/2 is aligned well with 91 via node-level one-to-one mapping. this way, we can generate a new graph g = (A', X') via mixing up graphs 91 and 93z To be specific, g' is generated via linear interpolation on both node features and topological structures. Formally, this process can be described as
= AX1 + (1 -1- A)MX,.
A' = AA1 + (1--1)(1AA 2)MA,
(5)
y' = Ay + (1 (1-4)y2,
where yı and y/2 are the one-hot class labels of graph Gi and G2. respectively. The mixup ratio max(X', X), where X E [0, is sampled from a Beta(a, a) distribution with hyper- parameter Note that the generated new graph g' (A', X') is a fully connected edge-weighted graph. In other words, A' E [0, 1| x a real matrix, where each entry AL,, denotes the weight of the edge between nodes and j in g'. Together with the label y', the generated new graph g' used as the augmented training data.
3.2 COMPUTING THE ASSIGNMENT MATRIX
Since we need to perform soft alignments for all input graph pairs, an accurate assignment matrix with efficient computation is in need. Thereby, we propose to compute the node-level assignment matrix based on a graph matching network (Li et al. 2019), which used to compare graph-level similarities. Specifically, pair of graphs 91 and Go is taken input to extract a pair of node representations H2 and H2 by message passing within and between graphs. Formally, the message passing process of node representations H in G1 at 1-th layer can be formulated as H(C) UPDATE(H (1-1), MSG, (H (H") A1), ( H
where MSG (-) is a message propagation function of vanilla GNNs in Eq.
[=] ... . "pT computes gross-graph messages from G2 to G1 where each row H4; denotes the message from G2 to the node i in G,. Let h and h denote the representation of node in G1 and node in G2 at layer - 1, respectively. The cross-graph message n4! (((-1) is computed by an attention-base based module
(1-1) (H .H.!"
(1-1)
(1-1) exp(sim (1-1) .nn5"")) Wij
no
P (1-1)
Σ
W js (h2 h
(1-1) (1-1) ((-1)), (7)
Σ k= exp(sim(h (1 (1-1) hh h22
(1-1)))²
j=1
3

---

Under review as a conference paper at ICLR 2023
Input Graph
Input Graph G
Soft Alignment
Mixed Graph g
X
X;
Mixup
Input Graph 22
Assignment Matrix
Graph 922
AC
M
An overview S-Mixup. Given pair of graphs 91 and G2, the color of each node rep- resents the node-level correspondence between two graphs. The assignment matrix M is obtained by soft alignment. Based on the assignment matrix, the graph Ø2 transformed from G2 to be aligned with G1. Finally, we obtain the mixed graph G' by mixing 91 and G2 The darkness level of each edge represents its weight.
Figure 1:
where sim(.) denotes the similarity between two node representations, such as Euclidean distance cosine similarity. The final node representations Hi H(")) and H2 H obtained after applying L layers of such message passing operations. Given the node representations H1 and H2, we take the likelihood of soft alignment to be proportional the similarity between node representations. Formally, the soft assignment matrix M is computed as
M = softmax(simi) H1, H2)),
(
where softmax function a column-wise operation, and sim(-) computes similarity score for node pairs between 9i and G2.
The network trained by a triplet loss following Li et al. (2019). Specifically, we treat graphs with the same class label positive pairs and graphs with different class labels negative pairs. Intuitively, the learned representations of graphs from the same class should be more similar than those from different classes. To be more specific, at each training step, first sample tuple of graphs (G,, G2 G3) from the training dataset. G1 and G2 are sampled from the same class, while Gu sampled from another class. We the graph matching network to extract node representations (H1, H2) from the graph pair (9, G2) as in Eq. (6). Afterwards, the graph representations hG, and hGg are separately computed from H1 and H₂ in Eq. (2). Similarly, compute the graph representations (h', log,) of graph pair (G1, Gz). The graph matching network is optimized by minimizing the triplet loss
Lupple EgG, C2G.,G2.St max sim(h', heg.) sim (e..) + 7),
(9)
where sim(-) computes similarity score between two graph representations. Minimizing such triplet loss encourages the similarity between G1 and G3 to be smaller than the similarity between In and Go by at least margin 7. The graph matching network is first trained on the training data. During the process of mixing graphs, the trained graph matching network is used to compute soft assignment matrices. See Figure [1] for an overview of our proposed S-Mixup method. The implementation details are summarized in Appendix B There are other well-studied graph alignment methods (Heimann et al. 20188 Zhang & Tong 2016 Xu et al.) 2019 Gold Rangarajan 1996) to align the nodes across two graphs. Nevertheless. not all of them appropriate for framework due to computational complexity. See more discussion about graph alignment methods in Appendix D.I
3.3 COMPLEXITY ANALYSIS
Given a pair graphs &. with n, nodes and G2 with n2 nodes, S-Mixup computes the soft as- signment matrix M E 1Ra,x thus having space complexity of ((m)))) Besides, during the
4

---

Under review as a conference paper at ICLR 2023
Table I: Comparison between ours and other graph mixup methods
Methods
Instance-lovel
Preserving motif
Mixing Input-lovel feature space
Perserving graph size
G-mixup (Han et al 2022
Graph Transplant (Park el al
2022
SubMix el al
ilMixup (Guo & Nai 2021
Manifold Mixup Wang a.
202th
S-Mixup
computation of the soft assignment matrix M, the graph matching network uses a cross graph mes- sage passing scheme, which needs to compute attention weights (see Equation 7 for every pair of nodes across two graphs. Thus, S-Mixup has computational cost of (())2)) This time cost is affordable for small graphs but may lead to large computational and memory costs on large graphs. The better performance of S-Mixup comes from the higher computational cost.
4 RELATED WORK
Most commonly used graph data augmentation methods (Velickovic et al., 2019: Rong et al. 2019
Feng et al. 2020 You et al. 2020 Zhu et al. 2020) are based on uniformly random modifications of graph elements, such as dropping edges, dropping nodes, or sampling subgraphs.
addition to ran- dom modifications, recent studies (You et al., 2021 [Sun et al.] 2021] Luo et al. (022) use learnable
neural network model to automate the selection of augmentation. Another line of research (Suresh
et al. 2021; Zhao al. 202T Chen et al. 2020; Jin et al., 2020) for improving random modifica- tions is to enhance task-relevant information in augmented graphs with learnable data augmentation methods. However, the above methods are based on a single graph when performing augmentation, so they don't I exchange information between different instances. To address the limitation, a few studies propose interpolation-base based Mixup methods for graph augmentation. Waan et al. (202Tb) follows manifold Mixup (Verma et al., 2019) to interpolate the latent representations of pairs of graphs. Since the graph representations are obtained the last layer of GNN models, this solution may be not optimal. In contrast to the previous method, ifMixup (Guo & Mao 2021) interpolates the input graph data instead of latent space. It uses an arbitrary node order to align two graphs and linearly interpolates adjacency matrices and feature matrices generate new graph data. ifMixup doesn't consider the node-level correspondence between graphs, leading to generating noisy graph data as discussed in Section 5.1 Moreover, the size of the generated graphs equals the larger one of the input pair, resulting in a distribution shift in graph sizes. Unlike ifMixup, Graph Transplant (Park al. 2022) proposes to generate new graph data by connecting subgraphs from different in- put graphs. Graph Transplant uses node saliency information to select meaningful subgraphs from input graphs and determine labels of generated graphs. Similarly, SubMix Yooo al. 2022) mixes random subgraphs of different input graphs. Nonetheless, random sampling doesn't 't preserve motifs in the graphs, thus generated graph data may be noisy. Both Graph Transplant (Park et al., (022)) and SubMix (Yoo et al. 2022) only consider graph topology, so the node features of generated graphs are kept the same. Instead of directly mixing instances, G-mixup (Han et al., (022) proposes a class- level graph mixup method that interpolates the graph generators of different classes. Specifically, it uses graphons to model graph topology structure and then generates synthetic graphs through sam- pling the mixed graphons of different classes. Note that G-mixup relies strong assumption that graphs from the same class can be generated by the same graph generator (i.e., graphon).
However, none of these methods explicitly consider the node-level correspondence between graphs, which is important to generate high-quality graphs as discussed in Scction [.I]] In contrast, our approach uses soft graph alignment to compute the node-level correspondence and mixes graphs based on the alignment, thereby avoiding the generation of noisy data. We compare our method with existing graph mixup methods in T
5 DISCUSSION
5.1 NODE-LEVEL CORRESPONDENCE MATTERS IN GRAPH MIXUP
We use the MOTIF (wu et al. 2022 dataset as an example to show the importance of node order. Each graph in the MOTIF dataset is composed of one base (tree, ladder, wheel) and one motif (cycle,
'MOTFF dataset is synthetic dataset that is proposed for the out-of-distribution problem. In this work, we avoid introducing the distribution shift when constructing the dataset.
5

---

Under review as a conference paper at ICLR 2023
5
3
5
2
3
2
4
8
10
11
8
9
12
9
12
9
12
8
10
10
11
12
10
(a) Original graph data.
(b) Random Mixup
(c) S-Mixup
An example from the MOTIF dataset showing that using random order to mix graphs creates noisy data. Red nodes represent the motif, while blue nodes represent the base. The color of the edge indicates its weight. In (a), show pair of graphs sampled from the Motif dataset. In both graphs, red nodes represent cycle motif. In (b), we show the mixed graph using a random node order. In this graph, red nodes no longer form cycle motif. In (c), we show the mixed graph by our method. In this graph, red nodes still form a cycle motif.
Figure 2:
house, cranc). The task of the MOTIF dataset is to classify graphs by the motif contained in the graph. In Figure we visualize case of mixing two graphs in the same class. We randomly align two graphs and linearly interpolate their node feature matrices and adjacency matrices to generate new graph. As shown in Figure 2b] the generated graph doesn't 'tt preserve the motif in the input graphs. In other words, red nodes that form a cycle motif in the original graphs no longer form a cycle motif in the generated graph. Training with such noisy data greatly decreases the accuracy of a GIN (Xu et al. 2018) model from 91.47% to 52.88%. The significant performance drop clearly demonstrates the importance of node-level correspondence between graphs when mixing graphs.
5.2 GRAPH TRANSFORMATION ANALYSIS
There is limitation of our method caused by transforming graphs have the same number of nodes and the same node order. We first introduce graph edit distance (GED) to characterize the similarity of two graphs. Given a pair of graphs (91, G2), the graph edit distance GED G2) is defined as the minimum cost of an edit path between two graphs. An edit path between graphs G1 and G2 is sequence of edit operations that transforms G1 to G2. For graph edit operations, we consider six edit operations, including node insertion, node deletion, node substitution, edge insertion, edge deletion, and edge substitution. The cost of all graph edit operations are given as follows:
The cost of node insertion and node deletion is defined as the square of the l2 norm of node feature of the inserted node and deleted node, respectively.
Node substitution is to change the feature of node and its cost is defined as ||æ w' 12 where xe and x' are the node features before and after node substitution, respectively.
The cost of edge insertion and edge deletion is the weight of the inserted edge and deleted edge, respectively.
Edge substitution is to change the weight of an edge and its cost is defined as le - e'1, where and e' are the weights of the edge before and after edge substitution, respectively.
The cost of an edit path is defined as the sum of the costs of its operations.
Definition 1 (Graph Edit Distance (GED)). For graph pair (91.92). the graph edit dis- tance GED(GI, is defined the minimum cost of edit puth between two graphs, i.e GED(G G2) minl(op..... (P 92) E c(op:), where (P G2) denotes the set of edit paths from G1 G2. c(op) denotes the cost edit operation op.
GED C.)
Subsequently, we define normalized GED as e
GED & GED G2) E [0, 1] to characterize
the similarity between the generated graph G' and the original pair (91, G2). Note that, for a perfect mixed result, the normalized GED should be equal to the mixup ratio X. To study the difference between normalized GED and mixup ratio, we propose the following theorem.

---

Under review as a conference paper at ICLR 2023
Table 2: Comparisons between our method and baselines on six datasets from the TUDatasets bench- mark with the GIN and GCN model. The average testing accuracy of 10 runs is reported. The best results are shown in bold.
Dalaset
IMDB-B
PROTEINS
REDDIT-B
IMDB
REDDITMS
#graphs
1000
1113
4110
2000
1500
4999
#classes
2
2
2
3
Ravg nodes
19.77
39.06
29.87
429.63
13.00
508.52
#avg edges
96.53
72.82
497.75
65.94
594.87
Vanilla
72.80
4.08
71,43
1: 2.60
72.38 1: 1.45
84.85
1: 2.42
49.47
1: 2.60
49.99
1: 1.37
DropEdge
73.20 1: 5.62
71.61
1. 4.28
68.32
1: 1.60
85.15
1: 2.81
49.00
1: 2.94
51.19
1: 1.74
DropNode
73.80
5.71
72.69
+ 3,55
70.73
+ 2.02
83.65
3.63
50.00
+ 4.85
47.71
+ 1.75
Subgraph
70.90
5.07
67.93
3.24
65.05
+ 4.36
68.41 2.57
49,80 3.43
47.31 = 5.23
GCN
M. Mixui
72.00 5.66
71.16 +: 2.87
71.58 1: 1.79
J: 2.47 87.05
49.73
1: 2.67
51.49 1 2.00
SubMix
72.30 4.75
72.42 +: 2.43
71.65 + 1.58
85.15 2.37
49.73
2.88
52.87 + 2.19
G-Mixup
5.60
70.18
70.75
2.30 86.85
3.67
51.77 1:
S-Mixup
74,40
5.44
73.05
2.81
75.47
+ 1.49
89.30 2.69
50,73 + 3,66
53.29 + 1.97
Vanilla
71.30 1 4.36
68.28
1 2.47
79.08 1: 2.12
22447
48.80 1 2.54
$3.17 1 2.26
DropEdge
70.50
3.80
68.01 1. 3,22
76.47
1: 2.34
87.45 3.91
48.73 1. 4.08
54,11 1 1.94
DropNode
6.97
74.60
88.60
2.59
+
Subgraph
70.40 = 4.98
66,67 = 3,10
60. + 2.33
76.80
43.74
+4.44+00 5.74
50.09 = 4.94
GIN
Mixup
72.00 1: 5.14
68.65 1: 3.76
79.85 1: 1.88
87.70 2:550
5.32 48.67
$2.85 +: 1.03
SubMix
71.70 6.20
69.54
79.78 +: 1.09
1.93
4.01
54,27 + 54.33 1 1.99
G Mixix
72.40
5.64
64.69 1. 3,60
78.20 1. 1.58
90.20
1. 2.84
49.93
2.82
S-Mixup
73,40 + 6.26
69.37 + 2.86
80.02
+ 2.45
90.55 + 2.11
S0.13
+ 4.34
55.19 + 1.99
Theorem 1. Given a pair of input graphs 91 and 92. the mixup ratio is X and the mixed graph is G'. Let G22 be the graph transformed based on soft alignments discussed in Section 3.1 The difference between normalized GED and mixup ratio is upper bounded by
(1- () 922
- GED(G, GED(G2.
(10)
Detailed proof of this theorem is given in Appendix A Note that the difference between normalized GED e and mixup ratio X equals to zero when input graphs are already aligned (i.e., 92 = Gy)) Theorem D indicates that such difference is caused by transforming G2 to G/2- Furthermore, the difference is small when is close to 1. Thereby, in this work, we make the range of À to be [0.5, 1] reduce the difference via taking the maximum value of X' and 1 - -. A promising solution is to use an adaptive À range for different graph pairs, and we leave for future work. See a case study in Appendix
EXPERIMENTS
In this section, we evaluate the effectiveness of our method on six real-world datasets from the TU- Datasets benchmark MMrris et al. 2020), including one bioinformatics dataset PROTEINS, one molecule dataset NCII, and four social network datasets BINARY, and REDDIT-MULTI-S5 method substantially improves the performance of different GNN backbones as well as generaliza- tion in Section 6.1 Further, we show our method improves the robustness of GNNs against label corruption in Section 6.22 addition, we conduct extensive ablation studies to evaluate the effec- tiveness of our design in Section 6.3]and and perform a case study in F
IMDB-MULTI, REDDIT- We first show that in various graph classification tasks, our
Baselines. We compare our methods with the following baseline methods, including (1) DropEdge RRong et al., 2019), which uniformly removes a certain ratio of edges from the input graphs; (2) DropNode (Feng et al. 2020 You et al. 2020), which uniformly drops certain portion nodes from the input graphs; (3) Subgraph Yoou et al. 2020). which extract subgraphs from the input graphs via a random walk sampler; (4) M-Mixup Verma et al.
2019 Wang et al. 2021b). which linearly interpolates the graph-level representations; (5) SubMix Yoo et al. 2022 which mixes random subgraphs of input graph pairs; (6) G-Mixup (Han et al.
2022). which is a class-level graph mixup method by interpolating graphons of different classes. For fair comparison, we use the same architecture of GNNs (c.g., number of layers) and the same training hyperparameters (e.g., learning rate) for all methods. The optimal hyperparameters of all methods are obtained by grid search.
'https//cchsmmrrs.g githhhhiiodaassss///osssdaaaa A Athhough Wang et al. (2021b) proposes mixup methods for both graph and node classification tasks, we only consider the for graph classification tasks in this paper.

---

Under review as a conference paper at ICLR 2023
IMDB-BINARY
5.700
0.70
emboos mmiup eabmb
OWALDD miidca
2,550
2.00
2,815
2,800
Text
2.84
0.60
1.02
2350
2335
2,500
50
150
200
300
0.54
200
350
502
120
100
252
Epoch Number
Epoch Number
Epoch Number
The Learning curves of GCN model on IMDB-BINARY, NCI1, and IMDB-MULTI datasets. The curves are depicted on the averaged test loss over 10 runs.
Figure
Table 3: Robustness to label corruption with different ratios.
Dataset
Methods
20%
40%
60%
Vanilla
69.50 7.83
62.70
7.93
45.80 + 6.63
M-mixup
70.60 + 3.69
64.90 + 6.20
47.60 + 6.79
IMDB-B
SubMix
71.00 5.23
62.80 5.74
48.40 + 6.83
G-mixup
69.90 + 5.01
63.20 + 6.01
48.70 + 5.28
S-Mixup
70.20 5.69
65.10 5.58
48.90 + 4.61
Vanilla
48.00 3.37
44.87
2.91
36.20 + 3.78
M-mixup
48.40 + 2.83
44.07 + 2.18
38.60 3.97
SubMix
47.80
5.16
44.20 6.75
36.80 5.44
IMDB-M
G-mixup
48.53
3,08
44.67
+ 2.42
39.27 5.12
S-Mixup
49.40 3.06
46.27 + 3.86
39.27 +
Setup. We first train the graph matching network until converges. Then, we evaluate the per- formance of our method and other baselines by the testing accuracies of a classification model over six datasets. For the classification model, we use two GNN models; namely, GCN (Kipt & Welling 2016) and GIN (Xu et al. 2018). We split the dataset into train/validationntestt data by 50%/10%/100 The averaged testing accuracy over runs is reported for comparison. See more experimental details in Appendix C
6.1 S-MIXUP IMPROVES THE PERFORMANCE AND GENERALIZATION
Table summarizes the performance of our proposed S-Mixup compared baselines on all six datasets. From the results, our method can improve the performance of different GNN models on various datasets. For example, compared to the GCN model without data augmentation, our method achieves improvement of 4.45%. 3.3% and 3.09% the REDDIT-BINARY, REDDIT- MULTI-5K, and NCII datasets, respectively. is worth noting that our method achieves the best performance among the graph mixup methods. Since M- M-Mixup only interpolates the graph rep- resentations at the last layer of GNN models, its improvement is limited. Meanwhile, G-Mixup generates the same node features for all augmented graphs, thus leading performance degradation on PROTEINS and NCII datasets which have node features.
We further learning curves to study the effects of mixup methods GNN models. Figure shows the test loss at each training epoch of our method compared to other graph mixup methods on IMDB-BINARY, NCII, and IMDB-MULTI datasets. From the results, we have the following observations:
For the IMDB-BINARY and IMDB-MULE datasets, the test loss of GCNs without data augmen- tation increases after certain training epochs. While all graph mixup methods reduce the increase in test loss at later iterations, our method has the best results in helping the GCN model to con- verge to a lower test loss. This demonstrates that our method can effectively regularize GNN models prevent over-fitting.
For the NCII dataset, our method achieves an obvious improvement over the other methods. Such observation indicates that our method generates better synthetic graph data than other methods, thereby obtaining much lower test loss.
8

---

Under review as a conference paper at ICLR 2023
Table 4: Results of the ablation study on mixup strategies and À range.
IMDB-B
PROTEINS
REDDIT-B
IMDB-M
Vanilla
72.80 - 4.08
71.43 + 2.60
84.85 = 2.42
49.47 2 2.60
S-Mixup w/o different classes S-Mixup with À [0, 1]
73.07 + 5.78
72.23 3.56
87.60 + 1.74
50.27 2.86
73.00 5.87
72.15 3.86
88.70 2.18
49.07 + 4.06
S-Mixup
74.40 = 5.44
73.05 + 2.81
89.30 = 2.69
50.73 + 3.66
Table 5: Results of the ablation study on normalization.
IMDB-B
PROTEINS
NCII
REDDIT-B
IMDB-M
REDDIT-MS
Sinkhorn
73.20 6.13
72,80 1. 3.72
74.89 1 1.34
90.50 1: 1.80
50.40 1: 2.83
53.13 1 2.33
GCN
Softmax
74,40 = 5.44
73.05 + 2.81
75.47 + 1.49
89.30 + 2.69
50.73 = 3,66
53.29 = 1,97
Sinkhorn
73.10
6.62
69.09 +: 2.84
79.95
+ 2.15
91.25
1.70
50.23
=: 4.70
55,09
1.54
GIN
Softmax
73.40
6.26
69.37 2.86
80.02 + 2.45
90.55
50.13 4.34
55.19 1,99
6.2 S-MIXUP IMPROVES THE ROBUSTNESS
In this subsection, we evaluate the robustness our method and other graph mixup methods against noisy labels. We generate the noisy training data by randomly corrupting the labels of the IMDB- BINARY and IMDB-MULTI datasets. Specifically, we create three training datasets, where 20%, 40%, and 60% of the labels are flipped to a different class, respectively. All the test labels are kept the same for evaluation. We adopt GCN as the classification backbone this experiment. Results in Table 3 show that method can achieve the best performance in most cases, indicating that our method can improve the robustness of GNNs against corrupted labels.
6.3 ANALYSIS
Mixup strategy. In this subsection, we investigate the performance of different mixup strategies. Specifically, we use "S-Mixup w/o different classes" to denote design choice that only mixes graphs from the same class, In this experiment, we adopt GCN as the classification model on IMDB-BINARY, PROTEINS, REDDIT-BINARY, and IMDB-MULT datasets. Results in Table 4 demonstrate that "S-Mixup w/o different classes" creates more training graph data, leading to the improvement in the performance of GNN models. In addition, mixing graphs from different classes can further improve the performance of GNN models. Such observation shows that mixing all the classes is better design choice for the mixup strategies.
Mixup ratio X. As we mentioned in Section 5.2, the À range has an effect on the quality of the generated graphs, so we investigate the performance of different À ranges in this subsection. Specif- ically, we compare the performance of À E [o, 1] and the default setting (i.e., X E [0.5, 1l). In this experiment, we adopt GCN the classification model IMDB-BINARY, PROTEINS, REDDIT- BINARY, and AMDB-MULLY datasets. Table shows that our method achieves better performance with larger À value, which is consistent with our analysis in Section 5.2
Softmax normalization. While most graph matching algorithms use sinkhorn normalization to fulfills the requirements of doubly-stochastic alignment, we relax this constraint by only apply- ing column-wise softmax normalization on the soft assignment matrix M in Equation ( In this subsection, we investigate the effect of different normalization functions on our framework. Specif- ically, we replace softmax normalization in Equation S with sinkhorn normalization. Results in Ssho that sinkhorn normalization has similar performance to softmax normalization. Since sinkhorn normalization has higher computational cost than softmax normalization, we choose to use softmax normalization in our framework for efficiency.
7 CONCLUSION
In this work, we propose S-Mixup, a novel mixup method for graph classification by soft graph alignments. S-Mixup computes soft assignment matrix model the node-level correspondence between graphs. Based on the soft assignment matrix, we transform one graph to align with the other graph and then interpolate adjacency matrices and node feature matrices generate augmented training graph data. Experimental results demonstrate that our method can improve the performance and generalization of GNNs, as well as the robustness of GNNs against noisy labels. In the future, we would like to apply S-Mixup to other tasks on graphs, such as the node classification problem.

---

Under review as a conference paper at ICLR 2023
REFERENCES
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. Mixmatch: holistic approach to semi-supervised learning. Advances in neural informa- fion processing systems, 32, 2019.
Sebastien Bougleux, Luc Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Gaüzère, and Mario Vento. Graph edit distance as a quadratic assignment problem. Pattern Recognition Letters, 87: 38 48-46,22 2017.
Horst Bunke. On relation between graph edit distance and maximum common subgraph. Pattern recognition letters, 1888):689-694 1997.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3438-3445, 2020.
Minsu Cho, Jungmin Lee, and Kyoung Mu Lee. Reweighted random walks for graph matching. In European conference on Computer vision, pp. 492-505. Springer, 2010.
Tansel Dokeroglu and Ahmet Cosar. A novel multistart hyper-heurisee algorithm the grid for the quadratic assignment problem. Engineering Applications of Artificial Intelligence, 52:10-25, 2016.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning graphs. Advances in neural information processing systems, 33:22092-22103, 2020.
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. arXiv preprint arXiv:2001.0966 2020.
Steven Gold and Anand Rangarajan. A graduated assigmment algorithm for graph matching, 1EEE Transactions on pattern analysis and machine intelligence, 18(4):377-388, 1996.
Hongyu Guo and Yongyi Mao. Intrusion-free graph mixup. arXiv preprint arXiv: 10.09344, 2021.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. arXiv preprint arXiv:220..07/73 2022.
Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. Regal: Representation learning- based graph alignment. In Proceedings of the 27th ACM international conference on information and knowledge management, pp. 117-126, 2018.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery data mining, pp. 66-74, 2020.
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. arXiv preprint arXiv: ww..6..99999900 2016.
Marius Leordeanu and Martial Hebert. A spectral technique for correspondence problems using pairwise constraints. 2005.
Marius Leordeanu, Martial Hebert, and Rahul Sukthankar. An integer projected fixed point method for graph matching and map inference. Advances in neural information processing systems, 22, 2009.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity of graph structured objects. In International conference on machine learning, pp. 3835-3845. PML.R, 2019.
10

---

Under review as a conference paper at ICLR 2023
Chang Liu, Shaofeng Zhang, Xiaokang Yang, and Junchi Yan. Self-supervised learning of visual graph matching. In European Conference on Computer Vision, pp. 370-388. Springer, 2022.
Youzhi Luo, Michael McThhro, Wing Yee Au, Tao Komikado, Kanji Uchino, Koji Maruhash, and Shuiwang Ji. Automated data augmentations for graph classification. arXiv preprint 13224 2022.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprini arXiv:2007.08663 2020.
Michel Neuhaus and Horst Bunke. A quadratic programming approach the graph edit distance problem. International Workshop on Graph-Based Representations in Pattern Recognition, pp- 92-102. Springer, 2007.
Joonhyung Park, Hajin Shim, and Eunho Yang. Graph transplant: Node saliency-guided graph mixup with local structure preservation. In Proceedings of the First MiniCon Conference, 2022.
Yun Peng, Byron Choi, and Jianliang Xu. Graph edit distance learning via modeling optimum matchings with constraints. In Zhi-Hua Zhou (ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 1534-1540. International Joint Con- ferences on Artificial Intelligence Organization, 8 2021. doi: 20224966/iccaa.2222222.. URL https://dol org 24963/11cai. 2021/212
Main Track.
Kaspar Riesen and Horst Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision computing, 27(7):950-99) 9599, 2009.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv: 2019.
Alberto Sanfeliu and King-Sun Fu. distance measure between attributed relational graphs for pattern recognition. IEEE transactions on systems, man, and cybernetics, (3):353-362, 1983.
Junwei Sun, Bai Wang, and Bin Wu. Automated graph representation learning for node classifi- cation. In 2021 International Joint Conference on Neural Networks (LJCNN), pp. 1-7. IEEE, 2021.
Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to im- prove graph contrastive learning. Advances Neural Information Processing Systems, 34:15920- 15933, 2021.
Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez- Paz, and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states. In International Conference on Machine Learning, pp. 6438-6447. PMLR, 2019.
Vikas Verma, Thang Luong, Kenji Kawaguchi, Hieu Pham, and Quoc Le. Towards domain- agnostic contrastive learning. In International Conference on Machine Learning, pp. 10530- 10541. PMLR, 2021.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's s quadratic assignment problem with extension to hypergraph and multiple-graph match- ing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021a.
Tao Wang, Haibin Ling, Congyan Lang, and Songhe Feng. Graph matching with adaptive and branching path following. IEEE transactions on pattern analysis and machine intelligence, 40 (12):2853-286)) 2017.
Yiwei Wang, Wei Wang. Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 2021, pp. 3663-3674, 2021b.

---

Under review as a conference paper at ICLR 2023
Ying-Xin Xin Wu, Xiang Wang. An Zhang, Xiangnan He, and Tat seng Chua. Discovering invariant rationales for graph neural networks. ICLR, 2022.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov-wasserstei learning for graph matching and node embedding. In International conference on machine learning, pp. 6932-6941. PMLR, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.0082. 2018.
Yaoqing Yang, Rajiv Khanna, Yaodong Yu, Amir Gholami, Kurt Keutzer, Joseph E Gonzalez, Kan- nan Ramchandran, and Michael W Mahoney. Boundary thickness and robustness in learning models. Advances in Neural Information Processing Systems, 0226223-62344 2020.
Jaemin Yoo, Sooyeon Shim, and U Kang. Model-agnostic augmentation for accurate graph classifi- cation. In Proceedings of the ACM Web Conference 2022, pp. 1281-1291, 2022.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812-5823, 2020.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning auto- mated. In International Conference on Machine Learning, pp. 12121-12132. PMLR, 2021.
Sangdoo Yun, Dongyoon Han, Scong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In Proceed- ings of the IEEE/CVF international conference on computer vision, pp. 6023-6032, 2019.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXiv:1710.09412 2017.
Shaofeng Zhang, Meng Liu, Junchi Yan, Hengrui Zhang, Lingxiao Huang, Xiaokang Yang. and Pinyan Lu. M-mix: Generating hard negatives via multi-sample mixing for contrastive learning. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 2461-2470, 2022.
Si Zhang and Hanghang Tong. Final: Fast attributed network alignment. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1345- 1354, 2016.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data aug- mentation for graph neural networks. Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 35, pp. 11015-11023, 2021.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning, arXiv preprint 20ti::20000413311 2020.
12

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM
Proof. Since g' has the same number of nodes and the same node order as 91, we have
GED = =(44' - A1) + +|XX - -111
= (1 A) A/2 A1) + X2 Xill
(11)
= (1 A)GED(G1..3)
where ((A) calculates the sum of the absolute value of all elements in the matrix A. Similarly, we have
GED AGED(GG, ()
(12)
From the triangle inequality, we have
( GED (2) v GED(g', (3) + GED(92, g3
(13)
Then the difference between normalized GED and mixup ratio is
GED
A1
GED(G'.9) GED 92) À
(a)
GED GED (6
GED (1) GED + GED 92 - A
(0)
GED (3) + GED(O2, 9%)
(1 (1- 1--AGEEDGG..99 91) GED( 93) GED 922 XGED(G,.9) + GED 0%
(14)
(c)
(1- AJ-E)DDDG,, (3) + AGED(G 93) (ED(G2,
XGED(O, (3) + GED 92
GED 9%) + GED C2. 92
(1 A) (
GED 9b + GED 9
where inequality (a) holds due equation holds due to equation (13).
inequality (b) holds due to equation 12 and (c)
B IMPLEMENTATION DETAILS
In this section, provide the implementation details for our method. We first present the pseudo codes for training the graph matching network Algorithm I After training the graph matching network,
to perform Mixup graphs. The pseudo codes for mixing up graphs marized in Algorithm 2] The mixed graphs are used as the augmented training data. To reduce I/O cost, we follow Zhang et al. (2017) mix graphs from the same batch by random shuffling. For the mixup ratio, we select the hyperparameter a from 10. 0.2, 0.5, 1,2, 5, 10). For the sim function, consider two different metrics, including cosine similarity and Euclidean distance. The optimal hyperparameters are obtained by grid search.
sum-
Algorithm Training algorithm
Input: training set S, graph matching network GMNET while not converged do
Sample a tuple graphs (91, G2, Ga) from S, where G. and G2 are sampled from the same
class and G3 is sampled from another class.
Obtain a pair of graph representations (hg, hg,)) from the graph pair (G,, G2) using GMNET
Obtain pair of graph representations (hog hg,) from the graph pair (G,, Gs) using GMNET
Compute Luripeet as Eq. (9)
Update GMNET by applying stochastic gradient descent minimize Luiptet
end while
13

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Mixup algorithm
Input:
well-trained graph matching network GMNET, pair of graphs (91, 92) Generate a pair of node representations (H1, H2) from graph pair (91, 92) using GMNET
Compute the soft assignment matrix Eq. {
Generate the synthetic graph G' and corresponding label y'as as Eq.
return g" and y'
Datasets IMDB-B
Initial learning rate
# Training epochs
Batch size
0.001
300
256
PROTEINS
0.001
300
256
NCI1
0.01
500
256
REDDIT-B
0.01
500
16
IMDB-M
0.001
300
256
REDDIT-MS
0.01
500
16
Table 6: Hyperparameters for training classification model
C EXPERIMENTAL DETAILS
C.I EXPERIMENTAL SETTING
For fair comparison, we use the same architecture of GNN backbones and the same training hyper- parameters for all methods. For the classification model, we use two GNN models; namely, GCN and GIN. The details of GNNs are listed follows,
GCN( & Welling 2016). The number of GCN layers is four, and we use global mean pooling as the readout function. We set the hidden size as 32. The activation function ReLU.
Xu et al. 2018). We use a global mean pooling as the readout function. The number of GIN layers four, and all MLPs have layers. We the hidden size as 32. The activation function is ReLU.
We the Adam optimizer (Kingma & Ba 2015) train all models. See Table for the hyperpa- rameters of training the classification model. We split the dataset into train/validation/tes data by 80%/10% 10%. The best model is selected on the validation
For the graph matching network used in S-Mixup, we set the hidden size as 256 and the readout layer global sum pooling. For all six datasets, the graph matching network is trained for 500 epochs with learning rate of 0.001. For the number of layers and batch size, see Table
Datasets IMDB-B
# layers
Batch size
6
256
PROTEINS
5
256
NCII
5
256
REDDIT-B
8
IMDB-M
5
256
REDDIT-MS
8
Table 7: Hyperparameters for the graph matching network
D MORE DISCUSSIONS
D.1 GRAPH MATCHING METHODS
There are many well-studied graph match methods, which aim to find the node-level correspondence between the graph pairs. Traditional graph matching problem is often formulated quadratic signment problem (QAP). For example, Gold & Rangarajan (1996) relaxes the constraints and pro-
poses the graduate assignment algorithm to solve the QAP. Leordeanu Hebert 2005 uses spectral
14

---

Under review as a conference paper at ICLR 2023
Table 8: The sensitivity of S-Mixup to mixup hyperparameter d.
0.1
vanilla
REDDIT-B
89.10= 2.09
89.15 # 2.10
89,30 = 2.69
84.70 = 6.17
81.40 = 8.01
77.25 + 5.39
84.85 = 2.42
IMDR-M
50.47 + 3.38
50.73 4: 3.66
49.67 + 2.89
50.53-42.77
50.29 + 3.91
49,20 :: 3.34
49.47 +: 2.60
relaxation to approximate the QAP. The Spectral Matching first relaxes the integer constraints and uses greedy method to satisfy them later. Furthermore, they propose iterative matching method IPFP [eordeanu et al. 2009) to optimize quadratic score in the discrete domain with climbing and convergence properties. Unlike these methods, [Cho al. (2010) proposes a novel random walk algorithm to solve the matching problem. However, it usually ly takes long time for these traditional algorithms (Wang et al.] 2017: Dokeroglu & Cosar] 2016) to compute the alignment, thereby we don't Von'tun use traditional graph matching algorithms in our framework for efficiency.
Another line of research uses bearning-based networks to compute the alignments between graphs. For example, [i et al. (2019) proposes to extract node embeddings by new cross-graph attention- based matching mechanism. Xu et al. (2019) learns the alignment and node embeddings of graphs simultaneously with Gromov- Wasserstein learning framework. Unlike these methods that obtain Bromov-Wasserstein
the final alignment by computing the pairwise similarity between node embeddings. Fey et al. (2020) proposes to add second stage iteratively update the initial alignments. Wang et al. (202 la pro- pose to learn the association graph, so the matching problem is translated into a constrained node classification task. While many learning- maaning-baased graph matching methods use ground truth correspon- dences to supervise the training of the networks, in our problem, there is a lack of such ground truth correspondences. Only a few studies address the problem by using self-supervised learning. For example, Liu et al.] (2022) proposes a contrastive learning framework for the visual graph matching problem. In our work, we follow [i et al.] (2019) to use the triplet loss in Equation f graph matching network by incorporating the prior knowledge that the learned representations of graphs from the same class should be more similar than those from different classes.
to train the
D.2 GRAPH EDIT DISTANCE
Sanfeliu 1983 first introduces the graph edit distance (GED) to measure the similarity be- tween graph pairs. As we introduced in Section 5.2 GED is defined as the minimum cost of an edit path which a sequence of elementary graph transformation operations. Computing the GED is known an NP-hard problem (Bunke, 1997p and many methods have been proposed to reduce the computational cost of GED. For ixample, Riesen & Bunke (2099) approximates the GED com- putation by means of bipartite graph matching. Several studies (Bougleux al. 2017 Neuhaus & Bunke 2007) show that GED is closely related to QAP and can be computed efficiently by graph matching solvers. Besides, there some caarinngbasse methods (Peng al. 2021 improve GED computation. We believe they can be adopted in our framework to compute an adaptive range for different graph pairs, addressing the limitation of S-Mixup discussed in Section 5.2
D.3 MIXUP FOR SELF-SUPERVISED LEARNING
While we study mixup methods for graph classification problems in this paper. few studies have investigated mixup in self-supervised learning on graphs. For example. Verma et al. (202 proposes Mixup-noise to generate positive and negative samples for contrastive learning. ZZhang et al.) (2022) proposes to generate negative samples for contrastive learning by mixing multiple samples with adaptive weights.
E SENSITIVITY ANALYSIS TO MIXUP HYPERPARAMETER
In this section, we conduct a hyperparameter study to analyze the sensitivity of S-Mixup to mixup hyperparameter a. We sample X' from beta distribution parameterized by different a. Specifically, we tune hyperparameter a among (0.1,0.2,005.112225) We adopt GCN as the classification back- bone in this experiment. Results in Table show that E [0.1, 0.5] consistently leads to better performance than vanilla, while using too large a may lead to underfitting. After we tune the hyper- parameter a, S-Mixup significantly improves GNNs" performance.
15

---

Under review as a conference paper at ICLR 2023
F WHAT IS S-MIXUP DOING? A CASE STUDY
In this subsection, we study the outcomes of S-Mixup via case study on the MOTIF dataset. Firstly, investigate the case of mixing graphs from the same class. We select random pair of graphs from the same class in the MOTIF dataset and visualize the outcomes of our method in Figure 2 The original graphs and the generated graph are shown Figure 2a and Figure respectively. The results show that our method can preserve the motif in the mixed result. In other words, the red nodes still form a cycle motif in the generated graph.
To study the case of mixing graphs from different classes, we characterize the similarity between generated graphs and original graph pairs using the normalized GED in- troduced Section 5.2 In this case study, we select ran-
tzed GED
dom pair of graphs from different classes in the MOTIF dataset and visualize the relationship between the mixup ratio À and the normalized GED in Figure 4 We observe that the normalized GED is closer to the mixup ratio À when À is larger. Such observation is consistent with The- orem in Section
0.5
Mixup ratio
Figure 4: Relationship between normal- ized GED and mixup ratio À
16


Reviews:
[{"review_id": "zUBSh9EQyD", "reviewer": "Reviewer_pxKa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "summary_of_the_review": "See above comments.", "strength_and_weaknesses": "Pros:\n\n1) The paper is clearly written and the idea is interesting and novel.\n2) The experimental results are convincing with state-of-the-art performance on public benchmarks.\n3) 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).\n\nCons:\n\nI 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. \n\nI have some suggestions on expanding the related work part (if space permits or put some to the appendix).\n\nIn the related work part, the authors may also briefly discuss:\n1) 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.\n\n[a] Self-supervised Learning of Visual Graph Matching, ECCV 2022\n\n2) 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.\n\n3) For mix-up based graph augmentation, there is another missed reference:\n[b] m-mix: Generating Hard Negatives via Multi-sample Mixing for Contrastive Learning, SIGKDD 2022", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "elb7rhcbp-", "reviewer": "Reviewer_KdGK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "Strengths:\n* 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.\n* 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.\n* The proposed method is simple and effective, and easy to implement. Compared to strong/recent baselines, the proposed method shows competitive performance. \n\t\t\nWeaknesses:\n* 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.\n* The proposed method needs to be compared with broader related work such Hu et al. [1] GraphMix [2], Gaug [3] etc.\n* 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?\n\n[1] Hu, Weihua, et al. \"Strategies for pre-training graph neural networks.\" arXiv preprint arXiv:1905.12265 (2019).\n[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.\n[3] Zhao, Tong, et al. \"Data augmentation for graph neural networks.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 12. 2021.\n\nQuestions:\n1.  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.\n2. The proposed method is limited to class-level tasks. Is it extensible to other tasks on graphs beyond graph classification?\n3. In eq (4), M is used. Did you consider the square root of M as in the normalized graph Laplacian matrix?\n4. What alpha was used for the beta distribution? How did you tune the hyperparameter? How sensitive is the performance gain to the hyperparameter tuning?\n5. How do you make sure that the augmented samples have the same labels? Or do you interpolate labels as well?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_v58Fn-QOK", "reviewer": "Reviewer_CYp4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n", "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.\n", "strength_and_weaknesses": "## Strengths\n1. 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.\n2. 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.\n\n\n## Weaknesses\n1. 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’$.\n2. 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?\n3. 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?\n4. Sec 5.1 and 6.4 can be merged.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "A_Mrp-2PPz", "reviewer": "Reviewer_t5LQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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", "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.", "strength_and_weaknesses": "**Strengths**\n\n1. Enforcing node-level alignment in graph mixup tasks is an interesting and convincing effort.\n2. The empirical improvements brought by the proposed alignment method seem significant and consistent w.r.t. other mixup strategies. \n\n**Weaknesses**\n\n1. 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. \n\n    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).\n\n2. 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?\n\nReferences:\n1. Li et al. Graph Matching Networks for Learning the Similarity of Graph Structured Objects. ICML 2019.\n1. Cho et al. Reweighted random walks for graph matching. ECCV 2010.\n1. Leordeanu et al. An integer projected fixed point method for graph matching and map inference. NIPS 2009. \n1. Zhou et al. Factorized Graph Matching. PAMI 2016.\n1. Wang et al. Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching. PAMI 2022.\n1. Fey et al. Deep Graph Matching Consensus. ICLR 2020.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9o1FY9l7WJ0", "reviewer": "Reviewer_bSxi", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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. ", "strength_and_weaknesses": "**Strengths**:\n- The paper is well-written and clear.\n- The method is straightforward and easy to implement.\n\n\n**Weaknesses**:\n- 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.\n- 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.  \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject