Inductive Subgraphs as Shortcuts: Causal Disentanglement for Heterophilic Graph Learning

Título: Subgrafos Indutivos como Atalhos: Desemaranhamento Causal para Aprendizado em Grafos Heterofílicos

1. Problema e Motivação

Os grafos do mundo real frequentemente exibem heterofilia, onde nós conectados tendem a ter características e rótulos diferentes (em contraste com a homofilia, onde nós similares se conectam). As Redes Neurais em Grafos (GNNs) tradicionais, baseadas na suposição de homofilia (como GCN e GAT), sofrem degradação significativa de desempenho em grafos heterofílicos.

Embora trabalhos anteriores tenham tentado resolver isso através de extensão de vizinhança não-local ou refinamento de arquitetura, a causa fundamental das falhas de classificação permanece mal compreendida.

• A Hipótese Central: Os autores propõem que subgrafos indutivos (padrões estruturais recorrentes locais) atuam como "atalhos espúrios" (shortcuts).
• O Mecanismo de Falha: Em grafos homofílicos, esses padrões ajudam na inferência. No entanto, em grafos heterofílicos, eles induzem viéses que reforçam correlações não-causais entre a estrutura local e os rótulos, levando a previsões errôneas. O modelo aprende facilmente esses padrões recorrentes (atalhos) em vez de capturar os fatores causais verdadeiros.

2. Metodologia Proposta: CD-GNN

Para abordar esse problema, os autores introduzem o CD-GNN (Causal Disentangled GNN), um framework baseado em inferência causal que visa isolar os sinais causais verdadeiros dos atalhos espúrios.

2.1 Análise Causal e Modelagem

Os autores constroem um Modelo Causal Estrutural (SCM) para identificar dois caminhos não bloqueados que causam viés:

1. Caminho de Confundimento ($C \leftarrow S \rightarrow N \rightarrow E \rightarrow Y$): O subgrafo de atalho ($S$) atua como um confundidor, influenciando tanto o subgrafo causal ($C$) quanto a previsão ($Y$), criando uma correlação espúria.
2. Caminho de Transbordamento (Spillover) ($S \leftrightarrow C$): A relação bidirecional entre vizinhos de atalho e vizinhos causais viola a suposição de independência unitária (SUTVA), onde o resultado de um nó é influenciado pelo tratamento de seus vizinhos.

A solução proposta é bloquear explicitamente esses dois caminhos no grafo causal, garantindo que a previsão dependa apenas do subgrafo causal genuíno.

2.2 Arquitetura do CD-GNN

O framework utiliza uma estratégia de desemaranhamento causal através de máscaras de estrutura e características:

• Máscaras Causais e de Atalho: Para cada subgrafo de vizinhança, o modelo aprende máscaras probabilísticas para decompor o grafo em duas partes:
  • $G_c$: Subgrafo Causal (fatores verdadeiros).
  • $G_s$: Subgrafo de Atalho (padrões recorrentes espúrios).
• Dois Branches de GNN:
  • GNN de Atalho ($GNN_s$): Treinado para amplificar e capturar rapidamente os padrões de atalho.
  • GNN Causal ($GNN_c$): Treinado para capturar os sinais causais mais complexos.

2.3 Funções de Perda e Otimização

O modelo é otimizado através de uma combinação de quatro componentes de perda:

1. Amplificação de Atalho ($L_s$): Usa Generalized Cross-Entropy (GCE) para forçar o $GNN_s$ a aprender rapidamente os atalhos, isolando-os.
2. Aprendizado Causal ($L_c$): Usa um score de dificuldade relativa para reponderar a perda, forçando o $GNN_c$ a focar nos padrões causais mais difíceis de aprender.
3. Perda Contrafactual ($L_{cf}$): Cria embeddings contrafactuais de atalho (permutando aleatoriamente dentro do mini-batch) para garantir que a previsão causal seja invariante a mudanças nos atalhos, bloqueando o caminho de transbordamento.
4. Critério de Independência Hilbert-Schmidt ($L_{HSIC}$): Um regularizador que força a independência estatística entre os embeddings causais e os embeddings de atalho no nível dos nós, garantindo o desemaranhamento completo.

3. Contribuições Principais

1. Novas Perspectivas Teóricas e Empíricas: Demonstram que subgrafos indutivos são benignos em grafos homofílicos, mas atuam como atalhos maliciosos em grafos heterofílicos, degradando o desempenho.
2. Identificação de Vias Causais: Mapeiam formalmente as vias de confundimento e transbordamento que ligam subgrafos espúrios às previsões errôneas.
3. Framework de Desemaranhamento Causal (CD-GNN): Propõem o primeiro método a tratar o aprendizado em grafos heterofílicos sob a ótica de subgrafos indutivos, bloqueando ativamente as vias de viés sem modificar a arquitetura base de agregação de mensagens.
4. Garantias Teóricas: Provas matemáticas (Teoremas 3.1, 3.2 e 5.2) que mostram que o desemaranhamento aumenta o ganho de camada e a homofilia efetiva, mitigando a degradação de desempenho.

4. Resultados Experimentais

O CD-GNN foi avaliado em sete conjuntos de dados reais (incluindo benchmarks desafiadores como Chameleon, Squirrel, Roman-empire e Amazon-ratings).

• Desempenho: O CD-GNN superou consistentemente o estado da arte (SOTA) em 6 dos 7 conjuntos de dados, incluindo modelos baseados em causalidade (CIE, CAT) e modelos específicos para heterofilia (FAGCN, GGCN, LatGRL).
• Comparação: Em grafos com alta heterofilia (ex: Roman-empire com $h_L \approx 0.94$), o CD-GNN alcançou 65.85% de acurácia, superando significativamente o GCN (34.45%) e o GAT (39.36%).
• Estudo de Ablação: A remoção de qualquer componente (Amplificação de Atalho, Aprendizado Causal, Perda Contrafactual ou HSIC) resultou em queda de desempenho, validando a necessidade de todas as partes do framework.
• Complexidade: O método mantém uma complexidade computacional aceitável ($O(N^2)$ no pior caso devido ao HSIC), sendo viável para escalas de grafos típicas.

5. Significado e Impacto

Este trabalho representa uma mudança de paradigma no aprendizado de grafos heterofílicos:

• Mudança de Foco: Sai da análise puramente baseada em dinâmica de nós (como oversmoothing) para uma perspectiva estrutural, identificando padrões recorrentes como a fonte de viés.
• Interpretabilidade: Ao desemaranhar os fatores, o CD-GNN não apenas melhora a acurácia, mas também fornece interpretações em nível de subgrafo, revelando quais partes da estrutura são verdadeiramente causais para a decisão.
• Robustez: Oferece uma solução robusta para cenários onde a correlação entre vizinhos e rótulos é fraca ou enganosa, um problema comum em detecção de fraudes, redes sociais e sistemas de recomendação.

Em resumo, o CD-GNN demonstra que a chave para o aprendizado eficaz em grafos heterofílicos não é apenas agregar mais vizinhos, mas sim identificar e bloquear ativamente os atalhos estruturais espúrios que confundem os modelos tradicionais.