PaperlayerView exact revision on arXiv

Source-linked AI summary

Uncertainty in Representation Learning on Knowledge Graphs

Yuqicheng Zhu

arXiv:2610.06974v1cs.LG

TL;DR

KGE predictions can lack principled reliability guarantees despite strong benchmark performance. This thesis addresses algorithmic, predictive, and knowledge uncertainty with voting, conformal intervals, and embedding-based probabilistic inference; it reports reduced disagreement, valid query-adaptive intervals, and sound SEL point estimates when embedding loss is zero.

  • Problem

    KGE methods can perform strongly on benchmarks yet lack principled reliability guarantees, limiting responsible use in high-stakes settings.

    Source: ZUSAMMENFASSUNG · p. 5

  • Method

    The thesis combines voting over KGE rankings, conformal intervals for confidence-scored triples, and embedding-based probabilistic inference over statistical ontologies.

    Source: §3.1 · p. 72, §6.7 · p. 143, §7.10 · p. 169

  • Results

    Up to 39% of test queries receive conflicting predictions across training configurations; UnKGCP produces valid, sharp, query-adaptive intervals, and SEL point estimates are sound when embedding loss is zero.

    Source: §3.1 · p. 72, §6.7 · p. 143, §7.10 · p. 169

  • Takeaways & Limitations

    For SEL inference, the known embedding error provides a practical quality indicator because inference error increases proportionally with it.

    Source: §7.10 · p. 169

    Evaluation uses academic benchmarks, and conformal coverage assumes calibration and test data are i.i.d. or exchangeable; transfer to real-world KGs remains open.

    Source: §8.2 · p. 173

Abstract

from arXiv · show

Knowledge graph embedding (KGE) methods represent entities and predicates in continuous vector spaces to infer missing knowledge. Despite strong benchmark performance, their predictions often lack principled reliability guarantees, limiting their use in high-stakes applications. Moreover, uncertainty arises throughout the KGE pipeline, from incomplete or probabilistic input knowledge to stochastic training and prediction. This thesis systematically investigates three sources of uncertainty in KGE: knowledge uncertainty, arising from incomplete, noisy, or probabilistic input knowledge; algorithmic uncertainty, induced by randomness in model training; and predictive uncertainty, concerning the reliability of model outputs. To address algorithmic uncertainty, the thesis demonstrates that models trained under identical settings can produce substantially different predictions and introduces a voting-based aggregation framework to mitigate this instability. To quantify predictive uncertainty, it adapts conformal prediction to KGE, constructing answer sets with distribution-free coverage guarantees and extending them to provide predicate-conditional reliability guarantees. To support reasoning under knowledge uncertainty, it develops statistically valid prediction intervals for confidence-scored triples and an embedding-based approach to approximate probabilistic reasoning over statistical ontologies with formal soundness guarantees. Together, these complementary, model-agnostic methods provide a practical and theoretically grounded approach to uncertainty in KGE, advancing beyond predictive accuracy toward reliable and uncertainty-aware knowledge graph reasoning.

1.1 contributions

The section examines uncertainty in knowledge-graph reasoning, outlining ontology- and rule-based approaches and motivating embedding-based representations in light of challenges posed by uncertainty, pattern complexity, and machine-learning integration. It presents methods addressing uncertainty across the KGE pipeline, including aggregation, conformal prediction, and embedding-based reasoning with reliability guarantees.

1.1 contributions

  • Different random seeds cause conflicting top-K predictions for up to 39% of test queries despite overall accuracy differences below 1%; voting-based aggregation combines models to improve inference reliability.The study quantifies predictive multiplicity across six representative KGE methods and introduces an aggregation framework inspired by social choice theory.Source: §1.1 · p. 30
  • KGCP constructs answer sets with user-specified, distribution-free coverage guarantees, with set size reflecting query difficulty or ambiguity.Easy queries yield smaller sets, while difficult or ambiguous queries yield larger ones.Source: §1.1 · pp. 30–31
  • CondKGCP extends marginal KGCP coverage to predicate-conditional guarantees by grouping predicates with similar representations and incorporating rank information into calibration.Source: §1.1 · p. 31
  • UnKGCP produces confidence-level prediction intervals for triple confidence scores, using a UnKGE-specific nonconformity measure and an efficient construction procedure.Interval length reflects predictive uncertainty.Source: §1.1 · p. 31
  • BoxSEL represents concepts as geometric boxes for approximate probabilistic reasoning in Statistical EL, enabling linear-time inference with formal soundness and runtime guarantees.The embeddings preserve ontological structure and statistical proportions.Source: §1.1 · p. 32

2.2.1 Ontology-based Reasoning

2.2.2 Rule-based Reasoning

  • Rule-based reasoning applies Horn clauses to graph facts, deriving consequences through forward chaining to a fixpoint or backward chaining from a query.Datalog reasoners and rule engines implement these strategies.Source: Rule-based Reasoning over a KG · p. 44

2.2.3 From Symbolic to Statistical Representations

2.3 knowledge graph embeddings

This section introduces knowledge graph embedding methods, covering how entities and predicates are represented, how triples are scored and models trained, and the settings used to evaluate them. It describes link prediction and triple classification, including ranking metrics, filtered evaluation, and predicate-specific threshold tuning.

2.3.1 Embedding Mapping

  • Embedding spaces range from efficient Euclidean vectors to non-Euclidean manifolds for hierarchical or cyclic structure and probability distributions for uncertainty.Hyperbolic embeddings model hierarchical relations, spherical embeddings capture cyclic or transitive patterns, and Gaussian embeddings represent entities with means and covariance matrices.Source: §2.3.1 · p. 48

2.3.2 Triple Scoring

  • KGE scoring functions assign plausibility scores to triples and distinguish models through translation, bilinear interaction, or learned nonlinear operations.Examples include TransE and RotatE, RESCAL, DistMult and ComplEx, and ConvE; these families trade off expressivity, relational-pattern capacity, and computational cost.Source: §2.3.2 · pp. 48–49, Translation-based Scoring · p. 49, Bilinear Scoring · p. 49

