Breaking the Reclustering Barrier in Centroid-based Deep Clustering

## Abstract

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 B reak the R eclustering B arrier 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 .

### 1 Introduction

Figure: Figure 1: Breaking the reclustering barrier with BRB. Uniting the deep clustering method IDEC with BRB (IDEC+BRB) breaks through the performance barrier (dashed line) encountered when just using IDEC or combining it with periodic reclustering (IDEC+Recluster). Performance is measured by clustering accuracy on USPS.
Refer to caption: x1.png

“To live is to change; to be perfect is to change often” (Newman, ): Though not originally about ML, this proverb underscores the importance of adaptability.
This adaptability is critical for the success of machine learning algorithms, especially during training. It is particularly crucial in clustering — a family of unsupervised learning algorithms that partition samples into multiple groups based on their similarity. Deep clustering (DC) involves not only assigning samples to a particular group but also jointly learning a representation of the data using deep learning. As this representation improves, the algorithm enhances its ability to identify clusters in the data, requiring it to adjust its assignments frequently.

In this paper, we analyze whether centroid-based DC algorithms can sufficiently adapt during training to facilitate further improvements. The central finding of our analysis is that they cannot and that commonly used techniques, such as reclustering with $k$-Means, are insufficient to address this issue. Specifically, we find that reclustering by itself 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 from 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., ), IDEC (Guo et al., ), and DCN (Yang et al., ) across a diverse set of benchmarks. When combined with contrastive learning and self-labeling (Gansbeke et al., ), 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 self-labeling, BRB achieves competitive performance compared to state-of-the-art approaches.

###### Research focus

Centroid-based deep clustering is a highly active research area intersecting with various fields. For instance, the current state-of-the-art image clustering technique SeCu (Qian, ) is centroid-based. Self-supervised learning uses prototypes, like centroids, for representation learning (Asano et al., ; Caron et al., ; ; ). This study concentrates on established centroid-based DC algorithms, specifically DEC, IDEC, and DCN, which are widely used in diverse domains such as biology (Li et al., ; Hu et al., ; Luo et al., ), medicine (Wachowiak et al., ; Kalweit et al., ) or finance (Choi & Renelle, ). These algorithms also form the foundation for several recent DC methods (Qian, ; Li et al., ). Enhancing DEC, IDEC, and DCN could significantly impact multiple research fields and accelerate progress on downstream applications. With this context, we proceed to discuss some background and related work.

### 2 Background and Related Work

Deep clustering (DC) is the combination of clustering and deep learning. Popular deep learning approaches for DC include self-supervised networks such as autoencoders (AEs), or SimCLR (Chen et al., ) as they can be trained without given labels. The idea of centroid-based DC is to obtain an initial clustering, typically by running the clustering algorithm $k$-Means in the latent space of a pre-trained network. The algorithm proceeds to update this result by optimizing $L(\theta,\mathbf{\bm{M}})=\lambda_{1}L_{SSL}(\theta)+\lambda_{2}L_{C}(\theta,
\mathbf{\bm{M}})$, where $L_{C}$ refers to the clustering loss and $L_{SSL}$ refers to the self-supervised loss (e.g., contrastive or reconstruction loss, for SimCLR and AE respectively). Here, the embedding and the clustering can be updated simultaneously or iteratively (Zhou et al., ).
A well-known representative utilizing simultaneous optimization is DEC (Xie et al., ). It uses a kernel based on the Student’s t-distribution to minimize the Kullback-Leibler divergence between the data distribution and an auxiliary target distribution, which can be trained end-to-end.
As $L_{SSL}$ is not used during the clustering optimization, a distorted embedding could occur (Guo et al., ). This issue is tackled by IDEC (Guo et al., ), which concurrently optimizes $L_{C}$ and $L_{SSL}$.
DCN (Yang et al., ) pursues an iterative optimization, where the embedding is frozen when the clustering is updated, and vice versa. Since the cluster centers are not learned via the neural network but explicitly updated, it is feasible to use $k$-Means to obtain non-differentiable hard cluster labels. The well-established algorithms DEC, IDEC, and DCN are the building blocks for a number of follow-up works and have diverse applications, making them a natural choice for this study.
We provide more details on these algorithms in Appendix B.1.

Contemporary DC methods broadly fall into two groups. The first group is focused on image clustering (Gansbeke et al., ; Dang et al., ; Li et al., ; Zhong et al., ; Qian, ) and leverages domain knowledge, such as augmentations. The second group consists of data-agnostic DC methods, like DEC, IDEC, and DCN or (Miklautz et al., ; Leiber et al., ; Mahon & Lukasiewicz, ) that do not rely on augmentations. For a more detailed overview of DC algorithms, see (Ren et al., ; Zhou et al., ).

### 3 Problem Setup

Given an unlabeled dataset $\mathcal{X}=\{\mathbf{\bm{x}}_{i}\}_{i=1}^{n}$ containing $n$ instances $\mathbf{\bm{x}}_{i}\in\mathbb{R}^{D}$, our objective is to partition $\mathcal{X}$ into $k$ distinct clusters. Each cluster is represented by a centroid $\mathbf{\bm{\mu}}_{j}\in\mathbb{R}^{d}$, with $j\in\{1,\ldots,k\}$. This partitioning requires learning assignments $s_{i,j}\in\{0,1\}$ of instances $\mathbf{\bm{x}}_{i}$ to centroids $\mathbf{\bm{\mu}}_{j}$ subject to $\sum_{j=1}^{k}s_{i,j}=1$ for all $i$. Additionally, *deep* clustering methods aspire to learn a “cluster-friendly” (Yang et al., ) latent feature space $\mathcal{H}\subseteq\mathbb{R}^{d}$, where $d\ll D$ utilizing a non-linear encoder $f_{\theta}\colon\mathcal{X}\rightarrow\mathcal{H}$. For example, a $k$-Means friendly latent space consists of compressed spherical clusters (low intra-cluster distance) that are well-separated (high inter-cluster distance).

Many methods utilize a self-supervised auxiliary objective to prevent trivial solutions in DC, e.g., by including a reconstruction or contrastive loss in addition to the clustering loss. This auxiliary objective is applied in a task-dependent output space $\mathcal{Z}$ and is often learned with a separate task head $g\colon\mathcal{H}\rightarrow\mathcal{Z}$. In the case of reconstruction, the function $g$ serves as a decoder network, where $\mathcal{Z}\subseteq\mathbb{R}^{D}$ corresponds to the space of reconstructed data points. For contrastive learning, $g$ acts as a projector network (e.g., a shallow MLP), where $\mathcal{Z}$ is the projector’s output space.

A deep centroid-based clustering algorithm as outlined above can be formalized as the iterative application of a function $\mathcal{C}\colon(\theta_{t},\mathbf{\bm{S}}_{t},\mathbf{\bm{M}}_{t})\mapsto(
\theta_{t+1},\mathbf{\bm{S}}_{t+1},\mathbf{\bm{M}}_{t+1})$. Here, $\theta_{t}\in\Theta$ represents the network parameters at step $t$, $\mathbf{\bm{M}}_{t}\in\mathbb{R}^{k\times d}$ the centroid matrix and $\mathbf{\bm{S}}_{t}\in[0,1]^{n\times k}$ a matrix encoding the cluster assignments for each sample. The function $\mathcal{C}$ optimizes a clustering objective $L(\theta_{t},\mathbf{\bm{S}}_{t},\mathbf{\bm{M}}_{t})\colon\Theta\times[0,1]^{
n\times k}\times\mathbb{R}^{k\times d}\rightarrow\mathbb{R}$, utilizing a gradient-descent optimizer. Its output are improved parameters $\theta_{t+1}$ as well as new assignments $\mathbf{\bm{S}}_{t+1}$ and centroids $\mathbf{\bm{M}}_{t+1}$. Typically, $\mathcal{C}$ is iterated until a local minimum of $L(\theta,\mathbf{\bm{S}},\mathbf{\bm{M}})$ is reached.

### 4 The Reclustering Barrier

Figure: Figure 2: Why does reclustering not work? DCN with reclustering (orange line) shows minimal changes compared to unmodified DCN (blue line) in the embedded space (intra/inter-CD) or explored clusterings (CL Change) for GTSRB. This effect generalizes to other datasets (Figure 6).
Refer to caption: x2.png

Before introducing BRB in Section 5, we examine why reclustering by itself fails to enhance performance beyond a certain threshold during DC training. We assess the effect of reclustering on the embedded space using intra-class distance (intra-CD) to measure variation within ground truth classes and inter-class distance (inter-CD) to assess separation between ground truth classes; this follows the embedding space analysis in (Lehner et al., ). We quantify the impact of reclustering on the clustering targets by the *cluster label change* (CL Change) between epochs in terms of the normalized mutual information (NMI) (Kvalseth, ) as $\left(1-\operatorname{NMI}(\mathbf{\bm{S}}_{t},\mathbf{\bm{S}}_{t-1})\right)
\cdot 100$. A value of 0 means no change between two consecutive clusterings, while a value of 100 indicates complete change. Figure 2 tracks these three metrics and the clustering accuracy (Yang et al., ) with BRB application every $T=20$ epochs on the GTSRB dataset (^1^11Section 6.1 describes all datasets used in this work in detail.).

Figure: Figure 3: The effect of BRB during training of DEC. *(1) Pre-BRB*: Before BRB is applied, DEC strongly compresses (low variation within clusters) the five shown clusters and mixes different ground truth classes of USPS (indicated by color), leading to a performance plateau (cf. epochs 46 to 50 in the NMI plot). *(2) BRB* applies weight reset to increase the variation in the clusters with subsequent reclustering, which leads, after a small performance drop in NMI (epoch 51), to a steep increase (epochs 52 to 59). *(3) Post-BRB*: After applying BRB, the clusters are compressed again by DEC until BRB is applied another time.
Refer to caption: extracted/5976891/media/BRB_fig3_v3.png

Although reclustering marginally enhances clustering accuracy (orange line), it does not substantially alter the embedded space: the intra-CD and inter-CD are almost the same at the end of the training, irrespective of whether reclustering is applied. Correspondingly, the CL Change is largely unaffected by the reclustering, indicating only marginal differences in the obtained clustering solutions. These findings suggest that if we want to further improve performance, we require larger and better-structured changes in the embedded space to systematically impact the clustering. In contrast to only reclustering, BRB induces such changes and is able to improve the clustering performance (black line in Figure 2). Figure 3 schematically illustrates the changes caused by BRB in the embedded space. In Section 5, we describe how our approach, BRB, effectively introduces such changes.

### 5 Our Approach - BRB

