## 3 Information Granulation Strategies
### Stratified Clique  
The two extractors and granulator strategies in Sections 3.1 and 3.2 populate the bucket \(\mathcal{B}\) uniformly at random. Such procedures present the following two potential drawbacks:  
* The information about the ground-truth labels (freely available in classification problems) is not exploited in the extraction and granulation stages;
* A uniformly at random selection can bias the contents of \(\mathcal{B}\), especially in case of unbalanced datasets; indeed, training graphs pertaining to the majority class have a higher change of being selected.  
In order to overcome both problems, we further proposed a stratified clique-based extractor and granulator [46]. The main objective of the stratified extractor is to build the bucket \(\mathcal{B}\) as a set-of-sets \(\mathcal{B}=\{\mathcal{B}^{(1)},\ldots,\mathcal{B}^{(p)}\}\), with \(p\) being the number of classes for the classification problem at hand, with the constraint that \(\mathcal{B}^{(i)}\) contains subgraphs drawn from the subset of training graphs belonging to the \(i\)th class only.  
The stratified clique-based extractor works as follows:  
1. For each ground-truth class \(i=1,\ldots,p\): 1. [label=()]
2. Let \(\mathcal{S}_{\text{tr}}^{(i)}\) be the subset of the training set containing only patterns belonging to class \(i\); 2. Calculate the (relative) frequency of the \(i\)th class as \(f_{i}=\left\lfloor\frac{|\mathcal{S}_{\text{tr}}^{(i)}|}{|\mathcal{S}_{\text{ tr}}|}+\frac{1}{2}\right\rfloor\), where the operator \(\left\lfloor x+\frac{1}{2}\right\rfloor\) rounds \(x\) to the nearest integer; 3. Evaluate \(W_{i}=\left\lfloor W\cdot f_{i}+\frac{1}{2}\right\rfloor\), namely the size of \(\mathcal{B}^{(i)}\); 4. Set \(\mathcal{B}^{(i)}=\emptyset\); 5. For each graph \(\mathcal{G}\in\mathcal{S}_{\text{tr}}^{(i)}\): 1. Evaluate \(\mathcal{C}\) as the maximal clique decomposition of \(\mathcal{G}\); 2. Update \(\mathcal{B}^{(i)}=\mathcal{B}^{(i)}\cup\mathcal{C}\). 2. If \(|\mathcal{B}^{(i)}|>W_{i}\), then replace \(\mathcal{B}^{(i)}\) with a uniform random selection of \(W_{i}\) of its own subgraphs.  
Due to the set-of-sets nature of the stratified bucket, the Granulator described in Section 3.1 and later employed in Section 3.2 loses its effectiveness. To overcome this problem, we let \(p\) different Granulators to run independently on each of the class-stratified buckets, yielding a class-related alphabet, say \(\mathcal{A}^{(i)}\) for the \(i\)th class, to be merged together later in order to form the overall alphabet \(\mathcal{A}\). Specifically:  
1. Start with \(\mathcal{A}=\emptyset\);
2. For each ground-truth class \(i=1,\ldots,p\): 1. [label=()] 2. Consider the sub-bucket \(\mathcal{B}^{(i)}\) containing subgraphs drawn from \(\mathcal{S}_{\text{tr}}^{(i)}\); 3. Run the Granulator (see Section 3.1) on \(\mathcal{B}^{(i)}\), yielding \(\mathcal{A}^{(i)}\); 4. \(\mathcal{A}=\mathcal{A}\cup\mathcal{A}^{(i)}\).  
The above procedure allows to have, in the final alphabet \(\mathcal{A}\), information granules extracted from all of the problem-related classes, which should yield not only a better characterization of the data by means of a thorough extraction of pivotal elements, but also a better separation of the classes themselves. Indeed, we advance the hypothesis that if a particular subgraph is pivotal to characterize a given problem-related class, then the number of occurrences in the symbolic histogram (cf. Equation (1)) will be higher if the graph to be embedded belongs to the very same class. This comes with the drawback of a potentially higher-dimensional alphabet: indeed, since the Granulator from Section 3.1 has to be repeated \(p\) times, the worst-case size of \(\mathcal{A}\) grows as \(\mathcal{O}(p\cdot m\cdot Q)\).