Semidefinite Relaxations of the Gromov-Wasserstein Distance
Authors: Junyu Chen
Binh Nguyen
Shang Hui Koh
Yong Sheng Soh
Venue: NeurIPS 2024 poster (2024)
Keywords: optimal transport
gromov-wasserstein
semidefinite programming
optimization
Primary area: optimization
TL;DR: We propose a semi-definite programming (SDP) relaxation of the GW distance.

Abstract: The Gromov-Wasserstein (GW) distance is an extension of the optimal transport problem that allows one to match objects between incomparable spaces.  At its core, the GW distance is specified as the solution of a non-convex quadratic program and is not known to be tractable to solve.  In particular, existing solvers for the GW distance are only able to find locally optimal solutions.  In this work, we propose a semi-definite programming (SDP) relaxation of the GW distance. The relaxation can be viewed as the Lagrangian dual of the GW distance augmented with constraints that relate to the linear and quadratic terms of transportation plans. In particular, our relaxation provides a tractable (polynomial-time) algorithm to compute globally optimal transportation plans (in some instances) together with an accompanying proof of global optimality.  Our numerical experiments suggest that the proposed relaxation is strong in that it frequently computes the globally optimal solution.  Our Python implementation is available at https://github.com/tbng/gwsdp.

Semidefinite Relaxations of the Gromov- Manno--Wassersteiin Distance
Junyu Chen
Binh T. Nguyen
Shang Hui Koh
Yong Sheng Soh
Department of Mathematics National University of Singapore
chenjunyu@u nus edu, binhnt @nus. edu. .dw..e, matsysssususs wwwpeyyssnuueeu.......
Abstract
The Waaser--ssserttiin (GW) distance is extension of the optimal transport problem that allows one to match objects between incomparable spaces. At its core, the GW distance is specified gram and is not known to be tractable to solve. In particular, existing solvers for only able to find locally optimal solutions. In this work,
the solution of non-convex quadratic pro-
the GW distance we propose a semi-definite programming (SDP) relaxation the GW distance. The relaxation can be viewed as the Lagrangian dual of the GW distance aug- mented with constraints that relate to the linear and quadratic terms of transporta- relaxation provides a tractable (polynomial -ime))
tion plans. In particular, algorithm to compute globally optimal transportation plans (in some instances) together with accompanying proof of global optimality. Our numerical exper- iments suggest that the proposed relaxation is strong in that it frequently com- putes the globally optimal solution. Our Python implementation is available com/tbng/ htep//bbgg///ppp gwsdp.
Introduction
The optimal transport (OT) problem concerns the task of finding transportation plan between two probability distributions to minimize some costs. The problem has applications in a wide range of scientific and engineering applications. For instance, in the context of machine learning, the OT problem forms the backbone of recent breakthroughs generative modeling (Arjovsky al., 2017: Liu et al., 2022: Lipman et al., 2022), natural language processing (Kusner et al., 2015), domain adaptation (Courty et al., 2017), and single-cell alignment (Schicbinger et al., 2019; Bunne et al., 2023, 2024).
Let E Em and 8 E Σm be discrete probability distributions over a metric space here Σm {a E Rr 0; = 1} denotes the probability simplex. Let C' E Rm*n be the matrix such that C.,, models the transportation cost between points z; and Yj 3. The (Kantorovich) formulation of the discrete OT problem (Kantorovich, 1942; Villani et al., 2009; Santambrogio, 2015; Peyré et al., 2019) is defined as the solution of the following convex optimization instance
def. argmin (C,T). xEll(a,,)
(1)
Here, TT),,8) { E m 11, a, T 1m probability distributions a, 3 E Σm. while Im E R. denotes the vector of ones. The OT problem (1) is instance of linear program (LP), and hence admits global minimizer.
B} denotes the set of couplings between
Equual contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

One limitation of the classical OT formulation in (1) is that the definition of the cost matrix C requires the probability distributions a and 5 to reside in the same metric space. This is problematic in application domains where we wish to compare probability distributions in different spaces, in which case there is no meaningful way to describe the cost of moving from one location to another. Such settings arise frequently in shape comparison and graph matching applications, for example.
To address such scenarios, the work Mémoli (2011) formulates an extension of the OT problem known as the Gromov-Wasse Wasserstein distance (GW) whereby one can define an analogous OT problem given knowledge of the cost matrices for the respective spaces where a and 3 reside in. More concretely, let the tuple (C, a) E IR mm Em denote a discrete metric-measure space. Given smooth, differentiable function & discrete metric-measun spaces (C, and B) is defined by
RR R. the
distance between two
GW D, def. min E(Ci, DaI) = =EI((,,))
min (L(C, (T,T). =EI)(..8)
(GW)
Here, the transportation cost is specified by the four-way tensor that measures the discrepancy be- tween the metrics C' and D
L(C, D),aA [(Ca,, Dj,).
(2)
The squared loss error, for instance, is a common choice. Following Peyré et al. (2016), we define the massor-matrix multiplication by
L 2 TkJ
def.
Σ L.J.A.ITT..
k.
The GW distance has been applied widely to machine learning tasks, most notably on graph learning (Vayer et al., 2019a; Xu et al., 2019; Vincent-Cuas et al., 2021, 2022). It is an instance of a quadratic program (QP) - these are optimization instances in which we minimize a quadratic objective subject to some linear inequalities. To see this, one can re-write the objective in (GW) in terms of vectorized matrices
min (vec(TT), L vec(T)) s.t. 11(a,))
(GW+)
Here, (Lij,a)iif. E mm denotes the flattened 2-dimension tensor of L, while the vectorization of a matrix π E Rmmx given by
vec(IT)
def,
[1I1 T21,..., mml .... Tmn] E Rm
The constraint E II( 3) is convex, and in fact linear. On the other hand, the matrix L need not be positive semidefinite, and as such, the QP instance in (GW+) is non-convex in general. In fact, in the cases where the matrix L arises as the difference cost matrices (2), never positive semidefinite as these are zero on the diagonal while the off-diagona entries are non-negative.
2 Main Contributions
The main contribution of this work to propose a strong semidefinite programming (SDP)-based relaxation for the Gromov-Wasee Wasserstein distance that leads to globally optimal solutions in many instances. Concretely, let (Nsdp, Psdp) denote an optimal solution the following
GW-SDP(C,D,a,
min =ER"Xn
(L, P)
PER PaRmaxIi
P
vec(*)
s.t.
vec(T))
1
1 0
(GW-SDP)
E II((x,3) 33)
Pvec(ei1 vec)(())) E [m]
Pvec(1 B,vec(T)) [m]
P20 0
Here, e; denotes the standard basis vector whose i-th entry is 1. This relaxation can be viewed as the Lagrangian dual of the GW problem augmented with constraints that relate the lincar and quadratic

---

