  The Gromov-Wasserstein (GW) distance is a variant 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 dual of the GW distance augmented
with constraints that relate the linear and quadratic terms of transportation
maps. Our relaxation provides a principled manner to compute the approximation
ratio of any transport map to the global optimal solution. Finally, our
numerical experiments suggest that the proposed relaxation is strong in that it
frequently computes the global optimal solution, together with a proof of
global optimality.
