TOPICS
Search

Gromov-Wasserstein Distance


The Gromov-Wasserstein distance compares metric spaces equipped with probability measures by transporting their internal pairwise distances (Mémoli 2011). For compact metric spaces (X,d_X) and (Y,d_Y) with Borel probability measures mu and nu, the quadratic convention is

 GW_2(X,Y)=1/2inf_(pi in Pi(mu,nu))(int|d_X(x,x^')-d_Y(y,y^')|^2dpi(x,y)dpi(x^',y^'))^(1/2),
(1)

where Pi(mu,nu) consists of probability measures on X×Y with marginals mu and nu. The factor 1/2 is a normalization convention. Unlike the Wasserstein distance, this definition requires no shared ambient metric space.

For finite spaces with masses a_i and b_j, a coupling is a nonnegative matrix P with row sums a_i and column sums b_j. Writing C_(ik)=d_X(x_i,x_k) and D_(jl)=d_Y(y_j,y_l) gives the squared-loss objective

 E(P)=sum_(i,j,k,l)(C_(ik)-D_(jl))^2P_(ij)P_(kl).
(2)

This quadratic form can also be studied for symmetric dissimilarity matrices that are not distance matrices of metric spaces. For uniform masses on equally sized sets, the extreme couplings are scaled permutation matrices, but a minimum of this quadratic objective need not occur at an extreme coupling (Vayer 2026).

For example, Vayer (2026, Example 4.3) gives

C=(0 4 8 5; 4 0 1 5; 8 1 0 0; 5 5 0 0)
(3)
D=(0 8 6 0; 8 0 4 1; 6 4 0 0; 0 1 0 0).
(4)

Let P_sigma have entry 1/4 in position (i,sigma(i)) and zero elsewhere. Among these 24 couplings the minimum of E(P_sigma) is 29/4, whereas

 E((11)/(24)P_((1,3,2,4))+(13)/(24)P_((1,4,3,2)))=(1367)/(192)<(29)/4.
(5)

Both matrices are nonnegative and have zero diagonals, but they fail the triangle inequality; this is not a counterexample for genuine metric spaces. Vayer (2026) credits Claude with finding this family of examples.


See also

Distance Matrix, Metric Space, Optimal Transport, Wasserstein Distance

Explore with Wolfram|Alpha

References

Mémoli, F. "Gromov-Wasserstein Distances and the Metric Approach to Object Matching." Found. Comput. Math. 11, 417-487, 2011. https://doi.org/10.1007/s10208-011-9093-5.Vayer, T. "On Sparsity, Extremal Structure, and Monotonicity Properties of Wasserstein and Gromov-Wasserstein Optimal Transport Plans." 13 Nov 2026. https://arxiv.org/abs/2602.16265v3.

Cite this as:

Weisstein, Eric W. "Gromov-Wasserstein Distance." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Gromov-WassersteinDistance.html

Subject classifications