Non-exchangeable Conformal Prediction for Temporal Graph Neural Networks Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.

Tuo Wang, Jian Kang, Yujun Yan, Adithya Kulkarni, Dawei Zhou · 2025

Read Non-exchangeable Conformal Prediction for Temporal Graph Neural Networks Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. by Tuo Wang, Jian Kang, Yujun Yan, Adithya Kulkarni, Dawei Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-02151.txt.

Introduction

Tuo Wang and co-authors work on trust in graph-based AI in this 2025 paper. Conformal prediction gives a model a way to say how sure it is, with a firm guarantee. Most versions assume data points can be swapped freely, which fails for graphs that change over time. The team builds a version made for time-changing graphs.

Their method, NCPNET, scores oddness in a way that tracks both graph shape and time drift. A leaner training method keeps the cost down and cuts coverage slips. On four real data sets, the method kept its coverage promise. Its answer sets were up to about a third smaller on one set. Smaller sets with firm guarantees help in fraud checks and other high-stakes tasks.

Catalog record

CREATORTuo Wang, Jian Kang, Yujun Yan, Adithya Kulkarni, Dawei Zhou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-02151

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Non-exchangeable Conformal Prediction for Temporal Graph Neural Networks Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 3–7, 2025; Toronto, ON, Canada Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’25), August 3–7, 2025, Toronto, ON, Canada DOI: 10.1145/3711896.3737064 ISBN: 979-8-4007-1454-2/2025/08 CCS: Computing methodologies Supervised learning Tuo Wang, Jian Kang, Yujun Yan, Adithya Kulkarni, Dawei Zhou Abstract . 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 . 1. Introduction Graph Neural Networks (GNNs) have become integral to a wide range of real-world applications, including financial fraud detection ( Wang et al. 2019 ) , traffic forecasting ( Guo et al. 2019 ) , and pharmaceutical discovery ( Vignac et al. 2022 ) . In high-stakes domains like these, quantifying uncertainty in model predictions is essential, as it enables human oversight when the model encounters uncertain predictions, thereby mitigating potential risks and ensuring more reliable decision-making. To achieve robust uncertainty quantification, researchers have explored various approaches, including Bayesian-based ( Wu et al. 2021 ) , Frequentist-based ( Kan et al. 2022 ) , and conformal prediction (CP) methods ( Vovk et al. 2005 ) . Among these, CP stands out as a promising approach due to its distribution-free characteristics and ability to provide rigorous statistical guarantees on the confidence level of predictions. Unlike Bayesian or Frequentist approaches, which often rely on specific assumptions about data distributions, CP offers a flexible, theoretically grounded framework that ensures the ground truth label is included in the predicted set with a predefined level of confidence. A fundamental assumption in conformal prediction (CP) is the exchangeability condition 1 1 1 Exchangeability definition: for any z_{1},\dots,z_{n+1} and any permutation \pi of {1,\dots,n+1} , it holds that \mathbbm{P}((Z_{\pi(1)},\dots,Z_{\pi(n+1)})=(z_{1},\dots,z_{n+1}))=\mathbbm{P}((Z_{1},\dots,Z_{n+1})=(z_{1},\dots,z_{n+1})) . , which relaxes the independent and identically distributed (i.i.d.) assumption. This assumption generally holds in domains such as computer vision ( Kampffmeyer et al. 2016 ) and natural language processing ( Xiao and Wang 2019 ) because data samples are often independent of each other, making the application of CP relatively straightforward. However, in graph-based learning, data points such as nodes and edges are inherently interconnected, leading to dependencies that violate the i.i.d. assumption and, consequently, the exchangeability condition. This violation creates significant challenges when applying CP to graphs. Recent works ( H. Zargarbashi et al. 2023 ; Huang et al. 2023 ) have addressed this issue for static graphs by leveraging the fact that many graph neural network architectures are permutation equivariant. This means that the structure of the graph remains unchanged under node reordering. This property allows CP to be adapted to static graphs while preserving exchangeability, as illustrated in Fig. 1(a) . Although conformal prediction has been successfully extended to static graphs, many real-world systems evolve and are represented as chronological sequences of timestamped transactions, also known as temporal edges ( Zhang et al. 2022 ) . A temporal dimension introduces fundamental challenges to the permutation equivariant properties established for static graphs, leading to a violation of exchangeability. This violation occurs because each sample in a temporal graph may follow a unique distribution influenced by temporal dependencies in graph structures, node attributes, and prediction labels. As a result, the probability of selecting different calibration sets becomes unequal, breaking the exchangeability condition. Additionally, the training process of a temporal graph inherently depends on temporal ordering, meaning that the sequence in which samples are observed directly impacts the outcomes of temporal GNNs. As illustrated in Fig. 1(b) , calibration and test sets in temporal graphs exhibit a complex relationship driven by continuity and transformation. These dependencies introduce persistent correlations and gradual shifts in the distribution of graph structures, node attributes, and ground truth labels, further complicating the application of conformal prediction. (a) Static Graphs (b) Temporal Graphs Figure 1 . Illustration of non-exchangeability in temporal graphs, where the shapes of nodes indicate the class memberships and the colors of nodes indicate the assignments in training set, validation set, calibration set, and test set. Figure 1 (a) shows the exchangeability between the calibration set and test set in the static graphs. Figure 1 (b) shows the non-exchangeability between the calibration set and test set on the temporal graphs. Existing solutions for addressing non-exchangeability in temporal graphs focus on either proving exchangeability through transformations or using weighted quantile adjustments. ( Davis et al. 2024 ) preserves exchangeability by unfolding GNNs under a stochastic block model, but this relies on a stationary stochastic process, which rarely holds in real-world temporal graphs ( Liao et al. 2019 ) . In the time-series domain, ( Barber et al. 2023 ) proposes a non-exchangeability theory that quantifies the coverage gap and emphasizes optimized weighted quantiles to mitigate non-exchangeability. While insightful, this approach is designed for time-series data and lacks a direct method for optimizing performance in temporal graphs. In this paper, we propose NCPNet , a novel conformal prediction framework for temporal graphs. We begin by proving that the exchangeability condition is violated in temporal graphs, then develop a theory that quantifies the coverage gap between exchangeable and non-exchangeable settings. Our analysis shows that weighted quantiles and non-conformity measurements primarily drive this discrepancy. Building on these insights, we introduce NCPNet , a CP algorithm designed for temporal graphs that calibrates temporal GNNs by minimizing deviations from predefined coverage. NCPNet consists of two key components: (M1) A topological and temporal non-conformity score that improves uncertainty quantification in temporal graphs, and (M2) An efficiency-aware optimization algorithm that enhances computational efficiency and reduces the coverage gap. Our main contributions are summarized below. \bullet Challenges in Temporal Conformal Prediction. We identify the challenge of non-exchangeability in applying conformal prediction to temporal graphs and formally define the conformal prediction problem in this setting. We provide theoretical proofs demonstrating that a predefined coverage level can still be guaranteed despite temporal dependencies. \bullet Theoretical Grounding and Algorithm Design. We develop a theoretical analysis quantifying the coverage gap between exchangeable and non-exchangeable conditions in temporal graphs. Our analysis reveals that weighted quantiles and non-conformity measurements influence this gap. Based on these insights, we introduce NCPNet

Read the complete text