Locally Normalized Soft Contrastive Clustering for Compact Clusters

1 Introduction

Clustering aims to separate scattered N data samples X = {Xi}Ni=1 in a feature space into different groups (e.g., K number of clusters) in an unsupervised manner. In general, the priority is to gather the samples within the same group close and make the samples across different clusters distinct from each other. As a fundamental topic in machine learning, clustering has played critical roles in a broad range of fields including gene sequence clustering in bioinformatics [Petegrosso et al., 2020; Zou et al., 2020], creation of perfectionism profiles in social science [Bolin et al., 2014], unsupervised image segmentation [Kanezaki, 2018; Ji et al., 2019], document clustering in information retrieval [Xu et al., 2003; Fard et al., 2020; Costa and Ortale, 2020] and etc.

Traditional methods such as k-means [MacQueen and others, 1967], DenPeak [Rodriguez and Laio, 2014], DBSCAN [Ester et al., 1996], and Spectral Clustering [ZelnikManor and Perona, 2005; Chen and Cai, 2011] have been effective when datasets used to be relatively small. As recent datasets become larger in both size and dimension, traditional shallow methods suffer from high computational complexity. Various Deep Clustering (DC) techniques have been recently developed to cope with issues of conventional methods. The core of DC consists of two components: 1) Dimension Reduction with Deep Learning (e.g., autoencoder, self-supervised learning) for mapping high-dimensional data onto a low-dimensional space and 2) Self-training the lowdimensional embedding to further improve clustering results from traditional clustering algorithms such as k-means [Xie et al., 2016; Ghasedi Dizaji et al., 2017].

The premise behind the DC algorithms is that suitable lowdimensional embeddings and cluster centers will assign each sample to a vivid individual cluster. These techniques focus on optimizing 'cluster assignment probability' - a likelihood of a sample belonging to each cluster. Many DC methods minimize Kullback-Leibler (KL) divergence between the distribution of the cluster assignment probability and an auxiliary target distribution directly computed from it, or directly use Fully Connected (FC) Layers to predict the cluster assignment probability. This process makes the assignment probability localized to a single cluster for each sample.

Unfortunately, many DC approaches suffer from two major bottlenecks. First, the initial clusters usually computed from a centroid-based clustering algorithm with random initialization, e.g., k-means, often cause stability issues when the lowdimensional embedding is not sufficiently effective for clustering. This problem can be restrictively relieved for image data using self-supervised learning (e.g., SimCLR, MoCo, SwAV) to learn a better feature space for the initial clustering [Van Gansbeke et al., 2020; Caron et al., 2020], but not for other types of data. The second issue, perhaps even more critical, stems from the self-training process and FC layers where the update of cluster assignment probability is mainly focused on clustering easy samples close to the centers and overlooks the samples near the "boundary" of clusters.

In fact, for clustering, what matters over the variation in the data is the relationships between data samples (i.e., structure) typically represented as a graph, e.g., k-nearest neighbor (kNN) graph. Also, a sound clustering method should provide compact clusters that are distinct from each other. This can be done by pulling similar samples together and pushing dissimilar samples apart in a latent space in a contrastive way.

While many contrastive learning methods have been successful, they mainly work on identifying similar sample pairs (i.e., positive pairs) for optimization. However, focusing only on the positive pairs, a.k.a., "hard contrastive learning", may not be effective in practice as seen in k-Nearest Neighbors classification on ImageNet [Van Gansbeke et al., 2020] when the data are in high-dimensional space with large variations.

In this regards, for effective compact clustering, we propose the following hypothesis: the method should be able to 1) accurately separate samples near cluster boundaries where the similarities among the neighborhood have large variation, 2) compactly contract similar samples near cluster centers, 3) completely disconnected samples should be expanded far apart. For this, we propose an end-to-end clustering algorithm that implements our ideas above in three different phases. The key is to consider both positiveness and negativeness for each pair of samples together in a "soft contrastive" way rather than the hard contrastive scheme. Our work demonstrates the following contributions:

