Quantum-Assisted Correlation Clustering
This work addresses the problem of scalable and structurally-aware clustering for graph-based unsupervised learning, particularly in domains like hyperspectral imaging, but it is incremental as it adapts an existing quantum method to a new task.
The paper tackles correlation clustering on signed graphs by adapting a quantum-assisted solver (GCS-Q) to maximize intra-cluster agreement through recursive divisive partitioning, demonstrating that it outperforms classical algorithms in robustness and clustering quality on real-world data and imbalanced scenarios.
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.