2.3.3 Embedding Training

  • Training optimizes embeddings to score positive triples above negative ones, using margin-ranking or cross-entropy losses with different gradient behavior.Margin ranking encourages a score gap of at least γ and then has zero loss when that margin is reached; cross-entropy continues to provide nonzero gradients for all scores.Source: KGE Model · pp. 52–53, Figure 2.1 · p. 52
  • Because absent triples are not confirmed false under the Open World Assumption, training synthesizes negatives through uniform corruption, type-constrained sampling, or model-weighted hard-negative sampling.Uniform corruption can yield trivial negatives, while predicate domain and range constraints produce harder candidates and self-adversarial sampling favors corruptions the model already finds plausible.Source: KGE Model · pp. 53–54

2.3.4 Evaluation

  • Evaluation uses train, validation, and test splits, with this thesis adopting a transductive setting in which validation and test entities and predicates appear during training.Benchmarks include cleaned WN18RR and FB15k-237 to reduce inverse-relation leakage, as well as Wikidata5M for inductive link prediction involving unseen entities.Source: Datasets · p. 56
  • Link prediction ranks candidate entities by triple plausibility and evaluates correct-entity rank using MR, MRR, and Hits@K.MR averages correct-entity ranks, MRR averages reciprocal ranks, and Hits@K measures the share of queries with the correct entity in the top K.Source: Evaluation Metrics · pp. 57–58
  • The filtered setting removes other true matching triples from the ranking pool to avoid unfairly penalizing a prediction.Source: Evaluation Metrics · p. 58
  • Head and tail prediction share a triple-scoring notation, with head prediction represented by reversing the relation and swapping the entities.The passage notes that asymmetric models may still assign different scores depending on prediction direction.Source: Evaluation Metrics · p. 58
  • Triple classification compares each test triple’s plausibility score with a threshold, typically tuned on validation data to optimize accuracy per predicate.Accuracy is evaluated from true positives, true negatives, false positives, and false negatives on the test set.Source: Evaluation Metrics · pp. 58–59

2.4 uncertainty in knowledge graph embedding

Uncertainty arises at different stages of knowledge graph embedding and affects model trustworthiness. The thesis organizes it around uncertain input knowledge, stochastic training, and the reliability of predictions, rather than the aleatoric–epistemic dichotomy.

2.4.1 Knowledge Uncertainty

  • Knowledge uncertainty attaches to triples and axioms, with scores interpreted either as long-run frequencies or as beliefs given available information.Temporal uncertainty and predicate ambiguity are identified as relevant input uncertainties beyond the thesis’s scope.Source: §2.4.1 · pp. 59–61
  • Existing embedding methods for triple-level uncertainty provide point estimates without formal guarantees, while the thesis proposes statistically guaranteed methods for triples and approximate reasoning over statistical ontologies.Earlier statistical relational learning can be difficult to scale because grounding rules creates large probabilistic models and exact inference is intractable.Source: Reasoning under Knowledge Uncertainty · p. 62

2.4.2 Algorithmic Uncertainty

  • Algorithmic uncertainty is run-to-run variation from stochastic training; equally performing KGE models can disagree, motivating predictive-multiplicity analysis and voting-based mitigation.The thesis studies disagreement among similarly performing models and proposes methods to reduce this uncertainty.Source: Algorithmic Uncertainty in KGE · p. 65

2.4.3 Predictive Uncertainty

  • Predictive uncertainty concerns the reliability of a fixed trained model’s outputs, which KGE methods often leave unquantified; conformal prediction is adapted to provide statistical guarantees.Existing calibration approaches depend on high-quality negative examples and do not formally guarantee validity.Source: §2.4.3 · p. 65, Predictive Uncertainty in KGE · p. 67

2.4.4 Beyond the Aleatoric–Epistemic Dichotomy

  • The thesis rejects the aleatoric–epistemic split because its definitions vary, its components can be entangled, and it maps ambiguously to KGE’s pipeline stages.Instead, it categorizes uncertainty by where it arises in the KGE pipeline.Source: Limitations of the Aleatoric–Epistemic… · p. 68

3.1 introduction

KGE models trained with different random seeds can make conflicting link predictions despite comparable performance. The chapter measures predictive multiplicity and uses voting-based ranking aggregation, reducing conflicting predictions across test queries.

3.1 introduction

  • Random initialization, positive-sample order, and negative sampling can lead the same graph to embeddings with comparable link-prediction performance but conflicting predictions for individual queries.Such conflicts are also reported in medical, drug-discovery, and financial applications.Source: §3.1 · pp. 71–72
  • Two models with identical training configurations each achieve 50% overall accuracy yet recommend entirely different top-ranked suppliers.The figure illustrates the supplier-selection disagreement between models trained with different random seeds.Source: §3.1 · p. 71, Figure 3.1 · p. 72
  • Up to 39% of test queries receive conflicting predictions across training configurations, while voting-based aggregation reduces conflicts by 66% to 78%.The method aggregates individual model rankings using voting methods from social choice theory.Source: §3.1 · p. 72

3.2 predictive multiplicity of kge

This section formalizes and measures predictive multiplicity among similarly accurate KGE models and evaluates voting-based ranking aggregation as a way to reduce it. It reports substantial model disagreement, reductions in multiplicity through voting—stronger with more models—and a negative correlation between multiplicity and entity/relation frequency.

3.2 predictive multiplicity of kge

  • Predictive multiplicity occurs when a model within an ϵ-level set—models within tolerance of the best validation performer—disagrees with the baseline on a test triple’s top-K outcome.Disagreement is defined by whether models agree on ranking the test triple within the top-K predictions for its query.Source: §3.2 · p. 73

3.3.1 Ambiguity and Discrepancy

  • The discrepancy bound links multiplicity to baseline Hits@K: lower baseline accuracy permits greater multiplicity, and worst-case attainability requires complementary errors on non-overlapping test subsets.Observed empirical discrepancy was substantially below the bound because competing models often shared correct and incorrect predictions.Source: §3.3.1 · pp. 74–75

