Resumo Técnico: Alinhamento de Grafos para Avaliação de Redes Neurais de Grafos e Aprendizado de Codificações Posicionais

Declaração do Problema

As Redes Neurais de Grafos (GNNs) são amplamente utilizadas em diversos domínios, como química, ciência dos materiais e redes sociais. No entanto, avaliar sua compreensão estrutural continua sendo um desafio. Os benchmarks existentes frequentemente confundem capacidades estruturais com aprendizado de características ou dependem de tarefas de otimização combinatória (ex: SAT, TSP) que estão ligadas a topologias de problemas específicos ou modelos sintéticos como o Modelo de Bloco Estocástico (SBM), o que limita sua generalização. Além disso, os métodos atuais têm dificuldade em fornecer uma métrica detalhada para comparar modelos dentro da mesma classe de expressividade (ex: a classe 1-Weisfeiler-Lehman) ou para quantificar a expressividade estrutural através de diversas topologias de grafos encontradas em aplicações do mundo real.

Os autores propõem abordar essa lacuna introduzindo uma metodologia de benchmarking baseada no Problema de Alinhamento de Grafos (também conhecido como Correspondência de Grafos). Esta tarefa envolve alinhar dois grafos não rotulados para maximizar o número de arestas sobrepostas, um problema de otimização combinatória que generaliza o isomorfismo de grafos.

Metodologia

1. A Tarefa de Alinhamento de Grafos

A tarefa central é definida como encontrar uma permutação $\pi^*$ entre dois grafos $G$ e $\tilde{G}$ com $N$ vértices que maximize a sobreposição de suas matrizes de adjacência:
$$\pi^* \in \arg \max_{\pi \in S_N} \sum_{i,j} A_{i,j} \tilde{A}_{\pi(i),\pi(j)}$$
Isso é formulado como uma tarefa de aprendizado autossupervisionado. Os autores utilizam uma arquitetura Siamesa onde uma GNN processa ambos os grafos para produzir embeddings de nós $X$ e $\tilde{X}$. Uma matriz de similaridade $\Sigma = X\tilde{X}^T$ é computada.

• Treinamento: O modelo minimiza a perda de entropia cruzada binária entre a matriz de similaridade prevista e o alinhamento real (permutação plantada).
• Avaliação: O algoritmo de Hungaria resolve o Problema de Atribuição Linear em $\Sigma$ para extrair a permutação prevista. O desempenho é medido pela porcentagem de nós corretamente mapeados.

2. Construção do Conjunto de Dados

Para superar as limitações de conjuntos de dados sintéticos anteriores (ex: grafos de Erdős-Rényi), os autores propõem um método para gerar conjuntos de dados de Alinhamento de Grafos a partir de qualquer conjunto de dados de grafos existente (datasets base).

• Geração de Grafo Correlacionado: Para um grafo base $G$, um grafo correlacionado $\tilde{G}$ é gerado adicionando e removendo arestas aleatoriamente com base em um nível de ruído $\eta$.
• Solução Plantada: Como o alinhamento ideal é conhecido (a identidade ou uma permutação conhecida antes do ruído), o ground truth está disponível sem a necessidade de resolver o problema NP-difícil.
• Escalabilidade: Para grafos grandes (ex: OGBN-Arxiv), um algoritmo de amostragem por Busca em Largura (BFS) é usado para extrair subgrafos menores que preservam a topologia local, tornando-os compatíveis com Redes Neurais de Passagem de Mensagem (MPNNs).
• Controle de Dificuldade: Ao variar o nível de ruído $\eta$ (de 4% a 30%), os autores criam uma família de conjuntos de dados com dificuldade controlável, permitindo uma avaliação matizada.

3. Aprendizado de Codificação Posicional (GAPE)

Os autores utilizam os embeddings de nós aprendidos através da tarefa de Alinhamento de Grafos como Codificações Posicionais de Alinhamento de Grafos (GAPE). Estes embeddings pretendem servir como entradas estruturais para arquiteturas Transformer, que carecem de acesso inerente à estrutura do grafo.

Principais Contribuições

