Conformal Inductive Graph Neural Networks

• URL: http://arxiv.org/abs/2407.09173v1
• Date: Fri, 12 Jul 2024 11:12:49 GMT
• Title: Conformal Inductive Graph Neural Networks
• Authors: Soroush H. Zargarbashi, Aleksandar Bojchevski,
• Abstract summary: Conformal prediction (CP) transforms any model's output into prediction sets guaranteed to include (cover) the true label. CP requires exchangeability, a relaxation of the i.i.d. assumption, to obtain a valid distribution-free coverage guarantee. conventional CP cannot be applied in inductive settings due to the implicit shift in the (calibration) scores caused by message passing with the new nodes. We prove that the guarantee holds independently of the prediction time, e.g. upon arrival of a new node/edge or at any subsequent moment.
• Score: 58.450154976190795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Conformal prediction (CP) transforms any model's output into prediction sets guaranteed to include (cover) the true label. CP requires exchangeability, a relaxation of the i.i.d. assumption, to obtain a valid distribution-free coverage guarantee. This makes it directly applicable to transductive node-classification. However, conventional CP cannot be applied in inductive settings due to the implicit shift in the (calibration) scores caused by message passing with the new nodes. We fix this issue for both cases of node and edge-exchangeable graphs, recovering the standard coverage guarantee without sacrificing statistical efficiency. We further prove that the guarantee holds independently of the prediction time, e.g. upon arrival of a new node/edge or at any subsequent moment.

Related papers

• Online scalable Gaussian processes with conformal prediction for guaranteed coverage [32.21093722162573]
  The consistency of the resulting uncertainty values hinges on the premise that the learning function conforms to the properties specified by the GP model. We propose to wed the GP with the prevailing conformal prediction (CP), a distribution-free post-processing framework that produces it prediction sets with a provably valid coverage.
  arXiv  Detail & Related papers  (2024-10-07T19:22:15Z)
• Robust Yet Efficient Conformal Prediction Sets [53.78604391939934]
  Conformal prediction (CP) can convert any model's output into prediction sets guaranteed to include the true label. We derive provably robust sets by bounding the worst-case change in conformity scores.
  arXiv  Detail & Related papers  (2024-07-12T10:59:44Z)
• Similarity-Navigated Conformal Prediction for Graph Neural Networks [6.318857043484474]
  We propose a novel algorithm named Similarity-Navigated Adaptive Prediction Sets (SNAPS) SNAPS aggregates the non-conformity scores based on feature similarity and structural neighborhood. It can generate compact prediction sets and increase the singleton hit ratio.
  arXiv  Detail & Related papers  (2024-05-23T08:23:22Z)
• Predicting generalization performance with correctness discriminators [64.00420578048855]
  We present a novel model that establishes upper and lower bounds on the accuracy, without requiring gold labels for the unseen data. We show across a variety of tagging, parsing, and semantic parsing tasks that the gold accuracy is reliably between the predicted upper and lower bounds.
  arXiv  Detail & Related papers  (2023-11-15T22:43:42Z)
• 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)
• A Graph Is More Than Its Nodes: Towards Structured Uncertainty-Aware Learning on Graphs [49.76175970328538]
  We propose novel edgewise metrics, namely the edgewise expected calibration error (ECE) and the agree/disagree ECEs, which provide criteria for uncertainty estimation on graphs beyond the nodewise setting. Our experiments demonstrate that the proposed edgewise metrics can complement the nodewise results and yield additional insights.
  arXiv  Detail & Related papers  (2022-10-27T16:12:58Z)
• Approximate Conditional Coverage via Neural Model Approximations [0.030458514384586396]
  We analyze a data-driven procedure for obtaining empirically reliable approximate conditional coverage. We demonstrate the potential for substantial (and otherwise unknowable) under-coverage with split-conformal alternatives with marginal coverage guarantees.
  arXiv  Detail & Related papers  (2022-05-28T02:59:05Z)
• Distribution-free uncertainty quantification for classification under label shift [105.27463615756733]
  We focus on uncertainty quantification (UQ) for classification problems via two avenues. We first argue that label shift hurts UQ, by showing degradation in coverage and calibration. We examine these techniques theoretically in a distribution-free framework and demonstrate their excellent practical performance.
  arXiv  Detail & Related papers  (2021-03-04T20:51:03Z)

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.