Resumo Técnico: RADE – Random Add-Drop Edge como um Regularizador

Definição do Problema

As Redes Neurais de Grafos (GNNs), particularmente as Redes Neurais de Passagem de Mensagens (MPNNs), enfrentam dois desafios distintos: overfitting (sobreajuste) e over-squashing (esmagamento excessivo).

• Overfitting: Um problema generalizado de aprendizado de máquina onde os modelos falham em generalizar. Os regularizadores de GNN existentes frequentemente dependem de aumentos estocásticos de grafos, primariamente a exclusão de arestas (ex: DropEdge). No entanto, esses métodos podem introduzir um desalinhamento entre treino e inferência, onde o modelo treina em grafos perturbados, mas realiza a inferência no grafo original fixo, podendo causar desvios de distribuição.
• Over-squashing: Uma limitação estrutural onde a informação de nós distantes deve ser comprimida em embeddings de tamanho fixo conforme o número de camadas aumenta, dificultando a captura de dependências de longo alcance. As soluções existentes geralmente envolvem reestruturação (rewiring) determinística ou a adição de arestas de atalho para melhorar a conectividade. Embora eficazes para o fluxo de informação, esses métodos não regularizam inerentemente o treinamento contra o overfitting.

Trabalhos anteriores abordaram esses problemas de forma isolada: aumentos estocásticos regularizam, mas não melhoram a comunicação de longo alcance, enquanto métodos de reestruturação melhoram a conectividade, mas carecem de propriedades de regularização.

Metodologia

Os autores propõem o RADE (Random Add-Drop Edge), um framework de aumento de grafo estocástico que aborda simultaneamente o overfitting e o over-squashing ao adicionar e excluir arestas durante o treinamento. O RADE é projetado com dois componentes críticos:

1. Mecanismo de Perturbação

Em cada época de treinamento, o RADE amostra uma matriz de adjacência perturbada $A'$ do grafo de entrada $G$:

• Exclusão de Arestas: Arestas existentes são removidas com probabilidade $p$.
• Adição de Arestas: Não-arestas são adicionadas com probabilidade $q$.
  Isso generaliza o DropEdge (onde $q=0$) e permite a adição pura de arestas aleatórias (onde $p=0$).

2. Mecanismo de Correção de Agregação

Para evitar o desalinhamento entre treino e inferência, o RADE introduz regras explícitas de correção para a agregação de mensagens. Os autores propõem duas variantes baseadas no objetivo de treinamento:

• RADE-OF (Apenas Overfitting): Visa o overfitting garantindo que a agregação durante o treino seja preservadora da expectativa em relação à agregação de inferência do grafo de entrada original.

  • Mecanismo: Mensagens em arestas existentes são reescalonadas para corresponder à sua contribuição esperada. Mensagens em arestas recém-adicionadas são centralizadas (subtraídas pela média ponderada) para que sua contribuição esperada total seja zero.
  • Resultado: As perturbações aleatórias atuam puramente como um regularizador baseado em variância, sem deslocar a regra de inferência.

• RADE-OFS (Overfitting e Over-squashing): Visa ambos os problemas.

  • Mecanismo: Ele corrige o efeito de exclusão (reescalonando arestas existentes), mas mantém a contribuição esperada das arestas adicionadas.
  • Alinhamento de Inferência: A agregação em tempo de inferência é modificada para incluir a contribuição determinística esperada das arestas adicionadas.
  • Resultado: O treinamento é regularizado pela estocasticidade, enquanto a inferência beneficia-se da estrutura de grafo densificada, criando caminhos adicionais para a comunicação de longo alcance.

3. Seleção de Taxa Adaptativa (GradNorm)

Para evitar o ajuste de hiperparâmetros específicos de cada dataset para $p$ e $q$, o RADE emprega um algoritmo de balanceamento de norma de gradiente por mini-lote.

• Ele trata o efeito de regularização baseado em variância como um objetivo implícito.
• Ele ajusta dinamicamente $p$ e $q$ durante o treinamento para igualar a norma do gradiente do proxy de regularização com a da perda supervisionada.
• Um termo de penalidade evita a densificação excessiva do grafo, normalizando a taxa de adição em relação à densidade do grafo.
• Isso torna o RADE efetivamente livre de hiperparâmetros na prática.

Principais Contribuições

1. Framework Unificado: O RADE é o primeiro método a utilizar conjuntamente a exclusão e a adição aleatória de arestas para abordar tanto o overfitting quanto o over-squashing dentro de um único framework de aumento estocástico.
2. Alinhamento Teórico: O artigo fornece uma derivação fundamentada para a agregação preservadora da expectativa, garantindo que o treinamento estocástico se alinhe às regras de inferência, eliminando assim o desvio de distribuição.
3. Não-Intercambialidade de Primitivos: Os autores demonstram teórica e empiricamente que a exclusão e a adição de arestas induzem efeitos de regularização não-intercambiáveis. Elas atuam em diferentes estatísticas de nó (arestas existentes vs. não-arestas), e a combinação delas produz um desempenho superior em comparação ao uso de apenas uma delas.
4. Regularização Adaptativa: A introdução de uma regra baseada em GradNorm para ajustar as taxas de exclusão e adição elimina a necessidade de buscas manuais de hiperparâmetros.

Resultados Experimentais

Os autores avaliaram o RADE-OF e o RADE-OFS em diversos benchmarks de classificação de nós e de grafos usando backbones GCN, GIN e GAT.

• Classificação de Nós: O RADE-OF superou consistentemente regularizadores competitivos (Dropout, DropEdge, DropNode, DropMessage) na maioria dos datasets. O RADE-OFS apresentou desempenho comparável ou ligeiramente superior em datasets com over-squashing moderado (ex: PubMed).
• Classificação de Grafos: O RADE-OFS demonstrou os ganhos mais significativos, particularmente em datasets conhecidos por sofrer com over-squashing ou que exigem interações de longo alcance (ex: peptides-func, MUTAG). Ele superou todos os baselines nessas tarefas.
• Estudos de Ablação:
  • A remoção da correção preservadora da expectativa (EPC) ou da seleção de taxa adaptativa (GradNorm) degradou significativamente o desempenho, confirmando a necessidade de ambos o alinhamento e a adaptatividade.
  • A decomposição do RADE em variantes "Apenas Exclusão" (Drop-only) e "Apenas Adição" (Add-only) mostrou que a abordagem combinada superou consistentemente as variantes de componente único, validando a natureza complementar das duas operações.
  • A seleção de taxa adaptativa superou as taxas fixas e ajustadas manualmente em todos os datasets.

Significância e Alegações

O artigo afirma que o RADE oferece um framework de aumento simples e eficaz que faz a ponte entre a regularização e o enriquecimento de conectividade.

• Para Overfitting: O RADE-OF serve como um regularizador robusto e livre de hiperparâmetros que alinha o treino e a inferência, evitando as armadilhas das aumentações estocásticas padrão.
• Para Over-squashing: O RADE-OFS mitiga efetivamente o over-squashing ao preservar os benefícios das arestas adicionadas no tempo de inferência, tornando-o particularmente adequado para tarefas que exigem fluxo de informação de longo alcance.
• Praticidade: Ao utilizar uma regra de balanceamento de norma de gradiente, o RADE elimina a necessidade de ajustes tediosos e específicos de cada dataset para as taxas de perturbação, tornando-o um substituto prático para os pipelines de treinamento de GNN existentes.

Os autores concluem que a combinação de exclusão e adição aleatória de arestas, governada por correções preservadoras da expectativa e taxas adaptativas, fornece uma solução unificada para dois dos desafios mais persistentes das GNNs.