Outlier-Robust Gromov-Wasserstein for Graph Data
Authors: Lemin Kong
Jiajin Li
Jianheng Tang
Anthony Man-Cho So
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Gromov Wasserstein
Robust Optimization
Nonconvex Optimization

Abstract: Gromov-Wasserstein (GW) distance is a powerful tool for comparing and aligning probability distributions supported on different metric spaces. Recently, GW has become the main modeling technique for aligning heterogeneous data for a wide range of graph learning tasks. However, the GW distance is known to be highly sensitive to outliers, which can result in large inaccuracies if the outliers are given the same weight as other samples in the objective function. To mitigate this issue, we introduce a new and robust version of the GW distance called RGW. RGW features optimistically perturbed marginal constraints within a Kullback-Leibler divergence-based ambiguity set. To make the benefits of RGW more accessible in practice, we develop a computationally efficient and theoretically provable procedure using Bregman proximal alternating linearized minimization algorithm. Through extensive experimentation, we validate our theoretical results and demonstrate the effectiveness of RGW on real-world graph learning tasks, such as subgraph matching and partial shape correspondence.

Outlier-Robust in for Graph Data
Lemin Kong
Jiajin Li Stanford University jiajinli@stanfode edu
CUHK
1kongãse. cuhk, edu hk
Jianheng Tang HKUST
Anthony Man-Cho So CUHK manchoso@se.com cuhk. edu. hk
j jtangbf@connect. ust.hk
Abstract
Gromov-Wasse Wasserstein (GW) distance is powerful tool for comparing and aligning probability distributions supported on different metric spaces. Recently, GW has become the main modeling technique for aligning heterogeneous data for wide range of graph learning tasks. However, the GW distance known to be highly sensitive to outliers, which can result in large inaccuracies if the outliers are given the same weight as other samples in the objective function. To mitigate this issue, introduce new and robust version of the GW distance called RGW. RGW features optimistically perturbed marginal constraints within Kullback- Leibler divergence- based ambiguity set. To make the benefits of RGW more accessible in practice, we develop a computationally efficient and theoretically provable procedure using Bregman proximal alternating linearized minimization algorithm. Through extensive experimentation, we validate our theoretical results and demonstrate the effectiveness of RGW on real-world graph learning tasks, such as subgraph matching and partial shape correspondence.
Introduction
Cromov-Wassersiee distance (GW) [26, 28] acts as a main model tool in data science to compare data distributions on unaligned metric spaces. Recently, it has received much attention across host of applications in data analysis, e.g., shape correspondence [24, 31, 36, 27], graph alignment and partition [37, 38, 15, 18, 14, 44], graph embedding and classification [41, 43]. unsupervised word
embedding and translation [3, 19]. generative modeling across incomparable spaces [8, 45].
In practice, the robustness of GW distance suffers heavily from its sensitivity to outliers. Here, outliers mean the samples with large noise, which usually far away from the clean samples or have different structures from the clean samples, The hard constraints on the marginals in the distance require all the mass the source distribution to entirely transported to the target distribution, making it highly sensitive to outliers. When the outliers are weighted similarly as other clean samples, even small fraction of outliers corrupted can largely impact the GW distance value and the optimal coupling, which is unsatisfactory in real- hal-world applications.
To overcome the above issue, GW distance. [33] introduces a I.' relaxation of mass conservation the GW distance. However, this reformulation replaces the strict marginal constraint that the transport plan should be joint distribution with marginals as specific distributions by the constraint that only requires the transport plan be joint distribution, which easily lead over-relaxation. On another front, [10] propose a so-called partial GW distance (PGW), which only transports fraction of mass from source distribution target distribution. The formulation of PGW is limited facilitating mass
recent works trying relax the marginal constraints of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Gromov- Stomov-Wassersterr Wasserstein
Gromov-Wasseriter Wasserstein
Robust Gromov- Saeoys-Wssrrttiin
GW = 0.0
GW = 0,148
RGW = 0,002
(a) Clean datasct
(b) Dataset with outliers
(c) Dataset with outliers
Figure 1: Visualization of Gromov- Wasserstein couplings between two shapes, with the source in blue and the target in orange. In (a). the GW coupling without outliers is shown. In (b), the coupling with 10% outliers added to the target distribution is depicted. The sensitivity of GW to outliers evident from the plot. In (c), we present the coupling generated by our proposed RGW formulation, which effectively disregards outliers and closely approximates the true GW distance.
destruction, which restricts its ability to handle situations where outliers exist predominantly on one side. formulation that allows both mass destruction and creation is proposed in [35] called unbalanced GW (UGW). The UGW relaxes the marginal constraint via adding the quadratic yp- divergence as the penalty function in the objective function and extends GW distance to compare metric spaces equipped with arbitrary positive measures. Additionally, [40] proved that UGW is robust to outliers and can effectively remove the mass of outliers with high transportation costs. However, UGW is sensitive to the penalty parameter as it balances the reduction of outlier impact and the control of marginal distortion in the transport plan. On the computational side, an alternate Sinkhorn minimization method is proposed to calculate the regulaiyr UGW. Note that the algorithm does not exactly solve UGW but approximates the lower bound of the entropic regularized UGW instead. From a statistical viewpoint, these works do not establish a direct link between the reformulated GW distance and the GW distance in terms of uncontaminated levels.
In this work, we propose the robust -aanov-Wasserstein (RGW) to estimate the GW distance robustly when dealing with outliers. To achieve this, RGW simultancously optimizes the transport plan and selects the best marginal distribution from neighborhood of the given marginal distributions, avoiding contaminated distributions. Perturbed marginal distributions help to re-weight the samples and lower the weight assigned to the outliers. The introduction of relaxed distributions to handle outliers draws inspiration from robust OT techniques [4, 29, 23]. Unlike robust OT, which is convex, RGW is non-convex, posing algorithmic challenges. This idea is also closely related to optimistic modelings of distribution ambiguity data-driven optimization, e.g., upper confidence bound the ammd bandit problem and reinforeement learning [7, 30, 1], data-driven distributionally robust decision- making with outliers [21, 9]. etc.
Morcover, inspired by UGW, RGW relaxes the marginal constraint via adding the Kullback- (KL) divergence between the marginals of the transport plan and the perturbed distributions as the penalty function in the objective function to lessen the impact of the outliers further. Instead of utilizing the quadratic KL divergence as employed in unbalanced GW, we opt for KL divergence due to its computational advantages. It allows for convex subproblems with closed-form solutions, as opposed to the linearization required for non-convex quadratic KL divergence, which could be challenging algorithmically. Furthermore, we leverage the convexity of KI. divergence to establish the statistical properties of RGW, leading to an upper bound by the true GW distance with explicit control through marginal relaxation parameters and marginal penalty parameters. This statistical advantage is disrupted by the non-convex nature of quadratic KL divergence. Additionally, KL divergence aligns with our goal of outlier elimination and is less sensitive to outliers compared to quadratic KL divergence, which is more outlier-sensitive due to its quadratic nature. Overall, RGW combines the introduction of perturbed marginal distributions with the relaxation of hard marginal constraints to achieve greater flexibility, allowing control over marginal distortion through marginal penalty parameters and reduction of outlier impact using marginal relaxation parameters.
To realize the modeling benefits of RGW, we further propose an efficient algorithm based on the Bregman proximal alternating lincarized minimization (BPALM) method. The updates in each

---

iteration of BPALM can be computed in highly efficient manner. On the theoretical side, we prove that the BPALM algorithm converges critical point of the RGW problem. Empirically. we demonstrate the effectiveness of RGW and the proposed BPALM algorithm through extensive numerical experiments on subgraph alignment and partial shape correspondence tasks. The results reveal that RGW surpasses both the balanced GW-based method and the reformulations of GW, including PGW and UGW.
Our Contributions We summarize our main contributions as follows:
robust model called RGW to alleviate the impact of outliers the GW distance. The key insight is to sinultaneously optimize the transport plan and perturb marginal distributions in the most efficient way.
We develop
On the statistical side, we demonstrate that the robust Gromov- Wasserstein is bounded above by the true GW distance under the Huber e-contamination model.
On the computational side, we propose an efficient algorithm for solving RGW using the BPALM method and prove that the algorithm converges to critical point the RGW problem.
Empirical results on subgraph alignment and partial shape correspondence tasks demonstrate the effectiveness of RGW. This is the first successful attempt to apply GW-based methods to partial shape correspondence, a challenging problem pointed out in [36].
2 Problem Formulation
In this section, review the definition of Gromov-Wasserstein Wasserstein distance and formally formulate the robust Gromov-Wasserstein. Following that, we discuss the statistical properties of the proposed robust Cromov-Wasserstere model under the Huber e-contamination model.
For the rest the paper, we will use the following notation. Let (X, dx) be a complete separable metric space and denote the finite, positive Borel measure on X by (X). Let P(X) C M4 (X) denotes the space of Borel probability measures on X. We use A " to denote the simplex in RR. We use 1, and 1axm to denote the n-dimensional all-one vector and X all-one matrix. We use S to denote the set of n x n symmetric matrice. The indicator function of set C is denoted as (c))).
2.1 Robust Gromov-Wasseerstrr
The
(GW) distance aims at matching distributions defined in different metric spaces. defined as follows:
Definition 2.1 .aassrs-assssstein)...... Suppose that we are given two unregistered complete separable metric spaces (X, dx). (Y, dy) accompanied with Borel probability measures μ, v respectively. The GW distance between μ and defined as
(y. d/ (z)./)) [f -
inf #c (
where 11(1s, v) is the set of all probability measures X x Y with μ and y as marginals.
As shown in the definition, the sensitivity to outliers of Gromov-Wassere hard constraints on marginal distributions. This suggests relaxing the marginal constraints such that the weight assigned to the outliers by the transport plan can be small. To do it, we invoke the Bullback-Leiblee divergence, defined as da, 14) fx (xx) log (a(z)/u(x)) dr, to soften the constraint marginal distributions. We also introduce an optimistically distributionally robust mechanism to perturb the marginal distributions and reduce the weight assigned outliers. Further details on this mechanism will be discussed later.
distance is due to its
Definition 2.2 (Robust Gromov-Wasserstein Wasserstein). Suppose that we are given two unregistered com- plete separable metric spaces (X, dx). (Y, dy) accompanied with Borel probability measures v respectively. The Robust GW between μ and v is defined as
GW Pi:0a (H, v) aEP(X), BEP(Y) F(a,9)
min
(I)
S.t. dRI a) S Pl. dKL )) S p2,
3

---

