You Never Cluster Alone
Year: 2022

Abstract:
Recent advances in self-supervised learning with instance-level contrastive objectives facilitate unsupervised clustering. However, a standalone datum is not perceiving the context of the holistic cluster, and may undergo sub-optimal assignment. In this paper, we extend the mainstream contrastive learning paradigm to a cluster-level scheme, where all the data subjected to the same cluster contribute to a unified representation that encodes the context of each data group. Contrastive learning with this representation then rewards the assignment of each datum. To implement this vision, we propose twin-contrast clustering (TCC). We define a set of categorical variables as clustering assignment confidence, which links the instancelevel learning track with the cluster-level one. On one hand, with the corresponding assignment variables being the weight, a weighted aggregation along the data points implements the set representation of a cluster. We further propose heuristic cluster augmentation equivalents to enable cluster-level contrastive learning. On the other hand, we derive the evidence lower-bound of the instance-level contrastive objective with the assignments. By reparametrizing the assignment variables, TCC is trained end-to-end, requiring no alternating steps. Extensive experiments show that TCC outperforms the state-of-the-art on challenging benchmarks.

heading: 1 Introduction
text: Ancestored by various similarity-based [59] and feature-based [4, 56] approaches, unsupervised deep clustering jointly optimizes data representations and cluster assignments [81]. A recent fashion in this domain takes inspiration from contrastive learning in computer vision [11, 12, 24], leveraging the effectiveness and simplicity of discriminative feature learning. This strategy is experimentally reasonable, as previous research has found that the learnt representations reveal data semantics and locality [34, 80]. Even a simple migration of contrastive learning significantly improves clustering performance, of which examples include a two-stage clustering pipeline [73] with contrastive pretraining and k-means [56] and a composition of an InfoNCE loss [62] and a clustering one [81] in [89]. Compared with the deep generative counterparts [16, 36, 54, 86], contrastive clustering is free from decoding and computationally practical, with guaranteed feature quality.
However, have we been paying too much attention to the representation expressiveness of a single data point? Intuitively, a standalone data point, regardless of its feature quality, cannot tell us much about how the cluster looks like. Fig. 1 illustrates a simple analogy using the TwoMoons dataset. Without any context for the crescents, it is difficult to assign a data point to either of the two clusters based on its own representation, as the point can be inside one moon but still close to the other. Accordingly, observing more data reveals more about the holistic distributions of the clusters, e.g., the shapes of the moons in Fig. 1, and thus heuristically benefits clustering. Although we can implicitly parametrize the context of the clusters by the model itself, e.g., using a Gaussian mixture model (GMM) [4] or encoding this information by deep model parameters, explicitly representing the context yields the most common deep learning practice. This further opens the door for learning cluster-level representations with all corresponding data points. Namely, you never cluster alone.
∗A part of this work was done when the author was with eBay.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In this paper, motivated by the thought experiment above, we develop a multi-granularity contrastive learning framework, which includes an instance-level granularity and a cluster-level one. The former learning track conveys the conventional functionalities of contrastive learning, i.e., learning compact data representations and preserving underlying semantics. We further introduce a set of latent variables as cluster assignments, and derive an evidence lower bound (ELBO) of instance-level InfoNCE [62]. As per the cluster-level granularity, we leverage these latent variables as weights to aggregate all the corresponding data representations as the set representation [87] of a cluster. We can then apply contrastive losses to all clusters, thereafter rewarding/updating the cluster assignments. Abbreviated as twin-contrast clustering (TCC), our work delivers the following contributions:
• We develop the novel TCC model, which, for the first time, shapes and leverages a unified representation of the cluster semantics in the context of contrastive clustering.
• We define and implement the cluster-level augmentations in a batch-based training and stochastic labelling procedure, which enables on-the-fly contrastive learning on clusters.
• We achieve significant performance gains against the state-of-the-art methods on five benchmark datasets. Moreover, TCC can be trained from scratch, requiring no pre-trained models or auxiliary knowledge from other domains.

heading: 2 Preliminaries

