Timezone: »

 
Poster
Sliced Gromov-Wasserstein
Titouan Vayer · Rémi Flamary · Nicolas Courty · Romain Tavenard · Laetitia Chapel

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #38
in Algorithms -- Large Scale Learning »
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 ({\em 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.
Keywords: Combinatorial Optimization · Algorithms · Optimization
[ Paper]  [ Slides] 

Author Information

Titouan Vayer (IRISA)
Rémi Flamary (Université Côte d'Azur)
Nicolas Courty (IRISA, Universite Bretagne-Sud)
Romain Tavenard (LETG-Rennes / IRISA-Obelix)
Laetitia Chapel (IRISA)

More from the Same Authors