# Quantum-Assisted Correlation Clustering

arXiv: https://arxiv.org/abs/2509.03561 · HTML: https://mlsanity.com/paper/2509.03561/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 33 references that are in the map.
- First posted on arXiv 3 Sep 2025.

## Builds on (most cited first, 7 of 7)

- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [Prioritizing network communities](https://mlsanity.com/paper/1805.02411/) (2018)
- [Q-Seg: Quantum Annealing-Based Unsupervised Image Segmentation](https://mlsanity.com/paper/2311.12912/) (2023)
- [GCS-Q: Quantum Graph Coalition Structure Generation](https://mlsanity.com/paper/2212.11372/) (2022)
- [Qubit-efficient Variational Quantum Algorithms for Image Segmentation](https://mlsanity.com/paper/2405.14405/) (2024)
- [Balance and Frustration in Signed Networks](https://mlsanity.com/paper/1712.04628/) (2017)
- [QuACS: Variational Quantum Algorithm for Coalition Structure Generation in Induced Subgraph Games](https://mlsanity.com/paper/2304.07218/) (2023)

## Abstract (arXiv)

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.