Breaking the Reclustering Barrier in Centroid-based Deep Clustering

Ad W1) Noise comparison, contraction ablation

In line with the reviewer’s suggestion, we have added ablation experiments in Appendix H.13. Leaving out the contraction part of the soft resets results in substantially worse performance. We attribute this to the role of the contraction in reducing the gradient norms, which in turn prevents representation and centroid collapse. This is supported by research in supervised learning, where soft resets have been observed to balance gradients [4]. Additionally, we perform an ablation study where we add Gaussian noise to the weights (with the same mean and variance as the current weights) instead of doing a soft reset. This shows similar performance on OPTDIGITS but performs worse on USPS. 

In Appendix F, we perform an ablation where we use noise in the embedded space to evaluate whether BRB’s performance gains are due to new cluster labels obtained through perturbed weights or whether the perturbation itself improves performance. As one can see in Figure 9, simply adding scaled Gaussian noise to the embedding space degrades the performance over time

Ad W3) Missing information in the main paper

Our goal with the section about implementation details was to give an overview of what relevant implementation details are and where exact details can be found. We have improved the implementation details according to the reviewer’s feedback:

• We clarified that we reset momentum terms to 0 for DEC and IDEC.
• We added the (re-)initialization distribution to the main paper.
• We improved the item about image augmentation in the main paper with more detail. Concretely, we clarify how we use augmentations and summarize which augmentations we use for which datasets. Additionally, we added references to the Appendix tables where we list the hyperparameters of our augmentations.

Ad Q1) Initial weight distribution

We use the Pytorch default initializer to initialize convolutional and linear layers and for soft resetting, corresponding to “Kaiming uniform” [1] initialization in Pytorch. We clarified this aspect in the main paper.

Ad Q2) Frequency of resets for the main results

For all experiments with and without resetting (scenario 1, scenario 2) on MNIST, KMNIST, USPS, FMNIST, OPTDIGITS, and GTSRB, we use the same values of $\alpha=0.8$ and $T=20$, which we state in the bolded part in Section 6.1. Our settings for the experiments using contrastive learning on CIFAR10 and CIFAR100-20 are $\alpha=0.7$ and $T=10$, which we list in Table 6 in Appendix E.6.

Ad Q3) Image augmentations

We use image augmentations to enforce consistent cluster assignments among augmented and original samples, i.e., the cluster assignments should not change due to the augmentation. This requires slightly modifying the loss functions of DEC, IDEC, and DCN. The modified losses can be found in Equations 15-17) in Appendix E.

We use a different set of augmentations for the grayscale and the color datasets. For all of them, we rely on torchvision. On MNIST, KMNIST, USPS, FMNIST, and OPTDIGITS, we first resize the image before applying a random affine transformation around the center. Detailed hyperparameters for these augmentations are in Table 4 of Appendix E.4. CIFAR and GTSRB are color datasets. Consequently, we use a different set of augmentations for them, which we list in Table 5 (GTSRB, Appendix E.5) and Table 6 (CIFAR, Appendix E.6), respectively. These augmentations comprise random resized crop, color jitter, random gray scaling, random flipping, and random solarization (in this order). Note that this corresponds to the SimCLR augmentations w/o Gaussian blur, which they recommend be turned off for CIFAR [2]. We have added a summary of this information to the main paper.

The dataset is CIFAR10 without using self-labeling.

Ad W1, W2) Usage of the term “reclustering”

We agree with the reviewer that DC algorithms already iteratively reassign data points over the course of the training. When we refer to “reclustering”, we refer to a complete reassignment of all points in the embedded space via some clustering algorithm, e.g., k-means.

To improve clarity and reduce ambiguity, we added additional information on what we mean by “reclustering” in three places: 1) Abstract, 2) Introduction, and 4) Section 4 “The reclustering barrier”.

Ad W3) Incremental contribution

