Semidefinite Relaxations of the Gromov-Wasserstein Distance

Authors: junyu  chen
binh t nguyen
shang  hui
koh  yong
sheng  soh
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 02:51:25

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.

Main paper: 
 introduction: 
 The optimal transport (OT) problem concerns the task of finding a 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 in generative modeling (Arjovsky et 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 (Schiebinger et al., 2019; Bunne et al., 2023 Bunne et al., , 2024)) .Let α ∈ Σ m and β ∈ Σ m be discrete probability distributions over a metric space -here Σ m := {α ∈ R m + , m i=1 α i = 1} denotes the probability simplex. Let C ∈ R m×n be the matrix such that C i,j models the transportation cost between points x i ∼ α and y j ∼ β. 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 π W def.π∈Π(α,β) ⟨C, π⟩.(1)Here, Π(α, β) = {π ∈ R m×n + : π1 n = α, π ⊤ 1 m = β} denotes the set of couplings between probability distributions α, β ∈ Σ m , while 1 m ∈ R m denotes the vector of ones. The OT problem (1) is an instance of a linear program (LP), and hence admits a global minimizer.One limitation of the classical OT formulation in (1) is that the definition of the cost matrix C requires the probability distributions α and β 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 of Mémoli (2011) formulates an extension of the OT problem known as the Gromov-Wasserstein distance (GW) whereby one can define an analogous OT problem given knowledge of the cost matrices for the respective spaces where α and β reside in. More concretely, let the tuple (C, α) ∈ R m×m × Σ m denote a discrete metric-measure space. Given a smooth, differentiable function ℓ : R × R → R, the Gromov-Wasserstein distance between two discrete metric-measure spaces (C, α) and (D, β) is defined by GW (C, D, α, β) def.π∈Π(α,β)ℓ(C i,k , D j,l )π i,j π k,l = min π∈Π(α,β)⟨L(C, D) ⊗ π, π⟩.(GW)Here, the transportation cost is specified by the four-way tensor that measures the discrepancy between the metrics C and D L(C, D) i,j,k,l def.= ℓ(C i,k , D j,l ).(2) The squared loss error, for instance, is a common choice. Following Peyré et al. (2016) , we define the tensor-matrix multiplication by[L ⊗ π] i,j def. = k,l L i,j,k,l π k,l .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-Cuaz 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(π), L vec(π)⟩ s.t. π ∈ Π(α, β).(GW+)Here, (L ij,kl ) ij,kl ∈ R mn×mn denotes the flattened 2-dimension tensor of L, while the vectorization of a matrix π ∈ R m×n is given by vec(π)def.= [π 11 , π 21 , . . . , π m1 , . . . , π mn ] ⊤ ∈ R mn .The constraint π ∈ Π(α, β) 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 of cost matrices (2), L is never positive semidefinite as these are zero on the diagonal while the off-diagonal entries are non-negative.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 a 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 in 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
