###### Abstract
Second, data clustering is an inverse problem (i.e., when we want to calculate, starting from a finite set of data, the causal factors that produced them), which are known to be ill-posed. The lack of notion of what is a valid cluster and, in consequence, what is an appropriate clustering algorithm to detect such clusters depends on the application at hand [18], leading to the development of several families of clustering algorithms available in the current literature [19]. The interested reader can refer to [16,20] for detailed surveys on clustering algorithms. Here, we briefly discuss two families of clustering algorithms widely employed in a Granular Computing setting: hierarchical and partitional clustering. Hierarchical clustering algorithms aim at building a dendrogram that represents the dependency among clusters; in particular, hierarchical clustering algorithms can be further divided in two main families:  
* Agglomerative clustering algorithms, which work in a bottom-to-top fashion by starting with each data point forming its own cluster and then merging clusters until all data points belong to the same cluster;
* Divisive clustering algorithms, which work in a top-to-bottom fashion by starting with a single cluster embracing the entire dataset and then iteratively splitting the clusters until each data point forms its own cluster. Conversely, partitional clustering algorithms aim at assigning each data object to one and only one cluster, where the number of clusters can be set a priori. In the latter case, \(k\)-means stems as the flagship of partitional algorithms [21], alongside its extensions towards non-Euclidean dissimilarity measures [22; 23] and fuzzy extensions [24]. In the former case (i.e., hierarchical clustering), the algorithm natively returns a multi-scale overview of the dataset (i.e., the dendrogram linking its clusters at different scales). In the latter case (i.e., partitional clustering), one can let fewer or more clusters emerge, leading to partitions having different sizes. The possibility of analyzing the data (hence, letting information granules to emerge) at different levels of abstraction is at the very heart of the Granular Computing paradigm, which is why both approaches are commonly used in a Granular Computing approach. Recently, the Granular Computing paradigm has been employed for the synthesis of pattern recognition systems, as well as in structured domains such as graphs, sequences and images [25; 26]. The rationale behind these pattern recognition systems is to automatically extract recurrent and/or meaningful substructures (i.e., subgraphs, subsequences, portions of images) suitable to be considered as granules of information. On the top of these pivotal elements, it is possible to build an embedding space in such a way that the pattern recognition problem is cast from the structured domain towards the Euclidean space. The latter, being a metric space, allows to comfortably use one of the many statistical classifiers currently available in the pattern recognition and machine learning literature [27]. In this work, we exploit clustering-based approaches for the automatic synthesis of information granules in the context of graph classification. The information granules reflect pivotal subgraphs extracted from the training data endowed with high discriminative power. On the top of these information granules, we perform an embedding procedure thanks to the symbolic histograms approach. In particular, we review and compare two different candidate topologies for the synthesis of granules of information (paths and cliques) and we compare two additional strategies for their synthesis: a stratified approach, where the ground-truth labels of the classification problem play an important role in the information granules synthesis, and a non-stratified approach, where the ground-truth labels are completely discarded in the process.