# Fused Gromov-Wasserstein Distance for Structured Objects
## 2 Structured Objects as Distributions and Fused Gromov-Wasserstein Distance
### Comparing Structured Objects  
We now aim to define a notion of equivalence between two structured objects \((X\times\Omega,d_{X},\mu)\) and \((Y\times\Omega,d_{Y},\
u)\). We note in the following \(\
u_{Y},\
u_{B}\) the marginals of \(\
u\). Intuitively, two structured objects are the same if they share the same feature information, if their structure information are lookalike, and if the probability measures are corresponding in some sense. In this section, we present mathematical tools for individual comparison of the elements of structured objects. First, our formalism implies comparing metric spaces, which can be done _via_ the notion of isometry. **Definition 4** (Isometry). : _Let \((X,d_{X})\) and \((Y,d_{Y})\) be two metric spaces. An isometry is a surjective map \(f:X\to Y\) that preserves the distances:_  
\[\forall x,x^{\prime}\in X,d_{Y}(f(x),f(x^{\prime}))=d_{X}(x,x^{\prime}). \tag{3}\]  
An isometry is bijective, since for \(f(x)=f(x^{\prime})\) we have \(d_{Y}(f(x),f(x^{\prime}))=0=d_{X}(x,x^{\prime})\) and hence \(x=x^{\prime}\) (in the same way \(f^{-1}\) is also a isometry). When it exists, \(X\) and \(Y\) share the same \"size\" and any statement about X, which can be expressed through its distance is transported to \(Y\) by the isometry \(f\). **Example 1**. : _Let us consider the two following graphs whose discrete metric spaces are obtained as shortest path between the vertices (see corresponding graphs in Figure 2)_  
\[ \begin{pmatrix}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\end{pmatrix} \cdot\underbrace{ \begin{pmatrix}0&1&1&1\\ 1&0&1&2\\ 1&1&0&2\\ 1&2&2&0\\ \end{pmatrix} }_{d_{X}(x_{i}x_{j})}\quad\text{and}\quad\quad \begin{pmatrix}y_{ 1}\\ y_{2}\\ y_{3}\\ 1&2&1&0\\ \end{pmatrix} \cdot\underbrace{ \begin{pmatrix}0&1&1&1\\ 1&0&2&2\\ 1&2&0&1\\ 1&2&1&0\\ \end{pmatrix} }_{d_{Y}(y_{i},y_{j})}.\]  
_These spaces are isometric since the map \(f\), such that \(f(x_{1})=y_{1}\), \(f(x_{2})=y_{3}\), \(f(x_{3})=y_{4}\), \(f(x_{4})=y_{2}\) verifies Equation (3)._  
The previous definition can be used in order to compare the structure information of two structured objects. Regarding the feature information, because they all lie in the same ambient space \(\Omega\), a natural way for comparing them is by the standard set equality \(A=B\). Finally, in order to compare measures on different spaces, the notion of preserving map can be used. **Definition 5** (Measure preserving map). : _Let \(\Omega_{1},\mu_{1}\in\mathcal{P}(\Omega_{1})\) and \(\Omega_{2},\mu_{2}\in\mathcal{P}(\Omega_{2})\) be two measurable spaces. A function (usually called a map) \(f:\Omega_{1}\to\Omega_{2}\) is said to be measure preserving if it transports the measure \(\mu_{1}\) on \(\mu_{2}\) such that_  
\[f\#\mu_{1}=\mu_{2}.\]  
_If there exists such a measure preserving map, the properties about measures of \(\Omega_{1}\) are transported via \(f\) to \(\Omega_{2}\)._  
Combining these two ideas together leads to the notion of measurable metric spaces (often called _mm-spaces_[17]), i.e., a metric space \((X,d_{X})\) enriched with a probability measure and described by a triplet \((X,d_{X},\mu_{X}\in\mathcal{P}(X))\). An interesting notion for comparing mm-spaces is the notion of isomorphism. **Definition 6** (Isomorphism). : _Two mm-spaces \((X,d_{X},\mu_{X}),(Y,d_{Y},\mu_{Y})\) are isomorphic if there exists a surjective measure preserving isometry \(f:supp(\mu_{X})\to supp(\
u_{Y})\) between the support of the measures \(\mu_{X},\
u_{Y}\)._  
**Example 2**. : _Let us consider two mm-spaces \((X=\{x_{1},x_{2}\},d_{X}=\{1\},\mu_{X}=\{\frac{1}{2},\frac{1}{2}\})\) and \((Y=\{y_{1},y_{2}\},d_{Y}=\{1\},\mu_{Y}=\{\frac{1}{4},\frac{3}{4}\})\), as depicted in Figure 3. These spaces are isometric, but not isomorphic, as there exists no measure preserving map between them._  
All of this considered, we can now define a notion of equivalence b  
Figure 3: Two isometric but not isomorphic spaces. Figure 2: Two isometric metric spaces. Distances between the nodes are given by the shortest path, and the weight of each edge is equal to 1.