Abstract
Spectral clustering methods which are frequently used in clustering and community detection applications are sensitive to the specific graph constructions particularly when imbalanced clusters are present. We show that ratio cut (RCut) or normalized cut (NCut) objectives are not tailored to imbalanced cluster sizes 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 cluster sizes. Our approach parameterizes a family of graphs by adaptively modulating node degrees on a fixed node set, yielding 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 experiments on synthetic and real datasets for data clustering, semi-supervised learning and community detection.
The Problem of Balance Bias
Standard spectral clustering (SC) is a cornerstone of machine learning, yet it possesses a significant "blind spot": an inherent bias toward producing balanced clusters. SC typically works by transforming data into a graph and finding the "cheapest" way to cut that graph into pieces. To avoid simply cutting off a single outlier (a "singleton"), standard objectives like Ratio Cut (RCut) and Normalized Cut (NCut) include a balancing term.
However, this balancing term is a double-edged sword. When data naturally contains clusters of vastly different sizes, these terms can force the algorithm to split a large cluster in half rather than correctly identifying a small minority community. This mathematical bias makes standard SC unreliable for critical applications like medical diagnosis or community detection in social networks where the minority group is often the primary focus.
Proposed Framework: PCut and RMD Graphs
To overcome this, the authors introduce two key innovations: Partition Constrained Minimum Cut (PCut) and Rank Modulated Degree (RMD) graphs.
PCut (Partition Constrained Minimum Cut)
Instead of relying on a ratio that biases toward balance, the authors propose minimizing the absolute cut value subject to a hard constraint: every partition must contain at least a minimum fraction ($\delta$) of the total nodes. Since direct optimization is NP-hard, PCut serves as a selection criterion over a family of candidate graphs generated with varying parameters.
RMD (Rank Modulated Degree) Graphs
The RMD graph construction is the technical engine of the approach. Unlike standard $k$-nearest neighbor graphs, RMD graphs adaptively modulate node degrees based on local density. Nodes in high-density regions (cluster centers) are assigned more neighbors, while nodes in low-density regions (the "valleys" between clusters) receive fewer. This process effectively "stretches" the gaps between clusters, making the boundaries more apparent to spectral algorithms. For connectivity networks like social graphs, the count of common neighbors is used as a proxy for density.
Experimental Evaluation
The method was tested on synthetic benchmarks (LFR) and real-world datasets including USPS handwritten digits and social networks (Zachary’s Karate Club, Bottlenose Dolphins). Imbalance was introduced by sub-sampling specific classes to test the limits of standard algorithms.
Key Results
- Significant Error Reduction: On the USPS digits dataset (comparing digits 8 and 9), RMD achieved an error rate of 4.8%, compared to 16.67% for standard RBF $k$-NN spectral clustering.
- Community Detection: In the Dolphin network, as nodes were removed to increase imbalance, standard SC error rates climbed significantly, while RMD remained stable, offering up to a 40% reduction in average error.
- Superiority in SSL: In Semi-Supervised Learning (SSL) tasks, RMD consistently outperformed $b$-matching and adaptive RBF methods across all tested datasets.
Conclusion
While the RMD-PCut framework introduces some computational overhead due to the need to generate and evaluate multiple candidate graphs, it provides a robust solution to the long-standing issue of cluster imbalance in spectral methods. By using local density as a lever to modulate graph structure, the approach effectively "pre-processes" the difficulty out of clustering problems, making it a powerful tool for modern data analysis where imbalanced communities are the norm rather than the exception.
Summary updated