# Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport  
[PERSON]  
1 Department of Computer Science, University of California, Davis, CA 95616, USA 1  
[PERSON]  
2 Institut Pasteur, Universite Paris-Cite and CNRS, UMR 3528, U  
of ressources\" problem became well known, however, reappearing in many disciplines and consequently has been the object of many studies. [PERSON], for example, expressed it as the problem of finding how to evolve a probability distribution into another (see [2] for a review), the Schrodinger bridge problem. [PERSON] relaxed the Monge problem by allowing masses to split [3]. He also formulated a method, linear programming, for solving his relaxed version. All these problems are now referred to as the optimal transport problems, or OT. The OT problem is particularly intriguing since its solutions involve two crucial elements. It first specifies a distance between the measured spaces taken into account. This distance is known as the Monge-Kantorovich distance, the Wasserstein distance, or the earth mover's distance, according to the field of applications. It also derives the optimal transport plan between the measured spaces, thereby defining a registration between the spaces. Consequently, applications of OT have exploded in the recent years (for in-depth reviews of OT and its uses, see [4; 5]). The Monge-Kantorovich OT problem can be formulated as follows. Let \(A\) and \(B\) be two subsets of a space \(M\) with a metric \(d\), and let \(\alpha\) and \(\beta\) be probability measures on \(A\) and \(B\), respectively. Let \(C\) be a cost function \(C:A\times B\rightarrow\mathbb{R}^{+}\). The objective is to find a coupling \(G\) on \(A\times B\) that minimizes a transportation cost \(U\) defined as  
\[U(G)=\int_{A}\int_{B}C(a,b)G(a,b)d(a,b). \tag{2}\]  
The minimum of \(U(G)\) is to be identified over the couplings \(G\) that satisfy the following constraints on their restrictions to the subsets \(A\) and \(B\):  
\[\forall a,\ \ \int_{B}G(a,b)db =\alpha(a) \tag{3a}\] \[\forall b,\ \ \int_{A}G(a,b)da =\beta(b). \tag{3b}\]  
It was shown that this minimum exists and that it defines a distance between the two probability measures \(\alpha\) and \(\beta\) that satisfies all metric properties [6]. One key condition for solving the optimal transport problem between two sets \(A\) and \(B\) is that those sets belong to the same metric space. This allows for the definition of a distance between any point of \(A\) and any point of \(B\), and therefore of a cost function between the two sets. In practice, however, the two sets may not be in the same metric space, or, even if they do, the corresponding metric may not be practical. Consider for example two sets of points in \(\mathbb{R}^{3}\); while it is possible to compute the euclidean distance between any pairs of points belonging to the two sets, inter distances between the two sets depend on the relative position of the two sets, namely a rigid body transformation involving six real-valued parameters (three that define a rotation, three that define a translation). Distances within each set are independent of such transformation; such distances, however, define a different metric space, one for each set of points. Several methods have been developed to use this information within the framework of optimal transport [7; 8; 9]. Here we are concerned with the Gromov-Wasserstein formalism [8], which has become popular for shape matching [8], for word embedding [10], as well as in the machine learning community, solving learning tasks such as heterogenous domain adaptation [11], deep metric alignment [12], computing distances between graphs [13] and graph classification [14; 15], clustering [16] or generative modeling [17], among others. The GW problem can be stated as follows. Let \((A,d_{A})\) and \((B,d_{B})\) be two metric spaces, and let \(\alpha\) and \(\beta\) be probability measures on \(A\) and \(B\), respectively.