Sliced Gromov-Wasserstein

Titouan Vayer; Rémi Flamary; Romain Tavenard; Laetitia Chapel; Nicolas Courty

Source-linked AI summary

Sliced Gromov-Wasserstein

Titouan Vayer, Rémi Flamary, Romain Tavenard, Laetitia Chapel, Nicolas Courty

arXiv:1905.10124v4May 24, 2019stat.MLcs.LG

TL;DR

GW compares distributions whose supports need not share a metric space, but its non-convex optimization is costly. The paper derives a closed form for 1D GW and builds SGW through slicing; it reports comparable capabilities at much lower computational cost.

Problem
GW can compare distributions without shared metric spaces, but its non-convex quadratic optimization is costly, limiting large-scale computation.
Source: §1 · p. 2, §2 · p. 4
Method
The paper derives a closed form for 1D GW from a quadratic assignment result and defines SGW by applying 1D GW to projected distributions.
Source: §1 · p. 3, §3 · p. 6
Results
SGW retains various GW properties while being much cheaper to compute, with discrete computation costing O(L n log(n)) for L sampled directions.
Source: §1 · p. 3, §5 · p. 10
Takeaways & Limitations
The authors report that SGW supports large-scale applications such as large mesh matching and generative adversarial networks.
Source: §1 · p. 3
The authors state that the proof of Theorem 3.1 contains an error and the result is false, although simulations suggest it is often true; other results remain valid.
Source: p. 1

Abstract

from arXiv · show

Recently used in various machine learning contexts, the Gromov-Wasserstein distance (GW) allows for comparing distributions whose supports do not necessarily lie in the same metric space. However, this Optimal Transport (OT) distance requires solving a complex non convex quadratic program which is most of the time very costly both in time and memory. Contrary to GW, the Wasserstein distance (W) enjoys several properties (e.g. duality) that permit large scale optimization. Among those, the solution of W on the real line, that only requires sorting discrete samples in 1D, allows defining the Sliced Wasserstein (SW) distance. This paper proposes a new divergence based on GW akin to SW. We first derive a closed form for GW when dealing with 1D distributions, based on a new result for the related quadratic assignment problem. We then define a novel OT discrepancy that can deal with large scale distributions via a slicing approach and we show how it relates to the GW distance while being $O(n\log(n))$ to compute. We illustrate the behavior of this so called Sliced Gromov-Wasserstein (SGW) discrepancy in experiments where we demonstrate its ability to tackle similar problems as GW while being several order of magnitudes faster to compute.

1 Introduction

The introduction frames GW as a way to compare distributions without aligned supports, but its non-convex optimization limits scale. The paper introduces SGW, combining 1D GW with slicing for faster computation.

1 Introduction

Wasserstein distance assumes distributions share a metric space or have a meaningful cross-domain cost, unlike GW's comparison of within-domain relational structure.This makes GW suitable for heterogeneous supports that cannot be directly aligned.Source: §1 · p. 2, §2 · p. 4
Sliced Wasserstein projects high-dimensional data onto one-dimensional distributions and averages their distances, using sorting to compute each 1D distance in O(n log(n)).The paper presents this framework as efficient at million-point scale.Source: §1 · p. 3
SGW applies exact 1D GW to distributions projected onto random directions, with discrete computation costing O(L n log(n)) for L directions.The paper derives a 1D closed form through a new result for the Quadratic Assignment Problem.Source: §1 · p. 3

2 Gromov-Wasserstein distance

With distance-based costs, GW is invariant to translations, permutations, and rotations, and has metric properties up to measure-preserving isometries.The passage also notes equivalence to realignment followed by Wasserstein distance when spaces have the same dimension.Source: §2 · p. 4
GW is a non-convex quadratic program whose conditional-gradient iterations require O(n3) OT solves, while entropic iterations are nearly O(n2) but final cost computation remains O(n3).The paper notes these approaches remain costly for large-scale settings.Source: §2 · p. 4

3 From 1D GW to Sliced Gromov-Wasserstein

The section derives an efficient one-dimensional solution for a quadratic assignment problem and uses it to define Sliced Gromov-Wasserstein (SGW). It also introduces Rotation Invariant SGW (RISGW), which restores rotational invariance when the dimensions match.

Solving a Quadratic Assignement Problem in 1D

For sorted real numbers, the squared-distance quadratic assignment solution is either the identity or anti-identity permutation.The result also provides a closed form for the Gromov-Monge problem on the real line.Source: §3 · p. 5

Gromov-Wasserstein distance on the real line

