Globally solving the Gromov-Wasserstein problem for point clouds in low
  dimensional Euclidean spaces
Martin Ryner Jan Kronqvist Johan Karlsson
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.