## 6 Conclusions  
In this work, we performed a two-fold investigation of clustering-based strategies for the automatic synthesis of information granules in the graph domain for solving (graph) classification problems on labeled graphs. Our investigation jointly considers the subgraph topology in order to extract granules of information (i.e., cliques vs. paths extracted via a random walk) and the possibility of performing a class-aware, stratified clustering over the set of candidate information granules to build class-specific alphabets of symbols. \begin{table}
\begin{tabular}{l c c c c c c c c c c} \hline \hline
**Technique** & **AIDS** & **GREC** & **Letter-L** & **Letter-M** & **Letter-H** & **Mutagenicity** & **MUTAG** & **DD** & **NCI** & **ENZYMES** & **Reference** \\ \hline \hline Bipartite Graph Matching + \(K\)-NN & - & 86.3 & 91.1 & 77.6 & 61.6 & - & - & - & - & - & [67] \\ Lipschitz Embedding + SVM & 98.3 & 96.8 & 99.3 & 95.9 & 92.5 & 74.9 & - & - & - & - & [72] \\ Graph Edit Distance + \(K\)-NN & 97.3 & 95.5 & 99.6 & 94 & 90 & 71.5 & - & - & - & [49] \\ Graph of Words + \(K\)-NN & - & 97.5 & 98.8 & - & - & - & - & - & - & [73] \\ Graph of Words + \(K\)PCA + \(K\)-NN & - & 97.1 & 97.6 & - & - & - & - & - & - & - & [73] \\ Graph of Words + \(L\)CA + \(K\)-NN & - & 95.8 & 92.8 & - & - & - & - & - & - & - & [73] \\ Topological embedding & 99.4 & - & - & - & - & 77.2 & - & - & - & - & [68,80] \\ FMGC & 99.0 & - & - & - & - & 76.5 & - & - & - & - & [68,81] \\ Attribute Statistics & 99.6 & - & - & - & - & 76.5 & - & - & - & - & [68,82] \\ Hypergraph Embedding + SVM & 99.3 & - & - & - & - & 77.0 & 84.6 & - & 72.7 & 43.1 & [74] \\ OOD ST\({}_{2}^{*}\)Kernel & 82.0* & - & - & - & - & - & - & 84.97* & - & [69] \\ OOD ST\({}_{2}^{*}\)\({}^{*}\)\({}^{*}\) & - & - & - & - & - & - & - & 84.57* & - & [69] \\ Laplacian kernel & 92.6 & - & - & - & - & 70.2 & - & - & - & - & [68,83] \\ Treelet kernel & 99.1 & - & - & - & - & 77.1 & - & - & - & - & [68,84] \\ Treelet kernel with MKL & 99.7 & - & - & - & - & 77.6 & - & - & - & - & [68,85] \\ WJK Hypergraph kernel + SVM & 99.5* & - & - & - & - & 82* & 90.9* & 78.9* & 70.7* & - & [70] \\ CGMM + linear SVM & 84.16* & - & - & - & - & 91.18* & - & - & - & [76] \\ G-L-Perceptron & - & 70 & 95 & 64 & 70 & - & - & - & - & - & [77] \\ G-M-Perceptron & - & 75 & 98 & 87 & 81 & - & - & - & - & - & [77] \\ C-1 NN & - & - & 96 & 93 & 84 & - & - & - & - & - & [77] \\ C-M-1 NN & - & - & 98 & 81 & 71 & - & - & - & - & - & [77] \\ EigenGCN-1 & - & - & - & - & - & 80.1 & - & 77.5 & 76.0 & 65.0 & [75] \\ EigenGCN-2 & - & - & - & - & 78.9 & - & 77.0 & 76.7 & 64.5 & [75] \\ EigenGCN-3 & - & - & - & - & - & 79.5 & - & 78.6 & 77.0 & 64.5 & [75] \\ GCN with logical descriptors & 96.93 & 96.64 & 85.27 & 79.1 & - & - & - & - & - & [78] \\ MPNN & - & 89.5 & 91.3 & 81.2 & 64.24 & - & - & - & - & [79] \\ MPNN (no set2 set) & - & 92.98 & 94.8 & 86.1 & 75.7 & - & - & - & - & - & [79] \\ Deep Graphlet Kernel & - & - & - & - & - & 82.6* & - & 62.48* & 27.08* & [71] \\ GRALG Paths & 99.09 & 79.13 & 96.80 & 91.11 & 88.31 & 68.14 & 83.69 & 73.67 & 73.02 & 30.44 & This work \\ GRALG Stratified Paths & 99.02 & 82.15 & 97.20 & 92.09 & 90.00 & 69.98 & 85.82 & 74.80 & 73.41 & 27.33 & This work \\ GRALG Cliques & 97.93 & 90.3 & 96.31 & 58.36 & 74.4 & 72.84 & 88.65 & 76.38 & 66.86 & 34.89 & This work \\ GRALG Stratified Cliques & 99.22 & 92.74 & 97.24 & 80.22 & 77.82 & 72.7 & 90.07 & 76.95 & 67.61 & 33.78 & This work \\ \hline \hline \end{tabular}  
* Results refers to cross-validation rather than a separate test set.  
\end{table} 
Table 3: Comparison against state-of-the-art graph classification system in terms of classification accuracy. Figure 5: Size of the alphabet before feature selection. These strategies are tested within the GRALG framework, where the set of automatically extracted granules of information serve as pivotal subgraphs for building and embedding space. The soundness of the latter is addressed by a statistical classifier working on the embedding space.