heading: 2.1 Contrastive Learning
text: Contrastive learning, as the name suggests, aims to distinguish an instance from all others using embeddings, with the dot-product similarity typically being used as the measurement. Let X = {xi}Ni=1 be an N -point dataset, with the i-th observation xi ∈ Rdx . An arbitrary transformation f : Rdx → Rdm encodes each data point into a dm-dimensional vector. With the index i being the identifier, the InfoNCE loss [62] discriminates xi from the others through a softmax-like likelihood:
log p (i|xi) = log exp (vᵀi f(xi)/τ)∑N j=1 exp ( vᵀj f(xi)/τ ) . (1) A temperature hyperparameter τ controls the concentration level [26, 80]. V = {vi}Ni=1 refers to the vocabulary of the dataset, which is usually based on the data embeddings under different augmentations. As caching the entire V is not practical for large-scale training, existing works propose surrogates of Eq. (1), e.g., replacing V with a memory bank [80], queuing it with a momentum network [12, 24], or training with large batches [11].

heading: 2.2 Deep Set Representations
text: To learn the representations of sets, we need to consider permutation-invariant transformations. Zaheer et al. [87] showed that all permutation-invariant functions T (·) applied to a set X generally fall into the following form:
T (X) = g (∑N i=1 h(xi) ) , (2)
where g(·) and h(·) are arbitrary continuous transformations. Note that the aggregation above can be executed on a weighted basis, which is typically achieved by the attention mechanism between the set-level queries and instance-level keys/values [31, 49]. Our design on each cluster is partially inspired by this, as back-propagation does not support hard instance-level assignment. Next, we define our cluster representation along with the clustering procedure, and describe how it is trained with contrastive learning.

heading: 3 Twin-Contrast Clustering
text: We consider a K-way clustering problem, with K being the number of clusters. Let k ∈ {1, · · · ,K} denote the entry of a cluster that xi may belong to, and the categorical variable πi = [πi(1), · · · , πi(K)] indicate the cluster assignment probabilities of xi. Following common practice, we regard image clustering as our target for simplicity. Fig. 2 provides a schematic of TCC. The cluster-level contrast track reflects our motivation from Sec. 1, while the instance-level one learns the semantics of each image. We bridge these two tracks with the inference model πi(k) = qθ(k|xi) so that both losses reward and update the assignment on each xi. In particular, qθ(k|xi) is parametrized by a softmax operation:
πi(k) = qθ(k|xi) = exp(µᵀk fθ(xi))∑K
k′=1 exp(µ ᵀ k′ fθ(xi))
, (3)
where fθ(·) is a convolutional neural network (CNN) [47, 48] built upon random data augmentations, producing dm-dimensional features. We denote µθ = {µk}Kk=1 as a set of trainable cluster prototypes, where θ refers to the collection of all parameters. In Sec. 3.1, we leverage qθ(k|xi) to aggregate cluster features, and in Sec. 3.2 we derive the ELBO of Eq. (1) with qθ(k|xi). In the following, we will omit the index i for brevity when x and π clearly correspond to a single data point.