3.3.2 Empirical Ambiguity and Discrepancy

  • Because enumerating the full ϵ-level set is infeasible, the empirical measures use sampled competing models trained with the baseline configuration and different random seeds.The baseline is selected through 60 hyperparameter-search trials, and the sample is capped at 10 competing models that meet the validation-performance tolerance.Source: §3.3.2 · p. 75

3.3.3 Predictive Multiplicity of KGE Models

  • With ϵ = 0.01, competing models assigned conflicting top-K predictions to 8%–39% of test queries, showing multiplicity was measurable across six methods and two benchmarks.The analysis focused on recommendation-style link prediction; the authors report consistent conclusions in query-answering settings.Source: Table 3.1 · p. 76, §3.3.3 · pp. 76–77

3.4 alleviating predictive multiplicity

  • Voting-based aggregation combines candidate-entity rankings from similarly performing KGE models to reduce variability from individual training runs.The section adapts voting methods from social choice theory to produce a consensus ranking.Source: §3.4 · p. 77

3.4.1 Social Choice Theory

  • For KGE link prediction, each model trained with a different random seed acts as a voter, and candidate entities are ranked according to model plausibility scores.The goal is a consensus ranking that is less sensitive to randomness in any individual training run.Source: §3.4.1 · p. 78

3.4.2 Ranking Aggregation using Voting Methods

  • Majority and Borda voting aggregate ordinal candidate positions, whereas adapted range voting uses plausibility scores transformed to [−1, 1].The methods sum voting scores to re-rank candidate entities.Source: §3.4.2 · p. 79

3.4.3 Evaluation After Voting-Based Aggregation

  • Range voting matched or exceeded baseline accuracy and reduced empirical ambiguity by 66%–78% and discrepancy by 64%–76%.All voting methods reduced multiplicity; majority voting substantially lowered Hits@K, while Borda voting kept accuracy close to baseline. As ϵ grew, ambiguity and discrepancy increased; aggregation reduced both across ϵ values, and conflicting predictions persisted even at ϵ = 0.Source: Overall Results · pp. 80–81, Predictive Multiplicity wrt. Error… · p. 81, Table 3.5 · p. 82
  • An exhaustive study across values of ϵ was feasible only on the small Nations KG, with 14 entities and 56 relations, because each setting required tens of KGE trainings.The authors state that this study was impractical on larger KGs given their computational budget.Source: Predictive Multiplicity wrt. Error… · p. 82
  • Using more models for ranking aggregation more strongly alleviates predictive multiplicity, while even a small ensemble yields substantial improvement without notably changing Hits@K.Figure 3.3 shows RESCAL on FB15k237; additional results are reported in Appendix B.3.Source: Predictive Multiplicity wrt. Number of… · p. 83, Figure 3.3 · p. 83
  • Entity/relation frequency has a significant negative correlation with predictive multiplicity metrics, and range voting weakens this correlation.The analysis uses Spearman’s coefficient across six KGE methods and entity/relation-specific subsets of all datasets; the authors suggest range voting may help queries with higher uncertainty.Source: Table 3.6 · p. 83, Predictive Multiplicity wrt.… · p. 84

3.5 influential factors of predictive multiplicity

The discussion relates predictive multiplicity to model expressiveness and inference patterns, then turns to conformal prediction as a way to quantify uncertainty in individual KGE outputs. It describes voting aggregation’s benefits and costs alongside the coverage, efficiency, and adaptiveness goals of conformal predictors.

3.5.1 Expressiveness and Inference Patterns

  • Greater expressiveness and the inference patterns captured by a model are proposed as structural factors that may shape predictive multiplicity.More expressive models allow more embeddings that fit the training graph; capturing relevant inference patterns is expected to reduce conflicts.Source: §3.5.1 · p. 84

3.5.2 Empirical Observations

  • Competing models show fewer conflicts on WN18 and FB15k than on WN18RR and FB15k237; TransE on FB15k237 is an outlier associated with symmetric relations.The thesis relates the dataset trend to inverse-relation patterns and the TransE outlier to TransE’s inability to represent symmetric pairs and capture symmetric patterns.Source: Figure 3.4 · p. 85, §3.5.2 · p. 85

3.7 conclusion and discussion

  • Across six representative KGE methods and benchmark datasets, substantial fractions of test queries receive conflicting top-K predictions from equally accurate models.The chapter defines predictive multiplicity and introduces empirical ambiguity and empirical discrepancy to measure it.Source: §3.7 · p. 86
  • Voting-based ranking aggregation, particularly range voting, substantially reduces empirical ambiguity and discrepancy while preserving or improving accuracy.The analysis also examines variation with error tolerance, aggregation-set size, and entity or relation frequency.Source: §3.7 · pp. 86–87
  • Voting aggregation requires training multiple models from scratch, and its consensus ranking does not quantify individual predictions’ confidence.The thesis identifies training-phase consistency methods and more memory-efficient voting as future directions, and motivates prediction-level uncertainty quantification.Source: Limitations · p. 87

4.1 introduction

  • Existing score-calibration techniques lack formal probabilistic guarantees and are sensitive to the calibration set, motivating conformal prediction for KGE.The thesis adapts conformal prediction to KGE outputs and evaluates practical issues including computational efficiency and calibration-set size.Source: §4.1 · p. 90

4.2.1 Confidence Predictor

  • A confidence predictor returns a prediction set at a desired confidence level, with validity, efficiency, and conditionality as its key quality goals.Efficiency concerns smaller, informative sets without sacrificing validity; conditionality concerns set size adapting to example difficulty.Source: §4.2.1 · p. 91, Validity · p. 91, Efficiency · p. 92

4.2.2 Conformal Predictor

  • Conformal prediction uses nonconformity scores to form prediction sets and guarantees conservative validity when calibration and test examples are exchangeable.The supplied theorem also states asymptotic exact validity.Source: §4.2.2 · pp. 93–94

4.3 kge-based answer set prediction

The section reframes KGE prediction as constructing compact answer sets that represent uncertainty, then adapts conformal prediction to provide coverage guarantees with computationally tractable calibration.

