# Fused Gromov-Wasserstein Distance for Structured Objects
## 7 Proofs of the Mathematical Properties
### Proof of Theorem 4--Constant Speed Geodesic  
**Proof.** Let \(t,s\in[0,1]\). Recalling:  
\[\forall(x,a),(y,b)\in X\times\Omega\times Y\times\Omega,\ \eta_{t}(x,a,y,b)=(x,y,(1-t)a+tb) \tag{50}\]  
We note \(\mathbb{S}_{t}=(X\times Y\times\Omega,(1-t)d_{X}\oplus td_{Y},\mu_{t}=\eta_{t }\#\pi^{*})_{t\in[0,1]}\) and \(d_{t}=(1-t)d_{X}\oplus td_{Y}\). Let \(\|.\|\) be any \(\ell_{m}\) norm for \(m\geq 1\). It suffices to prove:  
\[d_{FGW,\alpha,p,1}(\mu_{t},\mu_{s})\leq|t-s|d_{FGW,\alpha,p,1}(\mu_{0},\mu_{1}) \tag{51}\]  
To do so, we consider \(\Delta_{s}^{t}\in P(X\times Y\times\Omega\times X\times Y\times\Omega)\) defined by \(\Delta_{s}^{t}=(\eta_{t}\times\eta_{s})\#\pi^{*}\in\Pi(\mu_{t},\mu_{s})\) and the following \"diagonal\" coupling:  
\[d\gamma_{s}^{t}((x,y),a,(x^{\prime\prime},y^{\prime\prime}),b)=d\Delta_{s}^{t} ((x,y),a,(x^{\prime\prime},y^{\prime\prime}),b)d\delta_{(x_{0},x_{1})}(x_{0}^{ \prime\prime},x_{1}^{\prime\prime}) \tag{52}\]  
Subsquently, \(\gamma_{s}^{t}\in P(X\times Y\times\Omega\times X\times Y\times\Omega)\) and since \(\Delta_{s}^{t}\in\Pi(\mu_{t},\mu_{s})\) then \(\gamma_{s}^{t}\in\Pi(\mu_{t},\mu_{s})\) So by suboptimality:  
\[d_{FGW,\alpha,p,1}(\mu_{t},\mu_{s})^{p}\leq\int\limits_{(X\times Y \times\Omega\times X\times Y\times\Omega)^{2}}\left((1-\alpha)d(a,b)+\alpha |d_{t}|(x,y),(x^{\prime},y^{\prime})|-d_{s}|(x^{\prime\prime},y^{\prime\prime }),(x^{\prime\prime\prime},y^{\prime\prime})|\right)^{p}\] \[d\gamma_{s}^{t}(x,y,a,x^{\prime\prime},y^{\prime},b)d\gamma_{s}^ {t}(x^{\prime},y^{\prime},a^{\prime},x^{\prime\prime},y^{\prime\prime},b^{ \prime})\] \[=\int\limits_{(X\times Y\times\Omega\times X\times Y\times\Omega)^ {2}}\left((1-\alpha)d(a,b)+\alpha|d_{t}|(x,y),(x^{\prime},y^{\prime})|-d_{s}| (x,y),(x^{\prime},y^{\prime})|\right)^{p}\] \[d\Delta_{s}^{t}(x,y,a,x,y,b)d\Delta_{s}^{t}(x^{\prime},y^{\prime},a^{\prime},x^{\prime},y^{\prime},b^{\prime})\] \[=\int\limits_{(X\times\Omega\times Y\times\Omega)^{2}}\left((1- \alpha)\|(1-t)a+tb-(1-s)a-sb\|+\alpha|(1-t)d_{X}(x,x^{\prime})+td_{Y}(y,y^{ \prime})-(1-s)d_{X}(x,x^{\prime})+sd_{Y}(y,y^{\prime})|\right)^{p}\] \[d\pi^{*}(x,a,y,b)d\pi^{*}(x^{\prime},a^{\prime},y^{\prime},b^{ \prime})\] \[=|t-s|^{p}\int\limits_{(X\times\Omega\times Y\times\Omega)^{2}} \left((1-\alpha)\|a-b\|+\alpha|d_{X}(x,x^{\prime})-d_{Y}(y,y^{\prime})|\right)^ {p}d\pi^{*}(x,a,y,b)d\pi^{*}(x^{\prime},a^{\prime},y^{\prime},b^{\prime})\] So \[d_{FGW,\alpha,p,1}(\mu_{t},\mu_{s})\leq|t-s|d_{FGW,\alpha,p,1}(d_{0}, \mu_{1},\mu_{0},\mu_{1})\]  
**Author Contributions:** Conceptualization, T.V., L.C., N.C., R.T. and R.F.; methodology, T.V., L.C., N.C., R.T. and R.F.; software, T.V., R.F., L.C. and N.C.; formal analysis, T.V., L.C., N.C., R.T. and R.F.; investigation, T.V., L.C., N.C., R.T. and R.F.; resources, T.V., L.C., N.C., R.T. and R.F.; data curation, T.V., R.F., L.C. and N.C.; writing--original draft preparation, T.V.; writing--review and editing, T.V., L.C., N.C., R.T. and R.F.; visualization, T.V., L.C. and R.F.; supervision, L.C., N.C., R.T. and R.F.; project administration, L.C., N.C., R.T. and R.F.; funding acquisition, L.C., N.C., R.T. and R.F. All authors have read and agreed to the published version of the manuscript.  
**Funding:** This work is partially funded through the projects OATMIL ANR-17-CE23-0012, 3 IA Cote d Azur Investments ANR-19-P3 IA-0002 and MATS ANR-18-CE23-0006 of the French National Research Agency (ANR).  
**Conflicts of Interest:** The authors declare no conflict of interest.