Uncertainty Quantification over Graph with Conformalized Graph Neural Networks

• URL: http://arxiv.org/abs/2305.14535v2
• Date: Mon, 30 Oct 2023 18:10:30 GMT
• Title: Uncertainty Quantification over Graph with Conformalized Graph Neural Networks
• Authors: Kexin Huang, Ying Jin, Emmanuel Cand\`es, Jure Leskovec
• Abstract summary: 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.
• Score: 52.20904874696597
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) are powerful machine learning prediction models on graph-structured data. However, 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. Given an entity in the graph, CF-GNN produces a prediction set/interval that provably contains the true label with pre-defined coverage probability (e.g. 90%). We establish a permutation invariance condition that enables the validity of CP on graph data and provide an exact characterization of the test-time coverage. Moreover, besides valid coverage, it is crucial to reduce the prediction set size/interval length for practical use. We observe a key connection between non-conformity scores and network structures, which motivates us to develop a topology-aware output correction model that learns to update the prediction and produces more efficient prediction sets/intervals. Extensive experiments show that CF-GNN achieves any pre-defined target marginal coverage while significantly reducing the prediction set/interval size by up to 74% over the baselines. It also empirically achieves satisfactory conditional coverage over various raw and network features.

Related papers

• Positional Encoder Graph Quantile Neural Networks for Geographic Data [4.277516034244117]
  We introduce the Positional Graph Quantile Neural Network (PE-GQNN), a novel method that integrates PE-GNNs, Quantile Neural Networks, and recalibration techniques in a fully nonparametric framework. Experiments on benchmark datasets demonstrate that PE-GQNN significantly outperforms existing state-of-the-art methods in both predictive accuracy and uncertainty quantification.
  arXiv  Detail & Related papers  (2024-09-27T16:02:12Z)
• RoCP-GNN: Robust Conformal Prediction for Graph Neural Networks in Node-Classification [0.0]
  Graph Neural Networks (GNNs) have emerged as powerful tools for predicting outcomes in graph-structured data. One way to address this issue is by providing prediction sets that contain the true label with a predefined probability margin. We propose a novel approach termed Robust Conformal Prediction for GNNs (RoCP-GNN) Our approach robustly predicts outcomes with any predictive GNN model while quantifying the uncertainty in predictions within the realm of graph-based semi-supervised learning (SSL)
  arXiv  Detail & Related papers  (2024-08-25T12:51:19Z)
• 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)
• 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. Despite their efficacy, GNNs have limited ability to provide robust uncertainty estimates. We propose Conditional Shift Robust (CondSR) conformal prediction for GNNs.
  arXiv  Detail & Related papers  (2024-05-20T11:47:31Z)
• Uncertainty in Graph Neural Networks: A Survey [50.63474656037679]
  Graph Neural Networks (GNNs) have been extensively used in various real-world applications. However, the predictive uncertainty of GNNs stemming from diverse sources can lead to unstable and erroneous predictions. This survey aims to provide a comprehensive overview of the GNNs from the perspective of uncertainty.
  arXiv  Detail & Related papers  (2024-03-11T21:54:52Z)
• GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels [81.93520935479984]
  We study a new problem, GNN model evaluation, that aims to assess the performance of a specific GNN model trained on labeled and observed graphs. We propose a two-stage GNN model evaluation framework, including (1) DiscGraph set construction and (2) GNNEvaluator training and inference. Under the effective training supervision from the DiscGraph set, GNNEvaluator learns to precisely estimate node classification accuracy of the to-be-evaluated GNN model.
  arXiv  Detail & Related papers  (2023-10-23T05:51:59Z)
• Distribution Free Prediction Sets for Node Classification [0.0]
  We leverage recent advances in conformal prediction to construct prediction sets for node classification in inductive learning scenarios. We show through experiments on standard benchmark datasets using popular GNN models that our approach provides tighter and better prediction sets than a naive application of conformal prediction.
  arXiv  Detail & Related papers  (2022-11-26T12:54:45Z)
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
  Graph Neural Networks (GNNs) are proposed without considering the distribution shifts between training and testing graphs. In such a setting, GNNs tend to exploit subtle statistical correlations existing in the training set for predictions, even though it is a spurious correlation. We propose a general causal representation framework, called StableGNN, to eliminate the impact of spurious correlations.
  arXiv  Detail & Related papers  (2021-11-20T18:57:18Z)
• A Biased Graph Neural Network Sampler with Near-Optimal Regret [57.70126763759996]
  Graph neural networks (GNN) have emerged as a vehicle for applying deep network architectures to graph and relational data. In this paper, we build upon existing work and treat GNN neighbor sampling as a multi-armed bandit problem. We introduce a newly-designed reward function that introduces some degree of bias designed to reduce variance and avoid unstable, possibly-unbounded payouts.
  arXiv  Detail & Related papers  (2021-03-01T15:55:58Z)
• Unlabelled Data Improves Bayesian Uncertainty Calibration under Covariate Shift [100.52588638477862]
  We develop an approximate Bayesian inference scheme based on posterior regularisation. We demonstrate the utility of our method in the context of transferring prognostic models of prostate cancer across globally diverse populations.
  arXiv  Detail & Related papers  (2020-06-26T13:50:19Z)

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.