{"ID":2875003,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.03561","arxiv_id":"2509.03561","title":"Quantum-Assisted Correlation Clustering","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.","short_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 gener...","url_abs":"https://arxiv.org/abs/2509.03561","url_pdf":"https://arxiv.org/pdf/2509.03561v1","authors":"[\"Antonio Macaluso\",\"Supreeth Mysore Venkatesh\",\"Diego Arenas\",\"Matthias Klusch\",\"Andreas Dengel\"]","published":"2025-09-03T12:14:35Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.AI\",\"cs.LG\"]","methods":"[]","has_code":false}