On Information Granulation via Data Clustering for Granular Computing-Based Pattern Recognition: A Graph Embedding Case Study

Abstract

Granular Computing is a powerful information processing paradigm, particularly useful for the synthesis of pattern recognition systems in structured domains (e.g., graphs or sequences). According to this paradigm, granules of information play the pivotal role of describing the underlying (possibly complex) process, starting from the available data. Under a pattern recognition viewpoint, granules of information can be exploited for the synthesis of semantically sound embedding spaces, where common supervised or unsupervised problems can be solved via standard machine learning algorithms. In this work, we show a comparison between different strategies for the automatic synthesis of information granules in the context of graph classification. These strategies mainly differ on the specific topology adopted for subgraphs considered as candidate information granules and the possibility of using or neglecting the ground-truth class labels in the granulation process. Computational results on 10 different open-access datasets show that by using a class-aware granulation, performances tend to improve (regardless of the information granules topology), counterbalanced by a possibly higher number of information granules.

1. Introduction

In the early 2000s, Granular Computing emerged as a novel information processing paradigm that exploits pivotal mathematical structures called granules of information to describe an underlying set of (likely complex) data, describing a (likely complex) process under analysis [1,2]. The concept of information granulation dates back to the mid-1990s, thanks to soft computing and fuzzy logic pioneer Lotfi Aliasker Zadeh. In their words:

Among the basic concepts which underlie human cognition there are three that stand out in importance. The three are: granulation, organization and causation.

L.A. Zadeh [3]

and

Informally, granulation of an object A results in a collection of granules of A, with a granule being a clump of objects (or points) which are drawn together by indistinguishability, similarity, proximity or functionality. In this sense, the granules of a human body are the head, neck, arms, chest, etc. In turn, the granules of a head are the forehead, cheeks, nose, ears, eyes, hair, etc. In general, granulation is hierarchical in nature. A familiar example is granulation of time into years, years in months, months into days and so on.

L.A. Zadeh [3]

This philosophical viewpoint behind the birth of Granular Computing as human-inspired information processing paradigm has been embraced by other well-known scholars, notably Ronald R. Yager. In their words:

Language, which is central to most human cognitive activities, is based on granularization. In addition human facilities for distinctions are limited. Being limited, at the very least by language and perhaps additionally by their ability to perceive, human beings have been developed a granular view of the world. Thus, we see that the objects with which humankind perceives, measures, conceptualizes and reasons are granular.

R.R. Yager and D. Filev [4]

As the 1990s marked the golden age of fuzzy logic and fuzzy-based pattern recognition, L.A. Zadeh further argues that information granules should be inherently fuzzy since most of human reason and concept formation are fuzzy rather than crisp [3,5].

Clearly, Granular Computing is not a set of computational pipelines and is not a set of algorithms; rather, it can be considered as a goal-driven umbrella that, according to Y.Y. Yao, in their ”Granular Computing manifesto” [6] should fulfill the following points:

• Be a truthful representation of the real world;
• Be consistent with human thinking and problem solving;
• Allow a simplification of the problem;
• Provide economic and low-cost solutions.

Thus, in the realm of Granular Computing, we can easily find techniques that have not been developed for Granular Computing but, nonetheless, they satisfy the above goals. Indeed, information granulation can be performed by a plethora of different strategies, notably fuzzy sets [3,7,8], rough sets [8,9,10], shadowed sets [11], interval analysis [12] and data clustering [13,14,15].

In a general sense, the aim of a clustering algorithm is to group a finite set of data into a finite number of groups in such a way that the elements within the same cluster are more similar with each other with respect to elements belonging to other clusters [16]. The vagueness of such definition is not by chance as data clustering is an ill-posed problem. There are two ways to confirm such statement. First, according to J. Hadamard [17], a problem is said to be well-posed if a unique solution exists and the solution’s behavior changes continuously with the initial conditions. Data clustering does not satisfy (at least) the first requirement. 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.

The remainder of the paper is structured as follows: in Section 2, we describe the four main building blocks of the GRALG framework (extraction and synthesis of granules of information, graph embedding and classification), which we exploit in order to perform our two-fold investigation. In Section 3, we discuss in detail four granulation strategies based on different combination of subgraph topologies (paths vs. cliques) and stratification (class-aware vs. no stratification). In Section 4, we detail how these building blocks co-operate in order to synthesize an optimized model for graph classification. In Section 5, we show the computational results obtained by the four combinations of topology and granulation and, finally, Section 6 concludes the paper.

2. High-Level Framework Description

The GRALG framework is composed of the following four main modules:

• Extractor, which is in charge of extracting, from the training set, a suitable set of candidate information granules;
• Granulator, which is in charge of building an alphabet of symbols starting from the candidate information granules provided by the Extractor block;
• Embedder, which is in charge of mapping a graph dataset towards the Euclidean space;
• Classifier, which is in charge of training and testing a suitable classification system in the Euclidean space spanned by the Embedder block.

