Resumo Técnico: Características de Agregação Fixas Podem Rivalizar com GNNs

Declaração do Problema

As Redes Neurais de Grafos (GNNs) tornaram-se o padrão para o aprendizado de dados estruturados em grafos, particularmente para classificação de nós. Esses modelos tipicamente dependem do paradigma de passagem de mensagens, onde as representações dos nós são atualizadas através de múltiplas camadas de agregações de vizinhança treináveis (por exemplo, combinações lineares aprendidas, mecanismos de atenção). Embora eficaz, essa abordagem introduz alta complexidade de modelo, desafios de interpretabilidade e custos computacionais significativos.

Evidências recentes sugerem que as GNNs clássicas (GCN, GAT, GraphSAGE) permanecem competitivas com Graph Transformers de última geração e modelos conscientes de heterofilia quando equipadas com um ajuste rigoroso de hiperparâmetros. Isso levanta uma questão fundamental: A alta complexidade de aprender funções de agregação é realmente necessária? Especificamente, quão relevante é o aprendizado da própria agregação em comparação com a tarefa de classificação downstream?

Metodologia: Características de Agregação Fixas (FAFs)

Os autores introduzem as Características de Agregação Fixas (FAFs), uma abordagem livre de treinamento que transforma tarefas de aprendizado em grafos em problemas tabulares padrão. A ideia central é desacoplar o aprendizado de representação da otimização, utilizando operadores de agregação fixos e não treináveis.

O Pipeline FAF

1. Agregação Fixa: Para um determinado nó $v$, o método computa recursivamente características de suas vizinhanças de $k$-saltos usando um conjunto de redutores fixos $\mathcal{R}$ (ex: média, soma, máximo, mínimo, desvio padrão).
   • $h^{(0,r)}_v = x_v$ (características originais)
   • $h^{(k,r)}_v = r(\{h^{(k-1,r)}_u : u \in \mathcal{N}(v)\})$
2. Concatenação de Características: As características de todos os saltos ($k \in \{1, \dots, K\}$) e de todos os redutores ($r \in \mathcal{R}$) são concatenadas com as características originais do nó para formar um vetor tabular de alta dimensão $z_v$.
   • $z_v = x_v \oplus \bigoplus_{r \in \mathcal{R}} \bigoplus_{k=1}^K h^{(k,r)}_v$
3. Classificação Downstream: Um Perceptron Multicamadas (MLP) padrão e bem ajustado é treinado sobre essas características fixas $z_v$. Nenhum gradiente é retropropagado através dos passos de agregação; a agregação é um passo de pré-processamento.

Fundamentação Teórica

O artigo conecta as FAFs ao teorema da representação de Kolmogorov–Arnold, que afirma que qualquer função contínua multivariada pode ser representada como uma composição de funções univariadas.

• Possibilidade Teórica: Os autores constroem uma função de agregação injetiva fixa específica $\Phi$ (baseada em expansões ternárias e no conjunto de Cantor) que teoricamente permite uma codificação sem perdas de multiconjuntos de vizinhança. Isso implica que, em teoria, nenhuma informação precisa ser aprendida durante a agregação para preservar a expressividade.
• Realidade Prática: Embora $\Phi$ seja teoricamente sem perdas, ela é numericamente instável e produz embeddings "rugosos" inadequados para classificadores padrão. Em contraste, redutores simples e não injetivos (como média e soma) são empiricamente mais propensos à otimização. Os autores argumentam que, para a maioria dos benchmarks, o sinal relevante está concentrado em vizinhanças de poucos saltos (1–2 saltos), onde agregações simples preservam informação suficiente.

Principais Contribuições