Our core contributions are three-fold. First, we identify and quantify (in terms of inter-CD and intra-CD) the reclustering barrier in centroid-based deep clustering. In our eyes, the reclustering barrier in itself is of substantial interest to the deep clustering community, as we discuss in Section 7 of our paper under “Broader insights for deep clustering research”. Second, we apply soft resets in conjunction with a k-means reclustering of the latent space and moment resets. While we agree that the mere application of resets would be an incremental contribution, we want to emphasize that naive soft resetting of the encoder’s weights does not result in performance gains, as we show in Figure 4. This indicates that BRB is a non-trivial extension of plain soft resets. Lastly, our third contribution is the empirical investigation of why BRB alleviates the reclustering barrier (cf. Figures 6 and 7 of the paper). The underlying mechanisms of BRB are highly specific to deep clustering and differ substantially from the effect of resets in reinforcement learning, where they mitigate plasticity loss [1], or supervised learning, where soft resets improve generalization when fine-tuning a pre-trained network [2].

Our work also contains other contributions, such as presenting DEC, IDEC, and DCN baselines that are substantially stronger than previously used in the literature (e.g., in [3]) or the release of strong pre-trained models for other researchers to build on. In summary, we believe we make a worthwhile contribution to the current state of deep clustering algorithms.

Thank the authors for responding and clarifying the points raised in the review.

However, I still find the reclustering process discussed in the paper unclear. Based on equation (2), it appears that during reclustering, the new centroids and corresponding assignments depend solely on the perturbed embedding, without leveraging the clustering centers and assignments derived from the deep clustering methods or the reclustering process. This approach raises concerns because most deep clustering methods, whether centroid-based or not, use distinct mechanisms to generate cluster assignments. Even in centroid-based methods, enforcing clustering assignments to be generated solely from k-means could disrupt the natural assignment process inherent to the original method. After resetting the weights, it seems more intuitive to use the reclustering mechanism specific to the deep clustering algorithm for this purpose. So, an alternative approach to BRB could involve resetting the embeddings and then running the clustering step within the original deep clustering algorithm itself, which might yield similar improvements. It is unclear why k-means is needed for the reclustering step, and this choice warrants further discussion. Specifically, I would like to know the difference in performance between the two reclustering approaches: (1) resetting embeddings followed by reclustering with the original deep clustering algorithm, and (2) the proposed BRB method. Furthermore, the paper does not sufficiently clarify how the updated centroids and cluster assignments from reclustering are utilized in the iterative process. Deep clustering methods typically incorporate these assignments into backpropagation. Does BRB follow the same procedure, or does it only produce the final clustering output? If there is any misunderstanding on my part, I would greatly appreciate clarification from the authors.

Focusing solely on centroid-based methods could also limit the applicability of the proposed method. Non-centroid-based deep clustering methods, such as deep agglomerative clustering and deep density-based clustering, are widely used in various applications. From the authors’ response to W5, it seems that applying BRB to a newer method like SeCu shows only marginal improvement, which strengthens my concerns about the broader applicability of this method.

Additionally, while the authors responded to my questions in the rebuttal, the revised manuscript does not adequately address these points. For instance: I suggested including a discussion to intuitively justify the choice of critical hyperparameters, but this has not been provided. There is still no discussion of potential extensions or relationships with non-centroid-based methods. I believe similar issues, such as the “reclustering barrier,” are likely to arise in non-centroid-based approaches as well. If these discussions are included in the revised version and I have overlooked them, I would appreciate clarification.

Although I commend the authors for conducting extensive experiments and presenting their work in a nice manner, the manuscript still lacks clarity in conveying its core ideas, and its contributions remain insufficiently justified.

Ad) Reclustering with the deep clustering algorithm itself

We agree that "resetting the embeddings and then running the clustering step within the original deep clustering algorithm" is the most natural thing to do, and this was actually the first thing we tried. However, we found this to lead to unstable training for DEC, IDEC, and DCN. The main reason is that the previously learned centers are no longer meaningful after resetting the embedding. However, these centers are needed in DEC, IDEC, and DCN to generate the cluster assignments. Thus, we tried to compute new centers after an embedding reset with the previously learned cluster labels. While this made the training more stable, it led to less exploration and worse cluster performance. Our ablation experiments using only resets (Figure 4, DCN+Reset) also confirm this. Only resetting the embedding and using the cluster assignment of DCN can lead to large performance drops of more than 10% on GTSRB for DCN+Reset compared to just using DCN, while our DCN+BRB improves performance by 20%.