2.1. Extractor and Granulator

Let P be an unknown, oriented and possibly complex process to be modeled, where the inputs are annotated graphs and where the output domain is a finite set of class labels. Furthermore, let $\mathcal{S}$ be an input-output sampling of P and let ${\mathcal{S}}_{\mathrm{tr}}$, ${\mathcal{S}}_{\mathrm{val}}$ and ${\mathcal{S}}_{\mathrm{ts}}$ be a split of $\mathcal{S}$ into training, validation and test sets, respectively. The split should be performed so that each subset should share the same statistics, in order to be considered as valid representation of the same process. Moreover, this split must satisfy the following partition properties:

• The union of the three sets yields the original set: ${\mathcal{S}}_{\mathrm{tr}}\cup {\mathcal{S}}_{\mathrm{val}}\cup {\mathcal{S}}_{\mathrm{ts}}=\mathcal{S}$;
• The intersection of any two distinct sets is empty: ${\mathcal{S}}_{\mathrm{tr}}\cap {\mathcal{S}}_{\mathrm{val}}={\mathcal{S}}_{\mathrm{tr}}\cap {\mathcal{S}}_{\mathrm{ts}}={\mathcal{S}}_{\mathrm{ts}}\cap {\mathcal{S}}_{\mathrm{val}}=\varnothing$.

The Extractor is a block that takes as input ${\mathcal{S}}_{\mathrm{tr}}$ and returns a bucket $\mathcal{B}$ of subgraphs drawn from graphs in ${\mathcal{S}}_{\mathrm{tr}}$.

Conversely, the Granulator block takes as input $\mathcal{B}$ and returns an alphabet of symbols $\mathcal{A}\subset \mathcal{B}$, namely suitable granules of information, by running a clustering algorithm over $\mathcal{B}$, possibly electing the representative elements of the clusters as granules of information [13,14,15,28]. In particular, the latter runs a Basic Sequential Algorithmic Scheme (BSAS) [29] clustering algorithm driven by the following parameters:

• Q, namely, the maximum number of allowed clusters;
• $\theta$, namely, the maximum radius for including a pattern into one of the already-discovered clusters;
• A dissimilarity measure $d(·,·)$ between any two patterns.

The clustering algorithm addresses the dissimilarity between patterns (i.e., graphs) thanks to a parametric Graph Edit Distance (GED) [30,31] dissimilarity measure called node Best Match First (nBMF). The interested reader is referred to ([32], Appendix A) for a full mathematical formulation of nBMF. At the end of the clustering procedure, each cluster is evaluated by means of a suitable quality index that jointly takes into account its cardinality (i.e., number of patterns) and compactness (i.e., average pattern-to-center distance) and only the centers of well-formed (i.e., compact and populated) clusters are admitted to be part of the alphabet.

Since the Extractor and the Granulator blocks are the main focus of this paper, the four variants we aim to investigate will be thoroughly described in Section 3.

2.2. Embedder

The Embedder block takes as input the alphabet as returned by the Granulator block and runs an embedding function in order to cast each graph (belonging to an input graph set, e.g., ${\mathcal{S}}_{\mathrm{tr}}$) towards the Euclidean space.

The mapping function yields the so-called symbolic histogram [33] by transforming each input graph $\mathcal{G}$ into an n-length feature vector of the form:

$$\mathbf{h}(\mathcal{A},\mathcal{G})=[\mathrm{occ}(s_1,\mathcal{G}),\dots ,\mathrm{occ}(s_n,\mathcal{G})]$$

(1)

where $\mathcal{A}=\{s_1,\dots ,s_n\}$ and $\mathrm{occ}:\mathcal{A}\times \mathcal{G}\to {\mathbb{N}}_0^{+}$ is the enumeration function that counts the number of times each symbol $s\in \mathcal{A}$ appears in $\mathcal{G}$.

The counting procedure operates as follows:

• The input graph $\mathcal{G}$ is decomposed into its constituent parts, yielding a decomposition ${\mathcal{G}}^{\prime }=\{g_1,\dots ,g_k\}$. For the sake of consistency with the Extractor and Granulator modules, in case of path-based subgraphs, the decomposition follows a Breadth First Search strategy, whereas in case of cliques-based granulation, the decomposition follows the maximal clique decomposition.
• For the i^th symbol in $\mathcal{A}$:

  (a)

  The pairwise dissimilarities between $s_i$ and all subgraphs in ${\mathcal{G}}^{\prime }$ are evaluated;

  (b)

  All dissimilarities below a threshold ${\zeta }_i$ are retained and considered as a ‘hit’;

  (c)

  The i^th entry in $\mathbf{h}$ is filled with the number of occurrences (i.e., the number of ‘hits’);

• Repeat step 2 for $i=1,\dots ,n$.

There are two important aspects in this procedure that need to be addressed. First, the threshold ${\zeta }_i$ for scoring a ’hit’ is defined as:

$${\zeta }_i=1.1·\Phi \left({\mathcal{K}}_i\right)$$

