# Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
## Appendix B Proof of Proposition 2: Retrieving the Transport Plan from the SPA Solutions
### Monotonicity of the Free Energy  
The effective free energy \(F_{\beta}\) defined in Equation (24) is a function of the distance matrices \(d_{1}\) and \(d_{2}\) and of the real unconstrained variables \(C(k,l)\), \(D(k,l)\), \(\lambda(k)\), \(\mu(l)\), and \(s\). For sake of simplicity, for any \((k,l)\in[1,N_{1}]\times[1,N_{2}]\), we define:  
\[x(k,l)=C(k,l)+\lambda(k)+\mu(l). \tag{12}\]  
The effective free energy is then  
\[F_{\beta} =-\sum_{k,l}D(k,l)C(k,l)-\left(\sum_{k}\lambda(k)m_{1}(k)+\sum_{l }\mu_{l}m_{2}(l)\right) \tag{13}\] \[+\sum_{k,k}\sum_{l,l^{\prime}}D(k,l)\big{|}d_{1}(k,k^{\prime})-s \cdot d_{2}(l,l^{\prime})\big{|}^{p}D(k^{\prime},l^{\prime})-\frac{1}{\beta} \sum_{k,l}\ln\left(\frac{1-e^{-\beta x(k,l)}}{\beta x(k,l)}\right).\]  
As written above, \(F_{\beta}\) is a function of the variables \(\beta\), \(C(k,l)\), \(D(k,l)\), \(\lambda(k)\), \(\mu(l)\), and \(s\). However, under the saddle point approximation, with \(s=\bar{s}\), namely its optimal value, the free energy takes the value \(F_{\beta}^{MF}\), with the following constraints,\[\frac{\partial F_{\beta}^{MF}}{\partial C(k,l)} = 0,\quad\frac{\partial F_{\beta}^{MF}}{\partial D(k,l)}=0,\] \[\frac{\partial F_{\beta}^{MF}}{\partial\lambda(k)} = 0,\quad\frac{\partial F_{\beta}^{MF}}{\partial\mu(l)}=0, \tag{101}\] \[\frac{\partial F_{\beta}^{MF}}{\partial s} = 0,\]  
for all \(k\in[1,N_{1}]\) and all \(l\in[1,N_{2}]\). In the following, we will use the notations \(\frac{dF_{\beta}^{MF}}{d\beta}\) and \(\frac{\partial F_{\beta}^{MF}}{\partial\beta}\) to differentiate between the total derivative and partial derivative of \(F_{\beta}^{MF}\) with respect to \(\beta\), respectively. Based on the chain rule,  
\[\frac{dF_{\beta}^{MF}}{d\beta}= \frac{\partial F_{\beta}^{MF}}{\partial\beta}+\sum_{k,l}\frac{ \partial F_{\beta}^{MF}}{\partial C(k,l)}\frac{\partial C(k,l)}{\partial\beta }+\sum_{k,l}\frac{\partial F_{\beta}^{MF}}{\partial D(k,l)}\frac{\partial D(k,l)}{\partial\beta}+ \tag{102}\] \[\sum_{k}\frac{\partial F_{\beta}^{MF}}{\partial\lambda(k)}\frac{ \partial\lambda(k)}{\partial\beta}+\sum_{l}\frac{\partial F_{\beta}^{MF}}{ \partial\mu(l)}\frac{\partial\mu(l)}{\partial\beta}+\frac{\partial F_{\beta}^ {MF}}{\partial s}\frac{\partial s}{\partial\beta}.\]  
Using the constraints defined in Equation (102), we find that  
\[\frac{dF_{\beta}^{MF}}{d\beta}=\frac{\partial F_{\beta}^{MF}}{\partial\beta}, \tag{103}\]  
namely that the total derivative with respect to \(\beta\) is in this specific case equal to the corresponding partial derivative, which is easily computed to be  
\[\frac{dF_{\beta}^{MF}}{d\beta}=\frac{1}{\beta^{2}}\sum_{k,l}\left[\ln\left( \frac{1-e^{-\beta x^{MF}(k,l)}}{\beta x^{MF}(k,l)}\right)+\beta x^{MF}(k,l) \phi(\beta x^{MF}(k,l))\right], \tag{104}\]  
where \(\phi(x)=\frac{e^{-x}}{e^{-x}-1}+\frac{1}{x}\), as defined in Equation (26). Let \(f(x)=\ln\left(\frac{1-e^{-x}}{x}\right)+x\phi(x)\). As mentioned in the main text of the paper, \(\phi(x)\) is monotonically constrained in the interval \([0,1]\) and therefore correctly represent the possible values for the corresponding transport plan. The function \(f(x)\) is continuous and defined over all real values \(x\) (with the extension \(f(0)=0\)) and is bounded above by \(0\), i.e., \(f(x)\leq 0\quad\forall x\in\mathbb{R}\). As  
\[F_{\beta} =-\sum_{k,l}D(k,l)C(k,l)-\left(\sum_{k}\lambda(k)m_{1}(k)+\sum_{l }\mu_{l}m_{2}(l)\right) \tag{13}\]0  
we conclude that  
\[F_{\beta} =-\sum_{k,l}D(k,l)C(k,l)-\left(\sum_{k}\lambda(k)m_{1}(k)+\sum_{l }\mu_{l}m_{2}(l)\right) \tag{13}\]1  
namely that \(F_{\beta}^{MF}\) is a monotonically decreasing function of \(\beta\). In addition, we note that \(F_{\beta}^{MF}\) is the mean field approximation of the true free energy \(\mathcal{F}_{\beta}\) and that this approximation becomes exact when \(\beta\) tends to \(\infty\).