Further, note that DEC, IDEC, and DCN assume spherical, Gaussian-like clusters. They use k-means to generate their initial assignments, and they apply k-Means again after training to get their final assignments. This makes using k-means as a reclustering algorithm a natural choice for these algorithms. In Appendix H.4, we evaluate different algorithms for reclustering. The results show that k-means works well for DEC, IDEC, and DCN while being both simple and efficient.

Ad) The use of updated centroids and cluster assignments from reclustering in the iterative clustering process

BRB only produces the final clustering output after an epoch has ended, as outlined in the pseudocode in Algorithm 1. Therefore, BRB does not interfere with the gradient updates within one epoch. Specifically, BRB produces a new embedding and, therefore, new centroids after every $T$th epoch has ended. The new embedding and new centroids are then used for subsequent optimization steps. Both the new embedding and the new centroids implicitly affect the assignments generated in the loss of deep clustering methods, but BRB does not change the calculations for the deep clustering loss or backpropagation. Additionally, we observe in our ablation experiments that just using reclustering with k-means every $T$ epochs can improve performance in many cases, see Figure 1 or Figure 4, but BRB improves performance even further. This illustrates that reclustering helps to improve performance without destroying the learning process.

Ad) Focus on centroid-based methods

We agree that investigating non-centroid-based deep clustering methods is interesting, but as discussed in our limitations section, we leave this for future work. We focused on centroid-based deep clustering as it is currently the largest and most cited area of deep clustering, e.g., just DEC already has over 3500 citations, IDEC has 960, and DCN has 1130. Consequently, we believe the impact of our work is highest in this area. In contrast, the areas of deep hierarchical and deep density-based clustering methods, while definitely exciting, are much smaller in terms of usage when measuring citations. To illustrate this, we conducted a Google Scholar search for the term “deep density-based clustering”, which shows that the most cited deep density-based clustering paper, “Deep density-based image clustering” by Ren et al, 2020, has 120 citations. A search for “deep agglomerative clustering” and “deep hierarchical clustering” shows the paper “Clusternet: Deep hierarchical cluster network with rigorously rotation-invariant representation for point cloud analysis” by Cheng et al, 2019, as the highest cited paper with 202 citations. While this is not an in-depth study of the size of these subfields, we merely want to illustrate that centroid-based deep clustering methods are currently more used in research than other deep clustering approaches, making them a reasonable choice to approach first. BRB can likely be extended to non-centroid-based deep clustering methods by choosing a suitable algorithm for its reclustering step. The soft resetting step of BRB is a very general approach that can be applied to most neural network architectures.

Ad) Performance gains using SeCu

The limited performance gains when applying BRB to SeCu are due to saturation (SeCu is already close to supervised learning performance) and limited hyperparameter tuning. The performance can likely be further improved.

I sincerely thank the authors for discussing my concerns and committing to implementing the suggested changes in the camera ready version. I still believe the "reclustering step" remains a tricky aspect that should be carefully clarified and thoroughly discussed in the revised manuscript. Regarding the comments on "new centers", I believe that leveraging the natural assignment process inherent to the original deep clustering methods can also effectively generate the new centers. Without a clear justification for the reclustering step, the novelty of this work may be undermined. Regarding the discussion of hyperparameters, I highly recommend that the authors provide more comprehensive guidelines to assist practitioners in selecting appropriate values for the proposed method.

Ad reclustering step)

Yes, we agree and, therefore, have already clarified our use of the term “reclustering” in the manuscript (highlighted in green). Based on our discussion with the reviewer, we will add further details to Section 4, explaining how BRB affects the loss and backpropagation steps for centroid-deep clustering algorithms. Additionally, we provide pseudocode in Algorithm 1, which shows that the reclustering step of our BRB algorithm happens outside the training loop of the deep clustering methods.

Another way to think about our reclustering step is to think of it as reinitializing the clustering after the weight reset every $T$th epoch. As mentioned in our previous response, DEC, IDEC, and DCN all use k-means to initialize their cluster centers. So, reinitializing the centers with k-means after a strong embedding change is a reasonable choice.

Ad new centers)