(2)

where ${\mathcal{K}}_i$ is the cluster whose representative element is $s_i$ and $\Phi (·)$ is a function that evaluates the compactness of the cluster (further details in Section 3). In this manner, the threshold scales in a symbol-aware fashion by accounting the size of its cluster.

Second, the pairwise dissimilarities between symbols and subgraphs is evaluated by means of the very same nBMF dissimilarity measure already used by the Granulator block.

2.3. Classifier

The Classifier block trains a classification system on the embedded version of ${\mathcal{S}}_{\mathrm{tr}}$, say ${\mathbf{H}}_{\mathrm{tr}}$, namely an $|{\mathcal{S}}_{\mathrm{tr}}|\times n$ instance matrix with patterns (i.e., graphs from ${\mathcal{S}}_{\mathrm{tr}}$) organized as rows.

In order to validate the behavior of the classifier, the Classifier block also needs the embedded version of ${\mathcal{S}}_{\mathrm{val}}$, say ${\mathbf{H}}_{\mathrm{val}}$. The ability of the classification system, previously trained on ${\mathbf{H}}_{\mathrm{tr}}$, in predicting the ground-truth labels of ${\mathbf{H}}_{\mathrm{val}}$ dictates the performance of the Classifier.

In this work, we use a K-Nearest Neighbors (K-NN) decision rule [34] with $K=5$ as the classification system.

3. Information Granulation Strategies

3.1. Random Walk

The random walk extractor, proposed in [32], takes as input a bucket $\mathcal{B}$ of candidate information granules extracted via a plain random walk on the graphs belonging to the training set.

In a plain random walk [35,36], the next-hop $u\in \mathcal{V}$ is chosen uniformly at random among the neighbors of the current node $v\in \mathcal{V}$. Formally, the probability of moving from v to u is:

