# Fused Gromov-Wasserstein Distance for Structured Objects
## 5 Examples and Applications
### Graph Barycenter and Compression  
In this experiment, we use \(FGW\) to compute barycenters and approximations of toy graphs. In the first example, we generate graphs following either a circle or 8 symbol with 1D features following a sine and linear variation, respectively. For each example, the number of nodes is drawn randomly between 10 and 25, Gaussian noise is added to the features and a small noise is applied to the structure (some connections are randomly added). An example graph with no noise is provided for each class in the first column of Figure 13. One can see from there that the circle class has a feature varying smoothly (sine) along the graph, but the 8 has a sharp feature change at its center (so that low pass filtering would loose some information). Some examples of the generated graphs are provided in the 2 nd-to-7 th columns of Figure 13. We compute the \(FGW\) barycenter containing 10 samples while using the shortest path distance between the nodes as the structural information and the \(\ell_{2}\) distance \begin{table}
\begin{tabular}{l l l l l l} \hline \hline
**Vector Attributes** & **BZR** & **COX2** & **CUNEIFORM** & **ENZYMES** & **PROTEIN** & **SYNTHETIC** \\ \hline FGW sp & \(\mathbf{85.12\pm 4.15}^{*}\) & \(77.23\pm 4.86\) & \(\mathbf{76.67\pm 7.04}\) & \(71.00\pm 6.76\) & \(\mathbf{74.55\pm 2.74}\) & \(\mathbf{100.00\pm 0.00}\) \\ \hline HOPPERK & \(84.15\pm 5.26\) & \(\mathbf{79.57\pm 3.46}\) & \(32.59\pm 8.73\) & \(45.33\pm 4.00\) & \(71.96\pm 3.22\) & \(90.67\pm 4.67\) \\ PROPAK & \(79.51\pm 5.02\) & \(77.66\pm 3.95\) & \(12.59\pm 6.67\) & \(\mathbf{71.67\pm 5.63}^{*}\) & \(61.34\pm 4.38\) & \(64.67\pm 6.70\) \\ \hline PSCN k = 10 & \(80.00\pm 4.47\) & \(71.70\pm 3.57\) & \(25.19\pm 7.73\) & \(26.67\pm 4.77\) & \(67.95\pm 11.28\) & \(\mathbf{100.00\pm 0.00}\) \\ PSCN k = 5 & \(82.20\pm 4.23\) & \(71.91\pm 3.40\) & \(24.81\pm 7.23\) & \(27.33\pm 4.16\) & \(71.79\pm 3.39\) & \(\mathbf{100.00\pm 0.00}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Average classification accuracy on the graph datasets with vector attributes. \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Discrete Attr.** & **MUTAG** & **NCI1** & **PTC-MR** \\ \hline FGW raw sp & \(83.26\pm 10.30\) & \(72.82\pm 1.46\) & \(55.71\pm 6.74\) \\ FGW wl h = 2 sp & \(86.42\pm 7.81\) & \(85.82\pm 1.16\) & \(63.20\pm 7.68\) \\ FGW wl h = 4 sp & \(\mathbf{88.42\pm 5.67}\) & \(\mathbf{86.42\pm 1.63}\) & \(\mathbf{65.31\pm 7.90}\) \\ \hline GK k = 3 & \(82.42\pm 8.40\) & \(60.78\pm 2.48\) & \(56.46\pm 8.03\) \\ RWK & \(79.47\pm 8.17\) & \(58.63\pm 2.44\) & \(55.09\pm 7.34\) \\ SPK & \(82.95\pm 8.19\) & \(74.26\pm 1.53\) & \(60.05\pm 7.39\) \\ WLK & \(86.21\pm 8.48\) & \(85.77\pm 1.07\) & \(62.86\pm 7.23\) \\ WLK h=2 & \(86.21\pm 8.15\) & \(81.85\pm 2.28\) & \(61.60\pm 8.14\) \\ WLK h = 4 & \(83.68\pm 9.13\) & \(85.13\pm 1.61\) & \(62.17\pm 7.80\) \\ \hline PSCN k = 10 & \(83.47\pm 10.26\) & \(70.65\pm 2.58\) & \(58.34\pm 7.71\) \\ PSCN k = 5 & \(83.05\pm 10.80\) & \(69.85\pm 1.79\) & \(55.37\pm 8.28\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Average classification accuracy on the graph datasets with discrete attributes. \begin{table}
\begin{tabular}{l l l} \hline \hline
**Without Attribute** & **IMDB-B** & **IMDB-M** \\ \hline GW sp & \(\mathbf{63.80\pm 3.49}\) & \(\mathbf{48.00\pm 3.22}\) \\ \hline GK k = 3 & \(56.00\pm 3.61\) & \(41.13\pm 4.68\) \\ SPK & \(55.80\pm 2.93\) & \(38.93\pm 5.12\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Average classification accuracy on the graph datasets with no attributes. for the features. We recover an adjacency matrix by thresholding the similarity matrix \(C\) given by the barycenter. The threshold is tuned, so as to minimize the Frobenius norm between the original \(C\) matrix and the shortest path matrix constructed after thresholding \(C\). Resulting barycenters are showed in Figure 13 for \(n=15\) and \(n=7\) nodes. First, one can see that the barycenters are denoised in both the feature space and structure space.