Our goal with this work is to overcome the reclustering barrier in a centroid-based deep clustering algorithm $\mathcal{C}$. To this end, we establish three desiderata for our approach:

- 1.
*Exploration*: The proposed modification should increase the exploration of clustering solutions.
- 2.
*Knowledge preservation*: The knowledge encoded in network parameters $\theta$ should be preserved while exploring a wider range of solutions.
- 3.
*Generality*: The proposed modification should be applicable to existing DC approaches.

We now define our modified algorithm as

$$ $\displaystyle\mathcal{C}_{\mathrm{BRB}}\colon(\theta_{t},\mathbf{\bm{S}}_{t}, \mathbf{\bm{M}}_{t})\mapsto\mathcal{C}(\iota_{w}\left(\theta_{t}\right),\iota_ {c}\left(\mathbf{\bm{S}}_{t},\mathbf{\bm{M}}_{t})\right),$ $$

consisting of two modifications $\iota_{w}$ and $\iota_{c}$ as well as optional momentum resets, each impacting different components of the deep clustering algorithms.

###### Weight resets

Section 4 motivates the need for structured changes in the embedded space to enable effective reclustering. BRB achieves such changes by applying a soft weight reset (Ash & Adams, ; D’Oro et al., ) to the the non-linear encoder $f_{\theta_{t}}$. In particular, we obtain modified parameters $\tilde{\theta_{t}^{i}}$ through a convex combination of the network’s prior parameters and freshly sampled weights (D’Oro et al., ), denoted as $\iota_{w}(\theta_{t}^{i})$:

$$ $\displaystyle\tilde{\theta_{t}^{i}}=\iota_{w}(\theta_{t}^{i})=\alpha\theta_{t} ^{i}+(1-\alpha)\phi^{i},$ (1) $$

where $\theta_{t}^{i}$ are layer $i$’s weights at step $t$, $\phi^{i}$ is sampled from the initial weight distribution and $\alpha\in(0,1)$ is a hyperparameter. This strategy balances the need for inducing changes in the embedding function $f_{\theta_{t}}$ to escape local minima while preserving previously learned information.
While Equation 1 outlines a particular reset strategy, our approach is capable of accommodating different reset techniques, such as adding noise (cf. Section 6.3) or layer-wise resets (Alabdulmohsin et al., ). We discuss our choices in the paragraph “Implementation details” later in this section.

###### Reclustering

Applying a weight-reset $\iota_{w}(\theta_{t})$ to the encoding function $f_{\theta_{t}}$ induces a shift in embeddings: $f_{\tilde{\theta_{t}}}(\mathbf{\bm{X}})=\tilde{\mathbf{\bm{H}}}_{t}\neq\mathbf
{\bm{H}}_{t}=f_{\theta_{t}}(\mathbf{\bm{X}}).$ Consequently, the centroids $\mathbf{\bm{M}}_{t}$ at clustering step $t$ do not accurately characterize the cluster centers for $\tilde{\mathbf{\bm{H}}}_{t}$. We address this issue by proposing to recalculate the centroids based on the updated embedding matrix $\tilde{\mathbf{\bm{H}}}_{t}$:

$$ $\displaystyle\tilde{\mathbf{\bm{S}}}_{t},\tilde{\mathbf{\bm{M}}}_{t}=\iota_{c} (\mathbf{\bm{S}}_{t},\mathbf{\bm{M}}_{t},\tilde{\theta_{t}})=\mathrm{recluster }\left(f_{\tilde{\theta_{t}}}(\mathbf{\bm{X}})\right)$ (2) $$

Here, $\tilde{\mathbf{\bm{M}}}_{t}$ denotes the centroid matrix obtained from reclustering with the perturbed embeddings $f_{\tilde{\theta_{t}}}(\mathbf{\bm{X}})=\tilde{\mathbf{\bm{H}}}_{t}$ and $\tilde{\mathbf{\bm{S}}}_{t}\in[0,1]^{n\times k}$ represents the corresponding assignments. Note that any centroid-based method such as $k$-Means (Lloyd, ) or $k$-Medoids (Rdusseeun & Kaufman, ) works for the $\mathrm{recluster}$ operation.

###### Momentum resets

DEC and IDEC parameterize and iteratively refine cluster centers through gradient descent. However, integrating momentum-based optimization with weight resets and reclustering may introduce misalignment between momentum terms and re-calculated centroids, for which we provide ablations in Appendix H.2. To mitigate this, we propose re-initializing the momentum for the cluster centers after reclustering. This aligns gradient steps and recalculated centroids, preventing the moment estimates from diverging and harming task performance (Lyle et al., ). For DCN, which does not parameterize centroids, momentum resets are unnecessary.

###### Implementation details

The pseudo-code in Algorithm 1 shows how BRB is added to the training loop of an exemplary DC algorithm, highlighting its straightforward implementation and minimal overhead. We use four key implementation details for BRB that we highlight in the following.

- (1)
Resetting the encoder’s final embedding layer can adversely affect performance due to excessive perturbations in the latent space (see Appendix H.1). We observe a similar phenomenon in deep CNN architectures like ResNet (He et al., ), where resetting all layers also induces excessive perturbations (see Appendix  H.3). Our solution is to only reset the last ResNet Block and the MLP encoder.
- (2)
We introduce a reset interval hyperparameter $T$ and reset only every $T$-th epoch. For the reclustering step, we use the $k$-Means algorithm (Lloyd, ) due to its simplicity, performance, and speed. Appendix Table 10 shows a runtime comparison of different reclustering algorithms, while Appendix Table 12 shows a performance comparison.
- (3)
We sub-sample the dataset when reclustering to enhance computational efficiency. We use a subsample size of 10,000 for all datasets, which leads to a negligible runtime overhead of approximately 1.1% when using BRB. In Tables 4 and 9 in Appendix G, we analyze the impact of the subsample size on clustering accuracy and runtime performance in detail.
- (4)
Using image augmentation is a common enhancement for DC algorithms, and we find it complements BRB as well.

### 6 Experiments

We integrate BRB into DEC, IDEC, and DCN, presenting experiments that demonstrate the performance improvements resulting from this integration for a wide range of datasets. The first part of our analysis describes the datasets and setups used in our experiments. We then proceed to benchmark BRB against unmodified versions of DEC, IDEC, and DCN in three scenarios: With and without pre-training and with a contrastive auxiliary task. Then, we dig deeper into the underlying mechanisms of BRB and examine how it is able to break the reclustering barrier. Overall, we find that BRB improves performance in 88.10 % of all runs while incurring a minimal runtime overhead of approximately 1.1 %.(^2^22Appendix G provides a detailed theoretical and empirical runtime analysis.)

#### 6.1 Experiment setup and datasets

We evaluate the effectiveness of BRB on eight commonly used datasets for deep clustering, which we split into two different groups and use a different setup for each. Details regarding the datasets and the preprocessing can be found in Section Appendix C. The first group consists of MNIST (LeCun et al., ), KMNIST (Clanuwat et al., ), FMNIST (Xiao et al., ), USPS (Hull, ), OPTDIGITS (Alpaydin & Kaynak, ), and GTSRB (Stallkamp et al., ), where we use a feed-forward autoencoder and reconstruction as an auxiliary task. For these datasets, we use the same learning rate of 0.001 and use the same BRB hyperparameters $\alpha=0.8$ and $T=20$ across all algorithms and experiment setups. The second group consists of CIFAR10 and CIFAR100-20 (Krizhevsky et al., ), which are more challenging color image datasets, where we employ SimCLR (Chen et al., ) as an auxiliary task. Following the setup of (Qian, ), we use a Resnet18 (He et al., ) encoder and employ self-labeling (Gansbeke et al., ) after deep clustering. Appendix E describes the exact setup for each experiment.

Given the datasets outlined above, we evaluate DEC, IDEC, and DCN with and without BRB in three scenarios:
(1) starting from a representation pre-trained with reconstruction as an auxiliary task,
(2) training from scratch with reconstruction as an auxiliary task, and
(3) starting from a representation pre-trained with contrastive learning.
Our goal with scenario (1) is to verify whether BRB can break through performance plateaus late in training after pre-training took place. In scenario (2), we aim to test the hypothesis that BRB is able to improve the exploration of clustering solutions. When training from scratch, we would expect the baselines to perform badly due to premature convergence to suboptimal solutions. In contrast, BRB should be able to leverage resets and reclustering to continuously escape bad local minima, leading to better performance. In scenario (3), we use contrastive pre-training to scale our approach to more challenging benchmark datasets.

We measure algorithm performance using the clustering accuracy, Adjusted Rand Index (ARI) (Hubert & Arabie, ), and Normalized Mutual Information (NMI) (Kvalseth, ) over ten seeds reporting average performance with standard deviations if not otherwise indicated. All of these metrics are scaled between $[0,100]$ with higher values indicating better performance. Similar to Lehner et al. (), we track the separation of ground truth clusters in the embedded space with the inter/intra-class distances (inter-CD/intra-CD), which measure the variation between and within classes, respectively. We measure the change in cluster labels (CL Change) during training using the NMI of cluster labels in subsequent epochs. Section 4 describes the inter- and intra-class distances and our cluster label change metric in more detail. A detailed description of all metrics is provided in the Appendix D.

#### 6.2 Benchmark Results

Figure: Figure 4: Improved performance of BRB. Relative change in average accuracy against the unmodified DCN algorithm for *BRB* and important ablations with pre-training: *DCN+Reset* refers to performing only weight resets (Eq. 1); *DCN+Recluster*, refers to only reclustering. Our *DCN+BRB* with both weight resets and reclustering consistently improves performance for DCN.
Refer to caption: x3.png

###### Scenario 1: with pre-training

Figure 4 compares the performance of BRB against baselines on several DC benchmark datasets. As BRB consists of a weight reset and subsequent reclustering, we provide ablation studies for each component individually. Our results suggest that neither reclustering nor resetting can consistently improve the baseline on their own. For example, on GTSRB, *DCN+Reset* performs much worse than the baseline (-10%), while *DCN+Recluster* is surpassed by the baseline on USPS.
In contrast, BRB leverages the synergy between weight resets and reclustering and improves performance across all datasets. The ablation experiments for IDEC and DEC confirm the average improvement of BRB over the unmodified baseline and are shown in Appendix Table 13.

Figure: Figure 5: BRB enables training from scratch. Relative improvements of clustering accuracy for DEC and IDEC when using BRB without pre-training.
Refer to caption: x4.png

###### Scenario 2: without pre-training