$$p_{v\to u}=\left\{\begin{array}{cc}\frac{1}{\mathrm{deg}\left(v\right)},\hfill & \mathrm{if}u\in \mathcal{N}\left(v\right)\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

(3)

where $\mathcal{N}\left(v\right)$ is the neighborhood of node v and $\mathrm{deg}\left(v\right)$ is its degree, i.e., $\mathrm{deg}\left(v\right)=\left|\mathcal{N}\right(v\left)\right|$.

Populating the bucket $\mathcal{B}$ relies on two important parameters:

• W, the user-defined number of subgraphs in $\mathcal{B}$, i.e., $W=\left|\mathcal{B}\right|$;
• o, the user-defined maximum number of nodes for subgraphs in $\mathcal{B}$.

and it works as follows:

• Start with $\mathcal{B}=\varnothing$;
• Let $W^{\prime }=\frac{W}{o}$ be the number of subgraphs to be extracted for each of the candidate subgraph orders;
• For $l=1,\dots ,o$:

  (a)

  Let ${\mathcal{B}}^{\left(l\right)}=\varnothing$ be a temporary bucket containing only subgraphs of order l;

  (b)

  Until $|{\mathcal{B}}^{\left(l\right)}|$ equals $W^{\prime }$:

  i.

  Extract uniformly at random a graph $\mathcal{G}$ from the training set;

  ii.

  Extract uniformly at random a node v from $\mathcal{G}$;

  iii.

  Start a simple random walk of length l from node v;

  iv.

  The subgraph emerged from the random walk is added to ${\mathcal{B}}^{\left(l\right)}$;

  (c)

  $\mathcal{B}=\mathcal{B}\cup {\mathcal{B}}^{\left(l\right)}$;

The so-collected bucket $\mathcal{B}$ is the main input to the Granulator module.

As anticipated in Section 2, the Granulator block runs the BSAS clustering algorithm on $\mathcal{B}$ in order to extract suitable information granules, properly collected in the alphabet $\mathcal{A}$. Given a set of m candidate values for $\theta$, i.e., $\{{\theta }_1,\dots ,{\theta }_m\}$, the Granulator block runs m instances of BSAS, each with a different value for $\theta$. Recalling that $\theta$ identifies the radius of inclusion, exploring different $\theta$ values allows us to explore $\mathcal{B}$ at different levels of resolutions, which, in turn, will yield granules of information at different levels of granularity [37,38,39,40]. Recalling that each instance of BSAS is bounded by a maximum number of clusters Q, the Granulation block yields at most $\mathcal{O}(Q·m)$ clusters in the worst case. Each cluster returned by the clustering ensemble, regardless of the $\theta$ value that generated it, undergoes a cluster quality evaluation in order to address whether that cluster is suitable for being elected as granule of information. Specifically, for any cluster $\mathcal{K}$, we define a cluster quality index $F\left(\mathcal{K}\right)$ that reads as:

$$F\left(\mathcal{K}\right)=\eta ·\Phi \left(\mathcal{K}\right)+(1-\eta )·\Psi \left(\mathcal{K}\right)$$

(4)

namely, as a linear convex combination between the compactness of the cluster $\Phi \left(\mathcal{K}\right)$ and its cardinality $\Psi \left(\mathcal{K}\right)$ weighted by a trade-off parameter $\eta \in [0,1]$. In turn, the compactness of the cluster is defined as the average pattern-to-center distance:

$$\Phi \left(\mathcal{K}\right)=\frac{1}{\left|\mathcal{K}\right|-1}\sum _{i}d(g^{\star },g_i)$$

(5)

where $g_i\in \mathcal{K}$ is the ith pattern of cluster $\mathcal{K}$ and $g^{\star }$ is the representative element of the cluster. Since the Granulator deals with non-geometric entities (i.e., graphs), we consider the medoid of the cluster as its representative [41]. Finally, the cardinality of the cluster is defined as the relative size of the cluster $\mathcal{K}$ with respect to the overall number of candidate information granules:

$$\Psi \left(\mathcal{K}\right)=1-\frac{\left|\mathcal{K}\right|}{\left|\mathcal{B}\right|}$$

(6)

Since both $\Phi \left(\mathcal{K}\right)$ and $\Psi \left(\mathcal{K}\right)$ are negative-oriented, a cluster is considered for being part of the alphabet $\mathcal{A}$ if and only if its quality index $F\left(\mathcal{K}\right)$ is below a threshold ${\tau }_F\in [0,1]$. The medoids whose clusters satisfying such condition compose the alphabet of symbols $\mathcal{A}$.

3.2. Clique

The clique extractor aims at investigating a particular subgraph topology: the clique, namely an induced subgraph that is complete [42,43].

In this scenario, the bucket $\mathcal{B}$ will be filled with a subset of the cliques extracted from the graphs belonging to the training set. The end-user is still required to specify W, as for Section 3.1, yet the maximal order parameter o is meaningless as cliques are concerned since the formation (and the size) of a clique is strictly topology-dependent rather than user-defined.

The clique extractor works as follows:

• Start with $\mathcal{B}=\varnothing$;
• For each graph $\mathcal{G}$ from the training set:

  (a)

  Evaluate $\mathcal{C}$ as the maximal clique decomposition of $\mathcal{G}$. The maximal clique decomposition of a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ can be evaluated thanks to the Bron–Kerbosh algorithm [44] with a worst-case complexity of $\mathcal{O}\left(3^{\left|\mathcal{V}\right|/3}\right)$ [45];

  (b)

  $\mathcal{B}=\mathcal{B}\cup \mathcal{C}$;

• Let ${\mathcal{B}}^{\prime }$ be a set of W subgraphs selected uniformly at random from $\mathcal{B}$;
• $\mathcal{B}\leftarrow {\mathcal{B}}^{\prime }$.

The so-collected bucket $\mathcal{B}$ is the main input to the granulator module.

The Granulator block works exactly as the one described in Section 3.1, yet on a bucket $\mathcal{B}$ composed of cliques only.

3.3. Stratified Clique

The two extractors and granulator strategies in Section 3.1 and Section 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}}^{\left(1\right)},\dots ,{\mathcal{B}}^{\left(p\right)}\}$, with p being the number of classes for the classification problem at hand, with the constraint that ${\mathcal{B}}^{\left(i\right)}$ contains subgraphs drawn from the subset of training graphs belonging to the ith class only.

The stratified clique-based extractor works as follows:

• For each ground-truth class $i=1,\dots ,p$:

  (a)

  Let ${\mathcal{S}}_{\mathrm{tr}}^{\left(i\right)}$ be the subset of the training set containing only patterns belonging to class i;

  (b)

  Calculate the (relative) frequency of the ith class as $f_i=\lfloor \frac{|{\mathcal{S}}_{\mathrm{tr}}^{\left(i\right)}|}{|{\mathcal{S}}_{\mathrm{tr}}|}+\frac{1}{2}\rfloor$, where the operator $\lfloor x+\frac{1}{2}\rfloor$ rounds x to the nearest integer;

  (c)

  Evaluate $W_i=\lfloor W·f_i+\frac{1}{2}\rfloor$, namely the size of ${\mathcal{B}}^{\left(i\right)}$;

  (d)

  Set ${\mathcal{B}}^{\left(i\right)}=\varnothing$;

  (e)

  For each graph $\mathcal{G}\in {\mathcal{S}}_{\mathrm{tr}}^{\left(i\right)}$:

  i.

  Evaluate $\mathcal{C}$ as the maximal clique decomposition of $\mathcal{G}$;

  ii.

  Update ${\mathcal{B}}^{\left(i\right)}={\mathcal{B}}^{\left(i\right)}\cup \mathcal{C}$.

  (f)

  If $|{\mathcal{B}}^{\left(i\right)}|>W_i$, then replace ${\mathcal{B}}^{\left(i\right)}$ 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}}^{\left(i\right)}$ for the ith class, to be merged together later in order to form the overall alphabet $\mathcal{A}$. Specifically:

