# Fused Gromov-Wasserstein Distance for Structured Objects
## 5 Examples and Applications
### Graph-Structured Data Classification  
In this section, we adress the question of training a classifier for graph data and evaluate the FGW distance used in a kernel with SVM. **Learning problem and datasets. ** We consider 12 widely used benchmark datasets divided into 3 groups. BZR, COX2 [44], PROTEINS, ENZYMES [45], CUNEIFORM [46] and SYNTHETIC [47] are vector attributed graphs. MUTAG [48], PTC-MR [49], and NCI1 [50] contain graphs with discrete attributes derived from small molecules. IMDB-B, IMDB-M [51] contain unlabeled graphs derived from social networks. All of the datasets are available in [52]. **Experimental setup. ** Regarding the feature distance matrix \(M_{AB}\) between node features, when dealing with real valued vector attributed graphs, we consider the \(\ell_{2}\) distance between the labels of the vertices. In the case of graphs with discrete attributes, we consider two settings: in the first  
Figure 11: Couplings obtained when considering (**Top left**) the features only, where we have \(d^{\Omega}_{W,1}=0\) (**Top right**) the structure only, with \(d_{GW,1}=0\) (**Bottom left**, and **right**) both the features and the structure, with \(d^{\Omega}_{FGW,0,1,1,2}\). For readibility issues, only the couplings starting from non white pixels on the left picture are depicted. Figure 12: Behavior of trade-off parameter \(\alpha\) on a toy time series classification problem. \(\alpha\) is increasing from left (\(\alpha=0\): [PERSON] distance) to right (\(\alpha=1\): [PERSON]–Wasserstein distance). (**top row**) Two-dimensional (2D)-embedding is computed from the set of pairwise distances between samples with multidimensional scaling (MDS) (**bottom row**) illustration of couplings between two sample time series from opposite classes. one, we keep the original labels (denoted as raw); we also consider a Weisfeiler-Lehman labeling (denoted as wl) by concatenating the labels of the neighbors. A vector of size H is created by repeating this procedure h times [49; 53]. In both cases, we compute the feature distance matrix by using \(d(a_{i},b_{j})=\sum_{k=0}^{H}\delta(\tau(a_{i}^{k}),\tau(b_{j}^{k}))\) where \(\delta(x,y)=1\) if \(x\
eq y\) else \(\delta(x,y)=0\) and \(\tau(a_{i}^{k})\) denotes the concatenated label at iteration \(k\) (for \(k=0\) original labels are used). Regarding the structure distances \(C\), they are computed by considering a shortest path distance between the vertices. For the classification task, we run a SVM using the indefinite kernel matrix \(e^{-\gamma FGW}\), which is seen as a noisy observation of the true positive semidefinite kernel [54]. We compare classification accuracies with the following state-of-the-art graph kernel methods: (SPK) denotes the shortest path kernel [45], (RWK) the random walk kernel [55], (WLK) the Weisfeiler Lehman kernel [53], and (GK) the graphlet count kernel [56]. For real valued vector attributes, we consider the HOPPER kernel (HOPPERK) [47] and the propagation kernel (PROPAK) [57]. We build upon the GraKel library [58] to construct the kernels and C-SVM to perform the classification. We also compare \(FGW\) with the PATCHY-SAN framework for CNN on graphs (PSCN) [9] building on our own implementation of the method. To provide a comparison between the methods, most of the papers about graph classification usually perform a nested cross validation (using nine-fold for training, one for testing, and reporting the average accuracy of this experiment repeated 10 times), and report accuracies of the other methods taken from the original papers. However, these comparisons are not fair because of the high variance (on most datasets) _w.r.t._ the folds chosen for training and testing. This is why, in our experiments, the nested cross validation is performed on the same folds for training and testing for all methods [59].