Breaking the Reclustering Barrier in Centroid-based Deep Clustering

Authors: Lukas Miklautz, Timo Klein, Kevin Sidak, Collin Leiber, Thomas Lang, Andrii Shkabrii, Sebastian Tschiatschek, Claudia Plant
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: deep clustering, unsupervised learning, representation learning

Abstract:
This work investigates an important phenomenon in centroid-based deep clustering (DC) algorithms: Performance quickly saturates after a period of rapid early gains. Practitioners commonly address early saturation with periodic reclustering, which we demonstrate to be insufficient to address performance plateaus. We call this phenomenon the “reclustering barrier” and empirically show when the reclustering barrier occurs, what its underlying mechanisms are, and how it is possible to Break the Reclustering Barrier with our algorithm BRB. BRB avoids early over-commitment to initial clusterings and enables continuous adaptation to reinitialized clustering targets while remaining conceptually simple. Applying our algorithm to widely-used centroid-based DC algorithms, we show that (1) BRB consistently improves performance across a wide range of clustering benchmarks, (2) BRB enables training from scratch, and (3) BRB performs competitively against state-of-the-art DC algorithms when combined with a contrastive loss. We release our code and pre-trained models at https://github.com/Probabilistic-and-Interactive-ML/breaking-the-reclustering-barrier .

Decision: accept (poster)
Reviewer scores: 8, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1729305642695

thread_type:
official_review

<thread_object>
creator: reviewer_jvba

<content>
summary:
The paper addresses the problem in deep clustering of early over-commitment to sub-optimal partitions. They propose a method to combat this by periodically modifying the network weights and reclustering.

strengths:
The considered problem is an important one, and is reasonably well introduced the paper.

The method is intuitive.

The experimental results on CIFAR looking convincing.

There is some helpful surrounding discussion of how the method works to improve accuracy, e.g. Figures 6 and 7.

weaknesses:
The method itself is intuitive but maybe a bit simple--just slightly modifying the weights and then reclustering. The weight reset comprises two parts: contracting the current values and then adding noise. It would be good to compare the reset as per Eq (1) to just adding noise to the weights, from the same or similar distribution as the weight distribution (at least the same mean and variance). This would determine whether the contraction part is doing anything.

The comparison to SOTA methods on Cifar is reasonably convincing, but there's no such comparison on MNIST, KMNIST, USPS, FMNIST, OPTDIGITS and GTSRB. Does that mean your results are substantially worse than SOTA on those datasets?

Some information from the appendices would be better placed in the main paper. The paragraph 'implementation details' is mostly just pointers to various sections in the lengthy appendices, when it could just give the details directly. Specifically, it would be good to specify (1) the initial weight distribution, (2) the frequency across epochs that you performing resetting, and (3) which image augmentations and how exactly they are used. Presumably you just create multiple augmentations for each image and enforce them all to be in the same cluster, but I wasn't sure.

questions:
What is the initial weight distribution? As this is a part of the reset mechanism, it should be specified in the main paper.

For the main results, how frequently do you reset?

Which image augmentations do you how and how exactly are they put to use?

How does your method compare to SOTA on MNIST, KMNIST, USPS, FMNIST, OPTDIGITS and GTSRB?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730079958930

thread_type:
official_review

<thread_object>
creator: reviewer_vgyg

<content>
summary:
This paper addresses the issue of rapid early performance gains followed by quick saturation in deep clustering (DC). It introduces the concept of the "reclustering barrier" and explores when and why this phenomenon occurs. To overcome it, the authors propose the Break the Reclustering Barrier (BRB) algorithm, which avoids early over-commitment to initial clusters and allows continuous adaptation to reinitialized targets. The paper demonstrates that BRB improves performance across several clustering benchmarks.

strengths:
- The paper addresses an important issue in deep clustering, performance saturation.
- The writing is smooth and easy to follow, with the primary contributions well-communicated.
- The empirical evaluation is thorough, and the BRB algorithm is shown to enhance performance across benchmarks.

