{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:41:14Z","timestamp":1787341274308,"version":"build-2736575974"},"reference-count":48,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>The Gromov\u2013Wasserstein (GW) problem is a variant of the classical optimal transport problem that allows one to compute meaningful transportation plans between incomparable spaces. At an intuitive level, it seeks plans that minimize the discrepancy between metric evaluations of pairs of points. The GW problem is typically cast as an instance of a nonconvex quadratic program that is, unfortunately, intractable to solve. In this paper, we describe tractable semidefinite relaxations of the GW problem based on the sum-of-squares (SOS) hierarchy. We describe how the Putinar-type and the Schm\u00fcdgen-type moment hierarchies can be simplified using marginal constraints, and we prove convergence rates for these hierarchies towards computing global optimal solutions to the GW problem. The proposed SOS hierarchies naturally induce a distance measure analogous to the distortion metrics, and we show that these are genuine distances in that they satisfy the triangle inequality. In particular, the proposed SOS hierarchies provide computationally tractable proxies of the GW distance and the associated distortion distances (over metric measure spaces) that are otherwise intractable to compute.<\/jats:p>","DOI":"10.1137\/25m1736876","type":"journal-article","created":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T07:36:36Z","timestamp":1777275396000},"page":"729-759","source":"Crossref","is-referenced-by-count":0,"title":["Sum-of-Squares Hierarchy for the Gromov\u2013Wasserstein Problem"],"prefix":"10.1137","volume":"36","author":[{"given":"Hoang Anh","family":"Tran","sequence":"first","affiliation":[{"name":"Department of Mathematics, National University of Singapore, Singapore, 119076."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Binh Tuan","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Department of Mathematics, National University of Singapore, Singapore, 119076."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3367-1401","authenticated-orcid":true,"given":"Yong Sheng","family":"Soh","sequence":"additional","affiliation":[{"name":"Department of Mathematics, National University of Singapore, Singapore, 119076."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,4,27]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1401651112"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"D. Alvarez-Melis and T. Jaakkola, Gromov-Wasserstein alignment of word embedding spaces, in Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics, 2018, pp. 1881\u20131890.","DOI":"10.18653\/v1\/D18-1214"},{"key":"ref3","unstructured":"C. Bunne, D. Alvarez-Melis, A. Krause, and S. Jegelka, Learning generative models across incomparable spaces, in Proceedings of the International Conference on Machine Learning, 2019, pp. 851\u2013861."},{"key":"ref4","volume-title":"Numerical Geometry of Non-rigid Shapes","author":"Bronstein A. M.","year":"2008"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972290"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(92)90174-9"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-024-02076-1"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/21M144548X"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.52202\/079017-2231"},{"key":"ref11","unstructured":"J. Chen and Y. S. Soh, Exactness Conditions for Semidefinite Relaxations of the Quadratic Assignment Problem, preprint, arXiv:2409.08802, 2024."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2021.0446"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01737-9"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01537-7"},{"key":"ref15","series-title":"Progr. Math. 152","volume-title":"Metric Structures for Riemannian and Non-Riemannian Spaces","author":"Gromov M.","year":"1999"},{"key":"ref16","series-title":"Oper. Res.","volume-title":"A Low-Rank augmented Lagrangian method for doubly nonnegative relaxations of mixed-binary quadratic programs","author":"Di H.","year":"2025"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-015-0868-5"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-022-01851-3"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12701"},{"key":"ref20","unstructured":"N. Kravtsova, The NP-hardness of the Gromov-Wasserstein Distance, preprint, arXiv:2408.06525, 2024."},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"D. Klein, T. Uscidda, F. J. Fabian, et\u00a0al., GENOT: Entropic (Gromov) Wasserstein flow matching with applications to single-cell genomics, in Proceedings of the Thirty-Eighth Annual Conference on Neural Information Processing Systems, 2024.","DOI":"10.52202\/079017-3301"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1142\/p665"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/100806990"},{"key":"ref25","unstructured":"S. Ling, On the Exactness of SDP Relaxation for Quadratic Assignment Problem, preprint, arXiv:2408.05942, 2024."},{"key":"ref26","unstructured":"F. M\u00e9moli, On the use of Gromov-Hausdorff distances for shape comparison, in Symposium on Point Based Graphics 07, 2007."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9093-5"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-024-01422-x"},{"key":"ref29","unstructured":"P. A. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, Ph.D. thesis, California Institute of Technology, 2000."},{"key":"ref30","unstructured":"G. Peyr\u00e9, M. Cuturi, and J. Solomon, Gromov-Wasserstein averaging of kernel and distance matrices, in Proceedings of the International Conference on Machine Learning, 2016, pp. 2664\u20132672."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2009.01.002"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1993.42.42045"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718812"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-64546-9_12"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1137\/21M1458338"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925903"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s11511-006-0002-8"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"K.T. Sturm, The space of spaces: Curvature bounds and gradient flows on the space of metric measure spaces, Mem. Amer. Math. Soc.\u00a0290 (2023) no. 1443.","DOI":"10.1090\/memo\/1443"},{"key":"ref39","volume-title":"SIAM J. Optim.","author":"Tran H. A."},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"H. A. Tran and K.C. Toh, On the Convergence Rates of Moment-SOS Hierarchies Approximation of Truncated Moment Sequences, preprint, arXiv:2507.00572, 2025.","DOI":"10.1007\/s10107-026-02394-6"},{"key":"ref41","doi-asserted-by":"crossref","first-page":"21792","DOI":"10.52202\/068431-1584","volume":"35","author":"Thual A.","year":"2022","journal-title":"Adv. Neural Inform. Process. Syst."},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"key":"ref43","unstructured":"S. Villar, A. S. Bandeira, A. J. Blumberg, and R. Ward, A Polynomial-Time Relaxation of the Gromov-Hausdorff Distance, preprint, arXiv:1610.05214, 2016."},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.3390\/a13090212"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/058"},{"key":"ref46","unstructured":"H. Xu, D. Luo, H. Zha, and L. C. Duke, Gromov-Wasserstein learning for graph matching and node embedding, in Proceedings of the International Conference on Machine Learning, PMLR, 2019, pp. 6932\u20136941."},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1214\/24-AOS2406"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009795911987"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/25M1736876","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:12:12Z","timestamp":1787339532000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1736876"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,27]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/25M1736876"],"URL":"https:\/\/doi.org\/10.1137\/25m1736876","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,27]]}}}