Spectral clustering with imbalanced data

Jing Qian, Venkatesh Saligrama

TL;DR

Spectral clustering struggles with imbalanced datasets, often producing suboptimal partitions. This paper introduces a novel "Partition Constrained Min-Cut" (PCut) framework that explicitly incorporates cluster size constraints. By adaptively parameterizing graph construction, PCut can identify low-density cuts even in imbalanced scenarios, outperforming traditional spectral clustering methods.

What Problem Does This Paper Address?

Spectral clustering, a powerful technique for uncovering data structure, relies on constructing a graph that represents data relationships. However, standard spectral clustering methods, particularly those minimizing Ratio-Cut (RCut) or Normalized Cut (NCut) objectives, are sensitive to the graph construction and can fail when clusters are imbalanced (i.e., have vastly different numbers of data points) or proximal (close to each other). This sensitivity arises because RCut/NCut objectives can prioritize balanced partition sizes over finding true low-density boundaries, leading to misclassifications. The paper aims to address this by developing a spectral clustering approach that is robust to imbalanced and proximal clusters.

Methods

The core of the proposed solution is the Partition Constrained Min-Cut (PCut) framework. Instead of directly optimizing RCut/NCut on a fixed graph, PCut seeks to find minimum cut partitions while enforcing a minimum size constraint on each partition. Since directly solving this constrained problem is NP-hard, the authors propose a two-stage approach:

  1. Parameterized Graph Generation: They introduce a novel graph construction method called Rank Modulated Degree (RMD) Graphs. This method adaptively modulates node degrees based on the relative density of data points, effectively creating a family of graphs that can represent varying levels of imbalance. This is achieved by adjusting node degrees based on a ranking of samples, allowing for sparser graphs in low-density regions and denser graphs in high-density regions. This parameterization is crucial for capturing the nuances of imbalanced data.
  2. Parameter Optimization: Spectral clustering (or other graph-based learning algorithms) is applied to each of these parameterized graphs to generate a set of candidate partitions. The PCut objective (Equation 3) is then optimized over these candidate partitions to select the best one. This effectively uses spectral clustering as a black-box subroutine within a larger optimization framework.

Datasets

The paper evaluates its method on both synthetic and real-world datasets:

  • Synthetic Datasets:
    • A multi-cluster complex-shaped dataset (1 large Gaussian, 2 moon-shaped proximal clusters) to demonstrate the ability to detect small clusters and handle complex shapes.
  • Imbalanced Gaussian mixture models to specifically test performance under varying imbalance ratios.
  • Real-world Datasets:
    • USPS digits dataset: Used for both clustering (e.g., 8 vs 9, 1, 8, 3, 9) and semi-supervised learning (SSL) tasks, with varying levels of imbalancedness introduced by sampling.
  • Statlog landsat satellite images dataset
    • Letter recognition dataset
    • Optical recognition of handwritten digits dataset

The paper also introduces a way to evaluate performance against an "Oracle" that has access to ground truth labels and imbalanced proportions, serving as a benchmark.

Key Insights and Ideas

  • Imbalance is the Root Cause: The paper clearly articulates that the poor performance of standard spectral clustering on imbalanced data stems from the RCut/NCut objectives, which can favor balanced cuts over true low-density boundaries.
  • Graph Construction is Key: The authors highlight that the choice of graph construction significantly impacts spectral clustering's performance, especially with imbalanced data. Traditional methods like k-NN, ϵ-graph, and RBF graphs can fail.
  • RMD Graphs for Flexibility: The proposed Rank Modulated Degree (RMD) graph construction is a critical innovation. By adaptively modulating node degrees based on data density rankings, RMD graphs provide a rich parameterization that allows for better control over the cut-ratio (q) and thus better adaptation to imbalanced data.
  • PCut as a Constraint-Aware Objective: Explicitly incorporating minimum cluster size constraints into the min-cut objective is a direct and effective way to combat the issues caused by imbalanced data.
  • Parameter Optimization for Robustness: The framework's ability to optimize over graph parameters (like those in RMD graphs) allows it to automatically adapt to the specific characteristics of the imbalanced data, rather than relying on manual tuning.

Key Results

  • Superior Performance on Imbalanced Data: Across various synthetic and real-world datasets, the proposed PCut framework with RMD graphs consistently outperforms traditional spectral clustering methods (k-NN, b-matching, full-RBF, full-aRBF) in terms of error rates for both unsupervised clustering and semi-supervised learning tasks, especially as the level of imbalancedness increases.
  • Adaptability to Imbalancedness: Figure 6 demonstrates that while traditional methods' performance degrades significantly with increasing imbalancedness, the RMD-based PCut method remains competitive and adapts well.
  • Small Cluster Detection: Figure 7 shows that PCut can effectively detect small clusters that are missed by standard methods, by varying the partition-size threshold.
  • Approximation of Oracle: Table 2 shows that the PCut on RMD graphs, even when agnostic to ground truth labels, closely approximates the performance of an Oracle that is tuned to imbalanced data.

Limitations and Future Work

  • Computational Complexity: While the RMD graph construction is similar to k-NN (O(dn²logn)), the overall PCut framework involves generating and evaluating multiple parameterized graphs. The paper notes that the complexity is O(D(dn²logn + T)), where D is the number of parameterized graphs and T is the time for cut evaluation. This can be computationally intensive.
  • Parameter Search: The optimization step (Eq. 9) involves searching over graph parameters (λ, κ, σ). While the paper suggests that λ is the most critical parameter, the search space can still be large.
  • Future Work: The authors suggest that their framework can be combined with other graph-based partitioning algorithms to further improve performance on imbalanced data. They also mention that their approach is justified by asymptotic limit cut analysis, which provides theoretical backing for its effectiveness. The ability to detect small clusters opens avenues for applications in community detection.

Summary updated

Abstract

Spectral clustering is sensitive to how graphs are constructed from data. In particular, if the data has proximal and imbalanced clusters, spectral clustering can lead to poor performance on well-known graphs such as k-NN, ϵ-neighborhood and full-RBF graphs. We propose a graph partitioning problem that seeks minimum cut partitions under minimum size constraints on clusters to deal with imbalanced data. Our approach parameterizes a family of graphs by adaptively modulating node degrees on a fixed node set, to yield a set of parameter dependent cuts reflecting varying levels of imbalance. The solution to our problem is then obtained by optimizing over these parameters. We present asymptotic limit cut analysis to justify our approach. Experiments on synthetic and real data sets demonstrate the superiority of our method.
BibTeX
@inproceedings{qian2014spectral,
  author = {Jing Qian and Venkatesh Saligrama},
  title = {{Spectral clustering with imbalanced data}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2014},
  url = {https://openreview.net/forum?id=PD_hSweKZPB},
}
Figure