Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications
Authors: Xinyu Ma
Xu Chu
Yasha Wang
Yang Lin
Junfeng Zhao
Liantao Ma
Wenwu Zhu
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Data Augmentation
Graph Mixup
Fused Gromov Wasserstein

Abstract: Graph data augmentation has shown superiority in enhancing generalizability and robustness of GNNs in graph-level classifications. However, existing methods primarily focus on the augmentation in the graph signal space and the graph structure space independently, neglecting the joint interaction between them. In this paper, we address this limitation by formulating the problem as an optimal transport problem that aims to find an optimal inter-graph node matching strategy considering the interactions between graph structures and signals. To solve this problem, we propose a novel graph mixup algorithm called FGWMixup, which seeks a "midpoint" of source graphs in the Fused Gromov-Wasserstein (FGW) metric space. To enhance the scalability of our method, we introduce a relaxed FGW solver that accelerates FGWMixup by improving the convergence rate from $\mathcal{O}(t^{-1})$ to $\mathcal{O}(t^{-2})$. Extensive experiments conducted on five datasets using both classic (MPNNs) and advanced (Graphormers) GNN backbones demonstrate that \mname\xspace effectively improves the generalizability and robustness of GNNs. Codes are available at https://github.com/ArthurLeoM/FGWMixup.

Fused Soamov-Wasseestein Graph Mixup for Graph-level Classifications
Xinyu Ma
Xu Chu Yasha Wang Yang Lin'
Junfeng Zhao
Liantao Ma Wenwu Zhu
School of Computer Science, Peking University
Department of Computer Science and Technology, Tsinghua University
National Research and Engineering Center of Software Engineering, Peking University maxinyuêpku, edu. en, chu_ ttu_xu@mail. tsinghuu. edu.cn cn
Abstract
Graph data augmentation has shown superiority in enhancing generalizability and robustness of GNNs in graph-level classifications. However, existing methods primarily focus on the augmentation in the graph signal space and the graph structure space independently, neglecting the joint interaction between them. In this paper, we address this limitation by formulating the problem as an optimal transport problem that aims find an optimal inter-graph node matching strategy considering the interactions between graph structures and signals. To solve this problem, we propose novel graph mixup algorithm called FGWMixup, which seeks "midpoint" of source graphs in the Fused Ktrmovv-Wassereee enhance the scalability accelerates FGWMixup by improving the convergence rate from O(t-1) to O(1-)). Extensive experiments conducted on five datasets using both classic (MPNNs) and advanced (Graphormers) GNN backbones demonstrate that FGWMixup effectively improves the generalizability and robustness of GNNs. Codes are available com ccom/ArtthurleeM////Wiiix https://github: www.tttww.........eeeeeeeeeeeeee
(FGW) metric space. To our method, we introduce relaxed FGW solver that
1 Introduction
In recent years, Graph Neural Networks (GNNs) 11 have demonstrated promising capabilities in graph-level classifications, including molecular property prediction 3 4 social network classifica- tion (5). healthcare prediction 6 77. etc. Nevertheless, similar to other successfully deployed deep neural networks, GNNs also suffer from data insufficiency and perturbation, requiring the application of regularization techniques to improve generalizability and robustness (8). Data augmentation is widely adopted for regularization deep learning. involves creating new training data by applying various semantic-invarinn
transformations to the original data, such cropping rotating images in computer vision [9]. randomly inserting and rephrasing words in natural language [0, TT]. etc. The augmented data fortify deep neural networks (DNNs) against potential noise and outliers underlying insufficient samples, enabling DNNs to learn more robust and representative features.
Data augmentation for GNNs requires a unique design due to the distinctive properties of attributed graphs 11), such as irregular sizes, misaligned nodes, and diverse topologies, which are not encoun- tered when dealing with data in the Euclidean spaces such images and tabular data. Generally, the augmentation for GNNs necessitates the consideration of two intertwined yet complementary input spaces, namely the graph signal space X' and the graph structure space A, which are mapped to an aligned latent space H with GNNs. The graph signal space N' consists of node features. Current
"Corresponding Author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

GNNs rely on parameterized nonlinear transformations to process graph signals, which can be effi- ciently encoded and serve as crucial inputs for downstream predictions. Therefore, the augmentation of graph signals is significant for regularizing the GNN parameter space. On the other hand, the graph structure space A consists of information about graph topology. Traditional Message Passing Neural Networks (MPNNs), such as GCN and GIN, perform feature aggregation based on edge connectivity. Great efforts [3 14 IS [6] have been further exerted on enhancing the expressive power of GNNs 17]. which carry out new GNN architectures with stronger sensitivity to graph topology compared with MPNNs. Hence, a good augmentation method should also consider the graph structure space.
Recently, huge efforts have been made to design graph data augmentation methods based on the two spaces. Mainstream research [88] [9] 20] [2] considers the augmentation in the graph signal space and the graph structure space independently. For instance, ifMixup [9] conducts Euclidean mixup the graph signal space, yet fails to preserve key topologies of the original graphs. G-Mixup 20 realizes graph structure mixup based on the estimated graphons, yet fails to assign semantically meaningful graph signals. In fact, the graph signal and structure spaces are not isolated from each other, and there are strong entangling relations between them [23]. Therefore, a joint modeling of the interaction between the two spaces is essential for conducting graph data augmentation (joint modeling problem for short).
Aiming at graph data augmentation and addressing the joint modeling problem, we design a novel graph mixup [24] method considering the interaction of the two spaces during the mixup procedure. metric space that measures the distance with respect to both graph signals and structures. We propose to compute the distance metric by solving an optimal transport (OT) problem 25 The OT problem solves the optimal coupling between nodes across graphs in the fused Gromov- Wassersttn metric space (26). wherein the distance between points takes the interaction between the graph signals and structures into account. Specifically, following (26), graphs can be modeled as probability distributions embedded in the product metric space x A. Our objective is to solve an augmented graph that minimizes the weighted sum of transportation distances between the distributions of the source graphs and the objective graph in this metric space. Developing from the Gromov- Wasserstein metric (27), Fused Gromov- Wasserstein (FGW) distance (26) has been designed to calculate the tramsportation distance between two unregistered probability distributions defined on different product metric spaces comprising two components, such as graph signals and structures, which defines a proper distance metric for attributed graphs. In short words, the solved graph is the augmented mixup graph in a space considering the interaction between the graph signals and structures.
The key idea is to solve a proper inter-graph node matching strategy
However, trivially adopting FGW distance solvers 128 26) is not scalable to large graph datasets due to heavy computation burden. The computational bottleneck of baaed solvers is the nested triple-loop optimization (29]. mainly due to the polytope constraint for the coupling matrix in the FGW solver. Inspired by [30] disentangle the polytope constraint into two simplex constraints for rows and columns respectively, thence executing mirror descent with projections on the two simplexes in alternating manner to approximate the original constraint. We prove that with bounded gap with the ideal optimum, we may optimize the entire algorithm into a double-loop structure at convergence rate O(t²2), improving the Ot--l) rate of traditional FGW solvers.
In summary, we highlight the contributions of this paper: We address the challenge of enhancing the generalizability and robustness of GNNs by proposing novel graph data augmentation method that models the interaction between the graph signal and structure spaces. We formulate our objective as an OT problem and propose a novel graph mixup algorithm dubbed FGWMixup that seeks a "midpoint" of two graphs defined in the graph structure-signe product metric space. We employ FGW as the distance metric and speed up FGWMixUp xup by relaxing the polytope constraint into disentangled simplex constraints, reducing the complexity from nested triple loops to double loops and meanwhile improve the convergence rate of FGWMixup. Extensive experiments classic (MPNNs) and advanced (Graphormers) backbones. The results demonstrate that our method substantially improves the performance of GNNs in terms of their generalizability and robustness.
conducted on five datasets and four
2 Methodology
In this section, we formally introduce the proposed graph data augmentation method dubbed FGWMixup. We first introduce Fused Cromoo--asserse (FGW) distance that presents a dis- tance metric between graphs considering the interaction of graph signal and structure spaces.
2

---

