# Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
## 3 A Statistical Physics Approach to Solving the Gromov-Wasserstein Problem
In practice, however, it is of limited interest because the partition function and thus the extrema of the free energy cannot be computed explicitly. We propose using the saddle point approximation to approximate these quantities. We will demonstrate that the corresponding mean field values have the same properties as the exact quantities defined above. These mean field values are easily calculated. Following the method described in Ref. [23] to impose the constraints that define \(\mathcal{G}(S_{1},S_{2})\), the partition function can be rewritten as \[Z_{\beta}(s,S_{1},S_{2})= \int_{0}^{1}\prod_{k,l}dG(k,l)e^{-\beta\sum\limits_{k,l}\sum\limits_ {k^{\prime},l^{\prime}}G(k,l)|d_{1}(k,k^{\prime})-s\cdot d_{2}(l,l^{\prime})|^{ p}G(k^{\prime},l^{\prime})}\times \tag{15}\] \[\prod_{k}\delta\left(\sum_{l}G(k,l)-m_{1}(k)\right)\prod_{l} \delta\left(\sum_{k}G(k,l)-m_{2}(l)\right).\]  
To account for the quadratic term in the exponential, we introduce new variables \(C(k,l)\) that are constrained to mimic a cost function between \(S_{1}\) and \(S_{2}\):  
\[Z_{\beta}(s,S_{1},S_{2})= \int_{0}^{1}\prod_{k,l}dG(k,l)\int_{-\infty}^{+\infty}\prod_{k,l} dC(k,l) \tag{16}\] \[e^{-\beta\sum\limits_{k,l}^{C(k,l)C(k,l)}}\times\] \[\prod_{k}\delta\left(\sum_{l}G(k,l)-m_{1}(k)\right)\prod_{l} \delta\left(\sum_{k}G(k,l)-m_{2}(l)\right)\] \[P(s,G)=\frac{1}{Z_{\beta}(s,S_{1},S_{2})}e^{-\beta U_{p}(s,G)}. \tag{11}\]0  
Using the Fourier representation of a delta function,  
\[P(s,G)=\frac{1}{Z_{\beta}(s,S_{1},S_{2})}e^{-\beta U_{p}(s,G)}. \tag{11}\]1  
the partition function can be recast with integrals only. To do so, we introduce the Fourier variables \(D(k,l)\), \(\lambda(k)\) and \(\mu(l)\), with \((k,l)\in[1,N_{1}]\times[1,N_{2}]\). Omitting the normalization factors \(1/(2\pi)\), the partition function can then be expressed as,  
\[P(s,G)=\frac{1}{Z_{\beta}(s,S_{1},S_{2})}e^{-\beta U_{p}(s,G)}. \tag{11}\]2 \[P(s,G)=\frac{1}{Z_{\beta}(s,S_{1},S_{2})}e^{-\beta U_{p}(s,G)}. \tag{11}\]3 \[P(s,G)=\frac{1}{Z_{\beta}(s,S_{1},S_{2})}e^{-\beta U_{p}(s,G)}. \tag{11}\]4  
Note that we have introduced an explicit scaling factor \(\beta\) for the variables \(D(k,l)\), \(\lambda(k)\) and \(\mu(l)\). The corresponding terms are then consistent with the energy term. Note also that the terms within the integrals in \(Z\) are now complex functions, while the partition function \(Z\) itself is real. For sake of clarity, we include the i in \(D(k,l)\), \(\lambda(k)\) and \(\mu(l)\), i.e., \(D(k,l)\equiv iD(k,l)\), \(\lambda(k)\equiv i\lambda(k)\) and \(\mu(l)\equiv i\mu(l)\). Those variables are now complex. After rearrangements,  
\[P(s,G)=\frac{1}{Z_{\beta}(s,S_{1},S_{2})}e^{-\beta U_{p}(s,G)}. \tag{11}\]5 \[P(s,G)=\frac{1}{Z_{\beta}(s,S_{1},S_{2})}e^{-\beta U_{p}(s,G)}. \tag{11}\]6 \[P(s,G)=\frac{1}{Z_{\beta}(s,S_{1},S_{2})}e^{-\beta U_{p}(s,G)}. \tag{11}\]7  
\[ \begin{cases}D(k,l)&=\phi(\beta(C(k,l)+\lambda(k)+\mu(l)))\\ C(k,l)&=2\sum\limits_{k^{\prime},l^{\prime}}|d_{1}(k,k^{\prime})-s\cdot d_{2}(l,l ^{\prime})|^{p}D(k^{\prime},l^{\prime})\\ \sum\limits_{l}D(k,l)&=m_{1}(k)\\ \sum\limits_{k}D(k,l)&=m_{2}(l)\end{cases}  \tag{25}\]  
where,  
\[\phi(x)=\frac{e^{-x}}{e^{-x}-1}+\frac{1}{x}. \tag{26}\]  
For all real values \(x\), the function \(\phi(x)\) is defined and continuous (once we set \(\phi(0)=0.5\)). It is monotonically decreasing over \(\mathbb{R}\), with the asymptotes \(y=1\) and \(y=0\) at \(-\infty\) and \(+\infty\), respectively. The free energy \(F_{\beta}(s,S_{1},S_{2})\) can then be minimized with respect to \(s\), namely \(\frac{\partial F_{\beta}}{\partial s}=0\), leading to the equation:  
\[\sum\limits_{k,k^{\prime}}\sum\limits_{l,l^{\prime}}D(k,l)d_{2}(l,l^{\prime}) \big{|}d_{1}(k,k^{\prime})-s\cdot d_{2}(l,l^{\prime})\big{|}^{p-2}(d_{1}(k,k^{ \prime})-s\cdot d_{2}(l,l^{\prime}))D(k^{\prime},l^{\prime})=0, \tag{27}\]  
which needs to be solved for \(s\). Given \(D(k,l)\), this equation is polynomial in \(s\), with degree \(p-1\).