Based on the reviewer's feedback, we conducted an experiment comparing the performance of the “natural assignment process” of DEC and IDEC with our k-means reclustering approach. We conducted 10 runs for each configuration using the same settings as in the paper. We reported the average clustering accuracy (ACC) below for three datasets (OPTDIGITS, GTSRB, and USPS), with and without pretraining. Please note that DCN already uses k-means for its assignment and centroid update step, making k-means the “natural assignment process” of DCN. This motivates our focus on DEC and IDEC.

We can see that BRB with the “natural assignment process” can indeed improve over the baseline. Still, it is outperformed by BRB with k-means reclustering (ours) in the majority of cases. For OPTDIGITS with pre-training, the “natural assignments” are outperformed by our BRB with k-means reclustering by more than 5% for DEC. For USPS without pre-training, the performance gap between BRB with k-means and “natural assignments” widens to 10%. Together with the fact that BRB improved performance over the baseline for 88.10 % of all experiments we conducted, we provide enough evidence that reclustering with k-means works well for DCN, DEC, and IDEC. From our perspective, this is expected, as both k-means and DCN, DEC, and IDEC assume spherical Gaussian clusters.

Ad W1) Applying BRB on top of more recent DC methods

The goal of our paper was to investigate the phenomenon of the “reclustering barrier” empirically and to introduce BRB as a method that can address this phenomenon in well-established centroid-based deep clustering methods like DCN, DEC, and IDEC. As the other reviewers pointed out, our empirical findings regarding the “reclustering barrier” offer new insights for the deep clustering community and are supported thoroughly by experiments. 

Nevertheless, we show the results of adding BRB to the current state-of-the-art algorithm SeCu on CIFAR10 [1]:

Importantly, BRB also leads to (small) performance improvement when added to SeCU. This result can likely be further improved by hyperparameter tuning, which we did not do for these results.

Ad W2) Hyperparameter sensitivity on another dataset

We have added hyperparameter ablation studies for two more datasets (USPS and OPTDIGITS) in Appendix E.3. Our experiments show that both USPS and OPTDIGITS are more sensitive to lower values of $\alpha$ and $T$ while still performing well for settings with higher values of $\alpha$ and $T$. Interestingly, while our highest learning rate of 0.005 does not perform well on MNIST, it seems to help with performance on USPS and OPTDIGITS, indicating trade-offs between datasets for setting these hyperparameters. Our values used for grayscale datasets in the main paper ($T=20$, $\alpha=0.8$, learning rate 0.001) are within a broad range of well-performing hyperparameters on MNIST, OPTDIGITS, and USPS.

Ad Q1) Importance of inter-CD and intra-CD

This is an excellent question. To see why using the ground truth classes for calculating the inter-CD and intra-CD is crucial, note that it is possible to place clusters arbitrarily far apart in latent space. Optimizing the clustering objective will always yield compressed and well-separated clusters, particularly for algorithms that do not use an auxiliary reconstruction loss like DEC. Therefore, these algorithms will always produce good unsupervised scores, even if we have a poor clustering result in terms of ground truth labels. The high flexibility of deep clustering algorithms regarding the embedding makes the global structure within the embedding and, therefore, unsupervised scores less meaningful. 

Figure 3 can help to build an intuition. If we were to measure inter-CD and intra-CD with the predicted cluster labels, we would get a better score before applying BRB (Stage 1, “Pre-BRB”) than after BRB (Stage 3, “Post-BRB”) due to superior cluster separation. However, using inter-CD and intra-CD with predicted labels does not account for wrongly assigned samples. BRB facilitates the re-assignment of these potentially mislabeled samples by temporarily changing the structure in the latent space, followed by reclustering. This effect can only be measured by calculating the inter-CD and intra-CD with ground truth labels.

Ad Q2) Label change without clustering accuracy change

We compute label assignments using the Hungarian method before computing the cluster label change. Therefore, purely flipping labels does not cause the behavior observed in Figure 2. Instead, the resets flip labels between certain wrongly assigned points back and forth. Due to their position in the embedded space, the reset is not strong enough to facilitate assignment to the correct cluster. Note that this is an artifact of the GTSRB dataset. For example, Figure 6 shows that cluster label changes reduce over time for MNIST. Figure 6 also shows another case (OPTDIGITS) where the cluster label changes induced by the resets affect accuracy, but the algorithm converges to a similar accuracy value. Thus, the above findings indicate that the clustering algorithm has converged to a robust solution to the perturbations caused by the soft resets.