Then we propose our optimization objective of graph mixup based on the FGW metric and the algorithmic solutions. Finally, we present our acceleration strategy. In the following we denote A, == ( E R E, 14 1} as the probability simplex with n-bins, and (A) as the set of symmetric matrices of size n taking values A. C IR.
2.1 Fused Gromov-Wasserree Wasserstein Distance
In OT problems, undirected attributed graph G with n nodes is defined as tuple (n,, X, A). /a
A, denotes the probability measure of nodes within the graph, which can be modeled as the relative
importance weights of graph nodes. Common choices of μu are uniform distributions [31 (14 In/
and degree distributions [32 (μ
(e)egu,))./(E.. dcg(e:)) ) X (zx1),... (x))
denotes the node feature matrix with d-dimensional feature on each node. A E S., (R) denotes a matrix that encodes structural relationships between nodes, which can be selected from adjacency matrix, shortest path distance matrix or other distance metrics based on the graph topologies. Given two graphs G1 (11 X1, A1) and G2 (M2. X2, A2) of sizes n2 and n2 respectively. Fused Gromov-Wass Wasserstein distance can be defined as follows:
min FGW,,G, G2)= TE)l i.j.k.
E ((1-a)d
( [ 2 + + A2(1.01") Te TKI
where [[ (2) { X TI,, 11, 1,, =2² is the set of all valid couplings between node distributions μ1 and 142, d(.,-) is the distance metric in the feature space, and a E [o, I] the weight that trades off between the cost on graph signals. The FGW distance is formulated as an optimization problem that aims to determine the optimal coupling between nodes in a fused metric space considering the interaction of graph structure and node features. The optimal coupling matrix T serves as a soft node matching strategy that tends match two pairs of nodes from different graphs that have both similar graph structural properties (such as k-hop connectivity, defined by A) and similar node features (such as Euclidean similarity, defined by d):.)).
cost on graph structure and Wasserstein
fact, FGW also defines a strict distance metric on the 1 and As are distance matrices, and defines semi-metrie whose triangle inequality is relaxed by 27 for q > In practice, we usually choose q and Euclidean distance for d(.--) to calculate FGW distance.
graph space (A, X .A) when
Solving FGW Distance Solving FGW distance a non-convex optimization problem, whose non-convexity comes from the quadratic term of the GW distance. There has been a line of research contributing to solving this problem. (26) proposes to apply the conditional gradient (CG) algorithm solve this problem, and (28) presents an entropic approximation of the problem and solves the optimization through Mirror Descent (MD) algorithm according to KL-divergence.
2.2 Solving Graph Mixup in the FGW Metric Space
Building upon the FGW distance and its properties, we propose a novel graph mixup method dubbed (GWMixup. Formally, our objective is to solve a synthetic graph G = (p. X, A) of size à that minimizes the weighted sum of FGW distances between & and two source graphs G1 = (Mi, X1, A1) and G2 (12 X2, A2) respectively. The optimization objective is as follows:
XFG G1) + (1 A)FGW G2),
arg GE(A,, Rexd, (R))
min
where À E [0, 1] is a scalar mixing ratio, usually sampled from a Beta(k., k) distribution with hyper- parameter k. This optimization problem formulates the graph mixup problem as an OT problem that aims to find the optimal graph G at the "midpoint" of G₁ and G2 in terms of both graph signals and structures. When the optimum G* is reached, the solutions of FGW distances between G and the source graphs G1, G2 provide the node matching strategies that minimize the costs of aligning graph structures and graph signals. The label of G is then assigned as gc Ayy, + (1 A)yG..
In practice, we usually fix the node probability distribution of & with a uniform distribution (i.e.. f ln/n) (26). Then, Eq E can be regarded as a nested bi-level optimization problem, which composes the upper-level optimization w.E.t the node feature matrix X and the graph structure Á.
3

---

and the lower-level optimization w.A.f the couplings between current G and G1, G2 denotes as T1, 22. Inspired by 128 26 331. we propose to solve Eq Juiin Block Coordinate Descent algorithm. which iteratively minimizes the lower-level and the upper-level with a nested loop framework. The algorithm is presented in [ The inner loop solves the lower-level problem (i.e., FGW distance at the k-th outer loop iteration, which is non-convex and requires optimization algorithms introduced in Section 2.1. The outer loop solves the upper-level problem (i.e., minimizing the weighted sum of FGW distances), which is a convex quadratic optimization problem w.r.t. ( and A with exact analytical solution (i.e., Line 7.8).
and the optimal couplings ạ nT² based on X (A)
Algorithm 1 FGWMixup: Solving Eq 2 with BCD Algorithm
1: Input: jú, G = (11 11, A1). G2 (M2, A2)
2: Optimizing: X E IR Rxd A E (R), TT E [[ f1), T2 E [(
3: for k in outer ilerations and not converged do:
4: ((R) (jz, (N)
(k))
5: Solve arg min m
FGW(( ,ii with MD CG (inner iterations)
6: Solve arg min (1) (G G2) with MD or CG (inner iterations)
7: Update A ((+1)
ApT (ATT (R) A i
(1)) T
+ (1
(A) 2) A2T2 (R) T
8: Update (1+1) Adiag(1 p (16)
X1 + A)diag( (1/ 1/ X2
(k)
9: end for
10: return ((K), .J XyG, + (1 A)yG2
2.3 Accelerating FGWMixup
Algorithm [[ a practical solution to optimize Eq whereas the computation complexity is relatively high. Specifically, Alg A adopts a nested double-loop framework, where the inner loop is the FGW solver that optimizes the couplings ग, and the outer loop updates the optimal feature matrix X and graph structure A accordingly. However, the most common FGW solvers, such as MD and CG, require another nested double-loop algorithm. This algorithm invokes (Bregman) projected gradient descent type methods to address the non-convex optimization of FGW, which involves taking a gradient step in the outer loop and projecting to the polytope-come constrained feasible set w.r.f. the couplings in the inner loop (e.g., using Sinkhorn [30] or Dykstra [34] iterations). Consequently, this makes the entire mixup algorithm a triple-loop framework, resulting in heavy computation burden.
Therefore, we attempt to design a method that efficiently accelerates the algorithm. There lie two efficiency bottlenecks of [ 1) the polytope constraints of couplings makes the FGW solver a nested double-loop algorithm, 2) the strict projection of couplings to the feasible sets probably modifies the gradient step to another direction that deviates from the original navigation of the gradient, possibly leading to slower convergence rate. In order to alleviate the problems, we are motivated to slightly relax the feasibility constraints of couplings to speed up the algorithm. Inspired by 29 30,, we do not strictly project π to fit the polytope constraint I[ M4y := { E n 1 1 In n22} after taking each gradient step. Instead, we relax the constraint into two simplex constraints of rows and columns respectively (i.e., II, { R I x #1). J. Ilg := f1T *= ' T 1n, = μ22) )a, and project π to the relaxed constraints II, and Ilg in an alternating fashion. The accelcrated algorithm is presented in Alg dubbed FGWMixup..
R X2
mainly substitutes Line and Line 6 of A with a single-loop FGW distance solver (Line 7-12 in Alg that relaxes the joint polytope constraints of the couplings. Specifically, we remove the constant term in FGW distance, and denote the equivalent metric as FGW (G,,GG Gz). The optimization objective of FGW (G. G2) can be regarded as a function of π, and we name the FGW function f(Tr) (See Appendix A. for details). Then employ entropic regularization f(T)) and select Mirror Descent as the core algorithm for the FGW solver. With the negative entropy Φ(z) Σ, I; log z; as the Bregman projection, the MD update takes the form of:
π π @ exp(->V<./(m
π <- Projwen, (T) == arg min Elll
|| - T||
where y is the step size. The subgradient of FGW w.r.f the coupling ा can be calculated as: Vnf(()) = (1 a)D 4aA, A
(4)

---

Algorithm 2 : Accelerated FGWMixup
1: Input: ju, G1 (1), X1, A1), G2 (12, X2, A2)
2: Optimizing: X E RRaxd Á E Sn (R), ग. E [i m1); 02 E (2).
3: for k in outer iterations and not converged do:
4: G(k) = (it, (k), A (A)
5: D = (d(x [.], Xibii)
D = (d(((d((( (k) (b) (2,, 8xn2
8xn1
6: for i in (1, do
7:
while not convergence do:
> Solve arg min FGW(C G.)
+ exp (7(4aA (T) (K)
A. (1 a)
8:
f ;
9:
()) f diag(ii./T
(1) 1a)
(K)
>> Bregman Projection on row constraint
(k) f n (b)
o exp (7(44A()) (1) (N)
A. (1 - a) D
10:
(k) (6) t diag( (1)
11:
n
1m;)
> Bregman Projection on column constraint
12:
end while
13: end for
14: Update ( f auj
1
(ATT (8)
A A
(k)
A (k) X1 + (1 - X)diag( 1/ /1 X2
+ (1 - 2)T
(k)
(k) T
15:
Update X (1++) t Adiag(1 / (A)
(1:)
end for
17:
return (M)), NG = XyG, + (1- A)yG2
where D = (d(x M.
X2lil)),,, x is the distance matrix of node features between two graphs. The detailed derivation can be found in Appendix A.2
Our relaxation is conducted in Line 9 and 11, where the couplings are projected to the row and column simplexes alternately instead of directly to the strict polytope. Although this relaxation may sacrifice some feasibility due to the relaxed projection, the efficiency of the algorithm has been greatly promoted. On the hand, noted that II, and II, are both simplexes, the Bregman projection w.r.f. the negative entropy of a simplex can be extremely efficiently conducted without invoking extra iterative optimizations (i.e., Line 9, 11), which simplifies the FGW solver from nested double-loop framework to a single-loop one. On the other hand, the relaxed constraint may also increase the convergence efficiency due closer optimization path to the unconstrained gradient descent.
We also provide some theoretical results to justify our algorithm. Proposition D prresents a convergence rate analysis our algorithm. Taking 1/y as the entropic regularization coefficient, our FGW solver can be formulated as Sinkhorn iterations, whose convergence rate can be optimized from O(t-l) to (t+²²) by conducting marginal constraint relaxation. Proposition 2 presents controlled gap between the optima given by the relaxed single-loop FGW solver and the strict FGW solver.
Proposition Let (X, p)), (V.v) be Polish probability spaces, and π I(H,V) the prob- ability measure on X' x y with marginals μ. Let Te be the Sinkhorn iterations n2: arg min H(-[T2-11) 22 = arg minlT(p..)) H- where H(plg) =- -, Polog ai the [T<x
Kullback-Leible divergence, and (T(( v) is the set of measures with second marginal v and arbitrary first marginal (11(u, *) is defined analogously). Let πt be the unique optimal solution. We have the convergence rate as follows:
H(T((=")+ H(**mm))= = O(t1),
(5)
H(n())) + (ulpe)) + (v, + (vlm) =0(0)))))((()))
(6)
Proposition| I [implies the faster convergence of marginal constraints than the strict joint constraint. This entails that with & Sinkhorn iterations of solving FGW, the solution of the relaxed FGW solver moves further than the strict one. This will benefit the convergence rate of the whole algorithm with a
larger step size of π.: (k) in each outer iteration.
Proposition 2. Let C1, O2 be two convex sets, and [(T) denote the FGW function w.r. We denote as the critical point set of strict FGW that solves min, f(x) + Trec, + TreCg, defined by:X = { E C2 C2 O V((T) + NNo (T) + +No, (r)}, and (T(TT) is the normal cone C
5

---

at x. The fix-point set Xrel of the relaxed FGW solving min f(T) + f(w) + h(() h(w) is
defined by: Xrd = { C,.w C2 : E ff(z) + P(Vh(w)) - Vh(T)) + Nc, (T), and 0
(((w) + (V)(T)) T +Ncc (w)) where l((.) is the Bregman projection function. Then, the
gap between Net and X satisfies:
E IR, VIT", w E Kyet, dist( TT" + w
x² + w
2 x)
min #EA
x
S ST/P.
(7)
2
This bounded gap ensures the correctness of F that as long as we select step size 1/p that is small enough, the scale of the upper bound T/p will be sufficiently small to ensure the convergence to the ideal optimum of our algorithm. The detailed proofs of Propositions I aand are presented in Appendix
3 Experiments
3.1 Experimental Settings
Datasets We evaluate our methods with five widely-used graph classification tasks from the graph benchmark dataset collection TUDataset 35:: NCI1 and NC1109 [36] 377 for small molecule classification, PROTEINS (38) for protein categorization, and IMDB-B and IMDB-M [5] for social networks classification. Noted that there are no node features in IMDB-B and IMDB-M datasets,
we augment the two datasets with node degree features as in 22 19 20). Detailed statisties on these datasets are reported in Appendix D.I
Backbones Most existing works select traditional MPNNs such as GCN and GIN as the backbone. However, traditional MPNNs exhibit limited expressive power and sensitivity to graph structures (upper bounded by 1- Weisfeiilr--
(1-WL) test [I7 37), while there exist various adavanced GNN architectures [13 14 [6] with stronger expressive power (upper bound promoted to 3-WL test). Moreover, the use of a global pooling layer (c.g., mcan pooling) in graph classification models may further deteriorate their perception of intricate graph topologies. These challenges may undermine the reliability of the conclusions regarding the effectiveness of graph structure augmentation. Therefore, attempt to alleviate the problems from two aspects. 1) We modify the READOUT approach of GIN and GCN to save as much structural information as we can. Following (39], we apply virtual node that connects with all other nodes and use the final latent representation of the virtual node to conduct READOUT. The two modified backbones are dubbed vGIN and vGCN. 2) We select two Transformer-be based GNNs with stronger expressive power as the backbones, namely Graphormer (39 and Graphormer-O0 GD [16. They are proven to be more sensitive to graph structures, and Graphormer- GD is even capable of perceiving cut edges and cut vertices in graphs. Detailed information about the selected backbones is introduced in Appendix D.2
Comparison Baselines We select the following data augmentation methods as the comparison baselines. DropEdge 40) randomly removes a certain ratio of edges from the input graphs. DropNode 41 randomly removes a certain portion of nodes as well as the edge connections. M-Mixup 42] conducts Euclidean mixup in the latent spaces, which interpolates the graph representations after the READOUT function. ifMixup [9] applies an arbitrary node matching strategy to conduct mixup on graph node signals, without preserving key topologies of original graphs. G-Mixup (00 conducts Euclidean addition on the estimated graphons of different classes of graphs to conduct class-level graph mixup. We also present the performances of the vanilla backbones, as well as our proposed method w/ and w/o acceleration, denoted as FGWMixup, and FGWMi respectively.
Experimental Setups For a fair comparison, we employ the same set of hyperparameter configura- tions for all data augmentation methods each backbone architecture. For all datasets, We randomly hold out test set comprising 10% of the entire dataset and employ 10-fold cross-validation on the remaining data. We report the average and standard deviation of the accuracy on the test set over the best models selected from the 10 folds. This setting is more realistic than reporting results from validation sets in a simple 10-fold CV and allows a better understanding of the generalizability [43]. We implement our backbones and mixup algorithms based Deep Graph Library (DGL) (44) and Python Optimal Transport (POT) [45] open-source libraries. More experimental and implementation details are introduced in Appendix D33 and D.4

---

PROTEINS
NCI1
NCT109
IMDB-B
IMDB-M
Methods
vGIN
VGIN
VGCN
YGIN
vGCN
vGIN
VGIN
vGCN
sanilla
(4.93(3.02)
74.75(2.60)
(.8871187)
76.91(1.80) 80)
75.700 1.85)
71 9.99)) 1.359
72.30(1.34)
(9.002266))
49.47(.76)
Drophdde
23.59/2.50)
74.49(4.18)
86.47(285)
76.10(2.04)
75 25.38)))
75.77(155)
73. 3.885)
73.30(..29)
49.4%(2.66
49.40(3.52)
MPNNs
Drophode
24.48/2:911
76.59X1.29 75.11(3.00)
73.9 73.98/2.16) 72.42(1.71)
71 71.5003.25 75.45(1.90)
73.2065.58)
49.5003.28 3.9))
50.00,3.41)
M.Mixup
74.4033.00
75.6514.51)
76 76.499
77.76 77.762.75)
75 71.47)
75.7%
72 (2.38
72. 72.004445)
49 49.15)3.25)
49 49.47(2.56)
ifdxxup
14.7663.711
76.1611.75) 24.04
77.3362.50
76.441.56) 16.1311.7)
72.50
12:
49.07(3316)
49.73/4.67)
G-Misop
74 84.8992999
(4.5722.85 88)
75.55/2.32)
76 78.199)
72.40X4.83
(2.2006.45)
49.47(4,73)
860
76.01(3.19)
46.401665
76.7%(1.81)
73.00/ 69)
73.40.5.11 12)
49.50/2.63)
50.80/4.06)
PGWMizup-
75.2003.30)
75.2013.03)
77.272.711
78.47(1.74)
76.64/2.60
76.52(1.59)
43.50)
74.0%/2.90)
(9.2003333)
50.47(5444)
Methods
Kiraphommrr OrophommerDD DimploomnnDDKKKnoommmmeee CraphommerDD CraphomseGG/Gmnnooonen GriphomenCiD Ceophoommer
(repooereoOrrrrooeneee GraphommerGiD (Crpphommer GrophomerGD
vanilla
(28.4%(311)
76.0((2002)
(61.56(3.70)
77.49(2.01)
74.9% (6)5444304)
(00000000
71.50X4.00)
47.47(2.98) (48.57(4110)
Dropkidge
25.2004.02)
25.1213:22)
63.07(3.21)
74.94;2.44)
(6.73)3.50)
74.73(3.22)
71.10.5.65)
72.30(3.93)
49.0044.99)
46.87(33885
Griphrrmes
Drophidde
25.2222.15
76.29)349)
64 111))
76.2011.95)
(3.77)3.46)
74.74(2.07)
71 10)..118
71. 11.30.518)
48 48.47(4.008)
47 47.67(2.85
M.Mixup
25. (5.776))78)
74.39(3.883
(2.3313.48))
(5.47(1.45)
74.61(1.80 20..54(2770)
71 (...0888)
70.50 70.5044.70)
49. (3.6644255
48.00.3.85)
G-Misup
74.8513.52) 15.74(3.12)
63.0774,40) 40)
76.06)3112)
05..022.995 2.96)
74 2,044)
72. (2.100633) 38)
71 11.10/5.01>
46 93/5.18)
46. (0X40144441
Pos
76.82/2.35)
66.45(2.58) (7.18
TX
72.605.08) 76.01(3.04)
72.4014.48)
48.87(4.13))
POVMizup.
(6.19)3200
76.16(3.41)
61.2663.25)
76.62(3.06)
(67.66/2882)
75.45(1.80)
71.7
71.50(1.35)
50.27(4.26)
48.53/2.95)
Table 1: Test set classification accuracy (%) from 10-fold CV on five benchmark datasets, Results are presented with the form of (st.dee)). and the best-perforning method is highlighted in boldface. Note: ifMixup has no results on Graphormers because it generates graphs with continuous edge weights and is inapplicable for the Spatial Encoding module in the Graphormer-based architectures.
3.2 Experimental Results
Main Results We compare the performance of various GNN backbones on five benchmark datasets equipped with different graph data augmentation methods and summarize the results in Table [[] As is shown in the table, FGWMixup and FGWMixup, consistently outperform all other SOTA baseline methods, which obtain 13 and 7 best performances out of all the 20 settings respectively. The superiority is mainly attributed to the adoption of the FGW metric. Existing works hardly consider the node matching problem to align two unregistered graphs embedded in the signal-structure fused metric spaces, whereas the FGW metric searches the optimum from all possible couplings and conducts semantic-invariant augmentation guided by the optimal node matching strategy. Remarkably, despite introducing some infeasibility for acceleration, FGWMixup. maintains consistent performance due to the theoretically controlled gap with the ideal optimum, as demonstrated in Prop. [ Moreover, FGWMixup and FGWMixup, both effectively improve the performance and generalizability of various GNNs. Specifically, our methods achieve an average relative improvement of 1.79% on MPNN backbones and 2.67% Graphormer- based backbones when predicting held-out unseen samples. Interestingly, most SOTA graph data augmentation methods fail to bring notable improvements and even degrade the performance of Graphormers, which exhibit stronger expressive power and conduct more comprehensive interactions between graph signal and structure spaces. For instance, none of the baseline methods improve GraphormerGD on NCI109 and NCII datasets. However, our methods show even larger improvements on Graphormers compared to MPNNs, as we explicitly consider the interactions between the graph signal and structure spaces during the mixup process. In particular, the relative improvements of FGWMixup reach up to 7.94% on Graphormer and 2.95% on GraphormerGD. All the results above validate the effectiveness of our methods. Furthermore, we also conduct experiments on large-scale OGB 466 datasets, and the results are provided in Appendix E.5
Robustness against Label Corruptions In this subsection, we evaluate the robustness of our methods against noisy labels. Practically, we introduce random label corruptions (i.e., switching to another random label) with ratios of 20%, 40%, and 60% on the IMDB-B and NCI1 datasets. We employ vGCN as the backbone model and summarize the results in Table 2 The results evidently demonstrate that the mixup-serie methods consistently outperform the in-sample augmentation method (DropFigge) by significant margin. This improvement can be attributed to the soft-labeling strategy employed by mixup, which reduces the model's sensitivity to individual mislabeled instances and encourages the model to conduct more informed predictions based on the overall distribution of the blended samples. Notably, among all the mixup methods, FGWMi xup and PGWMixup, exhibit stable and consistently superior performance under noisy label conditions. In conclusion, our methods effectively enhance the robustness of GNNs against label corruptions.
Analysis on Mixup Efficiency We run FGWMixup and FGWMixup. individually with identical experimental settings (including stopping criteria and hyper- paprm-parameters such as mixup ratio, etc.) on the same computing device and investigate the run-time computational efficiencies. Table
7

---

IMDB-B
NCII
Methods
20%
40%
60%
20%
40%
60%
vanilla
70.00(5.16)
59.70(5.06)
47.90(4.30)
70.58(1.29)
61.95(2.19)
48. 48.25(4.87)
DropEdge
68.30(5.85)
59,40(5.00)
50.10(1.92)
69.51(2.27)
60.32(2.60)
49.61(1.28)
M-Mixup
70.70(5.90)
59.70(5.87)
50.90(1.81)
71.53(2.75)
63.24(2.59)
48.66(3.02)
G-Mixup
67.50(4.52)
59.10(4.74)
49.40(2.87)
72.46(1.95)
63.26(4.39)
50.01(1.26)
FGWMixup xup
70. 10.10().39)
61.90(6.17)
50.80(3.19)
62.99(1.35) 72.92(1.56)
50.12(3.51) 50.02(3.38)
FGWMixup.
70.80(3.97)
61.80(5.69)
51.00(1.54)
72.75(2.29)
63.55(2.60)
Table Experimental results of robustness against label corruption with different ratios.
Avg. Mixup Time (s) / Fold
Datasets
PROTEINS
NCI1
NCI109
IMDB-B
IMDB-M
FGWMixup
802.24
1711.45
1747.2
296.62
212.53
FGWMixup.
394.57
637.41
608.61
85.69
74.53
Speedup 2.03x
2.67
2.74x
3,46x
2.85x
Table 3: Comparisons of algorithm execution efficiency between FGWMixup and FGWMixup,
the average time spent on the mixup procedures of FGWMixup and FGWMixup, per fold. We can observe that FGWMixup, decreases the mixup time cost distinct margin, providing at least 2.03 and up to 3.46x of efficiency promotion. The results are consistent with our theoretical analysis of the convergence rate improvements, as shown in Proposition More detailed efficiency statistics and discussions are introduced in Appendix
Infeasibility Analysis the Single-loop FGW Solver in FGWMixup. We conduct experiment to analyze the infeasibility of our single-loop FGW solver compared with the strict CG solver. Practically, we randomly select 1,000 pairs of graphs from PROTEINS dataset and apply the two solvers to calculate the FGW distance between each pair of graphs. The distances of the i-th pair of graphs calculated by the strict solver and the relaxed solver are denoted d; and di, respectively. We report the following metrics for comparison:
MAE: Mean absolute error of FGW distance, i.e., 1/2 E dil
MAPE: Mean absolute percentage error of FGW distance, i.e., NV Σ
Id,-d;1
d,
mean-FGW: Mean FGW distance given by the strict CG solver, i.c., N Σ dy.
mean-FGW* Mean FGW distance given by the single-loop solver, i.c., N Ed.
T-diff: 1.2-norm of the difference between transportation plan matrices (divided by the size of the matrix for normalization).
MAE
MAPR
mean-FGW
mean-FGWs
T-diff
0.0126(0.0170)
0.0748(0.102) 1022)
0.2198
0,2143
0.0006(0.0010)
Table 4: Infeasibility analysis on the single-loop FGW solver in FGWMixup..
The results are shown in Table 4 We can observe that the MAPE is only 0.0748, which means the FGW distance estimated by the single-loop relaxed solver is only 7.48% different from the strict CG solver. Moreover, the absolute error is around 0.01, which is quite small compared with the absolute value FGW distances (-0.21). We can also find that the L2-norm of the difference between two transportation plan matrices only 0.0006, which means solvers give quite similar transportation plans. All the results imply that the single-loop solver will not produce huge infeasibility or make the estimation of FGW distance inaccurate.
3.3 Further Analyses
Effects of the Trade-off Coefficient We provide sensitivity analysis w.r.t. the trade-off coefficient of our proposed mixup methods valued from (0.05, 0.5. 0.95, 1.0) two backbones and two

