{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:37:44Z","timestamp":1760236664378,"version":"build-2065373602"},"reference-count":45,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2021,12,17]],"date-time":"2021-12-17T00:00:00Z","timestamp":1639699200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In the context of optimal transport (OT) methods, the subspace detour approach was recently proposed by Muzellec and Cuturi. It consists of first finding an optimal plan between the measures projected on a wisely chosen subspace and then completing it in a nearly optimal transport plan on the whole space. The contribution of this paper is to extend this category of methods to the Gromov\u2013Wasserstein problem, which is a particular type of OT distance involving the specific geometry of each distribution. After deriving the associated formalism and properties, we give an experimental illustration on a shape matching problem. We also discuss a specific cost for which we can show connections with the Knothe\u2013Rosenblatt rearrangement.<\/jats:p>","DOI":"10.3390\/a14120366","type":"journal-article","created":{"date-parts":[[2021,12,19]],"date-time":"2021-12-19T20:41:55Z","timestamp":1639946515000},"page":"366","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Subspace Detours Meet Gromov\u2013Wasserstein"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3390-1169","authenticated-orcid":false,"given":"Cl\u00e9ment","family":"Bonet","sequence":"first","affiliation":[{"name":"Laboratoire de Math\u00e9matiques de Bretagne Atlantique, Universit\u00e9 Bretagne Sud, CNRS UMR 6205, 56000 Vannes, France"}]},{"given":"Titouan","family":"Vayer","sequence":"additional","affiliation":[{"name":"ENS Lyon, CNRS UMR 5668, LIP, 69342 Lyon, France"}]},{"given":"Nicolas","family":"Courty","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Universit\u00e9 Bretagne Sud, CNRS UMR 6074, IRISA, 56000 Vannes, France"}]},{"given":"Fran\u00e7ois","family":"Septier","sequence":"additional","affiliation":[{"name":"Laboratoire de Math\u00e9matiques de Bretagne Atlantique, Universit\u00e9 Bretagne Sud, CNRS UMR 6205, 56000 Vannes, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3362-703X","authenticated-orcid":false,"given":"Lucas","family":"Drumetz","sequence":"additional","affiliation":[{"name":"IMT Atlantique, CNRS UMR 6285, Lab-STICC, 29238 Brest, France"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,17]]},"reference":[{"key":"ref_1","unstructured":"Arjovsky, M., Chintala, S., and Bottou, L. (2017, January 6\u201311). Wasserstein generative adversarial networks. Proceedings of the International Conference on Machine Learning, PMLR, Sydney, Australia."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1853","DOI":"10.1109\/TPAMI.2016.2615921","article-title":"Optimal transport for domain adaptation","volume":"39","author":"Courty","year":"2016","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s10208-011-9093-5","article-title":"Gromov\u2013Wasserstein distances and the metric approach to object matching","volume":"11","year":"2011","journal-title":"Found. Comput. Math."},{"key":"ref_4","first-page":"811","article-title":"Quantized Gromov\u2013Wasserstein","volume":"Volume 12977","author":"Oliver","year":"2021","journal-title":"Proceedings of the Machine Learning and Knowledge Discovery in Databases, Research Track\u2014European Conference, ECML PKDD 2021"},{"key":"ref_5","unstructured":"Alvarez-Melis, D., Jegelka, S., and Jaakkola, T.S. (2019, January 16\u201318). Towards optimal transport with global invariances. Proceedings of the The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, Naha, Japan."},{"key":"ref_6","unstructured":"Cai, Y., and Lim, L.H. (2020). Distances between probability distributions of different dimensions. arXiv."},{"key":"ref_7","unstructured":"Botsch, M., Pajarola, R., Chen, B., and Zwicker, M. (2007, January 2\u20133). On the use of Gromov-Hausdorff Distances for Shape Comparison. Proceedings of the 4th Symposium on Point Based Graphics, PBG@Eurographics 2007, Prague, Czech Republic."},{"key":"ref_8","unstructured":"Sturm, K.T. (2012). The space of spaces: Curvature bounds and gradient flows on the space of metric measure spaces. arXiv."},{"key":"ref_9","unstructured":"Peyr\u00e9, G., Cuturi, M., and Solomon, J. (2016, January 19\u201324). Gromov\u2013Wasserstein averaging of kernel and distance matrices. Proceedings of the International Conference on Machine Learning, PMLR, New York, NY, USA."},{"key":"ref_10","first-page":"2292","article-title":"Sinkhorn distances: Lightspeed computation of optimal transport","volume":"26","author":"Cuturi","year":"2013","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_11","unstructured":"Scetbon, M., Peyr\u00e9, G., and Cuturi, M. (2021). Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs. arXiv."},{"key":"ref_12","first-page":"14753","article-title":"Sliced Gromov\u2013Wasserstein","volume":"32","author":"Vayer","year":"2019","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_13","unstructured":"Fatras, K., Zine, Y., Majewski, S., Flamary, R., Gribonval, R., and Courty, N. (2021). Minibatch optimal transport distances; analysis and applications. arXiv."},{"key":"ref_14","unstructured":"Wallach, H.M., Larochelle, H., Beygelzimer, A., d\u2019Alch\u00e9-Buc, F., Fox, E.B., and Garnett, R. (2019, January 8\u201314). Subspace Detours: Building Transport Plans that are Optimal on Subspace Projections. Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, Vancouver, BC, Canada."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1070\/SM2005v196n03ABEH000882","article-title":"Triangular transformations of measures","volume":"196","author":"Bogachev","year":"2005","journal-title":"Sb. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1307\/mmj\/1028990175","article-title":"Contributions to the theory of convex bodies","volume":"4","author":"Knothe","year":"1957","journal-title":"Mich. Math. J."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1214\/aoms\/1177729394","article-title":"Remarks on a multivariate transformation","volume":"23","author":"Rosenblatt","year":"1952","journal-title":"Ann. Math. Stat."},{"key":"ref_18","unstructured":"Villani, C. (2008). Optimal Transport: Old and New, Springer Science & Business Media."},{"key":"ref_19","first-page":"94","article-title":"Optimal transport for applied mathematicians","volume":"55","author":"Santambrogio","year":"2015","journal-title":"Birk\u00e4user NY"},{"key":"ref_20","unstructured":"Jaini, P., Selby, K.A., and Yu, Y. (2019, January 9\u201315). Sum-of-Squares Polynomial Flow. Proceedings of the 36th International Conference on Machine Learning, PMLR, Long Beach, CA, USA."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1137\/080740647","article-title":"From Knothe\u2019s transport to Brenier\u2019s map and a continuation method for optimal transport","volume":"41","author":"Carlier","year":"2010","journal-title":"SIAM J. Math. Anal."},{"key":"ref_22","unstructured":"Bonnotte, N. (2013). Unidimensional and Evolution Methods for Optimal Transportation. [Ph.D. Thesis, Universit\u00e9 Paris-Sud]."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Ambrosio, L., Gigli, N., and Savar\u00e9, G. (2008). Gradient Flows: In Metric Spaces and in the Space of Probability Measures, Springer Science & Business Media.","DOI":"10.1016\/S1874-5717(07)80004-1"},{"key":"ref_24","unstructured":"Niles-Weed, J., and Rigollet, P. (2019). Estimation of wasserstein distances in the spiked transport model. arXiv."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1093\/imaiai\/iaz026","article-title":"The gromov\u2013wasserstein distance between networks and stable network invariants","volume":"8","author":"Chowdhury","year":"2019","journal-title":"Inf. Inference A J. IMA"},{"key":"ref_26","unstructured":"Vayer, T. (2020). A Contribution to Optimal Transport on Incomparable Spaces. [Ph.D. Thesis, Universit\u00e9 de Bretagne Sud]."},{"key":"ref_27","unstructured":"Paty, F.P., and Cuturi, M. (2019, January 9\u201315). Subspace robust wasserstein distances. Proceedings of the 36th International Conference on Machine Learning, PMLR, Long Beach, CA, USA."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Rasmussen, C.E. (2003). Gaussian processes in machine learning. Summer School on Machine Learning, Springer.","DOI":"10.1007\/978-3-540-28650-9_4"},{"key":"ref_29","unstructured":"Von Mises, R. (1964). Mathematical Theory of Probability and Statistics, Academic Press."},{"key":"ref_30","unstructured":"Salmona, A., Delon, J., and Desolneux, A. (2021). Gromov\u2013Wasserstein Distances between Gaussian Distributions. arXiv."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"2620","DOI":"10.3150\/18-BEJ1065","article-title":"Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance","volume":"25","author":"Weed","year":"2019","journal-title":"Bernoulli"},{"key":"ref_32","unstructured":"Lin, T., Zheng, Z., Chen, E., Cuturi, M., and Jordan, M. (2021, January 13\u201315). On projection robust optimal transport: Sample complexity and model misspecification. Proceedings of the International Conference on Artificial Intelligence and Statistics, PMLR, Virtual."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","article-title":"Perspectives of Monge Properties in Optimization","volume":"70","author":"Burkard","year":"1996","journal-title":"Discret. Appl. Math."},{"key":"ref_34","first-page":"1","article-title":"POT: Python Optimal Transport","volume":"22","author":"Flamary","year":"2021","journal-title":"J. Mach. Learn. Res."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Bogo, F., Romero, J., Loper, M., and Black, M.J. (2014, January 23\u201328). FAUST: Dataset and evaluation for 3D mesh registration. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Columbus, OH, USA.","DOI":"10.1109\/CVPR.2014.491"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","article-title":"Algebraic connectivity of graphs","volume":"23","author":"Fiedler","year":"1973","journal-title":"Czechoslov. Math. J."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Hagberg, A., Swart, P., and Chult, D.S. (2008). Exploring Network Structure, Dynamics, and Function Using NetworkX, Technical Report.","DOI":"10.25080\/TCWV9851"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/j.cam.2014.03.018","article-title":"An efficient and accurate method to compute the Fiedler vector based on Householder deflation and inverse power iteration","volume":"269","author":"Wu","year":"2014","journal-title":"J. Comput. Appl. Math."},{"key":"ref_39","first-page":"3052","article-title":"Scalable Gromov\u2013Wasserstein learning for graph partitioning and matching","volume":"32","author":"Xu","year":"2019","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_40","unstructured":"Chowdhury, S., and Needham, T. (2021, January 13\u201315). Generalized spectral clustering via Gromov\u2013Wasserstein learning. Proceedings of the International Conference on Artificial Intelligence and Statistics, PMLR, Virtual."},{"key":"ref_41","unstructured":"Vayer, T., Courty, N., Tavenard, R., and Flamary, R. (2019, January 9\u201315). Optimal transport for structured data with application on graphs. Proceedings of the 36th International Conference on Machine Learning, PMLR, Long Beach, CA, USA."},{"key":"ref_42","unstructured":"Lacoste-Julien, S. (2016). Convergence rate of frank-wolfe for non-convex objectives. arXiv."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1561\/2200000073","article-title":"Computational optimal transport: With applications to data science","volume":"11","author":"Cuturi","year":"2019","journal-title":"Found. Trends\u00ae Mach. Learn."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1582","DOI":"10.1109\/TSP.2019.2893835","article-title":"Detecting approximate reflection symmetry in a point set using optimization on manifold","volume":"67","author":"Nagar","year":"2019","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_45","unstructured":"Billingsley, P. (2013). Convergence of Probability Measures, John Wiley & Sons."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/366\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:50:38Z","timestamp":1760169038000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/366"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,17]]},"references-count":45,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["a14120366"],"URL":"https:\/\/doi.org\/10.3390\/a14120366","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,12,17]]}}}