Research map / Graph learning / Graph self-supervised learning
Revisiting Score Propagation in Graph Out-of-Distribution Detection
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.
Analyzes when post-hoc OOD score propagation helps graph OOD node detection and proposes GRASP, an edge augmentation on a selected training subset that boosts intra-edge ratio, with theoretical guarantees and experiments on 10 datasets.
Problem
OOD node detection on graphs, where naive OOD score propagation along edges can hurt performance when ID-to-OOD (inter) edges dominate.
Approach
Derives conditions (intra-edge ratio vs. inter-edge ratio) under which score propagation helps, and adds edges from a selected subset of training nodes that have more edges to confidently-ID test nodes than to confidently-OOD test nodes, so propagation is improved; the method is post hoc and works with existing OOD scores.
Key results
- GRASP reaches average FPR95 of 29.70 on Cora vs 54.71 for GNNSafe with GCN backbone (AUROC 93.50 vs 87.52).
- On large-scale benchmarks GRASP achieves average FPR95 49.96 vs 89.98 for GNNSafe and AUROC 84.73 average.
- Ablation: selecting top 50% training nodes by h(i) gives average AUROC 85.19 vs 81.19 for random 50% and 77.84 for low 50%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply GRASP score propagation rather than GNNSafe | GCN graph OOD detection · Common benchmarks (average) | FPR95: 17.87% | Helped |
| Apply GRASP score propagation rather than the strongest baseline | GCN graph OOD detection · Large-scale benchmarks (average) | FPR95: 32.21% | Helped |
| Use top 50% of training nodes ranked by h(i), rather than random selection (ablation) | GRASP · Common benchmarks (average) | AUROC: 81.19 -> 85.19 | Helped |
| Use top 50% of training nodes ranked by h(i), rather than the lowest 50% (ablation) | GRASP · Common benchmarks (average) | AUROC: 77.84 -> 85.19 | Helped |
| Choose augmentation nodes using h(i), rather than GAug without h(i) (ablation) | GRASP · Common benchmarks (average) | AUROC: 68.50 -> 85.19 | Helped |
| Augment selected training nodes rather than selected test ID/OOD nodes (ablation) | GRASP · Common benchmarks (average) | AUROC: 65.85 -> 85.19 | Helped |
| Add GRASP augmentation before propagation rather than use naive MSP propagation | MSP graph OOD scoring · Chameleon | AUROC: 50.35 -> 76.93 | Helped |
| Add GRASP augmentation before propagation rather than use naive MSP propagation | MSP graph OOD scoring · Squirrel | AUROC: 36.21 -> 61.09 | Helped |
| Use naive score propagation instead of raw MSP scores | Graph OOD detection on heterophily benchmarks · Chameleon and Squirrel | AUROC: 57.96 -> 50.35; 48.51 -> 36.21 | Hurt |
| Increase intra-edge ratio by augmenting the graph | Graph OOD detection · Common and large-scale benchmarks | AUROC: 87.52 -> 93.50; 31.99 -> 98.50 | Mixed |
Surprising findings
- Naive OOD score propagation can be harmful: on Cora-like or heterophilous graphs, propagation lowers AUROC (e.g., Squirrel MSP 48.51 vs MSP+prop 36.21 AUROC).
- Directly adding edges to test-set ID/OOD subsets (TestAug) performs worse than random selection, attributed to confirmation bias.
Limitations
- Theoretical results rely on a Bernoulli edge model and are informal in the main text; the formal guarantees are for A rather than normalized adjacency.
- Requires selecting ID/OOD test subsets via MSP percentiles, which depends on the quality of the base classifier's confidence.
Experimental setup
Datasets: Cora Amazon-Photo Coauthor-CS Chameleon Squirrel Reddit2 ogbn-products ArXiv-year Snap-patents Wiki
Benchmarks: Cora Amazon-Photo Coauthor-CS Chameleon Squirrel Reddit2 ogbn-products ArXiv-year Snap-patents Wiki
Metrics: AUROC FPR95
Baselines: MSP Energy KNN ODIN Mahalanobis GKDE GPN OODGAT GNNSafe fDBD NODESafe
Builds on: GNNSafe maximum softmax probability GAug
Closest papers by meaning
- Graph Out-of-Distribution Detection Goes Neighborhood Shaping (ICML 2024 · similarity 0.92)
- Bounded and Uniform Energy-based Out-of-distribution Detection for Graphs (ICML 2024 · similarity 0.90)
- GOLD: Graph Out-of-Distribution Detection via Implicit Adversarial Latent Generation (ICLR 2025 · similarity 0.90)
- Bridging OOD Detection and Generalization: A Graph-Theoretic View (NeurIPS 2024 · similarity 0.89)
- GOODAT: Towards Test-Time Graph Out-of-Distribution Detection (AAAI 2024 · similarity 0.89)
- Structural Entropy Guided Unsupervised Graph Out-Of-Distribution Detection (AAAI 2025 · 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.