For equal-size, uniformly weighted distributions on the real line, GW and GM coincide, and the best assignment is identity or anti-identity.The assignment and cost can be computed in O(n log(n)) under these hypotheses.Source: §3 · pp. 5–6

Sliced Gromov-Wasserstein discrepancy

SGW averages one-dimensional GW comparisons of projected distributions, extending the sliced-distance strategy to distributions in possibly different dimensions.The projections can be approximated with a finite sum over randomly drawn directions.Source: §3 · pp. 6–7
Minimizing SGW over the projection map defines RISGW, which is translation invariant and rotation invariant when p = q.The optimization adds a step but recovers a key GW invariance.Source: §3 · p. 6
SGW and RISGW are pseudo-distances; for compact supports, zero SGW implies isomorphism under the distance induced by the ℓ1 norm.The section also notes that SGW and RISGW are translation invariant.Source: §3 · pp. 6–7

Computational aspects

With L projections, discrete SGW costs O(Ln(p + q + log(n))); RISGW adds Stiefel-manifold optimization, with reported complexity niter(Ln(d + log(n)) + d^3).The authors report RISGW converges in about 10 iterations in their experiments.Source: §3 · p. 7

4 Experimental results

Across the experiments, SGW is substantially faster than entropic-GW for GAN training while recovering the galloping horse’s cyclical motion at far lower mesh-distance computation cost. The rotation-invariant variant is invariant to target rotation, unlike SGW with the identity projection.

SGW and RISGW on spiral dataset

RISGW is invariant to target rotation, like GW, whereas SGW with the identity projection is not.The comparison uses 100 spiral samples and 20 sampled lines across different target rotations.Source: §4 · p. 8

Runtimes comparison

The runtime experiment compares SGW, GW, and entropic-GW on two 2D random measures from 100 to 1,000,000 points.SGW uses 50 or 200 projections; timings include pair-to-pair distance calculations.Source: §4 · p. 8, Figure 3 · p. 8

Meshes comparison

25 minutes for the full mesh distance matrix with SGW, versus around 30 minutes for one GW distance; the 2D embedding recovers the horse’s cyclical motion.The 45 meshes each contain approximately 9,000 vertices; SGW averages 1.5 seconds per mesh pair.Source: §4 · p. 9, Figure 4 · p. 9

SGW as a generative adversarial network (GAN) loss

More than one order of magnitude faster per epoch, SGW trains the toy GAN compared with entropic-GW.The generator converges to a visually acceptable solution in a few hundred epochs.Source: §4 · p. 10

5 Discussion and conclusion

The paper derives a closed-form 1D GW result and builds SGW and rotation-invariant SGW from it. The approach is suited to sampled distributions embedded in a Hilbertian space, but not directly to inputs given only as pairwise distances.

5 Discussion and conclusion

A new quadratic-assignment result for squared Euclidean distances on the real line yields a closed form for GW between one-dimensional measures.The paper also introduces SGW and a rotation-invariant variant, which preserve various GW properties while being cheaper to compute; SGW takes 1 second for distributions with 1 million samples each.Source: §5 · p. 10
SGW’s projection approach fits empirical samples embedded in a Hilbertian space, but cannot be applied directly when only pairwise distances are available.The authors identify embedding those distances or reasoning directly on distance matrices as future directions.Source: §5 · p. 10

6 Suplementary materials

The supplementary material states a rearrangement inequality for sorted sequences and specifies which permutations attain its bounds when values differ.

Theorem 6.1 (Rearrangement Inequality)

Theorem 6.1 is labeled the Rearrangement Inequality and assumes x1 ≤ ... ≤ xn and y1 ≤ ... ≤ yn; the cited passage does not specify the resulting bound.Source: §6 · p. 13
When values differ, the lower bound is attained only by reversing the order, and the upper bound only by the identity permutation.Source: §6 · p. 13

7 Proof for the QAP

For sorted real sequences, the QAP optimum is identity or anti-identity, selected by the sign of C. The proof relaxes the assignment problem to doubly stochastic matrices and links its optimum back to a permutation.

The proof handles x,y in D by perturbing x while preserving its ordering, then using continuity of g to transfer the optimal permutation.Source: §7 · pp. 13, 16
Maximizing the convex quadratic relaxation over doubly stochastic matrices yields an optimum at an extreme point supported on a permutation, making QP and QAP equivalent.Source: §7 · pp. 14–15
The sign rule follows because the associated LP uniquely selects the identity for positive C and the anti-identity for negative C, by the rearrangement inequality.Source: §7 · p. 15
If C(x,y,σ*) > 0, the identity is optimal; if C(x,y,σ*) < 0, the anti-identity is optimal.Source: §7 · p. 15
For x,y in D, either the identity or anti-identity permutation is an optimal solution of the QAP.Source: §7 · pp. 13, 15, 16

