PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912950338453504 |
|---|---|
| author | Chumpitaz-Flores, Pedro Duong, My Mao, Ying Hua, Kaixun |
| author_facet | Chumpitaz-Flores, Pedro Duong, My Mao, Ying Hua, Kaixun |
| contents | Pairwise-constrained clustering incorporates side information through must-link (ML) and cannot-link (CL) relations between samples. While these constraints can improve cluster quality, they complicate optimization at scale and limit quantum and hybrid approaches through the size of the encoded problem. PASS is a scalable framework for pairwise-constrained k-means that concentrates optimization on a small working subset while updating remaining assignments through re-centering. Cannot-link feasibility under subset-restricted updates is formalized as a list-coloring problem on the induced constraint subgraph, yielding a checkable repair certificate with verifiable outcomes. The same subset restriction produces reduced classical subproblems and smaller quantum formulations, enabling a reduction-based hybrid evaluation under a simulation protocol. Infeasible constraint sets are handled explicitly: the pipeline returns a verifiable repair under stated conditions or reports residual conflicts under the same evaluation protocol. Across diverse benchmarks, PASS attains competitive SSE with lower runtime and returns solutions on instances where strong baselines do not finish within a fixed time budget. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_20157 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering Chumpitaz-Flores, Pedro Duong, My Mao, Ying Hua, Kaixun Machine Learning Emerging Technologies Pairwise-constrained clustering incorporates side information through must-link (ML) and cannot-link (CL) relations between samples. While these constraints can improve cluster quality, they complicate optimization at scale and limit quantum and hybrid approaches through the size of the encoded problem. PASS is a scalable framework for pairwise-constrained k-means that concentrates optimization on a small working subset while updating remaining assignments through re-centering. Cannot-link feasibility under subset-restricted updates is formalized as a list-coloring problem on the induced constraint subgraph, yielding a checkable repair certificate with verifiable outcomes. The same subset restriction produces reduced classical subproblems and smaller quantum formulations, enabling a reduction-based hybrid evaluation under a simulation protocol. Infeasible constraint sets are handled explicitly: the pipeline returns a verifiable repair under stated conditions or reports residual conflicts under the same evaluation protocol. Across diverse benchmarks, PASS attains competitive SSE with lower runtime and returns solutions on instances where strong baselines do not finish within a fixed time budget. |
| title | PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering |
| topic | Machine Learning Emerging Technologies |
| url | https://arxiv.org/abs/2601.20157 |