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

Meyer Scetbon, Gabriel Peyré, Marco Cuturi
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:19347-19365, 2022.

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(n2), 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-scetbon22b, title = {Linear-Time Gromov {W}asserstein Distances using Low Rank Couplings and Costs}, author = {Scetbon, Meyer and Peyr{\'e}, Gabriel and Cuturi, Marco}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {19347--19365}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/scetbon22b/scetbon22b.pdf}, url = {https://proceedings.mlr.press/v162/scetbon22b.html}, 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.} }
Endnote
%0 Conference Paper %T Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs %A Meyer Scetbon %A Gabriel Peyré %A Marco Cuturi %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-scetbon22b %I PMLR %P 19347--19365 %U https://proceedings.mlr.press/v162/scetbon22b.html %V 162 %X 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.
APA
Scetbon, M., Peyré, G. & Cuturi, M.. (2022). Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:19347-19365 Available from https://proceedings.mlr.press/v162/scetbon22b.html.

Related Material