Inductive Subgraphs as Shortcuts: Causal Disentanglement for Heterophilic Graph Learning

1. Il Problema: Heterophily e i "Shortcut" Induttivi

Le GNN (Graph Neural Networks) standard, come GCN e GAT, si basano sull'ipotesi di omofilia (nodi collegati tendono ad avere caratteristiche ed etichette simili). Tuttavia, molti grafi reali (es. rilevamento frodi, interazioni sociali) sono eterofili, dove nodi collegati hanno spesso caratteristiche o etichette diverse. In questi contesti, le GNN tradizionali mostrano un crollo delle prestazioni.

La ricerca esistente ha tentato di risolvere il problema estendendo i vicini non-locali o affinando l'architettura (filtri spettrali/attenuazione). Tuttavia, questo lavoro identifica una causa fondamentale trascurata: i sottografi induttivi ricorrenti (pattern strutturali locali che si ripetono).

• L'ipotesi centrale: In grafi omofili, questi sottografi agiscono come segnali utili. In grafi eterofili, diventano "shortcut" (scorciatoie) spurie. Le GNN imparano facilmente questi pattern strutturali ricorrenti perché sono semplici da catturare, ma in contesti eterofili queste strutture non sono causalmente legate all'etichetta corretta, portando a correlazioni ingannevoli e classificazioni errate.

2. Metodologia: Causal Disentanglement (CD-GNN)

Gli autori adottano una prospettiva di inferenza causale per analizzare e correggere il comportamento di apprendimento distorto.

Analisi Causale

Vengono identificati due percorsi causali non bloccati che collegano i sottografi induttivi ($S$) alle previsioni del modello ($Y$), causando bias:

1. Percorso di Confondimento ($C \leftarrow S \rightarrow N \rightarrow E \rightarrow Y$): Il sottografo scorciatoia $S$ agisce come un confondente che influenza sia il sottografo causale vero ($C$) che il risultato, creando una correlazione spuria.
2. Percorso di Spillover ($S \leftrightarrow C$): Esiste un'interferenza di rete (spillover) tra i vicini scorciatoia e quelli causali, violando l'ipotesi di indipendenza (SUTVA) e permettendo a $S$ di distorcere l'apprendimento di $C$.

La Soluzione: CD-GNN (Causal Disentangled GNN)

Il framework proposto, CD-GNN, mira a disentanglare (separare) i sottografi spurii da quelli causali bloccando attivamente questi percorsi. L'architettura non modifica la struttura di base della GNN, ma introduce un meccanismo di disentanglement basato su:

1. Maschere Causali e Shortcut:

   • Vengono apprese maschere probabilistiche (strutturali e sulle feature) per dividere il sottografo dei vicini in due parti: un sottografo causale ($G_c$) e un sottografo shortcut ($G_s$).
   • Due rami di GNN separati ($GNN_c$ e $GNN_s$) elaborano queste parti.

2. Strategia di Ottimizzazione con Loss Multipli:

   • Shortcut Amplification Loss ($L_s$): Utilizza una Generalized Cross-Entropy per forzare il ramo $GNN_s$ a imparare rapidamente e catturare i pattern "facili" (i shortcut), isolandoli.
   • Causal Learning Loss ($L_c$): Utilizza un punteggio di difficoltà relativo per pesare di più le loss sui sottografi causali complessi, costringendo $GNN_c$ a concentrarsi sui segnali veri.
   • Counterfactual Loss ($L_{cf}$): Per bloccare il percorso di spillover, vengono create embedding controfattuali permutando casualmente le rappresentazioni degli shortcut all'interno di un mini-batch. Questo forza il modello a essere invariante rispetto agli shortcut.
   • HSIC Loss (Hilbert-Schmidt Independence Criterion): Agisce come regolarizzatore per garantire l'indipendenza statistica a livello di nodo tra le embedding causali e quelle shortcut.

3. Obiettivo Finale:
   La funzione di perdita totale combina questi elementi per massimizzare l'indipendenza tra $S$ e $C$, assicurando che la previsione finale dipenda solo dai fattori causali genuini.

3. Contributi Chiave

• Nuovi Insight Teorici ed Empirici: Dimostrano che i sottografi induttivi sono la causa radice del degrado nelle GNN eterofile, agendo come shortcut spurie. Forniscono prove teoriche (Teoremi 3.1 e 3.2) su come questi sottografi riducano l'omofilia effettiva e degradino il segnale di classe attraverso gli strati della rete.
• Debiasing Guidato dalla Causalità: Introduzione di CD-GNN, il primo framework che disentangla esplicitamente i pattern induttivi spurii dai fattori causali reali, bloccando i percorsi di confondimento e spillover.
• Interpretabilità: Il modello fornisce interpretazioni a livello di sottografo, rivelando quali parti della struttura del grafo guidano realmente le decisioni causali.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su 7 dataset reali (5 fortemente eterofili: Chameleon, Squirrel, Roman-empire, Amazon-ratings, Cornell; 2 omofili).

• Prestazioni: CD-GNN ha ottenuto le prestazioni migliori (SOTA) su 6 dei 7 dataset, superando significativamente sia le GNN standard (GCN, GAT, GraphSAGE) che i modelli specifici per l'eterofilia (FAGCN, CAGNN, GGCN, LatGRL) e i modelli basati su causalità (CIE, CAT).
• Robustezza: Il modello mostra una maggiore stabilità e accuratezza, specialmente nei grafi con alti tassi di eterofilia (es. $h_L > 0.8$), dove le baselines falliscono.
• Studi di Ablazione: La rimozione di qualsiasi componente (amplificazione shortcut, apprendimento causale, loss controfattuale, HSIC) porta a un calo significativo dell'accuratezza, confermando la necessità di tutti i moduli per il successo del metodo.
• Complessità: La complessità temporale e spaziale è gestibile ($O(N^2)$ nel caso peggiore per HSIC, ma accettabile per le scale dei grafi reali), senza richiedere risorse computazionali proibitive rispetto alle baselines.

5. Significato e Impatto

Questo lavoro rappresenta un cambio di paradigma nell'analisi delle GNN per grafi eterofili. Invece di concentrarsi solo sull'ottimizzazione dei vicini o sui filtri di frequenza, sposta l'attenzione sulla struttura induttiva nascosta che inganna i modelli.

• Teorico: Fornisce una spiegazione causale rigorosa del perché le GNN falliscono in contesti eterofili, collegando il problema ai "shortcut" induttivi.
• Pratico: Offre una soluzione robusta e interpretabile che può essere applicata a scenari reali critici come il rilevamento di frodi, la raccomandazione e l'analisi di reti sociali, dove l'eterofilia è la norma e non l'eccezione.
• Generale: Introduce un approccio di "disentanglement causale" che potrebbe essere esteso ad altri domini di apprendimento su grafi dove i pattern strutturali ricorrenti possono creare bias.