Certainty in Uncertainty: Reasoning over Uncertain Knowledge Graphs with Statistical Guarantees

• URL: http://arxiv.org/abs/2510.24754v1
• Date: Sat, 18 Oct 2025 17:58:17 GMT
• Title: Certainty in Uncertainty: Reasoning over Uncertain Knowledge Graphs with Statistical Guarantees
• Authors: Yuqicheng Zhu, Jingcheng Wu, Yizhen Wang, Hongkuan Zhou, Jiaoyan Chen, Evgeny Kharlamov, Steffen Staab,
• Abstract summary: textscUnKGCP generates prediction intervals guaranteed to contain the true score with a user-specified level of confidence.<n>We provide theoretical guarantees for the intervals and empirically verify these guarantees.<n>Experiments on standard benchmarks across diverse UnKGE methods further demonstrate that the intervals are sharp and effectively capture predictive uncertainty.
• Score: 24.48143253497661
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Uncertain knowledge graph embedding (UnKGE) methods learn vector representations that capture both structural and uncertainty information to predict scores of unseen triples. However, existing methods produce only point estimates, without quantifying predictive uncertainty-limiting their reliability in high-stakes applications where understanding confidence in predictions is crucial. To address this limitation, we propose \textsc{UnKGCP}, a framework that generates prediction intervals guaranteed to contain the true score with a user-specified level of confidence. The length of the intervals reflects the model's predictive uncertainty. \textsc{UnKGCP} builds on the conformal prediction framework but introduces a novel nonconformity measure tailored to UnKGE methods and an efficient procedure for interval construction. We provide theoretical guarantees for the intervals and empirically verify these guarantees. Extensive experiments on standard benchmarks across diverse UnKGE methods further demonstrate that the intervals are sharp and effectively capture predictive uncertainty.

Related papers

• Uncertainty Quantification for Named Entity Recognition via Full-Sequence and Subsequence Conformal Prediction [0.0]
  We introduce a general framework for adapting sequence-labeling-based NER models to produce uncertainty-aware prediction sets.<n>Prediction sets are collections of full-sentence labelings guaranteed to contain the correct labeling with a user-specified confidence level.
  arXiv  Detail & Related papers  (2026-01-13T18:00:08Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• SConU: Selective Conformal Uncertainty in Large Language Models [59.25881667640868]
  We propose a novel approach termed Selective Conformal Uncertainty (SConU)<n>We develop two conformal p-values that are instrumental in determining whether a given sample deviates from the uncertainty distribution of the calibration set at a specific manageable risk level.<n>Our approach not only facilitates rigorous management of miscoverage rates across both single-domain and interdisciplinary contexts, but also enhances the efficiency of predictions.
  arXiv  Detail & Related papers  (2025-04-19T03:01:45Z)
• Relational Conformal Prediction for Correlated Time Series [56.59852921638328]
  We address the problem of uncertainty quantification in time series by exploiting correlated sequences.<n>We propose a novel distribution-free approach based on conformal prediction framework and quantile regression.<n>Our approach provides accurate coverage and achieves state-of-the-art uncertainty quantification in relevant benchmarks.
  arXiv  Detail & Related papers  (2025-02-13T16:12:17Z)
• Generative Conformal Prediction with Vectorized Non-Conformity Scores [6.059745771017814]
  Conformal prediction provides model-agnostic uncertainty quantification with guaranteed coverage.<n>We propose a generative conformal prediction framework with vectorized non-conformity scores.<n>We construct adaptive uncertainty sets using density-ranked uncertainty balls.
  arXiv  Detail & Related papers  (2024-10-17T16:37:03Z)
• Beyond Uncertainty Quantification: Learning Uncertainty for Trust-Informed Neural Network Decisions - A Case Study in COVID-19 Classification [7.383605511698832]
  Reliable uncertainty quantification is critical in high-stakes applications, such as medical diagnosis.<n>Traditional uncertainty quantification methods rely on a predefined confidence threshold to classify predictions as confident or uncertain.<n>This approach assumes that predictions exceeding the threshold are trustworthy, while those below it are uncertain, without explicitly assessing the correctness of high-confidence predictions.<n>This study proposes an uncertainty-aware stacked neural network, which extends conventional uncertainty quantification by learning when predictions should be trusted.
  arXiv  Detail & Related papers  (2024-09-19T04:20:12Z)
• Robust Conformal Prediction Using Privileged Information [17.886554223172517]
  We develop a method to generate prediction sets with a guaranteed coverage rate that is robust to corruptions in the training data.<n>Our approach builds on conformal prediction, a powerful framework to construct prediction sets that are valid under the i.i.d assumption.
  arXiv  Detail & Related papers  (2024-06-08T08:56:47Z)
• Revisiting Confidence Estimation: Towards Reliable Failure Prediction [53.79160907725975]
  We find a general, widely existing but actually-neglected phenomenon that most confidence estimation methods are harmful for detecting misclassification errors. We propose to enlarge the confidence gap by finding flat minima, which yields state-of-the-art failure prediction performance.
  arXiv  Detail & Related papers  (2024-03-05T11:44:14Z)
• Score Matching-based Pseudolikelihood Estimation of Neural Marked Spatio-Temporal Point Process with Uncertainty Quantification [59.81904428056924]
  We introduce SMASH: a Score MAtching estimator for learning markedPs with uncertainty quantification. Specifically, our framework adopts a normalization-free objective by estimating the pseudolikelihood of markedPs through score-matching. The superior performance of our proposed framework is demonstrated through extensive experiments in both event prediction and uncertainty quantification.
  arXiv  Detail & Related papers  (2023-10-25T02:37:51Z)
• Learning Uncertainty For Safety-Oriented Semantic Segmentation In Autonomous Driving [77.39239190539871]
  We show how uncertainty estimation can be leveraged to enable safety critical image segmentation in autonomous driving. We introduce a new uncertainty measure based on disagreeing predictions as measured by a dissimilarity function. We show experimentally that our proposed approach is much less computationally intensive at inference time than competing methods.
  arXiv  Detail & Related papers  (2021-05-28T09:23:05Z)

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.