DEC, IDEC, and DCN heavily rely on pre-training to get sufficiently good initial clusters. To our surprise, we find that BRB reaches strong levels of performance even without pre-training. Figure 5 shows the relative improvement in clustering accuracy for DEC and IDEC when compared to the unmodified algorithms, with absolute values shown in Table 13. Without BRB, the performance of DEC and IDEC plateaus early without pre-training, as highlighted already in Figure 1 for IDEC. BRB significantly improves the performance for both algorithms, sometimes by up to 30%, e.g., when using DEC on OPTDIGITS or GTSRB and for IDEC on USPS. Table 13 underscores that these large improvements hold for DCN as well. Interestingly, BRB improves DEC’s accuracy from 61 to 77 on OPTDIGITS without image augmentation, showing it can build strong representations from random initialization. However, we still recommend using image augmentations for generally better results.

###### Scenario 3: with contrastive learning

All of the above experiments use an AE with reconstruction loss as an auxiliary task. Table 1 shows that BRB’s performance improvements also transfer to other auxiliary tasks. Here, we compare DEC, IDEC, and DCN with and without BRB using SimCLR and self-labeling (Gansbeke et al., ); see Section E for implementation details and Table 7 for specific hyperparameter settings. We follow the experiment setup of Qian () by using a ResNet18 for all contrastive experiments and reporting the best performance after self-labeling on the respective test sets of CIFAR10 and CIFAR100-20. In Table 1, we see that BRB consistently improves performance for IDEC and DCN by about 2-3%, while DEC benefits from BRB for CIFAR10 by more than 2%. Surprisingly, we find that the established methods IDEC and DCN outperform more recent deep clustering algorithms when combined with a contrastive task and BRB. To the best of our knowledge, this is the first time that such high performance has been reported for DEC, IDEC, and DCN on CIFAR10 and CIFAR100-20 using a ResNet18. The findings highlight the continued relevance of these “older” methods up to today. For CIFAR100-20, DCN+BRB and IDEC+BRB even beat the current state-of-the-art deep clustering method SeCu (Qian, ). We provide additional results in Appendix Table 16 and results without self-labeling in Appendix Table 17.

**Table 1: Clustering performance with contrastive task and self-labeling. BRB improves overall performance for most baselines and DCN+BRB outperforms the state-of-the-art method SeCu on CIFAR100-20. The per-method best results are in bold, and the overall best results are underlined.**
| Methods | CIFAR10 | CIFAR100-20 |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| ACC | NMI | ARI | ACC | NMI | ARI |  |
| Pretraining + $k$-Means | $68.97$ | $63.98$ | $40.13$ | $37.22$ | $42.25$ | $14.86$ |
| DEC | $88.29$ | $80.60$ | $77.23$ | $50.16$ | $51.66$ | $\mathbf{35.37}$ |
| DEC + BRB | $\mathbf{90.57}$ | $\mathbf{82.57}$ | $\mathbf{81.18}$ | $\mathbf{50.46}$ | $\mathbf{51.72}$ | $35.05$ |
| IDEC | 88.30 | 79.50 | 77.27 | 52.73 | 52.79 | 36.79 |
| IDEC + BRB | $\mathbf{90.72}$ | $\mathbf{83.26}$ | $\mathbf{81.81}$ | $\mathbf{55.43}$ | $\mathbf{54.81}$ | $\mathbf{38.81}$ |
| DCN | 88.55 | 81.02 | 78.17 | 53.27 | 52.13 | 37.30 |
| DCN + BRB | $\mathbf{91.23}$ | $\mathbf{83.66}$ | $\mathbf{82.42}$ | $\mathbf{56.92}$ | $\mathbf{56.76}$ | $\mathbf{41.15}$ |
| SCAN (Gansbeke et al., ) | 88.3 | 79.7 | 77.2 | 50.7 | 48.6 | 33.3 |
| GCC (Zhong et al., ) | 90.1 | - | - | 52.3 | - | - |
| SeCu (Qian, ) | $93.0$ | $86.1$ | $85.7$ | $55.2$ | $55.1$ | $39.7$ |

###### Additional experimental results

We provide a hyperparameter sensitivity analysis in Appendix E.2, showing that BRB is stable for moderate reset values $\alpha$ between 0.8 and 0.9 with less frequent resets $T\in\{20,40\}$. In Appendix G, we validate that BRB is lightweight and adds only minor computational overhead by performing a detailed runtime analysis. Lastly, we also study the impact of different reclustering algorithms in Table 10.

#### 6.3 Analysis of BRB

Figure: Figure 6: Effects of BRB. We track average clustering accuracy, inter/intra-class distance (inter/intra-CD), and cluster label change (CL Change). For a detailed discussion, see Section 6.3.
Refer to caption: x5.png

Our central hypothesis is that BRB’s soft resets and subsequent reclustering structurally alter the embedded space and enable finding new clustering solutions. We validate this hypothesis by analyzing changes in the embedded space via the inter-class distance (inter-CD), with *higher* values indicating enhanced separation, and measuring variation within ground truth classes with the intra-class distance (intra-CD). BRB’s impact on clustering assignments is measured using the NMI-based cluster label change (CL Change) metric, detailed in Section 4. As BRB’s impact differs slightly depending on the dataset, we choose to analyze datasets where it has a substantial, moderate, and minor impact on performance. Therefore, we focus our analysis of BRB on the DCN algorithm and GTSRB (Figure 2), OPTDIGITS, and MNIST datasets (Figure 6).

###### Early over-commitment

For all three considered datasets, BRB increases intra-CD after the first few resets, indicating it counteracting premature cluster compression and potential early misassignments. For GTSRB and OPTDIGITS, the intra-CD increases over the whole training, whereas for MNIST, the intra-CD decreases around epoch 60. This leads to a lower intra-CD at the end of the training compared to the baselines. We find that avoiding cluster compression is more important in early training than later on, judging from BRB outperforming the baselines on MNIST despite a lower intra-CD at the end of training. We analyze the specific behavior of the increasing intra-CD and inter-CD for DCN and DCN+Recluster on MNIST in more detail in Appendix H.10.

Figure: Figure 7: Effects of BRB on centroid distances. We show the distribution of distance ratios $\rho(\mathbf{\bm{x}}_{i})=d_{1}(\mathbf{\bm{x}}_{i})/d_{2}(\mathbf{\bm{x}}_{i})$ for the distance to the closest $d_{1}(\mathbf{\bm{x}}_{i})$ and second-closest centroid $d_{2}(\mathbf{\bm{x}}_{i})$. BRB prevents early over-commitment by distributing samples more evenly between centroids, allowing for easier reassignment.
Refer to caption: x6.png

One possible hypothesis as to why BRB is effective at preventing early over-commitment is that its resets move samples closer to other centroids, allowing for more frequent reassignments during training. To verify this hypothesis, we look at the ratio $\rho(\mathbf{\bm{x}}_{i})=d_{1}(\mathbf{\bm{x}}_{i})/d_{2}(\mathbf{\bm{x}}_{i})$ between the distance to the closest centroid $d_{1}(\mathbf{\bm{x}}_{i})$ and the second closest centroid $d_{2}(\mathbf{\bm{x}}_{i})$ for a sample $\mathbf{\bm{x}}_{i}$. If this ratio is close to 1, then $\mathbf{\bm{x}}_{i}$ lies directly between two centroids and has a high likelihood of potentially being reassigned. If $\rho(\mathbf{\bm{x}}_{i})=0$, then the sample’s position in the embedded space is directly on top of the centroid that it is assigned to. Figure 7 shows how $\rho$ is distributed before and after applying BRB during DCN training. We choose DCN for this experiment because its clustering notion relies on the Euclidean distance, which is easy to interpret compared to the Student-t kernel of DEC or IDEC. Looking at the distribution of distance ratios $\rho$ in Figure 7, we see that after applying BRB, there are substantially more samples with a ratio $\rho$ between 0.9 and 1. This means that samples are more evenly distributed between centroids, which in turn facilitates potential reassignments in future update steps, effectively preventing early over-commitment.

###### Cluster separation

Because BRB increases variation within clusters, it needs to separate the classes by a higher margin in order to achieve the same or a better clustering accuracy with less compressed clusters (higher intra-CD). Consequently, Figures 2 and 6 indicate that BRB leads to higher distances between ground truth clusters as indicated by a higher inter-CD in the third row of both figures. For GTSRB and OPTDIGITS, the high intra-CD leads to a correspondingly higher inter-CD. For MNIST, the training ends with similar inter-CD values as the baselines, whereas the intra-CD at the end of training is lower than the corresponding baseline values.

###### Exploration of solutions

For all three datasets, we observe a significant spike in CL Change after applying BRB. As noted in Section 4, the *Recluster* step minimally changes the clustering compared to the unmodified baseline.
We attribute this to reclustering alone, reinforcing only existing solutions rather than generating substantially different ones, thus only slightly increasing CL Change and clustering accuracy. In contrast to the reclustering baseline, BRB manages to explore more diverse clusterings (higher CL Change) during training while retaining the knowledge of previous clustering solutions.

#### 6.4 Are changes in cluster labels the driving factor of BRB?

Here, we briefly discuss two ablation studies on the influence of new clustering targets obtained through reclustering on post-reset embeddings. First, we examine whether labels from a perturbed embedding are enough to induce changes in the cluster structure when the encoder network stays unchanged, *Disentangling* the effect of new cluster labels from weight resets. Second, we evaluate whether simply adding *Noise* to the embedded space instead of using BRB’s structured weight resets could induce similar improvements.

In summary, we find that for both modifications, the performance degrades, whereas BRB maintains the network’s ability to fit new targets due to the reset and yields strictly better results. Whereas BRB achieves a final accuracy above 85%, the *Noise* version is approximately 5% worse at 80%, and the *Disentangled* algorithm only achieves 75% accuracy. We attribute this either to inducing insufficient label changes to explore new clustering solutions (*Disentangled*) or to generating too large label changes late in training (*Noise*). This stems from both versions having no effect on intra-CD and inter-CD, as shown in Figure 9 in Appendix F. We conclude that applying BRB’s *structured, persistent perturbations* is crucial for later improvements through reclustering.

### 7 Discussion

In this section, we discuss the ramifications of early cluster compression more generally and connect BRB to works from other fields also combating early overfitting. We conclude the section with limitations and future work.

###### Broader insights for deep clustering research

