Generalized Clustering and Multi-Manifold Learning with
Geometric Structure Preservation

Intra-manifold Isometry Loss. The intra-manifold local structure is preserved by optimizing the objective as:

Alignment Loss. Global ranking loss $L_{rank}$ is imposed directly on $\left\{\mu_{j}\right\}_{j=1}^{C}$, so optimizing $L_{rank}$ only updates $\left\{\mu_{j}\right\}_{j=1}^{C}$ rather the encoder’s parameter $\theta_{f}$. However, the optimization of $\left\{\mu_{j}\right\}_{j=1}^{C}$ not only relies on $L_{rank}$, but is also constrained by $L_{cluster}$, which ensures that data points remain roughly distributed around cluster centers and do not deviate significantly from them during the optimization process. Alignment loss $L_{align}$, as an auxiliary term, aims to help align learnable centers $\left\{\mu_{j}\right\}_{j=1}^{C}$ with the ground-truth centers $\{v^{Z}_{j}\}_{j=1}^{C}$ and make this binding stronger, defined as

Contradiction. The contradiction between clustering and local structure preservation is analyzed from the forces analysis perspective. As shown in Fig. 2 (a), we assume that there exists a data point (red point) and its three nearest neighbors (blue points) around a cluster center (gray point). When clustering and local structure preserving are optimized simultaneously, it’s easy to fall into a local optimum, where the data point is in steady-state, and the resultant force from its three nearest neighbors is equal in magnitude and opposite to the gravitational forces of the cluster.

Alternating Training. To solve the above problem and integrate the goals of clustering and local structure preservation into a unified framework, we take an alternating training strategy. Within each epoch, we first optimize $L_{cluster}$ and $L_{rank}$ in a mini-batch, with joint loss defined as

Then at each epoch, we jointly optimize isometry loss $L_{\textit{LIS}}$ and $L_{align}$ on the whole dataset, defined as

Weight Continuation. At different stages of training, we have different requirements for clustering and structure preservation. At the beginning of training, to successfully decouple the overlapping manifolds, we hope that the $L_{cluster}$ will dominate and $L_{\textit{LIS}}$ will be auxiliary. When the margin between different manifolds is sufficiently large, the weight $\alpha$ for $L_{cluster}$ can be gradually reduced, while the weight $\beta$ for $L_{\textit{LIS}}$ can be gradually increased, focusing on the preservation of the local isometry. The whole algorithm is summarized in Algorithm 1.

Three-stage Explanation. The training process can be roughly divided into three stages, as shown in Fig. 2 (b), to explain the training strategy more vividly. Also, we provide the learning curves of key losses $L_{cluster}$, $L_{rank}$, $L_{\textit{LIS}}$ on the MNIST-test dataset in Fig. 2 (c). At first, four different manifolds overlap. At Stage 1, $L_{cluster}$ dominates, thus data points within each manifold converge towards cluster centers to form spheres, but the local structure of manifolds is corrupted. At Stage 2, $L_{rank}$ dominates, thus different manifolds in the latent space move away from each other to increase the manifold margin and enhance the discriminability. At stage 3, these manifolds gradually recover their original local structure from the spherical shape with $L_{\textit{LIS}}$ dominating. Note that the above losses may coexist rather than being completely independent at different stages, but the role played by different losses varies due to the alternating training and weight continuation strategies.

In this section, the effectiveness of GCML is evaluated in 7 benchmark datasets: MNIST-full, MNIST-test, USPS, Fashion-MNIST, REUTERS-10K, HAR, and Pendigits on which GCML is compared with 12 other methods in 8 evaluation metrics including metrics specifically designed for clustering and multi-manifold learning. The brief descriptions of the datasets are given in Appendix A.1.

Evaluation Metrics. Two standard evaluation metrics: Accuracy (ACC) and Normalized Mutual Information (NMI) are used to evaluate clustering performance. Besides, six evaluation metrics are adopted in this paper to evaluate the performance of multi-manifold learning, including Relative Rank Error (RRE), Trustworthiness (Trust), Continuity (Cont), Root Mean Reconstruction Error (RMRE), Locally Geometric Distortion (LGD) and Cluster Rank Accuracy (CRA). Limited by space, their precise definitions are available in Appendix A.3.

