# Fused Gromov-Wasserstein Distance for Structured Objects
## 7 Proofs of the Mathematical Properties
### Proof of Theorem 1--Metric Properties of FGW
\]  
using Jensen inequality with convexity of \(t\to t^{n}\) and subadditivity of \(|.|\). We note \((*)\) the first term above and \((**)\) the second term above. By the triangle inequality property of \(d\) we have:  
\[\begin{split}\text{(\ref{eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq: eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq  
Now let \(\pi_{*}\) be an optimal coupling for \(d_{FGW,\alpha,p,q}\) between \(\mu\) and \(\
u\). By hypothesis \(d_{FGW,\alpha,p,q}(\mu,\
u)=0\) so that:  
\[J_{qp}(d_{X},d_{Y},\pi*)=0 \tag{38}\]  
and:  
\[H_{qp}(\pi^{*})=0. \tag{39}\]  
Subsequently, \(\int\limits_{(X\times\Omega\times Y\times\Omega)}d(a,b)^{qp}d\pi^{*}((x,a),(y,b ))\)=0 which implies that \(d\) is zero \(\pi^{*}\)_a.e._ so that \(\int\limits_{(X\times\Omega\times Y\times\Omega)}d(a,b)^{m}d\pi^{*}((x,a),(y,b ))=0\) for any \(m\in\mathbb{N}^{*}\). In this way:  
\[M_{qp}(\pi^{*})=\beta\int\limits_{(X\times\Omega\times Y\times \Omega)^{2}}\sum\limits_{h}\binom{qp}{h}d(a,b)^{h}d(a^{\prime},b^{\prime})^{qp -h}d\pi^{*}((x,a),(y,b))d\pi^{*}((x^{\prime},a^{\prime}),(y^{\prime},b^{\prime }))\] \[=\beta\sum\limits_{h}\binom{qp}{h}\Big{(}\int\limits_{(X\times \Omega\times Y\times\Omega)}d(a,b)^{h}d\pi^{*}((x,a),(y,b))\Big{)}\Big{(}\int \limits_{(X\times\Omega\times Y\times\Omega)}d(a^{\prime},b^{\prime})^{qp-h}d \pi^{*}((x^{\prime},a^{\prime}),(y^{\prime},b^{\prime}))\Big{)}=0\]  
Using Equation (37), we have shown  
\[J_{qp}(d_{X\times\Omega},d_{Y\times\Omega},\pi_{*})=0\]  
which implies that \(d_{GW,p}(d_{X\times\Omega},d_{Y\times\Omega},\mu,\
u)=0\) for the coupling \(\pi^{*}\). Thanks to the Gromov-Wasserstein properties (see [17]) this states the existence of an isometry between \(\operatorname{supp}(\mu)\) and \(\operatorname{supp}(\
u)\). So there exists a surjective function \(f=(f_{1},f_{2}):\operatorname{supp}(\mu)\to\operatorname{supp}(\
u)\), which verifies **P.1** and:  
\[\forall((x,a),(x^{\prime},a^{\prime}))\in(\operatorname{supp}(\mu))^{2},\;d_{ X\times\Omega}((x,a),(x^{\prime},a^{\prime}))=d_{Y\times\Omega}(f(x,a),f(x^{ \prime},a^{\prime})) \tag{40}\]  
or equivalently:  
\[\forall((x,a),(x^{\prime},a^{\prime}))\in(\operatorname{supp}(\mu))^{2},\;(1 -\beta)d_{X}(x,x^{\prime})+\beta d(a,a^{\prime})=(1-\beta)d_{Y}(f_{1}(x,a),f_{ 1}(x^{\prime},a^{\prime}))+\beta d(f_{2}(x,a),f_{2}(x^{\prime},a^{\prime})) \tag{41}\]  
In particular, \(\pi^{*}\) is concentrated on \(\{(x,y)=f(x,y)\}\) or equivalently \(\pi^{*}=(I_{d}\times f)\#\mu\). Injecting \(\pi^{*}\) in (39) leads to:  
\[H_{qp}(\pi^{*})=\int\limits_{(X\times\Omega\times Y\times\Omega)}d(a,b)^{qp}d \pi^{*}((x,a),(y,b))=\int\limits_{X\times\Omega}d(a,f_{2}(x,a))^{qp}d\mu(x,a)=0 \tag{42}\]  
Which implies:  
\[\forall(x,a)\in\operatorname{supp}(\mu)\;,f_{2}(x,a)=a \tag{43}\]  
Moreover, using the equality (41), we can conclude that:  
\[\forall(x,a)(x^{\prime},a^{\prime})\in\operatorname{supp}(\mu)^{2},\;d_{X}(x, x^{\prime})=d_{Y}(f_{1}(x,a),f_{1}(x^{\prime},a^{\prime})) \tag{44}\]  
In this way, \(f\) verifies all of the properties (33)-(35). Moreover, suppose that \(\mu\) and \(\
u\) are generalized labeled graphs. In this case there exists \(\ell_{f}:X\to A\) surjective such that \(\mu=(I\times\ell_{f})\#\mu_{X}\). Afterwards, (44) implies that:  
\[H_{qp}(\pi^{*})=0. \tag{39}\]0  
We define \(I:\operatorname{supp}(\mu_{X})\to\operatorname{supp}(\mu_{Y})\) such that \(I(x)=f_{1}(x,\ell_{f}(x))\). Then we have by (45) \(d_{X}(x,x^{\prime})=d_{Y}(I(x),I(x^{\prime}))\) for \((x,x^{\prime})\in\operatorname{supp}(\mu_{X})^{2}\). Overall we have \(f(x,a)=(I(x),a)\) for all \((x,a)\in\operatorname{supp}(\mu)\). Also since \(f\#\mu=\
u\) we have \(I\#\mu_{X}=\
u_{Y}\). Moreover, \(I\) is a surjective function. Indeed let \(y\in\text{supp}(\
u_{Y})\). Let \(b\in\text{supp}(\
u_{B})\) such that \((y,b)\in\text{supp}(\
u)\). By surjectivity of \(f\) there exists \((x,a)\in\text{supp}(\mu)\) such that \((y,b)=f(x,a)=(I(x),a)\) so that \(y=I(x)\). Overall, \(f\) satisfies all **P.1**, **P.2** and **P.3** if \(\mu\) and \(\
u\) are generalized labeled graphs.