The Gromov–Wasserstein distance of measured kernels #

A measured kernel is a triple (X, μ, ω): a measurable space X, a measure μ on it, and a kernel ω : X × X → Z with values in an extended metric space Z. A metric-measure space is the special case Z = ℝ and ω (x, x') = dist x x'. Two measured kernels living on different spaces cannot be compared pointwise; the Gromov–Wasserstein distance compares them through a coupling π of μ and ν, measuring how badly π distorts the two kernels. For an exponent p : ℝ≥0∞ the distortion of π is the L^p (π ⊗ π) seminorm

dis_p (π) = ‖(x, y), (x', y') ↦ edist (ωX (x, x')) (ωY (y, y'))‖_{L^p (π ⊗ π)},

and the p-Gromov–Wasserstein distance is its infimum over the couplings of μ and ν. This file defines both, with no factor 1 / 2, and proves the axioms of an extended pseudodistance under finiteness and measurability hypotheses: the distance vanishes from an almost-everywhere strongly measurable kernel on an s-finite measure to itself, it is symmetric for a sigma-finite measure on one side, and for 1 ≤ p and a finite middle measure it satisfies the triangle inequality whenever the two couplings glue along the middle carrier, in particular when the third carrier is standard Borel.

As for TauCeti.wassersteinEDist, the objective is an eLpNorm, so the exponent p = ∞ is a case of the definition: there the distortion is the π ⊗ π-essential supremum of the kernel discrepancy. For 0 < p < ∞ the p-th power of the distance is the infimum of the integrals ∫∫ edist (ωX (x, x')) (ωY (y, y')) ^ p d(π ⊗ π).

The kernels are only assumed almost-everywhere strongly measurable, AEStronglyMeasurable ωX (μ.prod μ): this gives the kernel an essentially separable range, so no separability, completeness or measurable structure is required of the target Z, and no topology is required of X. The measures are raw MeasureTheory.Measures, as for the Wasserstein distance; the theorems take the finiteness instances they use.

Main definitions #

TauCeti.gromovWassersteinDistortion p ωX ωY π — the L^p (π ⊗ π) seminorm of edist (ωX (x, x')) (ωY (y, y')).
TauCeti.gromovWassersteinEDist p μ ωX ν ωY — the infimum of the distortion over the couplings π of μ and ν.

Main statements #

TauCeti.gromovWassersteinEDist_le, TauCeti.le_gromovWassersteinEDist and TauCeti.gromovWassersteinEDist_lt_iff — the universal property of the infimum;
TauCeti.gromovWassersteinDistortion_map_prodMk_of_aemeasurable and TauCeti.gromovWassersteinDistortion_map_prodMk — the distortion of the plan (f, g)_# γ induced by two parametrizations f, g of the marginals, read on γ ⊗ γ, with TauCeti.gromovWassersteinEDist_le_eLpNorm_of_aemeasurable, TauCeti.gromovWassersteinEDist_le_eLpNorm and TauCeti.tendsto_gromovWassersteinEDist_zero_of_tendsto_eLpNorm the resulting distance bound and convergence criterion;
TauCeti.gromovWassersteinEDist_rpow and TauCeti.gromovWassersteinEDist_top — the integral-of-a-power formula for 0 < p < ∞ and the essential-supremum formula for p = ∞;
TauCeti.gromovWassersteinDistortion_congr_ae and TauCeti.gromovWassersteinEDist_congr_ae — invariance under almost-everywhere modification of the kernels;
TauCeti.gromovWassersteinDistortion_eq_zero_iff — for a weak extended metric target and a nonzero exponent, zero distortion is exactly almost-everywhere equality of the pulled-back kernels;
TauCeti.gromovWassersteinEDist_comp_prodMap_eq_zero — a measured kernel and its pullback along a measure-preserving map are at distance 0;
TauCeti.gromovWassersteinEDist_eq_zero_of_ae_eq_comp_prodMap — the same conclusion when the source kernel agrees almost everywhere with the pullback;
TauCeti.gromovWassersteinEDist_self, TauCeti.gromovWassersteinEDist_comm and TauCeti.gromovWassersteinEDist_triangle — the axioms of an extended pseudodistance, the triangle inequality for a standard Borel third carrier, from the general form TauCeti.gromovWassersteinEDist_triangle_of_exists_glue for any carriers along which the two couplings glue;
TauCeti.gromovWassersteinEDist_dirac_left and TauCeti.gromovWassersteinEDist_dirac_right — the distance to a one-point measured kernel ({y}, δ_y, ω) is the L^p (μ ⊗ μ) size ‖edist (ωX ·) (ω (y, y))‖_{L^p (μ ⊗ μ)} of ωX about the point ω (y, y).

Implementation notes #

The distance is an iterated ⨅ over plans and over proofs of TauCeti.IsCoupling, matching TauCeti.wassersteinEDist: two measures with no coupling, for instance finite measures of different total mass, are at distance ∞.

The distance is not a metric on measured kernels: a kernel and its pullback along a measure-preserving map are at distance 0 (TauCeti.gromovWassersteinEDist_comp_prodMap_eq_zero), and so are two kernels agreeing almost everywhere. Under the hypotheses above (finite measures, almost-everywhere strongly measurable kernels, 1 ≤ p and gluing carriers) it behaves as an extended pseudometric.

Some sources, among them Bauer, Mémoli, Needham and Nishino, put a factor 1 / 2 in front of the infimum; the distance here is twice theirs.

References #

F. Mémoli, Gromov–Wasserstein distances and the metric approach to object matching, Found. Comput. Math. 11 (2011), where the distance is defined on metric-measure spaces as an infimum of distortions over couplings and the triangle inequality is proved by gluing.
K.-T. Sturm, The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces, Mem. Amer. Math. Soc. 290 (2023).
M. Bauer, F. Mémoli, T. Needham and M. Nishino, The Z-Gromov–Wasserstein distance, J. Mach. Learn. Res. 26 (2025), for kernels with values in a general metric space Z.