• (i) we propose a novel method "Locally Normalized Soft Contrastive Clustering" (LNSCC) that achieve very compact clusters by introducing the concept of contrastive learning to the clustering task,
• (ii) LNSCC performs dimension reduction, self-training and clustering simultaneously as a unified framework,
• (iii) we carry extensive empirical validation of LNSCC with various independent datasets, demonstrating competitive qualitative and quantitative performances.

Fig. 1 (d) is a teasing result from LNSCC achieving localized clusters in a learnt 2D space using high-dimensional MNISTtest data, and its details are introduced in the following.

2 RelatedWork

Deep Clustering introduces deep learning into clustering to learn effective representations and cluster assignments [Guo et al., 2019; Xie et al., 2016; Yang et al., 2019; Huang et al., 2020]. In [Ghasedi Dizaji et al., 2017], a denoised autoencoder was used to further improve the low-dimensional embedding and increased clustering performance. Some DC methods demonstrated more powerful results with data augmentation. SCAN [Van Gansbeke et al., 2020], GCC [Zhong et al., 2021], SwAV [Caron et al., 2020] and MiCE [Tsai et al., 2020] recently achieved state-of-the-art clustering performance on image datasets using contrastive learning. SCAN takes advantage of the nearest neighbors and proposes that the sample and its nearest neighbors should be assigned to the same cluster, and GCC assumes that the transform of an image and its neighbors' transformer should also be similar further improving clustering performance on image data.

Unlike other DC algorithms which treat nearest neighbors of each sample equally as similar pairs, we take advantage of the local structure (i.e., the distribution of neighbors) of each sample in a dataset with both positiveness (similar) and negativeness (dissimilar/disconnected) with soft contrastive learning. Moreover, the input of our framework is not limit to images, and the good features learned by self-supervised models (e.g., SimCLR, MoCo) can also be utilized to boost the clustering performance further.

3 LNSCC: Locally Normalized Soft Contrastive Clustering

Given a dataset X = {Xi ∈ RD }Ni=1 with N samples in Ddimensional space, the principle of clustering is to separate X into K clusters such that intra-cluster samples stay compact while inter-cluster samples stay far apart. LNSCC aims to obtain compact clusters with a low-dimensional embedding Z by mining the relationships between samples via positiveness and negativeness of each sample pair for clustering.

3.1 Locally Normalized Soft Contrastive Learning

Contrastive learning is a representation learning technique that aims at learning good representations by contracting positive (i.e., similar) pairs and expanding negative (i.e., different) pairs without labels. The key is to discriminate positive sample pairs: SimCLR [Chen et al., 2020] considers positive sample pairs in a latent space, and SCAN [Van Gansbeke et al., 2020] and GCC [Zhong et al., 2021] discover positive sample pairs using a kNN graph. In all those methods, discriminating good positive sample pairs is known as "Hard Contrastive Learning". However, the assumption that a sample and its neighbors belong to the same category may not be true as shown in the misleading k-NN classification on ImageNet [Van Gansbeke et al., 2020], which indicates that the neighbors of each sample should be considered separately.

Unlike the previous contrastive learning which considers positive pairs only, in this paper, we consider both positive and negative sample pairs jointly. We explore both positive and negative relations among the neighbors of each sample and propose a locally normalized soft contrastive learning (LNSCL) approach with two components: Locally Normalized Structure and Soft Contrastive Assignment. The former builds a locally normalized kNN graph via three phases P:

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

• Pim: focusing on samples with a skewed distribution of similarities among its neighbors with high variance (i.e., imbalanced neighbors) near cluster boundaries,
• Pba: focusing on samples with similarities among its neighbors close to uniform distribution (i.e., balanced neighbors) near cluster centers,
• Pdis: focusing on disconnected samples,