terms of transportation plans (we discuss these aspects in greater detail in Appendix B). A simpler way to express the condition Pvec(e; a,vec( (T) is note that
Prec(e, 1,,) = a, vec(T)
Σ, P(s), = TR
(vec(1me)) 8g vec(T)
We begin by noting basic observation: Let
II(a, be transportation plan. (TT, vec(TT) (ve(()) is feasible solution to (GW-SDP) since
Then the tuple (m,, P) vec(T)vec(T)) vec(e; ( = vec(T)( m (ec(T) (.) ) = a,vec(T). The inequalities for 3 follow analogously. This implies that the optimal value of (GW-SDP) is lower bound the GW problem (GW): Let n' denote an optimal solution to the GW problem (note: this is (GW),
which is equivalent (GW+)). By recalling that the tuple (vec(x*), veo( (==))="((=**)) is a feasible solution to (GW-SDP), one has
(Psdps L) S (veo(T"), L vec(==)) = (m x*)
The inequality (3) provides with principled way of certifying global optimality of given trans- portation plan. Let E II 3) be an arbitrary transportation plan. A natural approach to quantify the quality of is compare its objective value with the optimal choice:
{T, L x)
Apx. (T)
This ratio is at least one and is equal to one if ı is also globally optimal. consequence of (3) is the following upper bound
( (Tsdp:: L & Tsdp)
Apx. Ratio(Tedp))
S
(4)
(Pedp: L)
Note that all the quantities in the RHS can be computed efficiently as the solution of a SDP. Suppose are able to do so, and in the process evaluate the RHS to be equal one. Then, we have a proof that Tadp is the global optimal solution to the GW problem. In recent work that appeared during the reviewing process of our work. the GW problem is shown to intractable in general (Kravtsova, 2024). What our discussion shows is that it is possible, in some instances, to obtain the globally optimal solution via a polynomial-time algorithm by solving (GW-SDP), and with guarantee that the obtained solution is indeed globally optimal. In fact, the instances for which one can obtain an upper bound equal to one using (GW-SDI CGW-SDP) not as far-fetched as one might think: our numerical experiments in Section 4 show that this happens quite often, and especially so whenever m n. No restrictions on cost tensor. One of the strengths of our proposed SDP relaxation that it is valid for all cost tensors L. This stands in contrast with other methods like the entropic GW (Peyré al., 2016), which is only applicable to the cost that can be decomposed to specific form such as the & or discrete KI. loss.
3 SDP Relaxations of QPs
We motivate the relaxation in (GW-SDP). The starting point is to recognize that the GW problem is an instance of QPs these optimization instances of the form
min J ER
T Ax + 26 +
s.t.
Bx S d.
(5)
QPs are an important class of optimization problems. If the matrix is PSD, then the objective is convex, and the QP instance can be solved tractably using standard software (Nocedal and Wright, 2006). The problem becomes difficult if A contains negative cigenvalues. The general class of QPs is NP-hard; for instance, it contains the problem of finding the maximum clique of a graph (Motzkin and Straus, 1965). In fact, the presence of a single negative eigenvalue in is sufficient to make the class of QPs NP-hard (Pardalos and Vavasis, 1991). The typical approach to solving a quadratic program exactly is via a branch-and-bounth type of algorithm. Other approaches include relating QPs to the class of co-positive programming, mixed integer linear programming, and deploying SDP relaxations (Bomze and de Klerk, 2002) typically, these methods are used as a sub-routine within a mranch-and-bouae procedure.
3

---

Standard SDP Relaxation. The first step of SDP relaxation is to express the quadratic terms with a PSD matrix whose rank is one. Concretely, the QP instance (5) equivalent to the following:
min x ER X ER
tr (r(AX) 2b x +c
s.t.
Bx I d X σ
x.
X x 1 =1
= 0, rank
1
This optimization instance is not convex because of the rank-one constraint. The second step is to simply omit the rank constraint, which yields a semidefinite program and therefore is convex. This is the standard SDP relaxation for QPs (the technique applies more generally quadratically constrained quadratic programs QCQPs).
By applying the same sequence of steps to (GW+), the standard SDP relaxation one arrives at is the following:
min rERmxn, PERmaxxm
(L,
s.t.
vec(1T) π E ({(,
P vec(T)
= 0
(6)
Problem (6) a tractable convex semidefinite programming, which can be efficiently solved in polynomial time. If the solution to (6) (and the subsequent SDP relaxations we introduce) has a rank equal to one, we would have solved the original GW problem (GW). Unfortunately, the feasible region of P in (6) is not compact, and the optimal value to (6) is unbounded below in general.
Proposition 3.1. The optimization instance (6) is unbounded below.
Tightening the Relaxation. As such, it is necessary to augment (6) with additional constraints to further strengthen the relaxation. Recall that the relaxation (6) is exact P = vec(=)vee(r)) Therefore, simple way to improve the relaxation is to add any linear constraints that is satisfied by solutions of the form (IT, P) = (TT, vec(T)vec(T))
First, π 0 for all π E II(, 8), and hence ree(T))ecd)
0. This means we may freely impose
P20 0.
(Nng.)
Second, note that E; THy = THe E, niy) = T21 Subsequently, we may impose Σ, P(.s).a.)) By This leads to the following set of equalities:
(vec(e; 1 = vece)()), E [m],
Pvec(1 (ee() = 3,vec(=), E [m]
(Mar.)
The proposed SDP relaxation (GW-SDP) is precisely (6) with the additional constraints (Nng.) and (Mar.). In addition, the set of matrices P satisfying (Mar.) have trace most one. Hence the feasible region is a subset of PSD matrices with trace at most one, which is compact.
Relation to the QAP. We point out that the constraints (Nng.) and (Mar.) have been previously pro- posed for a different but closely related problem known as Quadratic Assignment Problem (QAP) (Dym et al., 2017; Kezurer al., 2015; Zhao al., 1998). Mathematically, the QAP problem be viewed as equivalent to (GW+) but with the additional restriction that m = n and that π is permu- tation matrix. The work in Zhao al. (1998) proposes SDP relaxation that is effectively equivalent to (GW-SDP) but with additional linear equalities implied by orthogonality कग = π works Dym et al. (2017); Kezurer al. (2015) subsequently build on the ideas in Zhao et al. (1998) and propose more scalable alternatives while providing tight relaxations.
T. The
The key difference between the QAP and the GW problem we investigate is that is not necessarily a permutation matrix the GW problem, and necessarily so if m * n. As such, the relaxation in Zhao et al. (1998) is invalid. Our contribution is recognize that, by omitting the constraints corresponding to orthogonality. one obtains an SDP relaxation that now becomes valid for the GW problem, which leads to good practical performance.
No need for rounding. One important property of the relaxation (GW-SDP) is that the output will always be feasible transportation plan in I1(a, 3). This means that no additional rounding

---

is necessary. This is vastly different from combinatorial optimization problems including the QAP where the optimal solution to the relaxation not guaranteed to be feasible solution, and additional rounding steps may be necessary.
4 Numerical Experiments with Off-the-shelf Convex Solvers
In this section, implement our proposed SDP relaxation using off-the-shelf solver. We com- pare our method with the Conditional Gradient (CG-GW) solver for finding local solutions (Vayer al., 2019a), and the Sinkhorn projections solver for computing solutions the entropic GW (eGW) problem by Peyré et al. (2016). Both of the latter are implemented in the Python Optimal Transport library (PythonOT, Flamary et al. 2021). The goal is show that our proposed SDP relaxation frequently computes the global optimal transportation plan whereas existing methods fre- quently do not.
In what follows, we will use the Z-Gromov-Wssserteiin distance, i.e. the cost function is squared Euclidean norm. We solve the GW-SDP instance implemented in CVXPY (Diamond and Boyd, 2016) using the SCS and MOSEK solvers (ApS, 2022; O' O'Donoghue et al., 2016).
4.1 Matching Gaussian Distributions
In this example, we estimate the GW distance between two Gaussian point clouds, one in R²a and the other in RS. A visualization of this dataset can be found in Figure la. The classical optimal transport formulation such as the likes of Wasserstein-2 distance does not apply because the two point clouds belong to different spaces.
As seen in a qualitative demonstration of Figure 1b, our algorithm returns optimal transport plans that are as sparse as the transportation plans obtained via the Conditional Gradient descent solver of Python OT for GW distance (CG-GW). We also vary the number of sample points and calculate the value of the objective function (Tr, L & .²). As shown in Figure 2a, the transport plans obtained by (GW-SDP) consistently returns smaller objective value (orange line) than those obtained via the GW- CG counterpart from PythonOT (blue line) and its entropic regularization (green line). This shows that the transport plans computed by PythonOT, for instance, are in fact frequently sub-optimal.
In Figure 2b, we plot the estimated approximation ratio across different numbers of sample points. We notice that in this scenario of Gaussian matching, the estimated approximation ratio is close to 1.0 in most instances this tells us that the (GW-SDP) frequently computes globally optimal transportation plans. In contrast, local methods such as PythonOT often do not. Note that we also observed the sparsity of the SDP-GW transport plans in this varying scenario.
CAGINGGU
(a) Datasets visualization
(b) Solution of the OT plans
Figure 1: Left: source distribution (2D, blue dots) and target distribution (3D, red dots). For ease of visualization, lift the source 2² mm--spacs into target R3 by padding the third coordinate to zero Right: OT solutions of GW-SDP (our algorithm), CG-GW (conditional gradient descent, default solver of PythonOT) and entropic OT solver. The OT plans from GW-SDP is almost sparse in the same manner to CG-GW, while the eGW is not.
Scenario where m + n. The bulk of our experiments focus on the setting where m n. We performed an experiment where m a nı the number of samples in one distribution is fixed (n 8) and we vary the number of samples m in the other distribution. From our results in Figure 3, we notice that the relaxation is exact whenever m is multiple of n. On the other hand, when m not multiple of n, we still observe exactness, but much less frequently.
5

---

(ruupi @ Muaii
Ofeege & Rageo
0.8
0.4
0.0
0.0
30
12
10
24
30
Number of sample points
Number of sample ple points
(a) Objective of problem (GW-SDP).
(b) Estimation gap (RHS of (4)).
Figure 2: Value of the objective (left) and approximation ratio (right) with a varying number of sample points, calculated on runs the Gaussian matching experiment.
1.8
CM 207
275
358
225
3.0
34
20
(a) GW Distances with different solvers.
(b) Approximation Gap GW-SDP.
Figure 3: Gaussian Matching experiments with the sample points from source distribution varying while the sample points from target distribution keeping fixed n = 8. Average of 20 runs.
Runtime Comparisons Table presents the run-time of the GW-SDP problem in Experiment 1, running on PC with 8 cores CPU and 32GB of RAM. In these experiments, the cost matrix C' is pre-computed (i.e. assumed given). As such, the run-time is independent of the data dimension. The GW-SDP has matrix of dimension mn X mn, which is slower than most local and entropic solvers. However, the solvers we implement (SCS and MOSEK) are off-the-shelf and are general SDP solvers that do not exploit special structures in the problem and do not provide options to use initialization of the transport plans. (SCS first-order method, we are otherwise unaware of its complexity). We want to emphasize that in most settings where SDPs are applied, one will always try to develop specialized solvers that exploit the structure the problem. In our setup, the optimal solution has low rank, and is rank-one if the relaxation is tight. There numerous well-established methods for exploiting such structure, This is the subject of ongoing work.
Table 1: Average run time in seconds for experiment in Figure la (matching Gaussians with varying number samples n)).
GW-SDP
GW-CG
eGW (s 0.1)
0.2437 (0.0265)
0.0005 (0.000041)
0.226 (0. 145)
12
11.615 (2.4088)
0.0006 (0. (0.00003)
0.2596 (0.0726)
216.3645 (14.1123)
0.0014 (0.000017)
0.4923 (5.1500)
Comparisons of GW-SDP solver and GW-CG solver when number of sample points n increase. We increase the number of samples for GW-CG (non-convex GW solver using conditional gradient descent or Frank-Wolfe algorithm) vs our GW-SDP solver for fixed number of samples. From Table 2, we noticed that objective value for GW-CG decreases as we increase the number of samples. For 100000 sample points, the GW-CG algorithm is more expensive and has poorer

---

objective value than our method with 10 sample points. This suggests that our method can give good approximations of the GW distance with fewer sample points than existing methods.
Table 2: Comparisons of GW-SDP solver and GW-CG solver with a varying number of sample points
GW-SDP
GW-SDP Runtime (s)
GW-CG
GW-CG runtime (s)
10
0.4577
6.3753
1.135940
0.000389
100
0.629425
0.007571
1000
0.540984
2.520011
10000
0.496796
138.358954
4.2 Graph Community Matching
The objective of this task is to find matching between two random graphs that drawn from the stochastic block model (SBM) (Abbe, 2017: Holland et al., 1983) with fixed inter/intra-cluseers connected, respectively). The probability (the probability that nodes inside and outside cluster source is three-cluster SBM whose intra-cluster probability is p = {1.0, 0.95, 0.9), and the target a two-cluster SBM whose intra-cluster probability p 0.90. The inter-clusters probability is all set to 0.1. The distance matrices on each graph are created first by simulating the node features drawn from Gaussian distributions with uniform weights. Subsequently, we compute the & norm between nodes and shrink the value of disconnected nodes to zero to form the distance matrices.
We compare the transportation plans obtained using our methods with the baseline comparisons GW-CG and eGW in Figure 4a. We note that the (GW-SDP) model typically returns a transport plan with smaller total transportation cost (i.e., smaller objective value) (Tadp, L @ mad))- This trend consistent with our observations in the previous experiments. Nevertheless, we see degree of similarity between the transportation plans provided output by all three methods. In addition, the transportation plans computed by our method and GW-CG are both reasonably sparse. This fact is observed in multiple of different seeds and graph sizes.
4.3 Extension of GW-SDP to Structured Data
In this example, we consider an extension the (GW-SDP) to structured data, more specifically graphs with node features similar to the Fused-GW distance in (Vayer et al., 2019a). The discrete metric-measure space is now described by the tuple (F, C.).))) E Rm x Rmxm Em. where
F def. (ft); E Rd encodes the feature information of the sample point. The Fused GW-SDP (FGW- SDP) formulation is given by
C. C,
min TER"XM XH PeRmicnon
(1 4) + D),
veo(T)
s.t.
vec(T))
(FGW-SDP)
π E II(,
Pvec(e,1,] = a, veo(T))) i [m] Pvec(1 B, vec()), e [n] P20. 0,
with MrG d(ff, ky encodes the distance between node features, and & [0, 1] the interpola- tion parameter. Figure 4b shows the result of matching two SBM graphs with the same setting as in Section 4.2, with the exception that now we input the feature to calculate MyG by &o norm, and the structured matrices are the shortest path matrices obtained from the adjacency matrices of the graphs. We set ş = 0.8 for this example. The figure shows that the output OT plans and values of (FGW-SDP) and FGW-CG (using PythonOT) are identical, while entropic Fused-GW returned higher value and a denser transport plan. This indicates that the SDP relaxation of Fused-GW can be uscful in graph matching applications, akin to Fused-GW.
7

---

(a) Matching with GW.
(b) Matching with FGW.
Figure 4: Value of the objective on the synthetic graph matching task, from the three-block SBM (left) to the two-block SBM (right). Upper: calculated using GW. Lower: calculated using Fused- GW.
4.4 Using GW-SDP Realistic Shape-Matching Task
We use publicly available dataset of triangular meshes (Sumner and Popović, 2004). The dataset comprises 72 objects from seven different classes, from which we chose samples of class cat, ele- phant, and horse. For each object, we first chose 4 representative points (the right back foot, the left front foot, the nose, and the tail) for each object and then selected another 14 points following the Euclidean farthest point sampling (fps) procedure. The distance matrices C' and D are computed using Dijkstra's algorithm. Each object's probability measure chosen to uniform. We apply (GW-SDP) to the corresponding metric-measure spaces to determine the correspondence between the selected vertices across different objects. Two representative examples are given in Figure 5. For better visualization, in the representative examples we sampled only 6 points (4 representative points and selected using fps).
(a)
(b)
Figure 5: Correspondence between different 3D objects obtained by (GW-SDP), Left: Correspon- dence between two elephants. Right: Correspondence between an elephant and cat. For both cases, (GW-SDP) returns one-one mappings.
Table illustrates the results when we perform matching of distance matrices across different ob- jects. In general, expect shapes of the same animals to have smaller GW distance than shapes of different animals, which is indeed the case for the three GW formulations. We still notice that GW-SDP consistently returns the smallest value when performing the same matching task.
Table 3: Value of different GW formulations for the realistic 3D shape matching dataset, visualized Figure GW-SDP consistently returns the smallest value when performing the same matching task.
GW-SDP
GW-CG
eGW-PPA
Seephant-Elephan
0,007416
0.043879
0.025688
Elephant- Cat
0.015695
0.050594
0.042214
Cat-Cat
0.006549
0.016634
0.006757
Cat- Horse
0.011040
0.033736
0.011041
Morse-Horse
0.006287
0.033768
0.007395

---

Duality
Given a generic optimization instance, the dual optimization instance concerns the task of finding optimal lower bounds to the primal instance. The (Lagrangian) dual to any optimization instance convex program general and provides a principled way of obtaining convex relaxations of difficult optimization instances. We briefly discuss some of these relationships. A more detailed discussion on the duality can be found in Appendix B.
It possible to obtain the relaxation (GW-SDP) via duality. Concretely, let (GW++) refer to the orig- inal GW problem instance (GW+) with the additional and redundant constraints (Nng.) and (Mar.). Let (GW-Dual) refer to the Lagrangian dual of the proposed semidefinite relaxation (GW-SDP).
Theorem 5.1. The optimization instance (GW-Dual)) is the Lagrangian dual of (GW++), which is (GW+) with the additional constraints (Nng-) and (Mar.).
The (duality) gap between (GW-Dual) and (GW++) is non-zero in general, and is equal to zero precisely when the convex relaxation (6) succeeds. These can be characterized by a rank condition:
Proposition 5.2. Let P sdp and sdp be the solution to (GW-SDP). Suppose the matrix variable has rank equals to one; that is
Podp (vec(Tsds))
ved(TTdd) 1.
rank
Then the duality gap is zero; i.e. strong duality holds.
Related work
There is substantial body of prior work concerning the GW problem in the literature. We briefly discuss some of these and explain the novelty of our work.
First, the work in Vayer et al. (2019a) applies an alternating minimization-tyee approach based on the conditional gradient (Frank-Wole Wolfe) algorithm to find local optima to the GW problem. This algorithm is currently implemented and is the default choice within the Python Optimal Transport package (Flamary et al., 2021). The basic idea is to start by computing the partial derivative of the objective (GW) with respect to
G( =
This is linear OT problem that can be solved using classical OT solvers. One proceeds with an alternating minimization scheme in which one updates the gradient G with respect to π (1-1)) subsequently solves for (1) with the loss G(Tr) each ith-iteration, and finally projects π (0) into the feasible set by performing line-search. The Conditional Gradient-based approach is not guaranteed to find globally optimal solutions; in fact, our numerical experiments in Section 4 suggest that this is quite often the case. Last, we briefly note that the work in Kerdoncuff et al. (2021) suggests similar alternating numerical scheme.
Second, there is a body of work that aims at developing numerical schemes for finding transportation plans that approximately minimize the GW objective without incurring the expensive Omm dependency. For instance, the work in Peyré et al. (2016) introduces an entropic regularization into the GW objective this leads to formulation that permits Sinkhorn scaling-like updates, much like the original scheme to solve entropic Wasserstein distance in Cuturi (2013). The work of Vayer et al. (2019b) adapts the ideas from the Wasserstein problem one dimension in which closed-form solutions are available (this is known the sliced Wasserstein problem, Rabin et al. 2012) to the GW context. Finally, the work in Sejourne et al. (2021); Vincent-Cuaa et al. (2021) relaxes the constraints on the probability distributions. These numerical schemes frequently lead to numerical schemes that are far more scalable than other existing methods, but they ultimately optimize for an objective that is different from the GW problem.
There is an interesting piece of work Scetbon al. (2022), which operates under the assump- tion that the cost matrices have low-rank structure. While the algorithm does not give guarantees about global optimality, raises an interesting future direction; namely, could we develop numerical schemes for our proposed SDP relaxation that also exploit similar structures?

---

Finally, we discuss prior works that do in fact address global optimality (which is the heart of this paper); a recent work is in Mula and Nouy (2022), which suggests the use of moment sum-of- square (SOS) relaxation technique to solve the GW problem. The standard SDP relaxation for QPs on which our work is based on may be viewed, in suitable sense, as the first level of the SOS hierarchy for polynomial optimization. Unfortunately, and as we note in Section 3, this alone is in- sufficient - the real novelty in our work is the addition of constraints that substantially strengthen the overall convex relaxation. A piece of related work by Villar et al. (2016) proposes SDP relaxation of the closely related Fromov-Hausdoon problem. The relaxation is primarily designed for the alent to ours. The formulation also requires the probability distributions to be uniform whereas we do not. Another recent work by Ryner et al. (2023) also studies the and proposes a Branch-and- Boudd approach for solving integer programs. The GW problem does not contain integer constraints, and hence Branch-and-Bound techniques not applicable. That said, SDP relaxations can be used conjunction with Branch-and-4 Bound. It would be interesting to see if our proposed SDP relaxations for GW suggest suitable relaxations for the Haaudofff problem, which can be used in conjunction with the Sanch-and-Bourt techniques in Ryner et al. (2023).
problem, with an extension to the in
problem and is not equiv-
problem,
7 Conclusions and Future Directions
In this work, we proposed semidefinite programming relaxation of the Gromov- Wasserstein dis- tance. Our initial results suggest that the relaxation (GW-SDP) is strong in the sense that xadp frequently coincides with the globally optimal solution; moreover, we are able to provide proof when this actually happens. These results are exciting, as it suggests a tractable approach for solv- ing the GW problem at least for examples of interest which was previously assumed to be quite difficult.
An interesting future direction is to understand precisely how difficult is an instance of the GW problem. The fact that our convex relaxations work very well for the examples we considered suggests that the GW problem might not be as difficult as we think. It is important to bear in mind that these cost tensors L have structure - they arise from the difference of actual cost matrices. Could it be that the difficult instances of the GW problem correspond to cost tensors L that are not realizable as the difference of cost matrices; e.g., they violate the triangle inequality? A concrete question to this end is: Is the GW problem corresponding to cost tensors L arising in practical instances tractable to solve?
A second important future direction concerns computation. One limitation of our proposed convex relaxation that is specified as the solution of an SDP in which the matrix dimension mn; that is, it is equal to the dimension of the transport plan. The prohibitive dependence on the data dimension means that we are currently only able apply the relaxation on moderate sized instances using off-the-shelf SDP solvers. It would be of interest to develop specialized algorithms to solve the proposed relaxation (GW-SDP).
Acknowledgements
We thank the anonymous reviewers for their helpful comments and feedback that helped improve our work. B.T. Nguyen is supported by NUS Start-up Grant A-0004595-00-00.
References
Abbe, E. (2017). Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 1844):444-6531.
Agueh, M. and Carlier, G. (2011). Barycenters in the wasserstein space. SIAM Journal on Mathe- matical Analysis, 43(2):904-92
ApS, M. (2022). The MOSEK optimization toolbox for Python manual. Version 10.0.
10

---

Arjovsky, M., Chintala, S., and Bottou, L. (2017). Wasserstein generative adversarial networks. In Precup, D. and Teh, Y. W., editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 214-223. PMLR.
Benamou, J.-D., Carlier G., Cuturi, M., Nenna, L., and Peyré, G. (2015). Iterative bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing, 37(2):1111-AI1)
Bomze, I. M. and de Klenk, E. (2002). Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim., 24(2):163-185.
Bunne, C., Schiebinger, G., Krause, A., Regev, A., and Cuturi, M. (2024). Optimal transport for single-cell and spatial omics. Nature Reviews Methods Primers, 4(1):58.
Bunne, C.,, Stark, S. G., Gut, G., Del Castillo, J. S., Levesque, M., Lehmann, K.-V, Pelkmans, L.., Krause, A., and Rätsch, G. (2023). Learning single-cell perturbation responses using neural optimal transport. Nature methods, (0(11):1759-111
Courty, N., Flamary, R., Habrard, A., and Rakotomamonjy. A. (2017). Joint distribution optimal transportation for domain adaptation. Advances in neural information processing systems, 30.
Cuturi, M. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26.
Diamond, S. and Boyd, S. (2016). CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83)11-5.
Dym, N., Maron, H., and Lipman, Y. (2017). Ds++: Flexible, Scalable and Provably Tight Relaxation for Matching Problems. ACM Transactions on Graphics, 36(184):1-14.
Flamary, R., Courty, N., Gramfort, A., Alaya, M. Z., Boisbunon, A., Chambon, S., Chapel. L., Corenflos, A., Fatras, K., Fournier, N., Gautheron, L., Gayraud, N. T., Janati, H., Rakotoma- monjy, A., Redko, L, Rolet, A., Schutz, A., Seguy, V., Sutherland, D. J., Tavenard, R., Tong, A., and Vayer, T. (2021). Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8.
Holland, W., Laskey, K. B., and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social networks, 5(2):109-137.
Kantorovich (1942). On translocation of masses. USSR AS Doklady New Series, 37, 7-8, 227-229 (in Russian).
Kerdoncuff, T., Emonet, R., and Sebban, M. (2021). Sampled gromov wasserstein. Machine Learn- ing. 110())2151-21866
Kezurer, I., Kovalsky, S. Z.,, Basri, R., and Lipman, Y. (2015). Tight relaxation of quadratic match- ing. In Computer graphics forum, volume 34, pages 115-128. Wiley Online Library.
Kong, I.,, Li, Tang, J., and So, A. M.-C. (2024). Outlier-robust gromov-wasserstinn for graph data. Advances in Neural Information Processing Systems, 36.
Kravtsova, N. (2024). The NP-hardness of the Gromov-Wasserste Wasserstein Distance. abs/2408.06525.
arXiv,
Kusner, M., Sun, Y., Kolkin, N., and Weinberger, K. (2015). From word embeddings document distances. Bach, and Blei, D.,, editors, Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 957-966, Lille, France. PMLR.
Lipman, Y., Chen, R. T., Ben-Hamu, H., Nickel, M., and Le, M. (2022). Flow matching for genera- tive modeling. arXiv preprint 1rXiv:2210.02747.
Liu, X., Gong, C., and Liu, Q (2022). Flow straight and fast: Learning generate and transfer data with rectified flow. arXiv preprint arXiv:2209.0300