main contributions: 
 The main contribution of this work is to propose a strong semidefinite programming (SDP)-based relaxation for the Gromov-Wasserstein distance that leads to globally optimal solutions in many instances. Concretely, let (π sdp , P sdp ) denote an optimal solution to the following GW-SDP(C, D, α, β)def.π∈R m×n , P ∈R mn×mn ⟨L, P ⟩s.t. P vec(π) vec(π) ⊤ 1 ⪰ 0 π ∈ Π(α, β) P vec(e i 1 ⊤ n ) = α i vec(π), i ∈ [m] P vec(1 m e ⊤ j ) = β j vec(π), j ∈ [n] P ≥ 0 (GW-SDP)Here, e i 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 linear and quadratic terms of transportation plans (we discuss these aspects in greater detail in Appendix B). A simpler way to express the condition P vec(e i 1 ⊤ n ) = α i vec(π) is to note that P vec(e i 1 ⊤ n ) = α i vec(π) ⇔ j P (i,j),(k,l) = α i π k,l , P vec(1 m e ⊤ j ) = β j vec(π) ⇔ i P (i,j),(k,l) = β j π k,l .We begin by noting a basic observation: Let π ∈ Π(α, β) be a transportation plan.Then the tuple (π, P ) = (π, vec(π)vec(π) ⊤ ) is a feasible solution to (GW-SDP) sincevec(π)vec(π) ⊤ vec(e i 1 ⊤ m ) = vec(π)⟨π, e i 1 ⊤ m ⟩ = vec(π)⟨π1 n , e i ⟩ = α i vec(π).The inequalities for β follow analogously. This implies that the optimal value of (GW-SDP) is a lower bound to the GW problem (GW): Let π ⋆ denote an optimal solution to the GW problem (note: this is (GW), which is equivalent to (GW+)). By recalling that the tuple (vec(π ⋆ ), vec(π ⋆ )vec(π ⋆ ) ⊤ ) is a feasible solution to (GW-SDP), one has⟨P sdp , L⟩ ≤ ⟨vec(π ⋆ ), L vec(π ⋆ )⟩ = ⟨π ⋆ , L ⊗ π ⋆ ⟩.(3)The inequality (3) provides us with a principled way of certifying global optimality of a given transportation plan. Let π ∈ Π(α, β) be an arbitrary transportation plan. A natural approach to quantify the quality of π is to compare its objective value with the optimal choice:Apx. Ratio(π) := ⟨π, L ⊗ π⟩ ⟨π ⋆ , L ⊗ π ⋆ ⟩ .This ratio is at least one and is equal to one if π is also globally optimal. A consequence of (3) is the following upper boundEQUATIONNote that all the quantities in the RHS can be computed efficiently as the solution of a SDP. Suppose we are able to do so, and in the process evaluate the RHS to be equal to one. Then, we have a proof that π sdp is the global optimal solution to the GW problem. In a recent work that appeared during the reviewing process of our work, the GW problem is shown to be 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 a 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-SDP) is 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 is that it is valid for all cost tensors L. This stands in contrast with other methods like the entropic GW (Peyré et al., 2016) , which is only applicable to the cost that can be decomposed to a specific form such as the ℓ 2 or discrete KL loss.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The main limitation of 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 a separate "Limitations" 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 authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or 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 it 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 address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 a QPs -these are optimization instances of the formEQUATIONQPs are an important class of optimization problems. If the matrix A 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 eigenvalues. 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 A 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-bound 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 branch-and-bound procedure.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) is equivalent to the following:min x∈R n ,X∈R n×n tr(AX) + 2b ⊤ x + c s.t. Bx ≤ d X x x ⊤ 1 ⪰ 0, rank X x x ⊤ 1 = 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 to quadratically constrained quadratic programs -QCQPs).By applying the same sequence of steps to (GW+), the standard SDP relaxation one arrives at is the following: minEQUATIONProblem ( 6) is 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 if P = vec(π)vec(π) ⊤ . Therefore, a simple way to improve the relaxation is to add any linear constraints that is satisfied by solutions of the form (π, P ) = (π, vec(π)vec(π) ⊤ ).First, π ≥ 0 for all π ∈ Π(α, β), and hence vec(π)vec(π) ⊤ ≥ 0. This means we may freely imposeP ≥ 0. (Nng.)Second, note that i π ij π kl = π kl ( i π ij ) = π kl β j . Subsequently, we may impose i P (i,j),(k,l) = β j π kl . This leads to the following set of equalities:P vec(e i 1 ⊤ n ) = α i vec(π), i ∈ [m], P vec(1 m e ⊤ j ) = β j vec(π), j ∈ [n]. (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 at 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 proposed for a different but closely related problem known as Quadratic Assignment Problem (QAP) (Dym et al., 2017; Kezurer et al., 2015; Zhao et al., 1998) . Mathematically, the QAP problem can be viewed as equivalent to (GW+) but with the additional restriction that m = n and that π is a permutation matrix. The key difference between the QAP and the GW problem we investigate is that π is not necessarily a permutation matrix in the GW problem, and necessarily so if m ̸ = n. As such, the relaxation in Zhao et al. ( 1998) is invalid. Our contribution is to 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 in (GW-SDP) is that the output will always be a feasible transportation plan in Π(α, β). 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 is not guaranteed to be a feasible solution, and additional rounding steps may be necessary.4 Numerical Experiments with Off-the-shelf Convex SolversIn this section, we implement our proposed SDP relaxation using an off-the-shelf solver. We compare our method with the Conditional Gradient (CG-GW) solver for finding local solutions (Vayer et al., 2019a) , and the Sinkhorn projections solver for computing solutions to 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 to show that our proposed SDP relaxation frequently computes the global optimal transportation plan whereas existing methods frequently do not.In what follows, we will use the 2-Gromov-Wasserstein 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'Donoghue et al., 2016) .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Justification: The main contribution is algorithmic. There is no 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 be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. Justification: The paper's focus is on improvements towards solving the GW distance problem and is foundational in nature. The societal impact is limited insofar as it improves existing ML techniques that are based on Optimal Transportation techniques. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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 specific 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 out 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 is 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 or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
matching gaussian distributions: 
 In this example, we estimate the GW distance between two Gaussian point clouds, one in R 2 , and the other in R 3 . A visualization of this dataset can be found in Figure 1a . 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 ⟨π, 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. For ease of visualization, we lift the source R 2 mm-spaces into target R 3 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 ̸ = 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 a multiple of n. On the other hand, when m is not a multiple of n, we still observe exactness, but much less frequently. Runtime Comparisons Table 1 presents the run-time of the GW-SDP problem in Experiment 1, running on a 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 a matrix of dimension mn × 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 is a first-order method, but 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 of the problem. In our setup, the optimal solution has low rank, and is rank-one if the relaxation is tight. There are numerous well-established methods for exploiting such structure. This is the subject of ongoing work. 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 a fixed number of samples. From Table 2 , 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. The objective of this task is to find matching between two random graphs that are drawn from the stochastic block model (SBM) (Abbe, 2017; Holland et al., 1983) with fixed inter/intra-clusters probability (the probability that nodes inside and outside a cluster are connected, respectively). The source is a three-cluster SBM whose intra-cluster probability is p = {1.0, 0.95, 0.9}, and the target is a two-cluster SBM whose intra-cluster probability is p = {1.0, 0.9}. 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 ℓ 2 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 a smaller total transportation cost (i.e., a smaller objective value) ⟨π sdp , L ⊗ π sdp ⟩. This trend is consistent with our observations in the previous experiments. Nevertheless, we see a degree of similarity between the transportation plans provided as 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 runs of different seeds and graph sizes.In this example, we consider an extension of 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, α) ∈ R m×d × R m×m × Σ m , where F def. = (f i ) i ∈ R dencodes the feature information of the sample point. The Fused GW-SDP (FGW-SDP) formulation is given byFGW-SDP(M F G , C, D, α, β, ξ) def. = min π∈R m×n , P ∈R mn×mn (1 -ξ)⟨M α,β , π⟩ + ξ⟨L(C, D), P ⟩ s.t. P vec(π) vec(π) ⊤ 1 ⪰ 0 (FGW-SDP) π ∈ Π(α, β) P vec(e i 1 ⊤ n ) = α i vec(π), i ∈ [m] P vec(1 m e ⊤ j ) = β j vec(π), j ∈ [n] P ≥ 0,with M F G = d(f j , g j ) i,j encodes the distance between node features, and ξ ∈ [0, 1] the interpolation 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 M F G by ℓ 2 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 a higher value and a denser transport plan. This indicates that the SDP relaxation of Fused-GW can be useful in graph matching applications, akin to Fused-GW. 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.We use a 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, elephant, 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 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 5 .For better visualization, in the representative examples we sampled only 6 points (4 representative points and 2 selected using fps). Table 3 illustrates the results when we perform matching of distance matrices across 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.  
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 is a convex program in 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 is possible to obtain the relaxation (GW-SDP) via duality. Concretely, let (GW++) refer to the original 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 rankP sdp vec(π sdp ) vec(π sdp ) ⊤ 1 = 1.Then the duality gap is zero; i.e., strong duality holds. 
related work: 
 There is a 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-type approach based on the conditional gradient (Frank-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(π) = 2 L(C, D) ⊗ π,This is a 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 π (i-1) , subsequently solves for π (i) with the loss G(π) at each ith-iteration, and finally projects π (i) into the feasible set by performing a 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 a 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 O(m 2 n 2 ) dependency. For instance, the work in Peyré et al. (2016) introduces an entropic regularization into the GW objective -this leads to a formulation that permits Sinkhorn scaling-like updates, much like the original scheme to solve entropic Wasserstein distance in Cuturi (2013) 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 in Scetbon et al. (2022) , which operates under the assumption that the cost matrices have low-rank structure. While the algorithm does not give guarantees about global optimality, it 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-ofsquare (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 a suitable sense, as the first level of the SOS hierarchy for polynomial optimization. Unfortunately, and as we note in Section 3, this alone is insufficient -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 a SDP relaxation of the closely related Gromov-Hausdorff problem, with an extension to the Gromov-Wasserstein problem. The relaxation is primarily designed for the Gromov-Hausdorff problem and is not equivalent to ours. The formulation also requires the probability distributions to be uniform whereas we do not. Another recent work by Ryner et al. (2023)  
conclusions and future directions: 
 In this work, we proposed a semidefinite programming relaxation of the Gromov-Wasserstein distance. Our initial results suggest that the relaxation (GW-SDP) is strong in the sense that π sdp frequently coincides with the globally optimal solution; moreover, we are able to provide a proof when this actually happens. These results are exciting, as it suggests a tractable approach for solving 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 is that it is specified as the solution of an SDP in which the matrix dimension is 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 to 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).Vincent  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: There is no 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 no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to 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 a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [Yes] Justification: The open source Python Optimal Transport package, released under the MIT license, is only used for algorithmic comparisons. Other datasets that using in the numerical experiment sections are also cited. Guidelines:Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we 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. 
 
 Appendix: Proof of Proposition 3.1. Let 1 ≤ s, t ≤ mn be coordinates such that L st > 0. Let v := v (s,t) ∈ R mn be a vector whose s-th entry is 1, whose t-th entry is -1, and whose remaining entries are zeros. Let π ∈ Π(α, β) be any transportation map and consider the matrix P c = vec(π)vec(π) ⊤ + cvv ⊤ . Notice that P c ⪰ vec(π)vec(π) ⊤ for all c ≥ 0. Hence the choice of variables π = π and P = P c are feasible. Then notice that the objective evaluates to⟨L, P c ⟩ = ⟨L, vec(π)vec(π) ⊤ ⟩ + c(L ss -2L st + L tt ) = ⟨L, vec(π)vec(π) ⊤ ⟩ -2cL st .We obtain the last equality by noting that L ii = 0 for all i (this is a property of cost matrices). The result follows by taking c → +∞.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 is 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 we call such settings strong duality.In this section, we explore these relationships in the context of the GW problem. As we shall see, the proposed SDP relaxation (GW-SDP) can be 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 denotea i = vec(e i 1 ⊤ n ), b j = vec(1 m e ⊤ j ). We proceed to describe the dual program. We start by defining the following dual variables:Y y y ⊤ t ⪰ 0 : P vec(π) vec(π) ⊤ 1 ⪰ 0 (a) λ i ∈ R : a ⊤ i vec(π) = α i , i ∈ [m] (b) µ j ∈ R : b ⊤ j vec(π) = β j , j ∈ [n] (c) Z ≥ 0 : P ≥ 0 (d) η i ∈ R mn : P a i = α i vec(π), i ∈ [m] (e) θ j ∈ R mn : P b j = β j vec(π), j ∈ [n] (f)As a reminder, the constraints in (b) and (c) specify the transportation map Π(α, β) while the constraints in (e) and (f) correspond to (Mar.). Theorem B.1. The Lagrangian dual of (GW-SDP) is given as followsmax λ ⊤ α + µ ⊤ β -t s.t. L -Z + 1 2 m i=1 (η i a ⊤ i + a i η i ⊤ ) + 1 2 n j=1 (θ j b ⊤ j + b j θ j ⊤ ) y y ⊤ t ⪰ 0, m i=1 λ i a i + α i η i + n j=1 µ j b j + β j θ j + 2y ≤ 0, Z ≥ 0.(GW-Dual)Furthermore, strong duality holds; that is, the duality gap between (GW-SDP) and (GW-Dual) is zero.It turns out that it is possible to derive the dual instance (GW-Dual) directly from (GW+), an equivalent formulation of the original GW problem, with additional constraints specified by (Nng.) and (Mar.). Concretely, consider minπ∈R m×n P ∈R mn×mn ⟨L, P ⟩ s.t. P = vec(π)vec(π) ⊤ π ∈ Π(α, β) P vec(e i 1 ⊤ n ) = α i vec(π), i ∈ [m] P vec(1 m e ⊤ j ) = β j vec(π), j ∈ [n] P ≥ 0. (GW++)The last three constraints on P are always satisfied so long as P = vec(π)vec(π) ⊤ , where π ∈ Π(α, β) is a transportation map. Hence these constraints on 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 are different, and we 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 P sdp and π sdp be the solution to GW-SDP. Suppose the matrix variable has rank equals to one, that is rankP sdp vec(π sdp ) vec(π sdp ) ⊤ 1 = 1.Then the duality gap for (GW++) is zero; i.e., strong duality holds.Proof. The rank condition implies P sdp = vec(π sdp )vec(π sdp ) ⊤ . Subsequently, the choice of variables π = π sdp and P = vec(π sdp )vec(π sdp ) ⊤ is a feasible solution to (GW++). This means (GW++) attains the same objective value as 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.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+). Consequently, (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 as the Lagrangian dual to both (GW++) and (GW-SDP), and strong duality establishes the equivalence between (GW-Dual) and (GW-SDP). We begin by defining these functions: H(η, θ, Z) := L -Z + 1 2 m i=1 (η i a ⊤ i + a i η i ⊤ ) + 1 2 n j=1 (θ j b ⊤ j + b j θ j ⊤ ), g(λ, µ, η, θ, y) := m i=1 λ i a i + α i η i + n j=1 µ j b j + β j θ j + 2y.+ m i=1 λ i (α i -a ⊤ i vec(π)) + n j=1 µ j (β j -b ⊤ j vec(π)) + m i=1 η i ⊤ (P a i -α i vec(π)) + n j=1 θ j ⊤ (P b j -β j vec(π)) -tr(ZP ) = min P tr ((H(η, θ, Z) -Y ) P ) + min π≥0 ⟨-g(λ, µ, η, θ, y), vec(π)⟩ + λ ⊤ α + µ ⊤ β -t.In the above minimization over P , we observe that the objective evaluates to -∞ if the following does not holdH(η, θ, Z) = Y.Similarly, in the minimization over π ≥ 0, the objective evaluates to -∞ if the following does not hold g(λ, µ, η, θ, y) ≤ 0.We impose these as constraints, and we add the additional constraint that Y ⪰ 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 exists a strictly feasible solution.Considerη i = (|λ min (L)| + 2)1, λ i = -2m for i ∈ [m], θ j = 0, µ j = 0 for j ∈ [n], t = 1, y = 0, and Z = (|λ min (L)| + 2)11 ⊤ -(|λ min (L)| + 1)Ifor some 1, 0 and I of appropriate dimension. Then we have Z > 0, andg(λ, µ, η, θ, y) = -2m m i=1 a i + m i=1 1 = -m1 < 0.Additionally, since H(η, θ, Z) = L + (|λ min (L)| + 1)I ≻ 0, t > 0 and y = 0, it follows that the LHS of the first constraint in (GW-Dual) is positive definite. Therefore, we find a feasible solution of (GW-Dual) such that strict inequality holds for all inequality constraints. Strong duality then follows.Proof of Theorem B.2. In addition to the dual variables (b)-(f), we define these additional dual variables:Y ∈ R mn×mn : P = vec(π)vec(π) ⊤ z ≥ 0 : vec(π) ≥ 0Then the dual function of (GW++) is given bymin π,P tr(LP ) -tr(Y (P -vec(π)vec(π) ⊤ )) + m i=1 λ i (α i -a ⊤ i vec(π)) + n j=1 µ j (β j -b ⊤ j vec(π)) + m i=1 η i ⊤ (P a i -α i vec(π)) + n j=1 θ j ⊤ (P b j -β j vec(π)) -tr(ZP ) -z ⊤ vec(π) = min P tr((H(η, θ, Z) -Y ) P ) A1 + min π vec(π) ⊤ Y vec(π) -   m i=1 (λ i a i + α i η i ) + n j=1 (µ j b j + β j θ j ) + z   ⊤ vec(π) A2 + λ ⊤ α + µ ⊤ β.To simplify notation, we denotep := m i=1 (λ i a i + α i η i ) + n j=1 (µ j b j + β j θ j ).Observe thatEQUATIONmax π∈R m×n A 2 = -1 4 (p + z) ⊤ Y † (p + z) , if Y ⪰ 0 and (I -Y Y † )(p + z) = 0 -∞ , otherwiseHence, the dual of (GW++) is given bymax λ,µ,y,z,Z λ ⊤ α + µ ⊤ β - 1 4 (p + z) ⊤ Y † (p + z) s.t. Y ⪰ 0 (I -Y Y † )(p + z) = 0 Y = H(η, θ, Z) Z ≥ 0 z ≥ 0 .We re-write this as max λ,µ,y,z,Z,tλ ⊤ α + µ ⊤ β -t s.t. 1 4 (p + z) ⊤ Y † (p + z) ≤ t Y ⪰ 0 (I -Y Y † )(p + z) = 0 Y = H(η, θ, Z) Z ≥ 0 z ≥ 0By taking Schur complements and by replacing Y with H(η, θ, Z), the above optimization instance reduces to max λ,µ,z,Z,tλ ⊤ α + µ ⊤ β -t s.t. H(η, θ, Z) -1 2 (p + z) -1 2 (p + z) ⊤ t ⪰ 0 Z ≥ 0 z ≥ 0Note that g(λ, µ, η, θ, y) = p + 2y, the theorem then follows by doing a change of variable y = -1 2 (p + z).One popular application of optimal transport is to 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 in Euclidean space (Fréchet), the Wasserstein barycenter is defined as the solution of a weighted sum of OT distances over the space of measures. An efficient algorithm to compute the discrete OT barycenter with entropic regularization was proposed in Benamou et al. (2015) , and was later extended to discrete metric-measure spaces with entropic GW distance in Peyré et al. (2016) .We show that it is straightforward to extend the GW-SDP formulation to find barycenters of a set of data as Fréchet means. For simplicity, we assume that the base histogram ᾱ, the size of the barycenters m ∈ N, and (λ k ) k such that k λ k = 1 are fixed. We aim to find a structure matrix C that minimizes minEQUATIONWe have the following corollary. Corollary D.1 (Adaptation of Proposition 3 in Peyré et al. (2016) ). In the special case of the squared loss ℓ(a, b) = (a -b) 2 , the solution of (7) readsEQUATIONwhere π sdp,k is the solution to GW-SDP(C k , C, α k , ᾱ) and the division is entry-wise.Corollary D.1 shows that we may apply iterative updates to solve for the barycenter C via the Block Coordinate Descent (BCD) algorithm. At each iteration, we solve K independent instances of the GW-SDP problem to find (π sdp,k ) k , and then compute C using (8) to solve for (7). A pseudocode for the GW-SDP barycenter calculation is provided in Algorithm 1. We demonstrate the effectiveness of the GW-SDP barycenter calculation by applying it to find the barycenter of a graph dataset. The dataset consists of 20 noisy graphs, created by adding random connections from a 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 a circular graph of 10 nodes.Algorithm 1 Computation of GW-SDP barycenters. Input: dataset {C k , α k } K k=1 ; {λ k } K k=1 . Initialize C. repeat for k = 1 to K do π sdp,k ← solve_GW-SDP(C k , C, α k , ᾱ).It 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. (2024) . Here, (X, d X ) and (Y, d Y ) are two metric spaces with accompanying measures µ and ν. The distance between µ and ν ismin ⟨L, P ⟩ + τ 1 d KL (π1, α) + τ 2 d KL (π T 1, β) s.t. P vec(π) T vec(π) 1 ⪰ 0 i P (i,j),(k,l) = f k,l j , Σ j P (i,j),(k,l) = g k,l i P ≥ 0 d KL (µ, α) ≤ ρ 1 , d KL (ν, β) ≤ ρ 2 .There is one technical aspect: In the marginal sums i P (i,j), (k,l) we set this equal to some constant f k,l j . In GW-SDP, the corresponding RHS term depends on π and α. In the robust set-up, α is an optimization variable, not a constant, which necessitates the above change. We remark that the resulting formulation is convex but not an SDP because of the presence of the KL divergence. 


Decision: 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.

Reviews: review: paper_summary: paper_summary: The authors provide SDP relaxations of the Gromov-Wasserstein distance, which turns out to provide global optimal in many cases.
strength_weakness: strength_weakness: 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?
questions: questions: How does the runtime compare with that of commonly used algorithms?

If 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: limitations: The run-time is not discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* 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.
* It seems as though the estimation gap for the first point in Figure 1b is less than 1, though this should not be possible.  
* 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.
questions: 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?
* Can the authors provide more details on the choice of parameters in Section 5? How sensitive are the results to these parameter choices?
* 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?
* 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]? 
* 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.


