# Fused Gromov-Wasserstein Distance for Structured Objects
## 5 Examples and Applications
### Illustrations of \(Fgw\)  
In this section, we present several applications of \(FGW\) as a distance between structured objects and provide an interpretation of the OT matrix. **Example with one-dimensional (1D) features and structure spaces. ** Figure 10 illustrates the differences between Wasserstein, Gromov-Wasserstein, and Fused Gromov-Wasserstein couplings \(\pi^{*}\). In this example, both the feature and structure space are one-dimensional (Figure 10 left). The feature space (vertical axis) denotes two clusters among the elements of both objects illustrated in the OT matrix \(M_{AB}\), the structure space (horizontal axis) denotes a noisy temporal sequence along the indexes illustrated in the matrices \(C_{1}\) and \(C_{2}\) (Figure 10 center). Wasserstein respects the clustering, but forgets the temporal structure, Gromov-Wasserstein respects the structure, but do not take the clustering into account. Only \(FGW\) retrieves a transport matrix respecting both feature and structure. **Example on two simple images. **We extract a \(28\times 28\) image from the MNIST dataset and generate a second one through translation or mirroring of the digit in the original image. We use pixel gray levels of the pixels as the features, and the structure is defined as the city-block distance on the pixel coordinate grid. We use equal weights for all of the pixels in the image. Figure 11 shows the different couplings obtained when only considering either the features, the structure only or both information. \(FGW\) aligns the pixels of the digits, recovering the correct order of the pixels, while both Wassertein and Gromov-Wasserstein distances fail at providing a meaningful transportation map. Note that in the Wasserstein and Gromov-Wasserstein case, the distances are equal to 0, whereas \(FGW\) manages to spot that the two images are different. Additionally, note that, in the \(FGW\) sense, the original digit and its mirrored version are also equivalent as there exists an isometry between their structure spaces, making \(FGW\) invariant to rotations or flips in the structure space in this case. **Example on time series data. ** One of the main assets of \(FGW\) is that it can be used on a wide class of objects and time series are one more example of this. We consider here 25 monodimensional time series composed of two humps in \([0,1]\) with random uniform height between 0 and 1. The signals are distributed according to two classes translated from each other with a fixed gap. The \(FGW\) distance is computed by considering \(d\) as the euclidean distance between the features of the signals (here the value of the signal in each point) and \(d_{X}\) and \(d_{Y}\) as the euclidean distance between timestamps. A two-dimensional (2D) embedding is computed from a \(FGW\) distance matrix between a number of examples in this dataset with multidimensional scaling (MDS) [43] in Figure 12 (top). One can clearly see that the representation with a reasonable \(\alpha\) value in the center is the most discriminant one. This can be better understood by looking as the OT matrices between the classes. Figure 12 (bottom) illustrates the behavior of \(FGW\) on one pair of examples when going from Wasserstein to Gromov-Wasserstein. The black line depicts the matching provided by the transport matrix and one can clearly see that while Wasserstein on the left assigns samples completely independently to their temporal position, the Gromov-Wasserstein on the right tends to align perfectly the samples (note that it could have reversed exactly the alignment with the same loss), but discards the values in the signal. Only the true \(FGW\) in the center finds a transport matrix that both respects the time sequences and aligns similar values in the signals. Figure 10: Illustration of the difference between \(W\), \(GW\), and \(FGW\) couplings. (**left**) Empirical distributions \(\mu\) with 20 samples and \(\
u\) with 30 samples which color is proportional to their index.