4.3.1 Task Definition

  • KGE answer-set prediction seeks sets that include the true answer at a target confidence level, remain as small as possible, and grow for harder queries.This replaces the conventional goal of producing a full ranking of candidate entities.Source: §4.3.1 · p. 94

4.3.2 Confidence Predictors for KGE Models

  • Naive and Platt predictors rely on normalized plausibility scores as probabilities, while TopK uses a globally calibrated fixed set size and cannot adapt to query difficulty.TopK can also be viewed as a conformal predictor using rank position as its nonconformity score.Source: §4.3.3 · p. 96, TopK Confidence Predictor · p. 96

4.3.3 Conformal Predictors for KGE Models

  • Conformal predictors use nonconformity scores to construct answer sets; NegScore uses raw plausibility, Minmax normalizes within each query, and Softmax uses relative score differences.The score is intended to quantify how unusual a candidate triple is; the choice affects how well it captures data structure.Source: Nonconformity Measures · pp. 97–98
  • Inductive conformal prediction splits training triples into proper-training and calibration sets, reuses one trained KGE model, and yields conservative validity under exchangeability.With no ties among calibration scores, the answer set is asymptotically exactly valid.Source: Answer Set Construction · pp. 98–99
  • The finite-sample coverage guarantee requires exchangeable calibration and test examples, so it does not directly apply under distribution shifts such as temporal or predicate-stratified splits.Random partitions from the same sampling mechanism are presented as a reasonable working assumption for conventional KG benchmarks.Source: Answer Set Construction · p. 99
  • ICP avoids retraining for every candidate answer and has O(|E|) asymptotic complexity when calibration and test set sizes are small relative to the entity set.The earlier retraining approach would require a separate model for each candidate answer.Source: Answer Set Construction · p. 98, Time Complexity · p. 100

4.4 evaluation of answer set prediction

Across the evaluated KGE models and datasets, conformal predictors meet target coverage while producing compact, query-adaptive answer sets. The section also motivates predicate-conditional calibration because marginal coverage can conceal shortfalls for infrequent predicates.

4.4.1 Validity and Efficiency

  • Conformal predictors consistently match target empirical coverage and produce smaller answer sets than other methods that meet the coverage requirement.Naive prediction frequently misses validity, Platt scaling does not guarantee it, and TopK is valid but generally produces larger fixed-size sets.Source: Table 4.1 · p. 101, §4.4.1 · p. 102

4.4.2 Conditionality

  • Conformal answer-set size tracks query difficulty, supporting its use as an estimate of predictive uncertainty when the true answer is unknown.Difficulty is assessed by the rank of the true answer in the KGE model's ranking.Source: Figure 4.1 · p. 102, §4.4.2 · p. 103

4.4.3 Calibration Sample Efficiency

  • Even relatively small calibration sets produce answer-set quality close to that obtained with the full calibration set, while larger sets generally yield tighter sets.The reported coverage falls between α and α + 1/|Tcali| under the stated i.i.d. calibration condition.Source: §4.4.3 · p. 103, Table 4.2 · p. 104

4.4.4 Performance Across Confidence Levels

  • Across confidence levels, conformal predictors achieve the desired empirical coverage, and at high confidence levels they yield the most compact sets among the compared predictors.Answer-set size increases as α increases.Source: §4.4.4 · p. 104, Figure 4.2 · p. 105

4.5 related work

  • Prior KGE uncertainty work mainly used probabilistic representations or off-the-shelf calibration without systematic uncertainty evaluation or formal guarantees; the section presents conformal prediction as a new application to KGE.The cited prior calibration approaches are described as sensitive to the validation set and lacking formal guarantees.Source: §4.5 · pp. 104–106

4.6 conclusion and discussion

  • The chapter's answer sets quantify predictive uncertainty with coverage guarantees and can identify hard or uncertain queries; the method is compatible with KGE models and some other embedding approaches.The discussion notes a limitation: marginal validity does not ensure validity within query subgroups, motivating predicate-conditional guarantees.Source: §4.6 · p. 106

5.1 introduction

  • KGCP's marginal coverage can mask severe shortfalls for low-degree predicates, where a global calibration threshold may miscalibrate answer-set sizes.The passage reports some predicates below 0.2 coverage at α = 0.9 and links the most severe violations to low predicate degree.Source: §5.1 · p. 108, Figure 5.1 · p. 108
  • CondKGCP approximates predicate-conditional validity by merging structurally similar predicates and combining score- and rank-based calibration to limit set size without sacrificing coverage.The motivation is the long-tail distribution of predicates, which leaves many with few triples for calibration.Source: §5.1 · p. 109

5.3 conditional conformal predictors

The section reviews conditional conformal prediction strategies and introduces CondKGCP, which approximates predicate-conditional validity while keeping answer sets compact. CondKGCP merges predicates with sparse calibration data and combines score and rank calibration, with bounded coverage deviations and reduced set size under stated conditions.

5.3.1 Mondrian Conformal Predictor

  • Mondrian Conformal Prediction calibrates separately by predicate, but sparse predicate data can yield unstable thresholds, oversized sets, or invalid coverage.Most predicates have few triples, limiting calibration-set size.Source: §5.3.1 · pp. 110–111

5.3.2 Clustered Conformal Predictor

  • ClusterCP groups predicates using quantile-based embeddings of calibration-score distributions, but splitting calibration data can reduce its effectiveness for long-tail predicates.The calibration set is divided into clustering and proper calibration subsets.Source: §5.3.2 · pp. 111–112

5.3.3 Adaptive Conformal Predictor

  • APS changes the nonconformity score to reflect probability mass above each candidate, and RAPS adds rank regularization to discourage low-probability candidates.RAPS often reduces average set size relative to APS while maintaining similar coverage.Source: §5.3.3 · p. 112, §5.3.4 · p. 113

5.4 conditional knowledge graph conformal predictor

  • CondKGCP combines predicate merging with score- and rank-based calibration to approximate predicate-conditional validity while maintaining compact answer sets.Merging pools calibration triples for similar predicates; rank thresholding limits candidates before score calibration.Source: §5.4 · p. 114, §5.4.2 · p. 115