weaknesses:
1. While the concept of reclustering is mentioned early in the paper, the term can carry specific meanings in the context of deep clustering. Typically, reclustering refers to periodically or iteratively reassigning data points to clusters. However, since DC algorithms inherently involve iterative steps of representation learning and clustering, the authors should better contextualize their use of the term. 

2. Building on the previous point, many existing DC methods already incorporate some form of iterative clustering. As such, the distinction between "DC" and "DC+Recluster" groups in the paper’s figures could be unclear. The authors should explicitly explain what differentiates these two groups and how their use of reclustering is unique. This will help readers better interpret these figures.  

3. The core innovation of BRB lies in its use of weight resets, which the paper notes is inspired by a technique from reinforcement learning. Weight resetting is also known as a popular regularization technique in deep learning, where a portion of layer weights is periodically reinitialized during training. While applying this idea to deep clustering is somewhat novel, this contribution could be perceived as incremental. 

4. Some choices in the implementation seem empirical. For example, the authors mention resetting only the last ResNet block and the MLP encoder, and they use hyperparameters such as LR = 0.001, alpha = 0.8, and T = 20. While these values are derived from extensive experimentation, it would strengthen the work to provide more intuitive or theoretical justification for these decisions. This would also make it easier to generalize the choice of hyperparameters (especially alpha) to other settings and DC algorithms.  

5. The algorithms tested in the experiments are relatively older. The authors are encouraged to apply BRB to more recent deep clustering methods to better demonstrate its effectiveness and relevance. This would enhance the impact of the work and align it with the latest advancements in the field.  

6.  The paper uses widely-known data augmentation techniques such as contrastive learning and self-labeling, which are not novel,  in the main results. Therefore, combining these techniques and comparing BRB with SOTA algorithms like SCAN, GCC, and SeCu may not represent a fully fair comparison. The authors should clarify whether the improvements stem from BRB itself or the use of these auxiliary techniques, ensuring a more balanced evaluation of the proposed method.

Minor:
Some grammar error:  (line 128) Its output are => its output is

questions:
In addition to the questions raised in the Weaknesses section:

1. alpha is a critical hyper parameter. From Figure 8, it appears that α = 0.9 yields better performance across various settings. It is unclear why the authors recommend α = 0.8 instead. Additionally, should the choice of α = 0.9 or 0.8 remain consistent across all DC algorithms, or is there room for algorithm-specific tuning? Clarifying whether this parameter can or should be personalized for different algorithms would enhance understanding.

2. How does the approach extend to deep clustering methods that are not centroid-based?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730718634974

thread_type:
official_review

<thread_object>
creator: reviewer_xseo

<content>
summary:
The paper discusses 'reclustering barrier', a common and important phenomenon that occurs in centroid-based deep clustering methods, where performance quickly saturates in the very early stage of the training phase. The authors carefully discuss when and why reclustering barrier happens and propose BRB which prevents this early commitment to initial clustering and gain performance over the training with the reinitializing clusters after every few epochs. They apply BRB on top of several existing deep clustering methods to verify its advantage. The paper contains simulation results to support its main claims.

strengths:
### SIGNIFICANCE:
This work is important because it seeks to overcome an important phenomenon commonly seen in centroid based deep clustering methods and this can be studied further over other recent deep clustering methods (also not centroid based as they may also face the similar issue).

### ORIGINALITY:
This work is novel because it demonstrates the application of BRB over some existing methods that improves the performance further.

### CLARITY:
This work is well-written and well-organized. It clearly explains the key components of the method and their functions. For example, the discussion about the hyperparameter $T$, $\alpha$ and learning rate is complete and important for the reproducibility and understanding of this work. In addition, I also have some questions regarding this method (see the next section).

### QUALITY:
The quality of this work is good. The work includes carefully designed simulations that are sufficient to support the claim of the paper.

