# Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
## 3 A Statistical Physics Approach to Solving the Gromov-Wasserstein Problem  
Solving the GW problem amounts to finding the minimum of a function defined by Equation (7) over the space of possible couplings between the two discrete sets of points considered. If this function is reworded as an \"energy\", statistical physics allows for a different perspective on how to solve this problem. Indeed, in statistical physics, finding the minimum of an energy function is equivalent to finding the most probable state of the system it characterizes. Here, this system corresponds to the different couplings between between the measured sets of points \(S_{1}\) and \(S_{2}\). We refer to the space of such couplings \(\mathcal{G}(S_{1},S_{2})\) (see above). Couplings \(G\) in this space satisfy multiple constraints. Their row sums and row columns correspond to the masses associated with \(S_{1}\) and \(S_{2}\), respectively (see Equation (8)). In addition, their elements are positive, and in fact smaller than one, if we assume that the sums of the masses on \(S_{1}\) and on \(S_{2}\) are both equal to \(1\) (the fact that these sums are equal is referred to as the balance condition and setting them to 1 is arbitrary but useful, as illustrated below). A state in this system is then characterized with a coupling \(G\) and its energy value \(U_{p}(G)\) as defined by Equation (7). To account for possible differences of scales between the metrics on \(S_{1}\) and \(S_{2}\), we introduce a scaling factor \(s\) between the distances \(d_{1}\) and \(d_{2}\):  
\[U_{p}(s,G)=\sum_{k,l}\sum_{k^{\prime},l^{\prime}}G(k,l)\big{|}d_{1}(k,k^{\prime })-s\cdot d_{2}(l,l^{\prime})\big{|}^{p}G(k^{\prime},l^{\prime}), \tag{10}\]  
where \(p\) is a constant and \(s\) is considered as a variable. The probability of finding the system in a state characterized by \(G\) and \(s\) is:  
\[P(s,G)=\frac{1}{Z_{\beta}(s,S_{1},S_{2})}e^{-\beta U_{p}(s,G)}. \tag{11}\]  
In this equation, \(\beta\) is the inverse of the temperature, namely \(\beta=1/(k_{B}T)\) with \(k_{B}\) the Boltzmann constant and \(T\) the temperature. \(Z_{\beta}(s,S_{1},S_{2})\) is the partition function defined as  
\[Z_{\beta}(s,S_{1},S_{2})=\int_{G\in\mathcal{G}(S_{1},S_{2})}e^{-\beta U_{p}(s, G)}d\mu_{12}. \tag{12}\]  
An interesting property of a partition function \(Z\) is that most thermodynamic variables of the system can be expressed as functions of \(Z\), or as functions of its derivatives. This is the case for the free energy of the system:  
\[\mathcal{F}_{\beta}(s,S_{1},S_{2})=-\frac{1}{\beta}\ln(Z_{\beta}(s,S_{1},S_{2} )), \tag{13}\]  
as well as for the average energy \(E_{\beta}(s,S_{1},S_{2})=<U_{p}(s,G)>_{s\in\mathbb{R},G\in\mathcal{G}}\) by  
\[E_{\beta}(s,S_{1},S_{2})=-\frac{\partial\ln(Z_{\beta}(s,S_{1},S_{2}))}{ \partial\beta}. \tag{14}\]  
In addition to finding the coupling matrix \(G\), we want to find the scaling factor \(s\) that defines the best match between the two distributions. To reach this goal, we will minimize the free energy \(\mathcal{F}_{\beta}(s,S_{1},S_{2})\) with respect to \(s\). The minimized free energy is denoted by \(\mathcal{F}_{\beta}(S_{1},S_{2})\) and similarly, the average energy computed with the minimal \(s\) is denoted as \(E_{\beta}(S_{1},S_{2})\). We start with an important property of the free energy and of the average energy:  
**Proposition 1**. : _For all \(\beta>0\), the free energy and the average energy are monotonically decreasing functions of \(\beta\). Both functions converge to \(d_{p}(S_{1},S_{2})\) from which we can compute the GW distance as \(GW_{p}(S_{1},S_{2})=d_{p}(S_{1},S_{2})^{\frac{1}{p}}\)._  
Proof. : How the functions \(\mathcal{F}_{\beta}\) and of \(E_{\beta}\) behave as the parameter \(\beta\) is increased is studied in Appendix A. This approach to solving the GW problem is appealing. It is based on a temperature-dependent free energy with a monotonic dependence on the inverse of the temperature, \(\beta\), and convergence to the actual GW distance at zero temperature.