and the overview of the framework including the ideas of the three P is shown in Fig. 2. The latter assigns both positiveness and negativeness scores instead of choosing either positive or negative for each sample pair by exploring the structure of locally normalized kNN.

LocallyNormalized Structure. Anaiveweighted kNNoften has large edge weights (i.e., high similarities) among samples in densely populated regions mostly near the center of sample clusters, and small weights among samples near cluster boundaries where samples exist sparsely (e.g., E and F in Fig. 3 respectively). Because of such tendency, a downstream clustering algorithm mostly focuses on the already well compactly grouped samples with large edge weights and ignores the samples sparsely distributed at the boundary of clusters. To fairly separate the samples at the cluster boundary, we introduce a locally normalized kNN graph which normalizes the neighbors' weights at each sample to fully take advantage of neighbor structure of each sample independently.

Consider a distance matrix DN×M computed from X where M is the predefined number of nearest neighbors. The elements in each row Di:, i ∈ [1, 2, ..., N] of D are distance metrics (e.g., Euclidean distance) of the i-th sample to its M different nearest neighbors (we use M instead of k to avoid confusion with the number of clusters K). To normalize the neighbors at each sample, the softmax function is used at each row of D to achieve a normalized weight matrix W.

Based onW, a directed weight matrix ˆWN×N can be derived, and a symmetric adjacency matrix A is defined as

which defines edge weights of a latent graph Glg. The A imputes edges that are one-sided inW and makes the separation of cluster boundaries more effective.

In a latent graph Glg, small edge weights typically exist on the samples with neighbors with large variations in their similarities as they are normalized per sample. At the central region of each cluster, samples stay close to each other and the weights in their sub-graphs have low variation. However, at the cluster boundaries, samples are sparsely distributed and it is highly likely to obtain imbalanced sub-graphs with high average and variations in their distances. Fig. 3 illustrates such behavior, where samples around F are sparse with different similarities (edge thickness) while samples around an interior point E are populated with low variation in their similarities.

Soft Contrastive Assignment. Instead of discriminating positive and negative pairs as in other works, we assign positiveness and negativeness scores for each sample pair to represent the similarity and dissimilarity. We observed that connected samples in a kNN graph do not always belong to the same category, and the difference between positive pairs and negative pairs may not be clear in a naive kNN.

We propose a soft contrastive assignment scheme which derives positiveness score s+ij and negativeness score s-ij to quantify the relationships between samples Xi and Xj .

where ϕP(·) and φP(·) are score functions with a clustering rule that similar samples have large positiveness score while dissimilar samples have with large negativeness score, and P ∈ {Pim, Pba, Pdis} represents different learning phases.

Batch-wise Training with Over/Under Sampling. Operating directly on all edges in a graph for training a model can be computationally challenging since the number of edges dramatically increases along with the number of samples. For efficient training, we take traditional batch-wise training by randomly selecting a batch of sample pairs. As seen in Fig. 2, there are two Networks to be trained using this batch training scheme, where the Neural Network (NN) is a backbone network used to obtain embedding Z of X and FC is used to obtain localized clustering assignment matrix U from Z.

Also, instead of directly defining ϕ and φ, we create overand under-sampled datasets whose elements are augmented sample pairs according to the ideas of ϕ and φ depending on A. Different datasets are curated for each Pim, Pba, Pdis such that the notion of s+ij and s-ij are inherited as the proportion of desirable and undesirable sample pairs for different phases. This is done by designing a quantity augmentation (QA) matrix Q as a function of A (and thereby s+ and s-) that determines how many times each sample pair should be included in the augmented dataset. This way, we indirectly incorporate the notion of the scores.

3.2 Learning Clustering-oriented Latent Space

Let Z be an unknown embedding of samples in a lowdimensional latent space. Given two samples Zi and Zj from Z, their similarity Oij in the embedding space should be antidependent on their distance d(Zi, Zj), and we use an exponential function to define Oij as