Parameters Settings. The encoder structure is $d$-500-500-500-2000-10 where $d$ is the dimension of the input data, and the decoder is its mirror. After pretraining, to initialize the learnable clustering centers, the t-SNE is applied to find the best clustable manifold in the latent space $Z$, and then the $K$-Means algorithm is run to obtain the label assignments for each data point. The centers of each category in the latent space $Z$ are set as initial cluster centers $\left\{\mu_{j}\right\}_{j=1}^{C}$. Besides, Adam optimizer with learning rate $\lambda$=0.001 is used, the batch size is set to 256, the epoch is set to 300, the parameter $k$ for nearest neighbor is set to 5, and the parameter $\kappa$ is set to 3 for all datasets. Sensitivity analysis for parameters $k$ and $\kappa$ is available in Appendix A.4. As described in Sec. 3.3, the weight continuation is applied to train the model. The weight parameter $\alpha$ for $L_{cluster}$ decreases linearly from 0.1 to 0 within epoch 0-150. In contrast, the weight parameter $\beta$ for $L_{\textit{LIS}}$ increases linearly from 0 to 1.0 within epoch 0-150. In this paper, each set of experiments is run 5 times with different random seeds, and the results are averaged into the final performance metrics.

Quantitative Comparison. The metrics ACC/NMI of different methods are reported in Tab. 1. For those methods whose results are not reported or experimental settings are not clear, we run the released code with the same provided hyperparameters and mark them with (*). Moreover, we mark those methods that are only applicable to 2-D image data as (-) on the vector dataset. While ASPC-DA achieves the best performance on three datasets (MNIST-test, MNIST-full, and USPS), its performance gains do not come directly from clustering, but from sophisticated modules such as data augmentation and self-paced learning. Once these modules are removed, there is large performance degradation. For example, with Data Augmentation (DA) removed, ASPC achieves less competitive performance, e.g., an accuracy of 0.931 (vs 0.988) on MNIST-full, 0.813 (vs 0.973) on MNIST-test and 0.768 (vs 0.982) on USPS. Since ASPC-DA is based on the MLP architecture, its image-based augmentation cannot be applied directly to vector data, which explains why ASPC has no performance advantage (even compared to DEC and IDEC) on the vector datasets, such as REUTERS-10K and HAR datasets.

In a fair comparison (without considering ASPC-DA and marking its results in Tab. 1 as gray color), we find that GCML outperforms $K$-Means, GNN, and SC-Ncut by a significant margin and surpasses the other nine compared DNN-based algorithms on all datasets except MNIST-test. Nevertheless, even with the MNIST-test dataset, GCML still ranks second, outperforming the third by 0.9%. In particular, we obtain the best performance on the Fashion-MNIST, REUTERS-10K, and HAR datasets, and more notably, our clustering accuracy exceeds the current SOTA method by 3.9%, 4.1%, and 3.8%, respectively.

Clustering Visualization. The visualization of GCML with comparison methods is shown in Fig. 3 (visualized using UMAP). Among all methods, only DEC, IDEC, and GCML can hold clear boundaries between different clusters, while the cluster boundaries of the other methods are indistinguishable. Though DEC and IDEC successfully separate different clusters, they group many data points from different classes into the same cluster. Most importantly, due to the use of the clustering-oriented loss, the embedding learned by these algorithms (especially DSC) tend to form spheres and disrupt the original topological structure. Instead, GCML overcomes the above problems and achieves almost perfect separation between different clusters while preserving the local and global structure.

The embeddings of the latent space during the training process are visualized in Fig. 4 for explaining how both clustering and structure-preserving are achieved. We can see that the different clusters initialized by the pre-trained autoencoder are closely adjacent. In the early stage of training, with clustering loss $L_{cluster}$ and global ranking loss $L_{rank}$, different manifolds are separated from each other, but each manifold loses its local structure, and all of them degenerate into spheres. As the training progresses, the weight $\alpha$ for $L_{cluster}$ gradually decreases, while the weight $\beta$ for $L_{\textit{LIS}}$ increases and the optimization is gradually focused from global to local, with each manifold gradually recovering its original geometric structure from the sphere. These visualizations show that clustering-oriented loss does deteriorate the geometric structure of the latent space, and the designed structure-oriented losses help to recover it.