The problem of over-committing to early clustering targets is of great interest to the deep clustering community, as we use powerful deep neural networks to fit changing clustering targets. Our study identifies sharp drops in the intra-class distance early in training as the main culprit of this problem. Once objects with different ground truth classes are compressed in a cluster, reclustering is insufficient to separate them again. This causes a shallow exploration of clustering solutions and leads to performance plateaus, which we call the *reclustering barrier*. Section 6.4 shows that the network fails to adapt to the more diverse targets even if the variation in clustering labels is increased. While we use these findings to develop BRB, they may help to guide the design of future deep clustering methods as well.

###### Connection to early overfitting in other fields

The *primacy bias* is an example of early overfitting (Nikishin et al., ) in deep reinforcement learning. In supervised learning, Zaidi et al. () explore the role of weight resets regarding generalization performance. They find that soft resets enhance test accuracy by preventing overfitting to noise during early training (Zaidi et al., ) and hypothesize that resets may force the network to prioritize learning the “easy” data points first. The resets potentially prevent the network from “confidently fitting to [the] noise” (Zaidi et al., ). In DC algorithms, fitting to noise corresponds to a premature assignment of points to specific clusters.
Subsequent optimization steps, particularly the compression loss $L_{C}$, inhibit these points from being re-assigned later.
BRB mitigates this issue to some extent, as shown by resets increasing the intra-CD.

###### Limitations and future work

BRB is partially inspired by theoretical research on perturbation-robust clustering (Bilu et al., ; Awasthi et al., ). We hypothesize that BRB’s frequent resets and reclustering create an analog to an $\alpha$-perturbation-resilient clustering instance, where the soft resets mimic the $\alpha$-perturbation, altering the Euclidean distance in the embedding space by a factor of at most $\alpha$. A full theoretical analysis of BRB in deep clustering is complex due to the nonlinearity of neural networks and minibatch SGD and would be a significant contribution on its own. Therefore, we focus on empirical results and ablation studies for practical purposes and want to explore the theoretical aspect in future work.
Another limitation is that we investigate the *reclustering* barrier for centroid-based DC algorithms only. Whether a similar phenomenon exists for non-centroid-based DC algorithms, such as density-based or agglomerative clustering methods, is an exciting direction for future work.

### 8 Conclusion

This paper identifies a common problem in centroid-based DC algorithms: Reclustering during training fails to explore new clustering solutions due to early over-commitment to a sub-optimal clustering. We call this phenomenon the *reclustering barrier*. Integrating our proposed algorithm BRB into widely-established DC methods, like DCN, DEC, and IDEC, demonstrates consistent performance gains under multiple conditions,
including a range of different datasets, different auxiliary tasks (contrastive learning and autoencoding), and settings with and without pre-training. Under all of these conditions,
BRB is able to break through existing performance plateaus of DEC, IDEC, and DCN.
Notably, BRB with contrastive learning yields competitive performance to state-of-the-art algorithms on CIFAR10 and CIFAR100-20.

Through empirical analysis, we identify three key mechanisms contributing to BRB’s success. These mechanisms consist of
(i) prevention of premature commitment to clustering solutions by DC methods
(ii) exploration of a wider range of clusterings and
(iii) enabling adaptation to improved clustering targets.
BRB can be easily integrated in centroid-based DC methods. Given that DCN, DEC, and IDEC underpin numerous DC algorithms, we anticipate that BRB will impact the development of centroid-based DC methods going forward.

##### Acknowledgments

We acknowledge EuroHPC Joint Undertaking for awarding us access to Meluxina at LuxProvide, Luxembourg. Also, we gratefully acknowledge financial support from the Vienna Science and Technology Fund (WWTF-ICT19-041) and the Federal Ministry of Education, Science and Research (BMBWF) of Austria within the interdisciplinary project ”Digitize! Computational Social Science in the Digital and Social Transformation”. We thank the open-source community for providing the tools that enabled this work: PyTorch (Paszke et al., ), NumPy (Harris et al., ), Matplotlib (Hunter, ), and ClustPy (Leiber et al., ). Lastly, we want to thank the anonymous reviewers who helped improve our work through their feedback.

## Part I Appendix

Table 2 summarizes the contents of our Appendix:

**Table 2: Structure of our appendix.**
| Appendix Section | Content |
| --- | --- |
| Appendix A | Pytorch-style pseudocode for BRB |
| Appendix B | Detailed information about the clustering algorithms used in this study<br>SimCLR (Chen et al., ) overview<br>Overview of resetting methods in other fields |
| Appendix C | Datasets of our experiments, data properties, and preprocessing |
| Appendix D | Evaluation metrics |
| Appendix E | Implementation details<br>Hyperparameters & Hyperparameter sensitivity analysis |
| Appendix F | Detailed setup and results of the noise & disentanglement ablations |
| Appendix G | Runtime analysis |
| Appendix H | Supplementary results and figures<br>Full result tables |

### Appendix A Pseudocode

Figure: Algorithm 1 PyTorch-style pseudo-code of BRB

### Appendix B Background

In this section, we provide additional background for some of the methods employed in our main paper. It is structured as follows: First, we provide more details on deep clustering objective functions in Section B.1. Then, we briefly review SimCLR (Chen et al., ) as the contrastive learning method used in this work. Lastly, we review reset methods in other fields.

#### B.1 Deep Clustering Optimization

In general, the procedures mentioned in this work optimize $L(\theta,\mathbf{\bm{M}})=\lambda_{1}L_{SSL}(\theta)+\lambda_{2}L_{C}(\theta,
\mathbf{\bm{M}})$. To highlight the differences in more detail, we explain below how $L_{C}$ is chosen.

DEC and IDEC: As mentioned in Sec. 2, the clustering loss $L_{C}$ of DEC (Xie et al., ) and IDEC (Guo et al., ) is based on the Kullback-Leibler divergence. Here, the data distribution $\mathbf{\bm{Q}}$ is compared with an auxiliary target distribution $\mathbf{\bm{P}}$. The data distribution $\mathbf{\bm{Q}}$ is quantified by a kernel based on the Student’s t-distribution:

$$ $q_{i,j}=\frac{(1+||\mathbf{\bm{z}}_{i}-\mathbf{\bm{\mu}}_{j}||_{2}^{2})^{-1}}{ \sum_{j^{\prime}}(1+||\mathbf{\bm{z}}_{i}-\mathbf{\bm{\mu}}_{j^{\prime}}||_{2} ^{2})^{-1}},$ (3) $$

where $\mathbf{\bm{z}}_{i}$ is an encoded sample, i.e., $\mathbf{\bm{z}}_{i}=f_{\theta}(\mathbf{\bm{x}}_{i})$, and $\mathbf{\bm{\mu}}_{j}$ is the center of cluster $j$.
The target distribution $\mathbf{\bm{P}}$ is defined as:

$$ $p_{i,j}=\frac{q_{i,j}^{2}/f_{j}}{\sum_{j^{\prime}}(q_{i,j^{\prime}}^{2}/f_{j^{ \prime}})},$ (4) $$

where $f_{j}=\sum_{i}q_{i,j}$ are the soft cluster frequencies. Here, $q_{i,j}^{2}$ is used to strengthen predictions on data points that are assigned with high confidence. Simultaneously, a division by $f_{j}$ should prevent large clusters from dominating the loss.

Putting everything together, we receive:

$$ $L_{C}(\theta,\mathbf{\bm{M}})=KL(P||Q)=\sum_{i}\sum_{j}p_{i,j}\log(\frac{p_{i, j}}{q_{i,j}}).$ (5) $$

In the case of DEC, $\lambda_{1}=0$ and $\lambda_{2}=1$ during the clustering optimization. For IDEC, $\lambda_{1}=1$ and $\lambda_{2}=0.1$ to prevent a distorted embedding.

DCN: The optimization strategy of DCN (Yang et al., ) is based on the classical $k$-Means (Lloyd, ) algorithm. First, the network parameters $\theta$ are updated using $L(\theta,\mathbf{\bm{M}})$, where

$$ $L_{C}(\theta,\mathbf{\bm{M}})=\frac{1}{2}\sum_{i}||\mathbf{\bm{z}}_{i}-\mathbf {\bm{\mu}}_{h(\mathbf{\bm{z}}_{i})}||^{2}_{2}$ (6) $$

and $h(\mathbf{\bm{z}}_{i})$ returns the cluster $\mathbf{\bm{z}}_{i}$ is assigned to. Afterward, each sample $\mathbf{\bm{z}}_{i}$ is assigned to its closest cluster center. Last, the cluster centers are updated by calculating:

$$ $\mathbf{\bm{\mu}}_{h(\mathbf{\bm{z}}_{i})}^{\text{updated}}=\mathbf{\bm{\mu}}_ {h(\mathbf{\bm{z}}_{i})}-\frac{1}{c_{h(\mathbf{\bm{z}}_{i})}}(\mathbf{\bm{\mu} }_{h(\mathbf{\bm{z}}_{i})}-\mathbf{\bm{z}}_{i}).$ (7) $$

Here, $c_{j}$ counts the total number of samples already assigned to cluster $j$. This update strategy is inspired by the SGD-$k$-Means algorithm (Bottou & Bengio, ). Finally, the process repeats by optimizing the embedding using Eq. 6 with the newly obtained cluster parameters.

#### B.2 SimCLR

SimCLR (Chen et al., ) is a contrastive learning method designed to discriminate among pairs of augmented samples. In its pretraining phase, the encoder $f_{\theta}$ processes a batch of $N$ samples, each augmented twice, resulting in a batch size of $2N$. This yields embeddings $\mathbf{\bm{h}}_{i}=f_{\theta}(\mathbf{\bm{x}}_{i})$. Instead of explicitly mining negatives, SimCLR treats all augmented samples not belonging to the anchor as negative samples. Before the contrastive loss is applied, the encoded samples are mapped into another latent space $\mathbf{\bm{z}}_{i}=g(\mathbf{\bm{h}}_{i})$ by a projector network. SimCLR then applies the InfoNCE loss (van den Oord et al., ):

$$ $\displaystyle L_{i,j}=-\log\frac{\exp\left(\operatorname{sim}\left(\mathbf{\bm {z}}_{i},\mathbf{\bm{z}}_{j}\right)/\tau\right)}{\sum_{k=1}^{2N}\mathbb{1}_{[k \neq i]}\exp\left(\operatorname{sim}\left(\mathbf{\bm{z}}_{i},\mathbf{\bm{z}}_ {k}\right)/\tau\right)},$ (8) $$

where $\operatorname{sim}\left(\mathbf{\bm{z}}_{i},\mathbf{\bm{z}}_{j}\right)$ denotes the cosine similarity between two projected embeddings, and $\mathbb{1}_{[k\neq i]}$ is 1 if $k\neq i$. Essentially, contrastive learning fosters a latent space wherein the features of augmented versions of the same image are close while being distanced from others, thereby promoting a cluster-friendly latent space (Wang & Isola, ).

