Invariant-Based Diagnostics for Graph Benchmarks

Resumo Técnico: Diagnósticos Baseados em Invariantes para Benchmarks de Grafos

Declaração do Problema
O progresso no desenvolvimento de modelos fundamentais de grafos (GFMs) está atualmente impedido por práticas de benchmarking que confundem as contribuições das características dos nós e da estrutura do grafo. Essa confusão torna difícil determinar se um modelo está genuinamente aprendendo a partir da conectividade ou apenas explorando correlações de características. Além disso, as práticas de avaliação existentes sofrem com tamanhos pequenos de conjuntos de dados, falta de diversidade estrutural dentro dos conjuntos de dados e um ênfase excessiva na expressividade teórica (por exemplo, a capacidade de distinguir grafos não isomorfos) que pode não alinhar-se com o desempenho preditivo real em tarefas específicas. Os autores argumentam que as Redes Neurais em Grafos (GNNs) padrão são inadequadas para isolar o impacto da estrutura porque elas entrelaçam informações estruturais e de características durante o processo de passagem de mensagens.

Metodologia
Os autores propõem um quadro de diagnóstico baseado em invariantes de grafo: descritores estruturais invariantes a permutações e agnósticos a tarefas que servem como "impressões digitais estruturais" para grafos. Esses invariantes são proxies computáveis para a estrutura do grafo que não dependem de parâmetros treináveis.

• Construção de Invariantes: O estudo utiliza um conjunto diversificado de invariantes, incluindo medidas básicas da teoria dos grafos (por exemplo, diâmetro, posto de circuito), métricas baseadas em entropia (por exemplo, entropia de von Neumann), invariantes geométricos e topológicos (por exemplo, torção analítica, contagens de homomorfismo) e índices moleculares (por exemplo, índice de Wiener, índice de Balaban). Estes são concatenados em um único vetor de características por grafo.
• Modelos: Os autores empregam duas famílias principais de modelos:
  1. Ensembles de Árvores com Boosting de Gradiente (XGBoost): Utilizados como classificadores primários para baselines baseadas em invariantes. Essa escolha é deliberada para garantir eficiência computacional e facilidade de ajuste de hiperparâmetros em 26 conjuntos de dados diversos.
  2. Redes Neurais em Grafos (GIN): Utilizadas em experimentos de aprendizado multi-tarefa para analisar o alinhamento de gradientes e a heterogeneidade estrutural.
• Cenários Experimentais: A metodologia é aplicada em quatro configurações experimentais distintas:
  1. Análise de Expressividade: Testando a capacidade dos invariantes de distinguir pares de grafos não isomorfos no conjunto de dados BREC (grafos indistinguíveis pelo teste de Weisfeiler-Lehman 1).
  2. Caracterização de Conjuntos de Dados: Tratando a associação ao conjunto de dados como uma tarefa de "meta-classificação" para quantificar a heterogeneidade estrutural dentro e entre domínios.
  3. Predição de Desempenho Multi-Tarefa: Investigando a correlação entre diferenças estruturais (medidas pela precisão da meta-classificação baseada em invariantes) e o alinhamento de gradientes/desempenho a jusante em configurações de aprendizado multi-tarefa.
  4. Benchmarking: Avaliando quatro configurações de entrada — características baseadas em soma, características baseadas em agregação, invariantes completos e um subconjunto expressivo mínimo de invariantes — em 26 conjuntos de dados para desvendar os papéis das características, da passagem de mensagens, da expressividade e da estrutura global.

Principais Contribuições e Resultados

1. Expressividade dos Invariantes:

   • Os invariantes demonstram ser mais expressivos do que as GNNs padrão no contexto do conjunto de dados BREC. Uma combinação simples de invariantes (especificamente um subconjunto de quatro) alcança 73% de precisão na distinção de pares não isomorfos, superando a maioria dos métodos baseados em GNNs e igualando o desempenho de arquiteturas mais complexas como N2.
   • Os autores demonstram que alta expressividade não requer o conjunto completo de invariantes; uma seleção gananciosa revela que um pequeno subconjunto é suficiente para capturar o mesmo poder discriminativo.

2. Caracterização da Heterogeneidade Estrutural:

   • Os invariantes caracterizam efetivamente os conjuntos de dados de benchmark existentes. Um meta-classificador usando invariantes alcança ~56% de precisão na distinção de 23 conjuntos de dados de diferentes domínios e ~93% de precisão ao distinguir conjuntos de dados dentro do mesmo domínio.
   • Isso indica uma pronunciada "mudança de conjunto de dados" onde grafos do mesmo domínio ainda possuem assinaturas estruturais distintas, sugerindo que os benchmarks atuais carecem da homogeneidade necessária para generalização robusta.

3. Predição de Desempenho Multi-Tarefa:

   • Há uma correlação negativa consistente entre a dissimilaridade estrutural de dois conjuntos de dados (medida pela precisão da meta-classificação) e seu desempenho em uma configuração de aprendizado multi-tarefa.
   • Maior dissimilaridade estrutural leva a menor alinhamento de gradientes e desempenho reduzido a jusante, sugerindo que mudanças estruturais são um obstáculo primário para pré-treinamento eficaz e aprendizado de transferência entre domínios.

4. Competitividade de Modelos Baseados em Invariantes:

   • Modelos simples baseados em invariantes (XGBoost treinado em vetores de invariantes) são competitivos com, e em alguns casos superam, as baselines state-of-the-art de transformadores e passagem de mensagens em 26 conjuntos de dados.
   • Notavelmente, em conjuntos de dados de "fluxo", os modelos baseados em invariantes superaram os melhores resultados reportados por uma margem significativa.
   • O estudo revela que a expressividade não é o principal motor do desempenho preditivo. Um subconjunto de invariantes com a mesma expressividade que o conjunto completo frequentemente produz desempenho preditivo inferior, indicando que a relevância específica da tarefa da estrutura importa mais do que o poder discriminativo bruto.
   • Em muitos casos, adicionar invariantes a baselines baseadas em características melhora o desempenho, mas em algumas tarefas (por exemplo, CIFAR10 representado como grades de pixels), os invariantes não fornecem ganho, indicando que a estrutura desempenha um papel marginal.

Significância e Alegações
O artigo postula que baselines baseadas em invariantes devem se tornar um padrão para avaliar benchmarks de grafos. Os autores argumentam que essas baselines servem a duas funções críticas:

1. Ferramenta de Diagnóstico: Elas ajudam a determinar se uma tarefa específica realmente requer estrutura de grafo. Se um modelo simples baseado em invariantes desempenha tão bem quanto uma GNN complexa, a tarefa pode não depender de informações estruturais.
2. Verificação de Alinhamento: Elas fornecem uma "verificação de sanidade" para detectar desalinhamento modelo-tarefa. Se um modelo complexo falha em superar substancialmente uma baseline de invariantes, o déficit provavelmente reflete sub-ajuste ou falha em extrair estrutura significativa, em vez de uma limitação fundamental da arquitetura.

Os autores concluem que o ênfase atual na expressividade como objetivo principal de design merece reconsideração. Em vez disso, o campo deve focar em entender a relevância da estrutura para tarefas específicas. Diagnósticos baseados em invariantes oferecem um ponto de verificação necessário para garantir que os conjuntos de dados sejam adequados para aprendizado em grafos antes de perseguir objetivos mais ambiciosos como modelos fundamentais de grafos. O artigo não alega que invariantes substituem GNNs, mas sim que eles fornecem uma baseline necessária e mínima para validar se a estrutura está sendo aprendida efetivamente.