Research map / Graph learning / GNN architectures
Conformal Inductive Graph Neural Networks
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.
Adapts conformal prediction to inductive node classification on node- and edge-exchangeable graph sequences by recomputing calibration scores on the current subgraph (NodeEx CP) and using degree-weighted quantiles (EdgeEx CP), recovering 1-alpha coverage at any prediction time.
Problem
Conformal prediction guarantees break in inductive node classification because message passing with newly arriving nodes and edges shifts conformity scores of calibration nodes, so calibration and test scores are no longer exchangeable.
Approach
Under node-exchangeability, the effect of newly arriving nodes is symmetric across calibration and evaluation nodes, so recomputing calibration scores conditional on the current subgraph at each timestep restores exchangeability; under edge-exchangeability, the sequence decomposes into weighted node-exchangeable subsequences with weights 1/deg(v), enabling weighted CP.
Key results
- On node-exchangeable sequences with GCN, NodeEx CP deviates from 90% target by 0.039-1.254% across seven datasets versus 2.689-6.373% for naive CP.
- On edge-exchangeable sequences, EdgeEx CP deviates by 0.335-3.024% versus 3.460-7.835% for naive CP.
- NodeEx CP yields smaller prediction sets and higher singleton hit ratios than naive CP on CiteSeer with GCN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Recompute calibration scores conditional on the current graph instead of using pre-arrival scores | Naive CP on Cora-ML · Node-exchangeable sequence | absolute deviation from coverage guarantee (%): 5.860 -> 0.280 | Helped |
| Recompute calibration scores conditional on the current graph instead of using pre-arrival scores | Naive CP on PubMed · Node-exchangeable sequence | absolute deviation from coverage guarantee (%): 4.649 -> 1.254 | Helped |
| Recompute calibration scores conditional on the current graph instead of using pre-arrival scores | Naive CP on CiteSeer · Node-exchangeable sequence | absolute deviation from coverage guarantee (%): 4.150 -> 0.039 | Helped |
| Recompute calibration scores conditional on the current graph instead of using pre-arrival scores | Naive CP on Coauth-CS · Node-exchangeable sequence | absolute deviation from coverage guarantee (%): 4.082 -> 0.397 | Helped |
| Recompute calibration scores conditional on the current graph instead of using pre-arrival scores | Naive CP on Coauth-Phy. · Node-exchangeable sequence | absolute deviation from coverage guarantee (%): 2.689 -> 0.555 | Helped |
| Recompute calibration scores conditional on the current graph instead of using pre-arrival scores | Naive CP on Amz-Comp. · Node-exchangeable sequence | absolute deviation from coverage guarantee (%): 6.373 -> 0.263 | Helped |
| Recompute calibration scores conditional on the current graph instead of using pre-arrival scores | Naive CP on Amz-Photo · Node-exchangeable sequence | absolute deviation from coverage guarantee (%): 3.483 -> 0.127 | Helped |
| Use degree weights when computing the conditional calibration quantile | NodeEx CP on Cora-ML · Edge-exchangeable sequence | absolute deviation from coverage guarantee (%): 3.883 -> 1.929 | Helped |
| Use degree weights when computing the conditional calibration quantile | NodeEx CP on PubMed · Edge-exchangeable sequence | absolute deviation from coverage guarantee (%): 3.405 -> 1.241 | Helped |
| Use degree weights when computing the conditional calibration quantile | NodeEx CP on CiteSeer · Edge-exchangeable sequence | absolute deviation from coverage guarantee (%): 1.572 -> 0.335 | Helped |
| Use degree weights when computing the conditional calibration quantile | NodeEx CP on Coauth-CS · Edge-exchangeable sequence | absolute deviation from coverage guarantee (%): 4.662 -> 3.024 | Helped |
| Use degree weights when computing the conditional calibration quantile | NodeEx CP on Coauth-Phy. · Edge-exchangeable sequence | absolute deviation from coverage guarantee (%): 4.378 -> 2.240 | Helped |
Surprising findings
- Naive CP over-covers under homophily, so higher empirical coverage can look better but results in larger set sizes and is invalid.
- NAPS leaves a notable proportion of test nodes without any calibration neighbors on sparse graphs, making it largely inapplicable.
Limitations
- Guarantee is marginal rather than conditional on features or labels.
- Real-world graphs may not satisfy node- or edge-exchangeability; the guarantee is invalid under adversarial choice of evaluation timesteps.
- Empirical results rely on sampling from existing datasets treated as exchangeable sequences.
Experimental setup
Datasets: CoraML CiteSeer PubMed Coauthor CS Coauthor Physics Amazon Computers Amazon Photos Flickr Reddit2
Benchmarks: CoraML CiteSeer PubMed Coauthor CS Coauthor Physics Amazon Computers Amazon Photos Flickr Reddit2
Metrics: absolute deviation from 90% coverage average set size singleton hit ratio
Baselines: Naive CP NAPS TPS DAPS
Builds on: conformal prediction adaptive prediction sets weighted conformal prediction beyond exchangeability
Closest papers by meaning
- Valid Conformal Prediction for Dynamic GNNs (ICLR 2025 · similarity 0.86)
- Conformal Structured Prediction (ICLR 2025 · similarity 0.85)
- Optimal transport-based conformal prediction (ICML 2025 · similarity 0.85)
- Similarity-Navigated Conformal Prediction for Graph Neural Networks (NeurIPS 2024 · similarity 0.84)
- GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs (NeurIPS 2026 · similarity 0.84)
- Verifiably Robust Conformal Prediction (NeurIPS 2024 · similarity 0.84)
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.