Breaking the Reclustering Barrier in Centroid-based Deep Clustering

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.

Published as a conference paper at ICLR 2025 is not enough to enable late-training improvements to the clustering because it fails to change the structure of the underlying embedded space. A bad initial representation or clustering exacerbates the effect and potentially decreases final performance by more than 10%, as our experiments demonstrate. When a clustering algorithm cannot improve late in training despite frequent reclustering, we refer to this as the reclustering barrier.

But can we overcome the reclustering barrier? Yes, as we show in Figure 1 for the centroid-based DC method IDEC with reclustering, without reclustering, and with our proposed approach. Our novel method, BRB, can Break the Reclustering Barrier (BRB). After 100 epochs, BRB breaks through the plateau that cannot be surpassed by the competitors even after 400 additional epochs of training. By analyzing the evolution of the latent space during clustering, we identify a lack of change in the embedding as the primary cause of reclustering's limited effectiveness. BRB combines reclustering with a carefully designed weight reset, leveraging a synergistic effect between these algorithmic components. This synergy creates a virtuous cycle between generating new clustering targets and adapting to them, enabling our method to escape suboptimal performance plateaus. At the same time, BRB is easy to implement and compatible with a wide range of centroid-based DC algorithms.

Our experiments show that despite its simplicity, BRB improves the performance of the widely-used centroid-based DC algorithms DEC (Xie et al., 2016), IDEC (Guo et al., 2017), and DCN (Yang et al., 2017) across a diverse set of benchmarks. When combined with contrastive learning and self-labeling (Gansbeke et al., 2020), BRB even pushes DEC, IDEC, and DCN to state-of-the-art performance. With BRB, these algorithms find good clustering solutions even without the usual pre-training, effectively escaping the reclustering barrier. To summarize our contributions:

• We propose BRB, a novel algorithm that can break through existing performance plateaus in centroid-based deep clustering.

• We empirically identify the underlying causes of the reclustering barrier and explain the success of BRB: It preserves the variation within clusters in early training and increases exploration of diverse clustering solutions.

• We apply BRB on top of several deep clustering algorithms, yielding robust performance improvements across a wide range of datasets and setups. With contrastive learning and selflabeling, BRB achieves competitive performance compared to state-of-the-art approaches.