---

Motzkin, T. and Straus, E. G. (1965), Maxima for graphs and new proof of theorem of tur tan Canadian Journal of Mathematics.
Mula, O. and Nouy, A. (2022). Moment-sos methods for optimal transport problems. arXiv preprint vrXiv:2211.10742
Mémoli, F. (2011). Goomov-Wasserstein Distances and the Metric Approach Object Matching. Foundations of Computational Mathematics, 11(4)4417-487
Nocedal, J. and Wright, S. J. (2006). Numerical Optimization. Springer.
O' O'Donoghue, B., Chu, E., Parikh, N., and Boyd, S. (2016). Conic optimization via operator split- ting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 169(3):1022-1068
Pardalos, P. M. and Vavasis, S. A. (1991). Quadratic programming with one negative eigenvalue is np-hard. Journal of Global optimization, 1(1):15-22.
Peyré, G., Cuturi, M., et al. (2019). Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 116-66)355-607.
Peyré, G., Cuturi, M., and Solomon, J. (2016). Gromov-wasserstein averaging of kernel and distance matrices. In International conference on machine learming, pages 2664-2672. PMLR.
Rabin, J., Peyré, G., Delon, J., and Bernot, M. (2012). Wasserstein barycenter and its application to texture mixing. In Scale Space and Variational Methods in Computer Vision: Third International
Conference, SSVM 2011, Ein-Gedi, Israel, May 29-June 2, 2011, Revised Selected Papers 3, pages 435 Springer.
Ryner, M., Kronqvist, J., and Karlsson, J. (2023). Globally solving the Gromov-Wassersee prob- lem for point clouds in low dimensional Euclidean spaces. arXiv preprint arXiv:2307.09057.
Santambrogio, F. (2015). Optimal transport for applied mathematicians, Birkäuser, NY, 55(58- 63):94.
Scetbon, M., Peyré, G., and Cuturi, M. (2022). Linear-time gromov wasserstein distances using low rank couplings and costs. In International Conference Machine Learning, pages 19347-19365. PMLR.
Schiebinger, G., Shu, J., Tabaka, M., Cleary, B., Subramanian, V., Solomon, A., Gould, J., Liu, S., Lin, S., Berube, P., et (2019). Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming. Cell, 176(4):928-943.
Sejourne, T., Vialard, F-X.,, and Peyré, G. (2021). The unbalanced gromov wasserstein distance: Conic formulation and relaxation. In Advances in Neural Information Processing Systems, vol- ume 34, pages 8766-8779.
Sumner, R. W. and Popović, J. (2004). Deformation transfer for triangle meshes. ACM Transactions on graphics (TOG), 23(3):399-405.
Vayer, T., Courty, N., Tavenard, R., Laetitia, C., and Flamary, R. (2019a). Optimal transport for structured data with application on graphs. In Chaudhuri, K. and Salakhutdinov, R., editors, Pro- ceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 6275-6284. PMLR.
Vayer, T., Flamary, R., Tavenard, R., Chapel, L.,, and Courty, N. (2019b). Sliced gromov-wasserstein. In Advances in Neural Information Processing Systems, volume 33, pages (4753-14763
Villani, C. et al. (2009). Optimal transport: old and new, volume 338. Springer.
Villar, S., Bandeira, A. S., Blumberg, A. J., and Ward, R. (2016). A polynomial-time relaxation of
the gromov- houuor-haudoorff distance. arXiv, abs/1610.05214.
12

---

Vincent- Cuaz, C., Flamary, R., Corneli, M., Vayer, T., and Courty, N. (2022). Template based graph neural network with optimal transport distances. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A., editors, Advances in Neural Information Processing Systems, volume 35, pages 1 18800-18144 Curran Associates, Inc.
Cunze,t-Cuaz, C., Vayer, T., Flamary, R., Corneli, M., and Courty. N. (2021). Online graph dic- tionary learning. In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11564-10574. PMLR.
Xu, H., Luo, D., Zha, H., and Duke, L. C. (2019). Gromov-Wassersiee learning for graph matching and node embedding. In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6932-6941, PMLR.
Zhao, Q.. Karisch, S. E., Rendl, F., and Wolkowiez, H. (1998). Semidefinite Programming Relax- ations for the Quadratic Assignment Problem. Journal of Combinatorial Optimization, 2:71-109.
13

---

A Proofs of Main Results
Proof of Proposition 3.1. Let 1 S. s, S mn be coordinates such that L,t 0. Let U v(stt)
Rmn be a vector whose s-th entry is 1, whose t-th entry is 11, and whose remaining entries are zeros.
Let [1, (9) be any transportation map and consider the matrix P. vec(fi vec(a) + cvu and P Pa
for all 2 O. Hence the choice of variables are feasible. Then notice that the objective evaluates to
Notice that Pa vec(T))
Pa) (L,
> c(Lss 2t + Lue) = (L, vec(f)vec(*t); 2cL
We obtain the last equality by noting that La = 0 for all i (this is property of cost matrices). The result follows by taking +00.
B
Duality
Given a generic optimization instance, the dual optimization instance concerns the task of finding optimal lower bounds the primal instance. The (Lagrangian) dual to any optimization instance a convex program in general. As such, the process of deriving the dual to any optimization instance provides a principled way of obtaining convex relaxations of difficult optimization instances.
The objective value of the dual will always be a lower bound to the primal instance - this is precisely weak duality. In some cases, however, the objective values of these problems may coincide, and call such settings strong duality.
In this section, explore these relationships in the context of the GW problem. As shall see, the proposed SDP relaxation (GW-SDP) can viewed as being equivalent to the dual of an equivalent form of the GW problem (GW+), augmented with additional constraints that relate the linear and quadratic terms of transportation maps specified by (Nng.) and (Mar.). To simplify notation, we denote
a; veo(e;
bj = vec(1me]]
We proceed to describe the dual program. We start by defining the following dual variables:
P vec(T)
= o
(ve((m)
2 0
(a)
A R
a. vec(TT) = ai
i E [m] 6J vec(TT) = By,
(b)
My E R
[n]
(c)
Z 2 0
P 2 0
(d)
1// R mn
Pa; vec(m))
i [m]
0 Rm
: Pb; = 3, veve))))
j E [n]
As reminder, the constraints in (b) and (c) specify the transportation map II 3) while the straints in (c) and (f) correspond to (Mar.). Theorem B.1. The Lagrangian dual of (GW-SDP) is given as follows
A a Ta + TT -
max
L 2 + 2 ( + aam )
+ + b,, / z 0
/)=0
s.f.
y
(GW-Dual)
m
12
(dras + aunn)
Σ
(1yb + 3,00) 2y < 0,
22 0.
Furthermore, strong duality holds; that is, the duality gap between (GW-SDP) and (GW-Dual) zero.
14