where F(a, 5) =
inf xeMt rEMF(XXY) [dx(x, ((xxx)] |]
- dy (v. Mf dx vidT (a',v) + Tidxa a) + T2dxL (T2, 8):
and (T,, ma) two marginals of the joint distribution n, defined by क (i +(A Y) for any Borel set A C X and (B) = xxX x B) for any Borel set B C Y.
The main idea our formulation is to optimize the transport plan and perturbed distribution variables in the ambiguity set of the observed marginal distributions jointly. This formulation aims to find the perturbed distributions that approximate the clean distributions and compute the transport plan based on the perturbed distributions. However, incorporating the constraints of equal marginals between the transport plan π and the perturbed distributions a and 3 directly poses challenges in developing an algorithm due to potential moo-smoothness issues. Inspired by [35], address this challenge by relaxing these marginal constraints and incorporating the KL divergence terms, denoted as dxu (T1, a) and dxL (T2, 33. into the objective function penalty functions. Different from [35], we use KL divergence instead of quadratic KL. divergence due to its joint convexity, which is more amenable to algorithm development, quadratic KL divergence is typically non-convex. Besides, transforming the hard marginal constraints into penalty functions can further lessen the impact of outliers on the transport plan.
Our new formulation extends the balanced GW distance and can recover by choosing = P2 0 and letting тi and 72 tend to infinity. When properly chosen, P1 and P2 can encompass the clean distributions within the ambiguity sets. In this scenario, the relaxed reformulation closely approximates the original GW distance in certain manner. Building this concept, we prove that RGW can serve as a robust approximation of the GW distance without outliers, given some mild assumptions the outliers.
2.2 Robustness Guarantees
Robust Gromov-Wassersterr Wasserstein aims at mitigating the sensitivity of the GW distance to outliers, which can result large inaccuracies if the outliers are given the same weight as other samples in the objective function. Specifically, RGW is designed to address the issue of the GW distance exploding as the distance between the clean samples and the outliers goes infinity. In general, even a small number of outliers can cause the GW distance to change dramatically when added to the marginal distributions. To formalize this, consider the Huber e e-contamination model popularized in robust statistics [22, 11, 12]. In that model, base measure Me is contaminated by an outlier distribution Po. to obtain a contaminated measure Jl,
μ= -1 (1- - e)fe + efaa
(2)
Under this model, data are drawn from μ defined (2).
Under the assumption of the Huber e-contamination model, it can be demonstrated that by selecting suitable values of Pi and P2. the robust Gromov- -aassertes distance ensures that outliers are unable to substantially inflate the transportation distance. For robust Gromov- Wasserstein, we have the following bound:
Theorem 2.3. Let μ and be two distributions corrupted by fractions 61 and e2 of outliers, respec- tively. Specifically, 4 is defined as (1 -1-60 =1) + Eifa- and v is defined as (1 e2) + 62 where th and ve represent the clean distributions, and pa and Va represent the outlier distributions. Then,
GW prip2 (M, v) < GW ve) + max (,.6-
P1
TIdKL (Her pa)
dkl. dKL Ho)
+ max 0,62 dKI, vo)
P2
T2dKL Va).
In Appendix B, we provide a proof that constructs a feasible transport plan and relaxed marginal distributions. By relaxing the strict marginal constraints, we can find a feasible transport plan that closely approximates the transport plan between the clean distributions and obtain relaxed marginal distributions that approximate the clean distributions.

---

The derived bound indicates that robust Gromov-Wast Wasserstein provides provably robust estimate under the Huber e-contamination model. If the fraction of outliers is known, the upper bound for the robust GW is determined by the true Gromov- Wasserstein distance, along with additional terms that account for the KI. divergence between the clean distribution and the outlier distribution for both jr and v. The impact of this factor is determined by the extent of relaxation in the marginal distributions P1 and p2. By carefully choosing P1 = εidgr (Jaa (o) and P2 = é2dKı, (Va, Vc), we can tighten the upper bound on the robust GW value, while still keeping it below the original GW distance (excluding outliers). Importantly, substituting these values of pi and p2 yields GW p1.ga (1,, v) S GW (We: Me), indicating that the robust GW between the contaminated distribution y and is upper bounded by the original GW distance between the clean distribution Me and Ve-.
The following inequality for UGW under the Huber e-contamination model can be derived using the same techniques in Theorem 2.3:
Remark 2.4.
(H, S GW(Mes vo) + TiI TT (Me: ()) + 72d (V). v).
We observe that the terms d (Mer p)) and d (Jer (4) cannot be canceled out unless TI and T2 are set to zero, resulting in over-relaxation. However, RGW allows us to control the error terms dgL (Pe Ha) and (K Va) through the marginal relaxation parameters pt and p2.
3 Proposed Algorithm
3.1 Problem Setup
To start with our algorithmic developments, we consider the discrete case for simplicity and prac- ticality, where μ and v are two empirical distributions, i.e., l Ei= pzdz, and v Σド= Uy0y.. Denote D E 8" Dak =x((,,, and D S and Djt (uj; w)) We construct 4-way tensor as follows:
C(D. D) = (Idx (2:, dr (15.20)12 k.g.
We define the tensor-matrix multiplication as
E hee
(C の (T
45
Then, the robust GW admits the following reformulation:
min (C(D, D) n, m) + ( + TT2 B)) x,0,3
s.t. dKL (H, a) S pi, del S P2:
(3)
n. E A m Ι 2 0.
Here, Ti = mlm and IT2 = π 11n
3.2 Bregman Proximal Alternating Linearized Minimization (BPALM) Method
As Problem (3) is non-convex and involves three variables, we employ BPALM [5. 2] to solve it. By choosing the KL. divergence as Bregman distance, the updates of this algorithm are given by:
k+1 arg min #0
(C(D. & th T) + di a+) T2dKL ( 8h) +
1
(T, (4)
ty
a k-1
arg min oE Sm
( a)
I da a0)
(5)
Ck
1 k+1 1B)+ dkL (3+ ,3) (k2
gk
arg min BEA" m (k.(),
(6)
T&k
Here, th. Ck. and T& stepsizes in BPALM.
5

---

In our algorithm updates, we employ distinct proximal operators for π and a (and 8). The use of dgr. (T) >²) T-subproblem (4) allows for the application of the Sinkhorn algorithm, while the introduction of dxr((" a) in a-subproblem (5) facilitates a closed-form solution, which we will detail in the following part.
To solve the r-subproblem, we can utilize the Sinkhorn algorithm for the entropic regularized unbalanced optimal transport problem. This algorithm, which has been previously introduced in [13, 32]. is well-suited for our needs. As for the a-subproblem, larger than O. Otherwise, when P = 0, a should simply equal μ. making the subproblem unnecessary. To solve the a-subproblem, attempt find the optimal dual multiplier w". Specifically, consider the problem:
consider the case where P1 is strictly
1 dai a) + wo(dka(1, ax) - pı).
min dxI.(= ..) + DE
Ck
Let ā(w) represent the optimal solution to (7), and we define the function p: R+ - R by p(w) dxL (u. a(w)) P1. We prove the convexity, differentiability, and monotonicity of p. which are crucial for developing an efficient algorithm for (5) later.
Proposition 3.1. Problem (7) has closed-form solution
a(w) T m a + ww
Eij
Tij 6
+
If u satisfies (i) and p(w) I O, (ii) O. p(w) O, then ā(w) is the optimal solution to the a-subbroolemm (5). Moreover, p(.) is convex, twice differentiable, and monotonically non-increasing on R,..
Given Proposition 3.1, we begin by verifying p(0) S O. If this condition is not met, and given that p(0) > 0 while lim p(w)= = -P1 < O, it implies that possesses at least one root within R.. The following proposition provides the framework to seek the root of p by employing Newton's method, with the initialization set at O. Hence, the a-subproblem can be cast to search root of p in one dimension, in which case it can be solved efficiently.
Proposition 3.2. Let p(-) : I + R be a convex, twice differentiable, and monotonically non- increasing on the interval I C RR Assume that there exists ă. F E I such that p(t) > 0 and p(z) < O. Then p has a unique root on I, and the sequence obtained from Newton's 's method with initial point 2n = I will converge to the root of p.
Since the 3-subproblem shares the same structure as the a-subproblem, can apply this method to search for the optimal solution to the 3-subproblem.
3.3 Convergence Analysis
To illustrate the convergence result of BPALM, we consider the compact form for simplicity:
min F' a, B) - f(T) + q(T) + 91 (T,, a) + g2 B) + (1 l2((3)
0,
where f(T) = D) @ π) ((T) [(=20) (T), g1 (T. a) 7 dı (T1 m. a), 92 (2 (3) (a), and h2(3) [[se (datu..)) (3).
Todku (nT 1,, 8), h2(a)
The following theorem states that any limit point of the sequence generated by BPALM belongs to the critical point set of problem (3).
Theorem 3.3 (Subsequence Convergence). Suppose that in Problem (1), the step size la in (4) satisfies O < L l < I S L, for k 2 O where I, I are given constants and Ly is the gradient Lipschitz constant of f. The step size C in (5) and r&k in (6) satisfy 0 < KIS Th < i for k 0 where n, i are given constants. Any limit point of the sequence of solutions {Thh a ,8* J220 belongs the critical point set X, where X is defined by
0 E f(T) + 0q(T)) + V= + Vn92(T,8),
0 V (. + Th1
0 E V V922(T, 0h2(3), (TT, a, 8):
(T,, or 3) E Raxm x RR" x T
For the sake of brevity, omit the proof. We refer the reader to Appendix C for further details.

---

Experiment Results
In this section, we present comprehensive experimental results validate the effectiveness of our proposed RGW model and BPALM algorithm in various graph learning tasks, specifically subgraph alignment and partial shape correspondence. Traditionally, balanced GW has been applied successfully in scenarios where the source and target graphs have similar sizes. However, in our approach, we treat the missing part of the target graph as outliers and leverage RGW for improved performance. All simulations are conducted in Python 3.9 on a high-performance computing server running Ubuntu 20.10, equipped with Intel(R) Xeon(R) Silver 4214R 1R CPU. Our code is available at https::/github..co http:://ggihub..ooom/ooo//22222 http://mmkong022/ottrrrrrrrssss
4.1 Partial Shape Correspondence
In this subsection, we first investigate toy matching problem in a 2D setting to support and validate our theoretical insights and results presented in Section Figure (a) illustrates an example where we aim to map a two-dimensional shape without symmetries to rotated version of the same shape while accounting for outliers the source domain. Here, we sample 300 points from the source shape and 400 points from the target shape. Additionally, adding points from a discrete uniform distribution on |-3, 22.5 x [0, 0.5] to the source domain. The distance matrices, D and D are computed using pairwise Euclidean distances.
introduce 50 outliers by randomly
Figures 2 provide visualizations of the coupling matrices and objective values for all the models, highlighting the matching results. In Figure 2(c), it is evident that even small number of outliers has significant impact on the coupling and leads an increased estimated GW distance. While unbalanced GW and partial GW attempt handle outliers to some extent, they fall short in achieving accurate mappings. On the other hand, our robust GW formulation, RGW, effectively disregards outliers and achieves satisfactory performance. Additionally, the objective value of RGW closely approximates the true GW distance without outliers, as indicated by Theorem 2.3, approaching zero
100
200
025
0.00
150
350
0.25
200
250
-1.00
(a) Shape Geametry
(b) Ground TPtth
(c) Balanced GW: GW 0.59
50
100
230
250
330
300
200
100
200
GW.s
Partial GW:
202
0.08
100
201
Figure 2: (a): 2D shape geometry of the source and target; (b)-(f): visualization of ground truth and the matching results of balanced GW, unbalanced GW, partial GW, and robust GW.
We evaluate the matching performance of RGW on the TOSCA dataset 34] for partial shape correspondence. For the initial estimation of the transport plan in both RGW and PGW, we utilize the partial functional map method [34], employing 30 eigenfunctions. This method establishes an initial matching relationship between the source and target shapes. This method establishes an initial matching relationship between the source and target shapes by setting T&k. for matching pairs (i, k) and 0 otherwise. The resultant transport plan is scaled by ||T||| E.g Tij. UGW is not suitable for this large-scale task due to its long execution time. As shown in Figure 3, RGW outperforms PGW, and enhances the performance of the initial point.
4.2 Subgraph Alignment
The subgraph alignment problem, which involves determining the isomorphism between query graph and subgraph of a larger target graph, has been extensively studied [16, 20]. While the
7

---

20
40
60
80
100
120
140
(a) Shape Geometry
100
200
300
400
Ground
20
20
20
81
40
40
60
50
50
80
80
80
100
100
100
120
120
140
140
100
200
300
400
100
200
300
400
100
200
300
400
Partial Functional Map
(c) Partial GW
(c) Robust GW
Figure 3: (a): 3D shape geometry of the source and target; (b)-(e): visualization of ground truth, initial point obtained from the partial functional map, and the matching results PGW and RGW.
restricted quadratic assignment problem is commonly used for graphs of similar sizes, the GW distance provides optimal probabilistic correspondence that preserves the isometric property. In the subgraph alignment context, the nodes the target graph, excluding those in the source graph, can be considered outliers, making the RGW model applicable to this task. In our comparison, we evaluate RGW against various methods, including unbalanced GW, partial GW, semi-relaxed GW (srGW) [42], RGWD [25], and methods for computing balanced GW such as FW [39], BPG [46], SpeeGW [15]. eBPG [36], and BAPG [24].
Database Statisties We evaluate the methods on synthetic and real databases. In the synthetic database, we generate target graphs G, using Barabasi-Albert models with scales ranging from 100 500 nodes. The source graphs G, are obtained by sampling connected subgraphs of G. with specified percentage of nodes. This process results in five synthetic graph pairs for each setup. totaling 200 graph pairs. The Proteins and Enzymes biological graph databases from [15] are also used, following the same subgraph generation routine. For the Proteins database, we evaluate the accuracy of matching the overlap between two subgraphs with 90% overlap and between subgraph and the entire graph, presented in the "Proteins-2" and "Proteins-1" columns, respectively. We compute the matching accuracy by comparing the predicted correspondence set Spred to the ground truth correspondence set Sgi. with accuracy calculated as Acc = (Sgt /ppel///S.. 100%. In addition, we also evaluate our methods on the Douban Online- Online-Offline social network dataset, which consists of online and offline graphs, representing user interactions and presence at social gatherings, respectively, The online graph includes all users from the offline graph, with 1, users serving as ground truth alignments. Node locations used as features in both graphs. In line with previous works [18, 37), we gauge performance using the Hit@k metric, which calculates the percentage of nodes in set V where the ground truth aligmment includes V, among the top-k candidates.
Table 1:
Comparison of the average matching accuracy (%) and wall-clock time (seconds) on subgraph alignment of 50% subgraph on datasets Synthetic, Proteins and Enzymes and Hit@) 1 and Hit@ 10 of dataset Douban.
Synthetic
Proteins-1 1
Proteins-2 2
Enzymes
Douban
Method
Acc
Time
Ace
Time
Acc
Time
Acc
Time
Hit@/
Hit@
FW
2.27
18.39
16.00
27.05
26.15
60.34
15.47
9.57
17.97
51.07
SpecGW
1.78
3.72
12.06
11.07
42.64
12.85
10.69
3.96
2.68
9.83
eBPG
3.71
85.31
19.88
1975.12
32.15
9645.05
21.58
1219.81
0.08
0.53
BPG
15.41
24.67
29.30
118.26
61.26
80.39
32.49
70.42
72.72
92.39
BAPG
48.89
27.95
30.98
122.13
66.84
16.49
35.64
16.41
72.18
92.58
SrGW
1.60
152.01
21.30
63.00
12.08
172.48
24.13
19.68
4.03
11.54
RGWD
16.68
955.40
27.94
4396.41
59.69
3586.56
30.35
2629.00
4.11
16.46
UGW
89.88
176.24
25.72
4026.93
67.30
1853.82
43.73
1046.29
0.09
0.72
PGW
2.28
479.99
13.94
544.79
20.08
348.44
11.43
212.09
18.24
37.03
RGW
94.44
361.44
53.30
834.76
69.38
466.91
63.43
293.84
75.58
96.24

---

SpecGW
BPG BARG
SpecGW BPG
BAFG RGW
SpecG
BPG BAPG
+UGW
RGW
+UGW
+UGW
RGW
100
60
80
Accuracy (%)
80
Accuracy (%)
Aecuracy (%)
60
40
60
40
40
20
20
20
0.2
0.2
0.5
Ratio number nodes
Ratio of number nodes
Ratio number nodes (c) Enzymes
(a) Synthetic
(b) Proteins
Figure 4: Graph Alignment performance for selected methods in relation to varying ratios of overlapping subgraphs on Synthetic, Protein, and Enzymes databases.
Parameters Setup We unweighted symmetric adjacency matrices D and 1) as input distance matrices. SpecGW employs the heat kernel (x)p(-)) with the normalized graph Laplacian matrix L. Both f and
uniform distributions. For SpecGW, BPG, eBPG, BAPG, srGW, and RGWD, we follow their respective paper setups. FW is implemented using the default PythonOT package. UGW selects the best results from regularization parameter sets {0.5, 0.2, 0.1, 0.01, 0.001} and marginal penalty parameter sets {0.1, 0.01, 0.001 PGW reports the best results in the range of transported mass from 0. 0.9. RGW sets 71 T2 = 0.1 and selects the best results from the ranges {0.05, 0.1, 0.2, 0.5) for marginal relaxation parameters and {0.01, 0.05, 0.1, 0.5, 1 for step size parameters (tg, Ck. rk). The transport plan initialization uses different approaches depending on the dataset. For the Synthetic, Proteins, and Enzymes datasets, we employ the 1xxm/ (nm) approach. For the Douban Online-Offline dataset, we initialize the transport plan using classical optimal transport conducted on the feature space. Additionally, for all datasets, we initialize a and B with uniform distributions.
Result of All Methods Table and Figure 4 provide a comprehensive comparison of matching accuracy and computation time across various methods on the Synthetic, Proteins, and Enzymes datasets. Notably, RGW demonstrates superior accuracy compared to other methods, while maintain- ing comparable computation time with UGW and PGW. On the other hand, methods for computing the balanced GW exhibit poor performance on all datasets, particularly on the extensive Synthetic graph database. This can be attributed to their struggle in fulfilling the hard marginal constraint on the source side and addressing the presence of outliers. Furthermore, the introduction of local minima in the balanced GW problem due to partial source graph structures contributes to the suboptimal results. UGW performs well with low target graph partiality but suffers significant degradation partiality increases. PGW, aimed at mitigating outlier impact, inadvertently affects the matching between clean samples by reducing the mass transported from the source domain. In addition. RGW achieved the best results with the highest Hit @1 and Hit@ 10 on the Douban Online Offline dataset, improving performance from 4.04% and 14.9% respectively for the initial point created by features.
Selection of Hyperparameters and T The hyperparameters Pl, P2, Ti, and 72 in our for- mulation serve distinct roles. Specifically, and /2 control the extent of marginal relaxation, while Ti and 72 act as the marginal penalty pa- rameters. As indicated by Theorem 2.3, we have the flexibility to fix the value of T and adjust to accommodate outlier effects. To determine optimal hyperparameter values, we conduct two analyses. First, we examine the effect of varying while maintaining fixed subgraph node ratio and constant t on the Enzymes dataset. Second, we adjust 7 while holding P constant and assess the impact across the Synthesis, Proteins, and Engymes datasets in the task of matching a 50%
rabio 05 matio-0
Syntistic Protcins Eneyma
ratti
(M))
Accusoy (%)
60
0.01
10
Marginal Relaxation Parameter
Penalty
Figure 5: Sensitivity analysis of p with fixed 0.1 on the Enzymes database, and sensitivity analysis of 7 with fixed 0.2 on the Synthetic, Proteins, and Enzymes databases.

---

subgraph to the entire graph. In Figure 5, the left side demonstrates that while keeping the ratio and fixed but varying p. accuracy diminishes when p becomes either excessively large or too small. However, within the range of 0.05 to I, accuracy remains resilient, highlighting the mitigating effect of marginal relaxation on outlier influence. Notably, accuracy significantly improves when p falls within the range of 0.05 to 1 compared to the scenario with p O, thus affirming the significance of marginal relaxation in our model. A similar trend is observed for T on the right side of Figure where maintaining fixed ratio and p while adjusting results in stable accuracy within the range of 0.1 but declining beyond this range. Consequently, in RGW computations, we can initially set to 0.2 and to 0.1 by default and subsequently adjust p based on the outlier ratio: increasing it for large ratio and decreasing it for a small ratio.
4.3 Tightness of the Bound Theorem 2.3
Our primary focus is on scenarios where the GW distance between clean samples is nearly zero or zero due to noise, such as partial shape correspondence and subgraph alignment tasks. In such cases, it is possible to find an isometric mapping from the query subgraph to a portion of the entire graph. By appropriately selecting the value of p, as discussed Section 2.2, the upper bound in RGW becomes the GW distance between clean samples, which is zero. As RGW is always nonnegative, this upper bound is tight in this context.
To empirically validate this, we conducted experiments on the toy example in Section 4.1, and Figure (a) illustrates the function values of PGW, UGW, and RGW with varying outlier ratios. The results confirm that the value of RGW can remain close to zero as the ratio of outliers increases. Additionally, Figure (b) shows the function value of RGW and its upper bound as p varies. Both the RGW value and its upper bound decrease, converging to zero as p increases. This observation provides empirical support for Theorem 2.3. Regarding UGW and its upper bound with changing we observed that both the UGW value and its upper bound increase as becomes larger, as shown in Figure (c). Unlike RGW, UGW's т must strike a balance between reducing outlier impact and preserving marginal distortion in the transport plan. This demands a careful balance and caution against setting т excessively close to zero, which could lead to over-relaxation and potentially deteriorate the performance.
0.12
0.20
UGW
RGW-UD
2.5
UGW-UB
Function value
0.15
RGW
PGW
Function value
0.08
RGW
Function value
2.0
UGW
1.5
0.10
0.04
1.0
0.05
0.5
0.00
0.00
0.0
0.3
0.4
0.5
0.01
0.1
1.0
5.0
0.01
0.1
1.0
2.0
Ratio of outliers
Relaxation parameter P
Penalty parameter
(a) Values of PGW, UGW, and RGW (b) RGW value and upper bound
(c) UGW value and upper bound
Figure 6: (a) Funetion values of PGW, UGW, and RGW for varying e; (b) Function value of RGW and its upper bound for different (c) Function value of UGW and corresponding upper bound for different
5 Conclusion
In this paper, we introduce RGW, robust reformulation of Gromov-Wasserster Wasserstein that incorporates distributionally optimistic modeling. Our theoretical analysis demonstrates its robustness to outliers, establishing RGW as a reliable estimator. We propose Bregman proximal alternating linearized minimization method to efficiently solve RGW. Extensive numerical experiments validate our the- oretical results and demonstrate the effectiveness of the proposed algorithm. Regarding the robust estimation of Maamoov-asssesteen, a natural question is whether we can recover the transport plan from the RGW model. On the computational side, our algorithm suffers from the heavy computation cost due to the use of the unbalanced OT our subroutine, which limits its application in large- scale real-world settings. To address this issue, natural future direction to develop single-loop algorithms to leverage the model benefits of robust GW for real applications.
10

---

Acknowledgments and Disclosure of Funding
Anthony Man-Cho is supported in part by the Hong Kong Research Grants Council (RGC) General Research Fund (GRF) project CUHK 14203920.
References
[1] Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning. International Conference on Machine Learning, pages 104-114. PMLR, 2020.
[2] Masoud Ahookhosh, Le Thi Khanh Hien, Nicolas Gillis, and Panagiotis Patrinos. Multi- block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization. Computationnal Optimization and Applications, 79(3):681-715 2021.
[3] David Alvarez-Melis and Tommi S Jaakkola. Gromov-Wasserster alignment of word embed- ding spaces. arXiv preprint arXXiv1809.000 2018.
[4] Yogesh Balaji, Rama Chellappa, and Soheil Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. Advances in Neural Information Processing Systems, 33:12934 12944, 2020.
[5] Jérôme Bolte, Shoham Sabach, and Mare Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 146(1):459-494, 2014, 2014.
[6] Alexander M Bronstein, Michael M Bronstein, and Ron Kimmel. Numerical geometry of non-rigid shapes. Springer Science & Business Media, 2008.
[7] Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
[8] Charlotte Bunne, David Alvarez-Melis, Andreas Krause, and Stefanie Jegelka. Learning generative models across incomparable spaces. In International Conference on Machine Learning, pages 851-861. PMLR, 2019.
[9] Junyu Cao and Rui Gao. Contextual decision maaking under parametric uncertainty and data- driven optimistic optimization. Available Optimization Online, 2021.
[10] Laetitia Chapel, Mokhtar Z. Alaya, and Gilles Gasso. Partial optimal transport with applications learning. Advances in Neural Information Processing Systems, 33:2903-
2913, 2020.
[11] Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance and scatter matrix estimation under Huber's contamination model. The Annals of Statistics, 1635):1932-1 2018
[12] Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau. Online and distribution-fres robustness: Regression and contextual bandits with huber contamination. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 684-695 IEEE, 2022.
[13] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and Franççis-Xavie Xavier Vialard. Scaling algo- rithms for unbalanced optimal transport problems. Mathematics of Computation, 87(314):2663- 2609, 2018
[14] Samir Chowdhury and Facundo Mémoli. The and stable network invariants. Information and Inference: A Journal of the IMA, 8(4):757-777. 2019.
distance between networks
[15] Samir Chowdhury and Tom Needham. Generalized spectral clustering via Gromov-Wassersee learning. International Conference on Artificial Intelligence and Statistics, pages 712-720. PMLR, 2021.

---

[16] Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub) graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(10):1367-137, 2004.
[17] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, et al. Pot: Python optimal transport. The Journal of Machine Learning Research, 22(1):3511-3578 2021.
[18] Ji Gao, Xiao Huang. and Jundong Li. Unsupervised graph alignment with Wasserstein distance discriminator. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 426 065,43352200 2021.
[19] Edouard Grave, Armand Joulin, and Quentin Berthet. Unsupervised alignment of embeddings with Wasserstein procrustes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1880-1890. PMLR, 2019.
[20] Myoungji Han, Hyunjoon Kim, Geonmo Gu, Kunsoo Park, and Wook-Shin Han. Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together. In Proceedings of the 2019 International Conference on Management of Data,
pages
2019.
[21] Nan Jiang and Weijun Xie. DFO: A framework for data-driven decision-making with endoge- nous outliers. Preprint optimization-online.co 2021.
[22] Kassam and Thomas. Asymptotically robust detection of a known signal in contaminated non-gaussian noise. IEEE Trunsactions on Information Theory, 22(1):22-26, 1976.
[23] Khang Le, Huy Nguyen, Quang M Nguyen, Tung Pham, Hung Bui, and Nhat Ho. On robust optimal transport: Computational complexity and barycenter computation. Advances in Neural Information Processing Systems,
2021.
[24] Jajjin 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. In The Eleventh International Conference on Learning Representations, 2023.
[25] Weijie Liu, Jiahao Xie, Chao Zhang, Makoto Yamada, Nenggan Zheng, and Hui Qian. Robust graph dictionary learning. In The Eleventh International Conference on Learning Representa- tions, 2022.
[26] Facundo Mémoli. On the use of Gromoy-Hausdon Distances for Shape Comparison. In M. Botsch, R. Pajarola, B. Chen, and M. Zwicker, editors, Eurographics Symposium on Point- Based Graphies. The Eurographics Association, 2007.
[27] Facundo Mémoli. Spectral Gromov-Wasserstin distances for shape matching. In 2009 IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops, pages 256- 263. IEEE, 2009.
[28] Facundo Mémoli.
Cromov-Wasserse distances and the metric approach to object matching. Foundations of computational mathematics, 11:417-487, 1.
[29] Debarghya Mukherjee, Aritra Guha, Justin M Solomon, Yuekai Sun, and Mikhail Yurochkin. Outlier-robust optimal transport. In International Conference on Machine Learning, pages 7850-7860. PMLR, 2021.
[30] Rémi Munos et al. From bandits to monte-carlo tree search: The optimistic principle applied to optimization and planning. Foundations and Trends@ in Machine Learning, 7(1):1-129, 2014.
[31] Gabriel Peyré, Marco Cuturi, and Justin Solomon. Cromov-Wassersiere averaging of kernel and distance matrices. In International Conference on Machine Learning, pages 2664-2672 PMLR, 2016.
[32] Khiem Pham, Khang Le, Nhat Ho, Tung Pham, and Hung Bui. On unbalanced optimal transport: An analysis of sinkhorn algorithm. In International Conference on Machine Learning, pages 7673-7682. PMLR, 2020.
12

---

[33] Emanuele Rodola, Alex M Bronstein, Andrea Albarelli. Filippo Bergamasco, and Andrea Torsello. A game-theoretic approach deformable shape matching. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 182-189. IEEE, 2012.
[34] Emanuele Rodolà, Luca Cosmo, Michael M Bronstein, Andrea Torsello, and Daniel Cremers. Partial functional correspondence. In Computer graphics forum, volume 36, pages 222-236, Wiley Online Library, 2017.
[35] Thibault Séjourné, François-Xavies Vialard, and Gabriel Peyré. The unbalanced Gromov Wasserstein distance: Conic formulation and relaxation. Advances in Neural Information Processing Systems, 34, 2021.
[36] Justin Solomon, Gabriel Peyré, Vladimir G Kim, and Suvrit Sra. Entropic metric alignment for correspondence problems. ACM Transactions on Graphics (ToG), 35(4):1-13, 2016.
[37] Jianheng Tang, Weiqi Zhang, Jiajin Li, Kangfei Zhao, Fugee Tsung, and Jia Li. Robust attributed graph alignment via joint structure learning and optimal transport. In 2023 IEEE 39th International Conference Data Engineering (ICDE), pages 1638-1651, 2023.
[38] Jianheng Tang, Kangfei Zhao, and Jia Li. A fused Gromov- Belamov-Wasseee Wasserstein framework for unsu- pervised knowledge graph entity alignment. Findings of the Association for Computational Linguistics: ACI. 2023, pages 3320-3334.
[39] 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.
[40] Quang Huy Tran, Hicham Janati, Nicolas Courty, Rémi Flamary, levgen Redko, Pinar Demetci, and Ritambhara Singh. Unbalanced CO-Optimal transport. In Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI), 2023.
[41] Cédric Vincent-Cuaz, Titouan Vayer, Rémi Flamary, Marco Corneli, and Nicolas Courty. Online graph dictionary learning. In International Conference Machine Learning, pages 10564- 10574. PMLR, 2021.
[42] Cédric Sincent-Cuaz, Rémi Flamary, Marco Corneli, Titouan Vayer, and Nicolas Courty, Semi-relaxed Gromov Wasserstein divergence with applications on graphs. In International Conference on Learning Representations (ICLR), 2022.
[43] Hongteng Xu, Jiachang Liu, Dixin Luo, and Lawrence Carin. Representing graphs via Gromov- Wasserstein factorization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[44] Hongteng Xu, Dixin Luo, and Lawrence Carin, Scalable Gromoy- Wasserstenn learning for graph partitioning and matching. Advances in Neural Information Processing Systems, 32, 2019.
[45] Hongteng Xu, Dixin Luo, Lawrence Carin, and Hongyuan Zha. Learning graphons via struc- tured Gromov- Wasserstein barycenters. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 00505-10513, 2021.
[46] Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov- Wasserstein learning for graph matching and node embedding. In International Conference on Machine Learning, pages 6932-6941. PMLR, 2019.
13

---

A
Organization of the Appendix
We organize the appendix as follows:
The proof details of Theorem 2.3 and discussion of Remark 2.4 given in Section B.
The proof details of the algorithm, including the properties of p. the convergence analysis of Newton's method, and Bregman proximal alternating linearized minimization method are collected C.
Additional experiment results summarized in Section D.
B Proof of Robust Guarantee in Section 2.2
B.1 Proof of Theorem 2.3
Proof. GWmb
Pi.pz (1,, v) is defined as
/f [dx(xxz') - dy dy, 2/) yd (z'.0) +
GW (H,))
inf DEP(X), xEM-
inf
TikK( + T2dKI,(T,,))
s.t. (RI S...
Consider Te, the optimal transport plans for GW vo). Notably, Toe serves as a feasible solution for GWith PL (H, 1/). Consequently, we can deduce that: GWmb P1.P2 (H, aEP(X), BEP(Y)
If [dx(z, dy (y, ())l dd (e', ./)
inf
Ti diKI((Fe)1; a)) T2dki. ( (Te)2.
s.t. (u, S pI, (K, B) S 02 inf =GW(He, aEP(X), (p. (Me; a) +
inf
dKL. (Ve, B).
SEP(Y), (p,
To establish an upper bound for GW Pl.P2 (H, let us begin by addressing the following problem: inf aEP(X); (p.().
dKL (pe: a)
(8)
We consider the distribution of the form (1 7)μ + Yes for y E [0, Then we prove that
7 S min
(Pa, ue) (ee)))))) 11) then (1 7)2 + MH a feasible solution for problem (8).
P1
By the joint convexity of KL divergence, we have
dKL (H, (1 - 77) + mme) I 7dKL (H,, Mc)
7uKL ((1 - e1) + eifla Me)
I yeldKL (Har Mo)
S P1.
Therefore,
dRL. (Per (1 7)2 7P.) < (1 7dk (Her p2)
= (1 7) dd (Ner (1 - e 1) + (1P))
< (1 7) drd. (Pes pa)
The largest value y can take is
This gives
eidKI. (Mar Mc)
PI (Ke a) < max (0, eidka (Mar Mc)
) El (eer
inf aEP(X), dia (p
Similarly, prove that
P2 dKL (Ves 9) S max 0, e2dkI Uo)
inf
(EP(Y), Spp This completes the proof.
14

---

B.2 Proof and Discussion of Remark 2.4
Utilizing the same notations as in the proof of Theorem 2.3, and considering that Te is feasible solution to the UGW problem, substituting it directly leads to the desired result.
Furthermore, referring to [40, Theorem 1] and adapting the notations to our framework, we have the following property: specifically, when considering only is corrupted with outliers, characterized by J (1 61 ]d Ma,,,, while Ve. If we let 2( + 72) and K M M UGW (/ee v) + 6, where M represents the transported mass between clean data and A signifies the maximal deviation between the contaminated source and the target, then the following inequality holds:
Ax (1 + M) + K
]
(GW(H, - (1 (J) v) 8M - -eexp
5M
Given that UGW v) & GW(Me: v),, we can derive the following relationship:
UGW(A,) S G)) v) + 8M 1 exp Ax++ M) + + * GWiMe v) + }
(9)
6M
Comparing this result to Remark 2.4, (9) also incorporates GW (W 1/) in the exponential term and M, the transported mass between clean data. These variables may be influenced by the marginal parameters 71 and 72- As result, finding an optimal choice for тΙ and 72 establish tight upper bound for UGW using the GW distance between clean samples, as presented in (9), proves challenging. As outlined in Remark 2.4, it is worth noting that setting TI = T2 represents the sole means to attain tight upper bound. Nevertheless, in real-world applications, this approach is impractical, as it could lead to over-relaxation and compromise the performance.
C Proof Details of Bregman Proximal Alternating Linearized Minimization Method for Robust GW
Given vector x, we use ||æ||| to denote its l norm. We use | to denote the Frobenius norm of matrix X. For convex set C' and point x, we define the distance between C' and
dist(r, C)
min || - vl12. vCC
C.1 Proof of Proposition 3.1
Proof. Problem (7) can be written as
min
Σ ((mt (nt log
(अ (TT (x
+1 + as
a
log
a.
)
+
Σ
us log
M4
Pi
Ck
a
06
We first consider relaxed problem of the problem above:
min 1,=11
Σ (कt (
log log
(x++t);
(+)+)); a.
Σ of log
a
tw
Σ
n
pe log
pr
ax
as
a2
Consider the Lagrangian function of the relaxed problem
[m] x+1
h
L(a, A) = Σ
(m 1+++1 );
log
- (
+
+ -
Σ
a
log
+
ai
10
M4 log
Hi
p
+ > (aT1,, 1
ai
1=1
Let
(s) )2
al
+1
w
= O.
Da
Ck
On
an
15

---

Then we obtain that
k+++ 0g = (m(+1)
)
a wuji
cx
1
Since Σ a; = Ei= o 1, and Σ 2i=1
1, then + +1==Esh Téj
k+l
1 + w. Thus, the + o
optimal solution to the relaxed problem is
d(w) nb+11 m a + wi
Ei, mij + w
We can see that ā(w) 2 Hence, d(w) also the optimal solution to problem (7).
Since if w satisfies (i) or (ii), (&(w), w) is a solution to KKT conditions of problem (5), therefore, á(w) is an optimal solution to problem (5). Next, prove that p is differentiable when h is relative
entropy. Problem (7) admits the closed-fore forem-foommmmo solution
n 1 m ca
La + wp
a(w))
(10)
Σns
k+l
+ 1 + w
9/
By substituting (10) into p. p(w) be written
Mi CEn k+1 1 w: Te
a
p(w)= Σ us log
on
P1-
(I++llm); + 2 a + wpis
Thus, p is twice differentiable. The first-order derivative and second-order of p
(M (m))))m)) mm) + af + kww) Mi (Eng
k+1
+ 1 +
v'(w) Σ 14
Σ Tij
k+1
+ 1 + w) ((Tet11m)) + 1
aat k,w
1=1
ou
and
(nt+11 1m); + L + mmw!
-1 Eis Tij
k+1 1 +
n
p'(w) =
Σ H4
Eij nktt
k+1
c + w ( + ca
a 1:
Then we prove that (w0) < 0 and p((w) 2 for w 2 0, so p is monotonically non-increasing and
convex on R4. Let Lets, 8; ( 1m)
af + wai and (m
a p.w. Note that
cs
s = Σi= 9;. Then p' and p" can be written as
8
148
148
p'(w)= =
14
Pi
8:
St
1=1
1=1
and
n
2
1
n
12
('(w))
1- Σ
14
$
52
$
1=1
Therefore, it is equivalent to show
Σm=
1i=10 Mi
448
2 1
and
Σn
H4
1220
2
1.
84
Recall that and 1 are convex on 14,,, then x x2
548
P1
8i
81
Mi
1
2
2
P4g
22
2
3
1.
Mi
Mid
16

---

C.2 Proof of Proposition 3.2
Proof. First, prove that p only has one root on I. Since p is continuous on and there exists ă, such that p(ž) > 0 and p()) < 0, contains at least one root on [i, F.. Since is non con-increasing. p cannot have roots outside [ž. ø.. Suppose that p have two different roots 21 and 22 on [i, x) and
By convexity of p. we have
22
22
21 4
1 - 22 p(z1)
22 21
22 21 p(T)
0 = (222
21
+
(
< 0.
21
x 21
This is contradiction. So p has unique root on
p' (x) < 0 since p is non-increasing on 1. Denote the root of p as
Claim that p' < 0 for c r]. Otherwise, there exist [ā. such that ('x)) 0, then
p Ø 2 p(z) + (x) x) p(x) 2 0, 0
which leads to a contradiction. Especially, (z) < O, and we can set o as the initial point of Newton's method.
The update of Newton's method
p(ra)
F++1
Zk
p' p((xk)
Therefore, Te+1 2 and (2ra is an increasing sequence. Since is convex,
p(xx+1) 2 p(xx) + ( (xx) xx) = p(xx)) - p(xx) = 0.
Jy S r because p monotonically non-increasing function. k is increasing sequence with an upper bound, so it has limit x" and 1om (1 - 2x+1) = 0. Also, p' is bounded on [ž, r] since continuous. Therefore,
p(x")= lim p(æ+) = lim p' (<x) Ik+1) 0.
to
Hence, the sequence generated by Newton's method converges a root of p.
C.3 Proof of Theorem 3.3
Assumption C.1.
The critical point set is non-empty.
Before the proof of Theorem 3.3, first prove that sequence (T* generated by BPALM lies in a compact set.
Proposition C.2. Sequence ( k20 generated by BPALM lies a compact set.
Proof. We prove that (** J220 lies the compact set = {ır E Raxm 0 mij S 1) by mathematical induction. For & = O, we can initialize TO with S xh S Suppose that n² and
k+1 1. Recall that *+1 is the optimal N+1 & A. Then there exist E [n] and E [m] such that m
solution to the problem
1 at) + TodKı (x TTT1,, 1,, sh) + ty
min p(x) = (C(D. D) Th x) + Ti #2-0
dKL( a*), (11)
T Observe that function ((x) == x log - + a unimodal function on R,, and achieve its minimum
at Since oz Bj. and n/i are smaller than or equal to 1, os, 3j. and Ntty are strictly smaller than
k+1 Let स E mx
ij
max as By xt.)
(k, (i.j).
.+l Thl
otherwise.
Then (+t) (((tt), this contradicts to * is the optimal solution to problem (11). Thus, k+1 E A.
17

---

For the proof of Theorem 3.3, we first prove the sufficient decrease property of BPALM, i.e., there exist a constant K1 and an index 1n 2 such that for k 2 k1.
F (n a ++1 " F (n*
9*)) S -Ki (1I=+) - 111
+I1aa*t1 - a0 + - )
And then we prove the subsequence convergence result.
Proof. is worth noting that f(z) is quadratic function, i.e. f(T) ( D) 1,, then f(x)
is gradient Lipschitz continuous with the constant maxi, (Ex, ()).3..))) 1/2
To simplify the
notation, let L5- max,5 (En, L(D, 1/2
F F " k-1 1 1) - F (TT aa,,at, 14)
< (Vf(TT) k+1 - オt) + 41 | xx [| F + q ( + gi (1 at1) + 92 1r +
2
1/ (a x11 ) + 1/2 (3h+1)= - (g (x²) + 91 (Tt, a²) + 92 (Tt ,h)) + h1 (a*) + h2 (3"))
(V/(T²)) ) k+1 - )²) + Li dRI.
ddi. (m=+1
a a + 92 ( , 1) +
h1 (a x+1) + h2 (3++1) (g (x²)) + 91 (T* 92 ( 3h) + h1 (a
+ h2 (s
<VV[(T))) 1 + q (I + gl (n**), 02 3h) + dki. ( न
is
<V/(TT)) x/ q (T*)) - gl (T a) 92 (T 8hh + 91 ( ntt ,attt) + h1 (a*t1) + 1
dki (a, antt1)-
cx
(T*,, a²) - 11 (a+) + g2 ( (1 1 + 112 (aht1)+ + dRI (st, ,htht) - -92 (*) - h2 (3h)-
1
Ls]
1 dKL ( xx dKL (at kt)
dKl (Bh,
tk
σ
Cx
rk
Tuf)
dKL. (n xx
drL (a+ ,,,ttttt
1
dKl. ghtt1)
1
Ck
rk
(0)
1
| - 11p -
+ 1 Ck
-
Ilaatt - a
1111222 +
-
1
|| - -0413)
2
(4) is because as x log x is o-strongly convex, we have
dkl (x x²)== 2 |
n 11
dai a 11
2 σ
2 -0 dka ,1itl 2 2
By letting K1 = o min
1 (
L1p
> 0, we get
2 t/
iF
F (+1 x+1 1/+h)) FF (T a ,0t) S - (11
- 111/2 |/-= + +11a**1 - a&112= + -113ht1- - -3b1(2)
(12)
Summing up (12) from k- = 0 to +00, we obtain
x 1|2 + ||at1 a a²112 + 332t1-34133 S F( ae, (,), 3F))F((T* a00 BBo).
K1
As F is coercive and { at (²)) } is a bounded sequence, it follows that the left-hand side is bounded. This implies
Σ k=0
(| a h+1 - I 11? p + ||attt1 - a011 -a + 11ghtt- 100+1-14t0p -s(((2) < +00,
and
lim (1] -
-x*||= * + 1la - a+112 + 11gh41 - -3x112) O.
k-0000
18

---

Let (x)) = E, log.;; 24. Recall the optimality condition of BPALM, we have
0E V (** + 0y (x*+1) Va91 (n a²) + V #9 ( ,8hh
(VI
V/ (T()))
bx
(13)
0E Vagi ( a 1) + dh1 (a
a²). -
(14)
Ck
0 E Vgg2 ( k+ 1 + 2h2 (gh+1) +
- ( - ghh).
(15)
Th
Let (m , ) be limit point of the sequence {(=*, at g ) converges to (x= a B Since we assume that is
1200 Then, there exists sequence
(nx J220 such that {(***, ar*, ,=*,,"**)) )220 ("*)))
twice continuous differentiable and af and 3 are in compact set, then (²((a²) and (²((B*) bounded. Therefore, limu= (=((a=+)((a -** 0 and lima- )=((3++))(Bk+> 3h) = 0.
Replacing the & by nu in (13), (14), and (15), taking limits on both sides as k: - oo, we obtain that
0 Vf (T + 0T(T0))))))))))))))0)))))) xx91 ( , +V.V V 20 ,g0)
0 E Vagi (I ) + 0h (a
0 E Vage , + 0h2 (3x0.
Thus a
00 Bae)
belongs to X.
C.4 Discussion of Computational Complexity of PGW, UGW, and RGW
We consider the measure minosks minosk<*([ > + ||a a 1l + || - (1112) as the stationary measure, and it is observed that the convergence rate of our algorithm O (()R) Similarly,
the Frank-Wolt algorithm for PGW also exhibits convergence rate of ((+))) The literature on UGW does not provide a discussion on the convergence rate of alternate Sinkhorn minimization for UGW. In each iteration of PGW, UGW, and RGW, the computation of C(D, D) @ nT is crucial step. According to [31]. the complexity of this computation Onn2m + m²n). Additionally, PGW involves utilizing the network simplex algorithm to solve linear programming problem as subroutine, which has complexity of O((nmm + m²n) log"( (n + m)). On the other hand, both UGW and RGW utilize the sinkhorn algorithm to solve an entropic unbalanced optimal transport problem. The complexity of the sinkhorn algorithm for unbalanced OT is O(n + (s log(e))) for computing an E-approximation.
D Additional Experiment Results
D.1 Additional Experiment Results Subgraph Alignment
Source codes of all baselines used in this paper:
FW [17]: http:////gtaabb..oo////oooo////0
eBPG [17]: http:s////ggtthh..ocoo/yyyta/ta/
BAPG hhtp:///ghhcccccooaooc/ccc////aa
UGW http:////..tttu...o...ooo/uuu//e
PGW [10, 17]: ht/p:p/p///gthhbbb.oo///////o///
srGW: [42]: httppp///ghhaaacccc///occccceirr
RGWD: [25]:
Results in Figure The data utilized to create Figure 4 is provided in Table 2 and Table 3.
19

---

Table 2: Comparison of the average matching accuracy (%) and wall-clock time (seconds) subgraph alignment of 30% subgraph and 20% subgraph.
30% suhgraph
20% subgraph
Synthetic
Proteins
Enzymes
Synthetic
Proteins
Fazymes
Method
Acc
Time
Time
Acc
Time
Acc
Time
Acc
Time
Time
FW
2.22
17.06
12.96
14.83
12.08
5.37
2.24
6.65
10.83
11.34
9.53
4.92
SpecGW
1.38
2.24
10.64
11.54
9.41
3,74
1.71
2.21
10.78
10.15
8.35
3.21
cBPG
0.65
0.49
8.12
1022.02
3.84
476.83
1.17
0.42
7.23
545.50
2.66
94.78
BPG
1.86
17.53
17.89
86.85
17.69
52.89
1.64
11.66
12.99
55.47
14.35
32.89
BAPG
2.94
35.90
18.79
36.02
16.85
10.88
3.80
23.29
14.07
23.92
11.22
8.38
StGW
3.17
86.38
22.75
89.14
27.45
41.18
5.49
88.89
18.38
17.72
23.13
17.11
RGWD
1.94
933.25
16.90
3674.98
16.34
3322.16
1.94
933,25
16.90
3674,98
16.34
3322.16
UGW
35.15
168.03
14.32
10298
10.91
5552.27
4.48
251.41
11.75
7813.96
10.40
4019.62
PGW
2.06
339.23
11.68
507.11
11.77
174.26
1.90
227.87
9.34
365.88
7.97
165.27
RGW
52.35
679.00
30.17
947.48
37.12
$38.04
11.58
229.05
23.51
546.15
25.39
879.93
Table 3: Comparison of the average matching accuracy (%) and wall-clock time (seconds) on
subgraph alignment of 40% subgraph.
40% subgraph
Synthetic
Proteins
Enzymes
Method
Acc
Time
Ace
Time
Acc
Time
FW
1.84
17.96
15.34
19.64
14.22
6.36
SpecGW
1.72
3.25
11.21
12.17
9.59
3.88
eBPG
0.38
0.51
12.16
1628.38
9.96
943.49
BPG
3.41
18.61
24.31
108.10
24.58
62.81
BAPG
7.61
22.55
23.78
36.81
24.82
11.13
SGGW
2.45
120.12
22.58
74.58
27.0
32.14
RGWD
3.48
930.84
22.73
4490.60
22.63
3205.03
UGW
79.61
960.04
21.22
11398
22.26
5589.73
PGW
2.17
483.10
11.95
491.64
9.51
182.58
RGW
90.79
662.15
38.94
769.25
48.11
291.74
Selection of Stepsize thp Ck. and T& In the subgraph alignment task, we have used constant values for the stepsizes lx. C and Tи- We have conducted a sensitivity analysis for these parameters, and the details summarized in Tables and 5. Specifically, Table 4 reveals that RGW achieves its highest accuracy with / in the range of 0.01 to 0.05, allowing us to select = 0.01 as the default. Table further indicates that accuracy not significantly affected by variations in c, leading us as the default.
0.1
Table 4: The performance of RGW with different stepsize on three subgraph alignment databases.
Synthetic Acc
Proteins-1 Acc
Enzymes Acc
RGW
Time
Time
Time
0.01
94.64
541.50
$3.07
567.09
63.23
139.82
0.05
90.49
288.25
$3.37
1030.15
63.69
304.11
t= 0.1
87.00
233.65
$3.69
713.07
62.38
506.83
t= 0.5
87.09
779.84
51.56
1797.13
60.07
822.23
t= 1.0
71.10
491.93
50.21
3071.27
58.31
1166.88
Experiment Results of Normalized Degree as Marginal Distribution In addition to employing the uniform distribution as node distribution, we also explore the use of normalized degrees as node distribution. The results presented in Table 6 confirm that RGW surpasses other methods in terms of accuracy when utilizing normalized degrees as marginal distributions.
Experiment Results of Adding Noise to Query Graph We conducted an experiment by adding 10% pscudo edges to the subgraphs, and the results can be found in Table 7. These findings
20

---

Table 5: The performance of RGW with different stepsize on three subgraph alignment databases.
Synthetic Acc
Proteins-1 Acc
Enzymes Acc
RGW
Time
Time
Time
c= 0.01
90.39
481.06
53.17
459.43
63.06
163.45
0.05
90.39
967.98
53.12
919.18
62.86
327 227.44
0.1
90.39
1460.94
53.37
1374.43
63.69
490.91
c= 90.34
1969.18 18
53.35
1822.70
63.36
650.25
c= 1.0
90.28
2488.17
53.43
2262.07
63.53
807.57
Table Subgraph alignment results (Ace.) of 50% subgraph of compared GW-based methods using normalized degree.
Method
Synthetic
Proteins-1
Proteins-2
Enzymes
FW
2.96
14.82
42.16
15,90
SpecGW
1.57
8.92
43.10
12.07
cBPG
5.27
13.77
31.90
13.51
BPG
12.52
20.88
57.77
29.42
BAPG
74.39
24.65
63.26
31.92
SrGW
4.22
13.67
12.39
23.05
RGWD
13.54
25.92
57.30
28.12
UGW
99.56
25.51
62.92
39.71
PGW
3.97
11.59
37.79
13.08
RGW
99.61
50.61
66.09
63.59
demonstrate that RGW significantly outperforms other methods on the Enzymes and Proteins datasets.
Table 7: Subgraph alignment results (Mean + Std.) of 50% subgraph in 5 independent trials over different random seeds in the noise generating process.
Method
Synthetic
Proteins-1
Enzymes
FW
2.38=0.27 1.79=0.26
10.21
12.58+12.58
SpecGW
9.91=0.56
10.00+00.81
cBPG
6.84=1.89
15.63
14.31
BPG
17.71+2..23
20.96
22.29-t1.19
BAPG
43.39 + 4.84
2..08
24,424 1.54
SrGW
1.75# 0.18
13.3410.56
20.03:1 0.73
ROWD
17.30 1.90
22.7010.33
24.07 0.44
UGW
81.24 2.34
22.99+0.16
26.68+ 1.54
PGW
1.67 = 0.43
8.19-00.2
7.33+ 0.45
RGW
88.79 1.59
38.8811.31
49.01
D.2 Additional Experiment Results on Partial Shape Correspondence
The convergence results for the proposed BPALM using various step sizes are presented in Figure 7 for the toy example discussed in Section 4.1.
Convergence of BPALM
Additional Experiment Result on TOSCA Dataset Additional experiment results on TOSCA
Dataset are shown in Figure 8, 9, and 10.
21

---

1-1
10
100 P.0uPPtttt 0..
loqul
200
300
Ittration
Itoration
Figure 7: Convergence result of toy example with different stepsizes
50
150
250
100
200
500
(a) Shape Geometry
(b) Ground
50
50
50
100
150
150
150
200
200
200
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
(c) Partial Functional Map
(d) Partial GW
(e) Robust GW
Figure 8: (a): 3D shape geometry of the source and target; (b)-(e): visualization of ground truth,
initial point obtained from the partial functional map, and the matching results PGW and RGW.
22

---

20
60
100
120
140
100
200
300
400
500
(a) Shape Geometry
(b) Ground Truth
20
20
20
60
60
60
100
100
100
120
120
120
140
140
140
100
200
300
400
500
100
200
300
400
500
100
300
400
500
(c) Partial Functional Map
(d) Partial GW
(e) Robust GW
Figure 9: (a): 3D shape geometry of the source and target; (b)-(e): visualization of ground truth,
initial point obtained from the partial functional map, and the matching results of PGW and RGW.
100
150
200
100
200
300
400
500
(a) Shape Geometry
(b) Ground Truth
50
50
50
100
100
100
150
150
150
200
200
100
200
300
400
500
100
200
300
500
100
200
300
500
(c) Partial Functional Map
(d) Partial GW
(e) Robust GW
Figure 10: (a): 3D shape geometry of the source and target; (b)-(e): visualization of ground truth, initial point obtained from the partial functional map, and the matching results PGW and RGW.
23


Reviews:
[{"review_id": "kGbOI0KWVh", "reviewer": "Reviewer_we1a", "summary": "The authors propose a new variant for unbalanced Gromov-Wasserstein with Kullback-Leibler (KL) divergence for marginal relaxation (Sejourne et al., 2021) by leveraging the outlier-robust approach (Mukherjee et al., 2021). The authors propose an algorithm approach by using Bregman proximal alternating linearization. The authors illustrate the advantages of the proposed method on several experiments.", "questions": "The ideas of the proposed method are clear. It is easy to follow the presentation. However, some parts are needed to elaborate with more details to clarify the claims and the contributions.\n+ The authors should discuss the relation between the proposed outlier-robust GW with the approach in (Sejourne et al., 2021) for unbalanced GW and (Mukherjee et al., 2021) for outlier-robust approach.\n+ As in Definition 2.2, the authors propose to use KL-divergence instead of quadratic KL-divergence (as in Sejourne et al., 2022) due to non-convexity. However, the problem (1) is non-convex. It is not clear the advantages of using KL-divergence over quadratic KL-divergence. Could the authors elaborate more details on this point? Additionally, as  results in Theorem 3.3, could the authors comment the gain of such choice?\n+ The quadratic KL-divergence helps to maintain the homogeneity of GW while KL-divergence will result in non-homogeneous unbalanced GW (especially when input measures have small or large total mass). Could the authors comment on the choice of KL-divergence over the quadratic KL-divergence?\n+ For Theorem 2.3, is the bound tight? Additionally, Theorem 2.3 only address one of the input measures is corrupted, but not two input measures may be corrupted as in problem (1). Is there any limitation for this result? It is better if the authors extend this result for the case as considered in problem (1).\n+ As in line 161-162, Theorem 2.3 gives the upper bound only, it is not clear why “robust GW value that closely approximates the true GW distance (without outliers)”.\n+ It seems that the Proposition 3.2 is a standard optimization result about the unique solution for the root of a monotonic function?\n+ For results in Figures 2 and 3, how to choose the hyperparameters? Do the hyperparameters affect the results?\n+ Could the authors clarify the stopping condition of algorithms for the reported time? (since the problem is non-convex, are any algorithms sensitive to the initialization?)\n+ As in line 285-288, could the authors elaborate how to choose the best result for those hyperparameters?\n+ For results in Figure 5, it is surprising that the hyperparameters have negligible effects on accuracy when one maintains some fixed ratio? However, it is not clear how one can choose a suitable ratio? I suggest that it seems better to extend the range of $\\rho$ and $\\tau$ for results in Figure 5. Could the authors explain results in Figure 5 with more details? \n\nMinor point:\n+ It is better to add the standard deviation for results in Table 1, Figure 4?\n\n---\n\nThank you for the rebuttal.", "limitations": "The authors have discussed limitations of their work. However, there is no discussion about the potential negative societal impact of their work.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "+ The authors propose a new variant for Unbalanced GW with KL divergence for marginal relaxation (Sejourne et al., 2021) by extending the outlier-robust approach (Mukherjee et al., 2021).\n+ The authors propose to use the Bregman Proximal Alternating Linearized Method to optimize the proposed outlier-robust GW.\n+ The authors empirically demonstrate the advantages of the proposed approach.", "weaknesses": "+ The authors leverage the outlier-robust approach (Mukherjee et al., 2021) for unbalanced GW. The proposed method is essentially a new variant of unbalanced GW, but somewhat expected results.\n+ Some claims and experimental results are needed to elaborate with more details (see the Questions part)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your instructive comments. We would like to emphasize that RGW  definitely goes beyond the mere combination of outlier robust OT and unbalanced GW. Our primary contribution lies in the meticulous design of an objective function that offers the advantages of both enhanced model efficiency and computational effectiveness.\n* **Effective Model and Statistical Guarantee:**  Firstly, instead of utilizing the quadratic KL divergence as in unbalanced GW, we leverage the convexity of KL divergence to establish the statistical properties of RGW, leading to an upper bound. This upper bound is controllable through the hyperparameters $\\tau$ and $\\rho$. It serves as a guiding principle to assist us in effectively tuning parameters in practice. Notably, this favorable property ceases to hold for quadratic KL divergence due to its nonconvex nature.\n* **Computational Efficiency:** Secondly, employing KL divergence allows us to solve the subproblems in a highly efficient manner, as we detail in the response to Q2 below. Furthermore,  our RGW formulation is a nonconvex problem, which presents fundamental challenges for algorithm design compared with OT-related problems. To overcome this, we develop an efficient algorithm called BPALM  tailored to RGW.\n* **Exceptional Numerical Results:** Our confidence in the superiority of RGW stems from comprehensive numerical results that highlight its superior performance compared to other methods. \n\nBelow we provide a detailed response to your questions. We believe that our responses will address your concerns, leading to a reevaluation of our paper's contribution and quality.\n\n---\n**Q1:**  The authors should discuss the relation between the proposed outlier-robust GW with the approach for unbalanced GW for outlier-robust approach.\\\n**Response:**  Please refer to the response provided for Q1 in the global response section. We will include a related work section in the updated version.\n\n---\n**Q2:** Could the authors comment on the choice of KL-divergence over the quadratic KL-divergence?\\\n**Response:** First, we chose KL-divergence over quadratic KL-divergence for its computational advantages, allowing convex subproblems with closed-form solutions, unlike the nonconvex quadratic KL-divergence which requires linearization for the subproblems in each iteration. Though linearization increases computational complexity due to the lack of closed-form solutions, it still allows for convergence analysis (like Thm 3.3). Second, KL-divergence provides an upper bound with explicit control through hyperparameters, offering a statistical advantage that would be disrupted by the nonconvex nature of quadratic KL-divergence. Besides, rather than maintain homogeneity, the KL-divergence aligns with our main objective of eliminating outliers and is less sensitive to them, unlike the more outlier-sensitive quadratic KL-divergence.\n\n---\n**Q3:** For Theorem 2.3, is the bound tight? It is better if the authors extend this result for the case as considered in problem (1).\\\n**Response:** For the tightness of the bound in Theorem 2.3, please refer to the responses for Q3 in the global response section. Besides, Theorem 2.3 can be extended to scenarios where both input measures are corrupted. For a thorough discussion of this extension, kindly refer to the responses for Q2 in the global response section.\n\n---\n**Q4:** It seems that Proposition 3.2 is a standard optimization result about the unique solution for the root of a monotonic function?\\\n**Response:** Yes. Most of Newton's method convergence results focus on local convergence. We establish global convergence for convex monotonic functions for completeness.\n\n---\n**Q5:** For results in Figures 2 and 3, how to choose the hyperparameters? Do the hyperparameters affect the results? \\\n**Response:** The choice of hyperparameters in Figures 2 and 3 is obtained using the method discussed in section 4.2, where the hyperparameters affect the outcomes, as highlighted in the analysis in section 4.2 and illustrated in Figure 5.\n\n---\n**Q6:** Could the authors clarify the stopping condition of algorithms for the reported time? (since the problem is non-convex, are any algorithms sensitive to the initialization?)\\\n**Response:** The stopping criterion is determined by $\\max_{i,j} |\\pi_{ij}-\\pi^{prev}_{ij}|$, which is the same as used in UGW. All methods in section 4.2 are sensitive to initialization. We use the same initialization for evaluating their performance stated in lines 289-292.\n\n---\n**Q7:** As in line 285-288, could the authors elaborate on how to choose the best result for those hyperparameters?\\\n**Response:**  We conduct experiments with various combinations of $\\rho$, $\\tau$, and stepsizes within the range specified in lines 285-288 and report the highest accuracy achieved.\n\n---\n**Q8:** Question for Figure 5. It is not clear how one can choose a suitable ratio? I suggest that it seems better to extend the range of $\\rho$ and $\\tau$ for results in Figure 5. Could the authors explain Figure 5 with more details?\\\n**Response:** In Figure 5, the term 'ratio' refers to the subgraph's node proportion to the entire graph, a value dictated by the dataset. We have extended the range of $\\rho$ and $\\tau$, with results in **Figure 2 in the PDF of the global response section**. The accuracy declines when $\\rho$ is too large or too small but is robust between 0.05 and 1, leading us to set $\\rho=0.2$. A similar pattern was observed for $\\tau$ leading us to set $\\tau=0.1$ as the default.\n\n---\n**Q9**: It is better to add the standard deviation for results in Table 1, Figure 4? \\\n**Response:** We have conducted an experiment adding 10\\% pseudo edges to the subgraphs, and the preliminary findings, including the mean accuracy and standard deviation over 5 independent trials, are presented in **Table 2 of the global response section's PDF**. We will include the complete results with standard deviation in the updated paper."}, {"review_id": "XY2U0bxMtA", "reviewer": "Reviewer_1vP9", "summary": "The authors propose a new formulation of unbalanced Gromov-Wasserstein (GW), called Robust Gromov-Wasserstein (RGW). Instead of controlling the deviations of the OT marginals from the prior marginal distributions $\\mu$ and $\\nu$ directly via quadratic phi-divergences like UGW, RGW proposes to use linear phi-divergences (KL) operating on the intermediate learned marginals $\\alpha$ and $\\beta$ which are constrained to be relatively close to $\\mu$ and $\\nu$ w.r.t the KL. It is shown that this new formulation is theoretically better at handling outliers than the UGW under the assumption of Huber's contamination model.\n\nThey then suggest using a Bregman proximal alternating linearisation minimisation (BPALM) algorithm to solve this problem, which is shown to converge asymptotically to a critical point. Finally, the authors show empirically on a synthetic dataset that their method is more robust to outliers, and that it leads to better performance than many competitors on subgraph alignments and partial shape correspondences.", "questions": "I refer the authors to the weaknesses' list above for suggestions and questions that I encourage them to discuss. A last suggestion:\n- I believe both discussions and proofs for the Newton algorithm could be simplified simply observing that $p$ is strictly convex on the positive orthant.", "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 gladly increase my rating. \nThis work has no negative societal impact.", "rating": 7, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "-\tOverall I find the paper well-written and I didn’t find any mistake in the proofs.\n-\tRGW is novel in the Gromov-Wasserstein literature, even if inspired from prior work on unbalanced linear OT as mentioned by authors. The theoretical results on robustness are compeling. The solver proposed by authors seem clearly competitive compared to the one for UGW, while its use is also theoretically supported.\n-\tRGW shows better results than competitors on partial shape matching of both synthetic and real-world data.\n-\tRGW also shows better results than competitors on subgraph alignment problems on many real-world graph datasets. Authors empirical study considers subgraphs of various proportions sampled from given input (full) graphs. RGW shows consistent improvements compared to competitors along these various proportions. Moreover authors show that RGW performances are rather consistent within considered sets of validated hyperparameters.\n", "weaknesses": " - 1. Positioning w.r.t the unbalanced OT literature: \n     - a) *[addressed by authors]* The extension to GW of the work on Wasserstein in [Balaji & al, 2020] should be more explicit. As the latter does not consider regularizing their loss function, you should justify why you do so in your GW setting.\n\n     - b) *[addressed by authors]* The recent paper of [A] provides in a sense a primal point of view of robust GW, It would be good to discuss it and to benchmark it in your subgraph alignment benchmark.\n\n- 2. Robustness guarantees :\n     - a) *[addressed by authors]* Missing proof: Could you provide the proof for UGW in Remark 2.4 ?\n \n     - b) *[addressed by authors]* Tightness: Could you empirically analyze the tightness of both bounds for instance while e.g validating algorithm initializations to get better estimates of various GW terms ? \n\n     - c) *[addressed by authors]* Positioning with recent analysis: Theorem 1 in [Tran & al, 2023] also provides an affine relation of the form: noisy UCOOT <= a * clean UCOOT + b. I believe that this theorem can be easily extended to UGW so could you discuss the relation of this theorem to your bounds ?\n \n- 3. Benchmark: \n     - a) *[addressed by authors]* RGW depends on a lot of hyperparameters. Authors show that their performances were rather consistent for the hyperparameters tau and rho which are involved in the RGW program however it seems that the sensitivity analysis always includes an intensive validation of the BPALM step sizes hyperparameters.  i) Could you clarify if shown results in Section 4.2 always includes this validation of BPALM hyperparameters ? ii) Could you provide a sensitivity analysis to these hyperparameters ?\n\n     - b) *[partially addressed by authors using normalized degrees]* Sensitivity to input graph distribution:  In the context of graph representation learning, an open question relates to a good choice of input graph distribution for tasks like graph partitioning [Xu & al, 2019a ; Chowdhury & al, 2021; Vincent-Cuaz & al , 2022]. Uniform distribution is the common simple choice which seems to be a good enough choice, but power-law distributions based on normalized degrees clearly allow better partitioning performances. Could you integrate these kind of considerations in your benchmark for subgraph alignment ? That would also provide insights on the robustness of RGW to these hyperparameters inherent to all transport problems.\n\n\n[A] Liu, Weijie, et al. \"Robust Graph Dictionary Learning.\" The Eleventh International Conference on Learning Representations. 2022.\n\nNB: the citation model seems to be the wrong one for Neurips, currently names and dates instead of simple numbers.\n\n*Update after rebuttal : The authors have 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 5 (borderline accept) to 7 (accept).*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful review and the constructive feedback you have provided.  In what follows, we answer the following questions pointed out in your review. \n\n---\n**Q1:** The extension to GW of the work on Wasserstein in [Balaji et al, 2020] should be more explicit. As the latter does not consider regularizing their loss function, you should justify why you do so in your GW setting.\\\n**Response:** Please refer to the response provided for Q1 in the global response section. We will include more explanations about why we relax the hard marginal constraints in the updated paper.\n\n---\n**Q2:** The recent paper of [A] provides in a sense a primal point of view of robust GW, It would be good to discuss it and to benchmark it in your subgraph alignment benchmark.\\\n**Response:** We would like to acknowledge that the problem addressed in [A] is focused on tackling the inaccuracy of pairwise relation matrices (PRM), the matrices $D$ and $\\bar{D}$ in Eq. (3). The authors propose an approach by introducing a perturbation matrix to allow PRM to vary in a neighborhood of the observed PRM, seeking a transport plan that minimizes transportation costs for all perturbations. While their idea differs from ours, we recognize its potential to help reduce the impact of outliers by perturbing the distance between clean samples and outliers. In our paper, we plan to include RGWD introduced in [A] as one of the baselines in the subgraph alignment task. We have already provided preliminary results of RGWD on the 50\\% subgraph alignment in the following table, and we plan to present the complete results in the updated paper.\n\nTable: The performance of RGWD of 50\\% subgraph on datasets Synthetic, Proteins and Enzymes and Douban.\n\n|     | Synthetic |     | Proteins-1 |     | Proteins-2 |     | Enzymes |     | Douban |     |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| Method | Acc | Time | Acc | Time | Acc | Time | Acc | Time | Hit@1 | Hit@10 |\n| RGWD | 16.68 | 955.40 | 27.94 | 4396 | 59.69 | 3586 | 30.35 | 2629 | 4.11 | 16.46 |\n| Our RGW | 94.44 | 361.44 | 53.30 | 834.76 | 69.38 | 466.91 | 63.43 | 293.84 | 75.58 | 96.24 |\n\n---\n**Q3:** Missing proof: Could you provide the proof for UGW in Remark 2.4?\\\n**Response:** In Remark 2.4, the case where only $\\mu$ is corrupted is considered. Given that $\\pi_c$ is a feasible solution to the UGW problem, plugging it in yields $d_{\\textbf{KL}}^\\otimes (\\nu,\\nu)=0$, leading to the desired result.\n\n---\n**Q4:** Tightness: Could you empirically analyze the tightness of both bounds for instance while e.g validating algorithm initializations to get better estimates of various GW terms?\\\n**Response:** We have conducted experiments to investigate the tightness when varying the relaxation parameter $\\rho$ and penalty parameter $\\tau$. For a detailed explanation and insights into these experiments, please refer to our response to Q3 in the global response section.\n\n---\n**Q5:** Positioning with recent analysis: Theorem 1 in [Tran et al., 2023] also provides an affine relation of the form: noisy UCOOT <= a * clean UCOOT + b. I believe that this theorem can be easily extended to UGW so could you discuss the relation of this theorem to your bounds?\\\n**Response:** Thanks for pointing out this issue. We would like to emphasize that the baseline used in [Tran et al., 2023] is UGW but the baseline used in Remark 2.4 is GW. Specifically, the inequality constructed in [Tran et al., 2023] on the right-hand side is an affine function of UGW, whereas, in Remark 2.4, the right-hand side of the inequality is an affine function of GW. The result in [Tran et al., 2023] doesn't directly correlate UGW and GW as mentioned briefly in lines 42-44. We address this by establishing the UGW and GW relationship in Remark 2.4.  Theorem 2.3 establishes that RGW is robust to outliers and further establishes a clear relationship between RGW and GW. We will incorporate your suggestions to provide a more detailed exploration of this point in our discussion.\n\n---\n**Q6:** However it seems that the sensitivity analysis always includes an intensive validation of the BPALM step sizes hyperparameters. i) Could you clarify if shown results in Section 4.2 always includes this validation of BPALM hyperparameters? ii) Could you provide a sensitivity analysis to these hyperparameters?\\\n**Response:** In the subgraph alignment task, we have used constant values for the stepsizes $t_k$, $c_k$ and $r_k$. We have conducted a sensitivity analysis for these parameters, with the findings detailed in **Tables 3 and 4 in the PDF of the global response section**. Specifically, **Table 3** reveals that RGW achieves its highest accuracy with $t$ in the range of 0.01 to 0.05, allowing us to select $t=0.01$ as the default. **Table 4** further indicates that accuracy is not significantly affected by variations in $c$, leading us to set $c=0.1$ as the default.\n\n---\n**Q7:** Sensitivity to input graph distribution: Power-law distributions based on normalized degrees clearly allow better partitioning performances. Could you integrate these kind of considerations in your benchmark for subgraph alignment? That would also provide insights on the robustness of RGW to these hyperparameters inherent to all transport problems.\\\n**Response:** Thank you for your suggestion. In **Table 1 of the PDF in the global response section**, we present the results of using the normalized degree (a special case of power-law distribution) as the input graph distribution for the 50\\% subgraph alignment task. The findings affirm that our proposed RGW outperforms other methods in accuracy when using normalized degrees as marginal distributions. The complete results will be included in our updated paper.\n"}, {"review_id": "9Yv5ZEdGs9", "reviewer": "Reviewer_Lqoh", "summary": "The authors propose a robust version of the Gromov Wasserstein (RGW) distance and theoretically bound their RGW distance applied to noisy distances in terms of the GW distance between the clean distributions and an error term depending on the choice of parameters in RGW and the distance between the clean distribution and the outlier distribution. The authors develop an algorithm for computing the RGW distance using Sinkhorn’s algorithm and Newton’s method.", "questions": "(1) How can one estimate the GW distance between clean distribution?\n(2) Can Theorem 2.3 be extended to where \\nu also has an outlier distribution?\n(3) An obvious question, but can one hope to have a lower bound on the RGW distance? Numerically, I would have thought this would be fairly simple to investigate (for example in the context of the examples in Section 4.1) by computing GW of the clean distributions and then varying \\rho in the RGW to see how close the upper bound in Theorem 2.3 comes to RGW.", "limitations": "The authors close the paper by discussing the heavy computational cost of the method.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The theory provides guidance on how to choose parameters in order to get a good approximation (at least an upper bound) of the RGW distance in terms of the GW between clean distributions.", "weaknesses": "To get the upper bound (mentioned above) one needs to know the GW distance between the clean distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your dedicated review of our manuscript and the valuable feedback you've provided. In the following, we will address the questions and points you've raised in your review.\n\n---\n**Q1:** To get the upper bound (mentioned above), one needs to know the GW distance between the clean distributions. How can one estimate the GW distance between clean distribution?\\\n**Response:** The primary goal of RGW is to estimate the GW distance between clean distributions in the presence of outliers. Theorem 2.3 establishes that RGW provides a lower bound on the true GW distance between clean distributions and offers guidance on parameter selection for obtaining a tighter lower bound of the GW distance without outliers. This indicates RGW's ability to estimate the GW distance between clean distributions to some extent. BPALM can be efficiently utilized to compute RGW, enhancing its practicality for real-world applications.\n\n---\n**Q2:** Can Theorem 2.3 be extended to where $\\nu$ also has an outlier distribution?\\\n**Response:** Yes. Please refer to the response provided for Q2 in the global response.\n\n----\n**Q3:** An obvious question, but can one hope to have a lower bound on the RGW distance? Numerically, I would have thought this would be fairly simple to investigate (for example in the context of the examples in Section 4.1) by computing GW of the clean distributions and then varying $\\rho$ in the RGW to see how close the upper bound in Theorem 2.3 comes to RGW.\\\n**Response:** For general scenarios, where the GW distance between clean samples is not necessarily zero, the construction of a lower bound represents a non-trivial challenge. This difficulty stems from the nonconvexity of RGW. Notably, even in the case of robust OT [Balaji et al., 2020], which is a convex problem, only an upper bound has been established.  Following your suggestion, we conducted an experiment to analyze how the function value of RGW and its upper bound changes when varying $\\rho$ of the toy example in Section 4.1. In **Figure 1(b) in the PDF in the global response section**, the results demonstrate that the function value of RGW and the upper bound converge to zero as $\\rho$ increases, which aligns with the theoretical perspectives presented in Theorem 2.3. While the building of a precise lower bound for RGW remains a complex task, it will be a direction for our future research. Please refer to the response for Q3 in the global response for further discussion on the tightness of the bound in Theorem 2.3 and the lower bound."}, {"review_id": "0U1115ivIQ", "reviewer": "Reviewer_YxnT", "summary": "This paper proposes a Robust Gromov-Wasserstein (RGW) distance to tackle the high sensitivity to outliers of common GW distances. The key idea is to relax both the marginal distribution and the transport plan based on the KL divergence. An algorithm based on BPALM is further proposed with guaranteed convergence. Theoretical analysis demonstrates the robustness to Huber-$\\epsilon$ contamination, and empirical results demonstrate the effectiveness in partial correspondence with the presence of outliers.", "questions": "- RGW imposes an extra relaxation on the marginal distribution, i.e., $KL(\\alpha|\\mu)<\\rho$. Comparing with UGW (UGW is equivalent to $GW_{0,0}$), can you illustrate the benefit/intuition of imposing this extra relaxation?\n- For Theorem 2.3, it is possible to have a similar result when both marginals $\\mu, \\nu$ are contaminated?\n- Line 161-162: the statement “By appropriately selecting …  closely approximates the true GW distance (without outliers).” is inaccurate. Setting the second term in Theorem 2.3 only indicates achieving a tighter upper bound but does not necessarily indicates a better approximation.\n- For eq. (4-6), why the proximal operator is $KL(\\pi|\\pi^k)$ in Eq.(4) but $KL(\\alpha^k|\\alpha)$ in Eq.(5)? Since KL divergence is not symmetric, the authors should justify their choices here.\n- Experiments:\n  - It is encouraged to show an empirical evaluation on the convergence of the proposed BPALM.\n  - A key property of RGW is being robust to outlier. In the subgraph alignment part, will RGW achieve more significant improvements when the query graph is not an exact subgraph, but rather a subgraph with noises (e.g., pseudo nodes/edges) added or deleted?\n  - For table 1, why different metrics are used for different datasets?\n  - For figure 5, It would be good to show the results with $\\rho=0$. i.e., no relaxation on the marginal, to justify the effect of marginal relaxation.\n- Typo: the abbreviation for fused Gromov-Wassertein should be FGW instead of FW.\n", "limitations": "The authors properly addressed the limitations in the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and easy to follow, with theoretically and empirically sounded analysis.\n- The paper tackles the crucial robustness problem in GW distances, which could potentially benefit many OT-related research.\n- Experiment results demonstrate the effectiveness of RGW on the partial correspondence task, a task that is hard to addressed by most OT methods.\n", "weaknesses": "- A section on related works is **strongly encouraged**. It would be beneficial to discuss the relation/superiority of the proposed RGW compared with other relaxed GW methods, e.g., UGW and srGW.\n- Some modifications in the experiment part are encouraged for better presentation. See details in the “Questions” section.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback. In the upcoming sections, we will address the questions you've raised.\n\n---\n**Q1:** A section on related works is strongly encouraged. It would be beneficial to discuss the relation/superiority of the proposed RGW compared with other relaxed GW methods, e.g., UGW and srGW.\\\n**Response:** Thanks for your suggestion. We have taken it into account and will include the section mentioned in the response for Q1 in the global response part in our updated version.\n\n---\n**Q2:** RGW imposes an extra relaxation on the marginal distribution, i.e., $KL(\\alpha | \\mu) < \\rho$. Comparing with UGW (UGW is equivalent to $\\textnormal{GW}^{\\textnormal{rob}}_{0,0}$), can you illustrate the benefit/intuition of imposing this extra relaxation?\\\n**Response:** The extra relaxation in RGW draws inspiration from robust OT [Balaji et al., 2020], optimizing the transport plan and selecting the best marginal distribution within a neighborhood of the given distribution. Perturbed marginal distributions effectively re-weight the samples, reducing the impact of outliers. Introducing this additional relaxation enhances RGW's robustness to the hyperparameters $\\rho$ and $\\tau$, as demonstrated in Section 4.2. Unlike UGW, which is sensitive to penalty parameters, balancing outlier impact reduction and the control of marginal distortion in the transport plan (lines 44-45), RGW achieves greater flexibility by controlling marginal distortion through $\\tau$ and reducing outlier impact using $\\rho$.\n\n---\n**Q3:**  Line 161-162: the statement “By appropriately selecting … closely approximates the true GW distance (without outliers).” is inaccurate. Setting the second term in Theorem 2.3 only indicates achieving a tighter upper bound but does not necessarily indicates a better approximation.\\\n**Response:** Thank you for pointing out the inaccuracy in our statement. We will correct this in our revised paper to reflect that the chosen parameters help us obtain a tighter upper bound, rather than a closer approximation to the true GW distance. For a more comprehensive discussion on the tightness of the bound in Theorem 2.3, please refer to our answer to Q3 in the global response section.\n\n---\n**Q4:**  For Eq. (4-6), why the proximal operator is $KL(\\pi | \\pi^k)$ in Eq.(4) but $KL(\\alpha^k|\\alpha)$ in Eq.(5)? Since KL divergence is not symmetric, the authors should justify their choices here.\\\n**Response:** The choices facilitate efficient computation in solving the subproblems. Using $KL(\\pi | \\pi^k)$ in Eq. (4) allows us to directly adopt the Sinkhorn algorithm while employing $KL(\\alpha^k|\\alpha)$ in Eq. (5) enables a closed-form solution. Importantly, these choices do not affect the convergence results (Theorem 3.3) and provide computational benefits.\n\n---\n**Q5:** It is encouraged to show an empirical evaluation on the convergence of the proposed BPALM.\\\n**Response:** Thanks for your suggestion. We have taken your advice and included plots that illustrate the convergence using different step sizes. You can find these plots in **Figure 3 of the PDF in the global response section**.\n\n---\n**Q6:** A key property of RGW is being robust to outliers. In the subgraph alignment part, will RGW achieve more significant improvements when the query graph is not an exact subgraph, but rather a subgraph with noises (e.g., pseudo nodes/edges) added or deleted?\\\n**Response:** We have conducted an experiment adding 10\\% pseudo edges to the subgraphs, and the preliminary findings are in **Table 2 of the global response section's PDF**. These results highlight that RGW significantly outperforms other methods on all the datasets even in the presence of noise. The complete results will be included in our updated paper.\n\n---\n**Q7:** For table 1, why different metrics are used for different datasets?\\\n**Response:**  Hit@1 is equivalent to accuracy, and we use the metric Hit@k for the Douban dataset, which aligns with previous work s for consistency [A, B].\\\n[A] Gao, Ji, Xiao Huang, and Jundong Li. \"Unsupervised graph alignment with Wasserstein distance discriminator.\" Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery \\& Data Mining. 2021.\\\n[B] Tang, Jianheng, et al. \"Robust attributed graph alignment via joint structure learning and optimal transport.\" arXiv preprint arXiv:2301.12721 (2023).\n\n---\n**Q8:** For Figure 5, It would be good to show the results with $\\rho=0$. i.e., no relaxation on the marginal, to justify the effect of marginal relaxation.\\\n**Response:** Thanks for your suggestion. We have included these results in **Figure 2 of the PDF in the global response section**. The comparison clearly shows that marginal relaxation mitigates the influence of outliers. Specifically, the accuracy of $\\rho$ in the range of 0.1 to 1 is significantly higher than when $\\rho=0$, justifying the effect of marginal relaxation in our model.\n\n---\n**Q9:** The abbreviation for fused Gromov-Wasserstein should be FGW instead of FW.\\\n**Response:** Apologies for any confusion. In Table 1, the term ``FW'' refers to the Frank-Wolfe method introduced in [Titouan et al., 2019]."}]

Author rebuttal:
Thanks for all the insightful feedback. We summarize the common questions and provide corresponding responses in this global response section. We'd rather happy to take any other questions during the discussion period.

---
**Q1:** A section focusing on related work should be included to explore and compare the proposed RGW method with other relaxed GW approaches and robust OT techniques.\
**Response:** Thanks for your suggestions. Our introduction of relaxed distributions to handle outliers draws inspiration from robust OT techniques [Balaji et al., 2020]. Unlike robust OT, which is a convex optimal transport problem, RGW is non-convex, presenting algorithmic challenges. RGW replaces hard marginal constraints with a penalty function, inspired by UGW [Sejourne et al., 2021], to mitigate outlier impact. Notably, RGW offers improved robustness and efficiency compared to UGW, which is sensitive to penalty parameters and lacks an efficient algorithm as discussed in lines 44-48. Moreover, srGW corresponds to an extreme case of UGW, achieved by setting one of the penalty parameters to infinity and the other to 0. For a detailed discussion, we plan to include a paragraph titled ``Related Work'' for a comprehensive discussion of robust OT and the relationship between RGW and relaxed GW methods in the updated version.

---
**Q2:** Can Theorem 2.3 be extended to the case where both $\mu$ and $\nu$ are contaminated with outliers? \
**Response:**  Yes. Consider $\mu = (1-\epsilon_1)\mu_c + \epsilon_1 \mu_a$ and $\nu = (1-\epsilon_2)\nu_c + \epsilon_2\nu_a$. Utilizing the same notations and techniques as in the proof of Theorem 2.3, we obtain the following inequality by plugging in $\pi_ c$: \
$\text{GW}^{\text{rob}}_{\rho_1,\rho_2} (\mu, \nu)\leq\inf _{\alpha\in\mathcal{P}(X), \ \beta\in \mathcal{P}(Y)} \text{GW}(\mu_c, \nu) + \tau_1 d _{\textbf{KL}}(\mu _c,\alpha) + \tau_2 d _{\textbf{KL}}(\nu _c,\beta) $ \
$ \qquad\qquad\qquad\qquad\text{s.t.} \\ d _{\textbf{KL}}(\mu,\alpha) \leq \rho_1,~d _{\textbf{KL}}(\nu,\beta) \leq \rho_2.$\
Subsequently, employing the same technique as in the proof of Theorem 2.3 to minimize the right-hand side, we obtain \
$\text{GW} _{\rho_1,\rho_2}^{\text{rob}} (\mu, \nu) \leq \text{GW}(\mu_c, \nu_c)+\max \left(0,\epsilon_1-\frac{\rho_1}{d _{\textbf{KL}}(\mu_a,\mu_c)}\right)\tau_1d _{\textbf{KL}}(\mu_c,\mu_a)+\max \left(0,\epsilon_2-\frac{\rho_2}{d _{\textbf{KL}}(\nu_a,\nu_c)}\right)\tau_2d _{\textbf{KL}}(\nu_c,\nu_a)$.

---
**Q3:** Tightness of the upper bound in Theorem 2.3 and lower bound of RGW. \
**Response:** Thank you for raising this insightful question regarding the tightness of the upper bound in Theorem 2.3 and the lower bound of RGW. 
*  **Tightness of Upper Bound:** Since our primary focus is on cases where the GW distance between clean samples is zero or near zero (due to noise), such as in the partial shape correspondence and subgraph alignment tasks, there can be an isometric mapping from the query subgraph to part of the entire graph. By choosing an appropriate value for $\rho$ (as discussed in lines 160-161), the upper bound becomes the GW distance between clean samples, which is zero. As RGW is always nonnegative, the upper bound is tight in this context.
* **Lower Bound:** Addressing the lower bound for general cases, where the GW distance between clean samples is not necessarily zero, presents a non-trivial challenge due to the nonconvexity of RGW. Even robust OT [Balaji et al., 2020], a convex problem, only provides an upper bound. Building the lower bound is complex and will be considered as a potential direction for future research.
* **Empirical Insights:** We have empirically explored the function values of PGW, UGW, and RGW with varying outlier ratios in a toy example (Section 4.1), as shown in **Figure 1(a) in the PDF in the global response section**. The findings confirm that RGW's value can remain close to zero as the ratio of outliers increases. Moreover, **Figure 1(b) in the PDF** depicts the function value of RGW and its upper bound as $\rho$ varies. The function value of RGW and its upper bound decrease, converging to zero as $\rho$ increases. This observation provides a valid corroboration of Theorem 2.3. Furthermore, We have also examined how UGW and its upper bound change with $\tau$ as shown in **Figure 1(c) in the PDF**, noting that the value of UGW and its upper bound increase with enlarging $\tau$.  Unlike RGW, UGW's $\tau$ must balance between the reduction of outlier impact and the preservation of marginal distortion in the transport plan. This demands a careful balance and cautions against setting $\tau$ excessively close to zero, which could lead to over-relaxation.

Meta-review: The authors proposed a novel robust GW with a computationally efficient solver. Reviewers mostly appreciated the paper but had a few concerns in their reviews. 

The authors did a fairly convincing and detailed rebuttal for most of the questions and provided several new experimental results in the rebuttal PDF. This was much appreciated by the reviewers and two of them increased their score. 

For these reasons I propose to accept the paper but strongly suggest that the authors take into account the comments form the reviewers and integrate the new results and discussion in the main paper and supplementary since it clearly makes the paper stronger.
Decision: Accept (spotlight)