# Non-exchangeable Conformal Prediction for Temporal Graph Neural Networks

arXiv: https://arxiv.org/abs/2507.02151 · HTML: https://mlsanity.com/paper/2507.02151/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 42 references that are in the map.
- First posted on arXiv 2 Jul 2025.

## Builds on (most cited first, 24 of 24)

- [MLP-Mixer: An all-MLP Architecture for Vision](https://mlsanity.com/paper/2105.01601/) (2021)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks](https://mlsanity.com/paper/1908.01207/) (2019)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [A Semi-supervised Graph Attentive Network for Financial Fraud Detection](https://mlsanity.com/paper/2003.01171/) (2020)
- [Do We Really Need Complicated Model Architectures For Temporal Networks?](https://mlsanity.com/paper/2302.11636/) (2023)
- [S2-MLP: Spatial-Shift MLP Architecture for Vision](https://mlsanity.com/paper/2106.07477/) (2021)
- [Quantifying Uncertainties in Natural Language Processing Tasks](https://mlsanity.com/paper/1811.07253/) (2018)
- [Fair Conformal Predictors for Applications in Medical Imaging](https://mlsanity.com/paper/2109.04392/) (2021)
- [Improving Expert Predictions with Conformal Prediction](https://mlsanity.com/paper/2201.12006/) (2022)
- [Conformal Prediction Under Feedback Covariate Shift for Biomolecular Design](https://mlsanity.com/paper/2202.03613/) (2022)
- [Quantifying Uncertainty in Deep Spatiotemporal Forecasting](https://mlsanity.com/paper/2105.11982/) (2021)
- [Distribution Free Prediction Sets for Node Classification](https://mlsanity.com/paper/2211.14555/) (2022)
- [EvoluNet: Advancing Dynamic Non-IID Transfer Learning on Graphs](https://mlsanity.com/paper/2305.00664/) (2023)
- [Valid Conformal Prediction for Dynamic GNNs](https://mlsanity.com/paper/2405.19230/) (2024)
- [Leveraging Static Models for Link Prediction in Temporal Knowledge Graphs](https://mlsanity.com/paper/2106.15223/) (2021)
- [Developing a Temporal Bibliographic Data Set for Entity Resolution](https://mlsanity.com/paper/1806.07524/) (2018)

## Built on by (most cited first, 3 of 3)

- [Delving into Non-Exchangeability for Conformal Prediction in Graph-Structured Multivariate Time Series](https://mlsanity.com/paper/2605.04957/) (2026)
- [Temporal Graph Prototype-conditioned Conformal Prediction for Fraud Detection](https://mlsanity.com/paper/2608.15768/) (2026)
- [Learning to Adapt and Calibrate: Score Distribution Alignment for Few-Shot Uncertainty Prediction in Medical VLMs](https://mlsanity.com/paper/2609.10333/) (2026)

## Abstract (arXiv)

Conformal prediction for graph neural networks (GNNs) offers a promising framework for quantifying uncertainty, enhancing GNN reliability in high-stakes applications. However, existing methods predominantly focus on static graphs, neglecting the evolving nature of real-world graphs. Temporal dependencies in graph structure, node attributes, and ground truth labels violate the fundamental exchangeability assumption of standard conformal prediction methods, limiting their applicability. To address these challenges, in this paper, we introduce NCPNET, a novel end-to-end conformal prediction framework tailored for temporal graphs. Our approach extends conformal prediction to dynamic settings, mitigating statistical coverage violations induced by temporal dependencies. To achieve this, we propose a diffusion-based non-conformity score that captures both topological and temporal uncertainties within evolving networks. Additionally, we develop an efficiency-aware optimization algorithm that improves the conformal prediction process, enhancing computational efficiency and reducing coverage violations. Extensive experiments on diverse real-world temporal graphs, including WIKI, REDDIT, DBLP, and IBM Anti-Money Laundering dataset, demonstrate NCPNET's capability to ensure guaranteed coverage in temporal graphs, achieving up to a 31% reduction in prediction set size on the WIKI dataset, significantly improving efficiency compared to state-of-the-art methods. Our data and code are available at https://github.com/ODYSSEYWT/NCPNET.