heading: 3.1 Representing and Augmenting the Context for Cluster-Level Contrast
text: Cluster-Level Representation We implement Eq. (2) for each cluster using soft aggregation, where qθ(k|x) weighs the relevance of the data to the given cluster. Denoted as rk, the k-th cluster representation is computed by:
hθ(x; k) = π(k) · fθ(x),
rk = Tθ(X; k) = (∑N i=1 hθ(xi; k) )/∥∥∥∥∑Ni=1 hθ(xi; k) ∥∥∥∥ 2 , (4)
where ‖·‖2 refers to the L2-norm. We adopt L2 normalization here for two main purposes. First, the summation of π(k) = qθ(k|x) along x is not self-normalized. Second, and more importantly, as shown in [11, 12, 24], L2-normalized features benefit contrastive learning.
The Anchored Cluster Semantics Intuitively, π(k) reflects the degree of relevance of a datum to the k-th cluster. With it being the aggregation weight, rk represents the information that is related to the corresponding prototype µk. In other words, our design treats each µk as the semantic anchor that queries the in-coming batch to form a representation describing a certain latent topic.
Cluster-Level Augmentation Equivalents Contrastive learning is usually employed alongside random data augmentation [11, 24] to obtain positive candidates. Though defining a uniform augmentation scheme for sets is beyond the scope of this paper, the proposed model reflects clusterlevel augmentation in its design by the following heuristics:
(a) Augmentation on elements. TCC implicitly inherits existing image augmentation techniques (such as cropping, color jittering, random flipping, and grayscale conversion) by implementing them using fθ(·).
(b) Irrelevant minorities. We consider injecting a small proportion of irrelevant data into a cluster representation, while keeping the main semantics of the cluster unchanged. Eq. (4) turns out to be an equivalent to this. As the softmax product π(k) is always positive, those data that are not very related to the given cluster still contribute to the cluster’s representation, which compiles the irrelevant. Meanwhile, these irrelevant data are not dominating the value of the cluster representation, because the small value of π(k) scales the feature magnitude during aggregation, which counts the minority.
(c) Subsetting. Empirically, a subset of a cluster holds the same semantics as the original. Batch-based training samples data at each step, which naturally creates subsets for each cluster.
We experimentally find the above augmentation equivalents are sufficient for the clustering task. On the other hand, since Eq. (4) is permutation-invariant, reordering the sequence of data does not yield a valid augmentation.
Cluster-Level Contrastive Learning We define a simple contrastive objective that preserves the identity of each cluster against the rest. Having everything in a batch, e.g., a SimCLR-like framework [11], does not allow augmentation (c) to be fully utilized in the loss, since the two augmented counterparts rk and r̂k from a batch may form part of the same subset of a cluster. Hence, we opt for the MoCo-like solution [24], employing an L-sized memory queue P = {pl}Ll=1 to cache negative samples and a momentum network to produce r̂k = Tθ̂(X; k). P stores each cluster representation under different subsets, training with which preserves the temporal semantic consistency [45] of clusters. Our cluster-level objective minimizes the following negative loglikelihood (NLL):
L1 = Ek[− log pθ(k|rk)] = − 1
K K∑ k=1 log exp(r̂ᵀkrk/τ) exp(r̂ᵀkrk/τ) + ∑L l=1 exp(p ᵀ l rk/τ)1(l mod K 6= k) ,
(5) where 1(·) is an indicator function and mod is the modular operator. Since the cluster number K can be less than the queue size L, we exclude the features that represent the same cluster as k in the negative sample collection P by inserting the indicator function into the loss above.