Ad Q3) Use of true labels and calculation of metrics

BRB does not use the true labels. We use the true labels for calculating relevant metrics, e.g., clustering accuracy, which we compute after each epoch.

Dear Authors,

Thank you for addressing my concerns in your responses. However, I still have some concerns that I would like to address:

1. Regarding W2, It seems there is still room for searching the best hyperparameters across each dataset (which may end up with better results).
2. Regarding Q1, then how one can calculate inter-CD and intra-CD where the ground truth labels are not available (consider a pure unsupervised setting)? The same goes for supervised metric like accuracy, nmi etc. I believe there should be always an unsupervised metric (along with reconstruction loss so that the embedding points (and clusters) don't be meaningless) to evaluate clustering and that also should be with the predicted labels, not with the ground truth labels.
3. Regarding Q4, I don't quite get figure 17. If the accuracy goes higher, that means predicted labels are matching with the ground truth labels, right? So why, BRB outperforms baseline in respect to SC while considering ground truth but not for the predicted ones (even there are big difference specially for 17b)?
4. Regarding Q5, it seems reconstruction loss of BRB is worse than the baselines, that is another concern of the embedding points to be less meaningful.

Ad 1) Tuning hyperparameters for each dataset

We agree with the reviewer that “searching the best hyperparameters” could further improve the performance of BRB. Nevertheless, we want to emphasize that BRB’s improved performance over the various baselines in different training settings despite not tuning its hyperparameters is a clear strength and important for its practical application: As our hyperparameters work well across multiple datasets with different characteristics, practitioners can assume that they also lead to good results for the purely unsupervised setting mentioned by the reviewer.

Ad 2) Unsupervised metrics

In a pure unsupervised setting, one would likely have to rely on using predicted labels as there are no better alternatives. As we are evaluating benchmark scenarios, we have ground truth labels available and thus use widely accepted metrics (NMI, ARI, ACC) within the deep clustering literature for fairly comparing algorithms. The evaluation with ground truth labels is currently the standard procedure in deep clustering. NMI, ARI, and ACC are used to benchmark performance in papers of recent algorithms ((see [1, 2, 3]) and are recommended in up-to-date surveys ([4, 5, 6]). As per the reviewer’s request, we did include experiments showing the reconstruction loss and Silhouette score with predicted labels. We also discussed the dangers of using predicted labels (see Ad 3) of this comment and Ad Q1) in our rebuttal). The scenario outlined by the reviewer is an unsupervised model selection problem, where we must choose the best model in a purely unsupervised setting. Problems of this kind are an orthogonal area of research and require, e.g., specifically developed frameworks for hyperparameter tuning, such as [7].

Ad 3) Figure 17 “So why, BRB outperforms baseline in respect to SC while considering ground truth but not for the predicted ones”

The reviewer is right that higher accuracy implies a better match with ground truth labels. When using the predicted labels, this fact is irrelevant. A high Silhouette score with predicted labels for the baseline means that the learned clusters are compact and well-separated. This does not imply that they are a good fit for the ground truth labels, as the lower accuracy for the baseline shows. Thus, the baseline finds compact clusters but merges the wrong ground truth classes together. For BRB, the resets artificially keep the clusters more spread out in latent space (see Intra-CD and Inter-CD in Figure 2). This naturally leads to a worse Silhouette score with predicted labels due to less compact clusters but enables reassignments late in training, which allows for a better clustering given the ground truth.

Figure 3 of our paper illustrates potential problems with unsupervised metrics in latent space. “Stage 1, Pre-BRB” roughly corresponds to how the baseline clusters look like for the baseline in Appendix H.11: Well-separated given the predicted labels, but without consideration for ground truth labels. For the Silhouette score, this can lead to high values when using the predicted labels but low values when using the ground truth labels. “Stage 3, Post-BRB” corresponds to how the clustering looks like for BRB: Less compact and separated clusters. This decreases the Silhouette score using the predicted labels but allows for the reassignment of points close to the borders of the Voronoi cells late in training, improving clustering accuracy.