[1] Gromov-wasserstein averaging of kernel and distance matrices, Peyré et al., 2016.
[2] Partial Gromov-Wasserstein Metric, Bai et al., 2024.
[3] Outlier-Robust Gromov-Wasserstein for Graph Data, Kong et al., 2023.
[4] On a linear Gromov-Wasserstein distance, Beier et al., 2022.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.

* The computational complexity of the proposed method. The proposed method requires solving an SDP with a matrix of size 
$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=20$, the computation time exceeds 200 seconds, indicating difficulties in applying the method to real-world problems.

* 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.
questions: 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?

* 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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). 

- Very high runtime compared to GW-CG. This limits the practical utility of proposed GW-SDP or GW-PGD.
questions: questions: please see strength and weakness sections.
limitations: limitations: N/A

Comments: title: Comments on the Authors' Rebuttal
Response to rebuttal
Addendum about global optimality claims
Thank you!
Response to comment by Reviewer Xfoj
Response to authors' rebuttal
Comments on the Authors' Rebuttal
comment: >I believe that Mathias Staudigl, Shimrit Shtern, and Pavel Dvurechensky are working on related first-order methods suitable for problems with many constraints and possibly non-linear (e.g. entropy) objectives, but I cannot provide the pre-print at the moment.

Thank you for the reference. We will look out for it.

