Research map / Graph learning / Graph self-supervised learning
Pruning Spurious Subgraphs for Graph Out-of-Distribution Generalization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PrunE, a pruning-based graph OOD method that removes spurious edges via a graph size constraint and an epsilon-probability alignment regularizer on a learned edge subgraph selector, trained with ERM.
Problem
Graph neural networks degrade under distribution shift; prior graph OOD methods directly identify invariant subgraphs by edge selection, which is error-prone when spurious edges correlate strongly with labels.
Approach
Instead of identifying invariant edges directly, prune spurious edges using two regularizers on the subgraph selector (a total-edge budget eta*|E| and pushing the bottom K% edge probabilities toward epsilon=1/|E|), added to the ERM loss without extra OOD objectives.
Key results
- PrunE reaches 91.48% on GOODMotif-base and 66.53% on GOODMotif-size, beating the second-best AIA (72.91%, 55.85%) by about 24% and 19% respectively.
- Across real-world datasets PrunE outperforms AIA by an average of 2.38% on 7 datasets, per the paper.
- Under concept shift PrunE achieves 90.28% on GOODMotif-base, 10.86% above ERM.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PrunE instead of AIA | GOODMotif base · GOODMotif base | accuracy: 72.91 -> 91.48 | Helped |
| Use PrunE instead of AIA | GOODMotif size · GOODMotif size | accuracy: 55.85 -> 66.53 | Helped |
| Use PrunE instead of the strongest baseline | GOODHIV and EC50 benchmarks · GOODHIV scaffold, GOODHIV size, EC50 scaffold, EC50 size, EC50 assay | ROC-AUC | Helped |
| Use PrunE instead of AIA | OGBG-Molbbbp scaffold · OGBG-Molbbbp scaffold | ROC-AUC: 70.79 -> 70.32 | Hurt |
| Use PrunE instead of AIA | GOODHIV size and GOODMotif base (concept shift) · GOODHIV size and GOODMotif base | ROC-AUC / accuracy | Helped |
| Remove the graph size constraint loss L_e (ablation) | PrunE · GOODMotif and GOODHIV datasets | test performance | Hurt |
| Remove the epsilon-probability alignment loss L_s (ablation) | PrunE · GOODMotif and GOODHIV datasets | test performance | Hurt |
| Add epsilon-probability alignment loss L_s (ablation) | PrunE with graph size constraint · GOODMotif and GOODHIV datasets | test performance | Helped |
| Increase alignment probability epsilon (ablation) | PrunE · GOODMotif and EC50 scaffold | test performance | Hurt |
| Use GIN instead of GCN as the feature encoder (ablation) | PrunE · Four datasets | test performance | Helped |
| Set edge budget eta too small (e.g., 0.1) (ablation) | PrunE · OOD generalization | test performance | Hurt |
| Use PrunE instead of LIRS | GOODMotif size · GOODMotif size | accuracy: 74.51 -> 66.53 | Hurt |
Surprising findings
- Pruning spurious edges, rather than selecting invariant edges, retains more of the invariant subgraph in the case study, even though some spurious edges remain highly ranked.
Limitations
- Performance degrades on Motif-size where spurious substructures are larger and more numerous, as PrunE struggles to prune all spurious edges.
- Small eta (e.g., 0.1) may prune invariant edges, so the budget must be tuned within a reasonable range.
- Not applicable directly to node-level OOD tasks, per the paper.
Experimental setup
Datasets: GOODMotif GOODHIV EC50 OGBG-Molbbbp
Benchmarks: GOODMotif GOODHIV EC50 OGBG-Molbbbp
Metrics: accuracy ROC-AUC
Baselines: ERM IRM GroupDRO VREx DropEdge G-Mixup FLAG LiSA DIR DisC CAL GREA
Builds on: GSAT CIGA AIA Gumbel-Softmax
Closest papers by meaning
- Subgraph Aggregation for Out-of-Distribution Generalization on Graphs (AAAI 2025 · similarity 0.92)
- Disentangled Graph Self-supervised Learning for Out-of-Distribution Generalization (ICML 2024 · similarity 0.90)
- Graph Structure Extrapolation for Out-of-Distribution Generalization (ICML 2024 · similarity 0.89)
- GOODAT: Towards Test-Time Graph Out-of-Distribution Detection (AAAI 2024 · similarity 0.89)
- Disentangling Invariant Subgraph via Variance Contrastive Estimation under Distribution Shifts (ICML 2025 · similarity 0.89)
- GDeR: Safeguarding Efficiency, Balancing, and Robustness via Prototypical Graph Pruning (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.