# Fused Gromov-Wasserstein Distance for Structured Objects
## 7 Proofs of the Mathematical Properties
### Proof of Theorem 1--Metric Properties of FGW  
We prove the theorem point by point: first the existence, then the equality relation and finally the triangle inequality statement. We first recall the definition of weak convergence of probability measure in a metric space [62]:  
**Definition 10** (Weak-convergence on a metric space): _Let \((\mu_{n})_{n\in\mathbb{N}}\) be a sequence of probability measures on \((X,\mathcal{B}(d))\) where \((X,d)\) is a completely metrizable topological space (Polish space) and \(\mathcal{B}(d)\) is the Borel \(\sigma\)algebra. We say that \((\mu_{n})_{n\in\mathbb{N}}\) converges weakly to \(\mu\) in \((X,\mathcal{B}(d))\) if for all continuous and bounded functions \(f:X\to R\):_  
\[\int_{X}fd\mu_{n}\to\int_{X}fd\mu \tag{31}\]  
We also recall the definition of semi continuity in a metric space:  
**Definition 11** (Lower-semi continuity). : _On a metric space \((X,d)\) a function \(f:X\to\mathbb{R}\cup\{+\infty\}\) is said to be lower semi-continuous (l.s.c.) if for every sequence \(x_{n}\to x\) we have \(f(x)\leq\liminf f(x_{n})\)_  
To state the existence of a minimizer, we will rely on the following lemma:  
**Lemma 3**. : _Let \(W\) be a Polish space. If \(f:W\times W\to\mathbb{R}_{+}\cup+\infty\) is lower semi-continuous, then the functional \(J:\mathcal{P}(W)\to\mathbb{R}\cup+\infty\) with \(J(\mu)=\int\int f(w,w^{\prime})d\mu(w)d\mu(w^{\prime})\) is l.s.c. for the weak convergence of measures._  
Proof. : \(f\) is l.s.c. and bounded from below by 0. We can consider \((f_{k})_{k}\) a sequence of continuous and bounded functions converging increasingly to f (see e.g., [63]). By the monotone convergence theorem \(J_{k}(\mu)\to J(\mu)\stackrel{{ def}}{{=}}\sup_{k}J_{k}(\mu)=\sup _{k}\int\int f_{k}d\mu d\mu\). Moreover every \(J_{k}\) is continuous for the weak convergence. Using Theorem 2.8 [62] on the Polish space \(W\times W\) we know that if \(\mu_{n}\) converges weakly to \(\mu\) then the product measure \(\mu_{n}\otimes\mu_{n}\) converges weakly to \(\mu\otimes\mu\). In this way \(\lim_{n\to\infty}J_{k}(\mu_{n})=J_{k}(\mu)\) since \(f_{k}\) are continuous and bounded. In particular every \(J_{k}\) is l.s.c. We can conclude that \(J\) is l.s.c. as the supremum of l.s.c. functionals on the metric space of \((\mathcal{P}(W),\delta)\) (see e.g., [63]). Here we equipped \(\mathcal{P}(W)\) with a metric \(\delta\) as _e.g._\(\delta(\mu,v)=\sum_{k=1}^{\infty}2^{-k}|\int_{W}f_{k}d\mu-\int_{W}f_{k}dv|\) (see Remark 5.11 in [64]). **Proposition 2**. : _Existence of an optimal coupling for the FGW distance. For \(p,q\geq 1\), \(\pi\to E_{p,q,\alpha}(\pi)\) always achieves a infimum \(\pi^{*}\) in \(\Pi(\mu,v)\) such that \(d_{FGW,\alpha,p,q}(\mu,v)=E_{p,q,\alpha}(\pi^{*})<+\infty\)._  
Proof. : Since \(X\times\Omega\) and \(Y\times\Omega\) are Polish spaces we known that \(\Pi(\mu,v)\subset\mathcal{P}(X\times\Omega\times Y\times\Omega)\) is compact (Theorem 1.7 in [63]), so by applying Weierstrass theorem we can conclude that the infimum is attained at some \(\pi^{*}\in\Pi(\mu,v)\) if \(\pi\to E_{p,q,\alpha}(\pi)\) is l.s.c. We will use Lemma 3 to prove that the functionnal is l.s.c. on \(\Pi(\mu,v)\). If we consider \(W=X\times\Omega\times Y\times\Omega\) which is a a metric space endowed with the distance \(d_{X}\oplus d\oplus d_{Y}\oplus d\) and \(f((w=(x,a,y,b),w^{\prime}=(x^{\prime},a^{\prime},y^{\prime},b^{\prime}))=((1- \alpha)d(a,b)^{q}+\alpha L(x,y,x^{\prime},y^{\prime})^{q})^{p}\) then \(f\) is l.s.c. by continuity of \(d\), \(d_{X}\) and \(d_{Y}\). With the previous reasoning we can conclude that the infimum is attained.