A Scalable Global Optimization Algorithm For Constrained Clustering
This work addresses the scalability bottleneck in constrained clustering for domains requiring global optimality, offering a significant improvement over existing methods.
The paper tackles the NP-hard problem of constrained clustering with pairwise constraints by proposing SDC-GBB, a scalable branch-and-bound algorithm that handles datasets up to 200,000 samples with cannot-link and 1,500,000 with must-link constraints, achieving an optimality gap of less than 3% and scaling 200-1500 times larger than prior methods.
Constrained clustering leverages limited domain knowledge to improve clustering performance and interpretability, but incorporating pairwise must-link and cannot-link constraints is an NP-hard challenge, making global optimization intractable. Existing mixed-integer optimization methods are confined to small-scale datasets, limiting their utility. We propose Sample-Driven Constrained Group-Based Branch-and-Bound (SDC-GBB), a decomposable branch-and-bound (BB) framework that collapses must-linked samples into centroid-based pseudo-samples and prunes cannot-link through geometric rules, while preserving convergence and guaranteeing global optimality. By integrating grouped-sample Lagrangian decomposition and geometric elimination rules for efficient lower and upper bounds, the algorithm attains highly scalable pairwise k-Means constrained clustering via parallelism. Experimental results show that our approach handles datasets with 200,000 samples with cannot-link constraints and 1,500,000 samples with must-link constraints, which is 200 - 1500 times larger than the current state-of-the-art under comparable constraint settings, while reaching an optimality gap of less than 3%. In providing deterministic global guarantees, our method also avoids the search failures that off-the-shelf heuristics often encounter on large datasets.