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

arXiv: https://arxiv.org/abs/2510.24754 · HTML: https://mlsanity.com/paper/2510.24754/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 18 Oct 2025.

## Builds on (most cited first, 13 of 13)

- [ConceptNet 5.5: An Open Multilingual Graph of General Knowledge](https://mlsanity.com/paper/1612.03975/) (2016)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Conformal Prediction for Natural Language Processing: A Survey](https://mlsanity.com/paper/2405.01976/) (2024)
- [iDECODe: In-distribution Equivariance for Conformal Out-of-distribution Detection](https://mlsanity.com/paper/2201.02331/) (2022)
- [Embedding Uncertain Knowledge Graphs](https://mlsanity.com/paper/1811.10667/) (2018)
- [Probabilistic Box Embeddings for Uncertain Knowledge Graph Reasoning](https://mlsanity.com/paper/2104.04597/) (2021)
- [Probability Calibration for Knowledge Graph Embedding Models](https://mlsanity.com/paper/1912.10000/) (2019)
- [MultiADS: Defect-aware Supervision for Multi-type Anomaly Detection and Segmentation in Zero-Shot Learning](https://mlsanity.com/paper/2504.06740/) (2025)
- [Predictive Multiplicity of Knowledge Graph Embeddings in Link Prediction](https://mlsanity.com/paper/2408.08226/) (2024)
- [Predicting the Road Ahead: A Knowledge Graph based Foundation Model for Scene Understanding in Autonomous Driving](https://mlsanity.com/paper/2503.18730/) (2025)

## Built on by (most cited first, 9 of 9)

- [Conformal Graph Prediction with Z-Gromov-Wasserstein Distances](https://mlsanity.com/paper/2603.02460/) (2026)
- [Conformal Path Reasoning: Trustworthy Knowledge Graph Question Answering via Path-Level Calibration](https://mlsanity.com/paper/2605.08077/) (2026)
- [Scalable Uncertainty Reasoning in Knowledge Graphs](https://mlsanity.com/paper/2605.16568/) (2026)
- [Conformalized Large Language Models under Configuration Shift](https://mlsanity.com/paper/2608.01460/) (2026)
- [Towards Foundation Models for Relational Databases with Language Models and Graph Neural Networks](https://mlsanity.com/paper/2605.16085/) (2026)
- [Leveraging Graph Structure in Seq2Seq Models for Knowledge Graph Link Prediction](https://mlsanity.com/paper/2605.18211/) (2026)
- [ProbSPARQL: Querying Knowledge Graphs with Multi-dimensional, Uncertain Numeric Data](https://mlsanity.com/paper/2607.18262/) (2026)
- [SCAIR: Schema-Conditioned Agentic Iterative Reasoning for Enterprise Knowledge Graphs](https://mlsanity.com/paper/2607.22571/) (2026)
- [Propagating construction-time knowledge quality into medical question answering: A framework grounded in clinical guidelines](https://mlsanity.com/paper/2608.28360/) (2026)

## Abstract (arXiv)

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 textscUnKGCP, 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. textscUnKGCP 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.