Non-exchangeable Conformal Prediction for Temporal Graph Neural Networks

• URL: http://arxiv.org/abs/2507.02151v1
• Date: Wed, 02 Jul 2025 21:15:00 GMT
• Title: Non-exchangeable Conformal Prediction for Temporal Graph Neural Networks
• Authors: Tuo Wang, Jian Kang, Yujun Yan, Adithya Kulkarni, Dawei Zhou,
• Abstract summary: Conformal prediction for graph neural networks (GNNs) offers a promising framework for quantifying uncertainty.<n>Existing methods predominantly focus on static graphs, neglecting the evolving nature of real-world graphs.<n>We introduce NCPNET, a novel end-to-end conformal prediction framework tailored for temporal graphs.
• Score: 11.01716974299811
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Residual Reweighted Conformal Prediction for Graph Neural Networks [14.329186221388087]
  Graph Neural Networks (GNNs) excel at modeling data but face significant challenges in high-stakes domains due to unquantified uncertainty.<n>We propose Residual Reweighted GNN (RR-GNN), a framework designed to generate minimal prediction sets with provable marginal coverage guarantees.<n>RR-GNN achieves improved efficiency over state-of-the-art methods, with no loss of coverage.
  arXiv  Detail & Related papers  (2025-06-09T15:19:17Z)
• Topology-Aware Conformal Prediction for Stream Networks [54.505880918607296]
  We propose Spatio-Temporal Adaptive Conformal Inference (textttCISTA), a novel framework that integrates network topology and temporal dynamics into the conformal prediction framework.<n>Our results show that textttCISTA effectively balances prediction efficiency and coverage, outperforming existing conformal prediction methods for stream networks.
  arXiv  Detail & Related papers  (2025-03-06T21:21:15Z)
• Predict Confidently, Predict Right: Abstention in Dynamic Graph Learning [6.0497759658090775]
  We propose a reject option strategy within the framework of temporal graph neural networks (GNNs) for continuous-time dynamic graphs.<n>This allows the model to strategically abstain from making predictions when the uncertainty is high and confidence is low.<n>We show the effectiveness of our approach in improving the reliability and area under the curve (AUC)/ average precision (AP) scores for predictions in dynamic graph scenarios.
  arXiv  Detail & Related papers  (2025-01-14T19:27:58Z)
• Conformalized Link Prediction on Graph Neural Networks [8.807684750444626]
  Graph Neural Networks (GNNs) excel in diverse tasks, yet their applications in high-stakes domains are often hampered by unreliable predictions. We introduce a distribution-free and model-agnostic uncertainty quantification approach to construct a predictive interval with a statistical guarantee for GNN-based link prediction.
  arXiv  Detail & Related papers  (2024-06-26T21:17:37Z)
• DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment [57.62885438406724]
  Graph neural networks are recognized for their strong performance across various applications. BP has limitations that challenge its biological plausibility and affect the efficiency, scalability and parallelism of training neural networks for graph-based tasks. We propose DFA-GNN, a novel forward learning framework tailored for GNNs with a case study of semi-supervised learning.
  arXiv  Detail & Related papers  (2024-06-04T07:24:51Z)
• Conditional Shift-Robust Conformal Prediction for Graph Neural Network [0.0]
  Graph Neural Networks (GNNs) have emerged as potent tools for predicting outcomes in graph-structured data.<n>Despite their efficacy, GNNs have limited ability to provide robust uncertainty estimates.<n>We propose Conditional Shift Robust (CondSR) conformal prediction for GNNs.
  arXiv  Detail & Related papers  (2024-05-20T11:47:31Z)
• Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagation [80.227864832092]
  Graph neural networks (GNNs) have exhibited exceptional efficacy in a diverse array of applications. The sheer size of large-scale graphs presents a significant challenge to real-time inference with GNNs. We propose an online propagation framework and two novel node-adaptive propagation methods.
  arXiv  Detail & Related papers  (2023-10-17T05:03:00Z)
• Uncertainty Quantification over Graph with Conformalized Graph Neural Networks [52.20904874696597]
  Graph Neural Networks (GNNs) are powerful machine learning prediction models on graph-structured data. GNNs lack rigorous uncertainty estimates, limiting their reliable deployment in settings where the cost of errors is significant. We propose conformalized GNN (CF-GNN), extending conformal prediction (CP) to graph-based models for guaranteed uncertainty estimates.
  arXiv  Detail & Related papers  (2023-05-23T21:38:23Z)
• Dynamic Causal Explanation Based Diffusion-Variational Graph Neural Network for Spatio-temporal Forecasting [60.03169701753824]
  We propose a novel Dynamic Diffusion-al Graph Neural Network (DVGNN) fortemporal forecasting. The proposed DVGNN model outperforms state-of-the-art approaches and achieves outstanding Root Mean Squared Error result.
  arXiv  Detail & Related papers  (2023-05-16T11:38:19Z)
• Efficient Graph Neural Network Inference at Large Scale [54.89457550773165]
  Graph neural networks (GNNs) have demonstrated excellent performance in a wide range of applications. Existing scalable GNNs leverage linear propagation to preprocess the features and accelerate the training and inference procedure. We propose a novel adaptive propagation order approach that generates the personalized propagation order for each node based on its topological information.
  arXiv  Detail & Related papers  (2022-11-01T14:38:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.