>I should like to say I also find the response to reviewer fpsx (with the claims of global optimality unquantified) underwhelming.

When writing the rebuttal, we intended to write a quick summary before moving on to the other points in the rebuttal. The claims of global optimality were to be understood under the conditions that the approximation ratio is one. This was a point we made in the manuscript. When writing the rebuttal, it did not occur to us that it was necessary to repeat these conditions. Unfortunately, the rebuttal may have come across as overstating an incorrect claim. That is not our intention, and we apologize for the confusion.

To be clear, the claims of global optimality occurs only when the approximation ratio is one.

(In the follow-up replies to Reviewer fpsx you will find the follow-up exchange on this topic.)
Thank you for going through the rebuttal and your vote of confidence.
>The issue related to sparsity is not a major concern. However, I believe that the discussion on sparsity does not hold much significance and only serves to unnecessarily confuse the reader. Therefore, I suggest either removing the description or providing a more detailed explanation of its intent.

This is a useful suggestion and we will provide a more detailed explanation in the revision. Thanks for the suggestion.

>I understand your intention. The original paper presents an accurate description, so I don't see issues with it. However, the rebuttal lacks persuasive power, and my concerns regarding the novelty remain unresolved.

Thanks for understanding our intention, and we apologize for the confusion.

As for novelty, let's perhaps try to state our case a little differently. Besides our work, we are not aware of other work that address the issue of global optimality. When we say "addresses global optimality", we mean that the method computes the actual GW distance (up to numerical error) with a proof that it does so correctly. Methods that depend on performing descent within a neighborhood do not achieve that. It may compute the global minimum, or it might get stuck in a local optimum, but it won't know which case it belongs in, with certainty. The typical way to certify that one has the global minimum is to compute a lower bound to the GW problem -- usually, this is done via a suitable dual program.