---

PROTEINS
NCI1
Methods
om00.95
cm00.5
0m00.0
0=11.
em0.95
o=0.5
o.0.08
VGIN FGWW
75.02(3.86)
74.86(240) 75.38(2.58)
74.57(2.62)
78.32(2.68)
77.42(1.93)
77-62(2.37)
75.91(2.33)
VGCN-POONN Pop
76.01(3.19)
74.932.74) 75.47(3.56)
78.37(2.40) 74.4
78.00(1.00 77,93(168)
07.270.92)
VGIN- MuP.
75.20(3.30)
74.57(3.30)
74.39(3.01)
73.94(3.86)
77.27(2.71)
71,232.47)
76.59(2.14)
(7.20X1.69)
vGCN POWNExup.
75.20(3.03)
74.57(3.52)
74.84(316)
74.56(2.91)
78.47(1.4)
77.66(1.48)
78.93(1911)
77.71(197)
Table 5: Experimental results of different a on PROTEINS and NCII datasets.
Figure 1: Test performance of our methods with different graph size settings on NCII and PROTEINS
datasets using vGCNs as the backbone.
Adaptive
Modian
2xM
0.5xMed
Vanilla
NCI1
PROTEINS
79.0
79.0
78.5
78.5
78.0
78.0
75.5
73.5
Accuncy
77.5
77.0
77.0
74.5
74.5
76.5
76.5
76.0
76.0
FGWMixup
FGWMisup-
FGWMisup
FGWMixup-
datasets. Note that a controls the weights of the node feature alignment and graph structure alignment costs, and 1.0 falls back to the case of GW metric where node features not incorporated. From the results shown in Table we can observe that: 1) when FGW falls back to GW =l).), where node features are no longer taken into account, the performance will significantly decay (generally the worst among all investigated a values). This demonstrates the importance of solving the joint modeling problem in graph mixup tasks. 2) a=0.95 the best setting in most cases. This empirically implies that it is better to conduct more structural alignment in graph mixup. In practice, we set a to 0.95 for all of our reported results.
Effects of Mixup Graph Sizes We investigate the performance of FGwMixup and FGWMixup, with various mixup graph sizes (node numbers), including adaptive graph sizes (i.e., weighted average size of the mixup source graphs, ň An1 + (1 A)m2, which is selected sizes (i.e., the median size of all training graphs, 0.5 and x the median). The ablation studies are composed NCI1 and PROTEINS datasets using vGCN backbone as motivating examples, and the results are illustrated in [ We can observe that the best performance steadily obtained when selecting graph sizes with adaptive strategy, whereas the fixed graph sizes lead unstable results. Specifically, selecting the median or larger size may occasionally yield comparable performances, yet selecting the smaller size can result in an overall performance decay of over 1%. This phenomenon is associated with the graph size generalization problem [47] 48 that describes the performance degradation of GNNs caused by the graph size distributional shift between training and testing data, The fixed strategy may aggravate this problem, particularly for small graphs that struggle to generalize to larger ones. contrast, the adaptive strategy can potentially combat this distributional shift by increasing the data diversity and reach better test time performance.
method) and fixed graph
Effects of GNN Depths To validate the improvement of our methods across various model depths, evaluate the performance of FGWMixup and PGwMixup. using vGCNs equipped with different numbers (3-8) of layers. We experiment on NCII and PROTEINS datasets, and the results are illustrated in Fig We can observe that methods consistently improve the performance on NC11 under all GCN depth settings by significant margin. The same conclusion is also true for most cases on PROTEINS except for the 7-layer vGCN. These results indicate universal improvement of our methods on GNNs with various depths.
Other Discussions More further analyses are introduced in the Appendix, including qualitative analyses of our mixup results (see Appendix E. further discussions on G-Mixup (see Appendix F.2bb and sensitivity analysis of the hyperparameter in Beta distribution where mixup weights are sampled from (see Appendix E.4).

---

Figure 2: Test performance of methods using vGCNs with varying numbers of layers NCI1 and PROTEINS datasets.
NCI1
PROTEINS
76.0
78.5
Σ
75.5
78.0
14.5
77.5
97.0
73.5
16.5
73.0
72.5
GCN Depth
vuilla
Fow
POWMErrp
GCN Depth
4
Related Works
There currently two mainstream perspectives of graph data aug- mentation for graph-level classifications. A line of research concentrates on graph signal augmen- tation [1 18 19]. Node Atrribute Masking [4] assigns random node features for a certain ratio of graph nodes. IfMixup [19] conducts Fuclidean mixup on node features from different graphs with arbitrary node alignment strategy, whereas it damages the critical topologies (e-g.. rings, bi- partibility) of the source graphs. Another line of work focuses on graph structure augmentation 49 20 21 22 50 41 51] Approaches like Subgraph 49
Graph Data Augmentation
[9 41] DropEdge (4) and GAug [50] conduct removals or additions of graph nodes or edges to generate new graph structures. Graph Transplant 21] and Submix 2o realize CutMix-like augmentations on graphs, which off subgraph from the original graph and replace it with another. G-Mixup (20) estimates a graph structure generator (i.e., graphon) for each class of graphs and conducts Euclidean addition on graphons to realize structural mixup. However, as GNNs can capture the complex interaction between the two entangled yet complementary input spaces, is essential to model this interaction for comprehensive graph data augmentation. Regrettably, current works have devoted little attention to this interaction.
Optimal Transport on Graphs Building upon traditional Optimal Transport (OT)
25 methods
(e.g., Wasserstein distance(52),. graph OT allows defining a very general distance metric between structured/relaational data points embedded different metric spaces, where the data points are modeled probability distributions. It proceeds by solving coupling between the distributions that minimizes a specific cost. The solution of graph OT hugely relies on the (Fused)
Wannoov-tttseetteinn (GW) (77 26 distance metric. Further works employ the GW couplings for solving tasks such as graph node matching and partitioning [53
32 [4], and utilize GW distance as a common metric
in graph metric learning frameworks (55 3 56]. Due to the high complexity of the GW-series
efficiency. In our work, we formulate graph mixup concentrates on boosting the computational FGW-based OT problem that solves the optimal node matching strategy minimizing the alignment costs of graph structures and signals. Meanwhile, attempt to accelerate the mixup procedure with faster convergence rate.
algorithm, another line of research 28
57 58 29]
5 Conclusion and Limitation
In this work, we introduce novel graph data augmentation method for graph-level classifications dubbed FGWMixup. FGWMixup formulates the mixup of two graphs as an optimal transport problem aiming to seek "midpoint" of two graphs embedded in the graph signal-structure fused metric space. We employ the FGW distance metric to solve the problem and further propose an accelerated algorithm that improves the convergence rate from O(1-1) to 2( for better scalability of our method. Comprehensive experiments demonstrate the effectivenesss of FGWMixup in terms of enhancing the performance, generalizability, and robustness of GNNs, and also validate the efficiency and correctness of our accelcration strategy.
Despite the promising results obtained in our work, it is important to acknowledge its limitations. Our focus has primarily been on graph data augmentation for graph-level classifications. However, still remains a challenging question to better exploit the interactions between the graph signal and structure spaces for data augmentation
other graph prediction tasks, such as link prediction and node classification. Moreover, we experiment with four classic (MPNNs) and advanced (Graphormers) GNNs, while there remain other frameworks that could be taken into account. We expect to carry out graph classification benchmark with more comprehensive GNN frameworks in our future work.
10

---

Acknowledgements
This work was supported by the National Natural Science Foundation of China (No.82241052).
References
[1] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional 2016.
networks. arXiv preprint
[2] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations.
[3] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning. pages 1263-1272. PMLR, 2017.
[4] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical Science, 9()):113-530 2018.
[5] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1365-1374, 2015.
[6] Xinyu Ma, Yasha Wang, Xu Chu, Liantao Ma, Wen Tang, Junfeng Zhao, Ye Yuan, and Guoren Wang. Patient health representation learning via correlational sparse prior of medical features. IEEE Transactions on Knowledge and Data Engineering, 2022.
[7] Yongxin Xu, Xu Chu, Kai Yang, Zhiyuan Wang, Peinie Zou, Hongxin Ding, Junfeng Zhao, Yasha Wang, and Bing Xie. Seqcare: Sequential training with external medical knowledge graph for diagnosis prediction in healthcare data. In Proceedings of the ACM Web Conference 2023, pages 2819-2881 2830, 2023.
[8] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-
115, 2021.
[9] Suorong Yang, Weikang Xiao, Mengcheng Zhang, Suhan Guo, Jian Zhao, and Furao Shen. Image data augmentation for deep learning: A survey, arXiv preprint arXiv:2204.086/00 2022.
[10] Jason Wei and Kai Zou. Eda: Easy data augmentation techniques for boosting performance on text classification tasks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP) pages 6382-6388, 2019.
[11] Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances in Neural Information Processing Systems, 28, 2015.
[12] Zhiqiang Xu, Yiping Ke, Yi Wang, Hong Cheng, and James Cheng. A model-based approach to attributed graph clustering. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pages 605-516,70 2012.
[13] Haggai Maron, Heli Ben- Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in Neural Information Processing Systems, 32, 2019.
[14] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. arXiv preprint arXiv:2110.037533 2021.
[15] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. arXiv preprint 10x.v:2100.02910. 2021.
[16] Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. arXiv preprint arXiv:2301.09503 2023.
11

---

[17] Pan Li and Jure Leskovec. The expressive power of graph neural networks. Graph Neural Networks: Foundations. Frontiers, and Applications, pages 63-98, 2022.
[18] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi. Nodeaug: Semi-supervised node classification with data augmentation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 207-217, 2020.
[19] Hongyu Guo and Yongyi Mao. ifmixup: Towards intrusion-free graph mixup for graph classification. arXiv e-prints, pages arXiv-2110, 2021.
[20] Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In International Conference on Machine Learning, pages 2230-8248. PMLR, 2022.
[21] Joonhyung Park, Hajin Shim, and Eunho Yang. Graph transplant: Node selienccy-guidee graph mixup with local structure preservation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7966-7974, 2022.
[22] Jaemin Yoo, Sooyeon Shim, and U Kang. Model-agnostic augmentation for accurate graph classification. In Proceedings of the ACM Web Conference 2022, pages 1281-1291, 2022.
[23] Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE. 106(5):808-82) 828, 2018.
[24] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint urXiv: 2017.
[25] Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 11(5-6):355-600 2019.
[26] Vayer Titouan, Nicolas Courty, Romain Tavenard, and Rémi Flamary. Optimal transport for structured data with application on graphs. In International Conference on Machine Learning, pages 6275-6284. PMLR, 2019.
[27] Facundo Mémoli.
distances and the metric approach to object matching. Foundations of Computational Mathematics, 11:417-487, 2011.
[28] Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov-wassersten averaging of kernel and distance matrices. In International Conference on Machine Learning, pages 2664-2672. PMLR, 2016.
[29] Jiajin Li, Jianheng Tang, Lemin Kong, Huikang Liu, Jia Li, Anthony Man-Cho So, and Jose Blanchet. A convergent single-loop algorithm for relaxation of gromov-wasserstein in graph data. arXiv preprint Miiv:2303.06595 2023.
[30] Marco Cuturi. Sinkhorn distances:
Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, 26, 2013.
[31] Cédric Vincent-Cuaz, Rémi Flamary, Marco Corneli, Titouan Vayer, and Nicolas Courty. Template based graph neural network with optimal transport distances. arXiv preprint arXiv:2205.15733. 2022.
[32] Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov-wasserster learning for graph matching and node embedding. In International Conference on Machine Learning, pages 6932-6944 6941. PMLR, 2019.
[33] Rémi Flamary, Nicolas Courty, Devis Tuia, and Alain Rakotomamonjy. Optimal transport with laplacian regularization: Applications to domain adaptation and shape matching. In NIPS Workshop on Optimal Transport and Machine Learning OT'L,, 2014.
[34] Meyer Scethon, Marco Cuturi, and Gabriel Peyré. Low-rank sinkhorn factorization. In International Conference Machine Learning, pages 9344-9354, PMLR, 2021.
12

---

[35] 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.
[36] Nikil Wale and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. In Sixth International Conference on Data Mining (ICDM '06), pages 678-689. IEFE, 2006.
[37] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lchman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[38] Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex J Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 2: 2005.
[39] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888 2021.
[40] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint 1rXiv 10903, 2019.
[41] 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-58233 2020.
[42] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 2021, pages 3663-3674, 2021.
[43] Yoshua Bengio and Yves Grandvalet. No unbiased estimator of the variance of k-fold cross- validation. Advances in Neural Information Processing Systems, 16, 2003.
[44] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A centric, tighly-performant package for graph neural networks. arXiv preprint arXiv: 1wt.//9999.133 2019.
[45] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélic Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong. and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1 8, 2021.
[46] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances neural information processing systems, 33:22118 12-1333,, 2020.
[47] Davide Buffelli, Pietro Lió, and Fabio Vandin. Sizeshiftreg: a regularization method for improving size-generalization in graph neural networks. In Advances in Neural Information Processing Systems, 2022.
[48] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classification extrapolations. In International Conference on Machine Learning, pages 837-851. PMLR, 2021.
[49] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Grapherop: Subgraph cropping for graph classification. arXiv preprint arXiv:2009. 10564, 2020.
[50] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11015-11023, 2021.
13

---

[51] Hyeonjin Park, Seunghun Lee, Sihyeon Kim, Jinyoung Park, Jisu Jeong, Kyung-Min Kim, Jung-Wor -Wo Ha, and Hyunwoo Kim. Metropolis-hastine data augmentation for graph neural networks. Advances in Neural Information Processing Systems, 34: 34:19010-19020, 2021.
[52] Cédric Villani. Topics in Optimal Transportation. Number 58, American Mathematical Soc., 2003.
[53] Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromev-wasserstei learning for graph partitioning and matching. Advances in Neural Information Processing Systems, 32, 2019.
[54] Samir Chowdhury and Tom Needham. Generalized spectral clustering via gromov-wasserseeh learning. In International Conference on Artificial Intelligence and Statistics, pages 712-720.
PMLR, 2021.
[55] Cédric Vincent-Cuaz, Titouan Vayer, Rémi Flamary, Marco Corneli, and Nicolas Courty. Online graph dictionary learning. In International Conference on Machine Learning, pages 10564- 10574. PMLR, 2021.
[56] Benson Chen, Gary Bécigneul, Octavian-Eugen Ganea, Regina Barzilay, and Tommi Jaakkola. Optimal transport graph neural networks. arXiv preprint arXiv:2006.04880 2020.
[57] Cédric Vincent-Cuaz, Rémi Flamary, Marco Corneli, Titouan Vayer, and Nicolas Courty, Semi-relaxed wisserseann divergence with applications on graphs. arXiv preprint arXiv:2110.02753, 2021.
[58] Meyer Scetbon, Gabriel Peyré, and Marco Cuturi. Linear-time gromov wasserstein distances using low rank couplings and costs. In International Conference on Machine Learning, pages 19347-19365. PMLR, 2022.
[59] Promit Ghosal and Marcel Nutz. On the convergence rate of sinkhorn's algorithm. arXiv preprint arXiv:2212.06000 2022.
[60] Heinz H Bauschke. Projection algorithms and monotone operators. 1996.
[61] Zhi-Quan Luo and Paul Tseng. Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem. SIAM Journal on Optimization, 2(1):43- 54, 1992.
[62] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
[63] Douglas Klein and Milan Randić, Resistance distance, Journal of Mathematical Chemistry, 12:81-95, 1993.
[64] Hongteng Xu, Peilin Zhao, Junzhou Huang, and Dixin Luo. Learning graphon autoencoders for generative graph modeling. arXiv preprint arXiv:2105. /4244, 2021.
[65] Nikolay Sakhamykk and Braun Hugo. Efficient maximum flow allgorithm.
14

---

A Problem Properties
A.1 FGW Distance Metric
Fused Gromov-Wasserstein Distance 226 are defined in Eq[ It can also be rewritten as follows:
(G.(G1,G2)
min Tell( (2))
aL) A2) +
((1 (11-a] [[1-a]D-s
T),
(8)
where D = [d(z)) (1) ( His is the distance matrix of node features, and L(A1 A2) 22 {A - A2(i, Ols is 4-dimensional tensor that depicts the structural distances. We denote (U,V) = ur(UT V) as the matrix scalar product. The & operator conducts tensor-matrix
multiplication as: & T
def. (Ex,e Exs.eisk,eeee i.j
Then according to Proposition 28 when
we take the fo-n to calculate the structural distance, we have:
I(A,, A2) 2 CALAA 2
(9)
where CAJ.A, = - U U). Taking Eq 9 into Eq
I U2 A² and 62 denotes the Hadamard square (i.e., U we can rewrite the minimizer as:
RHS = (1 - (D, T A u 11 T) + a m1 A TT) -2
(10)
a{A p1 μ1 + - u2 (2) +(11 -al 2T
constant
The items the overbrace become a constant because the marginals of π are fixed as μr and p22 respectively. Therefore, we can remove the constant term and formulate equivalent optimization objective denoted FGW(G1, G2), which can be rewritten
FGW(G1, G2) min ((1 a) 22 π
nEll(uu,
(11)
min TEll(p).P))
a1 a)) tr(n T DD- 2a ATT
We denote the above optimization objective as function f(x) w.r.t. and we call it the FGW function in the main text.
A.2 Mirror Descent and the Relaxed FGW Solver in FGWMixup.
Definition (Normal Cone). Given any set C and point x E C, we can define normal cone as:
Nc(x) [g g g Vy EC
There are some properties of normal cone. The normal cone is always convex, and Proje(# + 2) x, Vr C, E Ne(x) always holds.
Proposition (The Update of Mirror Descent). The update of Mirror Descent takes the form of (k+1)) arg min (2c (k+))))) where o(-) is Bregman Projection, and V (k(l) (k) /=)//p
Proof. For constrained optimization problem minsex f(x), X D. Mirror Descent iteratively updates with (k+1) arg minrex V (x)(())) + pDo (()) with Bregman divergence Do(r, y) = Φ(x) - Φ(v) - (Volv), - y). We further have:
z (k+1) arg min Vf T + pDs(a,x<1))
= (z( (1)) T /p VQ(z((+1) vo(z(()) (x+())
(12)
(
arg min D (z, y (++1))) where (++1)) = Vo(z(1)) ()((())) z
15

---

Figure 3: The illustration of the MD procedure.
D
(x((x(
(k)
2
V VΦ
V
x (k+1)
X
VΦ(D)
(k+
Dual Space
Primal Space
This updating procedure is vividly depicted by Fig For each update of (((k), MD conducts the following steps:
Apply mirror mapping (Vo(+)) (k) from the primal space D the dual space VΦ(D).
Take gradient step in the dual space, which is 5(k+ = vo(x(*)) Vf(x()))/p
Inversely mapping (-)) the dual space back to the primal space, which is y(+11)
V (6(k+t))) also written as (o()(++1)) (k))
(x((()))
The updated point may fall out of the constraints of X. Thus, Bregman projection is conducted project (*++1) to ((++1) X. where ((++ arg min Dz ()))).)
The relaxed FGW conducts projections to constraints of rows and columns alternately, which is written as min, f(x [[ + [xell>) where the indicator function. We adopt the operator splitting strategy, and the optimization can be formulated as:
FT w) f(x) - f(w) + [ + [well>)
(13)
We apply Mirror Descent algorithm with Bregman divergence D2 y) to solve this problem, whose update takes the form of:
x (k+1) arg min Vf(x) π + pDs (T.W(())
relh
(14)
((+1) arg min V f()) w pDs (w))(
well,
Let's take the MD update of ग as an example. Taking relative entropy as o(x) = E. xe log vi. solve y (k+1) (conducting steps ① to 33) with exact analytical solutions. Specifically, VΦ(x) = (1 + log x;). and the update w.r.t. i writes:
(k+1)] arg min D DT (k+1))), where log(y (k+1) (o)( v mell
(15)
- arg min (T( (r y (*+1))), where (k+1) (h) exp( vf(w()))))
nell,
Furthermore, under this setting, we also have an exact solution of the projection step arg min,en, DT(T,, T, ()+ diag(p1./y(5 (1+11) (b++) Then the MD update procedure can be formulated according to Prop. as follows:
(k+1] (k) exp( (/(w()))p)) ((+1) diag(p1./m(k*t)) (
(16)
Furthermore, the sub-gradient of our FGW optimizing objective w.r.f. π is calculated as follows:
(s(=) = V FGW G2) = (1 a - 44
(17)
Taking 17 into T6 we have the update of n, similar procedure conducted for w. Setting p to 1/7, the final update procedure is shown in Line 8- 6-11 in Alg
16

---

B Proofs of Theoretical Results
B.1 Proof of Proposition
1
Proof.
From Corollary 4.6 of 159 we have: for any Sinkhorn iteration optimizing π E (1, v) on
two different marginals alternately u, let 11 inf 2 0: H( 1 1, when iterations
t 2 2
C7 C H (m. R) (t
H (P2 pb) + H (M p2t) S 10
[Lt/2] -t1]t
C V H (T. |R) C₁) = (
(18)
H (T22 | T.) + H (T.
T22
I 5
([t/2] +t)t
where Cj is a constant, and R is fixed reference measure.
B.2 Proof of Proposition 2
Definition 2 (Bounded Linear Regularity, Definition 5.6 in (60) Let C1 C2. Ox be closed
convex subsets of IK" with a non-empty intersection C. We call the set {Ci, C2. ... On } is bounded
linearly regular for every bounded subset B of IR" there exists constant K > 0 such that
max d(x, C:), Yx B, where d(x, C) d(z, C) S ie(1.....N
min x x' ||. x' EC
The BLR condition naturally holds if all the C2 are polyhedral sets. Definition 3 (Strong Convexity). A differentiable function f() is strongly convex with the constant m, if the following inequality holds for all points v. y in its domain:
(vf(x) ff())) (x v) m|x y11?.
where |I-Il is the corresponding norm.
In Mirror Descent algorithm, the Bregman divergence (Ix y) requires to be strongly convex.
Proof. Recall that the fixed point set of relaxed FGW is Xret { E Cl,w* E C2 0 ff(**) (p(a"))p(Vh()))) (VV(((")) Vh(TT))+NN, (T*), and 0 E Vf(w") ) + p (Vh(T=* - vh(w")) +No,(w))) Let p E No, (I²) and q No. (w*), Meet is denoted as:
Xret (x* Cn,w* E C2 f + p(Vh(w") Vh(T')) (1(TT"))+p +p= No,, (T") v)(W"))+ + 0, E ENc
(w")} (N, (19)
+(w"))+(VVin
We denote * = Projc, nc, (r*). According to Definition 2 as C1 and C2 are both polyhedral constraints and satisfy the BLR condition, we have:
A x || + || w' || - 2 a x"' || - w'll
( C (C)) + -
w'll
(20)
< (2x + ||
The first inequality holds based on the triangle inequality of the norm distances, and the second inequality holds based on the definition of point-to-space distance in Def Moreover, according to the definition of Xret, for any (TT", ,==" E Xyat, we have:
(l (# T²) + p (x=" (w()))) (# - --m") + TT (+- - (+- = -0p (x') Vf ( --) (Vh (h())) (R - w*) T (# w²) 0, No. (w*) (21)
Summing up the equations above, we have:
Vf(W') (f-W) (h()))) (w- m²) + PT (4- m²) + (# w*)
(s(W') (+-=*)+++ + (+') (
(FhWe)) + Da (w', ("), + PT (# - (-- + g (# w²) =0
(22)
17

---

The (a) equation holds based on the definition of Bregman Divergence DA (z, v) := h(z) - h(y)
(Vh(y). x y). Furthermore, due the property of normal cones Nc. (α*), N. (w"), we have
P (क )) I VT E C1 and q (w w") S O, Ve C2. Taking иT and w as C₁ n C2 we have p (ft x²) +9 (ft w²) S O. Therefore, from 22 we have the following inequality:
vf (w") (f - π²) + VJ ( (+ - w-) - p (Dn (T","""",, ==) Dr (w"))")) 20
p (Dn ,²' + Dr (w Vf (w0) (R --)=-))==- x²) (f(" (ft -w)
II (w" I|l - xt + | ( (= -
(23)
Cy(1 -- + || wI
C2(2k 1|] w0|l
-
The (b) inequality holds the optimization objective is quadratic function with bounded constraints, which means the gradient norm has a natural constant upper bound Cy. For the left hand side of the inequality above, the sum of Bregman divergences is also lower bounded by
Dr (T" _-" Dn (w", nT") ) = (Vh (T*) - Vh (w²)) (T - w²) 2 o||TT - w' (24)
as h()) is o-strongly convex in the definition of Bregman Divergence. Therefore, combining (24 and
23
we have:
| - --'l- C2 +
(25)
op
Based on this important result, we analyze the distance between X' and Xyst, which is given by x +w"
2 - x² E Cl,w* E Cz. By adding up the two equations in 19 depicting the conditions x² and w" of Xrels we have:
dist( 2 .) == mingex
π + w
p -0
+
)
(26)
2
2
The (c) derivation holds due to the linear property of the subgradient of FGW w.r.t. π (see Invoking this equality, we present the following uppper bound analysis on dist( x t't"""" x)):
Eq
17
dist π
w²
(d)
c
n² w=
projerns
π
w
Vg
" + w
2
2
(e)
+ w"
π + w² +q
projancs
2
2
(f)
projer (m + p) + proje, (wi + q) 22 projcinc
π + w + q
2
(g) Me
|| w'll,
2
(27)
The (d) inequality comes from the Luo-Tseng error bound condition 66] and Prop.3.1 in 22 The
(e) holds based on Eq 26 The (ʃ) equality holds based on the property of the normal cone, which
is Proie(1 + =) x, Ve E C E (or The (g) inequality holds by invoking Lemma 3.2 in
[29]. which tells |lprojc, (ar) + proje, (v) 2 proicc att < M [|proic, (x)) projo, (v)
Finally, combining (25) and 27 we can obtain the desired result, i.c.,
T" +
(2x 1)cC,M T/P
V(π" ,w" E Xrat, dist(
2)
(28)
2
20p
where 7 := 1)eC M
is constant.
25
C Complete Mixup Procedure
We provide the complete mixup procedure of our method in Algorithm 3 We conduct augmentation only the training set, and mixup graphs from every pair of classes. For specific mixup of two
18

---

Datasets
graphs
avg nodes
med nodes
avg edges
med edges
feat dim
classes
PROTEINS
1113
39.05
26
72.82
98
3
NCII
4110
29.76
27
32.30
58
37
2
NCI109
4127
29.57
26
32.13
58
38
IMDB-B
1000
19.77
17
193.06
260
N/A
2
IMDB-M
1500
13.00
10
131.87
144
N/A
Table 6: Detailed statisties of experimented datasets.
graphs, we apply our proposed algorithm (GWMixup(.) (Alg to obtain the synthetic mixup graph ú= (iz, X, A). However, the numerical solution does not ensure discrete adjacency matrix A. Thus, we adopt thresholding strategy to discretize A, setting entries below and above the threshold to and 1, respectively. The threshold linearly searched between the maximum and minimum entries A, aiming to minimize the density difference between the mixup graph and the original graphs. The mixup graphs added to the training set for augmentation, and the training, validating and testing procedures follow the traditional paradigms.
Algorithm 3 The whole mixup procedure
Input: Training set G {(G,, 9:) mixup ratio |
2: Output: Augmented training set G
3: = -G]. NN = {
G
4: for * j in range (N do
5: for in range , - 1)) do
6: Randomly sample G; (M4 X,, A,) from class y, and G, xj, from y/
7:
Generate new mixup graph and its label G, j FGNMixup(. Gj). G (, Search the threshold 0 to discretize Á: < {1 if o:j 2 0 else Oji which minimizes the density differences between Á and A A2.
8:
9:
Ç G-ğu (G)
end for
11: end for
return
D Experimental Settings
D.1 Dataset Information
(IMDB-B) and IMDE-MULTI (IMDB-M) are the five benchmark graph classification datasets used in experiments. When preprocessing the datasets, remove all the isolated nodes (i.e., O-degree nodes) in order to avoid invalid empty message passing of MPNNs. We present the detailed statistics of the preprocessed datasets in Table [6, including the number of graphs, the average/median node numbers, the average/median edge numbers, the dimension of node features, and the number of classes.
PROTEINS, NCII, NCI109,
D.2 Backbones
We adopt two categories of GNN frameworks as the backbones. The first category is the virtual-node- enhanced Message Passing Neural Networks (MPNNs), including vGCN and vGIN. The second category is the Graph Transformer-basee networks, including Graphormer and GraphormerGD. The details of these GNN layers are listed follows:
vGCN 1 Graph Convolution Network is developed from the spectral GNNs with 1-order approximation of Chebychev polynomial expansion. The update features can regarded as message passing procedure. The graph convolution operator of each layer in the vGCN is
19

---

defined as: X = σr (x()), where Á is the renormalized adjacency matrix, and W is the learnable parameters, We apply ReLU as the activation function (-)).
vGIN [2]: Graph Isomorphism Network takes the idea from the Weisfeiler-Lehman kemnel, and define the feature update of each layer through explicit message passing procedure. The GIN layer takes the form of: 2, (++1) = MLP(++)
In + EmEN(c) Ta where e is e(+ (1+
learnable scalar. We apply two-layer MLP with ReLU activation in implementation.
Graphormer [39] Graphormer adopts the idea of the Transformer [62 architecture, which designs a multi-hean global QK V-atteention across all graph nodes, and encode graph topologies as positional encodings (spatial encoding in Graphormers). A Graphormer layer conducts feature updating as follows:
A h
x (x)) softmax X W
(x"
(X
W
2! (D)
x (1)
X +
WWW ( X
( x GELU
X ( W
where (6-) is the spatial encoding module implemented as embedding tables, and D is the shortest path distance of the graph. A is the attention matrix.
GraphormerGD [6] GraphormerGD is an enhanced version of Graphormer, where the graph topologies are encoded with a General Distance metric defined by the combination of the shortest path distance (SPD) and the resistance distance 63 (RD). It mainly modifies the calculation of the attention matrix in Graphormer:
(x()
P1 (Dap: D,) @ softmax (x
whh
(")
W
I. (Dpp. D,))
+ +02
where 6(-) is an MLP taking SPD embedding and RD gaussian kernel embedding as inputs.
For all the backbones, we apply the virtual node READOUT approach (which the official READ- OUT function of Graphormers) instead of traditional global pooling. We apply 6 network layers and take 64 as the hidden dimension for all the backbones on all datasets. GraphormerGD has specical model design on PROTEINS dataset, which applies 5 layers and 32 as the hidden dimension due to the GPU memory limitation.
D.3 Experimental Environment
The experiments in this work are conducted two machines: one with 8 Nvidia RTX3090 GPUs and Intel Xeon E5-2680 CPUs, one with Nvidia RTX8000 GPUs and Intel Xeon Gold 6230 CPUs.
Hardware Environment
Software Environment Our experiments are implemented with Python 3.9, PyTorch 1.11.0, Deep Graph Library (DGL) 44 1.0.2, and Python Optimal Transport (POT) [45) 0.8.2. The implementation of all the backbone layers are based on their DGL implementations. For the FGW solver, FGWMixup uses the official FGW distance solver implemented POT, and FGWMixup. uses the accelerated FGW algorithm implemented on our own.
D.4 Implementation Details
For our mixup algorithm FGWMixup. we follow B1 and apply the Euclidean distance as the metric measuring the distance of the node features and the graph adjacency matrix the structural distances between nodes. We sample the mixup weight from the distribution (0.2, 0.2) and the trade-off coefficient of the structure and signal costs a are tuned in (0.05, 0.5, 0.95]. We set the size of the generated mixup graphs as the weighted average the source graphs, which The maximum number of iterations of FGWMi xupis set to 200 for the outer loop optimizing X and A, and 300 for the inner loop optimizing couplings л. The stopping criteria of our algorithm are the relative update of the optimization objective reaching below a threshold, which is set to 5e-4. For
An + (1 -))rg-
20

---

FGWMixup.. we select the step size of MD from (0.1, 1. 10). The mixup ratio (i.e., the proportion of mixup samples the original training samples) is set 0.25.
For the training of GNNs, MPNNs are trained for 400 epochs and Graphormers are trained for 300 epochs, both using A optimizer with weight decay rate of Se-4. The batch size of GNNs are chosen from (32. 128), and the learning rate is chosen from [1e-3, 5e-4, le-4), ). Dropout is employed with a fixed dropout rate 0.5 to prevent overfitting. All the hyperparameters are fine-tuned by grid search on validation sets. For a fair comparison, we employ the same set of hyperparameter configurations for all data augmentation methods in each backbone architecture. For more details, please check our code published online at https: //tptttt.tt.t////// com/ Awt.hrrLeoo//GGHW.....
E
Further Experimental Analyses
E.1 Qualitative Analyses
We present two mixup examples of FGWMixup in Figure 4 to demonstrate that augmented graphs by FGWMixup can preserve key topologies of the original graphs and have semantically meaningful node features simultaneously. In Example 1, we can observe that the mixup graph adopts an overall trident structure and a substructure (marked green) from G and adopts several substructures from G2 (marked red), finally formulating new graph sample combined properties from both graphs. In Example 2, we can observe that the mixup graph quite similar to G2, but breaks the connection of two marked (red arrow pointed) edges and formulates two disconnected subgraphs, which is identical to the overall structure G Moreover, in both examples, we can observe that the preserved substructures not only topologically alike, but also highly consistent in node features. The two examples demonstrate that FGWMixup can both preserve key topologies and generate semantically meaningful node features.
Figure 4: Two examples of FGWMixup. In each example, the subfigures on the left and middle are the original graphs be mixed up, denoted G1 and G2, respectively. The subtitle denotes the mixup ratio X. The subfigure on the right is the synthetic mixup graph. The node features are one-hot encoded and distinguished with the feature ID and corresponding color.
Example
(c)
(b)
(b)
(a)
(a)
G
G2
Example
5
G
21

---

E.2 Further Discussions on G-Mixup
In this subsection, we conduct further analyses on G-Mixup for a better understanding of its differences from our methods.
G-Mixup with GW Graphon Estimator G-Mixup does not originally apply GW metrics to estimate the graphons (as they introduce in Table and 6 in their paper [20]). In our implementation. we select the USVT method as the graphon estimator for G-Mixup. Yet it is also practical to apply GW metric to estimate graphons as ablation study. Here, we also provide the experimental results of G-Mixup+GW and G-Mixup+GW (GW with our single-loop solver) on PROTEINS as shown in 7
Backbone
G-Mixup
G-Mixup+GW
G-Mixup+GW
FGWMixup
vGIN
74.84(2.99)
74.48(2.54) 74.57(3.18)
74.03(4.46)
75.02(3.86)
vGCN
74.57(2.88)
74.84(2.15)
76.01(3.19)
Table 7:
Experimental results of different graphon estimators of G-Mixup on PROTEINS.
No matter what metrics are applied for the graphon estimation, we want emphasize that G-Mixup does not model the joint distribution of graph structure and signal spaces, but regards them as two disentangled and independent factors. However, our main contribution and the greatest advantage compared with G-Mixup comes from the joint modeling of graph structure and signal spaces. This also explains why FGWMixup can outperform.
Extend G-Mixup with FGW-based Attributed Graphon Estimator In 664] Xu et al. introduce an attributed graphon estimation algorithm, which makes us naturally think of an extended version of G-Mixup. With the attributed graphon, G-Mixup can also consider the joint modeling problem. Though is not the contribution and the core idea from G-Mixup to address our proposed joint modeling problem, g-Mixup. Hence, we conduct experiments with the extended version of G-Mixup using FGW as the attributed graphon estimator (denoted as G-Mixup+FGW) on PROTEINS and NCII datasets, and the results are shown in Table g
also interested in whether this extension improve the performance of
Dataset
Backbone
G-Mixup
G-Mixup+FGW
FGWMixup
vGIN
74.84(2.99)
74.66(3.51)
75.02(3.86)
PROTEINS
vGCN
72.57(2.88)
74.30(2.85)
76.01(3.19)
vGIN
77.79(1.89 76.42(1.79)
78.18(1.73)
78.37(2.40) 78.32(2.65)
NCI1
vGCN
75.91(1.54)
Table 8: Experimental results of G-Mixup extended with FGW attributed graphon estimator on PROTEINS and NCII.
We can observe that FGW does not significantly improve the performance of G-Mixup and still cannot outperform our methods. The main reason lies in that the node matching problem remains unsolved using the linear interpolation strategy two graphons introduced in G-Mixup. Though the intra-class node matching has been done with FGW graphon estimation, the graphons of different classes not ensured with an aligned node distribution, which requires the inter-class node matching for an appropriate mixup. This the core reason for the limited performance of G-Mixup series methods.
E.3 Algorithm Efficiency
In this subsection, we provide additional details regarding the runtime efficiency analyses.
Further Comparisons between FGWMixup and FGWMixup. Table 9 presents the average time spent on single iteration of update (i.e, FGW solver convergence) and the average iterations taken for updating X and A until convergence. We can observe that the convergence of a single FGW procedure does not appear to be significantly accelerated. This is because the gradient step
22

---

has been taken twice for an alternating projection process, which incurs double time for the gradient calculation (with complexity of O(n"). ) the graph size). In contrast, the strict solver only takes one gradient step for each projection. Therefore, despite a faster convergence rate of the relaxed FGW, the extra gradient step makes the overall convergence time of the relaxed FGW solver similar to that of the strict FGW solver. However, notable improvement is observed in the convergence rate of the outer loop responsible for updating X and A, resulting from the larger step π that the relaxed FGW provides, as shown in Prop | Considering the two factors above, the overall mixup time has been efficiently decreased by up 3.46 x with FGWMixup..
Single FGW Iter. Time (s) FGWMixup
Avg. Outer Loop Converge Iter. (#) FGWMixup.
Dataset
FGWMixup.
FGWMixup
Speedup
PROTEINS
0.0181
0.0225
80.64
153.69
1.91
NCI1
0.0140
0.0120
54.25
170.23
3.14x
NC
0.0136
0.0123
53.12
169.98
3.20x
IMDB-B
0.0162
0.0119
20.03
95.48
4.77x
IMDB-M
0.0081
0.0060
14.26
60.91
4.27
Table 9: More algorithm execution efficiency details of FGWMixup and FCWMixup..
Comparisons between Our Methods and Compared Baselines We present the averaged ef- ficiencies of different mixup methods and time spent on training vanilla backbones of each fold on PROTEINS and NCI1 datasets in Table IO] As the efficiency of G-Mixup hugely relies on the graphon estimation approach, we also include G-Mixup with GW graphon estimators (denoted as G-Mixup+GW) in the table.
We can observe that our methods and G-Mixup+GW are slower than the other data augmentation methods. The main reason is that the complexity of calculating (F)GW distances between two graphs cubic (Omm?² + nm 28). where m., are the sizes of graphs. Moreover, when calculating barycenters, we need an outer loop with T iterations and M graphs. In total, the time complexity of mixing up two graphs of size is ((MTn²). FGWMi xup, boosts the efficiency by enhancing the convergence rate and reducing the required iterations T (see Table for more details), whereas G-Mixup+GW will have to go over the whole dataset to calculate graphons, which much more time-consuming than FGWMixup.
However, sacrificing complexity to pursue higher performance has been the recent trend of technical development, c.g. GPT-4. Morcover, we believe that the current time complexity of FGWMixup, is still acceptable compared with performance improvements, most compared graph augmentation methods cannot effectively enhance the model performance as shown in Table
More importantly, in practice, the main computational bottleneck of (F)G based method is the OT network flow CPU solver in the current implementation based on the most widely used POT lib. In other words, GPU-based network flow algorithms have not been applied in current computation frameworks. Moreover, mini-batch parallelization
not yet deployed works (65] from NVIDIA have focused on accelerating network flow algorithms on GPU, which may probably be equipped on CUDA and allow a huge acceleration for GW solvers in the near future. Hence, we firmly believe that the fact that our method is not yet optimized in parallel GPUs is only a temporary problem. Just as some other works (c.g.. MLP, LSTM, etc.) that have brought enormous contributions in the past era, they initially slow when proposed, but have become efficient with fast-following hardware supports.
POT. However, recent
Dataset
DropEdge
DropNode
G-Mixup
ilMixup
G-Mixup+GW
FGWMixup
FGWMixup.
PROTEINS
0.192
0.229
6.34
2.08
2523.78 9657.48
802.24 1711.45
394.57
NCI1
0.736
0.810
10.31
5.67
637.41
Table 10: Average mixup efficiency (clock time spent, seconds) of all compared baselines on each fold of PROTEINS and NC11 datasets.
23

---

E.4
Sensitivity Analysis on Varying Beta Distribution Parameter &
We empirically follow the setting in 24 select the beta distribution parameter 0.2 where the mixup method is first proposed. We also provide the sensitivity analysis of the Beta distribution parameter l on PROTEINS and NCII datasets in Table I1
Methods
PROTEINS
NCII
k=0.2
k=0.5
k=1.0
k=2.5
1=0022
1=00.5
k=1.0
k=2.5
GGNN-GGMixup
75.02(3.88)
75.02(2.67)
74.93(2.93)
74.3%(107)
78.32(2.65)
76.37(2.00)
76.59(2.39)
77.71(2067)
VGCN PоWM
76.01(3.19)
75.47(.12)
75.95(2.58)
74.30(4.1))
78.37(2.40)
78.0011.40)
77.96(1.73) 77.98(1.50)
KGIN-FGRNarup.
75.20(3.30)
73.59(2.38)
76.10:2.97) 73.86(2.81)
71.27(2.71)
77.25(2.09)
77.32(1.78)
77.01(2.14)
vGCN-FGWHixup.
75.20(3.03)
74.29(4.62)
75.38(3.41)
74.21(4.52)
78.47(174)
78.71(1.49)
78.10(1.71)
77.96(1.02
Table 11: Experimental results of different on PROTEINS and NCT1 datasets.
From the results, we can find that (eta 0.2) is the overall best-performed setting. There are also a few circumstances where the other settings outperform. In our opinion, different datasets and backbones prefer different optimal settings of k. However, we should choose the one that is overall the best across various settings.
E,5 Experiments on OGB Datasets
We also conduct experiments on several OGB benchmark datasets (6). including ogbg-molhiv and ogbg-molbace, We conduct binary classification (molecular property prediction) on these datasets with AUROC (Area Under Receiver Operating Characteristic) as the reported metric. The split of training, validating, and testing datasets are provided by the OGB benchmark. In spite of the existence of edge features in OGB datasets, in this work, both of our GNN backbones and augmentation methods do not encode or consider the edge features. dimensions) the backbones and train the models five times with different random seeds, and we report the average and standard deviation of AUROCS as the results. The dataset information and predicting performances listed in Table 12
select vGCN and vGIN (5 layers and 256 hidden
From the table, we can observe evident improvements on both datasets and backbones with our methods. FGWMixup, obtains the best performance on relative improvements on vGCN and vGIN respectively, and FGWMixup obtains the best on ogbg- molbace dataset with 1.14% and 8.86% relative improvements. Meanwhile, our methods provide much more stable model performance where we reduce the variance by a significant margin, which demonstrates that our methods can resist the potential noises underlying the data and increase the robustness of GNNs. These additional experimental results further indicate the effectiveness of our methods in improving the performance of GNNs in terms of their generalizability and robustness.
dataset, with 2.69% and 3.46%
24

---

Stats
ogbg-molhiv
ogbg-molbace
Graphs
41,127
1,513
Avg. Nodes
25.5
34.1
Avg. Edges
27.5
36.9
Feature Dim.
Backbones
Methods
ogbg-molhiv
ogbg-molbace
vanilla
73.72(2.45)
76.62(4.59)
DropEdge
74.07(2.68)
75.31(4.57)
vGCN
G-Mixup
74.65(1.42)
69.80(6.41)
FGWMixup
75.24(2.78)
77.49(2.11)
FGWMi xup+
75.70(1.15)
76.40(2.45)
vanilla
72.61(1.01)
69.77(1.33)
DropEdge
72.97(1.61)
72.68(4.92)
VGIN
G-Mixup
74.52(1.58)
73.74(7.07)
FGWMixup
72.68(1.47)
75.95(2.42)
FGWMixup.
75.12(1.02)
74.02(2.18)
Table 12: Statistics and experimental results on OGB benchmark datasets. The reported metrics are AUROCs taking the form of (stdde.)).....
25


Reviews:
[{"review_id": "ru2o0eUgCp", "reviewer": "Reviewer_Cjiv", "summary": "In this paper, the authors study a new method \"FGWMixup\" for graph data augmentation. \n\nFor the two input graphs $G_1, G_2$, they propose to construct a synthetic graph $\\tilde G$ through optimizing the weighted distance sum (2). To further improve the efficiency of the algorithm, they relax the polytope constraint (row sum and column sum meet the source and target distribution) on the transport matrix $\\pi$, to two alternatively enforced constraints (separately on row sum and column sum); they summarize the new solver in Algorithm 2.\n\nThey also study the performance of the proposed method/solver through empirical experiments.", "questions": "1. In solving (2), they \"fix the node probability distribution of $\\tilde G$ with a uniform distribution\" (Line 129). It makes sense, while it can be better to add more justification, either empirically or theoretically.\n2. The concept of “Bregman projection” in Line 164, 171 is not well explained.\n3. The statement of Proposition 1 is confusing. \n        - \"Let $\\pi_t$ be the Sinkhorn iterations\" is unclear. What's the relationship between $\\pi_t$ and the following $\\pi_{2t}, \\pi_{2t+1}$?\n        - \"Let $\\pi^*$ be the unique optimal solution\" needs more explanation, optimal w.r.t. what? \n        - What's the definition of $\\mu_t, \\nu_t$?\n        - Does the proposition mean the new solver may not converge to $\\pi^*$?\n4. The statement of Proposition 2 is also confusing. \n        - The concept of “FGW function” is not defined.\n        - The concept of “normal cone” is not well explained.\n        - Actually the follow-up remark after Prop 2 is not very informative. Please provide more details and explain why the distance bound implies FGWMixup∗ \"will converge close to the ideal optimum\". What's the scale of $\\tau/\\rho$?\n5. The experiments only involve small datasets. Can the authors add some medium to large datasets, and also report the runtime of different mixup methods?", "limitations": "N/A.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- originality: \n    - While the rough idea to use OT for data augmentation is regular, this paper proposes a different solution and a new relaxed FGW solver, which is novel to me.\n\n- quality:\n    - The new method/solver they propose does work and can provide comparable performance to existing mixup methods.\n\n- significance: \n    - This paper provides a OT-based mixup method, which can be a good reference for self-supervised learning on graph.", "weaknesses": "- quality\n    - Some empirical results may be unconvincing due to the small size of datasets. I leave a related comment below.\n\n- clarity: \n    - Some concepts are not clearly illustrated. See the questions below. With the unclear illustration, the theoretical justifications for some claims are hard to follow.\n\n- significance: \n    - Even with the new approximate solver, I doubt the new FGWmixup is much slower than previous mixup methods, which can make the work less attractive to practitioners.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your comments and suggestions. We made every effort to address all the concerns. In the following, we quote your comments and then give our detailed response point-by-point. The references given in numbers correspond to the reference id in our paper, and those given in letters are provided at the end of our response.\n\n> **Q1. Justification on the uniform distribution selection of $\\tilde{G}$:**\n\nIn most cases where we have no prior knowledge of the node importance, works [a, 24] empirically choose a uniform distribution of $\\mu$. There are also some works [51, 52, 54] adaptively optimize it, which incorporate another degree of freedom to the model. Both approaches are reasonable and practical. In our current version, we choose the former one, and we find that FGWMixup has already outperformed SOTA methods with a fixed uniform distribution of $\\mu$. Considering that this design does not influence the core contribution of our method and the pages are limited, we have not explored the adaptive $\\mu$ version of FGWMixup in our current paper. We regard this as our future work. We will add more explanations and references of this design to the paper for better justification.\n\n> **Q2: The concept of \"Bregman Projection\":**\n\nWe have introduced the Bregman projection $\\phi$ is in Appendix A.2 Proposition 3. Specifically, Bregman projection is a function $\\phi()$ used to calculate the Bregman divergence $D_\\phi(x,y)$. More concretely, in the Mirror Descent algorithm, due to the geometry constraint of the feasible set $\\mathcal{X}$, we aim to map $x$ to the dual space and take a gradient step there, thence mapping it back to the primal space (illustrated in Fig.3 in Appendix A.2). The dual space is precisely produced by this Bregman projection, which maps the primal space with $\\nabla \\phi()$.\n\n> **Q3: Confusions about Proposition 1 - Definition of notations and meaning of the proposition:**\n\nSorry for the confusion. We clarify the questions as follows: \n1) *What's the relationship between $\\pi_t$ and $\\pi_{2t}, \\pi_{2t+1}$?* $\\\\{ \\pi_t \\\\}$ is the sequence of $\\pi$ generated from each update step $t$ of Sinkhorn iterations. At the even number steps ($2t$), we optimize the first marginal $\\mu$, and at the odd number steps ($2t+1)$, we optimize the second marginal $\\nu$. This is precisely the alternately updating procedure in Alg.2. \n2) *What is $\\\\pi^{\\*}$ optimal w.r.t?* $\\pi^*$ is the optimal solution of the FGW distance, which can also be regarded as a function of $\\pi$ (i.e., $f(\\pi)$), as shown in Appendix A.1. \n3) *What is the definition of $(\\mu_t, \\nu_t)$?* As we mentioned in Prop.1, $\\pi \\in \\Pi(\\mu, \\nu)$. Analogously, $(\\mu_t, \\nu_t)$ is the marginals of $\\pi_t$. \n4) *The meaning of the proposition?* This proposition demonstrates a faster convergence rate of the single-loop solver. Specifically, the divergences between the optimized marginals $\\mu_t, \\nu_t$ and the objective marginals $\\mu, \\nu$ descend quadratically as iteration $t$ goes  ($O(t^{-2})$), which is optimized by the single loop solver. Yet the divergence of strict solver over the joint distribution $\\pi$ goes linearly ($O(t^{-1})$).\n\n> **Q4: Confusions about Proposition 2 - Definition of concepts, meaning of the proposition, and the scale of the upper bound:**\n\nSorry for the confusion. The explanations are as follows:\n1) *What does the FGW function refer to?*  The FGW function is introduced in Eq.(1), and it can be regarded as a function of $\\pi$ ($f(\\pi)$). We have introduced this in Appendix A.1.\n2) *The definition of \"normal cone\"?* The concept of the normal cone is introduced in Definition 1 in Appendix A.2. \n3) *What is the scale of $\\tau/\\rho$ and why will our algorithm \"converge close to the ideal optimum\"?* Prop.2 gives an upper bound ($\\tau/\\rho$) of the distance between the optima given by our relaxed solver and the ideal optimum. In fact, as we introduced in L.557 and L.177, the entropic regularization coefficient $\\rho$ is actually equivalent to $1/\\gamma$, where $\\gamma$ is the step size of MD update. $\\tau$ is a fixed constant given by various factors (see Appendix B.2). Noted that the step size of MD can be arbitrarily adjusted, **when we select a step size as small as possible, the scale of the upper bound $\\tau/\\rho$ will be sufficiently small**. This proves that FGWMixup* can converge to the ideal optimum.\n\n> **Q5: Requirements of larger datasets and runtime of different mixup methods:**\n\n1) This paper focuses on data augmentation, which mainly tackles circumstances of data insufficiency. Therefore, it is more persuasive to observe results on small datasets. Furthermore, in former works [17, 18], datasets from TUDataset are widely adopted as the benchmark. Hence, we follow their settings and present the results on those datasets as the main results. However, we also have considered validating the effectiveness of our method on larger datasets, and **we have reported experimental results on large OGB datasets with 40K+ samples (see Appendix E.2)** and our methods also outperform all baselines.\n\n2) We present the runtime analysis of different methods in the public response. Please refer to our explanations in **Q1** of the **public response** for details.\n\n[a] Xu Hongteng, et al. Representing graphs via Gromov-Wasserstein factorization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 45(1): 999-1016.\n"}, {"review_id": "0vHX00Qk9M", "reviewer": "Reviewer_JSkL", "summary": "This paper addresses a gap in graph data augmentation for graph-level classifications, where existing methods mainly focus on augmenting graph signal space and graph structure space separately, overlooking their mutual interactions. The authors formulate the issue as an optimal transport problem that considers both graph structures and signals, and propose a novel graph mixup algorithm called FGWMixup. FGWMixup seeks the \"midpoint\" of source graphs in the Fused Gromov-Wasserstein (FGW) metric space. The authors further introduce a relaxed FGW solver to improve the scalability and performance of FGWMixup, and experimental results across five datasets and various GNN backbones demonstrate its effectiveness in enhancing the generalizability and robustness of GNNs.", "questions": "Q1. The algorithm may sacrifice some feasibility due to the relaxed projection. Can you provide some potential effects?  \nQ2. How does the computational complexity of FGWMixup compare to other graph mixup methods?", "limitations": "The paper does not explicitly address the potential limitation of the proposed approach. The authors can test their method on node classification or link prediction tasks.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. Innovation in Graph Mixup Method: The paper introduces FGWMixup, a novel graph mixup method that is formulated as an optimal transport problem. This innovative approach aims to find the optimal graph at the \"midpoint\" of two source graphs in terms of both graph signals and structures. This unique formulation could potentially provide a more effective way to combine graphs compared to traditional methods.  \nS2. Comprehensive Evaluation: The paper comprehensively evaluates the proposed method on five widely-used graph classification tasks from the graph benchmark dataset. The use of four different types of backbones for the evaluation further demonstrates the versatility and robustness of the FGWMixup method. This extensive evaluation provides strong evidence of the effectiveness of the proposed method across various tasks and settings.  \nS3. Theoretical Analysis and Optimization: The paper provides a thorough theoretical analysis of the proposed FGWMixup method, including the convergence of the algorithm and the correctness of FGWMixup. This rigorous theoretical foundation strengthens the credibility of the proposed method. Additionally, using an algorithm to optimize the computation complexity is a commendable effort to address potential efficiency concerns.", "weaknesses": "W1. High Time Complexity: The proposed FGWMixup and Accelerated FGWMixup methods have a relatively high time complexity. This could limit their applicability in scenarios where computational resources or time are constrained. The paper would benefit from a more detailed analysis of the time complexity of these methods, including how it scales with the size and complexity of the input graphs.  \nW2. Lack of Results for Varying Beta Distribution Parameter: The paper needs results showing the impact of changing the beta distribution parameter 'k' on the performance of the proposed methods. This parameter could significantly influence the distribution, and it would be informative to understand how its variation affects the results. This could also provide insights into how to choose the best 'k' for different scenarios.  \nW3. Effects of Relaxed Projection: The paper could provide more discussion about the potential negative effects due to the relaxed projection. While this approach may improve the algorithm's efficiency, it could also introduce inaccuracies or instability in the results. A deeper exploration of these trade-offs would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your comments and suggestions. We made every effort to address all the concerns. In the following, we quote your comments and then give our detailed response point-by-point.\n\n> **W1/Q2. Analysis and comparisons of computational complexity:**\n\nWe provide runtime comparisons between our methods and compared baselines as well as the computation complexity analysis in the public response. Please check **Q1** in the **public response** for details.\n\n> **W2. Sensitivity analysis on varying beta distribution parameter $k$:**\n\nEmpirically, we follow the $k$ setting in [a] where the mixup method is first proposed. We also provide the sensitivity analysis of the Beta distribution parameter $k$ on PROTEINS and NCI1 datasets as follows:\n\nResults on PROTEINS:\n|  k   | GIN (FGWMixup) | GCN (FGWMixup)| GIN (FGWMixup*)| GCN (FGWMixup*)|\n|-----|----------------|----------------|----------------|-----------------|\n| 0.2 | **0.7502(0.0386)** | **0.7601(0.0319)** | 0.7520(0.0330) | 0.7520(0.0303)  |\n| 0.5 | **0.7502(0.0267)** | 0.7547(0.0312) | 0.7359(0.0238) | 0.7429(0.0462)  |\n| 1.0 | 0.7493(0.0293) | 0.7565(0.0258) | 0.7386(0.0281) | **0.7538(0.0341)** |\n| 2.5 | 0.7439(0.0107) | 0.7430(0.0412) | **0.7610(0.0297)** | 0.7421(0.0452)  |\n\nResults on NCI1:\n|  k   | GIN (FGWMixup)| GCN (FGWMixup)| GIN (FGWMixup*)| GCN (FGWMixup*)|\n|-----|----------------|----------------|----------------|-----------------|\n| 0.2 | **0.7832(0.0265)** | **0.7837(0.0240)** | 0.7727(0.0271) | 0.7847(0.0174)  |\n| 0.5 | 0.7637(0.0206) | 0.7800(0.0140) | 0.7725(0.0209) | **0.7871(0.0149)**  |\n| 1.0 | 0.7659(0.0239) | 0.7798(0.0150) | **0.7732(0.0178)** | 0.7810(0.0171)  |\n| 2.5 | 0.7771(0.0267) | 0.7796(0.0173) | 0.7701(0.0214) | 0.7796(0.0102)  |\n\nFrom the results, we can find that **Beta(0.2, 0.2) is the overall best-performed setting**. There are also a few circumstances where the other settings outperform. In our opinion, different datasets and backbones prefer different optimal settings of $k$, but we should choose the one that is overall the best across various settings.\n\n> **W3/Q1. More exploration of the infeasibility introduced by the relaxed FGW solver:**\n\nFirst of all, we conduct an experiment to analyze how much infeasibility or inaccuracy has been introduced by our single-loop FGW solver compared with the strict CG solver. We randomly select 1,000 pairs of graphs from PROTEINS dataset and apply the two solvers to calculate the FGW distance between each pair of graphs. The distances of the $i$-th pair of graphs calculated by the strict solver and the relaxed solver are denoted as $d_i$ and $d^{\\*}_i$, respectively. We report the following metrics for comparison: i) MAE (mean absolute error of FGW distance, $\\frac{1}{N}\\sum |d_i - d^{\\*}_i|$), ii) MAPE (mean absolute percentage error of FGW distance,  $\\frac{1}{N}\\sum \\frac{|d_i - d^{\\*}_i|}{d_i}$), iii) mean FGW distance given by the single-loop solver ($\\frac{1}{N}\\sum d^{\\*}_i$), iv) mean FGW distance given by the strict CG solver ($\\frac{1}{N}\\sum d_i$), v) L2-norm of the difference between two transportation plan matrices (divided by the size of the matrix for normalization). The results are shown as follows:\n\n| MAE            | MAPE           | mean_FGW | mean_FGW\\* | T_diff          |\n|----------------|----------------|----------|-----------|-----------------|\n| 0.0126(0.0170) | 0.0748(0.1022) | 0.2198   | 0.2143    | 0.0006(0.0010)  |\n\nWe can observe that the MAPE is only 0.0748, which means the FGW distance estimated by the single-loop relaxed solver is only 7.48% different from the strict CG solver. Moreover, the absolute error is around 0.01, which is quite small compared with the absolute value of FGW distances (~0.21). We can also find that the L2-norm of the difference between two transportation plan matrices is only 0.0006, which means two solvers give quite similar transportation plans. All the results imply that **the single-loop solver will not produce huge infeasibility or make the estimation of FGW distance inaccurate**.\n\nFrom another perspective, we do not think the infeasibility brings totally negative effects. As we have analyzed in our experiments (Table 1), FGWMixup* even sometimes performs better than FGWMixup. We explain this with the subtle infeasibilities introduced by the relaxed single-loop solver. By incorporating those infeasibilities, FGWMixup* may be able to **occasionally generate more diverse examples, which potentially enlarge the input space, thus bringing opportunities to improve the generalizability of GNN models.**\n\n\n[a] Zhang Hongyi et al., mixup: Beyond Empirical Risk Minimization, ICLR 2018"}, {"review_id": "Law5lS5aBx", "reviewer": "Reviewer_ZCHq", "summary": "This paper proposes a new graph data augmentation method for graph-level classifications. To address the limitation of existing methods, the authors consider the joint interaction between the graph structure and node features by finding an optimal inter-graph node matching strategy. Furthermore, the authors introduce a relaxed FGW solver to accelerate the proposed method FGWMixup. Experiments show that the FGWMixup outperforms multiple baselines on five datasets using different GNN backbones. ", "questions": "There are multiple hyperparameters in the proposed FGWMixup, ex. $\\alpha$ in equation 1. How to choose the hyperparameters? How sensitive is the performance gain to the hyperparameter tuning?\n\nThe authors provide experiments about the running time between FGWMixup and FGWMixup*. How does FGWMixup compare to the other baselines? Does the improvement of the performance come from a much higher computational cost?\n\n", "limitations": "Yes. The authors have discussed the limitation of their method. ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Overall the paper is well-written and easy to read. \n\nUsing the Fused Gromov-Wasserstein distance metric space seems to be an interesting solution for mixing graphs. \n\nThe authors provide theoretical analysis for accelerating FGWMixup by improving the convergence rate.", "weaknesses": "My major concern is about the claim that most existing graph data augmentation methods only consider one of the graph structure space and node feature space. There exist many graph augmentation methods (adversarial augmentation, local graph augmentation, automated graph augmentation and etc). Many of them change both graph structure and node features to generate augmented graphs. I don't think this work is the only one considering the joint modeling problem. \n\nBesides, the authors claim the importance of the interaction between graph structure space and node features space. I think more explanations/analyses are needed to show that augmented graphs by FGWMixup can preserve key topologies of the original graphs and have semantically meaningful node features simultaneously.\n\nFor the experiments, the improvement of the performance is not significant compared to the high std. I would suggest the authors include experiments on the OGB benchmark(https://ogb.stanford.edu/docs/graphprop/) since the std on OGB is typically small compared to TUDataset. Furthermore, except for some graph mixup methods, the authors only compare with DropEdge and DropNode. It would make the experimental results more convincing if the authors can include some advanced graph data augmentation methods. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your comments and suggestions. We made every effort to address all the concerns. In the following, we quote your comments and then give our detailed response point-by-point.\n\n> **W1. Many existing works change both graph structure and node features to generate augmented graphs. I don't think this work is the only one considering the joint modeling problem.**\n\nWe want to emphasize that **we do NOT claim that existing methods only consider one of the graph structure and the node feature**, but express that **most existing works regard them as two disentangled perspectives and consider the augmentation on the two parts independently (separately)**. This means most works do not consider the effects of node features when generating new graph structures, and vice versa. We provide two examples (G-Mixup, ifMixup) in the Intro, and more are listed in the Related Works. However, as we mentioned in L.45-46 in the Intro, the graph structures and node features are correlated with each other, and it is essential to depict this correlation while generating new graph samples. Hence, we propose to consider the joint modeling problem to enhance the quality of graph augmentation.\n\n> **W2. More explanations/analyses are needed to show that augmented graphs by FGWMixup can preserve key topologies of the original graphs and have semantically meaningful node features simultaneously.**\n\nWe have presented two mixup examples in the attachment PDF file in the **public response**. In Example 1, we can observe that the mixup graph adopts an overall trident structure and a substructure (marked green) from G1, and adopts several substructures from G2 (marked red), finally formulating a new graph sample combined properties from both graphs. In Example 2, we can observe that the mixup graph is quite similar to G2, but breaks the connection of two marked (red arrow pointed) edges and formulates two disconnected subgraphs, which is identical to the overall structure of G1. Moreover, in both examples, we can observe that the preserved substructures are not only topologically alike, but also highly consistent in node features. These examples demonstrate that **FGWMixup can both preserve key topologies and generate semantically meaningful node features**. We will add this analysis to the Appendix of our paper.\n\n> **W3. It would be more convincing to include larger datasets and more data augmentation baselines.**\n\nThis paper focuses on data augmentation, which mainly tackles the circumstances of data insufficiency. Therefore, it is more persuasive to observe results on small datasets. Furthermore, in former works [17, 18], datasets from TUDataset are widely adopted as the benchmark. Hence, we follow their settings and present the results on those datasets as the main results. However, we also have considered validating the effectiveness of our method on larger datasets, and **we have reported experimental results on large OGB datasets with 40K+ samples** (see Appendix E.2) and our methods also outperform all baselines.\n\nFor the compared baselines, we think mixup-based methods are the state-of-the-art of graph augmentation. Former works such as ifMixup and G-Mixup have included some other graph augmentation methods as baselines (e.g., Subgraph, NodeAttrMasking), and have proven their superiority to those methods. Therefore, we think it is sufficiently convincing and persuasive to adopt SOTA mixup methods as the compared baselines.\n\n> **Q1. How to choose the hyperparameters? How sensitive is the performance gain to the hyperparameter tuning?**\n\nAs we introduced in Appendix D.4. L674, the hyperparameters are selected by grid search on validation sets. We have provided the analysis on hyperparameters such as graph sizes and GNN depths in Section 3.3. Here we additionally provide the sensitivity analysis w.r.t. $\\alpha$ valued from {0.05, 0.5, 0.95, 1.0}. Note that $\\alpha =1.0$ falls back to the case of GW metric where node features are not incorporated. \n\nResults on PROTEINS:\n| $\\alpha$ | GIN (FGWMixup) | GCN (FGWMixup) | GIN (FGWMixup*) | GCN (FGWMixup*) |\n|----------|----------------|----------------|-----------------|-----------------|\n| 0.95     | 0.7502(0.0386) | **0.7601(0.0319)** | **0.7520(0.0330)**  | **0.7520(0.0303)** |\n| 0.5      | **0.7538(0.0258)** | 0.7547(0.0356) | 0.7457(0.0330)  | 0.7457(0.0352)  |\n| 0.05     | 0.7486(0.0240) | 0.7493(0.0274) | 0.7439(0.0301)  | 0.7484(0.0316)  |\n| 1.0      | 0.7457(0.0262) | 0.7440(0.0357) | 0.7394(0.0386)  | 0.7466(0.0291)  |\n\nResults on NCI1:\n| $\\alpha$ | GIN (FGWMixup) | GCN (FGWMixup) | GIN (FGWMixup*) | GCN (FGWMixup*) |\n|----------|----------------|----------------|-----------------|-----------------|\n| 0.95     | **0.7832(0.0265)** | **0.7837(0.0240)** | **0.7727(0.0271)**  | 0.7847(0.0174)  |\n| 0.5      | 0.7742(0.0193) | 0.7793(0.0168) | 0.7723(0.0247)  | 0.7766(0.0148)  |\n| 0.05     | 0.7762(0.0237) | 0.7800(0.0100) | 0.7659(0.0214)  | **0.7893(0.0191)**  |\n| 1.0      | 0.7591(0.0293) | 0.7727(0.0092) | 0.7720(0.0169)  | 0.7771(0.0197)  |\n\nFrom the results, we can observe that 1) when FGW falls back to GW ($\\alpha$ =1), **where node features are no longer taken into account, the performance will significantly decay** (generally the worst among all investigated alpha values). This demonstrates the importance of solving the joint modeling problem in graph mixup tasks. 2) $\\alpha$=0.95 is the best setting in most cases. This empirically implies that **it is better to conduct more structural alignment in graph mixup**. In practice, we set $\\alpha$ to 0.95 for all of our reported results. We will add this analysis to the paper.\n\n> **Q2. How does the runtime of FGWMixup compare to the other baselines? Does the improvement of the performance come from a much higher computational cost?**\n\nWe provide runtime comparisons between our methods and baselines in the public response. Please check **Q1** in the **public response** for details.\n\n"}, {"review_id": "bJcq2dTt3r", "reviewer": "Reviewer_WT1n", "summary": "Authors study the problem of graph data augmentation for graph-level classifications. They propose a mix-up strategy based on the computation of Fused Gromov-Wasserstein(FGW) “mid-point” (or barycenter) between a pair of graphs from the training dataset. To solve these optimization problems, they adapt a recent single-loop GW solver [28] to the FGW setting (i.e including node features in the OT problem) and provide a theoretical analysis of the resulting algorithm. Finally, they benchmark their novel mix-up strategy against SOTA mix-up approaches on five real-world datasets using 4 different GNN architectures and show that their method achieves better performances than its competitors.", "questions": "I refer the authors to the weaknesses' list above for first suggestions and questions. Follows some questions/suggestions to potentially make the paper clearer:\n\nQ1. Could you please explicit the thresholding method used to deduce new sample from the FGWmixup strategy ?\n\nQ2. Could you report an ablation study with respect to the alpha parameter in FGW for the validated values {0.05, 0.5, 0.95} ?\n", "limitations": "I think discussing the weaknesses I've mentioned and answering my questions detailed above would help identify and work around the other limitations of their current work. If the authors manage to address these, I will happily increase my rating.\n\n This work has no negative societal impact.\n", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Authors propose an interesting mix-up strategy capable of incorporating both structure and feature information via the FGW distance.\n- They investigate two FGW solvers to estimate the inherent soft (attributed) graph matching problems in a novel task of graph dataset augmentation which is also interesting for the active optimization literature on (F)GW.\n- They partially extend the analysis done in [28] for GW to FGW.\n- They benchmark their FGWmixup with various SOTA mix-up strategies with 4 different backbones on 5 relatively small real-world datasets (small graphs with around 1k to 4k samples). The supplementary material also contains concluding experiments on the ogbg-molhiv datasets containing +40k samples. Plus study the robustness to label corruption of FGWmixup.\n- They study different mix-up strategies w.r.t the size of the FGW barycenters with pairwise (local) and global strategies (e.g proportional to the median size in the dataset)\n- Overall I find the paper well-written \n", "weaknesses": "- 1. *[addressed by authors]* **The FGWmixup is badly positioned with respect to the G-mixup** and the current literature on GW (resp. FGW) for the estimation of graphons (resp. attributed graphons): \nFrom my understanding, the G-mixup [18] strategy comes down to estimate 1 graphon per class then perform mix-up by sampling a graph from a linear interpolation between a pair of these graphons. [A] actually showed that a GW barycenter better estimates graphon than all methods considered in G-mixup paper. As discussed in [B], we can consider that an analog result holds for estimating attributed graphons using FGW barycenters. These observations highlight the following weaknesses / missing points in authors’ overall reasoning currently illustrated in the papier:\n\n\n     - a) G-mixup should be benchmarked using GW solvers which correspond to the FGW solvers studied by the authors. Note that [A] rather studied the Proximal Point solver introduced in [C], which seems to lead to lower performances on several tasks than the single-loop solver in [28] which coincides with your FGWmixup*.\n\n     - b) The extension of the G-mixup strategy using FGW instead of GW should also be discussed and benchmarked. In the same spirit, an ablation study with $\\alpha = 1$ should be considered for the FGWmixup. Basically, I would expect from your paper to identity what is better between a global mix-up strategy (G-mixup) or a pairwise one (FGWmixup) for data augmentation. From my point of view, the first one is favorably biased by a class (as a unique barycenter represents a class) but in the meantime the generated graphs are poorly representative of the graph dataset manifold as only one graphon is taken per class. Whereas your FGWmixup is not really biased by a class (potentially too local) but the generated graphs are intrinsically more representative of the input graphs.\n\n- 2. *[partially addressed by authors, the effect of removing marginals' cost is still unclear]* The single loop solver for FGW problems used in Algorithm 2, should be better positioned w.r.t to the one in [28] for GW. It is an exact adaptation from [28] adding the linear OT cost from node features. Moreover you propose to solve for an equivalent problem, where you removed the fixed terms on the marginals. This should be clear in the paper.\n\n     - a) As you remove fixed terms on the marginals, you solve an equivalent problem to get an OT solution. De facto, equation 4 is wrong as you do not consider exactly the gradient of FGW. Make this clearer in the paper please (maybe via different notations for both objective functions).\n\n     - b) In the spirit of [28, Table 7], the feasibility error i.e errors on marginals should be benchmarked across used solvers. I’m worried that removing the marginal terms in the FGW cost makes this feasibility error problem worse. Also this analysis should be completed with an analysis of the estimated FGW distances across used FGW solvers, over a dataset considered in the mix-up experiments.\n\n     - c) The theoretical results, especially proposition 2, are fairly easily proven by following [28]. This reduces the credit we can give to your theoretical contributions.\n\n- 3. [*partially addressed by the authors, the extension to full learning of the 'midpoint' distribution requires more in-depth analysis and will be the subject of future work.*] On the form there are still some points which can be easily improved:\n\n     - a) L93. Mu is not a probability measure, but a probability vector. + L95, references for ‘normalized’ degree distributions ?\n\n     - b) FGW (semi-)metric properties hold on the space of metric spaces quotiented by the notion of strong-isomorphism, like graphs depicted by distance matrices and invariant to permutations. Otherwise, following [D] it can be extended to any graph representations but w.r.t the notion of weak-isomorphism, hence FGW rather defines a pseudo-metric. \n\n     - c) I find the optimization parts confusing and heavy to read. I believe that their readability could be clearly improved by referring efficiently to specific steps in the algorithm and/or specific updates, instead of the confusing nested loop vocabulary. \n\n     - d) I got confused with Equation 2 being a nested bi-level optimization problem, could you further elaborate ? In my opinion it is more simple than that knowing that Atilde and Xtilde are not involved in the coupling constraints.\n\n     - e) Equation 2. In practice it seems that you do not consider learning the masses of the barycenter which removes a degree of freedom in your model. Learning those has actually been showed to be beneficial for many graph representation learning tasks (see [51, 52, 54]). Could you further justify your choice ? and I guess address that as a current limitation of your work. (Considering that it is not difficult to deduce a subgradient for the masses when using bregman projection based solvers.)\n\n     - f)  I believe that the paragraph ‘Effects of Mixup Graph Sizes’ could also take into consideration [E] where graph size also is a current limitation and does not exactly fall into the mentioned problem of graph size generalization. I believe that the latter problem mostly focuses on the question: can we generalize to big graphs when learning on small graphs ? (maybe I’m wrong)\n\n[A] Xu, Hongteng, et al. \"Learning graphons via structured gromov-wasserstein barycenters.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 12. 2021.\n\n[B] Xu, Hongteng, et al. \"Learning Graphon Autoencoders for Generative Graph Modeling.\" arXiv preprint arXiv:2105.14244(2021).\n\n[C] Xu, Hongteng, et al. \"Gromov-wasserstein learning for graph matching and node embedding.\" International conference on machine learning. PMLR, 2019.\n\n[D] Chowdhury, Samir, and Facundo Mémoli. \"The gromov–wasserstein distance between networks and stable network invariants.\" Information and Inference: A Journal of the IMA 8.4 (2019): 757-787.\n\n[E] Brogat-Motte, Luc, et al. \"Learning to predict graphs with fused Gromov-Wasserstein barycenters.\" International Conference on Machine Learning. PMLR, 2022.\n\n*Update after rebuttal : The authors have fully or partially addressed most of my concerns through their rebuttals and discussions. Considering that the authors have undertaken to amend the paper and supplementary material accordingly, I increase my grade from 4 (borderline reject) to 6 (weak accept).*\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your comments and suggestions. We made every effort to address all the concerns. In the following, we give our detailed response point-by-point. W denotes Weakness, and Q denotes Questions.\n\n- **W1:**\n\n  - a) We want to point out the fact that G-Mixup does not apply GW metrics to estimate the graphons (as they introduce in Table 1 and Table 6 in their paper [18]). In our implementation, we select the USVT method as the graphon estimator for G-Mixup. Indeed, it is also practical to apply the GW metric for graphon estimation. We also provide the experimental results of G-Mixup+GW and G-Mixup+GW*(single-loop solver) on PROTEINS in Table 1 of the PDF file from the **public response**. No matter what metrics are applied for graphon estimation, we want to emphasize that G-Mixup does not model the joint distribution of graph structure and signal spaces, and regard them as two disentangled and independent factors. However, **our main contribution and the greatest advantage compared with G-Mixup comes from the joint modeling of graph structure and signal spaces**. This also explains why FGWMixup can outperform.\n\n  - b) Just as the reviewer pointed out, G-Mixup can be extended with the attributed graphon using FGW estimator introduced in [B]. With the attributed graphon, G-Mixup can also consider the joint modeling problem. However, this is **NOT** the contribution and the core idea from G-Mixup, and we think **the comparison between our method with the original G-Mixup is already sufficient to prove the effectiveness of our core idea – solving the joint modeling problem with FGW**. Yet, we are also interested in the comparison of the sample-wise and class-wise mixup methods just like the reviewer. Hence, we conduct experiments with the extended version of G-Mixup with FGW graphon estimator, and the results are shown in Table 1 of the PDF file from the **public response**. We can observe that FGW does not significantly improve the performance of G-Mixup and still cannot outperform our methods. The main reasons lie in that the node matching problem remains unsolved using the linear interpolation strategy of two graphons introduced in G-Mixup.  Though the intra-class node matching has been done with FGW graphon estimation, **the graphons of different classes are not ensured with an aligned node distribution**. Simply conducting addition on two unaligned graphons is inappropriate. \n\n  - c) As for the ablation study of $\\alpha$=1 for FGWMixup, we will introduce it in our answer to Q2.\n\n- **W2:**\n\n  - a) After removing the constant terms in the FGW equations, we indeed should use another notation for this new optimization objective, and the gradient is calculated on this new objective instead of the original FGW. We will clarify the notation in the paper accordingly.\n\n  - b) For the analysis on infeasibility, please refer to **Q2** in the **public response** for details.\n\n- **W3:**\n\n  - a) Sorry for the mistake, and we will correct $\\mu$ as a probability vector. The normalized degree distribution is introduced in [C] (also [49] in our paper), and we will add this reference where we introduce this distribution.\n\n  - b,c) We will clarify the pseudo-metric property of FGW according to [D] in the paper and change the expression of the loop vocabulary to specific steps in the algorithm.\n\n  - d) If we take Eq.(1) into Eq.(2), we can find that Eq.(2) will be a nested minimization problem, where the optimization over $\\pi$ involves the calculation of $\\tilde{X}$ and $\\tilde{A}$ (according to Eq.(1)), and the minimization over $\\tilde{X}$ and $\\tilde{A}$ relies on the optimal $\\pi$. A classic paradigm to solve this problem is to iteratively solve the inner and outer optimization based on the local optima [a]. Actually, we think traditional solvers of (F)GW barycenters [24, 26] are based on this paradigm, and Alg.1 in our work is adapted from those solvers.\n\n  - e) We have considered whether to learn the masses of nodes ($\\mu$) in the mixup graph when designing our method. In fact, both choices are practical. For instance, [26] fixes the $\\mu$, while [51, 52, 54] adaptively optimize it. However, in our current version, we find that FGWMixup has already outperformed SOTA methods without adaptively learning $\\mu$. Considering that this design does not influence the core contribution of our method and the pages are limited, we have not explored the adaptive $\\mu$ version in our current paper and regard this as our future work.\n\n  - f) In the paragraph ‘Effects of Mixup Graph Sizes’, we actually do not claim to solve the graph generalization problem, but discuss why the fixed graph size is not a good option in our method. We explain that when we add a large proportion of graphs in a fixed size to the training set, the graph size distribution will be hugely biased and will be bad at generalizing to the test distribution. Especially for small graph sizes (0.5x Median), as we mentioned in the paper, they will make the distribution peaking at small sizes, which will ‘struggle to generalize to larger ones’ and lead to consistently worse performance as shown in Fig.1.\n\n- **Q1:**\n\n  - Our thresholding strategy is introduced in Appendix C. Here we further clarify the concept of ‘density difference’ in this section. The density of a graph G of N nodes is defined by: the number of edges / N(N-1), denoted as den(G). The density difference between the mixup graph $\\tilde{A}$ and two original graphs $A_1$, $A_2$ is: |den($\\tilde{A}$) – ($\\lambda$ den($A_1$) + (1-$\\lambda$) den($A_2$))|, and we try to seek a threshold to discretize$\\tilde{A}$ for minimizing this density difference.\n\n- **Q2:**\n\n  - Please refer to our response to **Q1** of Reviewer ZCHq for details. (If invisible, we will add them to the comments below)\n\n\n[a] Dempe, Stephan, and F. Mefo Kue, Solving discrete linear bilevel optimization problems using the optimal value reformulation, Journal of Global Optimization 68 (2017): 255-277.\n"}, {"review_id": "cCBMym2WgX", "reviewer": "Reviewer_Ake3", "summary": "This work presents a novel graph mixup strategy, which focuses on synthesizing a 'midpoint' graph between two graphs based on the graph structure-signal product metric space. The authors utilize the Fused Gromov-Wasserstein (FGW) distance to achieve this and also propose a method to accelerate the computation of FGW distance solvers by relaxing the polytope constraint. The effectiveness of the proposed method is verified through experiments on molecule and social network datasets.", "questions": "I noticed that Table 1 shows that the recent state-of-the-art baseline, G-Mixup, performs worse than the vanilla model in many cases. Is there a reason that the authors conjecture for these results?", "limitations": "The authors addressed the limitations of their work in the draft.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The draft is well-written, and the proposed methods are technically sound  with theoretical analysis.\n\n- Performance improvements compared to the recent baseline are significant.", "weaknesses": "- Efficient computation is a key aspect when deploying augmentation strategies in real-world applications. However, Table 3 is not conclusive to me in its current form. Please provide the computation cost for the vanilla model and other baselines to better understand the tradeoff between performance gain and efficiency.\n\n- Lack of qualitative analysis. It remains somewhat unclear whether the synthetic 'midpoint' graphs possess semantic meaning. For instance, in the case of molecules, specific functional groups determine their properties. If these key groups are missing in the synthetic 'midpoint' graphs, it might mislead the network. To provide readers with more insights regarding the 'midpoint' graphs, including real samples of synthetic graphs is recommended.\n\n- The experiments are currently limited to small-scale graph datasets (1K~4K). To demonstrate the applicability of the proposed method to medium/large-scale graphs, conducting experiments on more large-scale datasets such as the OGB benchmark datasets is highly required.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your comments and suggestions. We made every effort to address all the concerns. In the following, we quote your comments and then give our detailed response point-by-point.\n\n> **W1. Please provide the computation cost for the vanilla model and other baselines to better understand the tradeoff between performance gain and efficiency.**\n\nWe provide runtime comparisons between our methods and compared baselines as well as the time cost for the vanilla model traning in the public response. Please check **Q1** in the **public response** for details.\n\n> **W2. To provide readers with more insights regarding the 'midpoint' graphs, including real samples of synthetic graphs is recommended.**\n\nHere we provide two mixup examples of FGWMixup in the attachment PDF file in the **public response** for a more comprehensive qualitative analysis. The subfigures on the left and middle are the original graphs to be mixed up, denoted as G1 and G2, respectively. The subtitle denotes the mixup ratio $\\lambda$. The subfigure on the right is the synthetic mixup graph. The node features are one-hot encoded and distinguished with the feature ID and corresponding color. In Example 1, we can observe that the mixup graph adopts an overall trident structure and a substructure (marked green) from G1, and adopts several substructures from G2 (marked red), finally formulating a new graph sample combined properties from both graphs. In Example 2, we can observe that the mixup graph is quite similar to G2, but breaks the connection of two marked (red arrow pointed) edges and formulates two disconnected subgraphs, which is identical to the overall structure of G1. Moreover, in both examples, we can observe that the preserved substructures are not only topologically alike, but also highly consistent in node features. These examples demonstrate that **FGWMixup can both preserve key topologies and generate semantically meaningful node features**. We will add the qualitative analysis to the Appendix of our paper.\n\n> **W3. To demonstrate the applicability of the proposed method to medium/large-scale graphs, conducting experiments on more large-scale datasets such as the OGB benchmark datasets is highly required.**\n\nThis paper focuses on data augmentation, which mainly tackles the circumstances of data insufficiency. Therefore, it is more persuasive to observe results on small datasets. Furthermore, in former works [17, 18], datasets from TUDataset are widely adopted as the benchmark. Hence, we follow their settings and present the results on those datasets as the main results. However, we also have considered validating the effectiveness of our method on larger datasets, and **we have reported experimental results on large OGB datasets with 40K+ samples** (see Appendix E.2), and our methods also outperform all baselines.\n\n> **Q1. The recent state-of-the-art baseline, G-Mixup, performs worse than the vanilla model in many cases. Is there a reason that the authors conjecture for these results?**\n\nOn the one hand, **G-Mixup does not consider the joint modeling of graph structures and node features**. As we discussed in the Intro, ignoring the interaction between the graph structure and signal spaces may degrade the quality of graph data augmentation. \n\nAnother reason lies in that **the node matching problem remains unsolved using the linear interpolation strategy** introduced in G-Mixup to mix up two graphons. When calculating graphons, G-Mixup only focuses on aligning node distributions of graphs from the same class, but ignores the alignment across different classes. Therefore, the graphons of different classes are not ensured with an aligned node distribution. Thus, simply conducting the Euclidean addition operation on two unaligned graphons is not appropriate. \n\nThe two factors together may lead to a meaningless mixup graphon and probably introduce noises to the dataset, thus leading to performance decay."}]

Author rebuttal:
Thanks for all the constructive suggestions and comments concerning our paper from five nice reviewers. Here we provide our responses to some questions that are commonly asked by the reviewers.

> **Q1. Can you present the runtime comparison between your methods and compared baselines? Can you further analyze the time complexity of FGWMixup?**

We present the averaged efficiencies of different mixup methods and time spent on training vanilla backbones of each fold on PROTEINS and NCI1 datasets as follows. As Reviewer WT1n requires, we also include G-Mixup with GW graphon estimators (denoted as G-Mixup+GW) in the table. 

|          | DropEdge | DropNode | G-Mixup | ifMixup | G-Mixup+GW | FGWMixup | FGWMixup*  |
|:--------:|:--------:|:--------:|:-------:|:-------:|:----------:|:--------:|:----------:|
| PROTEINS | 0.192    | 0.229    | 6.34    | 2.08    | 2523.78    | 802.24   | 394.57     |
| NCI1     | 0.736    | 0.810    | 10.31   | 5.67    | 9657.48    | 1711.45  | 637.41     |

|          | GCN    | GIN    | Graphormer | GraphormerGD  |
|----------|--------|--------|------------|---------------|
| PROTEINS | 47.13  | 52.68  | 2636.98    | 2371.31       |
| NCI1     | 209.28 | 338.72 | 2701.04    | 6175.99       |

We can observe that FGWMixup(\*) and G-Mixup+GW are slower than the other data augmentation methods. The main reason is that the complexity of calculating (F)GW distances between two graphs is cubic ($O(mn^2+nm^2)$) [a], where $m, n$ are the sizes of two graphs. Moreover, when calculating barycenters, we need an outer loop with T iterations and M graphs. In total, the time complexity of mixing up two graphs of size $n$ is $O(MTn^3)$. FGWMixup\* boosts the efficiency by enhancing the convergence rate and reducing the required iterations T (see Table 5 in Appendix E.1 for more details), whereas G-Mixup+GW will have to go over the whole dataset to calculate graphons, which is much more time-consuming than FGWMixup. 

However, sacrificing complexity to pursue higher performance has been the recent trend of technical development, e.g. GPT-4. Moreover, **we believe that the current time complexity of FGWMixup\* is still acceptable compared with the time cost of model training (especially Graphormers) and our performance improvements**, as most compared graph augmentation methods cannot effectively enhance the model performance as shown in Table 1.

More importantly, in practice, the main computational bottleneck of (F)GW-based method is the OT network flow CPU solver in the current implementation based on the most widely used POT lib. In other words, GPU-based network flow algorithms have not been applied in current computation frameworks. Moreover, mini-batch parallelization is not yet deployed in POT. However, recent works [b, c] from NVIDIA have focused on accelerating network flow algorithms on GPU, which may probably be equipped on CUDA and allow a huge acceleration for GW solvers in the near future. **Hence, we firmly believe that the fact that our method is not yet optimized in parallel on GPUs is only a temporary problem.** Just as some other works (e.g., MLP, LSTM, etc.) that have brought enormous contributions in the past era, they are initially slow when proposed, but have become efficient with fast-following hardware supports.

> **Q2. Analysis of infeasibility of the single-loop FGW solver?**

First of all, we conduct an experiment to analyze the infeasibility of our single-loop FGW solver compared with the strict CG solver. We randomly select 1,000 pairs of graphs from PROTEINS dataset and apply the two solvers to calculate the FGW distance between each pair of graphs. The distances of the $i$-th pair of graphs calculated by the strict solver and the relaxed solver are denoted as $d_i$ and $d^{\*}_i$, respectively. We report the following metrics for comparison: i) MAE (mean absolute error of FGW distance, $\frac{1}{N}\sum |d_i - d^{\*}_i|$), ii) MAPE (mean absolute percentage error of FGW distance,  $\frac{1}{N}\sum \frac{|d_i - d^{\*}_i|}{d_i}$), iii) mean FGW distance given by the single-loop solver ($\frac{1}{N}\sum d^{\*}_i$), iv) mean FGW distance given by the strict CG solver ($\frac{1}{N}\sum d_i$), v) L2-norm of the difference between two transportation plan matrices (divided by the size of the matrix for normalization). The results are shown as follows:

| MAE            | MAPE           | mean_FGW | mean_FGW\* | T_diff          |
|----------------|----------------|----------|-----------|-----------------|
| 0.0126(0.0170) | 0.0748(0.1022) | 0.2198   | 0.2143    | 0.0006(0.0010)  |

We can observe that the MAPE is only 0.0748, which means the FGW distance estimated by the single-loop relaxed solver is only 7.48% different from the strict CG solver. Moreover, the absolute error is around 0.01, which is quite small compared with the absolute value of FGW distances (~0.21). We can also find that the L2-norm of the difference between two transportation plan matrices is only 0.0006, which means two solvers give quite similar transportation plans. All the results imply that **the single-loop solver will not produce huge infeasibility or make the estimation of FGW distance inaccurate**.

From another perspective, we do not think the infeasibility brings totally negative effects. As analyzed in our experiments (Table 1), FGWMixup* even sometimes performs better than FGWMixup. We explain this with the subtle infeasibilities introduced by the single-loop solver. By incorporating those infeasibilities, FGWMixup* may be able to **occasionally generate more diverse examples, which potentially enlarge the input space and bring opportunities to improve the generalizability of GNN models.**

[a] Gabriel Peyre et al., Gromov-Wasserstein Averaging of Kernel and Distance Matrices, ICML 2016

[b] https://on-demand.gputechconf.com/gtc/2017/presentation/S7370-hugo-braun-efficient-maximum-flow_algorithm.pdf

[c] https://mate.unipv.it/gualandi/talks/Gualandi_Aussois2020.pdf

Meta-review: This paper proposes a novel graph mixup method called FGWMixup that considers the joint interaction between graph structures and signals. FGWMixup seeks a "midpoint" of source graphs in the Fused Gromov-Wasserstein metric space to generate augmented graph samples. The authors also introduce a relaxed FGW solver to improve efficiency.

The reviewers raised several valuable concerns, including the computational complexity (WT1n), the quality of the synthetic graphs (Ake3), comparisons to related work like G-Mixup (WT1n), and theoretical justifications (Cjiv). The authors provided comprehensive rebuttals addressing each point. They analyzed the runtime and complexity compared to baselines, shared qualitative examples demonstrating meaningful graph structures and signals, clarified differences from G-Mixup, and explained the theoretical propositions in more detail. The reviewers acknowledged the satisfactory responses in their follow-up comments.

After considering the paper, reviews, rebuttal, and discussion, we believe this work makes a valuable contribution as an innovative graph mixup approach. The experiments demonstrate effectiveness on multiple datasets and GNN architectures. The theoretical analysis also strengthens the methodology. While more work can be done to optimize efficiency and refine the graph generation process, the core ideas warrant acceptance.

In conclusion, acceptance is recommended for this paper as a poster presentation.
Decision: Accept (poster)