# Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
## 2 The Discrete Gromov-Wasserstein Problem  
This section briefly describes the discrete Gromov Wasserstein transport problem and its regularized version. More thorough descriptions can be found in Refs. [7; 8; 22]. The discrete version of the GW problem is an optimal transport problem between two discrete probability measures whose supports are metric spaces \((M_{1},d_{1})\) and \((M_{2},d_{2})\) with possibly different metrics. Let \(S_{1}\) and \(S_{2}\) be subsets of \(M_{1}\) and \(M_{2}\) with cardinality \(N_{1}\) and \(N_{2}\), respectively. Each point \(k\) in \(S_{1}\) (resp \(S_{2}\)) is characterized by a \"mass\" \(m_{1}(k)\) (resp \(m_{2}(k)\)). We assume balance, namely that \(\sum\limits_{k}m_{1}(k)=\sum\limits_{l}m_{2}(l)\). In the following, these sums are set to \(1\), but the formalism could easily be adapted to handle a different values. The discrete GW problem is defined as finding a coupling or transport plan \(G\) that minimizes the total transport cost \(U\) defined as  
\[U_{p}(G)=\sum\limits_{k,l}\sum\limits_{k^{\prime},l^{\prime}}G(k,l)\big{|}d_{1 }(k,k^{\prime})-d_{2}(l,l^{\prime})\big{|}^{p}G(k^{\prime},l^{\prime}), \tag{7}\]  
where \(p\) is a fixed integer greater or equal to \(1\), and the summations extend over all \((k,k^{\prime})\in S_{1}^{2}\) and \((l,l^{\prime})\in S_{2}^{2}\). Note that \(G\) is a matrix of correspondence between points \(k\) in \(S_{1}\) and points \(l\) in \(S_{2}\). The minimization is to be performed over those matrices \(G\) that satisfy the following constraints  
\[\forall(k,l),\quad G(k,l) \geq 0, \tag{8a}\] \[\forall k,\quad\sum\limits_{l}G(k,l) =m_{1}(k),\] (8b) \[\forall l,\quad\sum\limits_{k}G(k,l) =m_{2}(l). \tag{8c}\]  
The set of all matrices \(G\) for which those conditions (8) are satisfied defines a polytope, which we refer to as \(\mathcal{G}(S_{1},S_{2})\). The minimization of the cost \(U_{p}(G)\) yields an optimal transport plan \(G_{opt}\). We refer to the minimum of the cost as \(d_{p}(S_{1},S_{2})\). Note that \(d_{p}(S_{1},S_{2})\) is not a distance. Its \(p\)-root, however, which we write as \(GW_{p}(S_{1},S_{2})=\big{(}U_{p}(G_{opt})\big{)}^{\frac{1}{p}}\) is a metric distance between \((S_{1},d_{1})\) and \((S_{2},d_{2})\) quotiented by measure-preserving isometries [8]. Solving for the transport plan that minimizes Equation (7) under the constraints defined in Equation (8) is a non-convex quadratic optimization problem [27; 28] and therefore \(NP\)-hard in the general case (see for example [29]). To circumvent this large computing cost when \(N\) is large, following [PERSON]'s idea proposed for the optimal transport problem [18], [PERSON] et al. proposed a regularized version of Equation (7) [22]:  
\[U_{p,c}(G) = \sum\limits_{k,l}\sum\limits_{k^{\prime},l^{\prime}}G(k,l)\big{|} d_{1}(k,k^{\prime})-d_{2}(l,l^{\prime})\big{|}^{p}G(k^{\prime},l^{\prime})+ \epsilon\sum\limits_{k,l}G(k,l)\log(G(k,l)), \tag{9}\]  
where \(\epsilon\) is a parameter that controls the level of regularization. This parameter scales an entropic term, with the entropy set to \(-x\ln(x)\), the standard information theory entropy,which imposes the positivity of the \(G(k,l)\) terms [18]. This regularized GW problem can then be solved iteratively using a regularized linear optimal transport solver, as described in Algorithm 1. Algorithm 1 is akin to a sequential quadratic programming method [30]. Briefly, given two sets of weighted points and the intra-set distances between those points, a \"cost matrix\" between the two sets is defined from the current transport plan \(G\) (initialized according to the masses of the points). This cost matrix is then used to solve a regularized linear optimal transport problem. The corresponding optimal transport plan is then used to update the cost matrix, and the procedure is then iterated until the transport plan does not change anymore (within a tolerance), i.e., when the transport plan and the cost matrix are consistent.