# Fused Gromov-Wasserstein Distance for Structured Objects
## 3 Mathematical Properties of \(Fgw\)
### Can We Adapt W and GW for Structured Objects? Despite the appealing properties of both Wasserstein and Gromov-Wasserstein distances, they fail at comparing structured objects by focusing only on the feature and structure marginals, respectively. However, with some hypotheses, one could adapt these distances for structured objects. **Adapting Wasserstein. ** If the structure spaces \((X,d_{X})\) and \((Y,d_{Y})\) are part of a same ground space \((Z,d_{Z})\), i.e., \((X,Y\subset Z\) and \(d_{X}=d_{Y}=d_{Z})\), one can build a distance \(\hat{d}=d_{Z}\oplus d\) between couples \((x,a)\) and \((y,b)\) and apply the Wasserstein distance, so as to compare the two structured objects. In this case, when the Wasserstein distance vanishes it implies that the structured objects are equal in the sense \(\mu=\
u\). This approach is very related with the one discussed in [30], where the authors define the Transportation \(L^{p}\) distance for signal analysis purposes. Their approach can be viewed as a transport between two joint measures \(\mu(X\times\Omega)=\lambda(\{(x,f(x))\mid x\in X\subset Z=\mathbb{R}^{d};\,f(x) \in A\subset\mathbb{R}^{m}\})\), \(\
u(Y\times\Omega)=\lambda(\{(y,g(y))\mid y\in Y\subset Z=\mathbb{R}^{d};\,g(y) \in B\subset\mathbb{R}^{m}\})\) for function \(f,g:Z\rightarrow\mathbb{R}^{m}\) representative of the signal values and \(\lambda\) the Lebesgue measure. The distance for the transport is defined as \(\hat{d}((x,f(x)),(y,g(y)))=\frac{1}{\alpha}\|x-y\|_{p}^{p}+\|f(x)-g(y)\|_{p}^{p}\) for \(\alpha>0\) and \(\|\cdot\|_{p}\) the \(l_{p}\) norm. In this case, \(f(x)\) and \(g(y)\) can be interpreted as encoding the feature information of the signal, while \(x,y\) encode its structure information. This approach is very interesting, but cannot be used on structured objects, such as graphs that will not share a common structure embedding space. **Adapting Gromov-Wasserstein. ** The Gromov-Wasserstein distance can also be adapted to structured objects by considering the distances \((1-\beta)d_{X}\oplus\beta d\) and \((1-\beta)d_{Y}\oplus\beta d\) within each space \(X\times\Omega\) and \(Y\times\Omega\), respectively, and \(\beta\in]0,1[\). When the resulting \(GW\) distance vanishes, structured objects are isomorphic with respect to \((1-\beta)d_{X}\oplus\beta d\) and \((1-\beta)d_{Y}\oplus\beta d\). However, the strong isomorphism is stronger than this notion, since the isomorphism allows for \"permuting the labels\", but not the strong isomorphism. More precisely, we have the following lemma:  
**Lemma 1**: _Let \((X\times\Omega,d_{X},\mu),(Y\times\Omega,d_{Y},\
u)\) be two structured objects and \(\beta\in]0,1[\)._  
_If \((X\times\Omega,d_{X},\mu)\) and \((Y\times\Omega,d_{Y},\
u)\) are strongly isomorphic then \((X\times\Omega,(1-\beta)d_{X}\oplus\beta d,\mu)\) and \((Y\times\Omega,(1-\beta)d_{Y}\oplus\beta d,\
u)\) are isomorphic. However the converse is not true in general._  
**Proof. ** To see this, if we consider \(f\) as defined in Theorem 1, then, for \((x,a),(x^{\prime},b)\in(\text{supp}(\mu))^{2}\), we have \(d_{X}(x,x^{\prime})=d_{Y}(I(x),I(x^{\prime}))\). In this way:  
\[(1-\beta)d_{X}(x,x^{\prime})+\beta d(a,b)=(1-\beta)d_{Y}(I(x),I(x^{\prime}))+ \beta d(a,b) \tag{15}\]  
which can be rewritten as:  
\[(1-\beta)d\oplus\beta d_{X}((x,a),(x^{\prime},b))=(1-\beta)d\oplus\beta d_{Y} (f(x,a),f(x^{\prime},b)) \tag{16}\]  
and so \(f\) is an isometry with respect to \((1-\beta)d\oplus\beta d_{X}\) and \((1-\beta)d\oplus\beta d_{Y}\). Because \(f\) is also measure preserving and surjective \((X\times\Omega,(1-\beta)d_{X}\oplus\beta d,\mu)\) and \((Y\times\Omega,(1-\beta)d_{Y}\oplus\beta d,\
u)\) are isomorphic. However, the converse is not necessarily true, as it is easy to cook up an example with the same structure but with permuted labels, so that objects are isomorphic but not strongly isomorphic.