#### B.3 Reset Methods in other Fields

Reset methods have been used in other fields to great success. For example, it has been shown that soft resets —named *Shrink and Perturb*— may be able to alleviate poor generalization performance in the pretrain + fine-tune setting in supervised learning (Ash & Adams, ). This phenomenon has been dubbed the *generalization gap* by Berariu et al. ().

A striking application of resetting has developed in the field of deep Reinforcement Learning (RL): Here, resets have been used to improve the data efficiency of algorithms by mitigating *plasticity loss* (Nikishin et al., ; D’Oro et al., ; Schwarzer et al., ).
Loss of plasticity refers to the loss of a network’s learning ability over the course of training (Berariu et al., ; Dohare et al., ). It is particularly prevalent in RL due to the non-stationarity induced by bootstrapped targets in deep value-based algorithms.

As our disentanglement ablation study in Figure 9 shows, deep clustering algorithms do not suffer from a loss of plasticity. Instead, the resets help avoid premature convergence to sub-optimal local minima by facilitating the exploration of multiple clustering solutions. When BRB commits to a clustering solution, the resets ensure that it is robust with respect to the structured noise induced by the resets.

The different reset strategy our method employs highlights this: Our method never applies Shrink and Perturb to the embedding layer, as this could lead to a collapse of deep clustering performance. On the other hand, deep RL algorithms often fully reset the last layers completely, as plasticity loss is commonly believed to be concentrated there (Berariu et al., ; D’Oro et al., ).

### Appendix C Datasets

**Table 3: Information regarding the benchmark datasets.**
| Dataset | Type | # Samples | # Features | # Classes |
| --- | --- | --- | --- | --- |
| Optdigits | Grayscale | $5{,}620$ | $8\times 8$ | $10$ |
| GTSRB | Color | $7{,}860$ | $32\times 32\times 3$ | $5$ |
| USPS | Grayscale | $9{,}298$ | $16\times 16$ | $10$ |
| CIFAR10 | Color | $60{,}000$ | $32\times 32\times 3$ | $10$ |
| CIFAR100-20 | Color | $60{,}000$ | $32\times 32\times 3$ | $20$ |
| MNIST | Grayscale | $70{,}000$ | $28\times 28$ | $10$ |
| FMNIST | Grayscale | $70{,}000$ | $28\times 28$ | $10$ |
| KMNIST | Grayscale | $70{,}000$ | $28\times 28$ | $10$ |

We evaluate our approach by analyzing the results regarding eight image datasets commonly used in machine learning. The information concerning these datasets is summarized in Tab. 3.

The grayscale image datasets Optdigits (Alpaydin & Kaynak, ), USPS (Hull, ), and MNIST (LeCun et al., ) contain images of handwritten digits (0-9), with each dataset having a different resolution. FMNIST (Xiao et al., ) contains grayscale images of ten articles from the Zalando online store, and KMNIST (Clanuwat et al., ) is composed of grayscale images showing ten Japanese Kanji characters.

The color dataset GTSRB (Stallkamp et al., ) contains images of $43$ German traffic signs. We use a subset of the data containing the signs ‘Speed limit 50’, ‘Priority road’, ‘No entry’, ‘General caution’, and ‘Ahead only’ (as proposed in (Leiber et al., ) - ‘Priority road’, ‘No entry’, and ‘General caution’ were given as ‘Right of way’, ‘No passing’, and ‘Attention’ here) and unify the sizes of the images. CIFAR10 (Krizhevsky et al., ) is composed of color images showing ten different objects with various backgrounds. The CIFAR100-20 dataset uses a course-grained grouping of the 100 classes of the CIFAR100 dataset to summarize the fine-grained classes within related super-classes.

All datasets are preprocessed by performing a channel-wise-z-transformation, resulting in a mean of zero and a unit variance for each color channel. In addition, histogram normalization is conducted for GTSRB due to the low contrast.

### Appendix D Metrics

In the following, we define the clustering evaluation metrics that are used throughout our work. More detailed descriptions and examples can be found in Murphy ().

#### D.1 Clustering Accuracy

Clustering accuracy (ACC) (Yang et al., ) measures the fraction of correctly assigned cluster labels over the dataset compared to the ground truth labels:

$$ $\displaystyle\text{ACC}=\text{max}_{\text{map}}\frac{\sum_{i=1}^{n}\delta(y_{i },\text{map}(\hat{y}_{i}))}{n}.$ (9) $$

Here $y_{i}$ is the ground-truth label of data point $i$, $\hat{y}_{i}$ the predicted label of sample $i$, and $\delta$ denotes the Kronecker-Delta. As the labels for the found clustering might deviate from the ground truth labels, we require the mapping function map that tests each possible mapping of labels. We use the Hungarian method (Kuhn, ) to identify the best mapping.

#### D.2 ARI

Adjusted Rand Index (ARI) (Hubert & Arabie, ) is a statistical measure that generalizes the notion of accuracy for clustering and additionally adjusts for chance. It provides a score $\operatorname{ARI}\in[-1,1]$. An ARI score of $1$ signifies agreement, $-1$ indicates disagreement, and a score of 0 0 suggests agreement by chance. ARI is defined as:

$$ $\displaystyle\operatorname{ARI}\coloneq\frac{\operatorname{R}-\mathbb{E}_{\hat {Y}\sim\operatorname{HGeom}(\mathbf{\bm{k}},n)}[R]}{1-\mathbb{E}_{\hat{Y}\sim \operatorname{HGeom}(\mathbf{\bm{k}},n)}[R]},$ (10) $$

where $\operatorname{R}$ denotes the Rand index, which corresponds to ACC in case the ground truth class labels are used as reference clustering. ARI adjusts for randomness by using the expected value of the Rand index $\mathbb{E}_{\hat{Y}\sim\operatorname{HGeom}(\mathbf{\bm{k}},n)}[R]$ under a generalized Hypergeometric distribution $\operatorname{HGeom}(\mathbf{\bm{k}},n)$ with $\mathbf{\bm{k}}=\left(k_{1},\ldots,k_{n}\right)$ to distribute the $n$ samples across the $k$ classes with uniform random probability.

#### D.3 NMI

The Normalized Mutual Information (NMI) (Kvalseth, ) calculates the Mutual Information between two sets of labels and scales the results between 0 and 1.

$$ $\displaystyle\operatorname{NMI}(C,\hat{C})\coloneq\frac{2I(C,\hat{C})}{H(C)+H( \hat{C})},$ (11) $$

where $C=\{C_{1},\ldots,C_{k}\}$ is the ground truth partition and $\hat{C}=\{\hat{C}_{1},\ldots,\hat{C}_{k^{\prime}}\}$ are the predicted clusters. $I$ denotes mutual information between two sets, whereas $H(X)$ corresponds to the entropy of a probability distribution $X$.

#### D.4 Inter- & Intra- Class Distance

Lehner et al. () uses the silhouette score Rousseeuw () of the l2 normalized embeddings to measure the separation of ground truth clusters in the embedded space of neural networks. The silhouette score is the relation between the intra- and inter-class distances that we use in this work. The intra-class distance (intra-CD) of a sample $\mathbf{\bm{x}}_{i}\in C_{l}$ is defined as the mean distance of the sample to other samples $\mathbf{\bm{x}}_{j}$ in the *same cluster* $C_{l}$:

$$ $\displaystyle d_{\text{intra}}(\mathbf{\bm{x}}_{i})\coloneq\frac{1}{|C_{l}|-1} \sum_{\mathbf{\bm{x}}_{j}\in C_{l}}d(\mathbf{\bm{x}}_{i},\mathbf{\bm{x}}_{j}).$ (12) $$

The inter-class distance (inter-CD) of a sample $\mathbf{\bm{x}}_{i}\in C_{l}$ is the mean distance of the sample to instances in the *next closest cluster* $C_{m\neq l}$:

$$ $\displaystyle d_{\text{inter}}(\mathbf{\bm{x}}_{i})\coloneq\text{min}_{m\neq l }\left(\frac{1}{|C_{m}|}\sum_{\mathbf{\bm{x}}_{j}\in C_{m}}d(\mathbf{\bm{x}}_{ i},\mathbf{\bm{x}}_{j})\right).$ (13) $$

### Appendix E Implementation Details and Hyperparameters

Our codebase builds on top of the open-source ClustPy-codebase (Leiber et al., ), which provides Pytorch implementations of the centroid-based deep clustering (DC) algorithms used in our work. We use the Adam optimizer (Kingma & Ba, ) due to its widespread use and strong performance on a wide range of deep learning problems. For DEC and IDEC, the centroids are optimizable parameters. Therefore, we also reset their momentum after each weight reset to prevent divergent gradients. Due to the high learning rates used in our contrastive learning experiments (cf. Table 7), we rarely encounter single gradient steps with very high gradient magnitudes. Therefore, we clip the $\ell_{2}$ gradient norms at a value of $500$. For the AE, the latent dimension is set to the dataset’s number of classes, a common practice in DC. Additionally, we reset the projector network for contrastive learning with each weight reset of BRB.

We have to slightly adapt the objective functions of DEC, IDEC, and DCN to handle augmentations in a meaningful way. An essential constraint is that the cluster assignments of a sample should not change due to the applied augmentations. Therefore, the augmented sample $\mathbf{\bm{x}}_{i}^{A}=\text{aug}(\mathbf{\bm{x}}_{i})$ must always receive the same assignments $s_{i,j}$ as the original sample $\mathbf{\bm{x}}_{i}$. We denote $\mathbf{\bm{z}}_{i}^{A}=f_{\theta}(\mathbf{\bm{x}}_{i}^{A})$ as the encoded version of $\mathbf{\bm{x}}_{i}^{A}$. In general, we use the average of the loss with respect to the original sample $\mathbf{\bm{x}}_{i}$ and the loss with respect to the augmented sample $\mathbf{\bm{x}}_{i}^{A}$.

First, we adjust $L_{SSL}$ (here shown for the AE):

$$ $\displaystyle L_{SSL}^{A}=\frac{1}{2}\left(L_{SSL}(\theta,\mathbf{\bm{x}}_{i}) +L_{SSL}(\theta,\mathbf{\bm{x}}_{i}^{A})\right).$ (14) $$

Next, we update the clustering loss $L_{C}$ regarding DEC and IDEC:

$$ $\displaystyle L_{C}^{A}=\frac{1}{2}\sum_{i}\sum_{j}\left(p_{i,j}\log(\frac{p_{ i,j}}{q_{i,j}})+p_{i,j}\log(\frac{p_{i,j}}{q^{A}_{i,j}})\right),$ (15) $$

