Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
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 pr...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-02-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/16/3/131 |
| _version_ | 1797613967094317056 |
|---|---|
| author | Patrice Koehl Marc Delarue Henri Orland |
| author_facet | Patrice Koehl Marc Delarue Henri Orland |
| author_sort | Patrice Koehl |
| collection | DOAJ |
| description | 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’s constraints. To account for possible differences of scales between the two metric spaces, we introduce a scaling factor <i>s</i> 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 <i>s</i>. We illustrate our approach on the problem of comparing shapes defined by unstructured triangulations of their surfaces. We use several synthetic and “real life” 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. |
| first_indexed | 2024-03-11T07:02:59Z |
| format | Article |
| id | doaj.art-e56ddd45039b48349f11a06a7d9d1152 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-11T07:02:59Z |
| publishDate | 2023-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-e56ddd45039b48349f11a06a7d9d11522023-11-17T09:08:57ZengMDPI AGAlgorithms1999-48932023-02-0116313110.3390/a16030131Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal TransportPatrice Koehl0Marc Delarue1Henri Orland2Department of Computer Science, University of California, Davis, CA 95616, USAInstitut Pasteur, Université Paris-Cité and CNRS, UMR 3528, Unité Architecture de Dynamique des Macromolécules Biologiques, 75015 Paris, FranceInstitut de Physique Théorique, CEA, CNRS, Université Paris-Saclay, 91191 Gif-sur-Yvette, FranceThe 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’s constraints. To account for possible differences of scales between the two metric spaces, we introduce a scaling factor <i>s</i> 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 <i>s</i>. We illustrate our approach on the problem of comparing shapes defined by unstructured triangulations of their surfaces. We use several synthetic and “real life” 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.https://www.mdpi.com/1999-4893/16/3/131optimal transportGromov-Wassersteinstatistical physics |
| spellingShingle | Patrice Koehl Marc Delarue Henri Orland Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport Algorithms optimal transport Gromov-Wasserstein statistical physics |
| title | Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport |
| title_full | Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport |
| title_fullStr | Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport |
| title_full_unstemmed | Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport |
| title_short | Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport |
| title_sort | computing the gromov wasserstein distance between two surface meshes using optimal transport |
| topic | optimal transport Gromov-Wasserstein statistical physics |
| url | https://www.mdpi.com/1999-4893/16/3/131 |
| work_keys_str_mv | AT patricekoehl computingthegromovwassersteindistancebetweentwosurfacemeshesusingoptimaltransport AT marcdelarue computingthegromovwassersteindistancebetweentwosurfacemeshesusingoptimaltransport AT henriorland computingthegromovwassersteindistancebetweentwosurfacemeshesusingoptimaltransport |