# A hierarchy of faithfulness criteria for knowledge base completion

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 20 Aug 2026.

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

- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [Towards Faithfully Interpretable NLP Systems: How should we define and evaluate faithfulness?](https://mlsanity.com/paper/2004.03685/) (2020)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [Logic Tensor Networks](https://mlsanity.com/paper/2012.13635/) (2020)
- [Logical Neural Networks](https://mlsanity.com/paper/2006.13155/) (2020)
- [BoxE: A Box Embedding Model for Knowledge Base Completion](https://mlsanity.com/paper/2007.06267/) (2020)
- [Knowledge Graphs: Opportunities and Challenges](https://mlsanity.com/paper/2303.13948/) (2023)
- [Knowledge Graph Embedding with Iterative Guidance from Soft Rules](https://mlsanity.com/paper/1711.11231/) (2017)
- [EL Embeddings: Geometric construction of models for the Description Logic EL ++](https://mlsanity.com/paper/1902.10499/) (2019)
- [Realistic Re-evaluation of Knowledge Graph Completion Methods: An Experimental Study](https://mlsanity.com/paper/2003.08001/) (2020)
- [Type-Constrained Representation Learning in Knowledge Graphs](https://mlsanity.com/paper/1508.02593/) (2015)
- [Faithiful Embeddings for EL++ Knowledge Bases](https://mlsanity.com/paper/2201.09919/) (2022)
- [Probability Calibration for Knowledge Graph Embedding Models](https://mlsanity.com/paper/1912.10000/) (2019)
- [Dual Box Embeddings for the Description Logic EL++](https://mlsanity.com/paper/2301.11118/) (2023)
- [From Knowledge Graph Embedding to Ontology Embedding? An Analysis of the Compatibility between Vector Space Representations and Rules](https://mlsanity.com/paper/1805.10461/) (2018)
- [Rethinking Knowledge Graph Evaluation Under the Open-World Assumption](https://mlsanity.com/paper/2209.08858/) (2022)
- [Description Logic EL++ Embeddings with Intersectional Closure](https://mlsanity.com/paper/2202.14018/) (2022)
- [Sem@K: Is my knowledge graph embedding model semantic-aware?](https://mlsanity.com/paper/2301.05601/) (2023)
- [Knowledge Base Embeddings: Semantics and Theoretical Properties](https://mlsanity.com/paper/2408.04913/) (2024)

## Abstract (arXiv)

Knowledge graph completion is evaluated by ranking observed triples above randomly corrupted ones, which treats every unobserved fact as false. When the object being completed is a description logic knowledge base rather than a plain graph, the open world assumption and deductive closure make this inadequate: relative to the knowledge base, a candidate axiom is entailed, contradictory, or undetermined, and a model that cannot separate a logically impossible axiom from a plausible novel one is not merely less accurate but semantically incorrect. We ask what it means for a knowledge base completion model to be logically faithful, and whether current embedding models are. We define a hierarchy of four increasingly strict criteria, discrimination, logical admissibility, monotonic logical faithfulness, and probabilistic logical faithfulness, and prove that they form a strict chain of implications. We ground the strongest criterion in the relative model count P(αmidO) = #(Ocupα)/#(O), which recovers the trichotomy at its endpoints and ranks undetermined axioms in between. Evaluating knowledge graph and logic-geometric embedding models on EL ontologies, with entailed, contradictory, and undetermined test sets generated by a reasoner, we find that ranking accuracy does not imply logical faithfulness and that none of the evaluated models is faithful across the hierarchy. The code is available at https://github.com/bio-ontology-research-group/kbc.