• Start with $\mathcal{A}=\varnothing$;
• For each ground-truth class $i=1,\dots ,p$:

  (a)

  Consider the sub-bucket ${\mathcal{B}}^{\left(i\right)}$ containing subgraphs drawn from ${\mathcal{S}}_{\mathrm{tr}}^{\left(i\right)}$;

  (b)

  Run the Granulator (see Section 3.1) on ${\mathcal{B}}^{\left(i\right)}$, yielding ${\mathcal{A}}^{\left(i\right)}$;

  (c)

  $\mathcal{A}=\mathcal{A}\cup {\mathcal{A}}^{\left(i\right)}$ .

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·m·Q)$.

3.4. Stratified Random Walk

The stratified path-based extractor, originally proposed in [41], works as follows:

• For each ground-truth class $i=1,\dots ,p$:

  (a)

  Let ${\mathcal{S}}_{\mathrm{tr}}^{\left(i\right)}$ be the subset of the training set containing only patterns belonging to class i;

  (b)

  Calculate the (relative) frequency of the ith class as $f_i=\lfloor \frac{|{\mathcal{S}}_{\mathrm{tr}}^{\left(i\right)}|}{|{\mathcal{S}}_{\mathrm{tr}}|}+\frac{1}{2}\rfloor$;

  (c)

  Evaluate $W_i=\lfloor W·f_i+\frac{1}{2}\rfloor$, namely the size of ${\mathcal{B}}^{\left(i\right)}$;

  (d)

  Evaluate $W_i^{\prime }=\lfloor W_i·o+\frac{1}{2}\rfloor$, namely the number of subgraphs to be extracted for each of the candidate subgraphs order, yet considering only graphs belonging to class i;

  (e)

  Set ${\mathcal{B}}^{\left(i\right)}=\varnothing$;

  (f)

  For $l=1,\dots ,o$:

  i.

  Set ${\mathcal{B}}^{(i,l)}=\varnothing$, namely a temporary bucket that will hold subgraphs of order l extracted from graphs of class i;

  ii.

  Until $|{\mathcal{B}}^{(i,l)}|$ is equal to $W_i^{\prime }$:

  A.

  Extract uniformly at random a graph $\mathcal{G}$ from ${\mathcal{S}}_{\mathrm{tr}}^{\left(i\right)}$;

  B.

  Extract uniformly at random a node v from $\mathcal{G}$;

  C.

  Start a simple random walk of length l from node v;

  D.

  The subgraph emerged from the random walk is added to ${\mathcal{B}}^{(i,l)}$;

  iii.

  ${\mathcal{B}}^{\left(i\right)}={\mathcal{B}}^{\left(i\right)}\cup {\mathcal{B}}^{(i,l)}$

The Granulator block works exactly as the one described in Section 3.3, yet on a bucket-of-buckets $\mathcal{B}$ composed of random walks (cf. Section 3.1).

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}{ccccccccccc}Q& \eta & {\tau }_F& w_{\mathrm{sub}}^{\mathrm{node}}& w_{\mathrm{ins}}^{\mathrm{node}}& w_{\mathrm{del}}^{\mathrm{node}}& w_{\mathrm{sub}}^{\mathrm{edge}}& w_{\mathrm{ins}}^{\mathrm{edge}}& w_{\mathrm{del}}^{\mathrm{edge}}& {\Pi }_{\mathrm{edge}}& {\Pi }_{\mathrm{node}}\end{array}\right]$$