5.4.1 Predicate Merging.

  • Predicate merging places well-sampled predicates in separate groups and assigns sparse predicates to the most similar well-sampled group, aiming for reliable thresholds.The method uses negative Manhattan distance to retain directional and magnitude differences between predicate embeddings.Source: §5.4.1 · pp. 114–115

5.4.2 Dual Calibration Schema

  • Dual calibration first selects a rank cutoff and then applies score calibration among top-ranked candidates, balancing conditional coverage and set size.The parameter γ controls the trade-off: larger values favor stricter coverage guarantees, while smaller values favor smaller sets.Source: §5.4.2 · p. 115, Rank Calibration · p. 116, Score Calibration · p. 116

5.4.3 CondKGCP

  • Conditional coverage within each predicate group is bounded around the target, with deviations controlled by rank-calibration error and a finite-sample correction.Each group is constructed to contain at least ϕ calibration triples, bounding the finite-sample term by 1/(ϕ+1).Source: Validity and Size Reduction Guarantees · pp. 117–118
  • CondKGCP adds per-query sorting and filtering, while score computation remains the dominant runtime cost in the stated analysis.The dominant term is O(|E| · d); the authors illustrate the smaller overhead with |E| = 10^6 and d = 512.Source: Complexity Analysis · p. 119

5.5 evaluation of conditional conformal predictors

Across six KGE models and two datasets, CondKGCP generally offers a favorable balance between predicate-conditional coverage and answer-set size. Its performance persists across confidence levels, while higher coverage targets and hyperparameter choices expose trade-offs in set size and coverage.

5.5.1 Overall Comparison

  • CondKGCP has the most favorable coverage–size trade-off in most model–dataset cases, with coverage gaps closest to MCP and compact sets often closest in size to KGCP.MCP has the lowest CovGap but substantially larger sets, while KGCP has the lowest AveSize in most cases.Source: §5.5.1 · pp. 120–122, Table 5.1 · p. 121
  • ClusterCP often fails to improve on KGCP because it does not form meaningful groups under the highly imbalanced distribution of triples across predicates.APS and RAPS often generate large answer sets without significantly improving CovGap in these KGE experiments.Source: §5.5.1 · p. 122

5.5.2 Comparison across Different Confidence Levels

  • Across α = 0.8, 0.85, 0.9, and 0.95, CondKGCP keeps CovGap closest to MCP while maintaining AveSize comparable to KGCP.At α > 0.95, it retains superior conditional coverage and a more favorable coverage–size trade-off.Source: §5.5.2 · p. 122, Figure 5.2 · p. 123
  • Beyond α = 0.95, all methods show a sharp increase in answer-set size, which the authors attribute to base KGE models’ limitations in ranking correct answers highly.On WN18, most models attain Hits@10 close to 0.95; the authors note that higher-coverage applications need a highly accurate base model, such as one achieving Hits@K > 0.95.Source: §5.5.2 · pp. 122–123

5.5.3 Impact of Hyperparameters

  • Larger ϕ increases CovGap and reduces AveSize, while adjusting γ can substantially reduce AveSize with only negligible CovGap change when sacrificing some lower-bound coverage.The authors identify γ as necessary to CondKGCP’s design.Source: §5.5.3 · pp. 123–124

5.5.4 Impact of Key Components

  • The full CondKGCP has lower EF than both ablations; predicate merging reduces CovGap, while rank calibration keeps answer sets more compact.Compared with w/o Merge, it has lower CovGap at comparable AveSize; compared with w/o RankCal, it has slightly higher CovGap but smaller AveSize.Source: §5.5.4 · p. 124, Table 5.3 · p. 125

5.6 related work

  • Prior conditional conformal approaches discussed here target classification, whereas this work addresses KGE link prediction with many possible answers and imbalanced predicate frequencies.The related-work discussion covers modified nonconformity scores and subgroup-level calibration strategies.Source: §5.6 · p. 126

5.7 conclusion and discussion

  • The chapter concludes that CondKGCP approximates predicate-conditional validity with bounded deviations, and its evaluation supports practical effectiveness across six KGE methods and two datasets.The guarantees rely on exchangeability and on similarity of predicate embeddings corresponding to similarity of nonconformity-score distributions; future work could address covariate shift and incorporate predicate semantic features.Source: §5.7 · pp. 126–127

R E A S O N I N G U N D E R T R I P L E - L E V E L UNCERTAINTY

This section presents UnKGCP for quantifying uncertainty in confidence-scored triples in uncertain knowledge graphs. It constructs valid, sharp, query-adaptive prediction intervals and examines predictive variation that point-based accuracy metrics may miss.

6.1 introduction; 6.3 task definition

  • Confidence scores on uncertain-graph triples represent reliability, but existing UnKGE methods output point estimates without quantifying predictive uncertainty.Uncertain graphs capture noisy or probabilistic facts; reasoning predicts a test triple’s score, and uncertainty is represented by an interval intended to provide validity, efficiency, and conditionality.Source: §6.1 · pp. 129–130, §6.3 · p. 132

6.2.1 Scoring Function; 6.2.2 Learning Objective; 6.2.3 Negative Sampling

  • UnKGE models transform plausibility scores into confidence scores and train to approximate ground-truth scores, while negative triples require estimated rather than simply zero scores.Existing approaches differ in negative generation and scoring: uses probabilistic soft logic, whereas estimates negative scores through semi-supervised learning.Source: §6.2.1 · p. 131, §6.2.2 · p. 131, §6.2.3 · p. 132

6.4 uncertainty reasoning with validity guarantees; 6.4.1 Efficient Interval Construction

  • UnKGCP uses a fixed model trained on a proper-training split and calibration nonconformity scores to avoid retraining for every possible test confidence score.Under exchangeability of training quadruples and a test quadruple, its intervals are conservatively valid and asymptotically exactly valid; test-set complexity is asymptotically linear.Source: §6.4 · p. 133, §6.4.1 · pp. 133–134

6.4.2 Adaptive Nonconformity Measures

  • Entropy-normalized absolute residuals scale nonconformity by prediction entropy, allowing UnKGCP intervals to adapt to query difficulty while retaining conformal validity.Standard absolute residuals yield fixed-width intervals that do not adapt to individual query uncertainty.Source: §6.4.2 · p. 135, Non-Adaptive Conformal Predictor · p. 136

