AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network

Resumo Técnico: AGDN – Aprendendo a Resolver o Problema do Caixeiro Viajante com uma Rede de Difusão de Grafos Anisotrópica

Definição do Problema
O Problema do Caixeiro Viajante (TSP) é um problema fundamental de otimização combinatória onde o objetivo é encontrar a rota mais curta que visite um conjunto de cidades exatamente uma vez e retorne à origem. Embora as Redes Neurais de Grafos (GNNs) tenham emergido como ferramentas eficazes para o TSP devido ao seu alinhamento com o espaço de busca topológico do problema, as abordagens atuais baseadas em aprendizado enfrentam duas limitações críticas:

1. Falta de Prior Topológico Informativo: Ao contrário das tarefas padrão de aprendizado em grafos, as instâncias de TSP são tipicamente modeladas como grafos totalmente conectados. Essa estrutura carece de priors topológicos inerentes em relação à solução ótima, tornando difícil para os modelos distinguirem informações relevantes para a solução do ruído.
2. Perda de Intercâmbio de Informação via Esparsificação: Para gerenciar a complexidade computacional, os métodos existentes frequentemente esparsificam o grafo do TSP (por exemplo, usando $k$-NN). No entanto, esse processo corre o risco de remover arestas que fazem parte da solução ótima. Quando pares de nós ótimos são desconectados, as GNNs rasas têm dificuldade em capturar as relações multi-salto necessárias, enquanto as GNNs mais profundas sofrem de over-smoothing (suavização excessiva) e over-squashing (esmagamento excessivo).

Metodologia: Rede de Difusão de Grafos Anisotrópica (AGDN)
Os autores propõem a AGDN, um framework projetado para resolver o TSP sem depender da esparsificação de grafos. A metodologia consiste em quatro componentes principais:

1. Matriz de Transição MixScore:
   Em vez de usar uma matriz de adjacência padrão ou uma simples transição baseada em distância, a AGDN constrói uma matriz de transição MixScore. Esta matriz integra dois tipos de informação:

   • Distância Pareada: Codificada via um kernel Gaussiano ($\exp(-e_{ij}/\sigma)$) para capturar a proximidade geométrica.
   • Similaridade de Nós: Derivada de embeddings de nós em dois espaços latentes distintos: um espaço de Origem ($S$) e um de Destino ($D$).
     A matriz é formulada concatenando os produtos internos de embeddings desses espaços ($H_S H_D^T$) com a matriz de distância normalizada ($T_{rw}$), processados através de um Perceptron de Camada Multicamadas (MLP). Isso permite que o modelo codifique probabilidades de transição que refletem tanto a distância geométrica quanto a similaridade estrutural aprendida.

2. Difusão de Grafo Anisotrópica:
   A AGDN emprega um mecanismo de difusão que propaga a informação tanto nas direções de entrada ($S$) quanto de saída ($D$) separadamente.

   • Atenção Multi-salto: O framework utiliza um mecanismo de atenção multi-salto aprendível (parametrizado por $\theta_k$) para agregar informações de $K$ saltos dentro de uma única camada de convolução. Isso evita a necessidade de empilhar múltiplas camadas, mitigando assim o over-smoothing.
   • Anisotropia: Ao manter espaços $S$ e $D$ separados, o modelo captura o fluxo de informação direcional, aumentando a granularidade da caracterização dos nós.

3. Agregação de Informação de Nó:
   Após a difusão, os embeddings dos espaços $S$ e $D$ são agregados. Os autores utilizam um mecanismo de auto-atenção onde os embeddings do espaço $S$ atuam como queries e os do espaço $D$ atuam como keys e values. Esta agregação assimétrica é seguida por um MLP final para produzir os embeddings de nó unificados.

4. Identificação da Solução:
   Os embeddings de nó agregados são usados para gerar embeddings de aresta via produtos externos. Um mecanismo de atenção ao nível de aresta repondera esses embeddings para destacar arestas críticas. Finalmente, um MLP prevê um mapa de calor representando a probabilidade de cada aresta fazer parte do tour ótimo. Este mapa de calor guia uma Busca em Árvore de Monte Carlo (MCTS) para construir a solução final. O modelo é otimizado usando aprendizado supervisionado (entropia cruzada contra mapas de calor reais) ou aprendizado não supervisionado (minimizando o comprimento esperado do tour).

Principais Contribuições

• Caracterização do Problema: O artigo identifica e formaliza as limitações das abordagens atuais de GNN, especificamente a desconexão causada pela esparsificação de grafos e a falta de priors informativos em grafos de TSP totalmente conectados.
• Design Algorítmico: A introdução da matriz de transição MixScore e do mecanismo de Difusão de Grafo Anisotrópica. Essas inovações permitem a propagação eficiente de informação multi-salto sem esparsificação, preservando a conectividade entre pares de nós ótimos.
• Validação Empírica: Experimentos extensos demonstram que a AGDN supera os métodos de estado da arte tanto em configurações supervisionadas quanto não supervisionadas em vários tamanhos de problema e distribuições de nós.

Resultados Experimentais
Os autores avaliaram a AGDN em instâncias de TSP variando de 200 a 1000 nós, bem como em conjuntos de dados do mundo real do TSPLIB.

• Eficácia: Em configurações de aprendizado supervisionado (SL), a AGDN alcançou o menor gap em relação à solução ótima comparado aos baselines como GatedGCN, Att-GCN e DIFUSCO. Por exemplo, no TSP-1000, a AGDN alcançou um gap de 1,28% comparado a 7,26% da GatedGCN. No aprendizado não supervisionado (UL), a AGDN também superou o UTSP e o Position.
• Eficiência: A AGDN demonstrou eficiência computacional superior. Ela exigiu menos parâmetros e menos tempo de inferência do que a GatedGCN, particularmente conforme o número de saltos para agregação de informação aumentava. Isso é atribuído à capacidade de capturar informação multi-salto em uma única camada.
• Generalização: O modelo mostrou uma generalização robusta quando treinado no TSP-100 e testado em instâncias maiores (TSP-200, 500, 1000) e diversas distribuições de nós (Uniform, Cluster, Explosion, Implosion). Também manteve alto desempenho em instâncias reais do TSPLIB (tsp225, pcb442, pr1002) sem necessidade de retreinamento.

Significância
O artigo afirma que a AGDN aborda o trade-off fundamental entre a esparsificação de grafos e a perda de informação na resolução de TSP. Ao introduzir uma estratégia de difusão anisotrópica e um prior MixScore, o framework permite que as GNNs utilizem efetivamente a conectividade total dos grafos de TSP. Os resultados sugerem que a AGDN fornece uma solução escalável e generalizável que preenche a lacuna entre as capacidades teóricas de aprendizado em grafos e as demandas práticas da otimização combinatória, alcançando o estado da arte enquanto mantém tempos de inferência competitivos.