Research map / Graph learning / GNN architectures
Uncertainty Estimation on Graphs with Structure Informed Stochastic Partial Differential Equations
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 SISPDE, a graph neural ODE whose noise is spatially correlated via a Matérn Gaussian-process kernel (SPDE-driven message passing), for OOD detection on graphs with varying label informativeness.
Problem
Uncertainty estimation on graphs under distribution shift is hard when label informativeness is low, because standard GNN uncertainty models assume neighboring nodes share similar uncertainty.
Approach
Replace the i.i.d./Laplacian-correlated Q-Wiener noise in graph SPDE message passing with a Matérn-kernel-correlated noise process (Φ-Wiener process), whose smoothness parameter ν controls long-range uncertainty correlations, implemented as a graph neural ODE with Chebyshev approximation of the kernel.
Key results
- SISPDE achieves best or second-best result in 71 of 72 OOD-detection comparisons (50 best, 21 runner-up) across label, structure, and feature shifts.
- On Cora under label leave-out, SISPDE reports AUC 96.85 and FPR95 10.87 versus GNSD's 95.75 and 19.76.
- Rewiring graphs by thresholding the Matérn covariance raises GCN OOD performance on low-LI datasets such as Roman Empire and Minesweeper.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use SISPDE instead of GNSD | graph OOD detection · OOD detection across eight graph datasets and three shift types | best-or-second-best results: 71 of 72 results | Helped |
| use SISPDE instead of GNSD | graph OOD detection · high label-informativeness datasets | cases with better performance: 26 of the 27 cases | Helped |
| use SISPDE instead of GNSD | graph OOD detection · low label-informativeness datasets | cases with better performance: 45 of the 45 | Helped |
| replace the RBF kernel with the flexible Matérn kernel (ablation) | SISPDE · Cora, label shift | AUC: 95.22 \pm 0.54 -> 96.85 \pm 0.68 | Helped |
| rewire with the Matérn covariance kernel | GCN · Minesweeper, label shift | AUC: 53.97 -> 59.64 | Helped |
| rewire with the Matérn covariance kernel | GCN · Tolokers, label shift | AUC: 48.73 -> 64.91 | Helped |
| rewire with the Matérn covariance kernel | GCN · Questions, label shift | AUC: 44.43 -> 56.56 | Helped |
| rewire with the Matérn covariance kernel | GCN · Roman Empire, label shift | AUC: 53.15 -> 64.53 | Helped |
| use a lower kernel smoothness parameter ν (ablation) | SISPDE · low label-informativeness graph datasets | OOD detection performance | Helped |
| use SISPDE instead of the strongest listed baseline | graph OOD detection · Citeseer, label shift | AUC: 94.20 \pm 4.52 vs 85.43 \pm 0.80 | Hurt |
| use SISPDE instead of the strongest listed baseline | graph OOD detection · Minesweeper, label shift | AUC: 66.46 \pm 0.46 vs 64.77 \pm 1.60 | Hurt |
| use SISPDE instead of the strongest listed baseline | graph OOD detection · Tolokers, label shift | AUC: 71.02 \pm 0.70 vs 68.40 \pm 1.67 | Hurt |
Surprising findings
- Models without graph structure (OE, ODIN) can outperform graph-based SOTA models such as GNNSafe and GNSD on low label informativeness datasets.
Limitations
- Theoretical results (e.g., Theorem 2 requiring nu > d and Weyl-law arguments) are only sketched for compact domains and do not directly match the graph setting.
- Scalability to larger graphs is listed as future work.
- Some baselines (e.g., GEBM) show high variance across runs.
Experimental setup
Datasets: Cora Citeseer Pubmed Roman Empire Amazon-Ratings Minesweeper Tolokers Questions
Benchmarks: Cora Citeseer Pubmed Roman Empire Amazon-Ratings Minesweeper Tolokers Questions
Metrics: AUC DET-ACC FPR95
Baselines: GCN ODIN MSP Mahalanobis OE GNNSafe GOLD GEBM GNSD SISPDE-RBF
Builds on: GRAND GNSD Matérn Gaussian process on graphs GREAD GNNSafe
Closest papers by meaning
- Uncertainty Modeling in Graph Neural Networks via Stochastic Differential Equations (ICLR 2025 · similarity 0.93)
- Graph Neural Stochastic Diffusion for Estimating Uncertainty in Node Classification (ICML 2024 · similarity 0.93)
- A Unified Uncertainty Representation for Graph Neural Networks via Doubly-Spectral Stochastic Expansion (NeurIPS 2026 · similarity 0.91)
- Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks (ICLR 2024 · similarity 0.90)
- Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory (ICML 2025 · similarity 0.89)
- Energy-based Epistemic Uncertainty for Graph Neural Networks (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.