Inductive Subgraphs as Shortcuts: Causal Disentanglement for Heterophilic Graph Learning

Probleemstelling

Graph Neural Networks (GNNs) presteren doorgaans slecht op heterofiele grafieken (grafieken waar verbonden knopen vaak verschillende labels of kenmerken hebben). Bestaande methoden proberen dit op te lossen door het uitbreiden van het receptieve veld (niet-lokale buren) of door architecturale verfijning (bijv. spectrale filters). Echter, de fundamentele reden voor misclassificaties blijft onduidelijk.

De auteurs identificeren een nieuwe oorzaak: inductieve subgrafieken (terugkerende lokale patronen of motieven).

• In homofiele grafieken fungeren deze patronen als nuttige inductieve bias.
• In heterofiele grafieken fungeren ze echter als spurious shortcuts (valse kortere wegen). GNNs leren deze makkelijke, terugkerende structuren liever dan de complexe causale relaties, wat leidt tot misleidende associaties tussen structuur en labels en uiteindelijk tot een afname van de prestaties.

Methodologie: Causal Disentangled GNN (CD-GNN)

De auteurs benaderen het probleem vanuit een causale inferentie-perspectief. Ze analyseren het leerproces via een Structureel Causaal Model (SCM) en identificeren twee ongeblokkeerde paden die leiden tot bias:

1. Verwarringspad (Confounding Path): De inductieve subgraaf ($S$) werkt als een confounder die zowel de causale subgraaf ($C$) als de uitkomst ($Y$) beïnvloedt, waardoor een valse correlatie ontstaat.
2. Spillover-pad: Er bestaat een wederzijdse afhankelijkheid tussen de shortcut-buren ($S$) en de causale buren ($C$), wat de Stable Unit Treatment Value Assumption (SUTVA) schendt.

Om dit op te lossen, stellen ze CD-GNN voor, een framework dat deze paden expliciet blokkeert door inductieve subgrafieken te ontkoppelen van de ware causale factoren. De kerncomponenten zijn:

1. Causale en Shortcut Maskers:

   • Het model deconstrueert de burensubgraaf in twee delen: een causale subgraaf ($G_c$) en een shortcut subgraaf ($G_s$) via geleerde structurele en kenmerk-masking.
   • Twee aparte GNN-branches worden getraind: een Shortcut GNN en een Causal GNN.

2. Ontkoppelingsstrategie (Disentanglement):

   • Shortcut Amplification Loss ($L_s$): Gebruikt Generalized Cross-Entropy (GCE) om de gradienten voor de shortcut-branch te versterken. Dit dwingt het model om de makkelijke, terugkerende patronen snel te leren en te isoleren.
   • Causal Learning Loss ($L_c$): Gebruikt een "relative difficulty score" om de cross-entropy loss te up-weighten voor de causale branch. Dit dwingt het model om zich te focussen op de complexere, maar cruciale causale signalen.

3. Controle van Spillover-effecten:

   • Counterfactual Loss ($L_{cf}$): Door shortcut-embeddings binnen een mini-batch te permuteren, worden counterfactual voorbeelden gegenereerd. Dit forceert de causale branch om onafhankelijk te zijn van specifieke shortcut-embeddings.
   • Hilbert-Schmidt Independence Criterion (HSIC): Een regularisatieterm die de statistische onafhankelijkheid tussen de causale en shortcut embeddings op knopeniveau garandeert, waardoor de spillover-paden effectief worden geblokkeerd.

4. Theoretische Garantie:

   • De auteurs bewijzen dat door de dominantie van de shortcut-subgraaf in de causale branch te verminderen, de effectieve homofilie ($h_{eff}$) toeneemt. Dit resulteert in een langzamere verval van het class-gerelateerde signaal over de lagen van het netwerk, wat de prestaties op heterofiele grafieken theoretisch garandeert.

Belangrijkste Resultaten

De methode werd getest op zeven benchmark datasets, waaronder sterk heterofiele datasets (Chameleon, Squirrel, Roman-empire) en homofiele datasets.

• Prestaties: CD-GNN behaalde de hoogste nauwkeurigheid op 6 van de 7 datasets en presteerde als tweede op de zevende. Het overtrof state-of-the-art (SOTA) methoden zoals FAGCN, GGCN, LatGRL en causale baselines zoals CIE en CAT.
• Ablatiestudies: Het verwijderen van enige component (zoals de HSIC loss of de counterfactual loss) leidde tot een merkbare daling in prestaties, wat aantoont dat zowel het isoleren van shortcuts als het garanderen van onafhankelijkheid essentieel zijn.
• Robuustheid: Het model is bijzonder effectief bij extreme heterofilie-ratio's, waar traditionele GNNs vaak volledig falen.

Significantie en Bijdragen

1. Nieuw Inzicht: Het paper verschuift de focus van knopen-niveau dynamiek (zoals oversmoothing) naar een structureel perspectief. Het identificeert inductieve subgrafieken als een eerder over het hoofd gezien bron van bias in heterofiele grafieken.
2. Causale Ontkoppeling: Het is de eerste werk dat heterofiel grafiekleren benadert door expliciet causale en spurious inductieve patronen te ontkoppelen via een causaal gefundeerd framework.
3. Interpreteerbaarheid: CD-GNN biedt niet alleen betere nauwkeurigheid, maar levert ook subgraaf-niveau interpretaties die de ware causale drijfveren van de beslissingen van het model blootleggen.
4. Theoretische Onderbouwing: Het paper levert rigoureuze theoretische bewijzen die aantonen hoe het blokkeren van confounding en spillover-paden de degradatie van GNN-prestaties op heterofiele grafieken tegengaat.

Samenvattend biedt CD-GNN een principieel en robuust antwoord op de uitdagingen van heterofiele grafieken door de "traps" van inductieve shortcuts te omzeilen en zich te focussen op de onderliggende causale structuur van de data.