6.5.1 Experimental Settings

  • Experiments use CN15k, NL27k, and PPI5k with UKGE, PASSLEAF, and BEUrRE backbones, comparing UnKGCP against Fisher, quantile regression, and CP.Datasets use 85% training, 7% calibration, and 8% test splits; QR results are unavailable for PASSLEAF because it is not directly applicable to that semi-supervised framework.Source: §6.5.1 · p. 137, UnKGE Backbones · p. 137, Confidence Predictors · pp. 137–138

6.5.2 Validity and Efficiency

  • UnKGCP produces sharper intervals than CP in 7 of 9 configurations, with interval lengths also reflecting model performance across datasets.CP and UnKGCP closely match target coverage, while Fisher and QR often under-cover; Fisher assumes normally distributed residuals, and QR requires a well-specified conditional quantile model. Valid predictors’ interval lengths correlate with model performance: wider intervals accompany lower performance.Source: Table 6.2 · p. 138, §6.5.2 · p. 139, Table 6.3 · p. 139
  • UnKGCP achieves the best overall performance while satisfying validity and producing reasonably sharp intervals, with interval lengths increasing as confidence levels rise.Its superiority persists across confidence levels from 80% to 95%, consistent with the stated monotonicity property.Source: §6.5.2 · p. 140

6.5.3 Validity and Efficiency for Negatives

  • Under distribution shift from synthetically corrupted negatives, UnKGCP retains empirical coverage and adapts query-specific intervals, while FPI reaches 100% coverage with reasonably sharp intervals.UnKGCP coverage is around 0.8 with UKGE, above 0.7 in most other settings, and reaches 0.91 in BOX–NL27k; its coverage gap can also indicate substantial distribution shift, consistent with.Source: §6.5.3 · p. 140, Table 6.4 · p. 141

6.5.4 Conditionality

  • UnKGCP adapts interval lengths to query difficulty, unlike fixed-length CP intervals, and thus satisfies the conditionality criterion.Across BEUrRE, UKGE, and PASSLEAF, average interval length increases with prediction error; interval length can therefore reliably indicate uncertainty.Source: §6.5.4 · pp. 140–141, Figure 6.2 · p. 142

6.5.5 Calibration Sample Efficiency

  • With only about 20% of calibration data, UnKGCP achieves reliable, stable performance across models, after coverage and interval length vary substantially with very small calibration sets.As calibration size increases, both metrics stabilize rapidly; limited data can make quantile estimates unreliable, yielding under-coverage or overly conservative intervals.Source: §6.5.5 · pp. 141–142, Figure 6.3 · p. 143

6.6 related work

  • Prior UnKGE methods model probabilistic triples, but most provide point estimates without uncertainty quantification or formal guarantees; this chapter’s approach is, to the authors’ knowledge, the first to provide both.UKGE extends DistMult [252], PASSLEAF broadens backbone support and improves negative sampling, while uses box embeddings and affine relation transformations.Source: §6.6 · pp. 142–143

6.7 conclusion and discussion

  • UnKGCP is a model-agnostic framework that constructs formally guaranteed intervals and yields valid, sharp, query-adaptive estimates with stable performance from a small calibration set.On CN15k, average interval length exceeds 0.8 despite reasonably low model errors, revealing high predictive variance that mean squared error alone misses. The current method assumes single-valued confidence scores; interval-valued inputs would require predicting and calibrating means and lengths jointly. The next chapter extends embedding methods to approximate probabilistic inference over ontologies.Source: §6.7 · pp. 143–144

R E A S O N I N G U N D E R S C H E M A - L E V E L UNCERTAINTY

These parts develop and evaluate box-embedding methods for reasoning under schema-level uncertainty in statistical EL ontologies, including statistical proportions and hierarchical structure. They define a geometric loss whose zero-loss embeddings satisfy encoded axioms, supporting sound and efficient approximation of statistical reasoning.

7.1 introduction

  • Box embeddings encode Statistical EL concepts through volumes, enabling linear-time inference that is sound at zero loss and has error proportional to embedding error otherwise.The approach targets joint reasoning over statistical proportions and hierarchical structure, beyond individual-triple uncertainty estimates.Source: §7.1 · p. 146

7.2.1 Description Logics; 7.2.2 Statistical Description Logics

  • EL supports conjunction and existential quantification, while SEL extends it with probabilistic conditionals and asks for the tightest interval entailed by a TBox.SEL conditionals express statistical proportions, such as the fraction of a concept’s elements that also belong to another concept.Source: §7.2.1 · p. 146, §7.2.2 · pp. 148–149

7.3 illustrative example

  • Increasing the number of embeddings is expected to reduce the gap between estimated and true interval bounds by increasing the chance of approaching extreme values.The interval estimate can be too tight, as the overall admission-rate example demonstrates.Source: §7.3 · p. 150
  • 0.84 for men versus 0.81 for women overall reverses women’s higher admission rates in both departments because women disproportionately apply to the lower-admitting department.Encoding department-level rates and applicant distributions as conditionals makes the aggregate reversal explicit in SEL.Source: §7.3 · p. 151

7.4 normal form for S E L

  • The normalization procedure produces an entailment-equivalent SEL TBox whose size is linearly bounded by the original TBox.The approach excludes probabilistic conditionals involving the top concept because it has no finite box representation.Source: §7.4 · pp. 152–153

7.5 embedding and approximation; 7.5.1 Concept Representation; 7.5.2 Role Representation; 7.5.3 Loss Function

  • Concepts are represented as n-dimensional boxes and roles as affine transformations; the embedding loss includes terms for the four axiom types in a normalized TBox.Learnable parameters specify concept-box corners and role transformations.Source: §7.5.1 · p. 153, §7.5.2 · p. 153, §7.5 · p. 153

7.5.3 Loss Function

