Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs

Abstract

The ability to align points across two related yet incomparable point clouds (e.g. living in different spaces) plays an important role in machine learning. The Gromov-Wasserstein (GW) framework provides an increasingly popular answer to such problems, by seeking a low-distortion, geometry-preserving assignment between these points. As a non-convex, quadratic generalization of optimal transport (OT), GW is NP-hard. While practitioners often resort to solving GW approximately as a nested sequence of entropy-regularized OT problems, the cubic complexity (in the number $n$ of samples) of that approach is a roadblock. We show in this work how a recent variant of the OT problem that restricts the set of admissible couplings to those having a low-rank factorization is remarkably well suited to the resolution of GW: when applied to GW, we show that this approach is not only able to compute a stationary point of the GW problem in time $O(n^2)$, but also uniquely positioned to benefit from the knowledge that the initial cost matrices are low-rank, to yield a linear time $O(n)$ GW approximation. Our approach yields similar results, yet orders of magnitude faster computation than the SoTA entropic GW approaches, on both simulated and real data.

References in corpus (7)

• Word Translation Without Parallel Data
• Gromov-Wasserstein Learning for Graph Matching and Node Embedding
• Learning Generative Models across Incomparable Spaces
• Linear Time Sinkhorn Divergences using Positive Features
• Partial Optimal Transport with Applications on Positive-Unlabeled Learning
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces
• MREC: a fast and versatile framework for aligning and matching point clouds with applications to single cell molecular data

Cited by in corpus (1)

• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey