# Fused Gromov-Wasserstein Distance for Structured Objects
## 7 Proofs of the Mathematical Properties
### Proof of Theorem 3--Interpolation Properties between \(GW\) and \(W\)  
Proof.: Let \(\pi_{OT}\in\Pi(\mu_{A},\
u_{B})\) be an optimal coupling for the \(pq\)-Wasserstein distance between \(\mu_{A}\) and \(\
u_{B}\). We can use the same Gluing lemma (Lemma 5.3.2 in [65]) to construct:  
\[\rho\in P(\overbrace{X\times\underbrace{\Omega\times\overbrace{\Omega\times Y }^{\
u}}_{\pi_{OT}}}^{\mu}\overbrace{\
u\times Y}^{\
u})\]  
such that \(\rho\in\Pi(\mu,\
u)\) and \(P_{2,3}\#\rho=\pi_{OT}\).  
Moreover we have:  
\[\int\limits_{\Omega\times\Omega}d(a,b)^{pq}d\pi_{OT}(a,b)=\int\limits_{X\times \Omega\times\Omega\times Y}d(a,b)^{pq}d\rho(x,a,b,y) \tag{48}\]  
Let \(\alpha\geq 0\) and \(\pi_{\alpha}\) optimal plan for the Fused Gromov-Wasserstein distance between \(\mu\) and \(\
u\).  
We can deduce that:  
\[d_{FGW,\alpha,p,q}(\mu,\
u)^{p}-(1-\alpha)^{p}d_{W,pq}(\mu_{A}, \
u_{B})^{pq}\] \[=\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}\right)^{p}d\pi_{a}(( x,a),(y,b))d\pi_{a}((x^{\prime},a^{\prime}),(y^{\prime},y^{\prime}))-\int\limits_{ \Omega\times\Omega}(1-\alpha)^{p}d(a,b)^{pq}d\pi_{OT}(a,b)\] \[\stackrel{{(x)}}{{\leq}}\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}\right)^{p}d\rho(x,a,b,y)d\rho(x^{\prime},a^{\prime},b^{\prime}, y^{\prime})-\int\limits_{X\times\Omega\times Y\times\Omega}(1-\alpha)^{p}d(a,b)^{pq}d \rho(x,a,b,y)\] \[=(1-\alpha)^{p}\int\limits_{(X\times\Omega\times Y\times\Omega)^ {2}}d(a,b)^{pq}d\rho(x,a,b,y)d\rho(x^{\prime},a^{\prime},b^{\prime},y^{\prime })-(1-\alpha)^{p}\int\limits_{X\times\Omega\times Y\times\Omega}d(a,b)^{pq}d \rho(x,a,b,y)\] \[+\sum\limits_{k=0}^{p-1}\binom{p}{k}(1-\alpha)^{k}\alpha^{p-k} \int\limits_{(X\times\Omega\times Y\times\Omega)^{2}}d(a,b)^{ik}L(x,y,x^{ \prime},y^{\prime})^{q(p-k)}d\rho(x,a,b,y)d\rho(x^{\prime},a^{\prime},b^{ \prime},y^{\prime})\] \[=\sum\limits_{k=0}^{p-1}\binom{p}{k}(1-\alpha)^{k}\alpha^{p-k} \int\limits_{(X\times\Omega\times Y\times\Omega)^{2}}d(a,b)^{ik}L(x,y,x^{ \prime},y^{\prime})^{q(p-k)}d\rho(x,a,b,y)d\rho(x^{\prime},a^{\prime},b^{ \prime},y^{\prime}).\]  
We note \(H_{k}=\int\limits_{(X\times\Omega\times Y\times\Omega)^{2}}d(a,b)^{qk}L(x,y,x ^{\prime},y^{\prime})^{q(p-k)}d\rho(x,a,b,y)d\rho(x^{\prime},a^{\prime},b^{ \prime},y^{\prime})\).  
Using (9) we have shown that:  
\[(1-\alpha)(d_{W,pq}(\mu_{A},\
u_{B}))^{q}\leq d_{FGW,\alpha,p,q}(\mu,\
u)\leq \left((1-\alpha)^{p}(d_{W,pq}(\mu_{A},\
u_{B}))^{pq}+\sum\limits_{k=0}^{p-1} \binom{p}{k}(1-\alpha)^{k}\alpha^{p-k}H_{k}\right)^{\frac{1}{p}}\]  
Accordingly, \(\lim\limits_{a\to 0}d_{FGW,\alpha,p,q}(\mu,\
u)=(d_{W,pq}(\mu_{A},\
u_{B}))^{q}\).  
For the case \(\alpha\to 1\) we rather consider \(\pi_{GW}\in\Pi(\mu_{X},\
u_{Y})\) an optimal coupling for the \(pq\)-Gromov-Wasserstein distance between \(\mu_{X}\) and \(\
u_{Y}\) and we construct  
\[\gamma\in P(\overbrace{\Omega\times\underbrace{X\times\overbrace{\gamma\times \Omega}^{\
u}}_{\pi_{GW}}}^{\mu}\overbrace{\pi_{GW}\times\Omega}^{\
u})\]such that \(\gamma\in\Pi(\mu,\
u)\) and \(P_{2,3}\#\rho=\pi_{GW}\). In the same way as previous reasoning we can derive:  
\[\alpha(d_{GW,pq}(\mu_{X},\
u_{Y}))^{q}\leq d_{FGW,\alpha,p,q}(\mu,\
u)\leq\left( \alpha^{p}(d_{GW,pq}(\mu_{X},\
u_{Y}))^{pq}+\sum_{k=0}^{p-1}\binom{p}{k}(1- \alpha)^{p-k}\alpha^{k}j_{k}\right)^{\frac{1}{p}} \tag{49}\]  
with \(J_{k}=\int d(a,b)^{q(p-k)}L(x,y,x^{\prime},y^{\prime})^{qk}d\rho(x,a,b,y)d\rho( x^{\prime},a^{\prime},b^{\prime},y^{\prime})\). In this way \(\lim_{\alpha\to 1}d_{FGW,\alpha,p,q}(\mu,\
u)=(d_{GW,pq}(\mu_{X},\
u_{Y}))^{q}\).