Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
This work addresses a computational bottleneck for researchers and practitioners using GW distances in machine learning applications involving point cloud alignment, offering a significant speedup but is incremental as it builds on existing low-rank optimal transport variants.
The paper tackles the high computational complexity of Gromov-Wasserstein (GW) distances, which are NP-hard and typically solved with cubic time approximations, by introducing a low-rank coupling and cost method that reduces the time to linear O(n) for approximations, achieving orders of magnitude faster computation than state-of-the-art entropic GW approaches on simulated and real data.
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.