Quantum-Assisted Correlation Clustering

Título: Agrupamento por Correlação Assistido por Quantum (Quantum-Assisted Correlation Clustering)

Autores: Antonio Macaluso, Supreeth Mysore Venkatesh, Diego Arenas, Matthias Klusch, Andreas Dengel.
Afiliação: Centro Alemão de Pesquisa em Inteligência Artificial (DFKI) e Universidade de Kaiserslautern-Landau (RPTU).

1. O Problema

O Agrupamento por Correlação (Correlation Clustering - CC) é uma tarefa de aprendizado não supervisionado baseada em grafos que visa particionar os nós de um grafo com base em acordos (arestas positivas) e desacordos (arestas negativas) entre pares de nós.

• Limitações dos Métodos Clássicos: Abordagens tradicionais (como k-means ou agrupamento hierárquico) geralmente exigem que os dados estejam embutidos em um espaço métrico, assumem formas de clusters esféricas e frequentemente exigem que o número de clusters ($k$) seja pré-definido. Além disso, muitos métodos clássicos têm dificuldade em lidar com arestas negativas (desacordos) ou relações não métricas, e tendem a fazer decisões gananciosas locais que podem levar a soluções subótimas.
• Desafio Específico: O problema é NP-difícil. Encontrar a partição ótima que maximize a concordância intra-cluster (ou minimize a discordância) em grafos com estruturas complexas e desbalanceamento de tamanho de clusters é computacionalmente desafiador para algoritmos clássicos.

2. Metodologia Proposta

Os autores propõem um método híbrido quântico-clássico que adapta o algoritmo GCS-Q (originalmente desenvolvido para Geração de Estrutura de Coalizão em Jogos de Subgrafos Induzidos) para resolver o problema de Agrupamento por Correlação.

• Abordagem Divisiva Hierárquica: O método utiliza uma estratégia "top-down". Começa com um único cluster contendo todos os nós e recursivamente divide o grafo em subgrafos menores e mais coerentes.
• Formulação QUBO: Cada passo de bipartição (divisão de um subconjunto de nós em dois) é codificado como um problema de Otimização Binária Quadrática sem Restrições (QUBO).
  • O objetivo é maximizar a soma dos pesos das arestas dentro dos clusters (acordo).
  • A função objetivo é transformada para ser compatível com solucionadores de Quantum Annealing (Recozimento Quântico).
• Vantagem do GCS-Q: Diferente de métodos divisivos clássicos que usam critérios heurísticos locais (como corte espectral ou entre-camadas), o GCS-Q utiliza o recozimento quântico para avaliar todas as bipartições binárias possíveis simultaneamente em cada passo recursivo. Isso permite encontrar o corte globalmente ótimo para aquele subgrafo, evitando armadilhas de ótimos locais.
• Critério de Parada: O algoritmo para de dividir um cluster quando o corte resultante não aumenta o acordo intra-cluster (ou seja, quando o corte é $\le 0$), eliminando a necessidade de especificar o número de clusters ($k$) antecipadamente.

3. Contribuições Principais

1. Adaptação do GCS-Q: Primeira aplicação do solucionador GCS-Q, projetado para teoria dos jogos, ao problema de agrupamento por correlação em grafos ponderados com arestas positivas e negativas.
2. Independência de Métricas: O método não assume métricas geométricas ou proximidade espacial, sendo capaz de lidar com relações de correlação puras, incluindo desacordos negativos.
3. Robustez ao Desbalanceamento: O algoritmo demonstra alta eficácia em cenários onde os clusters têm tamanhos altamente desiguais (medido pelo Índice de Gini), uma situação onde métodos clássicos como Spectral Clustering frequentemente falham.
4. Validação Híbrida: Demonstra a viabilidade prática de usar dispositivos de recozimento quântico ruidosos (como o D-Wave Advantage) para tarefas de aprendizado não supervisionado em larga escala através de uma abordagem híbrida.

4. Resultados Experimentais

Os autores avaliaram o método em dois tipos de dados:

• Grafos Sintéticos Assinados:

  • Gerados com diferentes distribuições de tamanho de cluster (uniforme, moderadamente desbalanceado e altamente desbalanceado).
  • Métrica: Informação Mútua Normalizada (NMI) em relação ao ground truth.
  • Desempenho: O GCS-Q superou consistentemente métodos clássicos (k-means, PAM, Hierárquico Aglomerativo, DIANA e Spectral Clustering), especialmente em cenários de desbalanceamento extremo. Enquanto o Spectral Clustering degradou-se significativamente com o aumento do desbalanceamento, o GCS-Q manteve alta precisão.
  • O GCS-Q não precisou do valor de $k$ fornecido, ao contrário dos métodos clássicos que foram "ajudados" com o $k$ correto para garantir uma comparação justa.

• Dados Reais (Imagens Hiperespectrais):

  • Aplicado em quatro conjuntos de dados de sensoriamento remoto (Indian Pines, Salinas, Pavia University, Kennedy Space Center) para agrupar bandas espectrais redundantes.
  • Métrica: Modularidade (qualidade da estrutura do grafo).
  • Desempenho: O GCS-Q obteve consistentemente os maiores valores de modularidade, indicando uma melhor separação de bandas correlacionadas e uma estrutura de cluster mais coerente do que os métodos clássicos. O desempenho foi particularmente superior em dados com alta complexidade espectral.

5. Significado e Conclusão

O trabalho destaca o potencial da otimização híbrida quântico-clássica para avançar técnicas de agrupamento em grafos.

• Escalabilidade e Estrutura: A abordagem permite lidar com estruturas de correlação arbitrárias sem depender de premissas métricas rígidas.
• Viabilidade Prática: Os resultados provam que, mesmo com hardware quântico atual (ruidoso e com limitações de qubits), a integração em frameworks hierárquicos pode superar algoritmos clássicos estabelecidos em tarefas específicas e desafiadoras.
• Futuro: Os autores sugerem a expansão para grafos esparsos de grande escala e a exploração de solucionadores quânticos baseados em portas (gate-based) para tarefas de aprendizado não supervisionado.

Em resumo, o artigo apresenta uma solução robusta e de alta qualidade para o agrupamento por correlação, superando as limitações de métodos clássicos em cenários de dados complexos e desbalanceados através do uso inteligente de otimização quântica.