PASS: Ambiguity Guided Subsets for Scalable Classical and Quantum Constrained Clustering
This addresses scalability issues in constrained clustering for applications like quantum computing, though it appears incremental as a hybrid method building on existing techniques.
The paper tackles the scalability challenge in pairwise-constrained clustering by proposing PASS, a framework that selects subsets based on ambiguity to preserve constraint satisfaction, achieving competitive SSE at lower cost across benchmarks.
Pairwise-constrained clustering augments unsupervised partitioning with side information by enforcing must-link (ML) and cannot-link (CL) constraints between specific samples, yielding labelings that respect known affinities and separations. However, ML and CL constraints add an extra layer of complexity to the clustering problem, with current methods struggling in data scalability, especially in niche applications like quantum or quantum-hybrid clustering. We propose PASS, a pairwise-constraints and ambiguity-driven subset selection framework that preserves ML and CL constraints satisfaction while allowing scalable, high-quality clustering solution. PASS collapses ML constraints into pseudo-points and offers two selectors: a constraint-aware margin rule that collects near-boundary points and all detected CL violations, and an information-geometric rule that scores points via a Fisher-Rao distance derived from soft assignment posteriors, then selects the highest-information subset under a simple budget. Across diverse benchmarks, PASS attains competitive SSE at substantially lower cost than exact or penalty-based methods, and remains effective in regimes where prior approaches fail.