Here, two close samples with small d(Zi,Zj) lead to a large Oij which indicates that "attractive force" between those two samples is strong in the latent space, and vice versa for two far samples. This Oij will be used to define loss functions together with an augmented dataset using A.

Pim: Focusing on Samples with Imbalanced Neighbors

The goal of Pim is to attract each sample to its similar neighbors and expand it from the farther neighbors, and the contrastive assignments are given as

Given the observation that the samples with imbalanced neighbors are highly associated with small edge weights which are near cluster boundaries, we use the following QA matrices, Qim+ and Qim-, to encode the above s+ and s-:

where ⌊·⌋ is the floor function, Amax and (1 - A)max are the largest values in A and 1 - A respectively, and α balances the over-sampling ratio for positiveness and negativeness.

The introduction of α lies in two reasons: 1) A is not uniformly distributed in the range [0, 1] and along with the increase of the number of nearest neighbors M, the mean of A is decreasing; 2) each sample pair (Xi,Xj) in Pim is in the top M nearest neighbors of Xi, which means the expansion between (Xi, Xj ) should be much weaker.

The Qim+ lets the edges with large weights become more likely to be selected to compute Lim, while Qim- behaves exactly the opposite. Then, the augmented sample pair datasets, E im+ and E im- are given as

The loss Lim for a batch E im+ bat , i.e., a subset of E im+, and a batch E imbat , i.e., a subset of E im-, is defined as

(9)

Here, logOij attracts sample pairs in E im+, while log(1 - Oij) expands sample pairs in E im-.

Pba: Focusing on Samples with Balanced Neighbors

While Pim focused on separating samples near cluster boundaries, the goal of Pba is to contract those samples and their neighbors to achieve compact clusters. Therefore, the contrastive assignments for Pba are defined as

Assigning positiveness scores s+ij = Aij and extremely low scores to denote negativeness s-ij = 0 for sample pairs let samples within the same cluster contract. To encode them, the QA matrix, Qba , for Pba is given by

where Amean is the mean value in A. This way, Qba assigns more numbers of the sample pairs with relatively large positiveness scores (i.e., above average) to be included in the augmented sample pair dataset E ba as

Then, the loss Lba computed for a batch E ba bat of training data per epoch is computed as

By contracting similar sample pairs only, Lba helps achieve very compact clusters with samples near cluster centers.

Pdis: Focusing on Disconnected Samples

In contrast to optimizing connected samples, to make better clusters, disconnected samples should be dramatically separated in Z. Notice that similarity is not needed here; the model only needs to know if two samples are disconnected (possibly from different clusters) to push them apart. Therefore, based on local similarity fromA, a binary disconnectivity matrix BN×N is computed with a sign function as

Note that each element in B indicates if two samples are disconnected in the kNN graph. To expand the disconnected samples far away, the contrastive assignment is given as

where only the negativeness scores are considered.

The number of disconnected sample pairs (i.e., non-zero elements in B) is often very large, so using the entire disconnected samples can be inefficient. Therefore, we use a subset of disconnections in the graph as the sample pair dataset E dis .

Let B be the set of disconnected sample pairs in B. We create E dis by undersampling the disconnected sample pairs from B according to the following condition

where |·| represents the size of the dataset, and β is the hyperparameter to balance the expansion among disconnected samples and the contraction among connected samples from other P. Intuitively, without a sufficient force to separate dissimilar samples from Pdis, Pim and Pba will contract all samples as close as possible without distinct clusters.

Finally, the loss Ldis for a batch E dis bat is computed as

Unlike Lim and Lba which inherit positiveness and negativeness of sample pairs inside local neighborhood, Ldis provides a global view of exploring the negativeness of disconnected sample pairs to avoid all samples from being merged.

3.3 Cluster Assignment with Self-training