Generalizability Evaluation. Tab. 2 demonstrates that a learned GCML can generalize well to unseen data with high clustering accuracy. Taking MNIST-full as an example, GCML was trained using 50,000 training samples and then tested on the remaining 20,000 testing samples using the learned model. In terms of the metrics ACC and MNI, GCML is optimal for both training and testing samples. More importantly, there is hardly any degradation in the performance of GCML on the testing samples compared to the training samples, while all other methods show a significant drop in performance, e.g., DEC from 84.1% to 74.8%. This demonstrates the importance of geometric structure preservation for good generalizability. The visualization results of the testing samples are shown in Fig. 5; even for testing samples, GCML still shows distinguishable inter-cluster discriminability, while other methods couple different clusters together, which shows GCML’s great generalizability.

Quantitative Metrics. Though many previous works have claimed that they brought clustering and dimensionality reduction into a unified framework, unfortunately, they all lacked an analysis of the effectiveness of the learned embeddings. In this paper, we compare GCML with the other five methods in six quantitative metrics on seven datasets. Limited by space, only the results of MNIST-full and Fashion-MNIST are provided on the left side of Tab. 3 and more results are in Appendix A.5. The results show that GCML outperforms all other methods, especially in the CRA metric, which is not only the best on all datasets but reaches 1.0, which means that the “rank” between different manifolds in the latent space is completely preserved and proves the effectiveness of the global ranking loss $L_{rank}$.

Statistical Analysis. The statistical analysis is performed to show the extent to which local and global structure is preserved in the latent space for each algorithm. Taking MNIST-full as an example, the statistical analysis of the global rank-preservation is shown in Fig. 6 (a)-(f). For the $i$-th cluster, if the rank (in terms of Euclidean distance) between it and the $j$-th cluster is preserved from the input space to the latent space, then the grid in the $i$-th row and $j$-th column is marked as blue, otherwise yellow. As shown in the figure, only GCML can fully preserve the global rank between different clusters, while all other methods fail.

Moreover, we perform statistical analysis for the local isometry property of each algorithm. For each sample $x_{i}$, it forms a number of point pairs with its neighborhood samples $\{(x_{i},x_{j})|i=1,2,...,N;x_{j}\in\mathcal{N}_{i}^{X}\}$. We compute the differences in the distance of these point pairs from the input space to the latent space $\{d_{Z}(x_{i},x_{j})-d_{X}(x_{i},x_{j})|i=1,2,...,N;x_{j}\in\mathcal{N}_{i}\}$, and plot them as a histogram. As shown in Fig. 6 (g), the curve of GCML are distributed on both sides of the 0 value, with maximum peak height and minimum peak-bottom width, respectively, which indicates that GCML achieves the best local isometry. Though IDEC [4] claims that they can preserve the local structure well, their results are still far from ours.

Downstream Tasks. Numerous deep clustering algorithms have recently claimed to obtain meaningful low-dimensional embeddings; however, they have not analyzed and experimented with the “meaningful” ones. Therefore, we are interested in whether these proposed methods can really learn manifold embeddings that are useful for downstream tasks. Four different classifiers, including a linear classifier (Logistic Regression; LR), two nonlinear classifiers (MLP, SVM), and a tree-based classifier (Random Forest Classifier; RFC) are used as downstream tasks, all of which use default parameters and default implementations in sklearn [15] for a fair comparison. The learned embeddings are frozen and used as input for training. The classification accuracy evaluated on the test set serves as a metric to evaluate the effectiveness of learned embeddings. Limited by space, only the results of MNIST-full and Fashion-MNIST are provided on the right side of Tab. 3 and more results are in Appendix A.5. The results show that GCML outperforms the other methods overall on all seven datasets, with MLP, RFC, and LR as downstream tasks.

Tab. 4 evaluates the effectiveness of the proposed loss terms and training strategies with 5 sets of experiments: the model without (A) Structure-oriented Loss (SL); (B) Clustering-oriented Loss (CL); (C) Weight Continuation (WC); (D) Alternating Training (AT), and (E) the full model. Limited by space, only the results MNIST-full and Fashion-MNIST are provided and more results are in Appendix A.6. After analyzing the results, we can conclude: (1) CL is the most important factor for obtaining excellent clustering performance, the lack of which leads to unsuccessful clustering, hence the numbers in the table are not meaningful and marked in gray color. (2) SL not only brings subtle improvements in clustering performance but greatly improves the performance of multi-manifold learning. (3) The training strategies (WC and AT) both improve the performance of clustering and multi-manifold learning to some extent, especially on metrics such as RRE, Trust, CRA, etc.