# A Scalable Deep Network for Graph Clustering
## 4 Experiments
### Evaluation Metrics and Experimental Setup  
#### 4.3.1 Evaluation Metrics  
We adopt four widely used evaluation metrics: Accuracy (**ACC**), Normalized Mutual Information (**NMI**), Average Rand Index (**ARI**), and macro-F1 score (**F1**) [37]. For each metric, a larger value implies a better clustering result.  
The specific calculation methods of the four indicators are as follows  
**Accuracy (ACC)**  
**ACC** is used to compare the obtained labels with the true labels, which can be calculated by the formula below  
\[ACC=\frac{\sum_{i=1}^{m}\delta(s_{i},map(r_{i}))}{n}, \tag{22}\]  
where \(r_{i},s_{i}\) represent the obtained label and true label corresponding to the data \(x_{i}\), respectively, \(n\) is the total number of data, \(\delta\) indicates that the indicator function is as follows  
\[\delta(x,y)=\left\{\begin{array}{ll}1&\quad if\ x=y\\ 0&\quad otherwise\end{array}\right.. \tag{23}\]  
The map in this formula represents the re-distribution of the best class label to ensure the correctness of the statistics.  
**Normalized Mutual Information (NMI)**  
**NMI** is often used in clustering to measure the similarity of two clustering results. Assuming that \(P_{A}(a),P_{B}(b)\) represent the probability distribution of \(A\) and \(B\), and \(P_{AB}(a,b)\) represents the joint distribution probability of \(A\) and \(B\), then we have  
\[H(A)=-\sum_{a}P_{A}(a)logP_{A}(a), \tag{24}\]\[H(B)=-\sum_{b}P_{B}(b)logP_{B}(b), \tag{25}\]  
\[H(A,B)=-\sum_{a,b}P_{AB}(a,b)logP_{AB}(a,b), \tag{26}\]  
where \(H(A)\) is called the information entropy of \(A\) vector. According to the relationship between joint entropy and individual entropy, **NMI** is defined as  
\[NMI=\frac{H(A)+H(B)}{H(A,B)}. \tag{27}\]  
**Adjusted Rand index (ARI)**  
**ARI** reflects the degree of overlap between the two divisions. Suppose clustering is a series of decision-making processes, that is, making decisions on all \(N(N-1)\) node pairs on the set. When only two nodes are similar, we group them into the same cluster. We utilize \(a\) to group two similar nodes into one cluster and \(b\) to group dissimilar nodes into different clusters. The Rand coefficient (RI) can be defined as  
\[RI=\frac{a+b}{C_{n}^{2}}. \tag{28}\]  
However, RI fails to guarantee that the RI value of randomly divided clustering results is close to 0. Therefore, the Adjusted Rand index (RI) is proposed.  
\[ARI=\frac{RI-E[RI]}{max(RI)-E[RI]}, \tag{29}\]  
where \(E[RI]\) represents the expectation of RI, \(ARI\in[-1,1]\).  
**Macro-F1 Score (F1)**  
The **F1 score** measures the accuracy of a binary classification (or multi-task binary classification) model. It takes into account both the accuracy and recall of the classification model. F1 score can be regarded as a weighted average of model precision and recall, and \(F1\in[0,1]\).  
According to Table 2, _precision_ refers to the proportion of samples with a predicted value of 1 and a true value of 1 in all samples with a predicted value of 1. In addition, _recall_ refers to the proportion of samples with a predicted value of 1 and a true value of 1 among all samples with a true value of 1. Therefore, _precision_ and _recall_ can be defined as  
\[precision=\frac{TP}{TP+FP}, \tag{30}\]  
\[recall=\frac{TP}{TP+FN}, \tag{31}\]  
On this basis, **F1 score** is defined as the harmonic mean of precision and recall  
\[F_{1}=2\times\frac{precision\times recall}{precision+recall} \tag{32}\]  
For macro-F1, it is the average of the **F1 score** of each cluster in the set.  
\[macroF_{1}=\frac{1}{N}\sum_{i=1}^{N}F_{1}. \tag{33}\]