Abstract
Spectral clustering is sensitive to how graphs are constructed from data, particularly when proximal and imbalanced clusters are present. We show that Ratio-Cut (RCut) or normalized cut (NCut) objectives are not tailored to imbalanced data since they tend to emphasize cut sizes over cut values. We propose a graph partitioning problem that seeks minimum cut partitions under minimum size constraints on partitions 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 rigorous limit cut analysis results to justify our approach and demonstrate the superiority of our method through unsupervised and semi-supervised experiments on synthetic and real datasets.
Introduction
Spectral clustering is a staple of the machine learning toolkit, favored for its ability to identify complex, non-linear cluster shapes. However, it faces a significant challenge when clusters are of vastly different sizes (imbalanced) and located close together (proximal). Standard spectral clustering objectives, such as Ratio-Cut (RCut) and Normalized Cut (NCut), often fail in these scenarios because they are mathematically biased toward producing balanced partitions.
The Challenge of Imbalance
The core of spectral clustering involves minimizing an objective function that balances two competing goals: finding a "density valley" (a small cut value) and ensuring that the resulting clusters are not too small. In datasets with extreme imbalance—for example, one cluster with 900 points and another with 10—the balancing term in NCut often makes it "cheaper" to split the large cluster in half rather than isolating the small, distinct sub-population. This bias effectively hides the "needle" of a small cluster within the "haystack" of a larger one.
Proposed Methodology: Partition Constrained Min-Cut
To address this, the authors propose a framework called Partition Constrained Min-Cut (PCut). The goal is to find the minimum cut that satisfies a minimum cluster size constraint. Since this is NP-hard, they implement a three-stage pipeline:
- Rank Modulated Degree (RMD) Graphs: This is the core innovation. Instead of a standard $k$-nearest neighbor graph, they modulate node degrees based on local density. Nodes in low-density "valleys" are assigned fewer neighbors, while nodes in high-density regions receive more.
- Candidate Generation: Standard spectral clustering is run on these RMD graphs across various parameters to generate a family of candidate partitions.
- Model Selection: These candidates are evaluated on a baseline graph to find the one that minimizes the cut value while meeting a minimum size threshold ($\delta$).
Key Insights and Limit Analysis
The authors utilize "limit cut analysis" to prove that while data imbalance is fixed, the "cut-ratio"—the relative cost of the cut—can be controlled through graph construction. By selectively sparsifying the graph in low-density regions, the RMD graph effectively "widens" the valley between clusters. This makes the imbalanced cut mathematically more attractive to standard spectral algorithms.
Experimental Results
The RMD approach was evaluated against standard $k$-NN, $b$-matching, and self-tuning spectral clustering on several benchmarks:
- Synthetic Data: A "2 moons and 1 Gaussian" set where the Gaussian represents a small, proximal cluster.
- USPS Digits: In "8 vs 9" tasks with high imbalance, RMD maintained error rates below 5%, while standard methods saw errors climb to 20-30%.
- UCI Datasets: On datasets like SatImg and OptDigit, RMD consistently outperformed traditional graph construction methods.
The method also showed significant gains in Semi-Supervised Learning (SSL), where the RMD graph structure improved label propagation even with very few labeled examples in imbalanced settings.
Conclusion
By adaptively modulating graph geometry, the RMD framework allows spectral clustering to overcome its inherent bias toward balanced partitions. While it introduces some computational overhead and requires a minimum size parameter, it provides a robust solution for detecting small, proximal clusters that are otherwise invisible to standard spectral methods.
Summary updated