Chaining 2-FWL GNNs for Combinatorial Graph Alignment

Resumo Técnico: Encadeamento de GNNs 2-FWL para Alinhamento Combinatório de Grafos

Definição do Problema
O artigo aborda o Problema de Alinhamento de Grafos Combinatórios (GAP), que busca encontrar a correspondência de nós entre dois grafos não rotulados ($G_A$ e $G_B$) que maximize o número de arestas comuns (nce). Formalmente, isso é equivalente a minimizar a norma de Frobenius $\|AP - PB\|_F^2$ sobre o conjunto de matrizes de permutação $P$, ou maximizar a forma quadrática $\langle AP, PB \rangle$. Este problema é uma instância específica do Problema de Atribuição Quadrática (QAP), conhecido por ser NP-difícil.

Os autores focam estritamente no cenário puramente estrutural, onde os grafos não possuem atributos de nós além de sua topologia. Neste regime, as abordagens existentes de Redes Neurais em Grafos (GNNs) têm tido dificuldade em igualar o desempenho de bases clássicas robustas, especificamente o algoritmo Fast Approximate Quadratic (FAQ) [Vogelstein et al., 2015], que resolve uma relaxação contínua do QAP usando otimização Frank-Wolfe.

Metodologia: Encadeamento com Feedback Discreto
A contribuição central é um procedimento de encadeamento que treina sequencialmente uma série de GNNs do tipo Folklore (GNNs 2-FWL) para gerar matrizes de similaridade cada vez mais precisas, que servem como inicializações para o algoritmo FAQ.

1. Loop de Refinamento Iterativo:

   • Passo 1 (Extração de Atributos): Uma GNN inicial ($f$) extrai atributos de nós das matrizes de adjacência e computa uma matriz de similaridade $S^{(0)}$.
   • Passo 2 (Decodificação e Ranking): A matriz de similaridade é decodificada em uma permutação $\pi$ via um resolvedor de atribuição linear (Projeção). Crucialmente, o artigo introduz um passo de ranking não diferenciável: os nós são classificados com base em sua "qualidade de alinhamento" (o número de arestas correspondidas pela permutação atual). Isso injeta feedback combinatório discreto no pipeline.
   • Passo 3 (Aprendizado Reforçado por Ranking): Uma GNN subsequente ($g^{(k)}$) recebe a estrutura do grafo e os rankings dos nós como entrada para computar uma matriz de similaridade aprimorada $S^{(k)}$. Espera-se que esta matriz seja mais informativa do que a anterior porque incorpora o conhecimento de quais nós estão se alinhando bem no momento.

2. Treinamento Sequencial:
   Como o passo de ranking é não diferenciável, as GNNs não podem ser treinadas de ponta a ponta. Em vez disso, elas são treinadas sequencialmente:

   • Treina-se $f$ para minimizar a perda de entropia cruzada contra a permutação real (ground-truth).
   • Fixa-se $f$, computam-se os rankings no conjunto de treinamento e, então, treina-se $g^{(1)}$ para minimizar a perda contra o ground-truth usando os novos rankings.
   • Repete-se para $g^{(2)}, \dots, g^{(L)}$.
     Cada rede aprende a melhorar a qualidade do alinhamento alcançada pela rede anterior na cadeia.

3. Inferência com Looping:
   Na inferência, a rede treinada final $g^{(L)}$ pode ser aplicada iterativamente (looping). Após cada passagem, uma permutação candidata é gerada, e aquela com o maior nce observado é mantida. Este "looping" atua como um refinamento heurístico sem treinamento adicional.

4. Arquitetura (FGNN):
   Os autores utilizam GNNs do tipo Folklore (FGNN), que operam em pares de nós em vez de nós individuais. Esta arquitetura alcança expressividade 2-FWL (2-Folklore Weisfeiler-Leman). Isso é crítico porque as MPNNs padrão são limitadas à expressividade 1-WL e falham em distinguir nós em grafos regulares (onde todos os nós possuem vizinhanças locais idênticas), levando a matrizes de similaridade degeneradas.

Principais Contribuições

• Procedimento de Encadeamento: Um novo paradigma de treinamento que une a otimização combinatória discreta ao aprendizado contínuo de GNNs através do uso de rankings discretos como sinais de feedback.
• Melhores Inicializações para FAQ: O método aprende a fornecer ao FAQ matrizes de similaridade que são inicializações significativamente melhores do que a relaxação convexa padrão ($D_{cx}$), particularmente em instâncias difíceis.
• Análise de Expressividade: O artigo demonstra que a expressividade 2-FWL é necessária para o cenário puramente estrutural, visto que MPNNs baseadas em 1-WL falham em grafos regulares e grafos esparsos com alto nível de ruído.
• Reavaliação de Baselines: Os autores argumentam que as comparações anteriores na literatura frequentemente subestimam o FAQ ao inicializá-lo com uma matriz duplamente estocástica uniforme, em vez da solução da relaxação convexa ($D_{cx}$). Quando devidamente inicializado, o FAQ é um baseline muito mais forte do que o relatado anteriormente.

Resultados
O método foi avaliado em grafos aleatórios correlacionados sintéticos (Erdős–Rényi Esparsos, Erdős–Rényi Densos e Grafos Regulares) e três benchmarks do mundo real (Yeast PPI, Coauthorship, Redes de Estradas).

• Grafos Erdős–Rényi Esparsos: Em um nível de ruído de 0,25, o ChFGNN FAQ encadeado alcançou 85% de acurácia, comparado a 13% para o FAQ inicializado a partir da relaxação convexa e essencialmente 0% para métodos GNN anteriores.
• Grafos Regulares: Este é um regime onde métodos padrão falham completamente. A relaxação convexa produz uma solução degenerada (o baricentro) e as MPNNs produzem embeddings idênticos. O ChFGNN é o único método relatado capaz de recuperar um alinhamento não trivial, alcançando 56% de acurácia no nível de ruído 0,1, enquanto todos os outros métodos falharam.
• Benchmarks do Mundo Real: Nos datasets do mundo real, os ChFGNNs melhoraram o baseline FAQ fortalecido (FAQ inicializado de $D_{cx}$) em aproximadamente 2% em termos de nce em configurações de alto ruído.
• Eficiência: Embora o procedimento de encadeamento exija treinamento baseado em GPU, a etapa de inferência reduz significamente o número de iterações de Frank-Wolfe necessárias pelo FAQ em comparação ao uso direto da relaxação convexa, indicando uma inicialização de maior qualidade.

Significância e Alegações
O artigo afirma que o refinamento iterativo com feedback combinatório discreto é uma direção promissora para problemas combinatórios com uma interpretação natural de ranking. Os autores não alegam que seu método se transfere sem modificações para problemas de otimização combinatória arbitrários.

A principal significância reside em demonstrar que representações aprendidas podem melhorar o estado da arte do solver clássico (FAQ) no cenário puramente estrutural, um domínio onde as GNNs historicamente tiveram desempenho inferior. O trabalho destaca que a falha das GNNs anteriores deveu-se, em parte, à expressividade insuficiente (limitações de 1-WL) e, em parte, à falta de um mecanismo para incorporar feedback estrutural discreto. Ao encadear GNNs 2-FWL, os autores conseguem superar essas barreiras, alcançando resultados de estado da arte em instâncias difíceis de grafos esparsos e regulares.