# Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
## Appendix A Proof of Property 1: Monotonicity of the Free Energy and Average Energy  
Let us consider two sets of points \(S_{1}\) and \(S_{2}\) embedded in two metric spaces \((M_{1},d_{1})\) and \((M_{2},d_{2})\) and mass vectors \(\mathbf{m}_{1}\) and \(\mathbf{m}_{2}\), respectively. We associate to this system a transport plan polytope \(\mathcal{G}(S_{1},S_{2})\) and a scaling factor \(s\) between distances within  
As the \(G(k,l)\) take values between \(0\) and \(1\), and as the delta functions restrain the space of possible transport plans, we have indeed that  
\[0\leq\int_{G\in\mathcal{G}(S_{1},S_{2})}d\mu_{12}\leq 1. \tag{10}\]  
The internal energy is the thermodynamic average of the energy \(U_{p}(s,G)\) (see Equation (10)) and is given by  
\[E_{\beta}(s,S_{1},S_{2})=<U(s,G)>_{s\in\mathbb{R},G\in\mathcal{G}(S_{1},S_{2}) }=\frac{d\big{(}\beta\mathcal{F}_{\beta}(s,S_{1},S_{2})\big{)}}{d\beta}, \tag{11}\]  
while the entropy is given by  
\[S_{\beta}(s,S_{1},S_{2})=\beta^{2}\frac{d\mathcal{F}_{\beta}(s,S_{1},S_{2})}{d \beta}=-\frac{d\mathcal{F}_{\beta}(s,S_{1},S_{2})}{dT}. \tag{12}\]  
An important implication of these relations is that  
\[\frac{dE_{\beta}(s,S_{1},S_{2})}{d\beta}=-\Big{(}\langle U_{p}(s,G)^{2} \rangle-\langle U_{p}(s,G)\rangle^{2}\Big{)}, \tag{13}\]  
where the thermodynamics averages \(<>\) are computed over \(\mathbb{R}\) for \(s\) and over the polytope \(\mathcal{G}(S_{1},S_{2})\) for \(G\). The quantity on the right is minus the variance of the energy. It is therefore negative and this is true for all values of \(\beta\). This property is true for all \(s\) and therefore for \(s=\bar{s}\), the optimal value of \(s\). Therefore,  
\[\frac{dE_{\beta}(S_{1},S_{2})}{d\beta}=\frac{dE_{\beta}(\bar{s},S_{1},S_{2})}{ d\beta}\leq 0. \tag{14}\]  
As a result, the internal energy of the system decreases as \(\beta\) increases. As \(U_{p}(\bar{s},G)\) is positive, \(E_{\beta}(S_{1},S_{2})\) is positive: it has a limit when \(\beta\to\infty\). This limit is the traditional GW quantity \(d_{p}(S_{1},S_{2})\) (see Section 2).  
The entropy is negative. Indeed, as the total number of states at an energy \(U_{p}(s,G)\) is given by,  
\[\mathcal{N}(U_{p}(s,G))=\int_{G\in\mathcal{G}(S_{1},S_{2})}\delta\Bigg{(}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})\Bigg{)} d\mu_{12}. \tag{15}\]  
As the volume of the polytope \(\mathcal{G}(S_{1},S_{2})\) is smaller than \(1\) (see above),  
\[0\leq\int_{G\in\mathcal{G}(S_{1},S_{2})}\delta\Bigg{(}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})\Bigg{)}d\mu_{12}\leq 1, \tag{16}\]  
which implies that  
\[\mathcal{N}(U_{p}(s,G))\leq 1. \tag{17}\]  
Since \(\mathcal{N}(U_{p}(s,G))=e^{S_{\beta}(U_{p}(s,G))}\), and all the properties above are valid for all \(s\), they are valid in particular for the value \(s=\bar{s}\) which minimizes the free energy. Taking \(s=\bar{s}\), we get \(S_{\beta}(S_{1},S_{2})\leq 0\) for all \(\beta\) (or equivalently for all \(T\)). The free energy is related to the entropy by  
\[\frac{d\mathcal{F}_{\beta}(S_{1},S_{2})}{dT}=-\beta^{2}\frac{d\mathcal{F}_{ \beta}(S_{1},S_{2})}{d\beta}=-S_{\beta}(S_{1},S_{2}). \tag{18}\]Consequently,  
\[\frac{d\mathcal{F}_{\beta}(S_{1},S_{2})}{d\beta}=\frac{S_{\beta}(S_{1},S_{2})}{ \beta^{2}}\leq 0. \tag{101}\]  
Therefore the free energy of the system decreases as \(\beta\) increases. Its limit for \(\beta\to\infty\) is the same as the limit of \(E_{\beta}\), namely 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}}\).