Similar to [Ghasedi Dizaji et al., 2017; Van Gansbeke et al., 2020], the clustering head in our framework is implemented with a FC layer, Θ, followed by the softmax function. Given an embedding Zi ∈ Z, the FC generates its cluster assignment probability Uki for each cluster k = [1, 2, · · · ,K].

To iteratively make cluster assignment probability U localized to a specific cluster, we adopt the self-training process which first calculates a target cluster assignment V from U by applying a specific normalization on U, and then minimize the clustering loss Lclu, i.e., the Kullback-Leibler (KL) divergence between the cluster assignment matrix U and V:

a hyperparameter to regularize the distribution of clusters to avoid all the predictions being assigned to the same cluster. If the prior distribution of clusters is known, the second term can be replaced with a KL-divergence loss. The overall objective function combines Lim, Lba, Ldis and Lclu as

to achieve LNSCC, an end-to-end pipeline to achieve an optimal embedding space and compact clustering of samples. δ is a hyperparameter to balance the clustering and embedding, ni represents the i-th iteration, and ξ is the upper limit of η.

4 Experiments

In this section, we compare LNSCC with various baseline clustering methods. We first evaluate LNSCC on relatively simple (image and non-image) datasets and then test it on complex image datasets that are adopted by SOTA methods.

4.1 Experimental Setup

Datasets. To evaluate performances of different clustering methods, five popular public datasets were used: REUTERS10K [Guo et al., 2017], MNIST, MNIST-test, USPS, and Fashion-MNIST. Each dataset contains several classes with ground truths. The datasets are summarized in TABLE 1.

Baselines. We adopt 20 different shallow to deep clustering methods for comparison shown in TABLE 2. All shallow methods are listed in the top panel, and Deep methods in the middle and bottom panels are categorized by the use of convolutional techniques, which are suited for image data.

Evaluation Metrics. To evaluate the performance of various clustering algorithms, we adopt the two most common evaluation metrics (i.e., Normalized Mutual Information (NMI) and Clustering Accuracy (ACC)) in our experiments. Unlike ACC which is computed by finding the best match between cluster assignment and target labels, NMI captures the similarity between cluster assignment and target labels which is appropriate for evaluating clustering.

Implementation. The input datawere projected onto a lowdimensional space with an MLP (with layers: 500, 500, 2000 nodes) which is widely used in other DC methods, while the clustering head is also implemented using an MLP (with one layer: 32 nodes). The dimension of Z was set to 64. When constructing the locally normalized kNN graph Glg, the number of nearest neighbors was set to 10 and 70 only for REUTERS-10k dataset, and Euclidean distance was used for distance metric. For the MLPs, we used Stochastic Gradient Descent (SGD) as the optimizer with learning rate 0.01, momentum 0.9, and weight decay 0.0005 and the batch size was set to 200. The α in (6) was 2, the β in (16) was 5, the γ in (18) was 1, and the (δ, ξ) were set as (0.05, 5) in (19). Pretrained VGG [Simonyan and Zisserman, 2015] was used to extract image features if convolution was separately needed.

4.2 Results and Discussions

Clustering on Public Datasets. TABLE 2 compares the clustering performances of baseline methods and LNSCC on various datasets. Top-2 algorithms on each dataset are highlighted in bold. TABLE 2 shows that most deep methods perform better than shallow models. Among the deep methods, comparing DEC and ConvDEC clearly tells that the convolution results in an increase in clustering performance for image data. Moreover, comparisons of DDC vs. DDC-DA and ConvDEC vs. ConvDEC-DA show that Data Augmentation (DA) provides an improvement as well.

Without Convolution. Shallow methods mostly did not perform well on these high-dimensional data, and Deep methods yielded reasonable results. On the other hand, LNSCC achieved the best performance in both ACC and NMI on all five datasets across image and non-image data. LNSCC's performances on image data were also comparable with or sometimes even better than the results from the baselines that utilize convolution to extract effective image representations. These results tell that LNSCC is able to learn very effective representation of the data regardless of its modality.

