## 4 Experimental Evaluation
### Experimental Setup  
All our experiments are performed on an Intel machine equipped with six 3.60 GHz i5-8600 CPUs, 64 GB RAM, and a 64-bit Fedora Core 31 operating system. All required codes are implemented with Python. We employ five well-known and publicly available datasets for our evaluation as follows. Table 1 shows some statistics of our datasets:  
* BlogCatalog [23; 27; 29] is a graph representing social relationships among bloggers. The node labels denote blogger interests inferred through the metadata provided by the bloggers. This graph is fully tagged by 39 different labels. * Cora [39; 40] is a citation graph of academic papers in the area of computer science. The node labels denote the paper's topic (e.g., Networking-Protocols). This graph is fully tagged by 70 different labels. * DBLP [1; 17; 41] is a citation graph of academic papers in the areas of data mining and databases published in 2006 and earlier. The node labels denote the paper's topic. This graph is partially tagged (i.e., 200 labeled nodes) by 11 different labels. * TREC [1; 17] is a hyperlink graph based on TREC 2003) ([[http://trec.nist.gov/data.html](http://trec.nist.gov/data.html)]([http://trec.nist.gov/data.html](http://trec.nist.gov/data.html))) where nodes represent web pages and links to the hyperlinks between web pages. The node labels denote the web page's topic. This graph is partially tagged (i.e., 127 labeled nodes) by 11 different labels. * Wikipedia [26; 27; 29] is a co-occurrence graph of words appearing in the first million bytes of the English Wikipedia dump. The labels represent the inferred Part-of-Speech (POS) tags of words. This graph is fully tagged by 40 different labels. In the case of undirected graphs, we create two links in both directions. In order to evaluate the effectiveness (i.e., accuracy), we utilize MAP (mean average precision), precision, recall, F-score [37], and PRES [48] as evaluation metrics. In each dataset, we consider the labels as ground truth; for each label \(l\), we use every single node with label \(l\) as a _query node for a similarity based searching_, and find those nodes that are considered similar to the query as a result set. If a node in the result set is labeled with \(l\), it is regarded as _relevant_ to the query, otherwise _irrelevant_. Then, we compute precision, recall, F-score, average precision (AP), and PRES for that query as follows:  
\[precision=\frac{|Res\cap Rel|}{|Res|} \tag{1}\]  
\[recall=\frac{|Res\cap Rel|}{|Rel|} \tag{2}\]  
\[F-score=\frac{2\times recall\times precision}{recall+precision} \tag{3}\]  
where \(Res\) indicates the query result set, \(Rel\) indicates the set of relevant nodes to the query (i.e., the set of all nodes labeled with \(l\)). \(|Rel|\) and \(|Res|\) indicate the sizes of \(Rel\) and \(Res\), respectively. In the AP measure, a precision value is computed in each position (rank) in the query result set:  
\[AP=\frac{\sum_{k=1}^{|Res|}P@k\times Rel(k)}{|Rel|} \tag{4}\]  
where \(P@k\) indicates the precision at position \(k\), \(Rel(k)\) is set as \(1\) if the node in position \(k\) is regarded as relevant. Otherwise, it is set as \(0\). PRES considers the rank of retrieved relevant nodes in a result set and is computed as follows:  
\[PRES=1-\frac{\frac{\frac{\Sigma_{r_{l}}}{|Rel|}-\frac{|Rel|+1}{|2|}}}{|Res|} \tag{5}\]  
where \(r_{l}\) is the rank of the \(i^{th}\) relevant node in the result set; for each of those \(m\) (i.e., \(m\leq|Rel|\)) number of nodes that are relevant to the query but _not_ retrieved in the result set, a rank is assigned by _starting_ from the value of \(\{|Res|+|Rel|-x+1\}\). After computing the AP, precision, recall, F-score, and PRES for all the query nodes with label \(l\), we take their average values to get MAP, precision, recall, F-score, and PRES values for label \(l\). Then, we compute the average values of MAP, precision, recall, F-score, and PRES over _all_ labels in the dataset.