The GW problem is believed to be computationally difficult (intractable). So we expect the dual problem to be equally difficult. Here, what we are offering is slightly different: We suggest a tractable (meaning polynomial time) method for computing a relaxation of the dual that is able to certify global optimality on many instances. Because we think finding the global optimal solution should be difficult (intractable), coming up with a tractable method that certifies global optimality in many instances is the next best thing one can hope for. This is precisely what we are offering.

It is correct that the specific SDP formulation is a minor variation of a closely related SDP relaxation for the QAP. We were upfront about this in the manuscript as well. There are a few things to note: We considered a few other relaxations but they did not work because for many instances, the approximation ratio was vacuous. The SDP formulation we arrived at was a specific formulation that gave meaningful ratios most of the time. But the point here is not that our relaxation is particularly novel (and we were careful to attribute our ideas to the source); the point here is that the relaxation helps to certify global optimality in many instances. This we think is an important contribution. There are no other methods we know of in the literature that solves this seemingly basic problem.

As such, the burden of the paper now shifts to quantifying how often the relaxation is exact. If exactness happens quite often, then the relaxation is useful. If exactness only occurs for very specific examples, then there is very little meaning to the relaxation. Our numerical experiments are intended to investigate how often the SDP is exact, and over fairly generic inputs. The largest instance we solve has $30$ points. In other words, the SDP is of size $900 \times 900$. This is considered moderate-sized for SDP. Most researchers working with SDPs would consider such a size very promising (meaning it suggests the relaxation is a powerful one). Now, $30$ points is considered small in data science and optimal transport applications. But the more relevant question here is the strength of the SDP, perhaps more so than the data analytical aspects.  Now, the Reviewer suggests that the exactness is due to the "small and simple" settings.  We don't agree with this characterization and our experiments are intended to suggest otherwise.  If the Reviewer has further reasoning to explain why the Reviewer thinks so, do let us know and we will be happy to engage.

