# Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
## 3 A Statistical Physics Approach to Solving the Gromov-Wasserstein Problem
We will see in the implementation section that in the special case \(p=2\), the solution is easy to obtain. We have the following property that relates the solutions of the SPA system of equations to the expected values for the transport plan:  
**Proposition 2**. : _Let \(\mathcal{S}\) be the expected state of the system with respect to the probability given in Equation (11). \(\mathcal{S}\) is associated with an expected transport plan \(\mathcal{G}\) and optimal scaling factor \(s\). Let \(D^{MF}(k,l)\), \(C^{MF}(k,l)\), \(\lambda^{MF}(k)\), \(\mu^{MF}(l)\)and \(s\) be the solutions of the system of Equations (25) and (27). Then the following identities hold,_  
\[\mathcal{G}(k,l) = \phi\big{(}\beta(C^{MF}(k,l)+\lambda^{MF}(k)+\mu^{MF}(l))\big{)}= D^{MF}(k,l). \tag{28}\]  
_Note that the solutions are mean field solutions, hence the superscript \(MF\)._  
Proof. : See Appendix B. Equation (28) shows that each element of \(\mathcal{G}(k,l)\) is built to be in the range of \(\phi(x)\), namely \((0,1)\), as expected by the constraints on \(G\). This optimal coupling matrix \(\mathcal{G}(k,l)\) is real, and therefore the variables \(C(k,l)\), \(D(k,l)\), \(\lambda(k)\) and \(\mu(l)\) must be real. Otherwise stated, note that the integral defining the partition function (see Equation (22)) does not depend on the choice of the integration path. The saddle point Equation (25) shows that a path parallel to the real axis for each of the variables is preferred. For a given value of \(\beta\), the expected values \(\mathcal{G}(k,l)\) define a coupling \(G^{MF}_{\beta}=\mathcal{G}\) between \(S_{1}\) and \(S_{2}\) that is an extremum of the free energy defined in Equation (24). This extremum is referred to as \(F^{MF}_{\beta}\) while the corresponding optimal internal energy is \(U^{MF}_{\beta}=\sum\limits_{k,k^{\prime}}\sum\limits_{l,l^{\prime}}G^{MF}(k,l )|d_{1}(k,k^{\prime})-s\cdot d_{2}(l,l^{\prime})|^{p}G^{MF}(k^{\prime},l^{ \prime})\). Those two values are mean field approximations of the exact free energy and internal energy defined in Equations (13) and (14), respectively. They satisfy the following properties:  
**Proposition 3**. : \(F^{MF}_{\beta}\) _and \(U^{MF}_{\beta}\) are monotonic decreasing functions of the parameter \(\beta\). They both converge to the GW quantity \(d_{p}(S_{1},S_{2})\), with the GW distance being \(\big{(}d_{p}(S_{1},S_{2})\big{)}^{\frac{1}{p}}\)._  
```
Input:\(N_{1}\) and \(N_{2}\), the size of the two sets of points \(S_{1}\) and \(S_{2}\). The mass vectors \(m_{1}(k)\) and \(m_{2}(l)\), for \(k\in[1,N_{1}]\) and \(l\in[1,N_{2}]\). The distance matrices \(d_{1}(k,k^{\prime})\) and \(d_{2}(l,l^{\prime})\) over all points \((k,k^{\prime})\in S_{1}^{2}\) and \((l,l^{\prime})\in S_{2}^{2}\). Initial and final temperatures \(\beta_{0}\), \(\beta_{inf}\). Tolerance, TOL; \(N\), maximum number of iterations. Initialize: Initialize transport plan \(G_{0}(k,l)=m_{1}(k)m_{2}(l)\) and scaling factor \(f_{0}=1\); Set \(STEP=\sqrt{10}\). Set \(\beta^{0}=\beta_{0}/STEP\) for\(i=1,\ldots\)do (1) Set \(\beta^{i}=STEP*\beta^{i-1}\). If \(\beta^{i}\geq\beta_{inf}\) break; (2) Initialize \(s_{0}=f_{i-1}\) for\(j=1,\ldots\) until convergence do (3) Initialize \(D_{0}=G_{i-1}\); for\(m=1,\ldots\) until convergence do (4) Compute \(C_{m}\) from \(D_{m-1}\) and \(s_{j-1}\) using Equation (29). (5) Solve non linear system of equations for \(\lambda\) and \(\mu\): \[\sum_{l}\phi(\beta^{i}(C_{m}(k,l)+\lambda(k)+\mu(l))) = m_{1}(k)\] \[\sum_{k}\phi(\beta^{i}(C_{m}(k,l)+\lambda(k)+\mu(l))) = m_{2}(l),\]  Set solutions as \(\lambda^{sol},\mu^{sol}\) (6) Compute \(D_{m}(k,l)=\phi(\beta^{i}(C_{m}(k,l)+\lambda^{sol}(k)+\mu^{sol}(l)))\) (7) If \(||D_{m}-D_{m-1}||<TOL\), break endfor (8) Compute current scaling factor \(s_{j}\) using converged \(D_{m}\) and Equation (30); (9) If \(|s_{j}-s_{j-1}|<TOL\), break endfor (10) Update \(G_{i}=D_{m}\) and \(f_{i}=s_{j}\).