Resumo Técnico: Revisão de GNNs de Pré-Propagação

1. Declaração do Problema

As Redes Neurais em Grafos de Pré-Propagação (PP-GNNs) oferecem uma alternativa escalável às tradicionais Redes Neurais em Grafos de Passagem de Mensagens (MP-GNNs), ao desacoplar a propagação de características da transformação. Nas PP-GNNs, a difusão do grafo é realizada uma única vez como uma etapa de pré-processamento para gerar características de múltiplos saltos, permitindo que a fase subsequente de treinamento utilize transformações densas e passíveis de mini-lotes, sem dependências inter-nós. Embora esse design melhore a eficiência e se alinhe com aceleradores de hardware modernos otimizados para computação densa, as PP-GNNs apresentam uma lacuna de desempenho significativa em comparação com as MP-GNNs, particularmente em grafos heterofílicos (onde nós conectados frequentemente possuem rótulos diferentes).

Os autores identificam duas limitações principais de design que contribuem para essa lacuna:

1. Limitações do Operador de Difusão: As PP-GNNs padrão dependem de operadores simples (por exemplo, adjacência normalizada, passeios aleatórios) que atuam como filtros passa-baixas. Estes são subótimos para grafos heterofílicos, que frequentemente requerem componentes de frequência mais alta ou de banda. Além disso, as bases de difusão monomiais padrão (potências da matriz de difusão) são frequentemente mal condicionadas e produzem características altamente correlacionadas, limitando a qualidade da aproximação.
2. Propagação de Único Disparo: As PP-GNNs propagam características de entrada brutas apenas uma vez. Diferentemente das MP-GNNs, que intercalam iterativamente a propagação com transformações não lineares para refinar representações adaptadas à tarefa, as PP-GNNs não podem atualizar as características propagadas com base em estados ocultos em evolução durante o treinamento.

2. Metodologia

O artigo propõe um conjunto de melhorias para fechar a lacuna de precisão, preservando a eficiência de treinamento das PP-GNNs. A abordagem consiste em três componentes principais:

A. Operadores de Difusão Robustos

Para abordar as limitações das bases de difusão padrão, os autores introduzem duas bases de difusão ortogonais e melhor condicionadas para a etapa de pré-processamento:

• Base de Polinômios de Jacobi: Em vez de usar monômios $\Phi^k$, os autores utilizam polinômios de Jacobi $P_k^{(\alpha, \beta)}(\tilde{L})$, onde $\tilde{L}$ é um Laplaciano deslocado. Os parâmetros $(\alpha, \beta)$ são calibrados em uma única etapa de pré-processamento leve, com base na densidade espectral do grafo (usando momentos de Chebyshev estocásticos) para alocar resolução onde o espectro do grafo se concentra. Isso cria uma base ortogonal que reduz a correlação de características.
• Base de Subespaço de Lanczos/Krylov: Para capturar conteúdo espectral específico de canal, os autores constroem um subespaço de Krylov para cada canal de característica usando a iteração de Lanczos. Isso gera um conjunto de vetores e valores de Ritz que formam um banco de difusão ortogonal e alinhado ao sinal. Este método decompõe características em componentes decorrelacionados, fornecendo um sistema de coordenadas mais estável para agregação sob um orçamento fixo de saltos.

B. Re-Propagação de Estado Oculto (HRP)

Para superar a limitação de "único disparo", os autores introduzem a Re-Propagação de Estado Oculto (HRP). Este mecanismo recasoa a propagação de características com representações aprendidas:

• Mecanismo: O treinamento é dividido em múltiplos estágios. Ao final de cada estágio, a melhor representação oculta (antes da projeção de saída final) é selecionada e desvinculada. Este estado oculto é então re-propagado através do operador de difusão para gerar um novo conjunto de características de múltiplos saltos.
• Integração: Essas características ocultas re-propagadas são misturadas com as características pré-calculadas originais para formar a entrada do próximo estágio de treinamento.
• Distinção: Os autores contrastam explicitamente a HRP com reutilização baseada em rótulos (por exemplo, usar logits ou rótulos one-hot como características). Eles argumentam que re-propagar estados ocultos de alta dimensionalidade carrega informação relacional complementar além das probabilidades de classe, enquanto a propagação de rótulos pode introduzir atalhos ou ruído, especialmente em grafos heterofílicos.

C. Agregador de Saltos Baseado em RNN

Como uma melhoria opcional de eficiência, os autores propõem substituir agregadores de Atenção Multi-Cabeça (MHA) (usados em modelos como HOGA) por uma Rede Neural Recorrente (RNN) para processar a sequência de características de saltos. Isso reduz a sobrecarga computacional e o uso de memória, mantendo precisão comparável.

3. Contribuições Principais

