Spectral Clustering with Unbalanced Data

Jing Qian, Venkatesh SaligramaarXiv 2013 · DOI · arXiv

TL;DR

Standard spectral clustering often fails when data clusters have vastly different sizes because its mathematical objectives (like NCut) are biased toward creating balanced partitions. This paper introduces Rank-Modulated Degree (RMD) graphs, which adaptively adjust node connectivity based on local density to "force" the algorithm to respect natural density valleys rather than cluster sizes.

What Problem Does This Paper Address?

Spectral clustering (SC) and graph-based semi-supervised learning (SSL) are workhorses of machine learning, prized for their ability to find complex, non-linear shapes that simple methods like K-Means miss. However, they have a "fairness" problem: the objective functions they minimize—namely Ratio-Cut (RCut) and Normalized Cut (NCut)—contain a balancing term. This term penalizes the creation of very small clusters.

While this prevents the algorithm from simply cutting off a single outlier, it creates a massive blind spot for unbalanced data. If one cluster is significantly smaller than another (e.g., a small group of rare disease cases vs. a large healthy population), standard SC will often "cut" through the middle of the large cluster to keep the sizes even, completely missing the true boundary. The authors demonstrate that once the "unbalancedness" reaches a certain threshold, spectral methods are mathematically guaranteed to fail.

Methods

The authors propose a novel framework that moves the "intelligence" of the algorithm from the clustering objective into the graph construction phase.

  1. Rank Computation: For every data point, they calculate a "rank" $R(x)$ based on nearest-neighbor distances. A point in a high-density region gets a high rank; a point in a sparse "valley" or outlier region gets a low rank.
  2. Rank-Modulated Degree (RMD): Instead of giving every node the same number of neighbors ($k$), they modulate the degree of each node based on its rank. Nodes in high-density areas are given more connections, while nodes in low-density areas are sparsified.
  3. The $\lambda$ Parameter: They introduce a parameter $\lambda$ that controls the intensity of this modulation. By varying $\lambda$, they generate a "family" of different graphs for the same dataset.
  4. Model Selection: They apply standard SC to this family of graphs. Finally, they use a model selection scheme to pick the partition that yields the smallest "cut" value on a reference graph, provided the clusters meet a minimum size threshold ($\delta$).

By sparsifying the graph specifically at the density valleys, they effectively "lower the price" for the algorithm to make a cut there, even if it results in unbalanced clusters.

Datasets

The researchers evaluated their method on a mix of synthetic and real-world benchmarks:

  • Synthetic: Mixtures of Gaussians with 85/15 split ratios and the "Two Moons" dataset augmented with a small Gaussian cluster to test complex shapes.
  • Real-World (Unbalanced):
    • USPS: Handwritten digits (specifically comparing difficult pairs like 8 vs 9).
  • SatImg: Statlog Landsat satellite images.
  • OptDigit: Optical recognition of handwritten digits.
  • LetterRec: Letter recognition images.
  • The authors created unbalanced versions of these datasets by randomly sub-sampling specific classes to create lopsided ratios.

Key Insights and Ideas

  • The "Aha" Moment on Balancing: The authors prove (Proposition 1) that SC fails whenever the "cut-ratio" (the depth of the density valley) is greater than $4y(1-y)$, where $y$ is the proportion of the smaller cluster. As $y$ gets smaller, the valley must be incredibly deep for standard SC to find it.
  • Density over Size: The RMD approach essentially "tricks" the NCut objective. By reducing the number of edges in density valleys, the "cut value" becomes so small that the algorithm chooses it despite the size penalty.
  • Asymptotic Justification: Through "limit cut analysis," the authors show that as the number of samples goes to infinity, their RMD graph converges to a state where the cut-ratio is explicitly reduced, pulling the algorithm toward the true density valley.

Key Results

The RMD method significantly outperformed standard $k$-NN and RBF graph constructions across the board:

  • Accuracy: On the USPS (8 vs 9) dataset with high imbalance, RMD achieved an error rate of 4.80%, while standard RBF $k$-NN and full-RBF graphs lagged behind at 16.67% and 19.87% respectively.
  • SSL Performance: In semi-supervised tasks (using GTAM), RMD maintained low error rates even as the imbalance ratio increased, whereas traditional methods saw error rates spike as soon as the clusters became lopsided.
  • Small Cluster Detection: The method proved highly effective at identifying "community" structures or small clusters that are usually treated as noise or outliers by other spectral methods.

Limitations and Future Work

  • Computational Overhead: The process involves computing ranks and constructing multiple graphs to find the best $\lambda$. While the authors note the complexity is $O(dn^2 \log n)$ (similar to building a $k$-NN graph), the constant factors are higher.
  • Prior Knowledge: The model selection requires a threshold $\delta$ (the minimum expected cluster size). While the authors show the results are relatively robust to this choice, it still requires some domain knowledge about the "smallest" cluster one might care about.
  • Future Directions: The authors suggest this framework could be extended to community detection in massive social networks, where "small but tight" communities are often obscured by massive, loosely connected ones.

Summary updated

Abstract

Spectral clustering (SC) and graph-based semi-supervised learning (SSL) algorithms are sensitive to how graphs are constructed from data. In particular if the data has proximal and unbalanced clusters these algorithms can lead to poor performance on well-known graphs such as $k$-NN, full-RBF, $ε$-graphs. This is because the objectives such as Ratio-Cut (RCut) or normalized cut (NCut) attempt to tradeoff cut values with cluster sizes, which are not tailored to unbalanced data. We propose a novel graph partitioning framework, which parameterizes a family of graphs by adaptively modulating node degrees in a $k$-NN graph. We then propose a model selection scheme to choose sizable clusters which are separated by smallest cut values. Our framework is able to adapt to varying levels of unbalancedness of data and can be naturally used for small cluster detection. We theoretically justify our ideas through limit cut analysis. Unsupervised and semi-supervised experiments on synthetic and real data sets demonstrate the superiority of our method.
BibTeX
@misc{qian2013spectral,
  author = {Jing Qian and Venkatesh Saligrama},
  title = {{Spectral Clustering with Unbalanced Data}},
  year = {2013},
  eprint = {1302.5134},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1302.5134},
}
Figure