  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.
