# A Scalable Deep Network for Graph Clustering
## 4 Experiments
### Methods  
We compare SDN with various existing representative unsupervised models for clustering tasks. Moreover, these models can be divided into three categories according to different input data, models that only use feature matrix (vector data): K-means, AE, and Random Swap; models that only use adjacency matrix (graph data): K-algorithm and M-algorithm; models that use both the two data: DEC, IDEC, GAE, VGAE, DAEGC, ARGA, SDCN, AGCN, SDN\({}_{P}\), SDN\({}_{E}\), and SDN. The following are specific descriptions of these models. * **K-means**[32]: It is a traditional clustering method applied directly to the feature matrix (vector data). In this paper, we utilize the K-means supported by the sklearn package. For details, please refer to [[https://github.com/scikit-learn/scikit-learn](https://github.com/scikit-learn/scikit-learn)]([https://github.com/scikit-learn/scikit-learn](https://github.com/scikit-learn/scikit-learn)), accessed on 12 April 2022. * **AE**[22]: This auto-encoder consists of an encoder and a decoder. It uses the encoder to encode the initial data, then utilizes the decoder to reconstruct the embeddings. In addition, it calculates the reconstruction loss as the objective function. Finally, we employ K-means to perform clustering on the obtained high-dimensional embeddings. * **Random Swap**[33]: Random swap algorithm aims at solving clustering by a sequence of prototype swaps and by fine-tuning their exact location by k-means. We utilize the Random Swap file of the python version in the UEF Machine Learning repository. For details, please refer to [[https://github.com/uef-machine-learning/RandomSwap](https://github.com/uef-machine-learning/RandomSwap)]([https://github.com/uef-machine-learning/RandomSwap](https://github.com/uef-machine-learning/RandomSwap)), accessed on 12 April 2022. * **K-algorithm**[21]: K-algorithm applies similar iterative local optimization but without the need to calculate the means. It inherits the properties of k-means clustering in terms of both good local optimization capability and the tendency to get stuck at a local optimum. * **M-algorithm**[21]: M-algorithm gradually improves on the results of the K-algorithm to find new and potentially better local optima. It repeatedly merges and splits random clusters and tunes the results with the K-algorithm. * **DEC**[34]: DEC is a deep clustering method that defines a centroid-based probability distribution and minimizes the KL divergence as an auxiliary objective distribution to improve both cluster assignment and feature representation. It implements the joint optimization of deep embedding and clustering. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Dataset** & **Type** & **Samples** & **Classes** & **Dimension** & **Description** \\ \hline USPS & Image & 9298 & 10 & 256 & KNN network \\ HHAR & Record & 10,299 & 6 & 561 & KNN network \\ Reuters & Text & 10,000 & 4 & 2000 & KNN network \\ ACM & Graph & 3025 & 3 & 1870 & Citation network \\ CiteSeer & Graph & 3327 & 6 & 3703 & Citation network \\ DBLP & Graph & 4058 & 4 & 334 & Author network \\ \hline Flickr & Graph & 89,250 & 7 & 500 & Image network \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The statistics of the datasets. * **IDEC**[35]: Taking into account the preserved data structure, IDEC manipulates the feature space to disperse the data points. Moreover, it can jointly perform the embedding and the clustering process. * **GAE**[5]: This method is an effective combination of auto-encoder graph convolution. First, graph convolution is used to encode the data; then, the decoder is used to reconstruct its adjacency matrix. The loss function measures the difference between the reconstructed matrix and the original matrix. * **VGAE**[5]: This model first obtains the embeddings through GCNs, then learns the distribution satisfied by them. Finally, it calculates the posterior probability to obtain the latent variable to reconstruct the adjacency matrix.