arXiv:2509.03561quant-phcs.AI2025-09

用量子计算提升复杂图数据的聚类质量,尤其适合有负边和不均衡簇的情况。

Quantum-Assisted Correlation Clustering

  • 将量子优化嵌入分层聚类框架,通过递归分割最大化簇内一致性。
  • 在真实高光谱数据上比经典算法更鲁棒,簇大小不均时表现更优。
  • 无需预设簇数或距离度量,适合结构复杂的图数据聚类。

本文提出一种混合量子-经典方法用于相关聚类,这是一种基于图的无监督学习任务,旨在根据节点间的正负关系进行划分。我们改编了原为联盟结构生成设计的量子辅助求解器GCS-Q,通过递归分裂策略最大化签名图中的簇内一致性。该方法将每次二分步骤建模为二次无约束二值优化问题,并利用量子退火求解。这种将量子优化融入层次聚类框架的方式,使模型能够处理任意相关结构的图数据,包括负边,且无需依赖度量假设或预先设定聚类数量。在合成签名图和真实高光谱成像数据上的实证评估表明,相较于经典算法,该方法在真实数据上具有更强鲁棒性与更高聚类质量,在簇大小不平衡场景中优势显著。结果表明,混合量子-经典优化在推进可扩展、结构感知的图基无监督聚类技术方面具有巨大潜力。

原文摘要 · Abstract (English)

This work introduces a hybrid quantum-classical method to correlation clustering, a graph-based unsupervised learning task that seeks to partition the nodes in a graph based on pairwise agreement and disagreement. In particular, we adapt GCS-Q, a quantum-assisted solver originally designed for coalition structure generation, to maximize intra-cluster agreement in signed graphs through recursive divisive partitioning. The proposed method encodes each bipartitioning step as a quadratic unconstrained binary optimization problem, solved via quantum annealing. This integration of quantum optimization within a hierarchical clustering framework enables handling of graphs with arbitrary correlation structures, including negative edges, without relying on metric assumptions or a predefined number of clusters. Empirical evaluations on synthetic signed graphs and real-world hyperspectral imaging data demonstrate that, when adapted for correlation clustering, GCS-Q outperforms classical algorithms in robustness and clustering quality on real-world data and in scenarios with cluster size imbalance. Our results highlight the promise of hybrid quantum-classical optimization for advancing scalable and structurally-aware clustering techniques in graph-based unsupervised learning.

量子计算聚类分析图学习混合优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。