(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(·,·)$, 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_{\mathrm{sub}}^{\mathrm{node}}$, $w_{\mathrm{ins}}^{\mathrm{node}}$, $w_{\mathrm{del}}^{\mathrm{node}}$, $w_{\mathrm{sub}}^{\mathrm{edge}}$, $w_{\mathrm{ins}}^{\mathrm{edge}}$, $w_{\mathrm{del}}^{\mathrm{edge}}$;
• A set ${\Pi }_{\mathrm{edge}}$ of parameters, if needed, in order to drive the dissimilarity measure between edges;
• A set ${\Pi }_{\mathrm{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}}_{\mathrm{tr}}$ and ${\mathcal{S}}_{\mathrm{val}}$, namely ${\mathbf{H}}_{\mathrm{tr}}$ and ${\mathbf{H}}_{\mathrm{val}}$.

These two instance matrices are finally fed to the Classifier block, which trains a K-NN decision rule on ${\mathbf{H}}_{\mathrm{tr}}$ and predicts the ground-truth labels on ${\mathbf{H}}_{\mathrm{val}}$.

Each individual is evaluated by means of a fitness function (to be minimized) formalized as follows:

$$f=\alpha ·\pi +(1-\alpha )·\sigma$$

(8)

where $\pi$ is an error term and $\sigma$ is a penalty term. Specifically:

$$\pi =1-\frac{1}{p}\sum _{i=1}^p\mathrm{rec}\left(i\right)$$

(9)

where $\mathrm{rec}\left(i\right)$ 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{\left|\mathcal{A}\right|}{\left|\mathcal{B}\right|}$$

(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}}_{\mathrm{tr}}^{\star }$ and ${\mathbf{H}}_{\mathrm{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.

In this second optimization stage, the genetic code is simply a binary mask:

$$\mathbf{m}={\{0,1\}}^{|{\mathcal{A}}^{\star }|}$$

(11)

and each individual from the evolving population:

• Projects ${\mathbf{H}}_{\mathrm{tr}}^{\star }$ and ${\mathbf{H}}_{\mathrm{val}}^{\star }$ on the subset of columns spanned by the indices $\{i:{\mathbf{m}}_i=1\}$, say ${\mathbf{H}}_{\mathrm{tr}}^{\star \prime }$ and ${\mathbf{H}}_{\mathrm{val}}^{\star \prime }$;
• Trains the classifier on ${\mathbf{H}}_{\mathrm{tr}}^{\star \prime }$ and validates its performance on ${\mathbf{H}}_{\mathrm{val}}^{\star \prime }$.

The fitness function (to be minimized) reads as:

$$f^{\prime }=\beta ·\pi +(1-\beta )·\frac{\left|\right\{i:{\mathbf{m}}_i=1\left\}\right|}{|{\mathcal{A}}^{\star }|}$$

(12)

where the leftmost term reads as in Equation (9) and the rightmost term aims at fostering the evolution towards smaller alphabets by preferring sparse binary masks.

At the end of this second optimization stage, the (possibly) reduced alphabet ${\mathcal{A}}^{\star \prime }\subseteq {\mathcal{A}}^{\star }$ is retained, along with the projected training instance matrix ${\mathbf{H}}_{\mathrm{tr}}^{\star \prime }$. The test set is itself embedded against ${\mathcal{A}}^{\star \prime }$, yielding ${\mathbf{H}}_{\mathrm{ts}}^{\star \prime }$. The classifier is finally trained on ${\mathbf{H}}_{\mathrm{tr}}^{\star \prime }$ and its final performance is evaluated on ${\mathbf{H}}_{\mathrm{ts}}^{\star \prime }$.

5. Tests and Results

5.1. Datasets Description

The proposed comparison among different data granulation strategies involves 11 different datasets, with the first 6 datasets being taken from the IAM Repository [49] and the remaining ones being taken from the TUDataset Repository [50]. A brief description of the datasets, along with the formal definition of the dissimilarity measures between nodes and edges, follows:

AIDS: 

The AIDS dataset consists of 2000 graphs representing molecules showing activity or not against HIV (two classes). Molecules are converted into graphs in a straightforward manner by representing atoms as nodes and the covalent bonds as edges. Nodes are labeled by a three-element tuple that collects the 2D $\langle x,y\rangle$ coordinates of the atom, the chemical symbol (categorical) and its charge (integer). Although edges are originally labeled with the valence of the linkage, such a value has been discarded since it is not useful for the classification task.

Letter-L: 

The Letter-L dataset involves graphs that represent distorted letter drawings with a low level of distortion. The recognition task involves the 15 capital letters of the Roman alphabet that can be represented by straight lines only. Each handwritten letter is transformed into a graph by representing lines as edges and endpoints of lines as nodes. Each node is labeled by a two-dimensional real-valued vector giving its position within a reference coordinate system. Conversely, edges are unlabeled.

Letter-M: 

Same as Letter-L, but with medium level of distortion in handwritten digits.

Letter-H: 

Same as Letter-L, but with high level of distortion in handwritten digits.

GREC: 

The GREC dataset consists of symbols from electronic and architectural drawings and, after suitable pre-processing, graphs are extracted from such images. Ending points, corners, intersections and circles are represented by nodes and labeled with a two-dimensional attribute giving their position. The nodes are connected by undirected edges, which are labeled as ”line” or ”arc”. An additional attribute specifies the ”angle” with respect to the horizontal direction or the diameter in case of arcs.

Mutagenicity: 

The Mutagenicity dataset consists of 4337 graphs corresponding to chemical compounds divided into two classes, depending on their respective mutagenic propensity for being a marketable drug or not. Both nodes and edges are equipped with categorical labels: node labels identify the atom type and edge labels identify the valence of the linkage.

MUTAG: 

The MUTAG dataset consists of 188 graphs corresponding to chemical compounds divided into two classes according to their respective mutagenic effect on a bacterium. Both nodes and edges are equipped with categorical labels: node labels identify the atom type and edge labels identify the bond type (single, double, triple or aromatic).

DD: 

The DD dataset (also known as D&D) contains 1178 protein structures. Each protein is represented by a graph, in which the nodes are amino-acids and two nodes are connected by an edge if they are less than 6Å apart. Nodes encode a categorical label (i.e., the amino-acid type), whereas edges are unlabeled. The prediction task is to classify the protein structures into enzymes and non-enzymes.

NCI1: 

Each graph is used as representation of a chemical compound: each vertex stands for an atom of the molecule, and edges between vertices represent bonds between atoms. This dataset is relative to anti-cancer screens, where the chemicals are assessed as positive or negative to cell lung cancer. Each vertex has a categorical label representing the corresponding atom type, whereas edges are unlabeled.

ENZYMES: 

Each graph represents a simplified protein tertiary structure, where nodes correspond to secondary structure elements and edges connect nodes if those are neighbors along the primary structure (i.e., the amino-acid sequence) with the constraint that every node is connected to its three nearest spatial neighbors. Nodes contain a categorical label stating the type of secondary structure ($\alpha$-helix, $\beta$-sheet or turn) and a real-valued vector containing 18 physical and chemical measurements. Conversely, edges are unlabeled. The prediction task is used to classify the protein structures into one of the six Enzyme Commission classes [51].

Brief statistics about the datasets can be found in

Table 1. Dataset statistics.

Dataset Name	# Graphs	Avg. # Nodes	Avg. # Edges	# Classes	Balanced	Domain	Reference
AIDS	2000	15.69	16.20	2	No	Chemoinformatics	[49]
Letter-L	2250	4.7	3.1	15	Yes	Computer Vision	[49]
Letter-M	2250	4.7	3.2	15	Yes	Computer Vision	[49]
Letter-H	2250	4.7	4.5	15	Yes	Computer Vision	[49]
GREC	1100	11.5	12.2	22	Yes	Electronics	[49,52]
Mutagenicity	4337	30.3	30.8	2	No	Chemoinformatics	[49,53]
MUTAG	188	17.93	19.79	2	No	Chemoinformatics	[54,55]
DD	1178	284.32	715.66	2	No	Bioinformatics	[56,57]
NCI1	4110	29.87	32.30	2	Yes	Chemoinformatics	[57,58]
ENZYMES	600	32.63	62.14	6	Yes	Bioinformatics	[59,60]

, along with the reference paper in which each dataset has been originally presented, to which we refer the interested reader for more information.

Each dataset has been split into three disjoint sets: training, validation and test. For the six IAM datasets, we used the very same training/validation/test splits provided in the repository, whereas for the four TUDatasets, we had to perform our own splits with the following ratio: training set (50%), validation set (25%) and test set (25%). The splitting procedure has been performed in a stratified manner in order to preserve labels’ distribution across the three sets.

For Letter-L, Letter-M, Letter-H, GREC and AIDS, details about the dissimilarity measures on nodes and edges can be found in ([32] Appendix B). We anticipate that GREC is the only dataset with parametric dissimilarity measures on nodes and edges, i.e., for which ${\Pi }_{\mathrm{edge}}\ne \varnothing$ and ${\Pi }_{\mathrm{node}}\ne \varnothing$.

For MUTAG and Mutagenicity, since in both datasets nodes and edges are equipped with categorical labels, the dissimilarity between nodes and the dissimilarity between edges are set as the plain discrete distance between labels (i.e., their distance is 1 if they are not equal and 0 otherwise) ([61] Chapter 1).

For DD and NCI1, since in both datasets nodes are equipped with categorical labels and edges are unlabeled:

• The dissimilarity between nodes reads as the plain discrete distance between labels;
• The dissimilarity between edges reads as a constant value.

Finally, for ENZYMES:

• The dissimilarity between nodes reads as the (normalized) Euclidean distance between their respective 18-length attribute vectors if and only if the two nodes refer to the same secondary structure (i.e., both are $\alpha$-helices, $\beta$-sheets or turns); otherwise, their dissimilarity is 1;
• The dissimilarity between edges (that are unlabeled) reads as a constant value.

5.2. Algorithmic Setup

The software has been fully implemented in Python with the support of the following third-party libraries: NetworkX [62] and LittleBallOfFur [63] for handling and processing graph data structures, Scikit-Learn [64] for machine learning routines and SciPy [65] for optimization routines.

Other algorithm parameters have been configured as follows:

• $\alpha =0.9$ in the fitness function of the first genetic optimization (cf. Equation (8));
• $\beta =0.9$ in the fitness function of the second genetic optimization (cf. Equation (12));
• Maximum number of 20 generations for both genetic optimizations;
• A total of 20 and 100 individuals in the population for the first and second genetic optimization, respectively;
• Maximum walk length $o=5$;
• Candidate $\theta$ values are $\theta =\{0.5,0.25,0.125\}$;
• $Q\in [1,Q_{\max }]$, where $Q_{\max }=500$ for non-stratified Granulators and $Q_{\max }=500/p$ for stratified Granulators [41];
• The user-defined bucket size W has been chosen according to a given percentage of the maximum number of paths or cliques that can be drawn from the training graphs. The percentages are chosen according to the following rule: the larger the dataset, the higher the subsampling rate. For the sake of shorthand, we omit any sensitivity analysis on the behavior of the Granulators as a function of W. In this regard, we refer the interested reader to our previous works [41,46,66] The values for W for both clique-based and path-based Granulators are summarized in

  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.

  Dataset	Path-Based	Clique-Based
  AIDS	$10\%\times N_P$ with $N_P$ = 27,589	$40\%\times N_C$ with $N_C=3994$
  GREC	$10\%\times N_P$ with $N_P$ = 21,009	$40\%\times N_C$ with $N_C=3367$
  Letter-L	$10\%\times N_P$ with $N_P=7975$	$40\%\times N_C$ with $N_C=2391$
  Letter-M	$10\%\times N_P$ with $N_P=8217$	$40\%\times N_C$ with $N_C=2412$
  Letter-H	$10\%\times N_P$ with $N_P$ = 12,063	$40\%\times N_C$ with $N_C=2500$
  Mutagenicity	$10\%\times N_P$ with $N_P$ = 449,519	$40\%\times N_C$ with $N_C$ = 49,294
  MUTAG	$10\%\times N_P$ with $N_P$ = 15,530	$40\%\times N_C$ with $N_C=1897$
  DD	$1\%\times N_P$ with $N_P$ = 22,024,059	$10\%\times N_C$ with $N_C$ = 168,781
  NCI1	$5\%\times N_P$ with $N_P$ = 521,560	$20\%\times N_C$ with $N_C$ = 66,522
  ENZYMES	$10\%\times N_P$ with $N_P$ = 383,730	$40\%\times N_C$ with $N_C=9897$

  .

5.3. Computational Results

In Figure 1 and Figure 2 we show the accuracy on the test set and the number of resulting alphabet symbols, respectively, with Figure 3 and Figure 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 clique-based extractors, 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}\left(3^{n/3}\right)$ 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. This phenomenon is particularly evident for binary classification problems: a clear sign that building two dedicate alphabets (one for the positive class, one for the negative class) is excessive and just one alphabet would be a smarter choice.

In

Table 3. Comparison against state-of-the-art graph classification system in terms of classification accuracy.

Technique	AIDS	GREC	Letter-L	Letter-M	Letter-H	Mutagenicity	MUTAG	DD	NCI1	ENZYMES	Reference
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 + kPCA + K-NN	-	97.1	97.6	-	-	-	-	-	-	-	[73]
Graph of Words + ICA + K-NN	-	58.9	82.8	-	-	-	-	-	-	-	[73]
Topological embedding	99.4	-	-	-	-	77.2	-	-	-	-	[68,80]
FMGE	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]
ODD $S{T}_{+}$ kernel	82.06 *	-	-	-	-	-	-	-	84.97 *	-	[69]
ODD $S{T}_{+}^{TANH}$ kernel	82.54 *	-	-	-	-	-	-	-	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-1NN	-	-	96	93	84	-	-	-	-	-	[77]
C-M-1NN	-	-	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.91	-	-	-	-	-	[78]
MPNN	-	89.5	91.3	81.2	64.24	-	-	-	-	-	[79]
MPNN (no set2set)	-	92.98	94.8	86.1	75.7	-	-	-	-	-	[79]
Deep Graphlet Kernel	-	-	-	-	-	-	82.66 *	-	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