1. Insight Teórico: O artigo estabelece que a agregação de vizinhança sem perdas é teoricamente possível via funções injetivas fixas derivadas de representações de Kolmogorov–Arnold. No entanto, destaca uma lacuna crucial entre expressividade e aprendizado: redutores simples e não injetivos frequentemente produzem melhor desempenho prático porque geram embeddings mais suaves que os classificadores downstream podem otimizar de forma mais eficaz.
2. Proposta Metodológica: A introdução das FAFs, que converte dados de grafos em um formato tabular ao empilhar agregações de múltiplos saltos fixas. Isso fornece um framework interpretável para estudar a interação entre estrutura de grafo, características e a tarefa sem viés arquitetural.
3. Evidência Empírica: Experimentos extensos em 14 benchmarks padrão de classificação de nós mostram que as FAFs, combinadas com MLPs bem ajustados, rivalizam ou superam o estado da arte de GNNs e Graph Transformers em 12 de 14 tarefas.
   • Desempenho: As FAFs igualam ou excedem as GNNs clássicas (GCN, GAT, SAGE) e arquiteturas complexas em redes de citações (Cora, Citeseer, PubMed), grafos de coautoria e grafos de produtos da Amazon.
   • Exceções: As FAFs apresentam desempenho inferior apenas nos conjuntos de dados Roman Empire e Minesweeper. Os autores atribuem isso ao fato de esses datasets exigirem dependências de longo alcance ou conexões residuais lineares específicas que as FAFs padrão (usando 2–4 saltos) não capturam, alinhando-se com achados de que essas tarefas se beneficiam de GNNs profundas com resíduos parametrizados.
4. Implicações para Benchmarking: Os resultados desafiam a necessidade de agregação aprendida nos benchmarks atuais. Os autores argumentam que muitos datasets podem ser resolvidos por preditores tabulares poderosos alimentados com características fixas e transparentes, sugerindo que os benchmarks atuais podem não testar adequadamente a capacidade de modelos de aprender dinâmicas de agregação complexas.

Resultados e Análise

• Estudos de Ablação:
  • Complexidade do Classificador: Um MLP bem ajustado supera significativamente uma única camada linear quando aplicado às características FAF, indicando que não linearidade e capacidade são cruciais para aproveitar informações de múltiplos saltos.
  • Concatenação de Saltos: Concatenar características de todos os saltos produz melhor desempenho do que usar apenas o último salto, confirmando que informação é perdida durante agregações repetidas e que os saltos iniciais (0–2) contêm o sinal mais preditivo.
  • Escolha do Redutor: Embora a concatenação de múltiplos redutores (ex: média, soma, máximo, mínimo) seja geralmente benéfica, um único redutor (frequentemente a média) frequentemente basta e às vezes supera combinações complexas, provavelmente devido à redução de overfitting em espaços de alta dimensão.
• Interpretabilidade: Ao tratar o problema como tabular, os autores utilizam valores SHAP para analisar a importância das características. Por exemplo, no dataset Minesweeper, eles identificam que a média do salto-1 de características específicas é o principal sinal, esclarecendo exatamente onde o modelo tem sucesso ou falha.
• Eficiência: Pré-computar agregações e treinar um MLP é geralmente mais escalável e eficiente do que treinar GNNs profundas, embora a dimensionalidade de entrada aumente com o número de saltos e redutores.

Significância e Alegações

O artigo postula que o campo do aprendizado em grafos pode estar excessivamente dependente de mecanismos de agregação complexos e treináveis para tarefas onde estatísticas simples e fixas são suficientes. Os autores afirmam que:

1. Baselines Fortes: As FAFs devem servir como um baseline obrigatório e forte para futuras pesquisas de aprendizado em grafos. Se uma nova GNN não consegue superar uma FAF bem ajustada, sua complexidade adicional pode não ser justificada.
2. Reavaliação de Benchmarks: Os benchmarks atuais (ex: Cora, Citeseer) podem não exigir genuinamente agregação aprendida, pois o sinal preditivo está frequentemente concentrado em vizinhanças de baixa ordem. Os autores pedem "benchmarks mais ricos" que testem especificamente dependências de longo alcance e dinâmicas complexas entre saltos.
3. Otimização vs. Expressividade: O sucesso das FAFs sugere que a otimizabilidade e a treinabilidade são tão críticas quanto a expressividade teórica. GNNs complexas podem ter dificuldade em aprender agregações úteis devido a dificuldades de otimização (ex: desaparecimento de gradiente, over-smoothing), e não por falta de capacidade teórica.
4. Perspectiva Tabular: Converter problemas de grafos em problemas tabulares permite que pesquisadores utilizem o conjunto de ferramentas maduro do aprendizado tabular (seleção de características, interpretabilidade, tratamento de desequilíbrio de classes) e isole a contribuição da estrutura do grafo dos artefatos de otimização.

Em conclusão, os autores defendem uma mudança de foco: em vez de assumir que parâmetros extras ou maior expressividade extraem automaticamente sinais mais relevantes, a comunidade deve priorizar modelos mais simples e interpretáveis e projetar benchmarks que genuinamente necessitem do aprendizado de funções de agregação complexas.