Martin Ryner: Global solution to the Gromov Wasserstein discrepancy problem between point clouds in Euclidean spaces and low rank QAPs

The Gromov-Wasserstein problem is a generalization of the optimal transport problem and is to find the assignment between two sets that preserve pairwise distances to as large degree as possible. This can be used, for example, to quantify how similar two formations or shapes are. Gromov-Wasserstein distances and discrepancies can be formulated as quadratic assignment problems which are in general NP-hard. In this presentation we will discuss recent work on global optimality for a certain class of such problems. In particular, we show that a certain class of Gromov-Wasserstein problems can be formulated as quadratic assignment problems for which the global solution can be found efficiently. The approach is based on reformulating the problem as a low dimensional quadratic problem with convex feasible set. We take a starting point in shrinking approximate covers, linear relaxations and mixed integer strategies which are suitable for this certain problem class. We discuss problem areas where popular methods fail to find near global optima, and where our proposed method can reduce stability issues and provide good bases for decisions when the distance is used for comparative analysis. Finally, we apply the approach on symmetrical and near symmetrical problems which are of special interest in biology.