* Results refers to cross-validation rather than a separate test set.

, we finally show a brief comparison against current approaches for graph classification. Competitors span a variety of techniques, including classifiers working on the top of GEDs [49,67], kernel methods [68,69,70,71] and several embedding techniques [68,72,73], including Granular Computing-based [32,74] and those based on neural networks and deep learning [75,76,77,78,79]. We can see that our method has comparable performances against current approaches in the graph classification literature. It is worth remarking that, aside from the mere numerical results, our approach has considerable higher perspectives to be deployed for analytical investigation by field experts thanks to its interpretability advantages, a common facet of Granular Computing-based systems [32,74], since the resulting set of automatically extracted granules of information can be analyzed by field experts in order to gather further insights on the problem at hand, paving the way for knowledge discovery.

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.

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. A two-stage optimization process takes care of tuning the hyper-parameters of the classification model and performing an additional feature selection to ensure the selection of optimal granules of information.

In order to address the behavior of the granulation strategies, we performed a two-fold comparison in terms of classification performance and number of granules of information. To this end, 10 different open-access datasets of labeled graphs pertaining to different application domains have been considered. Computational results show that, regardless of whether cliques or paths are employed, running a class-aware granulation is beneficial in terms of classification accuracy. However, it has the potential drawback of yielding a higher number of granules of information (i.e., higher dimensional embedding space).

Although in this paper we used the BSAS free-clustering algorithm as the core clustering algorithm for the Granulator module, in principle, any clustering algorithm suitable for dealing with structured data and suitable for being equipped with an ad hoc dissimilarity measure can be employed instead. In the GRALG framework, the Granulator process is repeated many times (i.e., at least as many times as the are individuals in the first optimization stage), and therefore, the computational complexity of the clustering algorithm plays an important role in order to ensure reasonable training times (i.e., the BSAS clustering algorithm is known to scale linearly with respect to the number of patterns). Future research endeavours may investigate the trade-off in terms of training times against granulation quality with different clustering algorithms.