Ad 2, 4) Worse reconstruction loss, meaningless embedding points (and clusters)

The meaningfulness of an embedding is tied to a particular task, which, in our case, is clustering. Reconstruction can, but does not necessarily, indicate a meaningful embedding for clustering. BRB has slightly worse reconstruction loss than the baselines, making its embedding less meaningful for reconstruction tasks. This does not imply that BRB’s embedding has less meaning with respect to clustering tasks. Indeed, the improved clustering metrics such as ACC, NMI, and ARI indicate that BRB’s embedding is actually more meaningful for clustering. To further illustrate this point, consider the deep clustering algorithm DEC, which is one of the algorithms we use in our experiments. DEC does not use any reconstruction loss during the clustering phase but can still learn meaningful embeddings that correspond to the ground truth labels despite a growing reconstruction loss. We currently cannot edit the submission, but for the camera-ready version of our paper, we will include reconstruction loss plots for DEC to illustrate this point.

Dear Reviewer XSEo,

thank you for your response. We are glad that we could further clarify your concerns.

To address your last remaining concern regarding the relationship of reconstruction loss and clustering performance (meaningfulness of an embedding), we have conducted the following experiment:

We compare the performance in terms of clustering accuracy (ACC) and reconstruction loss (REC-Loss) of the deep clustering methods DEC and IDEC averaged over 10 runs below. Note, that DEC and IDEC are almost identical algorithms, except that IDEC keeps the reconstruction loss after pretraining. The comparison between DEC and IDEC thus shows the importance of the reconstruction loss in relation to the clustering accuracy.

If the reconstruction loss is the only thing that determines how meaningful an embedding is, then DEC should not be able to capture any meaningful cluster information and perform much worse than IDEC. However, from the tables below we see that while the REC-Loss of DEC is between 10 to 1000 times larger than the REC-Loss of IDEC it still performs well overall. For the datasets OPTDIGITS, GTSRB and FMNIST DEC clearly outperforms IDEC, even though the REC-Loss is several orders of magnitude higher.

We will include this discussion on the importance of the reconstruction loss into the camera ready version of our paper, and hope this sufficiently alleviates your last remaining concern regarding our work. If so, please consider increasing your score.

Dear Authors,

Thank you for further addressing my concerns. I do not have any other concern to discuss. It would be good to see discussion on reconstruction loss in the revision.

We are thrilled to hear the reviewer’s positive feedback regarding our work! In particular, we are glad about the reviewer’s assessment regarding our analysis and ablations.

Ad) Minor weaknesses

We thank the reviewer for thoroughly reading our paper. The typos they pointed out are now corrected. Additionally, we fixed the DOIs in the updated version of our paper.

Ad) Harder datasets, CIFAR100 clustering

The focus of our evaluation is broadly two-fold. First, we evaluate various simpler datasets (MNIST, KMNIST, USPS, FMNIST, OPTDIGITS, and GTSRB) to understand the effects of BRB under different conditions in a unified benchmarking environment. Second, we show that the combination of BRB and DEC, IDEC, and DCN can achieve surprisingly strong performance on well-established benchmarks for image clustering.

We use CIFAR10 and CIFAR100-20 because these are the most commonly used image clustering benchmarks. They have moderate computational requirements and allow us to evaluate BRB against a range of relevant competitors. Clearly, using the more realistic real-world datasets such as iNaturalist and BIOSCAN is an exciting direction for future work. However, evaluating our method on them is beyond the scope of our work due to a lack of well-established benchmarks for clustering algorithms on these datasets. Lastly, we want to point out that our baseline methods have been used for different types of real-world data already, as we point out in our introduction. Some of these include challenging datasets, such as noisy financial data [1] or medical data with missing values [2].

[1] Choi, Stephen, and Tyler Renelle. "Deep learning price momentum in US equities." 2019 International Joint Conference on Neural Networks (IJCNN)

[2] Kalweit, Maria, et al. "Patient groups in Rheumatoid arthritis identified by deep learning respond differently to biologic or targeted synthetic DMARDs." PLOS Computational Biology 19.6 (2023)