heading: 3.2 Instance-Level Contrast with Cluster Assignments
text: The ELBO We propose to reuse the inference model qθ(k|x) discussed above to compute the instance-level contrastive loss, so that the clustering process can benefit from contrastive learning. Let us start from the following ELBO of log pθ(i|x) in Eq. (1):
log pθ(i|x) ≥ Eqθ(k|x) [log pθ(i|x, k)]−KL (qθ(k|x)||pθ(k|x)) , (6) where KL(·) is the Kullback–Leibler (KL) divergence. We derive this ELBO in Appendix A. The true distribution pθ(k|x) is not available under the unsupervised setting. We follow [40, 69] and use a fixed prior instead. In practice, we employ the uniform distribution, i.e., pθ(k|x) := pθ(k) = 1/K. Then, the KL term above can be reduced to a simple form−KL (qθ(k|x)||pθ(k|x)) = logK+H(qθ(k|x)). Empirically, this encourages an evenly distributed cluster assignment across the dataset.
Regarding the expectation term in Eq. (6), back-propagation through the discrete entry k is not feasible. We resort to the Gumbel softmax trick [32, 57] as relaxation. Specifically, a latent variable c ∈ (0, 1)K is assigned to each x as a replacement. Each entry c(k) yields the reparametrization c(k) = Softmaxk((log π(k) + (k))/λ), where ∼ Gumbel(0, 1) and λ is another temperature hyperparameter. Hence, we obtain the surrogate Eqθ(k|x) [log pθ(i|x, k)] ' E [log pθ(i|x, c)] and the gradients can be estimated with Monte Carlo.
Instance-Level Contrastive Learning In alignment with Eq. (5), log pθ(i|x, c) learns the representation of x on a momentum contrast basis [24] by defining the following transformation:
e = (fθ(x)+NNθ(c))/‖fθ(x) + NNθ(c)‖2,
log pθ(i|x, c) = log exp(êᵀe/τ) exp(êᵀe/τ) + ∑J j=1 exp(q ᵀ j e/τ) , (7)
where NNθ(·) denotes a single fully connected network. We accordingly use ê to indicate the representation of x processed by a momentum network fθ̂(·) and NNθ̂(·) under different augmentations and Gumbel samplings [32, 57]. A J-sized memory queue Q = {qj}Jj=1 is also introduced to cache negative samples, updated by ê. In this way, we obtain the instance-level loss:
L2 = Ei[−E i [log pθ(i|xi, ci)]−H(qθ(k|xi))− logK]. (8)
3.3 Training and Inference
Algorithm 1: Training Algorithm of TCC Input: Dataset X = {xi}Ni=1 Output: Network parameters θ. Initialize θ̂ = θ repeat
Randomly select a mini-batch from X for each xi in the batch do
Randomly augment xi twice Sample ci with Gumbel softmax
end L ←Eq. (9) θ ← θ − Γ (∇θL) Update the queues P with r̂ and Q with ê Update θ̂ with momentum moving average
until convergence or reaching max iteration;
TCC enables end-to-end training from scratch. Our learning objective is a simple convex combination of Eq. (5) and (8), i.e.,
L = αL1 + (1− α)L2. (9) The hyperparameter α ∈ (0, 1) controls the contributions of the two contrastive learning tracks. As discussed in Sec. 3.1, L is computed following a batch-based routine. For each data point x, we obtain only one sample c from the Gumbel distribution at each step, since this is usually sufficient for long-term training [39, 40, 69]. One may also regard this stochasticity as an alternative to data augmentation. The overall training algorithm is shown in Alg. 1. Here, Γ(·) indicates an arbitrary stochastic gradient descent (SGD) optimizer. All trainable components are subscripted by θ, while those marked with θ̂ are the network momentum counterparts to be updated with momentum moving average. Inference with TCC only requires disabling random data augmentation and then computing argmaxk qθ(k|x). Complexity When sampling once for each x during training, the time complexity for Eq. (9) is O(L+J), while the memory complexity for the memory bank turns out to be the same. Here we omit the complexity introduced by the CNN backbone and dot-product computation, as it is orthogonal to the design. Compared with the recent mixture-of-expert approach [73], which requires a time and memory complexity of O(KJ), TCC is trained in a more efficient way.

heading: 3.4 Relations to Existing Works
text: MiCE [73] also proposes a lower bound for the instance-level contrastive objective. However, it does not directly reparametrize the variational model qθ(k|x) for lower-bound computation and inference, but instead employs a K-expert solution with EM. This design is less efficient than TCC since each data point needs to be processed by all K experts. Moreover, MiCE [73] does not consider cluster-level discriminability. SCL [28] follows a similar motivation to TCC in cluster-level discriminability, but it implements this with an instance-to-set similarity, while our model learns a unified representation for each cluster. Furthermore, in SCL [28], the clustering inference model is disentangled from the instance-level contrastive objective. In contrast, the inference model qθ(k|x) of TCC contributes to instance-level discrimination (Eq. (6)).
We recently find CC [53] comes with a cluster-level contrastive loss as well. It utilizes the in-batch inference results [π1(k), · · · , πn(k)] to describe the k-th cluster. However, this procedure is not literally learning the cluster representation, since it is not permutation free. Re-ordering the batch may shift the semantics of the produced feature. We mitigate this issue with deep sets [87] and the empirical cluster-level augmentations for temporal consistency [45]. A similar problem is witnessed in [66]. In addition, our instance-level discrimination model yields a more general case than the one
of CC [53]. When removing the stochasticity and enforcing pθ(i|x, c) := pθ(i|c) in our model, L2 reduces to the one of [53]. We experimentally show that our design preserves more data semantics, and thus benefits clustering. Being not related to our main contribution, we provide more elaboration on this in Appendix B under the framework of variational information bottleneck [2].

