Locally Normalized Soft Contrastive Clustering for Compact Clusters

Xin Ma, Won Hwa KimIJCAI 2022 · OpenReview

TL;DR

This paper introduces Locally Normalized Soft Contrastive Clustering (LNSCC), a novel deep clustering method that excels at separating clusters with clear boundaries, even in noisy, large-scale datasets. LNSCC achieves this by considering both positive and negative sample relationships within a locally normalized graph, leading to state-of-the-art performance across various image and non-image datasets.

What Problem Does This Paper Address?

Traditional clustering methods struggle with the scale and noise of modern datasets. While deep clustering (DC) techniques have emerged to address this by learning low-dimensional embeddings and using self-training, they often falter when clusters have unclear boundaries. Existing DC methods tend to focus on pulling similar samples together and may overlook samples near cluster edges. This can lead to suboptimal cluster assignments, especially in datasets with complex structures or high dimensionality. The paper aims to improve cluster separation, particularly at these boundaries, and create more compact, distinct clusters.

Methods

The core innovation is the Locally Normalized Soft Contrastive Clustering (LNSCC) framework, which operates in an end-to-end manner. It combines dimension reduction, self-training, and clustering. Key components include:

  • Locally Normalized kNN Graph: Instead of relying on standard kNN graphs where edge weights can be skewed by dense regions, LNSCC normalizes neighbor weights per sample. This ensures that samples with sparse or imbalanced neighborhoods (often found at cluster boundaries) are given appropriate consideration. This is achieved through three phases:
  • P_im: Focuses on samples with imbalanced neighbor distributions (high variance in similarities), crucial for separating boundary points.
  • P_ba: Focuses on samples with balanced neighbor distributions (uniform similarities), aiming to contract samples near cluster centers.
  • P_dis: Focuses on globally disconnected samples, pushing them far apart.
  • Soft Contrastive Assignment: Unlike previous methods that strictly define positive or negative pairs, LNSCC assigns scores for both positiveness and negativeness between sample pairs. This allows for a more nuanced representation of relationships.
  • Batch-wise Training with Over/Under Sampling: To handle the computational complexity of large graphs, LNSCC employs a batch-wise training strategy. A "quantity augmentation" (QA) matrix is designed to determine how many times each sample pair should be included in augmented datasets for each phase (P_im, P_ba, P_dis), indirectly incorporating the soft contrastive scores.
  • Clustering-oriented Latent Space: The method learns a latent space Z where distances between samples are used to define an "attractive force" (O_ij). This force is then used in conjunction with the augmented datasets to define loss functions (L_im, L_ba, L_dis).
  • Self-training: A standard FC layer is used for cluster assignment, and a self-training process iteratively refines these assignments by minimizing a KL divergence loss between the predicted assignments and a target assignment.

Datasets

The paper evaluates LNSCC on several public datasets:

  • Image Datasets: MNIST, MNIST-test, USPS, Fashion-MNIST.
  • Non-image Dataset: REUTERS-10K.
  • Challenging Image Datasets: CIFAR10, CIFAR100-20, STL10.

These datasets cover a range of complexities and modalities, allowing for a comprehensive evaluation of the proposed method.

Key Insights and Ideas

  • The Importance of Boundaries: The paper strongly emphasizes that effectively separating samples near cluster boundaries is critical for achieving good clustering performance, especially in complex datasets. Overlooking these points can lead to merged clusters.
  • Softness is Key: Moving beyond hard positive/negative distinctions in contrastive learning to soft scores for both allows LNSCC to better capture nuanced relationships between samples, particularly in imbalanced neighborhoods.
  • Local Normalization Matters: Normalizing neighbor weights per sample is a crucial step. It prevents dense regions from dominating the graph structure and ensures that sparse or imbalanced neighborhoods (often indicative of boundaries) are properly accounted for.
  • Unified Framework: Integrating dimension reduction, contrastive learning (with both positive and negative pairs), and self-training into a single end-to-end pipeline is a significant advantage, allowing for joint optimization.
  • Modality Agnostic: The method demonstrates strong performance on both image and non-image data, suggesting its generalizability beyond specific data types.

Key Results

LNSCC consistently achieved state-of-the-art or highly competitive results across all tested datasets.

  • Public Datasets (Table 2): LNSCC achieved the best performance (ACC and NMI) on all five public datasets (MNIST, MNIST-test, USPS, Fashion-MNIST, REUTERS-10K) without using convolution. Its performance with VGG features was also comparable to or better than other methods. Notably, LNSCC without convolution outperformed convolution-based baselines on Fashion-MNIST.
  • Challenging Image Datasets (Table 3): On CIFAR10, CIFAR100-20, and STL10, LNSCC achieved competitive results, often outperforming other recent methods by a significant margin (e.g., >17% in accuracy compared to SCAN).
  • Ablation Study (Table 4): Removing L_im (boundary separation) led to a significant drop in performance, highlighting its importance. Removing L_ba or L_dis also degraded performance, underscoring the necessity of all three loss components for optimal results.
  • Visualization (Figure 4 & 5): Visualizations show that LNSCC produces well-separated and compact clusters in the learned latent space, and the training process demonstrates a gradual refinement of these clusters.

Limitations and Future Work

  • Hyperparameter Sensitivity: While not explicitly detailed as a limitation, the presence of multiple hyperparameters (α, β, γ, δ, ξ) suggests that tuning might be required for optimal performance on new datasets.
  • Computational Cost: Although batch-wise training is employed, deep clustering methods can still be computationally intensive. The paper mentions that operating directly on all edges is challenging, implying that efficiency for extremely large datasets might still be an area for improvement.
  • Future Work: The paper suggests that the learned representations from LNSCC could be beneficial for other downstream tasks. The generalizability of the framework to other data modalities and complex real-world scenarios could be further explored. The authors also mention that if prior cluster distributions are known, the KL-divergence term in L_clu could be replaced, suggesting potential for incorporating prior knowledge.

Summary updated

Abstract

Recent deep clustering algorithms take advantage of self-supervised learning and self-training techniques to map the original data into a latent space, where the data embedding and clustering assignment can be jointly optimized. However, as many recent datasets are enormous and noisy, getting a clear boundary between different clusters is challenging with existing methods that mainly focus on contracting similar samples together and overlooking samples near boundary of clusters in the latent space. In this regard, we propose an end-to-end deep clustering algorithm, i.e., Locally Normalized Soft Contrastive Clustering (LNSCC). It takes advantage of similarities among each sample's local neighborhood and globally disconnected samples to leverage positiveness and negativeness of sample pairs in a contrastive way to separate different clusters. Experimental results on various datasets illustrate that our proposed approach achieves outstanding clustering performance over most of the state-of-the-art clustering methods for both image and non-image data even without convolution.
BibTeX
@inproceedings{ma2022locally,
  author = {Xin Ma and Won Hwa Kim},
  title = {{Locally Normalized Soft Contrastive Clustering for Compact Clusters}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=m88hMP0cor},
}
Figure