7.6 soundness and runtime guarantees

  • Zero total loss guarantees that the geometric interpretation satisfies the ontology; inference is sound, queries run in O((c + d) · n), and PMP propagates probability bounds.When statistical proportions embed perfectly, computed probabilities are exact; embedding error propagates to probability estimates.Source: §7.6 · pp. 156–158

7.7 implementation and hyperparameters

  • The prototype supports four conditional forms (PNF1–PNF4) and combines location and volume regularizers because their combination can outperform either alone.The location regularizer encourages concept boxes to lie in [0, β]^n; the volume regularizer is introduced as an alternative, and the two terms have some redundancy.Source: §7.7 · p. 158, §7.7.1 · pp. 158–159

7.7.2 Softplus Volume

  • Softplus volume addresses zero gradients for disjoint boxes; gradually cooling its temperature makes the approximation converge to true volume while a high initial temperature supports faster early learning.The parameterization M_w(C) = m_w(C) + exp(δ_w(C)) guarantees M_w(C) ≥ m_w(C).Source: §7.7.2 · p. 159, §7.7.3 · p. 159

7.7.4 Hyperparameter Tuning

  • The hyperparameter search tested dimensions n = [8, 16, 32, 64, 128], side lengths β = [1, 10], and Adam learning rates [0.001, 0.01, 0.05, 0.1].Experiments ran on a Linux machine with a 40GB NVIDIA A100 SXM4 GPU.Source: §7.7.4 · p. 160

7.8.1 Dataset Construction

  • Because no SEL benchmark ontologies were available, Country, Hybrid, and Person datasets were derived from YAGO3; 30% of axioms form non-random queries whose premises remain in the ontology.Undefined-probability conditionals and redundant axioms are excluded.Source: §7.8.1 · pp. 160–161

7.8.2 Baselines

  • With no direct SEL reasoning implementations for comparison, the study uses fixed [0, 1], random, and KDE-sampled interval estimators; classical EL embedding methods cannot serve as SEL baselines.The fixed estimator always predicts [0, 1], while KDE samples intervals from a density estimated on the learning set.Source: §7.8.2 · p. 161, Fixed Estimator · p. 161, Random Estimator · p. 162

7.8.3 Evaluation Settings

  • For each query, 60 embeddings yield minimum and maximum probability estimates as an approximation interval; evaluation uses MAE and soundness accuracy, the share of estimates contained in the true interval.The experiments typically use five query sets created by varying the data split.Source: PMP Evaluation · p. 163

7.8.4 Experimental Results and Analysis

  • BoxSEL outperformed baselines on SA and SE across Person, Country, and Hybrid, with SA above 89% and approximation gaps between 0.2 and 0.3.The approximation gap decreased as the number of embeddings increased.Source: Approximation Quality · p. 165, Figure 7.2 · p. 165
  • Inference error tracked embedding error, making embedding quality a practical indicator of approximation quality; inference took milliseconds per query after one-time embedding computation.Computing one embedding took 39/3/6 minutes on average for Person/Country/Hybrid, respectively.Source: Figure 7.3 · p. 165, Connection to Embedding Quality · p. 166, Runtime · p. 166
  • Ablations favored box concepts over n-balls, affine role transformations in Person and Country, dual boxes in Hybrid at higher complexity, and both volume and location regularization.Dual boxes use more than twice as many role parameters as affine transformations; location regularization also reduced epochs to convergence.Source: Ablation Study · p. 167, Table 7.6 · p. 167, Table 7.7 · p. 168

7.9 related work

  • SEL models statistical proportions, unlike type-2 probabilistic logics; exact inference via type elimination is impractical as types explode, while proof-system completeness is known only for limited fragments.The related-work discussion notes that type-2 methods interpret uncertainty differently from SEL’s statistical proportions.Source: §7.9 · pp. 168–169

7.10 conclusion and discussion

  • Extending BoxEL, BoxSEL supports linear-time SEL point estimates that are sound when embedding loss is zero; combining multiple embeddings approximates full probability intervals, with quality improving as embedding count rises.Using random seeds alone to diversify embeddings can be inefficient; the discussion proposes encouraging divergence during training as a possible extension.Source: §7.10 · pp. 169–170

8.1 conclusion

  • The thesis addresses uncertainty in input knowledge, model development, and deployment with theoretically grounded, model-agnostic methods designed to be modular and combinable.For schema-level uncertainty, BoxSEL enables probabilistic reasoning; the thesis also describes methods for triple-level confidence scores.Source: §8.1 · p. 172

8.2 limitations

  • The evaluation uses academic benchmarks and does not establish transfer to production knowledge graphs, jointly manage all three uncertainty sources, or assess downstream-system effects.Conformal guarantees rely on exchangeability, and robustness to complex distribution shifts and uncertainty propagation through composed systems remains open.Source: §8.2 · pp. 173–174

8.3 future directions

  • Future work includes relaxing exchangeability assumptions, scaling uncertainty guarantees to complex queries, and integrating uncertainty-aware knowledge graphs with language models and agents.Proposed directions include online or shift-aware conformal methods, and using knowledge graphs to ground or verify language-model claims and inform agent decisions.Source: §8.3 · pp. 174–175

more empirical results

For query answering, predictive multiplicity means comparable models can return different answer sets, and the evaluation adds measures of disagreement and overlap. The results report stronger multiplicity in this setting and fewer conflicting predictions with voting, while noting threshold sensitivity.

more empirical results

  • For query answering, a model returns all entities whose predictive scores exceed threshold τ, and multiplicity occurs when a competing model returns a different answer set.Ambiguity is the proportion of test queries with differing answer sets; discrepancy is the maximum such proportion across competing models.Source: Experiments for Link Prediction in… · pp. 212–213
  • The agreement metric measures overlap between competing models’ predicted answer sets using average Jaccard similarity.The Jaccard similarity is the intersection size divided by the union size.Source: Experiments for Link Prediction in… · p. 213
  • Query answering exhibits more significant predictive multiplicity because competing models find it harder to predict the same answer set, while voting reduces conflicting predictions.The results also note that the voting method depends heavily on the scoring-based threshold.Source: Experiments for Link Prediction in… · pp. 213–214
  • Changing ϵ has negligible effect on model performance within the chosen range, supporting the attribution of reported multiplicity changes primarily to ϵ variation.The passage relates this observation to Proposition 1.Source: Model Performance wrt. Error Tolerance · p. 214, Figure B.2 · p. 215