In any case, thank you very much for your attention.
> For what it's worth, in writing the rebuttal, we intended to give a quick summary of our contributions before proceeding to the additional experiments we ran.

I understand your intention. The original paper presents an accurate description, so I don't see issues with it. However, the rebuttal lacks persuasive power, and my concerns regarding the novelty remain unresolved.

> The initial comments do not appear to be a concern and we answered the question as it is. 

The issue related to sparsity is not a major concern. However, I believe that the discussion on sparsity does not hold much significance and only serves to unnecessarily confuse the reader. Therefore, I suggest either removing the description or providing a more detailed explanation of its intent.
I thank the authors for their extensive response, which clarified some of the raised points. 

Overall, I think the contributions of the paper outweigh its deficiency. The new experiments conducted during the rebuttal period would significantly strengthen the paper. Given these points, I increased my score to Weak Accept.
In reading the response by other reviewers, it appears that other reviewers share similar concerns about overstating the claims.

For what it's worth, in writing the rebuttal, we intended to give a quick summary of our contributions before proceeding to the additional experiments we ran.

In writing "The first contribution is that we compute globally optimal solutions to the GW problem," we intended this sentence to be understood that it holds under the condition the approximation ratio is equals to one. From the reading the reviews, we believed the reviewers understood the extent of our claims. As such, it did not occur to us to repeat the conditions (namely that these claims hold if the approximation ratio equals one, which seems to hold fairly often empirically).

