Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
复制标题
DOI：
10.3390/a16030131
复制
发表时间：
2023-02
期刊：
影响因子：
2.3
通讯作者：
P. Koehl;M. Delarue;H. Orland
中科院分区：
文献类型：
--
作者：
P. Koehl;M. Delarue;H. Orland
Gromov-Wasserstein(GW)形式可以看作是最优传输(OT)形式的推广，用于比较与不同度量空间相关联的两个分布。这是一个二次优化问题，如果问题的大小超过几百个点，求解它的计算成本通常会急剧上升。最近，基于熵正则化的快速技术被开发出来，以快速解决GW问题的近似。然而，这些正则化近似的数值收敛到真正的GW解是有问题的。为了绕过这些问题，我们引入了一种新的策略，使用统计物理中的方法来解决离散GW问题。我们建立了一个与温度相关的自由能函数来反映GW问题的约束。为了考虑两种度规空间之间可能存在的标度差异，我们在能量的定义中引入了标度因子S。从自由能的极值，我们推导出两个被比较的概率度量之间的映射，以及这两个度量之间的距离。当温度降至零时，该距离等于GW距离。最优标度因子本身是通过最小化关于S的自由能来获得的。我们举例说明了我们在比较由其表面的非结构三角剖分定义的形状问题上的方法。我们使用了几个人工合成的和“真实生活”的数据集。我们展示了我们的方法在非刚性形状配准中的准确性和自动化程度。我们提供的数值证据表明，从低分辨率、基于表面的蛋白质表示计算的GW距离与从相同蛋白质的原子模型计算的类似距离之间存在很强的相关性。
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 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 “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.