Inductive Subgraphs as Shortcuts: Causal Disentanglement for Heterophilic Graph Learning

1. Problem Statement

Heterophily in graphs refers to the phenomenon where connected nodes often possess different features and labels (e.g., in telecom fraud detection, scammers contact legitimate users). This property violates the homophily assumption underlying most standard Graph Neural Networks (GNNs) like GCN and GAT, leading to significant performance degradation.

While prior work has attempted to address this via non-local neighbor extension or architectural refinements (e.g., spectral filters), the fundamental cause of misclassification remains unclear. The authors identify a specific, overlooked source of bias: Inductive Subgraphs.

• The Core Issue: In real-world graphs, recurring local structural patterns (motifs) act as inductive subgraphs.
• The Shortcut Effect: In homophilic graphs, these patterns are beneficial. However, in heterophilic graphs, they act as spurious shortcuts. GNNs easily learn these recurring structural motifs because they are statistically frequent, but these motifs often encode non-causal correlations (e.g., a specific shape appearing frequently with the wrong label in a heterophilic context).
• Consequence: The model relies on these easy-to-fit shortcuts rather than genuine causal signals, leading to biased predictions and poor generalization.

2. Methodology: Causal Disentangled GNN (CD-GNN)

The authors propose CD-GNN, a framework grounded in causal inference to disentangle spurious inductive subgraphs from true causal factors.

A. Causal Analysis & Structural Causal Model (SCM)

The authors construct a causal graph to analyze the learning trajectory, identifying two unblocked paths that cause bias:

1. Confounding Path ($C \leftarrow S \rightarrow N \rightarrow E \rightarrow Y$): The shortcut subgraph ($S$) acts as a confounder between the causal subgraph ($C$) and the neighborhood ($N$), creating a spurious correlation between $S$ and the label ($Y$).
2. Spillover Path ($S \leftrightarrow C$): A bidirectional "network interference" where the shortcut neighbors influence the causal neighbors, violating the Stable Unit Treatment Value Assumption (SUTVA).

Goal: Block both paths to ensure predictions depend only on the causal subgraph ($C$).

B. The CD-GNN Framework

The model employs a dual-branch architecture to separate the graph into Causal Subgraphs ($G_c$) and Shortcut Subgraphs ($G_s$) using learnable edge and feature masks.

1. Graph Disentanglement:

   • Shortcut Amplification ($L_s$): Uses Generalized Cross-Entropy (GCE) loss to force the "Shortcut GNN" branch to rapidly capture and amplify the easy-to-learn inductive patterns. This isolates the shortcut signals.
   • Causal Learning ($L_c$): Uses a difficulty-weighted loss to force the "Causal GNN" branch to focus on the harder, complex, but truly predictive causal patterns.

2. Spillover Control (Debiasing):

   • Counterfactual Loss ($L_{cf}$): To break the spillover path ($S \leftrightarrow C$), the model generates counterfactual shortcut embeddings by randomly permuting shortcut features within a mini-batch. This ensures the causal branch learns to predict labels regardless of the specific shortcut configuration.
   • Hilbert-Schmidt Independence Criterion ($L_{HSIC}$): A regularizer applied at the node level to enforce statistical independence between the causal embeddings ($h_{Gc}$) and shortcut embeddings ($h_{Gs}$), ensuring no residual entanglement.

3. Optimization Objective:
   The total loss combines the disentanglement losses and the spillover control regularizers:
   $$\mathcal{L} = \mathcal{L}_s + \mathcal{L}_c + \lambda_1 \mathcal{L}_{cf} + \lambda_2 \mathcal{L}_{HSIC}$$

3. Key Contributions

1. New Theoretical Insight: The paper provides the first empirical and theoretical evidence that inductive subgraphs act as spurious shortcuts in heterophilic graphs. It proves (via Theorems 3.1 and 3.2) that these subgraphs reduce the "effective homophily" of the message passing, causing class-related signals to decay multiplicatively with depth.
2. Causal Disentanglement Framework: CD-GNN is the first method to explicitly model and block the confounding and spillover paths induced by structural motifs in heterophilic graphs without modifying the underlying GNN architecture (e.g., spectral filters).
3. Theoretical Guarantees: The authors prove that by reducing the dominance of shortcut subgraphs in the causal branch, the effective homophily increases, thereby preserving class-related signals and improving classification margins.

4. Experimental Results

The authors evaluated CD-GNN on 7 benchmark datasets (5 highly heterophilic: Chameleon, Squirrel, Roman-empire, Amazon-ratings, Cornell; 2 homophilic: Computers, Questions).

• Performance: CD-GNN achieved State-of-the-Art (SOTA) results on 6 out of 7 datasets, significantly outperforming standard GNNs (GCN, GAT), causal baselines (CIE, CAT), and heterophily-specific models (FAGCN, GGCN, LatGRL).
  • Example: On the highly heterophilic Roman-empire dataset ($h_L \approx 0.94$), CD-GNN achieved 65.85% accuracy, outperforming the runner-up (GGCN) by ~0.5% and standard GCN by >30%.
• Ablation Studies: Removing any component (Shortcut Amplification, Causal Learning, Counterfactual Loss, or HSIC) resulted in a noticeable drop in accuracy, confirming that all parts are necessary for effective disentanglement.
• Complexity: The method has a time complexity of $O(N^2)$ due to the HSIC calculation, which is acceptable for typical graph scales.

5. Significance

This work shifts the paradigm of heterophilic graph learning from representation dynamics (e.g., oversmoothing) to structural inductive bias.

• Interpretability: By disentangling the graph, CD-GNN provides subgraph-level explanations, revealing which parts of the graph are truly causal versus spurious.
• Robustness: It offers a principled solution for learning on graphs where "similar nodes are not connected," a common scenario in fraud detection, biological networks, and social recommendation systems.
• Generalizability: The causal disentanglement approach can potentially be applied to other domains where spurious correlations arise from recurring structural patterns.