Sliced Gromov-Wasserstein

Abstract

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.

References in corpus (12)

• Stochastic Optimization for Large-scale Optimal Transport
• Optimal Transport for structured data with application on graphs
• Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation
• Kernel Operations on the GPU, with Autodiff, without Memory Overflows
• Subspace Robust Wasserstein Distances
• Towards Optimal Transport with Global Invariances
• Learning Generative Models across Incomparable Spaces
• McTorch, a manifold optimization library for deep learning
• The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces
• (Probably) Concave Graph Matching
• Sliced Wasserstein Generative Models
• On the existence of Monge maps for the Gromov-Wasserstein problem

Cited by in corpus (8)

• Learning to Simulate High Energy Particle Collisions from Unlabeled Data
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Lidar Upsampling with Sliced Wasserstein Distance
• Partial Optimal Transport with Applications on Positive-Unlabeled Learning
• Sliced Optimal Transport on the Sphere
• Sliced Mutual Information: A Scalable Measure of Statistical Dependence
• Flow-based Alignment Approaches for Probability Measures in Different Spaces
• Sliced Multi-Marginal Optimal Transport