Unfortunately, it gave the inadvertent impression that we overstate our contributions.

That is not our intention. We apologize for the inaccurate statement about our claims. We hope it was clear from our paper what the extent of our claims of global optimality were.
Many thanks for the clarifications.

I believe that Mathias Staudigl, Shimrit Shtern, and Pavel Dvurechensky are working on related first-order methods suitable for problems with many constraints and possibly non-linear (e.g. entropy) objectives, but I cannot provide the pre-print at the moment.

I should like to say I also find the response to reviewer fpsx (with the claims of global optimality unquantified) underwhelming.
When we wrote that "... our work is the only work we are aware of that addresses global optimality ... " and "The first contribution is that we compute globally optimal solutions to the GW problem. We can prove that our solutions are globally optimal.", it was to be understood in the context that global optimality was attained if the computed ratio was one.

When writing the rebuttal, we believed that all Reviewers understood the conditions under which global optimality held. Hence in writing a rebuttal, when summarizing our contributions, we did not think it was necessary to repeat the conditions under which global optimality held.

Unfortunately, this summary has given the impression that we claimed global optimality in all instances. We do not claim such a thing. We hope it was clear from the original paper we do not claim global optimality in all instances. We apologize for the confusion. This was not our intention. We hope the paper was very clear about its claims and limitations.

> Given just a solution to GW problem, the paper's approximation ratio cannot be used to check whether the given solution is optimal or not.

To check if a solution is optimal, one typically needs to compute the dual problem (of some suitable form). Computing the dual is (sort of) unavoidable if you want a proof of optimality. The GW-SDP does this (in a way) because it is a convex program.

Also, given the solution to the GW-SDP formulation, one can certify the optimality, or the gap to optimality, of any proposed solution to the GW problem. Compute the approximation ratio. If it is equal to one, the proposed solution is optimal. If it is close to one, we know it is quite good.

> In the (limited) additional experiments during the rebuttal phase, the paper has also shown empirically that in the experiment that were performed, their approach reach optimal solution when m is a multiple of n. However, no theoretical justification is provided.

