## 5 Tests and Results
### Computational Results  
In Figures 1 and 2 we show the accuracy on the test set and the number of resulting alphabet symbols, respectively, with Figures 3 and 4 showing their respective detailed breakdown. For the sake of completeness, in Figure 5, we show also the size of the alphabet before the second genetic optimization stage. Due to the stochastic nature of the model synthesis procedure, the results shown below have been obtained by averaging across 10 different runs of the algorithm. Each figure shows a heatmap whose color scale has been normalized by rows (i.e., independently for each dataset) and ranges from white (lower values) towards blue (higher values). By considering Figure 1, it is possible to observe that (regardless of the topology) a stratified approach leads to generally better performance (i.e., higher accuracy on the test set). The breakdown of the shifts in accuracy is shown in Figure 3: for both path-based and clique-based granulators, the majority of the differences between stratified and non-stratified approaches are positive. For path-based extractors, the only two datasets for which the opposite is true are AIDS and ENZYMES. Conversely, for \begin{table}
\begin{tabular}{c c c} \hline \hline
**Dataset** & **Path-Based** & **Clique-Based** \\ \hline AIDS & \(10\%\times N_{P}\) & \(40\%\times N_{C}\) \\  & with \(N_{P}\) = 27,589 & with \(N_{C}=3994\) \\ GREC & \(10\%\times N_{P}\) & \(40\%\times N_{C}\) \\  & with \(N_{P}\) = 21,009 & with \(N_{C}=3367\) \\ Letter-L & \(10\%\times N_{P}\) & \(40\%\times N_{C}\) \\  & with \(N_{P}\) = 7975 & with \(N_{C}=2391\) \\ Letter-M & \(10\%\times N_{P}\) & \(40\%\times N_{C}\) \\  & with \(N_{P}\) = 8217 & with \(N_{C}=2412\) \\ Letter-H & \(10\%\times N_{P}\) & \(40\%\times N_{C}\) \\  & with \(N_{P}\) = 12,063 & with \(N_{C}=2500\) \\ Mutagenicity & \(10\%\times N_{P}\) & \(40\%\times N_{C}\) \\  & with \(N_{P}\) = 449,519 & with \(N_{C}=49,294\) \\ MUTAG & \(10\%\times N_{P}\) & \(40\%\times N_{C}\) \\  & with \(N_{P}\) = 15,530 & with \(N_{C}=1897\) \\ DD & \(1\%\times N_{P}\) & \(10\%\times N_{C}\) \\  & with \(N_{P}\) = 22,024,059 & with \(N_{C}=168,781\) \\ NCI1 & \(5\%\times N_{P}\) & \(20\%\times N_{C}\) \\  & with \(N_{P}\) = 521,560 & with \(N_{C}=66,522\) \\ ENZYMES & \(10\%\times N_{P}\) & \(40\%\times N_{C}\) \\  & with \(N_{P}\) = 383,730 & with \(N_{C}=9897\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Size of \(W\) for path-based and clique-based Granulators. Here, \(N_{P}\) and \(N_{C}\) refer to the number of paths of maximum order \(o=5\) and the total number of maximal cliques that can be drawn from the training set, respectively. ENZYMES emerges as the only dataset showing the same phenomenon. By looking at the magnitude of the accuracy boost, cliques seem to benefit more from a stratified granulation approach: indeed, the vast majority of the boosts in terms of accuracy are upper-bounded by 10%, whereas the majority of path-based granulators reach at most a 3% accuracy boost with respect to the non-stratified counterpart. By looking at Figure 2, we can observe the number of symbols (i.e., the size of the alphabet) after the second genetic-driven feature selection stage. In principle, a clique-based approach is likely to yield a smaller alphabet: this is due to the fact that an \(n\)-vertex graph can have at most \(\mathcal{O}(3^{n/3})\) cliques, whereas the number of paths can grow as \(\mathcal{O}(n! )\) in the worst case, so the set of prospective information granules (even without any subsampling) is smaller. Conversely to the accuracy case, a stratified approach does not necessarily yield benefits. As can be seen in the breakdown (Figure 4), as paths are concerned, the stratification yields a smaller alphabet for 4 datasets out of 10. As cliques are concerned, the same phenomenon happens for 3 out of 10 datasets.