---

It turms out that it is possible to derive the dual instance (GW-Dual) directly from (GW+), an equiv- alent formulation of the original GW problem, with additional constraints specified by (Nng.) and (Mar.). Concretely, consider
min mERmxn
(L, P)
PERmaXmn
S.L.
P vec(Tr)ve(())"
E IT(a,
(GW++)
Pvec(e; 1, a, veo(m), [m] P Byveo(T), e [r] P20.
The last three constraints on are always satisfied so long as P = vec(r)vee(T)). where æ E II(a, 3) is transportation map. Hence these constraints P and are technically redundant within (GW++). That is, the optimization instances (GW+) and (GW++) are equivalent. However, the Lagrangian dual of these optimization instances different, and summarize this observation in the following.
Theorem B.2. (GW-Dual) is the Lagrangian dual of (GW++).
The (duality) gap between (GW-Dual) and (GW++) is non-zero in general, and is equal to zero precisely when the convex relaxation (6) succeeds. These can be characterized by a rank condition satisfied by the optimal solutions, namely:
Proposition B.3. Let Padp and sdd be the solution to GW-SDP. Suppose the matrix variable has rank equals one, that
rank Pedp (ec((Tsdp)
vec(TTed))
1
Then the duality gap for (GW++) is zero; i.e., strong duality holds.
Proof. The rank condition implies Psdp = vec( vec Subsequently, the choice of variables л = sddp and P = vec(T vec(Tsd))) is a feasible solution to (GW++). This means (GW++) attains the same objective value the (GW-Dual). Recall from Theorem B.2 that (GW-Dual) is the dual of (GW++), and hence in this instance the duality gap is indeed zero O
We summarize the relationships among the original GW problem, (GW+), (GW++), (GW-SDP), and (GW-Dual) in Figure 6:
(GW+) is an equivalent reformulation of the original GW problem.
(GW++) is derived by introducing additional redundant constraints to (GW+). Conse- quently, (GW+) and (GW++) share the same optimal solutions.
(GW-SDP) is obtained by applying the standard SDP relaxation to (GW+) and introducing supplementary constraints to tighten the relaxation.
(GW-Dual) serves the Lagrangian dual to both (GW++) and (GW-SDP), and strong duality establishes the equivalence between (GW-Dual) and (GW-SDP).
15

---

Equivalence
GW++
Dual relaxation
(nonconvex)
Equivalence
GW Problem (nonconvex)
GW [nonconvve)
GW-Dual (convex)
SDP relaxation and tightening the constraints
GW-SDP (convex)
Equivalence: strong duality
Figure 6: The relationship among the original GW problem, (GW+), (GW++), (GW-SDP) and (GW-Dual).
C Proof of Results Concerning Duality
We begin by defining these functions:
1 n H 0, L- 2 + "n'a + anv"") ) + (006 + b,000)
i=1
j=1
a
g(>. 14, 17, 0,y)
(Deas agnn")
(ujbı + 3,00) 2y. Σ
Proof of Theorem B.1. [Deriving the dual program]: The dual function of the GW-SDP problem is
given by
min P2200
tr(LP) -r((P)) - 2y vee(()) -
A1(a; at vec(T)) + Σ ps(3s - 0J vec(T))
(Pa: - a(vec(T)) + 0sT (Pb, 3,
tt(PP)
min tr ((H(1, 0, YY
min (-9(\, ve(() x20
+X a + 11 T -
In the above minimization over P, we observe that the objective evaluates to -oo if the following does not hold
H 0)= =Y
Similarly, in the minimization over 2 0, the objective evaluates to -2o if the following does not hold
g(,, 14, 0, S 0.
We impose these as constraints, and we add the additional constraint that > 0 on our dual variable, to obtain the form of the dual problem in (GW-Dual).
[Establishing zero duality gap]: Notice that (GW-SDP) and (GW-Dual) are convex programs. Hence, to show strong duality, it suffices to check that Slater's condition hold; that is, there ex- ists a strictly feasible solution.
Consider ry = (lmmia (L) + 2) A -2m for i E [m], A0 0. my = 0 for E [n], t 1, = 0, and
2 = (Amin (.)) + 2)11
(1Amin (T.) + 1)T
16

---

for some 1, 0 and I of appropriate dimension. Then we have Z >
0, and
m
g(>, 1,,, -2
01
+
ml <.
==1
Additionally, since (n, 0, 2) + (Amin(() + 1)I > 0, t LHS of the first constraint in (GW-Dual is positive definite. Therefore, find feasible solution of (GW-Dual) such that striet inequality holds for all inequality constraints. Strong duality then follows.
and = 0, it follows that the
Proof of Theorem B.2. In addition to the dual variables (b)-(f), we define these additional dual vari- ables:
Y R m
P n (ee((r)eec(())) vec(T> 2 0
Then the dual function of (GW++) is given by
m
min tr vec(T))ec(TT) R.P
Σ d1(0s a (ec((T) + Σ (k, b3 vec(t))
m
(Pa: - a,vec((T)
Σ
(Pby B)vec(T)) tr((P) vec(TT)
j=1
min
tr((H( (17, 8, -
P
A1
+ min vec(T) (vec(T)
(Aa + az)²) + Σ
(nzby + 3,00) +
vec(T)
j=1
+ + (aa+TB. BBB.
To simplify notation, we denote
Dea azn') + "(ub, + 3300).
Observe that
0
if = H(n, 0,
min A
PERmaXma
-00
otherwise
and
t TT(p++)))
if 2 0nd (I - -
max
A2
TER X
xC
otherwise
Hence, the dual of (GW++) is given by
Aa+ 1 2
max
s.t.
Y 0
(1 YY+) 2)
Y = H (n, (n.00.1) 0,Z)
Z>0 0
=20
17

---

We re- re-write this as
Na+p'a B-
2,,
1 (O++))T((p++++
s.t.
Y
(I - x))
Y H(n. 0, 7) 2 2 0
220
By taking Schur complements and by replacing Y with H (n, 0, 2), the above optimization instance reduces to
A B-
max 2,2,2,2,
(11.0,2) -2)
- -2(
s.t.
2
t
2 220
2 2
Note that (A, 0) = 2y, the theorem then follows by doing a change of variable (p 2).
D Extended Applications of GW-SDP
D.1 GW-SDP Barycenters
One popular application of optimal transport is compute the barycenters of measures that serves as a building block for many learning methods. The notion of barycenter for measures was first proposed in Agueh and Carlier (2011) for Wasserstein space. Akin to barycenter Euclidean space (Fréchet), the Wasserstein barycenter is defined as the solution of a weighted sum of OT distances efficient algorithm
over the space of measures. entropic regularization was proposed in Benamou et al. (2015), and was later extended to discrete metric-measune spaces with entropic GW distance in Peyré al. (2016).
compute the discrete OT barycenter with
We show that it is straightforward to extend the GW-SDP formulation to find barycenters of a set of data Fréchet means. For simplicity, assume that the base histogram the size of the barycenters m E N, and (A&); such that En d are fixed. We aim to find a structure matrix Ć that minimizes
min G&W-SDDPC&s O, C.,,a)))
We have the following corollary.
Corollary D.1 (Adaptation of Proposition in Peyré et al. (2016)). In the special case of the squared loss E(a, b) = (a - b)?, the solution of (7) reads
Ö Σx JdpT Sddpk
(8)
where Tadp,k is the solution to GW-SDP(Ck, C, C,a,, @) and the division is entry-wise,
Corollary D.I shows that we may apply iterative updates to solve for the barycenter via the Block Coordinate Descent (BCD) algorithm. At each iteration, we solve K independent instances of the GW-SDP problem to find (Tsdp, and then compute C' using (8) to solve for (7). A pseudocode for We demonstrate the effectiveness of the GW-SDP barycenter calculation by applying it to find the barycenter of graph dataset. The dataset consists of 20 noisy graphs, created by adding random connections from circular graph. We show a visualization of 9 of these in Figure 7a. The number of nodes ranges from 8-16. We apply the (GW-SDP) barycenters update for 100 iterations, and Figure 7b shows the result for circular graph of 10 nodes.
the GW-SDP barycenter calculation is provided in Algorithm
18

---

Algorithm Computation of GW-SDP barycenters.
Input: dataset (Ck; 0rk) (Ax)
Initialize C.
repeat
for k = to K do
Tadp.. f- solve_GH-SDPP (C,, C, CKR
end for Update C' using (8). until convergence
(b) Graph (GW-SDP).
barycenter
learned
by
(a) Visualization of noisy circular graphs.
Figure 7: Application of the (GW-SDP) to find graph barycenter of noisy circular graphs.
D.2 Outlier-Robust GW-SDP
It is generally possible extend the semidefinite relaxation variants of the GW problem. We briefly describe the semidefinite relaxation to the outlier-robust GW problem by Kong et al. (2024). Here, (X,dx and dy) are two metric spaces with accompanying measures p and v. The dis- tance between and // is
min () + +TdxI(Tl,aa) + (T 1,3,
P vec(T)
vec(T)T
s.t.
20
Σ, P(S)).()))) = f5 L EyP(es)a = R.l
P20
dKI(u, S Pr: dx S2- P2.
There is one technical aspect: the marginal sums Σ, ((..).(R.))) we this equal to some constant po.l In GW-SDP, the corresponding RHS term depends л and In the robust set-up, a is an optimization variable, not constant, which necessitates the above change. We remark that the resulting formulation is convex but not SDP because of the presence of the KL divergence.
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract highlights the proposed approach and advantages of solving the GW distance problem via SDP relaxation and talks about the use of numerical algorithms to solve the problem.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The main limitation the proposed GW-SDP formulation is the runtime, In the conclusion, we discuss possible future directions towards mitigating these issues.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "L.mitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
20

---

Answer:
[Yes]
Justification: The feasibility and basis of the formulation of the SDP relaxation is shown. The validity of the numerical algorithms is also shown.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The formulation of GW-SDP is compatible with existing convex optimization solvers. The equations and steps taken for the numerical algorithms are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, deseribing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is either be a way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
model (e.g.. a large language model), then there should
(d) We recognize that reproducibility may be tricky some cases, in which case au- thors welcome to describe the particular way they provide for reproducibility. In the case of -ource models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
21

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
The code is made publicly available at
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /niis... wtcccc/ppuu mublic//uide Sudeee// ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, experimental results for the new
The authors should provide scripts to reproduce proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Does the paper specify all the training and test details (e.g.. data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: The main contribution is algorithmic. There is testing or training aspect to this problem. The implementation of the algorithm in Section ?? does involve certain parameter tuning. We do not discuss these parameters but these will be specified in code that will be made public.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The main contribution this paper algorithmic. There are no numerical experiments of a statistical nature in this paper. All numerical experiments concern algo- rithmic performance.
Guidelines:
The answer NA means that the paper does not include experiments.
22

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer:
[Yes]
Justification: The details of the computer resourees used for the experiments are given in section 6.1.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with NeurlPS Code of Ethics https: /itt::/nneuippp
Answer: [Yes]
The research does not involve human subjects or private data. The libraries used for comparison against existing methodologies open source.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
23

---

The paper's 's focus is on improvements towards solving the GW distance prob- lem and is foundational in nature. The societal impact is limited insofar as improves existing MI. techniques that are based on Optimal Transportation techniques. Guidelines:
Justification:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There is risk of misuse for the algorithms in the research. There is no release of data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Ye]]
The open source Python Optimal Transport package, released under the MIT license, only used for algorithmic comparisons. Other datasets that using in the numerical experiment sections also cited.
Justification:
Guidelines:
24

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: The paper does not released new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
25

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "JWxPvC5uUD", "reviewer": "Reviewer_nsV6", "summary": "The authors provide SDP relaxations of the Gromov-Wasserstein distance, which turns out to provide global optimal in many cases.", "questions": "How does the runtime compare with that of commonly used algorithms?\n\nIf the SDP relaxations are correct, it should be possible to derive first-order methods for these, which could perhaps be simplified substantially, compared to general-purpose SDP solvers. Have you explore the direction?", "limitations": "The run-time is not discussed.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "-- The SDP relaxations and proofs of their exactness are most elegant. \n\n-- The authors suggest that their method does not make as strong assumptions on the loss as in the case of the previous work (e.g., the Proximal Point algorithm).", "weaknesses": "Commonly used pythonOT library (https://pythonot.github.io/auto_examples/gromov/plot_gromov.html) implements the conditional Gradient algorithm (ot.gromov.gromov_wasserstein), the Proximal Point algorithm with Kullback-Leibler as proximal operator (ot.gromov.entropic_gromov_wasserstein), and the  Projected Gradient algorithm with entropic regularization (ot.gromov.entropic_gromov_wasserstein), but the authors do not compare their run-time against neither of the methods. Plausibly, this is because the run-time of the SDP solver is much higher?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Run time comparisons*\n\nWe wish to clarify that the current manuscript compares run times of the Conditional Gradient (CG) method, the entropic Gromov-Wasserstein method and our method. The comparisons are found in Page 5 of the submitted manuscript. For a fixed number of samples, the SDP runtime is far more costly than the other two algorithms.\n\nWe performed additional experiments to compare the runtime with algorithms suggested by the Reviewer. These results will be included in the revised manuscript.\n\n| m  | GW-SDP \t| GW-CG\t| eGW-PGD  | eGW-PPA  |\n|----|------------|----------|----------|----------|\n| 8  | 0.557457   | 0.000349 | 0.162370 | 2.625325 |\n| 12 | 18.970195  | 0.000460 | 0.042703 | 2.116204 |\n| 16 | 17.000997  | 0.000426 | 0.048222 | 3.316097 |\n| 20 | 108.477784 | 0.000556 | 0.056619 | 2.986389 |\n| 24 | 56.620260  | 0.000523 | 0.067252 | 4.503040 |\n\nWe also conducted additional experiments where we compared the performance of GW-SDP with GW-CG and eGW-PPA. (These are described in the global comment and in the attached PDF.) Interestingly, in the experiment with real data, the objective values obtained from eGW-PPA are smaller than the values obtained from GW-CG, though still larger than those obtained by GW-SDP. (A smaller objective value is better in this instance.) This suggests the GW-SDP is the best algorithm for finding optimal solutions (in terms of the smallest objective value), followed by the eGW-PPA and then GW-CG.\n\n*First-order methods*\n\nFirst-order methods should improve the run-time in general. We investigated this approach but encountered numerous difficulties.\n\nIt is difficult to apply most first-order methods for solving SDPs to our relaxation. The main reason is that our formulation contains many constraints whereas most numerical techniques typically rely on having few affine constraints.\n\nThere is a line of work that uses proximal methods in combination with numerical schemes that allows families of constraints to be decoupled such as the ADMM method. Unfortunately, these ideas also do not translate easily. Our formulation has many different types of constraints: PSD, doubly stochasticity, non-negativity, and marginal sums. It is not clear how one designs proximal operators that project onto the intersection of these constraints, or design ADMM schemes that combine several different proximal operators.\n\nThere are some prior works that develop numerical schemes for solving semidefinite relaxations for the closely related Quadratic Assignment Problem (QAP) [KKBL:15,DML:17,OWX:18]. These works do point out that these semidefinite relaxations, while powerful, are not easy to solve. This suggests that it is equally difficult to develop numerical schemes for our semidefinite relaxations.\n\nIn fact, the scale of the problems we work on are not far from state-of-the-art for semidefinite relaxations of the QAP. In a work by Oliveira et al. -- a work purely about numerical optimization -- the authors propose an ADMM scheme to solve QAP instances where the dimension is 40 while the largest GW instance we solve has dimension m=n=32. This means that our problem size is not far from the state of the art.\n\nWe hope that the Reviewer accepts and values the conceptual and theoretical contributions already present in this paper, and recognizes that the scope of developing scalable numerical schemes, while important, goes comfortably beyond the scope of a single paper.\n\n*References*\n\n[KKBL:15] I. Kezurer, S. Z. Kovalsky, R. Basri, & Y. Lipman. (2015). Tight relaxation of quadratic match. In Computer Graphics Forum, volume 34, pages 115–128. Wiley Online Library.\n\n[DML:17] N. Dym, H. Maron, & Y. Lipman. (2017). DS++: A Flexible, Scalable and Provably Tight Relaxation for Matching Problems. ACM Transactions on Graphics, 36(184):1–14.\n\n[OWX:18] D. E. Oliveira, H. Wolkowicz, & Y. Xu, (2018). ADMM for the SDP relaxation of the QAP. Mathematical Programming Computation, 10(4), 631-658.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pT7flFgxJb", "reviewer": "Reviewer_3Vyi", "summary": "The authors propose a semidefinite programming (SDP) relaxation of the Gromov-Wasserstein (GW) distance. While the GW problem is non-convex, the proposed SDP relaxation is convex and hence can be solved in polynomial time with any off-the-shelf convex solver. The authors also provide an accompanying proof of global optimality for the relaxed problem, which can be checked efficiently. The numerical experiments use an off-the-shelf solver to solve the proposed SDP relaxation and compare it with two solvers from the PythonOT package, i.e.,  Conditional Gradient (CG-GW) solver and  Sinkhorn projections solver on Matching Gaussian Distributions and Graph Community Matching. Lastly, the authors present a simple heuristic algorithm optimized for their proposed SDP relaxation.", "questions": "* The authors state at the end of Section 2 that optimal solutions can be found frequently when $m=n$ as shown in Section 4. What about when $m\\neq n$? Do the authors find that optimality cannot be verified as frequently in this setting?\n* Can the authors provide more details on the choice of parameters in Section 5? How sensitive are the results to these parameter choices?\n* Based on the observations I point out above, I am curious if the authors have considered how the behavior of the SDP-based solvers evolves w.r.t. the number of samples and how it compares to existing solvers? What about if the dimensions of the Gaussians is changed?\n* The authors extend their SDP relaxation to the task of computing barycenters in appendix D. Have the authors considered comparing (at least qualitatively) their proposed barycenter algorithm to that given in [1] and [2]? \n* Would it be possible to explore similar SDP relaxations for variants of the GW problem, such as partial GW [2], outlier-robust GW [3], linear GW [4], etc.? If so, it may be worthwhile to mention in Section 7.\n\n\n[1] Gromov-wasserstein averaging of kernel and distance matrices, Peyré et al., 2016.\n[2] Partial Gromov-Wasserstein Metric, Bai et al., 2024.\n[3] Outlier-Robust Gromov-Wasserstein for Graph Data, Kong et al., 2023.\n[4] On a linear Gromov-Wasserstein distance, Beier et al., 2022.", "limitations": "The main limitation of the proposed work, i.e., high dimensionality of the matrix $mn\\times mn$ in SDP, is provided by the authors.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors propose a novel SDP relaxation of the GW problem, which has not previously been explored in the literature. The theory is compelling.\n* The proposed SDP approach has several compelling advantages over existing GW solvers: the solver given by POT (which implements Frank-Wolfe) can only find local optima, and entropic GW cannot be used for general cost tensors. Meanwhile, the proposed approach is broadly applicable and to my knowledge the first tractable GW solver for which the optimality of solutions can be efficiently verified.\n* The paper is generally straightfoward to follow and the proofs do not seem to have any obvious mistakes.\n* The authors motivate the proposed SDP relaxation well.", "weaknesses": "* The empirical evaluation is limited in scope and done entirely with synthetic data. In particular, the authors make the claim that the SDP relaxation frequently computes globally optimal solutions, but I feel the experiments are not extensive enough to fully support such a claim. A more comprehensive experimental evaluation would be required to better understand the practical applicability and limitations of the proposed method.\n* The first experiment (Gaussian matching) is not that compelling to me. In Section 4.1, the experiment only considers up to 30 samples in each distribution and Figure 2a seems to suggest the possibility that Frank-Wolfe could perform similarly to the SDP relaxation for larger number of supports while being substantially faster. This is in line with what is reported in Table 2 with the heuristic algorithm, where the gap in performance between SDP and FW diminishes for larger number of supports.\n* It seems as though the estimation gap for the first point in Figure 1b is less than 1, though this should not be possible.  \n* Minor suggestions: 1) The readability of the paper could be enhanced by stating where proofs can be found for each claim, where the claim is presented. For instance, Proposition 3.1 is stated without mentioning where the proof can be found, and similarly for the theorems in appendix B. 2) I assume the numbers in parenthesis in Table 1 are standard errors based on Table 2. It would be helpful to state this in the caption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Real data*\n\nWe use a publicly available database of triangular meshes (Sumner et al. 2004). We obtain 18 points and compute distance matrices using Dijkstra's algorithm. Each object's probability measure is chosen to be uniform. We apply (GW-SDP) to the corresponding metric-measure spaces to determine the correspondence between the selected vertices across different objects. Two representative examples are given in Figure 1 in the attached pdf file.\n\nFollowing are the results when we do matching of distances matrices of different objects. In general, we expect shapes of the same animals to have a smaller GW distance than shapes of different animals, which is indeed the case for the three GW formulations. We still notice that GW-SDP consistently returns the smallest value when performing the same matching task.\n\n|               \t| GW-SDP   | GW-CG\t| eGW-PPA  |\n|-------------------|----------|----------|----------|\n| Elephant-Elephant | 0.007416 | 0.043879 | 0.025688 |\n| Elephant-Cat  \t| 0.015695 | 0.050594 | 0.042214 |\n| Cat-Cat       \t| 0.006549 | 0.016634 | 0.006757 |\n| Cat-Horse     \t| 0.011040 | 0.033736 | 0.011041 |\n| Horse-Horse   \t| 0.006287 | 0.033768 | 0.007395 |\n\n*Frank Wolfe with more samples*\n\nThis is our interpretation of the Reviewer's comment. Fix both sets of distributions. Increase the number of samples for Frank-Wolfe but fix the number of samples for GW-SDP. What happens?\n\nWe conducted this experiment and we noticed that the objective value for Frank-Wolfe (GW-CG in table) decreases as we increase the number of samples and approach the objective value obtained by the SDP relaxation, which is obtained using few samples.\n\nn\tGW-SDP\tGW-SDP Runtime (s)\tGW-CG\tGW-CG runtime (s)\n10\t0.4577\t6.3753\t1.135940\t0.000389\n100\t\t\t0.629425\t0.007571\n1000\t\t\t0.540984\t2.520011\n10000\t\t\t0.496796\t138.358954\n\nWe noticed that the objective value from Frank-Wolfe is greater than the objective value from GW-SDP. We do not know if this is because the solution from Frank Wolfe is sub-optimal, or if GW-SDP returns a smaller objective than the GW distance between the continuous distributions because of discretization error (from finite samples). This is an interesting question to investigate.\n\nIn any case, the experiment suggests it may be possible to mitigate the (lack of) global optimality issues we raise about Frank Wolfe simply by increasing the number of sample points. This is indeed a cheap way. Nevertheless, without the relaxation we propose, it is not possible to tell if the improved objective value obtained by increasing the number of samples is indeed globally optimal. Also, this experiment suggests that the SDP relaxation is able to obtain a far superior objective value with fewer data points compared to Frank Wolfe. One can further investigate trade-offs between these methods (as future work).\n\nWe caution against generalizing this approach of increasing samples to attain a better minima too broadly. For Frank Wolfe to converge to the global optimal solution, we need the optimization landscape to be favorable. This might not happen for more complicated data distributions or perhaps graphs. Again, without a relaxation (or a suitable dual problem), one cannot be certain if Frank Wolfe obtains the global solution.\n\n*Approximation gap*\n\nWe checked this. The value is numerically equal to one. The plot appears to be less than one due to an issue with the graph plotting software.\n\n*Readability*\n\nThanks for the suggestion. We will make these changes in the revision.\n\n*$m \\neq n$*\n\nWe performed an additional experiment where the number of samples in one distribution is fixed ($n=8$) and we vary the number of samples $m$ in the other distribution; see Figure 2 of the attached PDF. We notice that the relaxation is exact whenever $m$ is a multiple of $n$. On the other hand, the relaxation fails to be exact if $m$ is not a multiple of $n$.\n\n*Heuristic solver*\n\nNote that the heuristic solver will not be in the main body of the revised manuscript, based on a suggestion by another Reviewer.\n\nThe parameters are chosen heuristically. The parameters $\\gamma_2​$ and $\\gamma_3$ control the step size in each iteration, while $\\gamma_1$​ is used for backtracking to prevent $\\gamma_2$​ and $\\gamma_3​$ from becoming too large. Through experimentation, we found that the algorithm performs better for relatively small choices. \n\n*Behavior of SDP relaxation when dimensions of the Gaussians change*\n\nWe conducted experiments using Gaussian distributions with varying dimensions and found that the performance of the GW-SDP remained consistent across all tested dimensions. As such, we report results for a single representative dimension. \n\n*Barycenter algorithm*\n\nCould the Reviewer clarify which papers [1] and [2] refer to? Thanks.\n\n*Extensions*\n\nIt is generally possible to extend the semidefinite relaxation to variants of the GW problem. We briefly describe the semidefinite relaxation to the outlier-robust GW problem by Kong et. al [KLTS:23]. Here, $(X,d_{X})$ and $(Y,d_{Y})$ are two metric spaces with accompanying measures $\\mu$ and $\\nu$. The distance between $\\mu$ and $\\nu$ is \n\n$\\min~~\\langle L, P\\rangle+\\tau_1 d_{KL} (\\pi 1,\\alpha) + \\tau_2 d_{KL} (\\pi^T 1,\\beta)$\n\n$\\mathrm{s.t.}\\left( \\begin{array}{cc} P & \\mathrm{vec}(\\pi)^T \\\\\\ \\mathrm{vec}(\\pi) & 1 \\end{array} \\right) \\succeq 0 $\n\n$\\qquad\\sum_{i}P_{(i,j),(k,l)} = f_{j}^{k,l}$, $\\Sigma_{j} P_{(i,j),(k,l)} = g_i^{k,l}$\n\n$\\qquad P\\geq 0$\n\n$\\qquad d_{KL}(\\mu,\\alpha)\\leq\\rho_1,d_{KL}(\\nu,\\beta)\\leq\\rho_2$\n\nNote: The resulting formulation is convex but not an SDP because of the KL divergence. We discuss further extensions in the revised manuscript.\n\n*References*\n\n[KLTS:23] L Kong, J Li, J Tang, & A M-C So. (2023). Outlier-robust Gromov-Wasserstein for Graph Data. In Proceedings of the 37th International Conference on Neural Information Processing Systems.\n\n[SP:04] RW Sumner and J Popovíc. (2004). Deformation transfer for triangle meshes. ACM Transactions on Graphics.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L2wwUqB2ug", "reviewer": "Reviewer_fpsx", "summary": "The authors propose a new algorithm for measuring the Gromov-Wasserstein (GW) distance, an metric for assessing the similarity of point clouds in different spaces. Their algorithm formulates the computation of the GW distance as a quadratic programming problem, which is then solved by semidefinite relaxation. The authors conducted experiments using several synthetic datasets and confirmed that the proposed algorithm yields solutions with smaller objective function values compared to other algorithms.", "questions": "* The experiments emphasize the sparsity of the output of the proposed method, but what is the benefit of this sparsity? Additionally, why does sparsity emerge in the results?\n\n* The positioning of the Heuristic Solver proposed in Section 5 within this paper is unclear. Is this method one of the proposals of this paper? If so, it is necessary to explain its position within existing research and its motivation in more detail. If not, its contribution becomes unclear, and it is recommended to move it to the appendix.", "limitations": "The authors are aware of the significant computational complexity and discuss potential directions to address this issue. While this acknowledgment is commendable, the substantial computational complexity remains a critical drawback of this method. Unless this issue is resolved, the overall contribution of the paper must be considered limited.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "* The proposed method is grounded in solid theoretical foundations.\n* The proposed method has been experimentally verified to produce solutions with smaller objective function values.\n* The paper is well-written, and its contributions are clearly described.", "weaknesses": "* The novelty is limited. It is well-known that the computation of GW can be reduced to a quadratic programming (QP) problem, and solving a non-convex QP through semi-definite relaxation is a very common approach in the field of optimization. Additionally, as the authors themselves point out, such methods have been proposed for the quadratic assignment problem (QAP), which is closely related to GW. Thus, the proposed method is merely a simple variant of these approaches, and its technical contribution is minimal.\n\n* The computational complexity of the proposed method. The proposed method requires solving an SDP with a matrix of size \n$mn \\times mn$ as variables. Although SDPs can indeed yield globally optimal solutions with relatively low computational effort, it is well-known that the computational complexity increases sharply with the size of the problem. It is thus challenging to solve an SDP with a matrix of size $mn \\times mn$ as variables in practical applications. In fact, Table 1 shows that for \n$n=20$, the computation time exceeds 200 seconds, indicating difficulties in applying the method to real-world problems.\n\n* Insufficiency of the experiments. The experiments conducted in the paper are all small-scale and limited to ten artificial datasets, which is insufficient to demonstrate the effectiveness of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Limited novelty*\n\nWe emphasize, the paper has multiple contributions. The first contribution is that we compute globally optimal solutions to the GW problem. We can prove that our solutions are globally optimal. There is no existing work (as far as we are aware of), published or unpublished, that achieves this. This contribution alone, we believe, is a significant contribution.\n\nThe second contribution is to point out that many existing methods do not compute globally optimal solutions. This point, we believe, is a very concerning development, and researchers working on GW need to be aware.\n\nThe Reviewer is concerned with the limited novelty because the relaxation is a variant of an existing relaxation for the QAP. The point we make here is that this particular variant we propose is the simplest variant that answers the previous two questions.\n\nWe hope the Reviewer appreciates the conceptual aspects of our paper, namely that global optimality and certificate of optimality, are fundamental aspects of optimization.\n\n*Sparsity*\n\nWhen $m=n$, the feasible set of the GW problem is the set of doubly stochastic matrices. The extreme points of the set of doubly stochastic matrices is the collection of permutation matrices – this is known as the Birkhoff von-Neumann theorem. When $m \\neq n$, the feasible set is known as the transportation polytope. The extreme points correspond to bipartite graphs (the set of vertices are $\\alpha$ and $\\beta$) that have no cycles. These matrices are also sparse.\n\nThe optimal solution of a convex program whose feasible region is the set of doubly stochastic matrices or more generally the transportation polytope tends to be sparse. This is because optimal solutions tend to lie on low-dimensional faces, which are sparse (this is a known phenomenon in convex geometry).\n\nIn short, the optimal solution to the GW problem should generally be sparse. The solutions to GW-SDP are sparse, and this is a good sign. The solutions obtained by Conjugate Gradient tend to be sparse, which is also a good sign. On the other hand, if the solution is non-zero everywhere, we can be certain the solution is sub-optimal. This is the case for e-GW solvers, and the reason is that e-GW adds a bias to the objective; that is, they solve a slightly different problem.\n\n*Heuristic solver*\n\nWe will place the heuristic solver in the appendix, as recommended.\n\n*Unless this issue is resolved, the overall contribution of the paper must be considered limited.*\n\nWe hope the Reviewer will take into consideration that developing scalable algorithms for solving large-scale SDPs is an active research area and an open challenge. In fact, for the closely related semidefinite relaxation of the QAP, state-of-the-art methods are only able to solve problem instances where the dimension is around 40 [OWX:18]. The largest dimension in our experiments is 32, which is not far off the state of the art.\n\nThere are many promising directions to develop more scalable algorithms for solving the GW-SDP problem. Some of these were discussed in the manuscript. We discuss first-order methods in the response to another Reviewer. These directions are promising but the scope of the work goes comfortably the scope of a single paper. We urge the Reviewer to moderate expectations as to what is technically feasible within the scope of a single paper. \n\nAgain, we reiterate an earlier point, that there is no other work we are aware of that addresses the global optimality of the GW problem. Addressing global optimality is one of the key contributions of this paper.\n\n*References*\n\n[OWX:18] D. E. Oliveira, H. Wolkowicz, & Y. Xu, (2018). ADMM for the SDP relaxation of the QAP. Mathematical Programming Computation, 10(4), 631-658.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GBcMAnMnj7", "reviewer": "Reviewer_Xfoj", "summary": "The paper explores a semi-definite programming (SDP) based relaxation of the popular Gromov Wasserstein (GW) problem. The GW problem  is an instance of non-convex quadratic program (QP). Standard SDP relaxation of QPs has been explored in the literature. The present work leverages this SDP relaxation result. However, this standard SPD relaxation is not sufficient as the resulting minimization problem is unbounded from below. Hence, the paper tightens the relaxation via additional constraints which are motivated from the GW problem. Empirical evaluations are performed to showcase the effectiveness of the obtained solution, both in terms of quality and runtime efficiency.", "questions": "please see strength and weakness sections.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed SDP relaxation based approach for GW problem is an interesting idea and has not been explored in context of GW (to the best of my knowledge). This reformulation has interesting consequences such as \n    - an approximation ratio (Eqn 4) which can be computed from the solution obtained via the proposed solution. This ratio lower bounded by 1 and is equal to 1 only if the obtained solution is globally optimal. Hence, this approach provides an optimality certificate for a non-convex problem\n    - While no empirical results were shown in this regard, the proposed approach allows using a general GW cost tensor L. Existing approach such as (Peyré et al., 2016) can only employ decomposable costs (such as those obtained via L2 or KL loss). \n\n- The paper empirically evaluates the effectiveness of the proposed approach in terms of computational efficiency and quality (lower objective is better). While the proposed approach obtains better objective compared to current state-of-the-art GW-CG, its runtime (for problems of size n = 6,12,20) is around 500-150000 times higher than GW-CG (Table 1).  While the heuristic solver (GW-PGD) proposed in Section 5 is faster than the proposed GW-SDP, it is still at least 250 times slower than GW-CG and its objective becomes comparable to GW-CG as n increase. \n\n- The paper is well written, explaining the underlying concepts and the related works nicely.", "weaknesses": "- The paper provides a detailed discussion on the literature related to the quadratic assignment problem (QAP) and SDP relaxations of the QPs. The key technical contribution of the proposed work w.r.t. Zhao et al. (1998) is removing constraints related to \\pi being a permutation matrix, which also allows handling the m \\neq n setting (lines 125-137). \n\n- Very high runtime compared to GW-CG. This limits the practical utility of proposed GW-SDP or GW-PGD.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Detailed discussion on related work*\n\nCould we check if this comment was intended as a weakness? It does not sound like one. We assume this comment was misplaced. Could the Reviewer clarify?\n\n*High run-time*\n\nWe agree with the Reviewer’s concerns about run-time. We address some of these concerns in the global response.\nWe have been working on developing faster algorithms for solving the GW-SDP. Unfortunately, this is a difficult task. There are many promising directions to develop more scalable algorithms for solving the GW-SDP problem. Some of these were discussed in the manuscript. We discuss first-order methods in the response to another Reviewer. These directions are promising but the scope of the work goes comfortably the scope of a single paper.\n\nAs a note, for the closely related semidefinite relaxation of the QAP, state-of-the-art methods are only able to solve problem instances where the dimension is around 40 [OWX:18]. The largest dimension in our experiments is 32, which is not far off the state of the art.\n\n*References*\n\n[OWX:18] D. E. Oliveira, H. Wolkowicz, & Y. Xu, (2018). ADMM for the SDP relaxation of the QAP. Mathematical Programming Computation, 10(4), 631-658.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the Reviewers for taking time to provide valuable feedback. We have incorporated many of these suggestions with additional experiments which we believe improve the paper substantially. We outline some of these new experiments and contributions below, and describe them in further detail to the corresponding Reviewer who made these suggestions.

We are grateful that the Reviewers appreciate the conceptual contributions of our work, namely, that it computes global optimal solutions of the GW problem with a certificate of optimality. All Reviewers raised concerns about the run-time -- this is understandable. We too share the same concerns and are actively working on this aspect. We describe some of the technical difficulties below. Nevertheless, our work is the only work we are aware of that addresses global optimality, and we hope the Reviewers consider such a contribution valuable in spite of the run-time concerns.

We provide below general responses for common concerns questions. For the more detailed answer to each reviewer's question, we provide the answer as a comment following each of the individual reviews.

*Experiment on real data and more baseline solvers*

We use a publicly available database of triangular meshes (Sumner et al. 2004). We obtain 18 points and compute distance matrices using Dijkstra's algorithm. Each object's probability measure is chosen to be uniform. We apply (GW-SDP) to the corresponding metric-measure spaces to determine the correspondence between the selected vertices across different objects. Two representative examples are given in Figure 1 in the attached pdf file.

Following are the results when we do matching of distances matrices of different objects. In general, we expect shapes of the same animals to have a smaller GW distance than shapes of different animals, which is indeed the case for the three GW formulations. We still notice that GW-SDP consistently returns the smallest value when performing the same matching task.

|               	| GW-SDP   | GW-CG	| eGW-PPA  |
|-------------------|----------|----------|----------|
| Elephant-Elephant | 0.007416 | 0.043879 | 0.025688 |
| Elephant-Cat  	| 0.015695 | 0.050594 | 0.042214 |
| Cat-Cat       	| 0.006549 | 0.016634 | 0.006757 |
| Cat-Horse     	| 0.011040 | 0.033736 | 0.011041 |
| Horse-Horse   	| 0.006287 | 0.033768 | 0.007395 |

*Experiment where $m \neq n$*

We performed an additional experiment where the number of samples in one distribution is fixed ($n=8$) and we vary the number of samples $m$ in the other distribution; see Figure 2 of the attached PDF. We notice that the relaxation is exact whenever $m$ is a multiple of $n$. On the other hand, the relaxation fails to be exact if $m$ is not a multiple of $n$. For the runtime, please check the results in Table 1 of the pdf.

*Applying Frank-Wolfe with more sample points*

Reviewer 3Vyi raised an interesting suggestion to increase the number of samples for GW-CG (non-convex GW solver using conditional gradient descent or Frank-Wolfe algorithm) vs our GW-SDP solver for a fixed number of samples. We noticed that the objective value for GW-CG decreases as we increase the number of samples. For 100000 sample points, the GW-CG algorithm is more expensive and has a poorer objective value than our method with 10 sample points. This suggests that our method can give good approximations of the GW distance with fewer sample points than existing methods.

| n 	| GW-SDP | GW-SDP Runtime (s) | GW-CG	| GW-CG runtime (s) |
|-------|--------|--------------------|----------|-------------------|
| 10	| 0.4577 | 6.3753         	| 1.135940 | 0.000389      	|
| 100   |    	|                	| 0.629425 | 0.007571      	|
| 1000  |    	|                	| 0.540984 | 2.520011      	|
| 10000 |    	|                	| 0.496796 | 138.358954    	|

*Prohibitive run time of the GW-SDP solver and potential improvements*

We acknowledge the concerns about the run time of the GW-SDP.

We are actively trying to develop faster algorithms. Our current manuscript suggests some potential directions. Reviewer nsV6 suggests first order methods and we discuss this in detail in our response to Reviewer nsV6. In short, many existing techniques do not apply. In fact, in the work by Oliveira et al. on semidefinite relaxations on the closely related QAP, the authors solve problem instances of size 40. In our experiments, the largest instance is 32, and hence not far off state of the art.

Nevertheless, we hope the Reviewer appreciates the important conceptual contributions of our work. It is the only work we are aware of that addresses global optimality in the GW problem.

*References*

[OWX:18] D. E. Oliveira, H. Wolkowicz, & Y. Xu, (2018). ADMM for the SDP relaxation of the QAP. Mathematical Programming Computation, 10(4), 631-658.

[SP:04] RW Sumner and J Popovíc. (2004). Deformation transfer for triangle meshes. ACM Transactions on Graphics.

Meta-review: The paper received mixed, but mostly positive reviews. Reviewers note an elegant and new formulation that allows global optimiyation, and elegant proofs, solid and interesting theoretical aspects and good experimental results in terms of objective values of the optimization problem. On the downside limited evaluation on mostly synthetic examples and high runtime are noted. The rebuttal is positively acknowledged.
Decision: Accept (poster)