This paper presents a framework for computing the Gromov-Wasserstein problem between two sets of points in low dimensional spaces, where the discrepancy is the squared Euclidean norm. The Gromov-Wasserstein problem is a generalization of the optimal transport problem that finds the assignment between two sets preserving pairwise distances as much as possible. This can be used to quantify the similarity between two formations or shapes, a common problem in AI and machine learning. The problem can be formulated as a Quadratic Assignment Problem (QAP), which is in general computationally intractable even for small problems. Our framework addresses this challenge by reformulating the QAP as an optimization problem with a low-dimensional domain, leveraging the fact that the problem can be expressed as a concave quadratic optimization problem with low rank. The method scales well with the number of points, and it can be used to find the global solution for large-scale problems with thousands of points. We compare the computational complexity of our approach with state-of-the-art methods on synthetic problems and apply it to a near-symmetrical problem which is of particular interest in computational biology.

提出了一种计算低维空间中两组点之间Gromov-Wasserstein问题的框架，通过将Quadratic Assignment Problem (QAP)重新表述为低维域的优化问题来解决计算复杂度的挑战。该方法适用于具有成千上万个点的大规模问题，可用于找到全局解，并在合成问题和计算生物学中的一个感兴趣的问题上与最先进的方法进行比较。

在低维欧几里得空间全局解决点云的Gromov-Wasserstein问题