heading: 4 Related Work
text: Deep Clustering In addition to the classic approaches [4, 13, 18, 20, 43, 56, 59, 78, 91], the concept of simultaneous feature learning and clustering with deep models can be traced back to [81, 83]. The successors, including [9, 23, 61, 68, 77, 79, 85], have continuously improved the performance since. As a conventional option for unsupervised learning, deep generative models are also widely adopted in clustering [10, 16, 35, 36, 42, 51, 58, 86, 90], usually backboned by VAE [39] and GAN [21]. However, generators are computationally expensive for end-to-end training, and often less effective than the discriminative models [15, 27, 33] in feature learning [11]. Recent research has considered contrastive learning in clustering [28, 53, 73, 74, 89]. We discuss the drawback of them and their relations to TCC in Sec. 3.4.
Contrastive Learning Contrastive learning learns compact image representations in a selfsupervised manner [11, 12, 24, 62, 72]. There are various applications for this paradigm [34, 41, 82, 93]. We note that several contrastive learning approaches [7, 52] conceptually involve a clustering procedure. Nevertheless, they are based on a unified pre-training framework to benefit the downstream tasks, instead of delivering a specific clustering model.
Set Representations Our cluster-level representation (Eq. (4)) is a realization of deep sets [17, 87]. Existing research in this area mainly focuses on set-level tasks [19, 31, 37, 76, 84]. It is also notable that, though we leverage cluster-level representation learning, TCC is still an instance-level clustering model, which is different from the set-level clustering models [49, 50, 63].
5 Experiments 5.1 Settings
We follow the recent works [29, 33] and report the performance of TCC in terms of clustering accuracy (ACC) [81], normalized mutual information (NMI) [70] and adjusted random index (ARI) [30]. For fair comparison with existing works, we do not use any supervised pre-trained models. The experiments are conducted
on five benchmark datasets, including CIFAR-10/100 [44], ImageNet-10/Dog [9] and STL-10 [14]. Note that ImageNet-10/Dog [9] is a subset of the original ImageNet dataset [67]. Since most existing works have pre-defined cluster numbers, we adopt this practice and follow their training/test protocols [29, 33, 61, 73]. Tab. 1 depicts the details of the settings.

heading: 5.2 Implementation Details
text: TCC is implemented with the deep learning toolbox TensorFlow [1]. We choose the MoCo-style random image augmentations [24] for fair comparison with the recent works [28, 73]. We further link our choice of augmentations with the cluster representation temporal consistency in Sec. 3.1. Specifically, each image is successively processed by random cropping, gray-scaling, color jittering, and horizontal flipping, followed by mean-std standardization. We refer to [24, 73] for more details. We employ ResNet-34 [25] as the default CNN backbone fθ(·), which is also identical to [28, 73]. Appendix C gives a full illustration of the CNN structure. The image size dx and cluster number K are fixed for each dataset, as shown in Tab. 1. The feature dimensionality produced by CNN is dm = 128. Following common practice [12, 24, 11], we fix the contrastive temperature τ = 1, while using a slightly lower λ = 0.8 for the Gumbel softmax trick [32, 57] to encourage concrete assignments. We implement a fixed-length instance-level memory bank Q with a size of J = 12, 800 to match up with the smallest dataset in our experiments. The size of the cluster-level memory bank P is set to L = 100×K, varying from each dataset. We have α = 0.5 so that L1 and L2 provide equal contributions to training. The choice of batch size is of importance to TCC in computing
the cluster-level representations. We set it to 32 × K by default to ensure that sufficient images can be assigned to a cluster at each step. Training TCC only requires SGD w.r.t. θ and momentum update w.r.t. θ̂. We employ the Adam optimizer [38] with a default learning rate of 3× 10−3, without learning rate scheduling. The momentum network is updated by θ̂ ← 0.999θ̂ + 0.001θ, where all modules subscripted by θ̂ are involved in this procedure. We train TCC for at least 1, 000 epochs on a single NVIDIA V100 GPU.
5.3 Comparison with the State-of-the-Art
Baselines Both deep clustering and traditional models are compared, including a MoCO-based two-stage baseline introduced by [73]. Similar to the recent works [29, 33, 73, 79], we pick deep models that enable training from scratch and do not require supervised pre-training parameters, for fair and reasonable comparison. For this reason, baselines such as VaDE [36] and SPICE [60] are not included here. We also exclude the clustering refinement approaches [64] from our comparison as they are orthogonal to our design.
Results The clustering performance (in percentage %) is shown in Tab. 2. For those baselines that are not designed for clustering [3, 21, 39], we report the results with k-means on the produced features. TCC outperforms existing works on most benchmarks. In particular, on CIFAR-10 [44], TCC outperforms the state-of-the-art methods by large margins, e.g., 7% higher in ACC than the second best one (i.e., MiCE [73] with even stronger augmentations [11]). As a closely-related work, MiCE [73] only considers instance-level representation learning. The performance gain of TCC over MiCE endorses our motivation to introduce cluster-level representations. We also observe that TCC underperforms [53] on STL-10 [14] due to the exceptionally high performance of it on this dataset. However, TCC is still the runner-up on this dataset by a significant margin, and is superior to [53] on the other four datasets. We
argue that the performance on larger datasets is of more importance when comparing contrastive deep clustering methods, as contrastive learning is originally designed for large-scale tasks. Fig. 3 illustrates the t-SNE [55] scattering results of TCC on CIFAR-10 [44] and STL-10 [14].