weaknesses:
1. The biggest weakness is the baselines (on top of which BRB has been applied) are too old to compare, the latest one is from 2017. It would be good to see applying BRB on top of one or two recent DC method (like SCAN, GCC or SeCu mentioned in the paper) and report those results. This would provide a clearer comparison to the state-of-the-art.

2. Hyperparameter sensitivity. It would be good to report similar hyperparameters (T, α and learning rate) sensitivity (figure 8) to other one or two datasets besides MNIST.

questions:
1. You are computing inter-CD and intra-CD to measure variation within ground truth classes (for example, in figure 2). Why is this so important? What about this metrics for the predicted clustering by BRB? I suggest to include a comparison of these metrics for both ground truth classes and predicted clusters, which would provide a more complete picture of BRB's performance.

2. Again for figure 2, it seems even after 400 epochs the clustering labels are changing, but the accuracy is not. What is happening here? Are the clustering labels flipping only?

3. Is BRB optimizing based on the clustering metric (say accuracy)? Or is it updating for a specific epochs (say 500) and after that you are computing the relevant metrics? In other words, is BRB using trues labels while training? At what points the evaluation metrics are computed?

4. Accuracy, NMI or ARI, all of these metrics are supervised and need true labels. However, in practice, we don't have any true labels to compute these metrics. Can you include some unsupervised metric (say Silhouette Coefficient) in your evaluations and comparisons, in addition to the supervised metrics? This would provide insight into the method's performance in more realistic unsupervised scenarios.

5. As BRB modifying the encoding space after each reclustering step, the encoding space may degrade and may not represent the original data point anymore, did you verify it with the original data point with reconstruction loss? I suggest to report reconstruction loss for one or two datasets comparing to baselines, which would help to understand the underlying encoding structure.

6. Momentum resets section is not clear enough, can you elaborate more like how are you exactly re-initializing the momentum for the cluster centers after reclustering?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730932361177

thread_type:
official_review

<thread_object>
creator: reviewer_xowl

<content>
summary:
The authors explore a (known) problem when training a clustering model from scratch as follows. The architecture has an encoder followed by a clustering head. With end-to-end optimization, the encoder is updated by the gradients which flow back to it through the clustering head. This means that if and when the clustering head is saturated at a local minima, the encoder will stop learning. This can happen before the encoder has learnt a good encoding, resulting in a model which ceases to learn further despite performing poorly.

The authors demonstrate the problem, their method (a periodic weight perturbation strategy with cluster centroid reinitialization), show experiments comparing against relevant baselines, and analyze the behavior of their method.

strengths:
The problem is well presented and salient to the field. As far as I am aware, the proposed method is novel. The analysis is thorough, with ablations as well.

weaknesses:
It would be better if the work studied some harder datasets/tasks, such as ImageNet-1k or some taxonomic image datasets (iNaturalist, BIOSCAN, etc.). A lot of the datasets considered are simpler digit classification datasets. The work could be further improved by evaluating on other modalities.

**Minor points**

Some references are badly formatted and need some attention to correct them.
- Incorrect casing ("em algorithm", "hungarian method", "Spagcn", "rna")
- DOIs shouldn't include the domain name and should actually be links (the latter is fixed by importing the latex `doi` package in main.tex) "DOI: https://doi.org/10.24432/C50P49" -> "doi:[10.24432/C50P49](https://doi.org/10.24432/C50P49)". When the DOI is a link, you don't need to also include the URL field.
- It's good for readers if you can include links in the references (ideally as DOIs) as much as possible, so the reader can easily navigate to the article being cited (and know they are looking at the work you meant to cite)

questions:
Why do the authors only consider the CIFAR100 supersets (CIFAR100-20) instead of clustering 100 classes?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732377911595

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response