With Image Features. The LNSCC with VGG features achieved at least top-2 ACC and NMI (∼0.98) on MNIST and USPS datasets, and only ConvDEC with DA yielded a slightly better result than LNSCC on the accuracy. For Fashion-MNIST which is more complicated, LNSCC achieved good ACC (0.665) and NMI (0.703) which outperformed all the clustering baselines designed for images. One notable result is that LNSCC without VGG features yielded the highest accuracy on the Fashion-MNIST data. This may be because, while VGG features are effective, their dimensions are too high compared to the original image size.

4.3 Evaluations on Challenging Image Datasets

TABLE 3 compares the performances of other recent image clustering methods with LNSCC on more complex datasets including CIFAR10 [Krizhevsky et al., 2009], CIFAR100-20 [Krizhevsky et al., 2009] and STL10 [Coates et al., 2011]. We provide these results separately as their results on MNIST, USPS, Fashion-MNIST and Reuters-10K have not been reported. The experimental settings follow [Van Gansbeke et al., 2020] for SCAN which trains and evaluates the model using the train and validation splits, respectively.

TABLE 3 shows that SCAN [Van Gansbeke et al., 2020] and our LNSCC outperform other methods with a large gap (> 17%) in accuracy. SCAN uses self-supervised learning (i.e., SimCLR) from [Chen et al., 2020] and a strong data augmentation for self-labeling, i.e., RandAugment (RA) [Cubuk et al., 2020]. For fair comparisons, LNSCC here adopted the same embedding from SimCLR as an input. From the table, we can see SCAN with self-labeling performs much better than the original SCAN. However, our LNSCC can still outperforms SCAN on CIFAR10 and CIFAR100-20 datasets in both ACC and NMI. On STL10 dataset, our LNSCC is still competitive in ACC and achieves the best NMI. Finally, Fig. 4 visualizes the quality of low-dimensional embedding obtained with LNCSS on the CIFAR10 compared to PCA and UMAP, even when only 2D is used for the data embedding.

4.4 Ablation Study andModel Analysis

TABLE 4 shows our ablation study on Lim (separating boundary points), Lba (contracting sample pairs) and Ldis (expanding sample pairs) using MNIST-test data. It shows that the performance of LNSCC drops (i.e., ACC/NMI drop from 0.94/0.89 to 0.78/0.83 after removing Lim and to 0.80/0.82 when Lba and Ldis are ablated. It also shows that the expansion is critical in clustering accuracy emphasizing the importance of separating samples near cluster boundaries. The failure cases, i.e., indistinct clusters, were observed when Lim was removed or both Lba and Ldis were not included.

Fig. 5 shows the training process of LNSCC. It is seen that clusters are gradually separated as the training progresses. At the final epoch, individual clusters are compactly clustered with very few false-positives. The bottom row shows intraand inter-class similarity distributions of the two nearest clusters (i.e., classes) to demonstrate the quality of the clusters. Notice that the intra-class similarities in both clusters (red and blue) become highly localized to small values, and inter-class similarity distribution (purple) gets shifted to larger values. Such a behavior is exactly what we expected with LNSCC.

5 Conclusion

In this paper, we introduced a unified end-to-end clustering framework, i.e., LNSCC, which demonstrate very competitive clustering performance for both image and non-image data. The key idea is to consider both positiveness and negativeness for each pairs of samples in a locally normalized graph to learn an effective low-dimensional embedding of data, and propose a batch-wise training scheme to efficiently perform contrastive learning. The clustering results show very compact clusters, which demonstrate significant potentials to be deployed in various application fields.

Acknowledgments

This research was supported by NSF IIS CRII 1948510, NIH R03 AG070701, IITP-2019-0-01906 (AI Graduate Program at POSTECH) and IITP-2022-2020-0-01461 (ITRC) funded by Ministry of Science and ICT (MSIT), South Korea.