where

$$ $\displaystyle q^{A}_{i,j}=\frac{(1+||\mathbf{\bm{z}}_{i}^{A}-\mathbf{\bm{\mu}} _{j}||_{2}^{2})^{-1}}{\sum_{j^{\prime}}(1+||\mathbf{\bm{z}}^{A}_{i}-\mathbf{ \bm{\mu}}_{j^{\prime}}||_{2}^{2})^{-1}}.$ (16) $$

Note that $p_{i,j}$ remains the same compared to the DEC/IDEC version without augmentation.

Last, we adjust $L_{C}$ for DCN:

$$ $\displaystyle L_{C}^{A}=\frac{1}{4}\sum_{i}\left(||\mathbf{\bm{z}}_{i}-\mathbf {\bm{\mu}}_{h(\mathbf{\bm{z}}_{i})}||^{2}_{2}+||\mathbf{\bm{z}}_{i}^{A}- \mathbf{\bm{\mu}}_{h(\mathbf{\bm{z}}_{i})}||^{2}_{2}\right)$ (17) $$

For contrastive learning, which learns a representation that is invariant to the augmentations, we only use augmented samples during pretraining and deep clustering.

#### E.1 Self-Labeling Implementation Details

Many deep clustering methods have two stages: pretraining and joint deep clustering. Self-labeling (Gansbeke et al., ) can be used after joint deep clustering to further improve clustering performance as an additional third stage. Self-labeling uses ideas from self-training in semi-supervised learning to only train on samples that have already been assigned with high certainty to a cluster. Self-labeling does not work out of the box with centroid-based deep clustering methods as it assumes a classification head to discriminate between the pseudo-labels learned from the clustering. To solve this problem, we follow the training strategy of (Qian, ), which successfully applied self-labeling to their centroid-based deep clustering method SeCu by introducing a short warmup phase. This warmup phase trains a classification head based on the clustering labels obtained from the centroid-based clustering objective and is then followed by the self-labeling phase(^3^33We used the public repository of SCAN at [https://github.com/wvangansbeke/Unsupervised-Classification](https://github.com/wvangansbeke/Unsupervised-Classification)).

#### E.2 Hyperparameter Sensitivity Analysis

Figure: Figure 8: Hyperparameter sensitivity analysis. Clustering accuracy (averaged over DEC/IDEC/DCN and five seeds per setting on MNIST) for BRB’s reset factor $\alpha$, reset interval $T$ and different deep clustering learning rates. Large ($\alpha\in\{0.6,0.7\}$) and frequent ($T\in\{5,10\}$) resets can destroy cluster structure (lower accuracy), whereas moderate values ($T\in\{20,40\}$, $\alpha\in\{0.8,0.9\}$) perform consistently well.
Refer to caption: x7.png

In Figure 8, we provide a detailed sensitivity analysis of BRB over the learning rate (LR), the reset interval $T$, and the reset factor $\alpha$. We report averages over 15 runs (five seeds per DEC, IDEC, and DCN) for each setting on MNIST, resulting in 960 runs in total. For the AE pretraining, we use an LR of 0.001 and, therefore, select LRs that are higher (0.005), equal (0.001), and lower (0.0005, 0.0001) than the pretraining LR for DC. Note that usually, only LRs that are lower than the pretraining LR are considered in DC.
In Figure 8, the lower and higher end of LRs (0.0001, 0.005) suffer more from frequent ($T\in\{5,10\}$) and strong ($\alpha\in\{0.6,0.7\}$) resets. Intuitively this makes sense: The more often we reset with a high reset factor, the more likely it is to destroy useful cluster information. The lower and higher LRs exacerbate this by either recovering too slowly or too quickly, whereas the moderate LRs (0.0005, 0.001) are still robust. An exception occurs for $\alpha=0.6$ with $T=5$, where the setting with LR 0.0005 loses some performance. In general, we see that the moderate LRs (0.0005 and 0.001) remain stable over all other settings. As a rule of thumb, choosing a moderate reset value between 0.8 and 0.9 with less frequent resets ($T\in\{20,40\}$) and an LR that is equal to or slightly lower than the pretraining LR performs well in many settings. This is why for all main experiments, we choose an LR of 0.001 and set $\alpha=0.8$ with $T=20$.

#### E.3 Computational Resources

We primarily utilized internal servers to generate our results with grayscale datasets. For this paper, we had access to

- •
$2\times$ Intel Xeon Silver 4214R CPU @ 2.40GHz server with 48 cores and 2 Nvidia A100 GPUs with 40GB of VRAM each
- •
$2\times$ Intel Xeon Gold 6326 CPU @ 2.90GHz server with 64 cores and 1 NVIDIA A100 GPU with 80GB of VRAM

These machines were also used to run preliminary experiments and to identify broad working ranges for the most important hyperparameters.

For the experiments with color datasets and contrastive learning, we had access to 1000h compute hours per month on a SLURM supercomputing cluster. A node in this supercomputer uses an AMD EPYC 7452 processor with 128 cores and 1 NVIDIA A100 GPU with 80GB of VRAM. We also used these resources to tune hyperparameters for SimCLR (Chen et al., ) pretraining.

The average wall clock time for one run is summarized in Table 4. We identify two main factors contributing to the runtime of our method. First, the number of samples in the dataset (see Table 3), where, e.g., MNIST variants take substantially longer to run than USPS or OPTDIGITS. Second, the number of CPU cores we could utilize to parallelize data augmentations.

**Table 4: Average runtime of our experiments.**
| Dataset | Approximate Average runtime |
| --- | --- |
| MNIST, FMNIST, KMNIST | 4h |
| GTSRB | 20m |
| USPS | 15m |
| OPTDIGITS | 8m |
| CIFAR10 | 5h |
| CIFAR100-20 | 5h |

#### E.4 Hyperparameters for Grayscale Datasets

Table 5 lists the hyperparameters used for our experiments on grayscale datasets. These consist of OPTDIGITS (Alpaydin & Kaynak, ), USPS (Hull, ), MNIST (LeCun et al., ), FMNIST (Xiao et al., ), and KMNIST (Clanuwat et al., ). We tune the parameters for $\alpha\in\{0.6,0.7,0.8,0.9\}$ and $T\in\{10,20,40\}$ once on MNIST and re-use them for all grayscale datasets.

**Table 5: BRB hyperparameters for grayscale datasets.**
| Parameter | Value |
| --- | --- |
| General Training |  |
| Batch size | 256 |
| Learning rate | $1e-3$ |
| Pretraining |  |
| Epochs | 250 |
| Augmentation | False |
| Clustering |  |
| Epochs | 400 |
| Augmentation | True |
| DCN cluster loss | $0.025$ |
| IDEC cluster loss | $0.1$ |
| Augmentation |  |
| Resize | $(28,28)$ |
| RandomAffine | $\text{deg}=\pm 16,\text{transl}=0.1,$ |
|  | $\text{shear}=\pm 8$ |
| Architectures |  |
| Feed Forward | $D$-1024-512-256-$d$ |
| BatchNorm | False |
| Embedding size | # Clusters |
| Optimizer | Adam |
| Momentum $\beta_{1}$ | 0.9 |
| Momentum $\beta_{2}$ | 0.999 |
| Weight decay | 0 |
| BRB |  |
| Subsample size | $10000$ |
| $\alpha$ (Reset interpolation factor) | $0.8$ |
| $T$ (Reset interval) | $20$ |
| Reset embedding | False |
| Reset center momentum | True |

#### E.5 Hyperparameters for Color Datasets with Reconstruction Pretraining

Our hyperparameters used for the dataset GTSRB (Stallkamp et al., ) are in Table 6. We use the same hyperparameters as for the grayscale datasets except for the data augmentations.

**Table 6: BRB hyperparameters for GTSRB (Stallkamp et al., ).**
| Parameter | Value |
| --- | --- |
| General Training |  |
| Batch size | 256 |
| Learning rate | $1e-3$ |
| Pretraining |  |
| Epochs | 250 |
| Augmentation | False |
| Clustering |  |
| Epochs | 400 |
| Augmentation | True |
| DCN cluster loss | $0.025$ |
| IDEC cluster loss | $0.1$ |
| Augmentations |  |
| RandomResizedCrop | $(32,32)$ |
| ColorJitter | $\text{bright}=0.4,\text{contrast}=0.4,$ |
|  | $\text{sat}=0.2,\text{hue}=0.1,p=0.8$ |
| RandomGrayscale | $p=0.2$ |
| RandomHorizontalFlip | $p=0.5$ |
| RandomSolarize | $\text{thresh}=0.5,p=0.2$ |
| Architecture |  |
| Feed Forward | $D$-1024-512-256-$d$ |
| Embedding size | # Clusters |
| BatchNorm | False |
| Optimizer | Adam |
| Momentum $\beta_{1}$ | 0.9 |
| Momentum $\beta_{2}$ | 0.999 |
| Weight decay | False |
| BRB |  |
| Subsample size | $10000$ |
| $\alpha$ (Reset interpolation factor) | $0.8$ |
| $T$ (Reset interval) | $20$ |
| Reset embedding | False |
| Reset center momentum | True |

#### E.6 Hyperparameters for Color Datasets with Contrastive Learning

We conduct experiments with contrastive learning as auxiliary tasks on CIFAR10 (Krizhevsky et al., ) and CIFAR100-20. Some parameters depend on the dataset and algorithm in this setup, we therefore report them separately in Table 7. For self-labeling (Gansbeke et al., ) we use the same configs as specified in their public repository(^4^44The config for CIFAR100-20 can be found at [https://github.com/wvangansbeke/Unsupervised-Classification/blob/master/configs/selflabel/selflabel_cifar20.yml](https://github.com/wvangansbeke/Unsupervised-Classification/blob/master/configs/selflabel/selflabel_cifar20.yml) and the one for CIFAR10 is in the same folder denoted as selflabel_cifar10.yml.), except for the differing hyperparameters specified at the bottom of Table 7.

Table: Table 7: BRB hyperparameters when using contrastive learning as auxiliary task on CIFAR10 (Krizhevsky et al., ) and CIFAR100-20.

### Appendix F Ablation for New Clustering Targets

In this section, we describe the setups of our disentanglement and noise experiments from the main paper. We then provide a more detailed analysis of the results.

#### F.1 Experiment Setup for the Disentanglement Ablation

With the disentanglement ablation, our objective is to isolate the impact of altered cluster labels resulting from resets from the resets themselves. For this, we modify the pseudocode of Algorithm 1 as follows: Initially, we reset the weights of a duplicate of the DC algorithm’s model in the first and second steps, utilizing it to produce new embeddings. These embeddings are then used to derive new cluster labels while keeping the existing centroids unchanged. Subsequently, new centroids are computed using embeddings from the unaltered model but with the newly generated labels. The modifications are outlined in Algorithm 2.

Figure: Algorithm 2 PyTorch-style pseudo-code of Disentangled BRB

#### F.2 Experiment Setup for the Noise Ablation

BRB employs soft resets to introduce structured noise into the optimization process of the DC algorithm. While this approach offers the advantage of impacting both the deep learning components and clustering, one might hypothesize that simply adding noise to generate a new clustering could suffice to escape sub-optimal local minima. We explore this hypothesis through an ablation study where we add noise to the embeddings instead of resetting the network’s weights. To ensure bespoke distortions in the latent space, we first normalize the noise vector to match the norm of the embeddings. We then add a fraction of that vector, as described in Equation 18:

$$ $\displaystyle\forall i\in\{1,\ldots,n\}:\tilde{\mathbf{\bm{h}}_{i}}=\mathbf{ \bm{h}}_{i}+\beta\mathbf{\bm{\epsilon}},\quad\text{with}~{}\|\mathbf{\bm{ \epsilon}}\|=\|\mathbf{\bm{h}}_{i}\|$ (18) $$

Here, $\mathbf{\bm{\epsilon}}$ denotes independent and identically distributed noise across dimensions and samples. $\beta\in\mathbb{R}^{+}$ represents a positive scaling factor. Empirically, we find that Gaussian noise with scaling factor $\beta=0.3$ achieves a balance between inducing label changes and minimizing performance degradation in later training stages. Following noise addition, we recluster using the perturbed embeddings while continuing training on the unmodified network.

#### F.3 Detailed Analysis of the Disentanglement and Noise Ablation

Figure: Figure 9: Importance of resets. Clustering accuracy on OPTDIGITS drops considerably if only targets are changed without resetting the embedding (*Disentangled*). Similarly, adding Gaussian noise to the embedding is insufficient to change cluster structure (*Noise*).
Refer to caption: x8.png

To disentangle the effect of weight resetting from the influence of new clustering targets obtained through reclustering on the post-reset embedding, we perform two ablation studies: First, the *Disentangled* variant compares BRB with a modified algorithm utilizing labels generated from a perturbed embedding, achieved by resetting a duplicate encoder. This is followed by reclustering with $k$-Means on the perturbed encoder’s embedded space without changing the original network. For the second experiment, we add noise to the embedded space before reclustering. The exact experiment setups are described in the previous sections.

The results in Figure 9 show that for both modifications of BRB, the performance degrades, whereas BRB maintains the network’s ability to fit new targets due to the reset and yields strictly better results. The intra-CD and inter-CD of both the *Disentangled* and *Noise* versions remain virtually unchanged compared to the baseline, indicating that a persistent change in the embedded space is required to enable enhanced adaptation. In terms of CL change, the modified algorithms either fail to induce the required changes to explore new clustering solutions (*Disentangled*) or generate too large label changes late in training (*Noise*). Both negatively affect clustering performance. In summary, this lets us conclude that *structured, persistent perturbations* induced by our soft resets are a necessary condition for subsequent improvements through the reclustering step of BRB.

### Appendix G Runtime analysis

#### G.1 Runtime complexity

BRB consists of three components: parameter perturbations, reclustering, and momentum resets. We will first give the runtime complexity of these components and then verify these findings empirically. In summary: Our analysis reveals that the reclustering step of BRB adds the most overhead, but compared to the total training time, the impact of BRB is modest, for instance, resulting in a 5.38% increase in total training time for our experiments for IDEC on MNIST.

###### Parameter perturbations.

The complexity is $O(L\cdot D^{2})$, where $L$ is the number of layers that are to be reset and $D$ are the most neurons across all layers that are to be reset. Note that $L$ is usually small as we do not reset the full network for larger models and that the bound does not depend on the size of the dataset.

###### Reclustering.

Here, we must analyze two stages. The first stage consists of forward passes to embed the subsampled data points. We assume that our model is an $M$-layer feedforward network to quantify runtime complexity. The second stage is the reclustering algorithm. Combined, we obtain a complexity of $O(N\cdot M\cdot D^{3}+I\cdot k\cdot N)$, where $N$ is the number of subsampled data points for reclustering, $M$ is the total number of layers of the network, $k$ the number of clusters and $I$ the maximum number of clustering iterations (we use the sklearn default of $I=300$). We stress that while the first term seems prohibitively expensive, it is usually heavily parallelized through batched GPU implementations of deep learning frameworks such as PyTorch.

###### Momentum resets.

We just set the centroid momentum tensors to zero, which requires negligible compute.

#### G.2 Empirical results

All results discussed in this section are generated using an Intel Xeon Silver 4214R CPU @ 2.40GHz server with 12 physical and 48 virtual cores and 2 Nvidia A100 GPUs with 40GB of VRAM each.

For our empirical investigations, we measure the time for each BRB component individually in seconds (10 seed averages) and compare them with the time of one epoch of deep clustering training. Table 8 shows time estimates for IDEC+BRB on the MNIST dataset, including the constant (as a function of the number of samples) and negligible overhead for the perturbations. We separately report the time for embedding and clustering, which together comprise the reclustering phase.

**Table 8: Runtime in seconds for IDEC+BRB on MNIST with different subsample sizes.**
| Subsample<br>size | Reset<br>time | Embedding<br>time | Cluster<br>time | Momentum<br>reset time | BRB<br>time | Total<br>runtime | BRB % of total<br>runtime |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 700 (1%) | 0.007 | 0.639 | 0.063 | 0.001 | 0.710 | 5.025 | 14.131 |
| 7000 (10%) | 0.006 | 0.630 | 0.337 | 0.001 | 0.975 | 5.417 | 17.991 |
| 17500 (25%) | 0.007 | 0.710 | 0.866 | 0.001 | 1.583 | 5.872 | 26.964 |
| 35000 (50%) | 0.007 | 0.803 | 1.862 | 0.001 | 2.672 | 7.063 | 37.830 |
| 70000 (100%) | 0.007 | 1.068 | 3.647 | 0.001 | 4.724 | 9.113 | 51.835 |

For our experiments, we apply BRB every 20th epoch, and thus, the runtime cost of BRB is distributed over 20 epochs. In this case, reclustering on the full dataset leads to an increase in the total runtime of the clustering phase of 5.38%, which is reduced to 1.1% when only 10% of the samples are used. We calculate these numbers using the formula $\frac{\text{time}(\text{BRB})}{\text{time}(\text{No\,BRB})}=\frac{20*(\text{
Total\,runtime}-\text{BRB\,time})+\text{BRB\,time}}{20*(\text{Total\,runtime}-
\text{BRB\,time})}$. In our opinion, the overhead added by BRB is minor compared to its benefits and could, for instance, be further reduced by caching embeddings. Note that while the time increases with more frequent application of BRB, subsampling can further reduce the runtime at a minimal cost in clustering performance, as shown in Table 9 below:

**Table 9: MNIST ARI for different clustering algorithms and subsample sizes.**
| Subsample size | IDEC | DEC | DCN |
| --- | --- | --- | --- |
| 700 (1%) | $91.84\pm 1.99$ | $90.94\pm 2.37$ | $89.19\pm 1.59$ |
| 7000 (10%) | $93.04\pm 1.90$ | $90.04\pm 2.23$ | $91.99\pm 0.23$ |
| 17500 (25%) | $93.06\pm 1.90$ | $89.99\pm 2.43$ | $91.97\pm 0.22$ |
| 35000 (50%) | $93.05\pm 1.90$ | $90.49\pm 1.95$ | $92.08\pm 0.24$ |
| 70000 (100%) | $93.02\pm 1.90$ | $91.60\pm 1.93$ | $92.00\pm 0.21$ |

In Section 5, we state that “any centroid-based method” can be used for the reclustering stage of BRB. In Table 10, we analyze four different reclustering algorithms in terms of runtime: $k$-Means (Lloyd, ), $k$-Means++ initialization (Arthur et al., ), $k$-Medoids (Rdusseeun & Kaufman, ) and the expectation-maximization (EM) algorithm (Dempster et al., ). To calculate the percentage-based timings, we use the same formula as above. Unsurprisingly, EM takes the longest to run as it has to calculate full covariance matrices for all components of the fitted mixture model. $k$-Means++-init is the fastest, hinting at a possible strategy to speed up BRB. Our choice of $k$-Means provides simplicity while having intermediate speed.

**Table 10: Runtime in seconds for IDEC+BRB on MNIST with different reclustering algorithms.**
| Clustering<br>method | Reset<br>time | Embedding<br>time | Cluster<br>time | Momentum<br>reset time | BRB<br>time | Total<br>runtime | BRB % of total<br>runtime |
| --- | --- | --- | --- | --- | --- | --- | --- |
| EM | 0.006 | 0.465 | 8.944 | 0.001 | 9.416 | 10.239 | 91.968 |
| $k$-Means | 0.006 | 0.429 | 0.500 | 0.001 | 0.936 | 01.725 | 54.277 |
| $k$-Means++-init | 0.007 | 0.440 | 0.019 | 0.001 | 0.467 | 01.295 | 36.088 |
| $k$-Medoids | 0.007 | 0.446 | 2.768 | 0.001 | 3.222 | 04.007 | 80.410 |

### Appendix H Additional Results

In the following pages, we provide additional results and figures augmenting the findings of the main paper. We begin with ablation studies concerning embedding and momentum resets in Sections H.1 and H.2, respectively. An illustrative example of embedded space changes induced by BRB comes next. Lastly, we report ARI and NMI scores (see Section D) for our main experiments with and without pretraining.

#### H.1 Embedding Reset Ablation

Figure 10 shows an ablation for BRB with and without *Embedding-Reset*, for $T=20$ and $\alpha=0.8$ (same settings as in Experiment section of the main paper). We find small but consistent drops in average clustering accuracy for GTSRB and OPTDIGITS. Results for USPS and MNIST are mostly unaffected by embedding resets. Further, we found in initial experiments (not shown here) that embedding resets affect performance more severely for higher resets ($\alpha<0.7$). Thus, we do not use embedding resets in BRB.

Figure: Figure 10: Embedding reset ablation. Clustering accuracy averaged over ten seeds for baseline methods DCN/DEC/IDEC. Using weight resets on the embedding (*Embedding-Reset*) leads to performance drops for GTSRB and OPTDIGITS, whereas performance on USPS and MNIST is unaffected by it.
Refer to caption: x9.png

#### H.2 Momentum Reset Ablation

DEC and IDEC use learnable centroids that we optimize using the momentum-based Adam (Kingma & Ba, ) optimizer. In Figure 11, we compare BRB with and without momentum resets for $T=20$ and $\alpha=0.8$ (same settings as in the Experiment section of the main paper). We find that clustering accuracy drops considerably for IDEC on GTSRB and DEC on OPTDIGITS, while performance remains mostly unaffected for USPS and MNIST. To avoid large performance drops, we decided to always reset momentum in BRB for DEC and IDEC.

Figure: Figure 11: Momentum reset ablation for DEC and IDEC. Clustering accuracy averaged over 10 seeds for DEC and IDEC each. While performance for MNIST and USPS is almost unaffected if *No Momentum Reset*s are used, it drops considerably for IDEC on GTSRB and DEC on OPTDIGITS.
Refer to caption: x10.png

#### H.3 ResNet Block Reset Ablation

Table 11 shows the impact of resetting the different blocks of the ResNet18 on cluster accuracy. Note that the ResNet18 consists of four ResNet blocks, where blocks with a higher number are closer to the MLP encoder used in our architecture. This means that ResNet block 4 is closest to the embedding, and ResNet block 1 is closest to the input. We see that resetting block 1 does not induce any cluster improvement over the setting without any block reset (first line). We believe this is due to the lack of sufficient change induced in the embedding. The other extreme is resetting all ResNet blocks (last line), which leads to a large drop in performance. Resetting block 4 outperforms other block reset combinations in this experiment.

**Table 11: Reset ablation for IDEC+BRB of different ResNet18 blocks on CIFAR10 with and without reset of MLP encoder and fixed $\alpha=0.8$ and $T=10$ for contrastive auxiliary task. The ResNet18 consists of four ResNet blocks, where blocks with a higher number are closer to the MLP encoder, so ResNet block 4 is closest to the embedding, and ResNet block 1 is closest to the input. We report mean cluster accuracy with standard deviations over 5 runs.**
| Block reset | With MLP-Reset | Without MLP-Reset |
| --- | --- | --- |
| No Block reset | $82.39\pm 1.29$ | $82.15\pm 1.55$ |
| 1 | $82.36\pm 1.12$ | $82.22\pm 1.41$ |
| 4 | $84.56\pm 1.69$ | $84.29\pm 2.90$ |
| 1,2 | $82.17\pm 0.93$ | $82.03\pm 0.95$ |
| 4,3 | $81.29\pm 1.82$ | $81.73\pm 1.90$ |
| 4,3,2,1 | $68.84\pm 5.46$ | $70.56\pm 6.08$ |

#### H.4 Reclustering Algorithm Ablation

To isolate the effect of different reclustering algorithms on BRB, we conduct an ablation study, evaluating $k$-Means (Lloyd, ), $k$-Means++ initialization (Arthur et al., ), $k$-Medoids (Rdusseeun & Kaufman, ), and expectation-maximization (EM) (Dempster et al., ). Due to the computational cost of some algorithms, we use the smaller USPS dataset and run 10 trials for each method.

Table 12 presents the ARI for DEC, IDEC, and DCN using these reclustering methods. EM outperforms the others, achieving an average ARI of 79.46, while $k$-Means achieves 76.98. However, EM’s runtime is significantly longer, which we discuss further in Section G.2. This effect is most notable for larger datasets. Additionally, using BRB with EM is substantially more unstable, as can be seen by the increased standard errors.

Given BRB’s emphasis on scalability and simplicity, we choose $k$-Means as the reclustering algorithm. Although EM may offer improved performance, its higher computational cost makes it less suitable for our application.

**Table 12: ARI for DEC, IDEC, and DCN on the USPS dataset averaged over 10 seeds.**
| Reclustering algorithm | DEC | IDEC | DCN | Average |
| --- | --- | --- | --- | --- |
| EM | $\bm{79.93\pm 2.95}$ | $82.24\pm 2.28$ | $\bm{76.22\pm 1.02}$ | 79.46 |
| $k$-Means | $75.98\pm 1.27$ | $79.88\pm 0.33$ | $75.09\pm 1.54$ | 76.98 |
| $k$-Means++-init | $73.70\pm 1.60$ | $\bm{83.22\pm 2.89}$ | $67.87\pm 1.77$ | 74.93 |
| $k$-Medoids | $70.27\pm 2.51$ | $80.22\pm 2.40$ | $75.65\pm 1.89$ | 75.38 |

#### H.5 Voronoi Cells

To generate 2D visualizations of the embedded space, we select a subset of 4 classes on the USPS (Hull, ) dataset and embed these into two dimensions in Figure 12. We use DEC as clustering algorithm.

Figure: (a) Pre BRB
Refer to caption: extracted/5976891/media/voronoi_pre_brb.png

#### H.6 Additional Metrics with pretraining

In Figures 13(a) and 13(b), we report additional NMI and ARI results for experiments with pretraining.

Figure: (a) Performance experiments with pretraining measured in Normalized Mutual Information (NMI). NMI (averaged over DEC/IDEC/DCN and ten seeds) for *BRB* and important comparison methods: *Baseline+Reset* refers to performing only weight resets (Eq. 1), *Baseline+Recluster*, refers to only reclustering and *Baseline* are DEC/IDEC/DCN without modifications.
Refer to caption: x11.png

#### H.7 Additional Metrics without pretraining

In Figures 14(a) and 14(b), we report additional NMI and ARI results for experiments without pretraining.

Figure: (a) Performance experiments without pretraining measured in Normalized Mutual Information (NMI). NMI (averaged over DEC/IDEC/DCN and ten seeds) for *BRB* and important comparison methods as in Figure 13(a).
Refer to caption: x13.png

#### H.8 Detailed Ablations per Metric in Tabular Form

Tables 13, 14 and 15 show detailed results of our ablation experiments with and without pretraining.

Table: Table 13: Clustering accuracy for various datasets.

Table: Table 14: NMI performance comparison on various datasets.

Table: Table 15: ARI performance comparison on various datasets.

#### H.9 Detailed Results for Contrastive Auxiliary Task and Self-Labeling

Table 17 shows the mean cluster accuracy over ten runs for DEC, IDEC and DCN with and without BRB. We see that BRB always improves performance and leads to more than 2% increase for DCN on CIFAR10. Using self-labeling as proposed in SCAN (Gansbeke et al., ) we achieve even higher cluster accuracies as stated in Table 16. While DEC does not benefit as much from BRB, we find that IDEC+BRB and DCN+BRB clearly outperform SCAN by up to 6% on CIFAR100-20.

**Table 16: Ablation results with contrastive auxiliary tasks and self-labeling. Reporting mean cluster accuracy with standard deviations over 10 runs. Results from SCAN with self-labeling for reference (SeCu did not provide average performance results).**
| Methods | CIFAR10 | CIFAR100-20 |
| --- | --- | --- |
| DEC | $85.77\pm 2.28$ | $\mathbf{48.37\pm 1.39}$ |
| DEC + BRB | $\mathbf{86.98\pm 2.28}$ | $47.18\pm 2.63$ |
| IDEC | $85.89\pm 2.04$ | $48.85\pm 1.70$ |
| IDEC + BRB | $\mathbf{86.50\pm 3.24}$ | $\mathbf{50.00\pm 2.12}$ |
| DCN | $85.25\pm 3.11$ | $51.13\pm 1.65$ |
| DCN + BRB | $\mathbf{89.29\pm 0.72}$ | $\mathbf{52.32\pm 1.95}$ |
| SCAN (Gansbeke et al., ) | $87.60\pm 0.40$ | $45.90\pm 2.70$ |

**Table 17: Ablation performance with contrastive task only. Reporting mean cluster accuracy with standard deviations over 10 runs. Per method, the best result is set in bold, and the overall best result is underlined. BRB enables consistent improvements for DCN and IDEC on all datasets.**
| Methods | CIFAR10 | CIFAR100-20 |
| --- | --- | --- |
| DEC | $83.00\pm 1.65$ | $46.23\pm 1.17$ |
| DEC + BRB | $\mathbf{83.86\pm 1.72}$ | $\mathbf{46.63\pm 1.32}$ |
| IDEC | $82.12\pm 1.54$ | $46.79\pm 1.84$ |
| IDEC + BRB | $\mathbf{84.35\pm 1.06}$ | $\mathbf{47.92\pm 0.87}$ |
| DCN | $79.64\pm 1.98$ | $44.03\pm 1.13$ |
| DCN + BRB | $\mathbf{82.16\pm 0.57}$ | $\mathbf{44.89\pm 1.49}$ |

#### H.10 Detailed Analysis of Inter-CD and Intra-CD behavior in Figure 6.3

The behavior of the continually increasing intra- and inter-class distances (CD) of DCN(+Reclustering) for MNIST in Figure 6.3 can be analyzed through the silhouette score Rousseeuw (), which is defined as the ratio between the intra- and inter-CD. The baseline models exhibit proportional increases in intra- and inter-CD, resulting in a stable silhouette score (Figure 15). This indicates that the optimizer expands the embedding space without improving cluster separation, likely due to the absence of weight decay. In contrast, BRB’s soft resets help maintain small parameter and gradient norms during training (Ash & Adams, ). This allows BRB to effectively reduce intra-CD while increasing inter-CD, leading to enhanced cluster separation and a higher silhouette score.

Figure: Figure 15: Behavior of intra- and inter-CD Figure 6.3 of our main paper augmented by showing the silhouette score in addition to average clustering accuracy, inter/intra-class distance (inter/intra-CD), and cluster label change (CL Change) for DCN on MNIST. The silhouette score is defined as the ratio between the intra- and inter-CD. The plot shows that without BRB, the proportional rise in intra- and inter-CD leads to a flat silhouette score, indicating rising embedding magnitudes without improving separation. In contrast, BRB’s soft resets counteract increases in the embedding norms, allowing the cluster loss to better separate ground truth classes over time (lower intra-CD, slowly increasing silhouette score).
Refer to caption: x15.png

## Peer Reviews

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
questions: Why do the authors only consider the CIFAR100 supersets (CIFAR100-20) instead of clustering 100 classes?
soundness: 3
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.
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.
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)

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
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?
soundness: 3
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.
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.
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.

---

confidence: 5
contribution: 2
initial_rating: 5
presentation: 3
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?
soundness: 3
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.
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.
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

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
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?
soundness: 4
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.
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.
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.

Meta-review: 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.

Decision: Accept (Poster)