## 4 Model Synthesis and Testing  
In this section, we explain in detail how the above-described four blocks (Extractor, Granulator, Embedder and Classifier) co-operate in order to synthesize the classification model and subsequent testing of its final performance on the test set. Since there are several hyper-parameters involved in the model synthesis, notably:  
* The clustering algorithm parameters for the Granulator block;
* The weights for the nBMF dissimilarity measure (used in both Granulator and Embedder). We employ a differential evolution algorithm [47] for an automatic tuning of these parameters, hence driving the overall model synthesis. The model synthesis starts by triggering the Extractor block, which yields the set of candidate information granules \(\mathcal{B}\) by properly processing the training graphs. As \(\mathcal{B}\) is returned, the differential evolution optimization scheme can take place. The search space for the optimization procedure is defined as:  
\[\left[ \begin{array}{cccccccc}Q&\eta&\tau_{F}&w_{\text{sub}}^{\text{node}}&w_ {\text{ins}}^{\text{node}}&w_{\text{del}}^{\text{node}}&w_{\text{sub}}^{ \text{edge}}&w_{\text{ins}}^{\text{edge}}&w_{\text{del}}^{\text{edge}}&\Pi_{ \text{edge}}&\Pi_{\text{node}}\end{array} \right] \tag{7}\]  
Each individual from the evolving population forwards \(\mathcal{B}\) to the Granulator block. As anticipated in Section 2, the Granulator runs a BSAS-based ensemble driven by a suitable dissimilarity measure \(d(\cdot,\cdot)\), a maximum number of allowed clusters \(Q\) and a threshold value \(\theta\). Recall that the dissimilarity measure between any two patterns is evaluated by a parametric nBMF dissimilarity measure that, in turn, depends on:  
* Six real-valued weights that account for the importance of each atomic transformation (insertion, deletion and substitution) on nodes and edges: \(w_{\text{sub}}^{\text{node}}\), \(w_{\text{ins}}^{\text{node}}\), \(w_{\text{del}}^{\text{node}}\), \(w_{\text{sub}}^{\text{edge}}\), \(w_{\text{ins}}^{\text{edge}}\), \(w_{\text{del}}^{\text{edge}}\);* A set \(\Pi_{\text{edge}}\) of parameters, if needed, in order to drive the dissimilarity measure between edges;
* A set \(\Pi_{\text{node}}\) of parameters, if needed, in order to drive the dissimilarity measure between nodes. At the end of the Granulation stage, the alphabet \(\mathcal{A}\) is available for feeding the Embedder block, which yields the embedded version of \(\mathcal{S}_{\text{tr}}\) and \(\mathcal{S}_{\text{val}}\), namely \(\mathbf{H}_{\text{tr}}\) and \(\mathbf{H}_{\text{val}}\). These two instance matrices are finally fed to the Classifier block, which trains a \(K\)-NN decision rule on \(\mathbf{H}_{\text{tr}}\) and predicts the ground-truth labels on \(\mathbf{H}_{\text{val}}\). Each individual is evaluated by means of a fitness function (to be minimized) formalized as follows:  
\[f=\alpha\cdot\pi+(1-\alpha)\cdot\sigma \tag{8}\]  
where \(\pi\) is an error term and \(\sigma\) is a penalty term. Specifically:  
\[\pi=1-\frac{1}{p}\sum_{i=1}^{p}\text{rec}(i) \tag{9}\]  
where \(\text{rec}(i)\) is the recall of class \(i\). Hence, Equation (9) reads as the complement of the balanced accuracy [48]. On the other hand, \(\sigma\) is a penalty term defined as:  
\[\sigma=\frac{|\mathcal{A}|}{|\mathcal{B}|} \tag{10}\]  
in order to penalize large alphabets and foster the optimization towards smaller alphabets. At the end of the optimization stage, the best individual is retained, along with the best alphabet \(\mathcal{A}^{\star}\) synthesized with its genetic code and the two instance matrices \(\mathbf{H}_{\text{tr}}^{\star}\) and \(\mathbf{H}_{\text{val}}^{\star}\) embedded against \(\mathcal{A}^{\star}\). The choice of the trade-off parameter \(\alpha\in[0,1]\) in Equation (8) that weights performance against dimensionality can hardly be set a priori. In order to overcome this problem, a second lightweight optimization stage can be employed in order to further reduce the size of the alphabet.