## 3 Information Granulation Strategies  
### 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}= \begin{cases}\frac{1}{\deg(v)},&\text{if }u\in\mathcal{N}(v)\\ 0,&\text{otherwise}\end{cases}  \tag{3}\]  
where \(\mathcal{N}(v)\) is the neighborhood of node \(v\) and \(\deg(v)\) is its degree, i.e., \(\deg(v)=|\mathcal{N}(v)|\). Populating the bucket \(\mathcal{B}\) relies on two important parameters:  
* \(W\), the user-defined number of subgraphs in \(\mathcal{B}\), i.e., \(W=|\mathcal{B}|\);
* \(o\), the user-defined maximum number of nodes for subgraphs in \(\mathcal{B}\). and it works as follows:  
1. Start with \(\mathcal{B}=\mathcal{O}\);
2. Let \(W^{\prime}=\frac{W}{o}\) be the number of subgraphs to be extracted for each of the candidate subgraph orders;
3. For \(l=1,\ldots,o\): 1. Let \(\mathcal{B}^{(l)}=\mathcal{O}\) be a temporary bucket containing only subgraphs of order \(l\); 2. Until \(|\mathcal{B}^{(l)}|\) equals \(W^{\prime}\): 1. Extract uniformly at random a graph \(\mathcal{G}\) from the training set; 2. Extract uniformly at random a node \(v\) from \(\mathcal{G}\); 3. Start a simple random walk of length \(l\) from node \(v\); 4. The subgraph emerged from the random walk is added to \(\mathcal{B}^{(l)}\); 3. \(\mathcal{B}=\mathcal{B}\cup\mathcal{B}^{(l)}\);  
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},\ldots,\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\cdot 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(\mathcal{K})\) that reads as:  
\[F(\mathcal{K})=\eta\cdot\Phi(\mathcal{K})+(1-\eta)\cdot\Psi(\mathcal{K}) \tag{4}\]  
namely, as a linear convex combination between the compactness of the cluster \(\Phi(\mathcal{K})\) and its cardinality \(\Psi(\mathcal{K})\) 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(\mathcal{K})=\frac{1}{|\mathcal{K}|-1}\sum_{i}d(g^{\star},g_{i}) \tag{5}\]  
where \(g_{i}\in\mathcal{K}\) is the \(i\)th 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].