The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation
arXiv:2009.04266
Abstract
Comparing metric measure spaces (i.e. a metric space endowed with aprobability distribution) is at the heart of many machine learning problems. The most popular distance between such metric measure spaces is theGromov-Wasserstein (GW) distance, which is the solution of a quadratic assignment problem. The GW distance is however limited to the comparison of metric measure spaces endowed with a probability distribution. To alleviate this issue, we introduce two Unbalanced Gromov-Wasserstein formulations: a distance and a more tractable upper-bounding relaxation.They both allow the comparison of metric spaces equipped with arbitrary positive measures up to isometries. The first formulation is a positive and definite divergence based on a relaxation of the mass conservation constraint using a novel type of quadratically-homogeneous divergence. This divergence works hand in hand with the entropic regularization approach which is popular to solve large scale optimal transport problems. We show that the underlying non-convex optimization problem can be efficiently tackled using a highly parallelizable and GPU-friendly iterative scheme. The second formulation is a distance between mm-spaces up to isometries based on a conic lifting. Lastly, we provide numerical experiments onsynthetic examples and domain adaptation data with a Positive-Unlabeled learning task to highlight the salient features of the unbalanced divergence and its potential applications in ML.
References in corpus (14)
- Neural Message Passing for Quantum Chemistry
- DeCAF: A Deep Convolutional Activation Feature for Generic Visual Recognition
- Learning with a Wasserstein Loss
- Interpolating between Optimal Transport and MMD using Sinkhorn Divergences
- Towards Optimal Transport with Global Invariances
- Sinkhorn Divergences for Unbalanced Optimal Transport
- Learning Generative Models across Incomparable Spaces
- On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
- Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties
- Learning Autoencoders with Relational Regularization
- Massively scalable Sinkhorn distances via the Nyström method
- Global convergence of neuron birth-death dynamics
- Partial Optimal Transport with Applications on Positive-Unlabeled Learning
- Parallel Unbalanced Optimal Transport Regularization for Large Scale Imaging Problems
Cited by in corpus (7)
- Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
- Generalized Spectral Clustering via Gromov-Wasserstein Learning
- Entropy-Transport distances between unbalanced metric measure spaces
- On Robust Optimal Transport: Computational Complexity and Barycenter Computation
- Cycle Consistent Probability Divergences Across Different Spaces
- Entropic Gromov-Wasserstein between Gaussian Distributions
- A Quotient Space Formulation for Generative Statistical Analysis of Graphical Data