# Fused Gromov-Wasserstein Distance for Structured Objects
## 5 Examples and Applications
### Graph-Structured Data Classification
In the result, Tables 1-3, we write in bold the best score for each dataset and we add a (*) when the best score does not yield to a significative improvement (based on a [PERSON] signed rank test on the test scores) compared to the second best one. Note that, because of their small sizes, we repeat the experiments 50 times for MUTAG and PTC-MR datasets. For all methods using SVM, we cross validate the parameter \(C\in\{10^{-7},10^{-6},\ldots,10^{7}\}\). The range of the WL parameter h is \(\{0,1\ldots,10\}\), and we also compute this kernel with h fixed at \(2,4\). The decay factor \(\lambda\) for RWK \(\{10^{-6},10^{-5}\ldots,10^{-2}\}\), for the GK kernel we set the graphlet size \(\kappa=3\) and cross validate the precision level \(e\) and the confidence \(\delta\) as in the original paper [56]. The \(t_{\text{max}}\) parameter for PROPAK is chosen within \(\{1,3,5,8,10,15,20\}\). For PSCN, we choose the normalized betweenness centrality as labeling procedure and cross validate the batch size in \(\{10,15,\ldots,35\}\) and number of epochs in \(\{10,20,\ldots,100\}\). Finally, for \(FGW\), \(\gamma\) is cross validated within \(\{2^{-10},2^{-9},\ldots,2^{10}\}\) and \(\alpha\) is cross validated _via_ a logspace search in \([0,0.5]\) and symmetrically \([0.5,1]\) (15 values are drawn). **Vector attributed graphs. ** The average accuracies reported in Table 1 show that FGW is a clear state-of-the-art method and performs best on four out of six datasets with performances in the error bars of the best methods on the other two datasets. The results for CUNEIFORM are significantly below those from the original paper [46], which can be explained by the fact that the method in this paper uses a graph convolutional approach specially designed for this dataset and that experiment settings are different. In comparison, the other competitive methods are less consistent, as they exhibit some good performances on some datasets only. **Discrete labeled graphs. ** We first note in Table 2 that \(FGW\) using WL attributes outperforms all competitive methods, including \(FGW\) with raw features. Indeed, the WL attributes allow for more finely encoding the neighborhood of the vertices by stacking their attributes, whereas FGW with raw features only consider the shortest path distance between vertices, not their sequence of labels. This result calls for using meaningful feature and/or structure matrices in the FGW definition, which can be dataset-dependant, in order to enhance the performances. We also note that \(FGW\) with WL attributes outperforms the WL kernel method, highlighting the benefit of an optimal transport-based distance over a kernel-based similarity. Surprisingly, the results of PSCN are significantly lower than those from the original paper. We believe that it comes from the difference between the fold assignment for training and testing, which suggests that PSCN is difficult to tune. **Non-attributed graphs. ** The particular case of the GW distance for graph classification is also illustrated on social datasets, which contain no labels on the vertices. Note that no artificial features were added to these datasets. Accuracies reported in Table 3 show that it greatly outperforms the SPK and GK graph kernel methods. This is, to the best of our knowledge, the first application of the Gromov-Wasserstein distance for social graph classification and it highlights the fact that \(GW\) is a good metric for comparing the graph structures. **Comparison between \(FGW\), \(W\) and \(GW\)**. During the validation step, the optimal value of \(\alpha\) was consistently selected inside the \(]0,1[\) interval, i.e., excluding 0 and 1, suggesting that both structure and feature information are necessary.