Publication
Quantum-Assisted Correlation Clustering
Antonio Macaluso; Supreeth Mysore Venkatesh; Diego Arenas; Matthias Klusch; Andreas Dengel
In: 2025 IEEE International Conference on Quantum Artificial Intelligence. IEEE International Conference on Quantum Artificial Intelligence (IEEE QAI-2025), November 2-5, University of Naples Federico II, Via Partenope 36, Naples, Italy, Institute of Electrical and Electronics Engineers (IEEE), 9/2025.
Abstract
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.