{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T15:36:04Z","timestamp":1774020964201,"version":"3.50.1"},"reference-count":55,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T00:00:00Z","timestamp":1677542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1760485"],"award-info":[{"award-number":["1760485"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Gromov-Wasserstein (GW) formalism can be seen as a generalization of the optimal transport (OT) formalism for comparing two distributions associated with different metric spaces. It is a quadratic optimization problem and solving it usually has computational costs that can rise sharply if the problem size exceeds a few hundred points. Recently fast techniques based on entropy regularization have being developed to solve an approximation of the GW problem quickly. There are issues, however, with the numerical convergence of those regularized approximations to the true GW solution. To circumvent those issues, we introduce a novel strategy to solve the discrete GW problem using methods taken from statistical physics. We build a temperature-dependent free energy function that reflects the GW problem\u2019s constraints. To account for possible differences of scales between the two metric spaces, we introduce a scaling factor s in the definition of the energy. From the extremum of the free energy, we derive a mapping between the two probability measures that are being compared, as well as a distance between those measures. This distance is equal to the GW distance when the temperature goes to zero. The optimal scaling factor itself is obtained by minimizing the free energy with respect to s. We illustrate our approach on the problem of comparing shapes defined by unstructured triangulations of their surfaces. We use several synthetic and \u201creal life\u201d datasets. We demonstrate the accuracy and automaticity of our approach in non-rigid registration of shapes. We provide numerical evidence that there is a strong correlation between the GW distances computed from low-resolution, surface-based representations of proteins and the analogous distances computed from atomistic models of the same proteins.<\/jats:p>","DOI":"10.3390\/a16030131","type":"journal-article","created":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T03:00:38Z","timestamp":1677553238000},"page":"131","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0908-068X","authenticated-orcid":false,"given":"Patrice","family":"Koehl","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Davis, CA 95616, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0723-8102","authenticated-orcid":false,"given":"Marc","family":"Delarue","sequence":"additional","affiliation":[{"name":"Institut Pasteur, Universit\u00e9 Paris-Cit\u00e9 and CNRS, UMR 3528, Unit\u00e9 Architecture de Dynamique des Macromol\u00e9cules Biologiques, 75015 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6983-2951","authenticated-orcid":false,"given":"Henri","family":"Orland","sequence":"additional","affiliation":[{"name":"Institut de Physique Th\u00e9orique, CEA, CNRS, Universit\u00e9 Paris-Saclay, 91191 Gif-sur-Yvette, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,2,28]]},"reference":[{"key":"ref_1","first-page":"666","article-title":"M\u00e9moire sur la theorie des deblais et des remblais","volume":"1784","author":"Monge","year":"1781","journal-title":"Hist. l\u2019Acad. R. Sci. Mem. Math. Phys. Tires Regist. Cette Acad."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1533","DOI":"10.3934\/dcds.2014.34.1533","article-title":"A survey of the Schr\u00f6dinger problem and some of its connections with optimal transport","volume":"34","year":"2014","journal-title":"Discret. Contin. Dyn. Syst. Ser. A"},{"key":"ref_3","first-page":"7","article-title":"On the transfer of masses","volume":"37","author":"Kantorovich","year":"1942","journal-title":"Dokl. Acad. Nauk. USSR"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Villani, C. (2008). Optimal Transport: Old and New, Springer. Grundlehren der Mathematischen Wissenschaften.","DOI":"10.1007\/978-3-540-71050-9"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Peyr\u00e9, G., and Cuturi, M. (2018). Computational Optimal Transport. arXiv.","DOI":"10.1561\/9781680835519"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Villani, C. (2003). Topics in Optimal Transportation, American Mathematical Society. Graduate Studies in Mathematics.","DOI":"10.1090\/gsm\/058"},{"key":"ref_7","unstructured":"M\u00e9moli, F. (2007, January 2\u20133). On the use of Gromov-Hausdorff Distances for Shape Comparison. Proceedings of the Eurographics Symposium on Point-Based Graphics, Prague, Czech Republic."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s10208-011-9093-5","article-title":"Gromov-Wasserstein distances and the metric approach to object matching","volume":"11","year":"2011","journal-title":"Found. Comput. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"18221","DOI":"10.1073\/pnas.1112822108","article-title":"Algorithms to automatically quantify the geometric similarity of anatomical surface","volume":"108","author":"Boyer","year":"2011","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Alvarez-Melis, D., and Jaakkola, T.S. (2018). Gromov-Wasserstein alignment of word embedding spaces. arXiv.","DOI":"10.18653\/v1\/D18-1214"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Yan, Y., Li, W., Wu, H., Min, H., Tan, M., and Wu, Q. (2018, January 13\u201319). Semi-Supervised Optimal Transport for Heterogeneous Domain Adaptation. Proceedings of the IJCAI, Stockholm, Sweden.","DOI":"10.24963\/ijcai.2018\/412"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1111\/cgf.13244","article-title":"GWCNN: A metric alignment layer for deep shape analysis","volume":"Volume 36","author":"Ezuz","year":"2017","journal-title":"Proceedings of the Computer Graphics Forum"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"109351","DOI":"10.1016\/j.patcog.2023.109351","article-title":"On a linear fused Gromov-Wasserstein distance for graph structured data","volume":"138","author":"Nguyen","year":"2023","journal-title":"Pattern Recognit."},{"key":"ref_14","unstructured":"Titouan, V., Courty, N., Tavenard, R., and Flamary, R. (2019, January 9\u201315). Optimal transport for structured data with application on graphs. Proceedings of the International Conference on Machine Learning, Long Beach, CA, USA."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1016\/j.procs.2022.01.086","article-title":"A brief survey on Computational Gromov-Wasserstein distance","volume":"199","author":"Zheng","year":"2022","journal-title":"Procedia Comput. Sci."},{"key":"ref_16","unstructured":"Chowdhury, S., and Needham, T. (2021, January 13\u201315). Generalized spectral clustering via Gromov-Wasserstein learning. Proceedings of the International Conference on Artificial Intelligence and Statistics, Virtual."},{"key":"ref_17","unstructured":"Bunne, C., Alvarez-Melis, D., Krause, A., and Jegelka, S. (2019, January 9\u201315). Learning generative models across incomparable spaces. Proceedings of the International Conference on Machine Learning, Long Beach, CA, USA."},{"key":"ref_18","unstructured":"Burges, C.J.C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K.Q. (2013). Advances in Neural Information Processing Systems 26, Curran Associates, Inc."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1214\/aoms\/1177731829","article-title":"On a least squares adjustment of a sampled frequency table when the expected marginal totals are known","volume":"11","author":"Deming","year":"1940","journal-title":"Ann. Math. Stat."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1214\/aoms\/1177703591","article-title":"A relationship between arbitrary positive matrices and doubly stochastic matrices","volume":"35","author":"Sinkhorn","year":"1964","journal-title":"Ann. Math. Stat."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"343","DOI":"10.2140\/pjm.1967.21.343","article-title":"Concerning nonnegative matrices and doubly stochastic matrices","volume":"21","author":"Sinkhorn","year":"1967","journal-title":"Pacific J. Math."},{"key":"ref_22","unstructured":"Peyr\u00e9, G., Cuturi, M., and Solomon, J. (2016, January 19\u201324). Gromov-Wasserstein Averaging of Kernel and Distance Matrices. Proceedings of the Proceeding ICML\u201916, New York, NY, USA."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"040603","DOI":"10.1103\/PhysRevLett.123.040603","article-title":"A statistical physics formulation of the optimal transport problem","volume":"123","author":"Koehl","year":"2019","journal-title":"Phys. Rev. Lett."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"013310","DOI":"10.1103\/PhysRevE.100.013310","article-title":"Finite temperature optimal transport","volume":"100","author":"Koehl","year":"2019","journal-title":"Phys. Rev. E"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"042101","DOI":"10.1103\/PhysRevE.103.042101","article-title":"Fast computation of exact solutions of generic and degenerate assignment problems","volume":"103","author":"Koehl","year":"2021","journal-title":"Phys. Rev. E"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"012113","DOI":"10.1103\/PhysRevE.103.012113","article-title":"Physics approach to the variable-mass optimal-transport problem","volume":"103","author":"Koehl","year":"2021","journal-title":"Phys. Rev. E"},{"key":"ref_27","first-page":"32","article-title":"A quadratic programming bibliography","volume":"1","author":"Gould","year":"2000","journal-title":"Numer. Anal. Group Intern. Rep."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Higham, N., Dennis, M., Glendinning, P., Martin, P., Sentosa, F., and Tanner, J. (2015). The Princeton Companion to Applied Mathematics, Princeton University Press.","DOI":"10.1515\/9781400874477"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF00120662","article-title":"Quadratic programming with one negative eigenvalue is (strongly) NP-hard","volume":"1","author":"Pardalos","year":"1991","journal-title":"J. Glob. Optim."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Nocedal, J., and Wright, S.J. (2006). Quadratic programming. Numer. Optim., 448\u2013492.","DOI":"10.1007\/978-0-387-40065-5_16"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"A1111","DOI":"10.1137\/141000439","article-title":"Iterative Bregman Projections for Regularized Transportation Problems","volume":"37","author":"Benamou","year":"2015","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_32","unstructured":"Genevay, A., Cuturi, M., Peyr\u00e9, G., and Bach, F. (2016). Advances in Neural Information Processing Systems 29, Curran Associates, Inc."},{"key":"ref_33","unstructured":"Schmitzer, B. (2016). Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems. arXiv."},{"key":"ref_34","unstructured":"Dvurechensky, P., Gasnikov, A., and Kroshnin, A. (2018, January 10\u201315). Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn\u2019s Algorithm. Proceedings of the 35th International Conference on Machine Learning, Stockholm, Sweden."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"2563","DOI":"10.1090\/mcom\/3303","article-title":"Scaling Algorithms for Unbalanced Transport Problems","volume":"87","author":"Chizat","year":"2018","journal-title":"Math. Comp."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1812","DOI":"10.1137\/050639296","article-title":"Efficient computation of isometry-invariant distances between surfaces","volume":"28","author":"Bronstein","year":"2006","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1109\/TVCG.2007.1041","article-title":"Calculus of non-rigid surfaces for geometry and texture manipulation","volume":"13","author":"Bronstein","year":"2007","journal-title":"IEEE Trans. Vis. Comput. Graph"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/0216045","article-title":"The discrete geodesic problem","volume":"16","author":"Mitchell","year":"1987","journal-title":"SIAM J. Comput."},{"key":"ref_39","unstructured":"Biasotti, S., Lavou\u00e9, G., and Veltkamp, R. (2019). Proceedings of the Eurographics Workshop on 3D Object Retrieval, The Eurographics Association."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"2255","DOI":"10.1109\/TVCG.2018.2832136","article-title":"Robust non-rigid registration with reweighted position and transformation sparsity","volume":"25","author":"Li","year":"2018","journal-title":"IEEE Trans. Visual. Comput. Graphics"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/j.cagd.2019.04.014","article-title":"Non-rigid registration under anisotropic deformations","volume":"71","author":"Dyke","year":"2019","journal-title":"Comput. Aided Geom. Des."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Vestner, M., L\u00e4hner, Z., Boyarski, A., Litany, O., Slossberg, R., Remez, T., Rodol\u00e0, E., Bronstein, A., Bronstein, M., and Kimmel, R. (2017, January 10\u201312). Efficient deformable shape correspondence via kernel matching. Proceedings of the 2017 International Conference on 3D Vision (3DV), Qingdao, China.","DOI":"10.1109\/3DV.2017.00065"},{"key":"ref_43","first-page":"1","article-title":"A genetic isometric shape correspondence algorithm with adaptive sampling","volume":"37","year":"2018","journal-title":"ACM Trans. Graph. (ToG)"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"W477","DOI":"10.1093\/nar\/gkm342","article-title":"MinActionPath: Maximum likelihood trajectory for large-scale structural transitions in a coarse-grained locally harmonic energy landscape","volume":"35","author":"Franklin","year":"2007","journal-title":"Nucl. Acids. Res."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"990","DOI":"10.1038\/nsb1101-990","article-title":"Solution structure of Ca(2+)-calmodulin reveals flexible hand-like properties of its domains","volume":"8","author":"Chou","year":"2001","journal-title":"Nat. Struct. Biol."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1093\/nar\/28.1.235","article-title":"The Protein Data Bank","volume":"28","author":"Berman","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1107\/S0567739476001873","article-title":"A solution for the best rotation to relate two sets of vectors","volume":"32","author":"Kabsch","year":"1976","journal-title":"Acta Crystallogr."},{"key":"ref_48","first-page":"1849","article-title":"Using quaternions to calculate RMSD","volume":"25","author":"Coutsias","year":"2004","journal-title":"J. Comput. Sci."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/PL00009412","article-title":"Deformable Smooth Surface Design","volume":"21","author":"Edelsbrunner","year":"1999","journal-title":"Discret. Comput. Geom."},{"key":"ref_50","unstructured":"Cheng, H., and Shi, X. (2004, January 10\u201315). Guaranteed Quality Triangulation of Molecular Skin Surfaces. Proceedings of the IEEE Visualization, Austin, TX, USA."},{"key":"ref_51","unstructured":"Cheng, H., and Shi, X. (2005, January 23\u201328). Quality Mesh Generation for Molecular Skin Surfaces Using Restricted Union of Balls. Proceedings of the IEEE Visualization, Minneapolis, MN, USA."},{"key":"ref_52","unstructured":"Semeshko, A. (2023, January 02). Suite of Functions to Perform Uniform Sampling of a Sphere. GitHub. Available online: https:\/\/github.com\/AntonSemechko\/S2-Sampling-Toolbox."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/235815.235821","article-title":"The Quickhull Algorithm for Convex Hulls","volume":"22","author":"Barber","year":"1996","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_54","first-page":"2877","article-title":"A new fifth-order iterative method free from second derivative for solving nonlinear equations","volume":"68","author":"Ali","year":"2021","journal-title":"J. Appl. Math. Comput."},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"S\u00e9journ\u00e9, T., Peyr\u00e9, G., and Vialard, F.X. (2022). Unbalanced Optimal Transport, from theory to numerics. arXiv.","DOI":"10.1016\/bs.hna.2022.11.003"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/3\/131\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:43:50Z","timestamp":1760121830000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/3\/131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,28]]},"references-count":55,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["a16030131"],"URL":"https:\/\/doi.org\/10.3390\/a16030131","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,28]]}}}