Quantum-Assisted Correlation Clustering

1. Problem Definition

The paper addresses Correlation Clustering (CC), an unsupervised learning task that partitions the nodes of a graph based on pairwise agreements (positive edge weights) and disagreements (negative edge weights).

• Challenges: Unlike traditional clustering methods (e.g., k-means, spectral clustering) that rely on metric spaces, geometric proximity, or predefined cluster counts ($k$), CC must handle signed graphs where edges represent affinities or conflicts.
• Limitations of Classical Methods: Existing classical approaches often rely on heuristics, assume spherical clusters or connectivity, and require the number of clusters to be specified in advance. They frequently struggle with:
  • Cluster size imbalance: Performance degrades significantly when clusters vary greatly in size.
  • Negative correlations: Difficulty in handling graphs with negative edge weights without metric assumptions.
  • Global optimality: Greedy strategies often lead to suboptimal partitions.

2. Methodology

The authors propose a hybrid quantum-classical method that adapts the GCS-Q algorithm (originally designed for Coalition Structure Generation in Induced Subgraph Games) for correlation clustering.

• Core Approach: The method employs a recursive divisive hierarchical strategy. It starts with a single cluster containing all nodes and recursively splits them into smaller, more coherent sub-clusters.
• Optimization Formulation:
  • Each bipartitioning step is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem.
  • The objective is to maximize intra-cluster agreement (sum of positive edge weights within clusters + sum of negative edge weights between clusters).
  • Mathematically, for a graph $G=(V, E, w)$, the goal is to maximize $\sum_{i,j \in S} w_{ij} \cdot I[x_i = x_j]$, where $x_i \in \{0, 1\}$ represents the cluster assignment.
  • This is transformed into a QUBO form compatible with quantum annealers by expanding the indicator function: $I[x_i = x_j] = 1 - (x_i + x_j - 2x_ix_j)$.
• Quantum Integration: The QUBO problems are solved using Quantum Annealing (specifically on D-Wave Advantage hardware). This allows the algorithm to evaluate all possible binary bipartitions simultaneously, avoiding the local optima traps common in classical greedy heuristics.
• Stopping Criterion: The recursion stops when a split no longer increases intra-cluster agreement (i.e., the cut weight is $\le 0$) or results in an empty set, eliminating the need to predefine $k$.

3. Key Contributions

1. Algorithm Adaptation: Successfully repurposed the GCS-Q solver from game-theoretic coalition generation to graph-based correlation clustering, reinterpreting "coalition value" as "intra-cluster agreement."
2. Hybrid Framework: Demonstrated a scalable workflow where quantum annealing handles the combinatorial optimization of graph partitioning within a classical hierarchical framework.
3. Handling Signed Graphs: The method natively supports negative edge weights and non-metric relationships without requiring distance embeddings.
4. Robustness to Imbalance: The approach specifically targets and overcomes the sensitivity of classical algorithms to skewed cluster size distributions (quantified by the Gini index).

4. Experimental Results

The authors evaluated GCS-Q against classical baselines (k-means, PAM, Spectral Clustering, Hierarchical Clustering including DIANA) on two types of datasets:

A. Synthetic Signed Graphs:

• Setup: Graphs with 170 nodes and varying cluster size distributions (Uniform, Moderately Skewed, Highly Skewed) measured by the Gini index.
• Metric: Normalized Mutual Information (NMI) against ground truth.
• Findings:
  • GCS-Q maintained high NMI scores across all distribution types.
  • In highly skewed scenarios (where one cluster is massive and others are small), GCS-Q significantly outperformed Spectral Clustering and k-means.
  • GCS-Q was competitive with DIANA in extreme skew but outperformed it in other scenarios due to its global optimization capability versus DIANA's greedy single-point exclusion.
  • Crucially, GCS-Q achieved this without being provided the ground-truth number of clusters ($k$).

B. Real-World Hyperspectral Imaging Data:

• Setup: Four datasets (Indian Pines, Salinas, Pavia University, KSC) used to identify redundant spectral bands via correlation.
• Metric: Modularity (measuring the density of edges within clusters vs. between clusters).
• Findings:
  • GCS-Q consistently achieved the highest modularity scores across all datasets.
  • It demonstrated superior ability to group highly correlated spectral bands and separate them from uncorrelated ones, particularly in complex datasets like KSC and Salinas.
  • Classical methods (PAM, k-means, Agglomerative) yielded lower modularity, indicating less effective partitioning of the correlation structure.

5. Significance and Conclusion

• Scalability & Structure: The study proves that hybrid quantum-classical optimization can advance unsupervised learning by handling complex, non-metric graph structures that are difficult for classical heuristics.
• No Predefined $k$: The method offers a significant practical advantage by automatically determining the optimal number of clusters based on agreement maximization, removing a major bottleneck in exploratory data analysis.
• Noise Resilience: Despite using noisy intermediate-scale quantum (NISQ) devices (D-Wave Advantage), the method produced robust results, suggesting that quantum annealing is viable for real-world graph partitioning tasks.
• Future Directions: The authors suggest expanding this approach to larger, sparse graphs and exploring gate-based quantum solvers for further optimization.

In summary, the paper establishes that GCS-Q is a superior alternative to classical correlation clustering algorithms, particularly in scenarios involving signed graphs, negative correlations, and highly imbalanced cluster sizes, leveraging quantum annealing to achieve globally optimal partitions.