heading: 5.4 Ablation Study
text: We conduct an ablation study to validate our motivation and design, with the following baselines.
(i) Without L1. As a key component of TCC, the cluster-level contrastive learning objective L1 reflects our main motivation. We first assess the model performance when removing this loss, which reduces TCC to a simple instance-level contrastive clustering model. (ii) Without L2. We can also remove L2 to see if L1 alone still yields a valid baseline. (iii) Multiple Sampling. As described in Sec. 3.3, we only consider a single sample c each time to compute the lower bound of the instance-level loss (Eq. (8)). We also consider applying the Gumbel softmax trick multiple times for each image. In particular, we sample 10 groups of latent variables each time to compute the expectation term E [log pθ(i|x, c)] of L2. On each batch, we enqueue the mean of ê w.r.t. all 10 sampled c for each image. (iv) Without P. Since we usually have a small cluster number K, computing the cluster-level InfoNCE loss does not necessarily require a memory bank to cache the negative sample surrogates. In this baseline, we remove the cluster-level memory bank P, and use the remaining K − 1 cluster representations as negative samples when computing Eq. (5). (v) Without Augmentation (a) for L1. We validate our cluster-level augmentation strategies by removing image augmentations when computing Eq. (8). Note that this baseline does not influence the instance-level objective by rendering both augmented and original images to fθ(·). (vi) Without Augmentation (b) for L1. This baseline requires hard assignments at each step so that cluster-level aggregation only involves images that are assigned to the corresponding clusters. This modification does not affect L2. (vii) Without Augmentation (c) for L1. The final baseline changes the training pipeline. Since we do not subset any clusters here, cluster representation aggregation (Eq. (4)) runs on the whole training set after each epoch. We apply alternating training procedure as follows. First, L2 optimizes the model for a full epoch. Then, we descend L1 with aggregated cluster features and repeat.
Baseline Comparison Results We show the ablation study results in Tab. 3. Without L1, TCC performs similarly to the two-stage baseline with MoCo [24] and k-means [56] reported in [73], which is slightly lower than MiCE [73]. Interestingly, L1 does not provide instance-level discriminative information. Although it does still serve as a valid baseline, it does not perform very well (Baseline (ii)). Specifically, we
experience strong degeneracy [6, 33] with this baseline, but it still produces better results than the traditional models. We also observe that having multiple samples with the Gumbel softmax trick [32, 57] for gradient estimation does not make much difference from a single-sample solution. Baseline (iv) also underperforms the original model. As discussed in previous sections, having a memory bank for cluster representations provides a way to acquire more negative samples for contrastive learning, considering the fact that the cluster number is usually limited.
Hyperparameters We evaluate the hyperparameters most essential to our design, including the loss weight α, the temperature of the Gumbel softmax λ, the cluster-level memory queue length L, and the batch size. The InfoNCE temperature τ and the instance-level memory queue length J are not included here since they are not relevant to our key motivation and have been employed and evaluated in the recent works [24, 28, 73]. The corresponding results are plotted in Fig. 4. Though L1 plays an
essential role in the proposed model, having large values of α does not improve the performance, as the key instance-level semantics are yet learnt by L2. Only a reasonable proportion of L1, e.g., α = 0.25 or 0.5, in the overall learning objective improves the performance of our model. Further, we find that TCC is not very sensitive to the Gumbel softmax temperature λ, while a moderate hardness of the softmax produces the best results. Empirically, a large batch size benefits TCC, since more data can be involved in the subset of each cluster. Hence the aggregated features on each batch can be more representative. Fig. 4 (d) endorses this intuition. However, training with extremely large batch sizes may lead to out-of-memory problems with large images. To enable training on a single device, we opt to have a fixed batch size of 32×K in all experiments.
5.5 More Results
Training Time We compare the training epochs (Fig. 5 (a)) and training time (Fig. 5 (a)) of TCC and the re-implemented version of MiCE [73] with the same optimizer setting. As discussed in Sec. 3.3, MiCE obtains a higher time complexity during training than TCC. This is reflected in Fig. 5 (b), though not linearly proportional. In addition, TCC requires less training steps than MiCE to reach the best-performing results.
Conventional Clustering Losses During training, we also cache and observe the DEC loss [81], but we are not optimizing the model with it. In Fig. 5 (c), we show that by minimizing L (Eq. (9)), the traditional DEC loss [81] also decreases. This implicitly endorse our design.
Assumptions in Design One merit of constrastive learning is that one does not need to assume any empirical prior distribution to the feature space, which benefits
TCC when learning the cluster-level representations. The only assumption we employ is that the true posterior pθ(k|x) should be uniform to simplify the computation of the KL-divergence in Eq. (6). As previously discussed, this conventional relaxation [69] is intuitively valid since we generally expect evenly assigned clusters. It is illustrated in Fig. 6 that TCC achieves this during training by minimizing KL (qθ(k|x)||pθ(k|x)) = − logK −H(qθ(k|x)).