1. Nova Tarefa de Benchmarking: Introdução do Problema de Alinhamento de Grafos como um benchmark para GNNs, que generaliza o teste de Weisfeiler-Lehman e permite a avaliação através de diversas topologias (moleculares, sociais, aleatórias) sem modificar as estruturas de grafos subjacentes.
2. Framework de Geração de Conjuntos de Dados: Uma metodologia abrangente para gerar conjuntos de dados de Alinhamento de Grafos a partir de datasets base tanto sintéticos quanto do mundo real, permitindo a criação de conjuntos de dados com níveis de dificuldade variados.
3. Ranking Empírico de Arquiteturas: Um benchmark sistemático de MPNNs amplamente utilizadas (GCN, GIN, GatedGCN, GAT, GATv2) demonstrando que modelos anisotrópicos superam consistentemente modelos isotrópicos (como GCN e GIN) na análise estrutural, mesmo em grafos homofílicos.
4. Nível de Dificuldade Ótimo: Descoberta de que existe um "nível de ruído ideal" onde a diferença de desempenho entre os modelos é maximizada, fornecendo rankings estatisticamente significativos que são robustos a escolhas de hiperparâmetros e sementes aleatórias.
5. Codificações Posicionais (GAPE): Demonstração de que os embeddings aprendidos via Alinhamento de Grafos servem como codificações posicionais eficazes para Transformers, superando ou igualando codificações espectrais e baseadas em passeios aleatórios (random-walk) em tarefas de regressão molecular.
6. Reconstrução de Grafos: Evidência de que os embeddings GAPE comprimem a estrutura do grafo de forma eficaz, permitindo a reconstrução da matriz de adjacência completa com ~98% de precisão usando um decodificador simples.
7. Ferramental Open-Source: Disponibilização de um pacote Python para gerar esses conjuntos de dados e realizar o benchmark de novas arquiteturas.

Resultados

• Desempenho do Modelo: Em experimentos através de cinco datasets base (Erdős-Rényi, AQSOL, PCQM4Mv2, CoraFull, OGBN-Arxiv), arquiteturas anisotrópicas (GatedGCN, GAT, GATv2) alcançaram maior precisão de alinhamento do que as isotrópicas (GCN, GIN).
• Sensibilidade ao Ruído: A diferença de desempenho entre os modelos foi negligenciável em níveis de ruído muito baixos ou muito altos. A lacuna atingiu o pico em um nível de ruído ideal (ex: $\eta \approx 15\%$ para grafos moleculares), onde a significância estatística foi maior.
• Tarefas de Downstream: Quando usados como codificações posicionais para Transformers em regressão molecular (AQSOL, PCQM4Mv2, ZINC), o GAPE alcançou erro médio absoluto (MAE) de estado da arte ou competitivo em comparação com codificações de Laplacian, Random Walk e outras codificações espectrais. Especificamente, GAPE+RWPE obteve os melhores resultados em AQSOL e PCQM4Mv2.
• Reconstrução: Um autoencoder com um encoder GAPE congelado alcançou mais de 98% de precisão na reconstrução da matriz de adjacência, confirmando que os embeddings capturam a topologia completa do grafo.
• Correlação: Uma forte correlação negativa ($r < -0.90$) foi observada entre a precisão do Alinhamento de Grafos e o erro de previsão de propriedades moleculares downstream, sugerindo que a capacidade de alinhamento estrutural é um gargalo primário para essas tarefas.

Significância e Alegações

O artigo afirma fornecer um framework robusto e detalhado para avaliar a expressividade estrutural de GNNs, independente de características específicas de nós ou arestas. Ao isolar o entendimento estrutural, o benchmark revela que modelos anisotrópicos oferecem uma representação mais rica da topologia do grafo do que os modelos isotrópicos anteriormente estabelecidos.

Além disso, os autores argumentam que a tarefa de Alinhamento de Grafos não é meramente um "quebra-cabeça", mas sim um objetivo de pré-treinamento fundamental. O fato de os embeddings aprendidos poderem ser usados para reconstrução de grafos de alta precisão e melhorar significativamente o desempenho de Transformers em tarefas downstream sugere que a tarefa força o modelo a aprender uma compressão de alta fidelidade da estrutura do grafo. Isso valida a utilidade do benchmark tanto para comparar arquiteturas quanto para gerar representações úteis para aplicações do mundo real em química e ciência dos materiais.

O trabalho conclui que o benchmark de Alinhamento de Grafos oferece uma abordagem flexível e agnóstica ao domínio para a avaliação de GNNs, capaz de se adaptar às características topológicas específicas de qualquer domínio de aplicação alvo.