Research map / Graph learning / GNN architectures
Valid Conformal Prediction for Dynamic GNNs
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 unfolded (dilated tensor unfolding) graph representations fed to standard GCN/GAT so that split conformal prediction yields valid sets for dynamic graphs in transductive and semi-inductive regimes.
Problem
Uncertainty quantification with conformal prediction for node label prediction on dynamic graphs, where block-diagonal GNN embeddings are not exchangeable over time (temporal shift), leading to invalid or large prediction sets in the semi-inductive regime.
Approach
Represent the dynamic graph as a dilated unfolding (column-concatenated adjacency matrices in a square symmetric block matrix) and feed it to an unmodified permutation-equivariant GNN; under joint exchangeability and equivariance, split conformal prediction is valid even when the test point is fixed in time, while the transductive regime needs no assumptions.
Key results
- In the semi-inductive regime UGCN reaches 0.915 accuracy on School versus 0.116 for block GCN, and maintains valid coverage (0.924) where block GCN has 0.812 coverage.
- UGNNs achieve valid marginal coverage in all semi-inductive examples except Trade (drift), where block GNNs fail to cover in every semi-inductive example.
- On School semi-inductive, UGCN set size is 3.037 versus 8.079 for block GCN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the block-diagonal representation with unfolding for GCN | GCN · SBM, semi-inductive | accuracy: 0.334 $\pm$ 0.024 -> 0.985 $\pm$ 0.003 | Helped |
| Replace the block-diagonal representation with unfolding for GCN | GCN · School, semi-inductive | accuracy: 0.116 $\pm$ 0.011 -> 0.915 $\pm$ 0.013 | Helped |
| Replace the block-diagonal representation with unfolding for GCN | GCN · Flight, semi-inductive | accuracy: 0.121 $\pm$ 0.059 -> 0.477 $\pm$ 0.061 | Helped |
| Replace the block-diagonal representation with unfolding for GCN | GCN · Trade, transductive | accuracy: 0.095 $\pm$ 0.017 -> 0.082 $\pm$ 0.031 | Hurt |
| Replace the block-diagonal representation with unfolding for GCN | GCN conformal prediction · Flight, semi-inductive | coverage: 0.853 $\pm$ 0.013 -> 0.910 $\pm$ 0.003 | Helped |
| Replace the block-diagonal representation with unfolding for GCN | GCN conformal prediction · Trade, semi-inductive | coverage: 0.842 $\pm$ 0.015 -> 0.847 $\pm$ 0.017 | No clear effect |
| Replace the block-diagonal representation with unfolding for GCN | GCN conformal prediction · School, semi-inductive | prediction set size: 8.079 $\pm$ 0.188 -> 3.037 $\pm$ 0.251 | Helped |
Surprising findings
- Block diagonal GNNs are close to random guessing in the semi-inductive School and SBM examples, despite being valid in the transductive regime.
- Even block GNNs achieve valid coverage in the transductive regime, which the theory says needs no exchangeability, but time-conditional coverage fails for most methods due to drift.
Limitations
- Semi-inductive coverage fails under drift, as in the Trade dataset, where edge counts roughly double over time.
- Time-conditional coverage is not achieved in general because no two time points are exactly exchangeable.
- Unfolding doubles computational cost and cannot use typical memory-saving tricks for mega-scale graphs.
Experimental setup
Datasets: SBM (simulated) School (primary school contact network) Flight (OpenSky) Trade (UN agricultural trade, Temporal Graph Benchmark)
Benchmarks: SBM School Flight Trade
Metrics: accuracy marginal coverage prediction set size time-conditional coverage
Baselines: Block diagonal GCN Block diagonal GAT
Builds on: Adaptive Prediction Sets Graph Convolutional Networks Graph Attention Networks dilated unfolding of tensors
Closest papers by meaning
- When Graph Neural Networks Meet Dynamic Mode Decomposition (ICLR 2025 · similarity 0.89)
- Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks (ICLR 2024 · similarity 0.88)
- A Graph Dynamics Prior for Relational Inference (AAAI 2024 · similarity 0.88)
- Enhancing Trustworthiness of Graph Neural Networks with Rank-Based Conformal Training (AAAI 2025 · similarity 0.88)
- Towards Dynamic Message Passing on Graphs (NeurIPS 2024 · similarity 0.87)
- GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs (NeurIPS 2026 · similarity 0.87)
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.