We do not provide theoretical justification. In fact, we should not expect the SDP to provide exact solutions to all instances because the GW problem is not known to be tractable to solve. There must be some inputs for which the SDP is not exact. The surprising aspect here is that the SDP is exact for many inputs, and that is the point our experiments make.

(As to providing theoretical justification, such as proving such a phenomenon holds for random instances, is a difficult research problem. We don't have an answer for this at the moment.) 

The Reviewer posed some further questions about outliers. We need a bit more time to respond to this and will provide a reply later.
I thank the authors for their response. I also went through other reviews and their discussions. Please find my observations below:

1. The detailed discussion on QAP related work is not a weakness and is much appreciated. However, from solution approach point of view, the key technical contribution of this works seems to be only the removal of constraints related to \pi being a permutation matrix, which also allows handling the m \neq n setting (lines 125-137). And this was done because GW problem setting is interesting also for m \neq n setting. Hence, novelty seems limited (and this was the weakness part, perhaps my earlier statement was not very clear). Regarding novelty, please also see the next point. 

2. The approximation ratio (Eqn 4) is also a novel contribution and interesting. However, in their global comments and one of the rebuttals to another review, the authors mention statements such as "... our work is the only work we are aware of that addresses global optimality ... " and "The first contribution is that we compute globally optimal solutions to the GW problem. We can prove that our solutions are globally optimal." I think this is a gross exaggeration of their contribution. My understanding of the contribution of this paper in this regard is as follows. Please excuse the verbosity. 
- The paper *does not* propose an algorithm that is guaranteed to converge to a globally optimal solution of the (discrete) GW problem. 
- The paper *can only confirm* whether the solution obtained by *its approach* has converged to a globally optimal solution. 
- The paper *has empirically shown* that in several (very) small scale problem setting, it achieves global optimality. Whether similar observations would hold for larger setting is unclear. 
- However, given a problem instance, we do not know beforehand whether the proposed approach will converge sub-optimally or otherwise. 
- Given just a solution to GW problem, the paper's approximation ratio cannot be used to check whether the given solution is optimal or not. 
- In the (limited) additional experiments during rebuttal phase, the paper has also shown empirically that in the experiment that were performed, their approach reach optimal solution when m is a multiple of n. However, no theoretical justification is provided. 

3. In the additional experiments done with more sample points for FW, the setting seems quite synthetic since the source and target points are sampled from a distribution (with no noise). In practice, the source and target datasets could be corrupted by noise/outliers. Say the source and target datasets had 5000 datapoints with some outliers as well. GW-SDP maybe run by sampling 10 points from source and target datasets. Does GW-SDP seem more susceptible to outliers since only 10 points were taken and hence an outlier has a greater chance to influence the results? In certain applications where the GW transport map required for domain adaptation [1], such sampling would again not be useful. 

[1]  Gromov-Wasserstein Alignment of Word Embedding Spaces. EMNLP 2018. 

4. While the authors have acknowledged and discussed it in the draft as well as in their response, the concerns about run-time and scalability of the approach, and its practical relevance remain.
We thank the reviewer for their quick response to our rebuttals. 

> Originality: The statement in the rebuttal, "The first contribution is that we compute globally optimal solutions to the GW problem," is inaccurate. To be precise, a solution is guaranteed to be globally optimal only when the right-hand side of equation (4) equals 1.

In our paper, we do make it clear that we only claim global optimality when the RHS of equation (4) equals one.

> Sparsity: My concerns regarding sparsity have not been fully addressed. While it is correct that an optimal solution should be sparse, the argument that a sparse solution is close to the optimal one is not valid. Therefore, I find little merit in discussing the sparsity of the solutions.

The Reviewer asked why do solutions tend to be sparse. The initial comments do not appear to be a concern and we answered the question as it is. Our response simply states that solutions that are not sparse are certainly not optimal. Our proof of global optimality comes from the RHS of equation (4), not sparsity.
I have read the authors' rebuttal and would like to address the following points:

* Originality: The statement in the rebuttal, "The first contribution is that we compute globally optimal solutions to the GW problem," is inaccurate. To be precise, a solution is guaranteed to be globally optimal only when the right-hand side of equation (4) equals 1. Although Figure 4(b) shows that this condition is met in many cases, it is likely due to the small and simple problem setting. Therefore, the algorithm does not always yield a globally optimal solution, making the authors' claim in the rebuttal an overstatement. Moreover, as mentioned in my initial review, similar algorithms exist in the context of the Quadratic Assignment Problem (QAP).

* Computation Time: My concerns regarding computation time remain unresolved. While I recognize the value of this research even without significant reductions in computation time, the impact of the work is diminished as a result.

* Additional Experiments: I appreciate the additional experiments conducted by the authors.

* Sparsity: My concerns regarding sparsity have not been fully addressed. While it is correct that an optimal solution should be sparse, the argument that a sparse solution is close to the optimal one is not valid. Therefore, I find little merit in discussing the sparsity of the solutions.

Overall, my concerns have not been sufficiently resolved, and thus, I will maintain my previous score.