Classical transport compares measures whose points already live in a common space and can be charged by a cross-space cost \(c(x,y)\). Gromov--Wasserstein geometry removes that common coordinate system. It compares two metric-measure spaces by asking whether pairs of points have similar internal distances under a probabilistic correspondence.
Metric-measure spaces and their equivalence
Definition. A metric-measure space is a triple \[ \mathsf X=(X,d_X,\mu_X), \] where \((X,d_X)\) is a Polish metric space and \(\mu_X\in\mathcal P(X)\). Two such spaces are isomorphic if there are full-measure subsets \(X_0,Y_0\) and a bijection \(T:X_0\to Y_0\) such that \[ T_\#\mu_X=\mu_Y,\qquad d_Y(Tx,Tx')=d_X(x,x'). \]
Only the intrinsic distance table and its probability weights matter. Rotating, translating, relabeling, or isometrically embedding the entire space does not change its metric-measure isomorphism class.
Distortion of a coupling
Definition. Let \(1\le p<\infty\) and \(\pi\in\Pi(\mu_X,\mu_Y)\). Its \(p\)-distortion is \[ \operatorname{dis}_p(\pi) = \left[ \iint |d_X(x,x')-d_Y(y,y')|^p \,\mathrm{d}\pi(x,y)\,\mathrm{d}\pi(x',y') \right]^{1/p}. \] In this note the Gromov--Wasserstein distance is \[ \operatorname{GW}_p(\mathsf X,\mathsf Y) = \inf_{\pi\in\Pi(\mu_X,\mu_Y)} \operatorname{dis}_p(\pi). \] Some references insert a factor \(1/2\); all formulas below use the convention displayed here.
A draw \((x,y)\sim\pi\) declares \(x\) and \(y\) probabilistic counterparts. Drawing two such pairs independently lets the objective compare the within-\(X\) distance \(d_X(x,x')\) with the within-\(Y\) distance \(d_Y(y,y')\). No distance between \(x\) and \(y\) is required.
Existence of an optimal correspondence. If \(X,Y\) are compact, then the infimum defining \(\operatorname{GW}_p\) is attained.
Proof. The set \(\Pi(\mu_X,\mu_Y)\) is weakly compact. If \(\pi_n\Rightarrow\pi\), then \(\pi_n\otimes\pi_n\Rightarrow\pi\otimes\pi\). The distortion integrand is continuous and bounded on \((X\times Y)^2\), so its integral converges. The objective is therefore continuous on a compact set.
The metric theorem
Theorem. On isomorphism classes of compact metric-measure spaces, \(\operatorname{GW}_p\) is a metric.
Proof. Nonnegativity and symmetry are immediate. If the spaces are isomorphic through \(T\), then \((\operatorname{id},T)_\#\mu_X\) has zero distortion.
For the triangle inequality, let \(\pi_{XY}\in\Pi(\mu_X,\mu_Y)\) and \(\pi_{YZ}\in\Pi(\mu_Y,\mu_Z)\). The gluing lemma produces a law \(\eta\) on \(X\times Y\times Z\) with these two marginals. Let \(\pi_{XZ}\) be its \((X,Z)\)-marginal. Minkowski's inequality in \(L^p(\eta\otimes\eta)\) gives \[ \operatorname{dis}_p(\pi_{XZ}) \le \operatorname{dis}_p(\pi_{XY}) + \operatorname{dis}_p(\pi_{YZ}), \] because \(d_X-d_Z=(d_X-d_Y)+(d_Y-d_Z)\). Taking infima proves the triangle inequality.
Finally suppose \(\operatorname{GW}_p=0\). By compactness an optimal \(\pi\) exists with zero distortion. Hence \[ d_X(x,x')=d_Y(y,y') \] for \((\pi\otimes\pi)\)-almost every pair \(((x,y),(x',y'))\). After removing a null set, this holds throughout the support relation. If one \(x\) corresponded to both \(y\) and \(\tilde y\), setting the two \(X\)-coordinates equal would give \(d_Y(y,\tilde y)=0\), hence \(y=\tilde y\); similarly in the other direction. The relation is therefore the graph of a measure-preserving isometry between the supports.
Finite spaces and a quadratic assignment problem
Let \(X=\{x_i\}_{i=1}^n\), \(Y=\{y_j\}_{j=1}^m\), with weights \(a_i,b_j\), and distance matrices \(D^X,D^Y\). A coupling is a nonnegative matrix \(P\) satisfying \(P\mathbf1_m=a\) and \(P^{\mathsf T}\mathbf1_n=b\). Then \[ \operatorname{GW}_p^p = \min_{P} \sum_{i,k=1}^n\sum_{j,\ell=1}^m |D^X_{ik}-D^Y_{j\ell}|^pP_{ij}P_{k\ell}. \] Unlike discrete Kantorovich transport, this objective is quadratic and generally nonconvex.
Quadratic expansion. For \(p=2\), \[ \operatorname{dis}_2^2(P) = \sum_{i,k}(D^X_{ik})^2a_ia_k + \sum_{j,\ell}(D^Y_{j\ell})^2b_jb_\ell - 2\sum_{i,k,j,\ell} D^X_{ik}D^Y_{j\ell}P_{ij}P_{k\ell}. \] Thus minimizing distortion is equivalent to maximizing the correlation of the two distance matrices under \(P\otimes P\).
If the weights are uniform and \(P\) is restricted to permutation matrices, this becomes a quadratic assignment problem. The relaxed coupling polytope allows soft correspondences and spaces with different numbers of points, but it does not make the objective convex.
Intrinsic lower bounds
Let \[ \rho_X=(d_X)_\#(\mu_X\otimes\mu_X) \] be the distribution of the distance between two independent points of \(\mathsf X\), and define \(\rho_Y\) similarly.
Distance-distribution bound. \[ W_p(\rho_X,\rho_Y) \le \operatorname{GW}_p(\mathsf X,\mathsf Y). \]
Proof. Every \(\pi\in\Pi(\mu_X,\mu_Y)\) makes \[ \bigl(d_X(x,x'),d_Y(y,y')\bigr)_\#(\pi\otimes\pi) \] a coupling of \(\rho_X,\rho_Y\). Its \(p\)-cost is exactly \(\operatorname{dis}_p^p(\pi)\). Minimize first over all couplings of the distance distributions, then over \(\pi\).
A sharper hierarchy can compare pointwise eccentricities \[ e_X(x)=\left(\int d_X(x,x')^p\,\mathrm{d}\mu_X(x')\right)^{1/p}. \] Reverse Minkowski implies that the Wasserstein distance between \((e_X)_\#\mu_X\) and \((e_Y)_\#\mu_Y\) is also bounded by \(\operatorname{GW}_p\). Such invariants are inexpensive certificates, but equality need not hold because they discard higher-order geometry.
Gromov--Wasserstein geodesics
Displacement interpolation of metrics. Let \(\pi^\star\) be optimal between compact spaces \(\mathsf X,\mathsf Y\). For \(0<t<1\), put \[ \mathsf Z_t = (X\times Y,d_t,\pi^\star),\qquad d_t((x,y),(x',y')) = (1-t)d_X(x,x')+t\,d_Y(y,y'). \] With the natural endpoint identifications, \[ \operatorname{GW}_p(\mathsf Z_s,\mathsf Z_t) = |t-s|\,\operatorname{GW}_p(\mathsf X,\mathsf Y). \]
Proof. Couple \(\mathsf Z_s\) and \(\mathsf Z_t\) by using the same \((x,y)\) at both times. Since \(d_t-d_s=(t-s)(d_Y-d_X)\), this coupling has distortion \(|t-s|\operatorname{GW}_p(\mathsf X,\mathsf Y)\), proving the upper bound. Applying this upper bound to the three pieces \(\mathsf X\to\mathsf Z_s\to\mathsf Z_t\to\mathsf Y\), their upper bounds sum exactly to \(\operatorname{GW}_p(\mathsf X,\mathsf Y)\). The triangle inequality forces equality in every piece.
The interpolation changes the metric itself rather than moving points through a fixed ambient space. This is the intrinsic analogue of displacement interpolation.
Gromov--Monge maps and relaxation
If a measure-preserving map \(T:X\to Y\) exists, its distortion is \[ \left[ \iint |d_X(x,x')-d_Y(Tx,Tx')|^p \,\mathrm{d}\mu_X(x)\,\mathrm{d}\mu_X(x') \right]^{1/p}. \] Minimizing over such \(T\) is the Gromov--Monge problem. Replacing the graph coupling \((\operatorname{id},T)_\#\mu_X\) by an arbitrary \(\pi\) gives the Gromov--Wasserstein relaxation. As in classical transport, relaxation ensures compactness, but here even the relaxed objective remains nonlinear in \(\pi\).
Entropic computation and its limitation
A common numerical objective is \[ \operatorname{GW}_{p,\varepsilon}^p = \inf_{\pi\in\Pi(\mu_X,\mu_Y)} \left\{ \operatorname{dis}_p^p(\pi) + \varepsilon\operatorname{KL} (\pi\,\|\,\mu_X\otimes\mu_Y) \right\}. \] Linearizing the quadratic distortion at the current coupling produces an ordinary entropic transport subproblem, which can be solved by Sinkhorn scaling. Alternating or conditional-gradient schemes repeat this step.
What entropy does not fix. Entropic regularization makes each linearized subproblem smooth and numerically stable, but the full Gromov--Wasserstein objective remains nonconvex. Iterations may converge to different stationary points from different initializations; a small primal update is not a certificate of global optimality.
Features, barycenters, and structured data
If points also carry comparable features \(f_X(x),f_Y(y)\) in a common feature space with distance \(\delta\), fused Gromov--Wasserstein transport minimizes \[ (1-\alpha)\int\delta(f_X(x),f_Y(y))^p\,\mathrm{d}\pi + \alpha\iint|d_X(x,x')-d_Y(y,y')|^p \,\mathrm{d}\pi\,\mathrm{d}\pi. \] The endpoints \(\alpha=0\) and \(\alpha=1\) retain only feature matching and only intrinsic geometry, respectively.
A Gromov--Wasserstein barycenter minimizes \[ \mathsf Z\longmapsto \sum_{r=1}^R\lambda_r \operatorname{GW}_p^p(\mathsf X_r,\mathsf Z) \] over metric-measure spaces in a chosen model class. Unlike a Wasserstein barycenter, both the representative points and their internal distance matrix may be unknown.
Empirical metric-measure spaces
Comparison on a common ambient space. If \(\mu,\nu\in\mathcal P_p(X)\) on the same metric space, then \[ \operatorname{GW}_p((X,d,\mu),(X,d,\nu)) \le 2W_p(\mu,\nu). \]
Proof. Let \(\gamma\) couple \(\mu,\nu\). For two independent draws from \(\gamma\), \[ |d(x,x')-d(y,y')| \le d(x,y)+d(x',y'). \] Minkowski gives \(\operatorname{dis}_p(\gamma)\le2(\int d(x,y)^p\,\mathrm{d}\gamma)^{1/p}\). Infimize over \(\gamma\).
Empirical consistency. If \(X\) is compact and \(\widehat\mu_n=n^{-1}\sum_{i=1}^n\delta_{X_i}\) for i.i.d. \(X_i\sim\mu\), then \[ \operatorname{GW}_p((X,d,\widehat\mu_n),(X,d,\mu)) \longrightarrow0 \quad\text{almost surely}. \] Indeed, compactness gives \(W_p(\widehat\mu_n,\mu)\to0\).
Consistency does not by itself give a dimension-free rate, an identifiable pointwise correspondence, or reliable global optimization. Statistical error, symmetry-induced nonidentifiability, and numerical nonconvexity are three separate sources of uncertainty.
Relation to Gromov--Hausdorff geometry
Gromov--Hausdorff distance controls the largest distortion of a correspondence; Gromov--Wasserstein distance controls an \(L^p\) average distortion weighted by probability. The former is sensitive to every point, while the latter may ignore sets of very small mass. This distinction explains both the statistical robustness and the possible geometric blindness of the measure-weighted formulation.