heading: 6 Conclusion
text: Inspired by the recent success of self-supervised learning, this paper proposes a multi-granularity contrastive clustering framework to exploit the holistic context of a cluster in an unsupervised manner. The proposed TCC simultaneously learns instance- and cluster-level representations by leveraging cluster assignment variables. Cluster-level augmentation equivalents are derived to enable on-the-fly contrastive learning on clusters. Moreover, by reparametrizing the assignment variables, TCC can be trained end-to-end without auxiliary steps. Extensive experiments validate the superiority of TCC, which consistently outperforms competitors on the five benchmarks often by large margins, echoing our major motivation, i.e., we are not clustering alone.

heading: Acknowledgments
text: This work is supported by the UKRI grant: Turing AI Fellowship EP/W002981/1 and EPSRC/MURI grant: EP/N019474/1. We also acknowledge the philanthropic support of the donors to the University of Oxford’s COVID-19 Research Response Fund: BRD00230. We would like to thank the Royal Academy of Engineering and FiveAI.

Review summaries:
The authors propose a method for end-to-end deep clustering. Authors utilizes NCE loss and proposes a method to produce cluster level loss. They motivate their approach and supply empirical evaluation.

This paper proposed a new clustering method called Twin-Contrast Clustering(TCC), which extends the mainstream contrastive learning paradigm to a cluster-level scheme. TCC simultaneously learns instance- and cluster-level representations by leveraging cluster assignment variables. And TCC uses Gumbel Softmax to reparametrize the assignment variables, which makes TCC is able to be trained end-to-end without auxiliary steps.

For image clustering, this paper extends the mainstream contrastive learning paradigm to a cluster-level scheme, and proposes twin-contrast clustering. Heuristic cluster augmentation equivalents are presented to enable cluster-level contrastive learning. Besides, this paper also derives the evidence lower-bound of the instance-level contrastive objective with the assignments. Experiments on several datasets demonstrate its superiority.

This paper extends the mainstream contrastive learning paradigm to a cluster-level scheme. Specifically, the author propose twin-contrastive clustering (TCC),  which links the instance-level learning track with the cluster-level one. Extensive experiments show the advantages of TCC.