# Fused Gromov-Wasserstein Distance for Structured Objects
## 7 Proofs of the Mathematical Properties
### Proof of Theorem 1--Metric Properties of FGW
Finally finiteness come from:  
\[\int\limits_{(X\times\Omega\times Y\times\Omega)^{2}}\left((1- \alpha)d(a,b)^{q}+\alpha L(x,y,x^{\prime},y^{\prime})^{q})^{p}\,d\pi((x,a),(y,b ))\,d\pi((x^{\prime},a^{\prime}),(y^{\prime},b^{\prime}))\right. \tag{32}\] \[\stackrel{{*}}{{\leq}}\int 2^{p-1}(1-\alpha)d(a,b)^{qp}d\mu_{A}(a) dv(b)+\int 2^{p-1}\alpha L(x,y,x^{\prime},y^{\prime})^{qp}d\mu_{X}(x)d\mu_{X}(x^{ \prime})dv_{Y}(y^{\prime})dv_{Y}(y^{\prime})\] \[\stackrel{{**}}{{<}}+\infty\]  
where in (*) we used Lemma 30 and in (**) that \(\mu,v\) are in \(\mathbb{S}_{pq}(\Omega)\). **Proposition 3**. : _Equality relation. For \(\alpha\in]0,1[\), \(d_{FGW,\alpha,p,q}(\mu,v)=0\) if an only if there exists a bijective function \(f=(f_{1},f_{2}):supp(\mu)\to supp(v)\) such that:_  
\[f\#\mu=v \tag{33}\]  
\[\forall(x,a)\in supp(\mu)\,,f_{2}(x,a)=a \tag{34}\]\[\forall(x,a),(x^{\prime},a^{\prime})\in supp(\mu)^{2},\;d_{X}(x,x^{\prime})=d_{Y}(f _{1}(x,a),f_{1}(x^{\prime},a^{\prime})) \tag{35}\]  
_Moreover if \((\mu,\
u)\) are generalized labeled graphs then \(d_{FGW,\alpha,p,q}(\mu,\
u)=0\) if and only if \((X,d_{X},\mu)\) and \((Y,d_{Y},\
u)\) are strongly isomorphic._  
Proof. : For the first point, let us assume that there exists a function \(f\) verifying (33)-(35). We consider the map \(\pi=(I_{d}\times f)\#\mu\in\Pi(\mu,\
u)\). We note \(f=(f_{1},f_{2})\). Then:  
\[ \begin{split} E_{p,\mathcal{A}}(\pi)&=\int\limits_ {(X\times\Omega\times Y\times\Omega)^{2}}\Big{(}(1-\alpha)d(a,b)^{q}+\alpha L( (x,y,x^{\prime},y^{\prime})^{q})\Big{)}^{p}d\pi((x,a),(y,b))d\pi((x^{\prime}, a^{\prime}),(y^{\prime},b^{\prime}))\\ &=\int\limits_{(X\times\Omega)^{2}}\Big{(}(1-\alpha)d(a,f_{2}(x,a))^{q}+\alpha L\big{(}(x,f_{1}(x,a),x^{\prime},f_{1}(x^{\prime},a^{\prime}) )^{q}\big{)}^{p}d\mu(x,a)d\mu(x^{\prime},a^{\prime})\\ &=\int\limits_{(X\times\Omega)^{2}}\Big{(}(1-\alpha)d(a,f_{2}(x,a))^{q}+\alpha|d_{X}(x,x^{\prime})-d_{Y}(f_{1}(x,a),f_{1}(x^{\prime},a^{ \prime}))|^{q}\Big{)}^{p}d\mu(x,a)d\mu(x^{\prime},a^{\prime})\\ &=0\end{split}  \tag{36}\]  
Conversely, suppose that \(d_{FGW,\alpha,p,q}(\mu,\
u)=0\). To prove the existence of a map \(f:\text{supp}(\mu)\rightarrow\text{supp}(\
u)\) verifying (33)-(35) we will use the Gromov-Wasserstein properties. We are looking for a vanishing Gromov-Wasserstein distance between the spaces \(X\times\Omega\) and \(Y\times\Omega\) equipped with our two measures \(\mu\) and \(\
u\). More precisely, we define for \(\big{(}(x,a),(y,b),(x^{\prime},a^{\prime}),(y^{\prime},b^{\prime})\big{)}\in( X\times\Omega\times Y\times\Omega)^{2}\) and \(\beta\in]0,1[\):  
\[d_{X\times\Omega}\big{(}(x,a),(x^{\prime},a^{\prime})\big{)}=(1-\beta)d_{X}(x,x^{\prime})+\beta d(a,a^{\prime})\]  
and  
\[d_{Y\times\Omega}\big{(}(y,b),(y^{\prime},b^{\prime})\big{)}=(1-\beta)d_{Y}(y,y^{\prime})+\beta d(b,b^{\prime})\]  
We will prove that \(d_{GW,p}(d_{X\times\Omega},d_{Y\times\Omega},\mu,\
u)=0\). To show that we will bound the Gromov cost with the metrics \(d_{X\times\Omega},d_{Y\times\Omega}\) by the Gromov cost with the metrics \(d_{X},d_{Y}\) and a Wasserstein cost. Let \(\pi\in\Pi(\mu,\
u)\) be any admissible transportation plan. Subsequently, for \(n\geq 1\):  
\[ \begin{split}& J_{n}(d_{X\times\Omega},d_{Y\times\Omega},\pi) \stackrel{{ def}}{{=}}\int\limits_{(X\times\Omega\times Y\times \Omega)^{2}}L(x,y,x^{\prime},y^{\prime})^{n}d\pi((x,a),(y,b))d\pi((x^{\prime}, a^{\prime}),(y^{\prime},b^{\prime}))\\ &=\int\limits_{(X\times\Omega\times Y\times\Omega)^{2}}|(1-\beta) (d_{X}(x,x^{\prime})-d_{Y}(y,y^{\prime}))+\beta(d(a,a^{\prime})-d(b,b^{\prime }))|^{n}d\pi((x,a),(y,b))d\pi((x^{\prime},a^{\prime}),(y^{\prime},b^{\prime})) \\ &\leq\int\limits_{(X\times\Omega\times Y\times\Omega)^{2}}(1-\beta )|d_{X}(x,x^{\prime})-d_{Y}(y,y^{\prime})|^{n}d\pi((x,a),(y,b))\,d\pi((x^{ \prime},a^{\prime}),(y^{\prime},b^{\prime}))\\ &+\int\limits_{(X\times\Omega\times Y\times\Omega)^{2}}\beta|d(a,a ^{\prime})-d(b,b^{\prime})|^{n}d\pi((x,a),(y,b))d\pi((x^{\prime},a^{\prime}),(y ^{\prime},b^{\prime}))\end{split}