fixed-sized predictor

Fixed-size confidence predictors use a manually selected K to return the top-K entities. Their coverage and efficiency trade off against the chosen K, while a calibrated TopK choice still cannot adapt set size to query difficulty.

fixed-sized predictor

  • A small fixed K often misses the coverage target, whereas a large K creates unnecessarily large answer sets and reduces efficiency.The comparison evaluates K values 1, 3, 10, and 100.Source: fixed-sized predictor · p. 220
  • Tuning K on a calibration set gives a better d Cov–d Size trade-off than arbitrary fixed-size choices, but set size remains constant across queries.The TopK predictor therefore cannot adapt answer-set size to individual query difficulty.Source: fixed-sized predictor · p. 220

calibrated conformal predictor

The section examines score calibration for conformal prediction, but the reported calibration methods do not consistently improve answer-set quality. The discussion identifies assumptions and data sparsity that constrain calibration for KGE models.

calibrated conformal predictor

  • Platt predictors yield excessively large answer sets, and temperature scaling generally increases answer-set sizes rather than improving them as expected.The passage notes smaller sets for TransE, but says they remain uncompetitive with its best predictors.Source: calibrated conformal predictor · p. 221
  • Temperature scaling assumes uniform miscalibration and preserved score ordering, but KGE scores vary in calibration by query answer count and their ordering is sensitive to small hyperparameter changes.The discussed calibration divides plausibility scores by a temperature optimized on validation-set negative log-likelihood.Source: calibrated conformal predictor · pp. 221–222
  • The long-tailed distribution of triples across entities leaves insufficient validation data to calibrate entities associated with few or no triples effectively.Source: calibrated conformal predictor · p. 222

C.4 more empirical results for conditionality

The supplementary conditionality material examines answer-set adaptiveness across query difficulty and states conditional validity guarantees. Its proof material also gives a condition under which rank calibration reduces answer-set size.

C.4 more empirical results for conditionality

  • Supplementary plots examine how answer-set size varies with query difficulty for TransE predictors on FB15k and FB15k237.The figures describe this stratification as showing predictor adaptiveness.Source: Figure C.1 · p. 223, Figure C.2 · p. 223
  • Proposition 2 gives conditional validity bounds for each partition g at a user-specified confidence level α and parameter γ.The adjusted confidence level is α′ = α + γ · ϵκ.Source: §C.4 · pp. 227–228

D.1 proofs

  • Rank calibration reduces CondKGCP answer-set size when the condition in Equation (12) holds.Source: §D.1 · p. 230

D.2 verification of the condition in equation (12)

This appendix checks the condition underlying rank calibration, reports its empirical prevalence across model–dataset combinations, and examines CondKGCP’s robustness to nonconformity measures. It also supplies supplementary hyperparameter, method, dataset, and predictor details.

D.2 verification of the condition in equation (12)

  • The condition σg ≤1 holds for nearly all predicates across model–dataset combinations, supporting the practical utility of rank calibration for reducing answer-set size.Smaller average σ̄ values are typically associated with smaller AveSize.Source: §D.2 · p. 231

optimal hyperparameter settings

impact of nonconformity measure

  • CondKGCP achieves low CovGap with significantly smaller answer sets than MCP and ClusterCP in most cases, regardless of the nonconformity measure.The reported advantage remains when APS or RAPS is used, although those combinations do not improve the trade-off.Source: impact of nonconformity measure · p. 232, Table D.3 · p. 233

complete experimental results

details of existing unkge methods

  • UKGE predicts continuous triple-plausibility values, while PASSLEAF adds supervised, negative-sample, and pseudo-label losses to its training objective.UKGE scores lie in [0, 1]; PASSLEAF incorporates semi-supervised learning over pseudo-labeled triples.Source: UKGE · p. 239, PASSLEAF · p. 240

E.2 details of datasets

  • The three evaluation datasets use confidence scores with different source-specific interpretations and preprocessing: CN15k scores are capped and normalized, NL27k scores are normalized, and PPI5k scores can be interpreted as probabilities.Source: §E.2 · p. 241

details of confidence predictor

  • Fisher Prediction Intervals assume approximately normal residuals, i.i.d. calibration examples, and homoscedasticity, while the described QR approach requires two additional UnKGE models.FPI uses a t-distribution; its interval width is constant across test queries and does not satisfy the conditionality desideratum.Source: Fisher Prediction Intervals (FPI) · p. 242, Quantile Regression (QR) · p. 243

more experimental results

The supplementary material presents further experimental analyses and proves properties of the statistical-ontology methods. It also documents benchmark construction and reports selected hyperparameters.

more experimental results

  • The supplementary figures examine confidence-level effects on sharpness and coverage, conditionality across datasets and example types, and calibration-set-size effects on coverage and sharpness.For calibration-set-size plots, lines show means over 10 runs and shaded areas show standard deviations.Source: Figure E.1 · p. 244, Figure E.2 · p. 244, Figure E.6 · p. 245

F.1 proofs of technical results

  • The SEL normalization transformation preserves entailment of the specified conditionals and produces a normal-form TBox whose size is linearly bounded by the original TBox.Source: more experimental results · p. 251
  • The appendix states that probabilistic Modus Ponens derives bounds l3 = l1 · l2 and u3 = min{1, u1 · u2 + 1 − l1}, and that the runtime for computing p is O((c + d) · n).The runtime bound applies to concepts C and D of sizes c and d with embedding dimension n.Source: more experimental results · p. 252, §F.1 · p. 253

details for sel ontology construction

  • YAGO3 was selected for ontology construction because its concept assertions are complete for each entity, supporting more accurate probability counts; the benchmarks select concepts and roles from specified domains.The Hybrid dataset uses the top 18 roles by fact count and the top 12 concepts by instance count among their domains or ranges.Source: details for sel ontology construction · p. 254

F.3 additional experimental results

Loading 2610.06974v1…