1. Adaptação de Bases de Difusão Robustas: O artigo adapta bases de difusão de polinômios de Jacobi e subespaço de Krylov ao regime de pré-processamento de PP-GNNs. Essas bases melhoram o condicionamento das características pré-calculadas e permitem respostas espectrais mais ricas sob um orçamento fixo de saltos.
2. Re-Propagação de Estado Oculto (HRP): Um mecanismo leve que refina iterativamente as PP-GNNs re-propagando estados ocultos intermediários, efetivamente fechando a lacuna entre propagação de único disparo e passagem de mensagens iterativa sem sacrificar a escalabilidade.
3. Agregação Eficiente: Um agregador de saltos baseado em RNN que serve como uma alternativa computacionalmente mais barata à agregação baseada em atenção.
4. Validação Empírica: Experimentos extensivos em 12 conjuntos de dados (6 heterofílicos, 6 homofílicos) e 4 backbones de PP-GNN (SIGN, HOGA, GAMLP, GARNN).

4. Resultados Experimentais

Os métodos propostos foram avaliados em benchmarks heterofílicos e homofílicos:

• Grafos Heterofílicos: Em seis conjuntos de dados heterofílicos (incluindo Roman-Empire, Minesweeper e Pokec), as PP-GNNs aprimoradas reduziram significativamente a lacuna de precisão com as MP-GNNs.
  • A melhoria média na precisão de teste sobre as PP-GNNs de linha de base foi de +2,18% em conjuntos de dados heterofílicos.
  • Os modelos aprimorados superaram fortes linhas de base de MP-GNN (por exemplo, GraphSAGE, GAT) em 4 de 6 grafos heterofílicos.
  • No conjunto de dados Roman-Empire, a lacuna de precisão entre MP-GNNs e PP-GNNs foi reduzida de ~11% para quase paridade.
• Grafos Homofílicos: As melhorias também se transferiram para conjuntos de dados homofílicos (por exemplo, Cora, Citeseer, OGBN-Arxiv), com uma melhoria média de +1,96%. As PP-GNNs aprimoradas superaram as MP-GNNs em 3 de 6 conjuntos de dados homofílicos.
• Estudos de Ablação:
  • Operadores de difusão robustos isoladamente forneceram um ganho médio de ~2,09% (validação) / 1,99% (teste).
  • A HRP forneceu um ganho adicional de ~1,54% (validação) / 1,61% (teste).
  • A HRP superou significativamente estratégias de rótulo-como-entrada e propagação de rótulos, particularmente em grafos heterofílicos onde a suavidade de rótulos é baixa.
• Eficiência:
  • O operador de Lanczos adiciona um custo comparável a algumas etapas padrão de difusão.
  • A HRP introduz um pequeno número de estágios (tipicamente < 4, máximo 7), com a difusão de re-propagação representando apenas ~2% do tempo total de treinamento.
  • O agregador baseado em RNN (GARNN) alcançou precisão semelhante à HOGA, mas com tempo de treinamento significativamente reduzido (2,4s/época vs. 8,4s/época em Pokec).
  • No geral, as PP-GNNs aprimoradas alcançam uma troca favorável entre precisão e tempo de execução, aproximando a família PP-GNN da fronteira de Pareto das MP-GNNs.

5. Significado e Alegações

O artigo afirma que o framework proposto aborda com sucesso as limitações de expressividade das Redes Neurais em Grafos de Pré-Propagação sem recorrer aos gargalos computacionais da passagem de mensagens iterativa.

• Escalabilidade vs. Expressividade: O trabalho demonstra que as PP-GNNs não sacrificam inerentemente a expressividade pela escalabilidade; em vez disso, a lacuna decorre de operadores de difusão subótimos e da falta de refinamento iterativo. Ao usar bases de difusão robustas e HRP, as PP-GNNs podem igualar ou exceder a precisão das MP-GNNs, mantendo sua eficiência de treinamento e capacidades de mini-lotes.
• Aplicabilidade Geral: Embora motivado pelos desafios da heterofilia, os métodos demonstraram ser benéficos em estruturas de grafos tanto heterofílicos quanto homofílicos.
• Impacto Prático: A abordagem oferece um caminho para implantar GNNs altamente escaláveis em grafos de grande escala (por exemplo, redes sociais, sistemas de recomendação) com desempenho competitivo em relação a modelos de passagem de mensagens de última geração, potencialmente reduzindo custos computacionais e consumo de energia para aprendizado de grafos em grande escala.

Os autores mantêm uma postura modesta, observando que, embora os métodos melhorem o desempenho, eles não introduzem novas modalidades de dados nem previnem inerentemente riscos éticos downstream associados ao aprendizado em grafos (como amplificação de viés), enfatizando a necessidade de práticas responsáveis de ML na implantação.