comment:
We thank the reviewers for their time, thoughtful comments, and valuable suggestions for improving the paper. We appreciate the positive comments regarding the presentation of our manuscript. Their comments highlight the novelty and thorough motivation behind our work. We are pleased that the reviewers recognize the comprehensiveness of our experimental analysis, showing the effectiveness of our method BRB in addressing the challenge of early cluster performance saturation.

We respond to each reviewer in detail below. In the following, we briefly summarize the improvements to our work:

- We clarified several aspects of our method by adding more detail on how we recluster, how we perform momentum and weight resets, and how we use augmentations. We also disambiguated the term reclustering more thoroughly.
- We added additional hyperparameter sensitivity experiments for two datasets, USPS and OPTDIGITS.
- We included experiments using the predicted labels for the silhouette score on USPS and GTSRB.
- We added a figure in the Appendix showing the reconstruction loss behavior when performing resets on OPTDIGITS.
- We performed an additional ablation on the importance of the contraction of our soft resets on OPTDIGITS and USPS.
- We implemented BRB on top of a more modern algorithm, showing performance improvements.

Our manuscript has been updated accordingly.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732511185734

thread_type:
official_comment

<thread_object>
creator: area_chair_m76f

<content>
title:
The author-reviewer discussion period is ending soon

comment:
Dear reviewers,

If you haven’t done so already, please engage in the discussion as soon as possible. Specifically, please acknowledge that you have thoroughly reviewed the authors' rebuttal and indicate whether your concerns have been adequately addressed. Your input during this critical phase is essential—not only for the authors but also for your fellow reviewers and the Area Chair—to ensure a fair evaluation.
Best wishes,
AC
</content>
</thread_object>

</thread>
<thread>
creation date:
1733309877336

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Second General response

comment:
We thank all the reviewers for their contributions and valuable feedback on our work. Their thoughtful questions resulted in a highly relevant discussion and improved our paper. We believe we satisfied most of the reviewers’ concerns through extensive additional experiments and further clarification. Below is a summary of our takeaways from the discussion phase:

- Reviewer XSEo mainly had questions regarding our evaluation metrics and hyperparameters. We included the desired metrics and supported our choice of using clustering accuracy (ACC), Normalized Mutual Information (NMI), and Adjusted Rand Index (ARI) both with literature and empirically. We added hyperparameter sensitivity analyses on two more datasets. The reviewer indicated that our answers fully addressed their concerns.
- Reviewer VgYg raised concerns about the reclustering step of BRB, our hyperparameter choices, BRB with SOTA algorithms, and our evaluation setup. In reply, we clarified the term reclustering in our manuscript. We provided extensive details on the reclustering step and additional experiments that further justified our design choices for BRB. Moreover, we added new hyperparameter sensitivity experiments and clarified the intuition behind these hyperparameters. Lastly, we addressed the concerns regarding our evaluation setup and provided results for combining BRB with a SOTA algorithm. With our experiments and analysis of the “natural assignment process” vs. k-means cluster assignments, we have addressed the reviewer’s remaining major concern.
- Reviewer JvBA was concerned with the form of our weight reset, SOTA results, and the clarity of our presentation. We conducted an ablation study according to the reviewer’s specifications, supporting the use of soft resets, and added additional information to our main paper. Furthermore, we discussed our experiment setups and implementation specifics in more detail and added experiments with BRB and a SOTA deep clustering algorithm. According to the reviewer, we answered all of their questions.
- Finally, we answered the questions of reviewer xoWL.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper examines a pathological issue in certain centroid-based deep clustering methods, referred to as a reclustering barrier, and proposes a straightforward yet effective solution. While the analysis is not rigorous, the paper offers an intuitive explanation for the reclustering barrier, and the suggested remedy consistently enhances the baselines across various benchmark datasets. Some concerns were raised regarding the clarity of the term "reclustering"; however, the authors’ rebuttal appears to address this to some extent. I strongly encourage the authors to incorporate the additional comments from the reviewers in the final version of the manuscript.