PASS通过小样本优化提升约束聚类效率，支持经典与量子混合计算。
PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering
- 聚焦小样本集优化，其余样本通过重中心化更新
- 修复不可行约束，提供可验证的修复证书
- 适合大规模及量子化约束聚类任务
成对约束聚类通过样本间的必须链接（ML）和不能链接（CL）关系引入辅助信息。尽管这些约束能提升聚类质量，但会加剧大规模优化难度，并限制量子与混合方法的应用，因编码问题规模受限。PASS是一种可扩展的成对约束k均值框架，将优化集中在小规模工作子集上，其余样本通过重中心化更新。在子集受限更新下，无法链接的可行性被形式化为诱导约束子图上的列表着色问题，从而生成可检查的修复证书并保证结果可验证。相同的子集限制使经典子问题更小，量子模型规模也减小，支持基于还原的混合评估（仿真协议）。对于不可行约束集，流程明确返回可验证修复结果或报告残余冲突，且统一使用相同评估协议。在多种基准测试中，PASS实现与强基线相当的平方误差和（SSE），但运行时间更低，在强基线超时的情况下仍能返回解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。