8 Computing GW in the 1d case

In the one-dimensional case, finding the optimal permutation and computing the resulting cost have separate sorting-based and linear-time steps.

The optimal permutation can be found in O(n log(n)).Source: §8 · p. 17
The final cost can be computed using a binomial expansion in O(n) operations.Source: §8 · p. 17

9 Claims about GW

This section establishes properties of GW and its relation to GM. It gives a zero-distance characterization for squared Euclidean costs and shows GW and GM coincide under specified discrete conditions.

9 Claims about GW

When the costs are distances, GW is a distance on metric-measure spaces modulo measure-preserving isometries, and it is symmetric and satisfies the triangle inequality.Source: §9.1 · p. 17

9.1 GW when squared euclidean distances are used

With squared Euclidean costs, GW is zero exactly when the supports are related by a measure-preserving isometry.Source: §9.1 · p. 17

9.2 Equivalence between GM and GW in the discrete case

For equally weighted discrete measures with m=n, squared-Euclidean GW and GM have equal squared values.Source: §9.2 · p. 18
The doubly stochastic relaxation has the same optimum as the permutation problem under the stated conditional definiteness property, yielding GW–GM coincidence.Source: §9.2 · p. 18
For sorted samples with p=q=1, Theorem 7.1 makes an optimal GM permutation either the identity or anti-identity.Source: §9.2 · p. 18

10 Properties of SGW

SGW and RISGW are pseudo-distances with stated invariances, and compact support gives a zero-distance isomorphism result for SGW. The proof connects projected isomorphisms to a measure-preserving isometry of the full supports.

SGW and RISGW are symmetric pseudo-distances satisfying the triangle inequality; both are translation invariant, and RISGW is rotation invariant when p=q.Source: §10 · pp. 18–19
For compactly supported measures, SGW(µ,ν)=0 implies isomorphism under the distance induced by the ℓ1 norm.Source: §10 · p. 19
If almost all one-dimensional projections are isomorphic and the measures have compact supports, a measure-preserving isometry exists between their supports.Source: §10 · p. 19
The proof builds almost-orthogonal bases and a sequence of maps, then uses a convergent subsequence to obtain a candidate isometry.Source: §10 · pp. 19, 23

11 Algorithm for SGW

The SGW procedure projects samples onto sampled lines, sorts each projected set, and solves a one-dimensional problem. The section also reports a rotation-angle comparison of SW and RISW on spiral distributions.

11 Algorithm for SGW

Equation (23) can make the computation in line 7 linear in n.Source: §11 · p. 23
The procedure sorts projected samples and solves the one-dimensional problem for each sampled line.For each line, it solves for either the identity or anti-identity permutation.Source: §11 · p. 24
Figure 6 plots average SW and RISW values against target rotation angle, with shaded 20% and 80% percentiles.The figure also shows source and target spiral examples at different rotations.Source: Figure 6 · p. 24

12 SW∆and RISW

The section defines SW variants for measures in spaces of different dimensions and reports their computational cost and rotational behavior. RISW is rotationally invariant on average in the spiral experiment, whereas SW is not.

12 SW∆and RISW

SW∆ extends the sliced Wasserstein construction to measures in spaces of different dimensions, with a rotational-invariant counterpart.Source: §12 · p. 24
RISW is rotationally invariant on average in the spiral experiment, whereas SW is not.The authors note that SW’s larger variance may reflect its ability to realign distributions without accounting for rotation.Source: §12 · p. 24
Computing SW∆ has complexity O(Ln(p + q + log(n))), matching SGW∆.Source: §12 · p. 24

13 Supplementary results for the SGW GAN Section

The supplementary GAN experiment considers generators producing samples in two or three dimensions for a two-dimensional target. Figure 7 shows initialization and later training snapshots, with the target in the last column.

13 Supplementary results for the SGW GAN Section

The GAN examples include a 2D generator with a 2D target and a 3D generator with a 2D target.Source: §13 · pp. 24–25, Figure 7 · p. 25
Figure 7 shows generator snapshots at initialization, 100 epochs, and 1000 epochs, followed by the target distribution.Source: Figure 7 · p. 25
The supplementary results are reported for 1000 epochs.Source: §13 · p. 25