# Fused Gromov-Wasserstein Distance for Structured Objects
## 2 Structured Objects as Distributions and Fused Gromov-Wasserstein Distance
### Background on OT Distances  
The Optimal Transport (OT) framework defines distances between probability measures that describe either the feature or the structure information of structured objects.  
**Wasserstein distance.** The classical OT theory aims at comparing probability measures \(\mu_{A}\in\mathcal{P}(\Omega),\
u_{B}\in\mathcal{P}(\Omega)\). In this context the quantity:  
\[d_{W,p}(\mu_{A},\
u_{B})=\left(\inf_{\pi\in\Pi(\mu_{A},\
u_{B})}\int\limits_{ \Omega\times\Omega}d(a,b)^{p}d\pi(a,b)\right)^{\frac{1}{p}} \tag{6}\]  
Figure 4: Two structured objects with isometric structures and identical features that are not strongly isomorphic. The color of the nodes represent the node feature and each edge represents a distance of 1 between the connected nodes.  
is usually called the \(p\)-Wasserstein distance (also known, for \(p=1\), as Earth Mover's distance [20] in the computer vision community) between distributions \(\mu_{A}\) and \(\
u_{B}\). It defines a distance on probability measures, especially \(d_{W,p}(\mu_{A},\
u_{B})=0\)_iff_\(\mu_{A}=\
u_{B}\). This distance also has a nice geometrical interpretation as it represents an optimal cost (_w.r.t._\(d\)) to move the measure \(\mu_{A}\) onto \(\
u_{B}\) with \(\pi(a,b)\) the amount of probability mass shifted from \(a\) to \(b\) (see Figure 5). To this extent, the Wasserstein distance quantifies how \"far\" \(\mu_{A}\) is from \(\
u_{B}\) by measuring how \"difficult\" it is to move all the mass from \(\mu_{A}\) onto \(\
u_{B}\). Optimal transport can deal with smooth and discrete measures and it has proved to be very useful for comparing distributions in a shared space, but with different (and even non-overlapping) supports.  
**Gromov-Wasserstein distance.** In order to compare measures whose support are not necessarily in the same ambient space [16; 17] define a new OT distance. By relaxing the classical Hausdorff distance [15; 17], authors build a distance over the space of all mm-spaces. For two compact mm-spaces \((X,d_{X},\mu_{X}\in\mathcal{P}(X))\) and \((Y,d_{Y},\
u_{Y}\in\mathcal{P}(Y))\), the Gromov-Wasserstein distance is defined as:  
\[d_{GW,p}(\mu_{X},\
u_{Y})=\left(\inf_{\pi\in\Pi(\mu_{X},\
u_{Y})}\int\limits_{ X\times Y\times X\times Y}L(x,y,x^{\prime},y^{\prime})^{p}d\pi(x,y)d\pi(x^{ \prime},y^{\prime})\right)^{\frac{1}{p}} \tag{7}\]  
where:  
\[L(x,y,x^{\prime},y^{\prime})=|d_{X}(x,x^{\prime})-d_{Y}(y,y^{\prime})|\]  
The Gromov-Wasserstein distance depends on the choice of the metrics \(d_{X}\) and \(d_{Y}\) and with some abuse of notation we denote the entire mm-space by its probability measure. When it is not clear from the context, we will specify using \(d_{GW,p}(d_{X},d_{Y},\mu_{X},\
u_{Y})\). The resulting coupling tends to associate pairs of points with similar distances within each pair (see Figure 6). The Gromov-Wasserstein distance allows for the comparison of measures over different ground spaces and defines a metric over the space of all mm-spaces quotiented by the isomoprhisms (see Definitions 4 and 5). More precisely, it vanishes if the two mm-spaces are isomorphic. This distance has been used in the context of relational data e.g., in shape comparison [17; 22], deep metric alignment [23], generative modelling [24] or to align single-cell multi-omics datasets [25].  
Figure 5: Example of a coupling between two discrete measures on the same ground space equipped with a distance \(d\) that will define the Wasserstein distance. (**Left**): the discrete measures on \(\Omega\). (**Right**): one possible coupling between these measures that conserves the mass. Image adapted from [21] [Figure 2.6].