A hierarchy of faithfulness criteria for knowledge base completion

Olga Mashkova; Robert Hoehndorf

cs.AIAug 20, 2026

A hierarchy of faithfulness criteria for knowledge base completion

Authors: Olga Mashkova, Robert Hoehndorf

Organizations: Computer Science Program, Computer, Electrical, and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955, Saudi Arabia

Abstract

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(α\mid\mathcal{O}) = \#(\mathcal{O}\cup\{α\})/\#(\mathcal{O})$ , which recovers the trichotomy at its endpoints and ranks undetermined axioms in between. Evaluating knowledge graph and logic-geometric embedding models on $\mathcal{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.

Figures & tables

Logic-geometric (KBC)
Model	$\mathrm{AUC}_{+/-}$ $\uparrow$	Pair-FVR $\downarrow$	$\rho_{P}$ $\uparrow$	MRR $\uparrow$	Hits@10 $\uparrow$
ELEmbeddings	0.70 $\pm$ 0.01	0.48 $\pm$ 0.00	- 0.62 $\pm$ 0.02	0.14 $\pm$ 0.00	0.42 $\pm$ 0.01
EmEL++	0.73 $\pm$ 0.01	0.49 $\pm$ 0.00	- 0.63 $\pm$ 0.05	0.15 $\pm$ 0.01	0.41 $\pm$ 0.04
Box2EL	0.74 $\pm$ 0.01	0.60 $\pm$ 0.01	- 0.53 $\pm$ 0.00	0.17 $\pm$ 0.01	0.51 $\pm$ 0.01
Geometric (KGC)
BoxE	0.42 $\pm$ 0.06	0.73 $\pm$ 0.02	- 0.16 $\pm$ 0.04	0.10 $\pm$ 0.00	0.23 $\pm$ 0.04

Table 1: Faithfulness across models on atomic subsumption (

C\sqsubseteq D

, GCI0) over the Pizza ontology. Higher

\mathrm{AUC}_{+/-}

and

\rho_{P}

are better; Pair-FVR near

0.5

means

\mathcal{S}_{?}

is not separated from

\mathcal{S}_{\bot}

. Ranking accuracy (MRR, Hits@10) does not predict faithfulness. Full metrics, the GO-plus slice, and all normal forms are in Appendix 0.G .

Appendix figures & tables25 assets

Supplementary material from the paper’s appendix.

Appendix

Training axioms by normal form (GCI0 split)
	Pizza	GO-plus
Classes $\|N_{C}\|$	106	653
Roles $\|N_{R}\|$	4	6
Domain size $\|\Delta\|$	2	2
GCI0 $C\sqsubseteq D$	62	546
GCI1 $C\sqcap D\sqsubseteq E$	6	18

Appendix

Table 2: Ontology sizes and evaluation-split composition. Axiom counts exclude trivial axioms; “n/a” marks a quantity that is not applicable (the GO-plus GCI1, GCI2, and GCI3 splits have no contradictory set, whereas Pizza has one for every normal form).

Normal form	Axiom	$\mathrm{AUC}_{+/-}$ $\uparrow$	Pair-FVR $\downarrow$	$\rho_{P}$ $\uparrow$
GCI0	$C\sqsubseteq D$	0.72	0.53	- 0.59
GCI1	$C\sqcap D\sqsubseteq E$	0.15	0.80	-0.27
GCI2	$C\sqsubseteq\exists r.D$	0.50	0.57	- 0.43
GCI3	$\exists r.C\sqsubseteq D$	0.84	0.55	- 0.22
GCI1 ⊥	$C\sqcap D\sqsubseteq\bot$	0.97	0.06	- 0.42

Appendix

Table 3: Faithfulness is construct-dependent: mean over the logic-geometric models (ELEmbeddings, EmEL++, Box2EL) by normal form, on the Pizza ontology. Disjointness (

C\sqcap D\sqsubseteq\bot

) is the one construct handled faithfully (high AUC, Pair-FVR near

0

); conjunctive subsumption (

C\sqcap D\sqsubseteq E

) inverts (AUC below

0.5

, negative

\rho_{P}

), driven by the ball models’ loss (Section 6.2 ; Appendix 0.C ).

Panel of Figure 1 — Figure 1: Full negative-sampling sweep (Section 6.3 ) on the Pizza ontology: FVR (left axis, lower is better) and MRR (right axis) as the fraction of random-corruption negatives varies; the remainder $p_{\bot}=1-x$ is drawn from $\mathcal{S}_{\bot}$ . In all 12 panels the all-contradiction endpoint ( $x=0$ ) has lower FVR than the all-random endpoint ( $x=1$ ); the response is not monotone in between, and on GCI0 the ball-based models’ effect is within single-seed noise.

Model name	$\mathrm{AUC}_{+/-}$ $\uparrow$	Adm@10 $\uparrow$	FVR $\downarrow$	Pair-FVR $\downarrow$	$\rho_{P}$ $\uparrow$	MRR $\uparrow$	Hits@10 $\uparrow$
ELEm	0.70 $\pm$ 0.01	0.98 $\pm$ 0.00	0.74 $\pm$ 0.00	0.48 $\pm$ 0.00	0.62 $\pm$ 0.02	0.14 $\pm$ 0.00	0.42 $\pm$ 0.01
Box2EL	0.74 $\pm$ 0.01	0.99 $\pm$ 0.00	0.76 $\pm$ 0.01	0.60 $\pm$ 0.01	0.53 $\pm$ 0.00	0.17 $\pm$ 0.01	0.51 $\pm$ 0.01
EmEL++	0.73 $\pm$ 0.01	0.98 $\pm$ 0.01	0.73 $\pm$ 0.01	0.49 $\pm$ 0.00	0.63 $\pm$ 0.05	0.15 $\pm$ 0.01	0.41 $\pm$ 0.04
BoxE	0.42 $\pm$ 0.06	0.94 $\pm$ 0.01	0.90 $\pm$ 0.03	0.73 $\pm$ 0.02	0.16 $\pm$ 0.04	0.10 $\pm$ 0.00	0.23 $\pm$ 0.04
ComplEx	0.53 $\pm$ 0.03	0.94 $\pm$ 0.01	0.82 $\pm$ 0.01	0.45 $\pm$ 0.01	-0.13 $\pm$ 0.03	0.08 $\pm$ 0.01	0.11 $\pm$ 0.01
DistMult	0.52 $\pm$ 0.09	0.94 $\pm$ 0.01	0.82 $\pm$ 0.05	0.47 $\pm$ 0.08	-0.03 $\pm$ 0.08	0.05 $\pm$ 0.02	0.08 $\pm$ 0.06

Appendix

Table 4: GCI0, Pizza

Model name	$\mathrm{AUC}_{+/-}$ $\uparrow$	Adm@10 $\uparrow$	FVR $\downarrow$	Pair-FVR $\downarrow$	$\rho_{P}$ $\uparrow$	MRR $\uparrow$	Hits@10 $\uparrow$
ELEm	0.84 $\pm$ 0.01	1.00 $\pm$ 0.00	0.60 $\pm$ 0.01	0.47 $\pm$ 0.01	0.53 $\pm$ 0.01	0.16 $\pm$ 0.01	0.46 $\pm$ 0.01
Box2EL	0.82 $\pm$ 0.01	1.00 $\pm$ 0.00	0.50 $\pm$ 0.01	0.25 $\pm$ 0.02	0.63 $\pm$ 0.01	0.09 $\pm$ 0.00	0.26 $\pm$ 0.01
EmEL++	0.83 $\pm$ 0.01	1.00 $\pm$ 0.00	0.62 $\pm$ 0.02	0.49 $\pm$ 0.02	0.57 $\pm$ 0.01	0.15 $\pm$ 0.01	0.45 $\pm$ 0.02
BoxE	0.61 $\pm$ 0.01	1.00 $\pm$ 0.00	0.74 $\pm$ 0.01	0.33 $\pm$ 0.02	0.24 $\pm$ 0.02	0.16 $\pm$ 0.00	0.20 $\pm$ 0.00
ComplEx	0.55 $\pm$ 0.05	1.00 $\pm$ 0.00	0.78 $\pm$ 0.04	0.49 $\pm$ 0.08	0.01 $\pm$ 0.05	0.16 $\pm$ 0.00	0.19 $\pm$ 0.00
DistMult	0.27 $\pm$ 0.07	1.00 $\pm$ 0.00	0.95 $\pm$ 0.03	0.76 $\pm$ 0.13	0.01 $\pm$ 0.01	0.04 $\pm$ 0.02	0.09 $\pm$ 0.02

Appendix

Table 5: GCI0, GO-plus slice

Model name	$\mathrm{AUC}_{+/-}$ $\uparrow$	Adm@10 $\uparrow$	FVR $\downarrow$	Pair-FVR $\downarrow$	$\rho_{P}$ $\uparrow$	MRR $\uparrow$	Hits@10 $\uparrow$
ELEm	0.57 $\pm$ 0.01	1.00 $\pm$ 0.00	0.78 $\pm$ 0.00	0.52 $\pm$ 0.01	0.51 $\pm$ 0.01	0.10 $\pm$ 0.00	0.29 $\pm$ 0.01
Box2EL	0.35 $\pm$ 0.02	1.00 $\pm$ 0.00	0.90 $\pm$ 0.01	0.73 $\pm$ 0.02	0.22 $\pm$ 0.01	0.09 $\pm$ 0.00	0.18 $\pm$ 0.01
EmEL++	0.59 $\pm$ 0.01	1.00 $\pm$ 0.00	0.76 $\pm$ 0.00	0.48 $\pm$ 0.01	0.55 $\pm$ 0.01	0.10 $\pm$ 0.00	0.29 $\pm$ 0.01
BoxE	0.34 $\pm$ 0.01	1.00 $\pm$ 0.00	0.91 $\pm$ 0.00	0.75 $\pm$ 0.01	0.22 $\pm$ 0.03	0.14 $\pm$ 0.01	0.20 $\pm$ 0.01
ComplEx	0.51 $\pm$ 0.03	1.00 $\pm$ 0.00	0.83 $\pm$ 0.01	0.51 $\pm$ 0.03	-0.05 $\pm$ 0.01	0.11 $\pm$ 0.01	0.19 $\pm$ 0.02
DistMult	0.47 $\pm$ 0.02	1.00 $\pm$ 0.00	0.86 $\pm$ 0.01	0.48 $\pm$ 0.06	-0.04 $\pm$ 0.03	0.09 $\pm$ 0.01	0.18 $\pm$ 0.02

Appendix

Table 6: GCI2, Pizza

Model name	$\rho_{P}$ $\uparrow$	MRR $\uparrow$	Hits@10 $\uparrow$
ELEm	0.43 $\pm$ 0.02	0.06 $\pm$ 0.00	0.22 $\pm$ 0.00
Box2EL	0.30 $\pm$ 0.00	0.01 $\pm$ 0.00	0.01 $\pm$ 0.01
EmEL++	0.49 $\pm$ 0.02	0.06 $\pm$ 0.00	0.22 $\pm$ 0.02
BoxE	0.15 $\pm$ 0.04	0.06 $\pm$ 0.00	0.07 $\pm$ 0.00
ComplEx	-0.15 $\pm$ 0.05	0.06 $\pm$ 0.00	0.07 $\pm$ 0.00
DistMult	-0.22 $\pm$ 0.14	0.01 $\pm$ 0.00	0.01 $\pm$ 0.01

Appendix

Table 7: GCI2, GO-plus slice

Model name	$\mathrm{AUC}_{+/-}$ $\uparrow$	Adm@10 $\uparrow$	FVR $\downarrow$	Pair-FVR $\downarrow$	$\rho_{P}$ $\uparrow$	MRR $\uparrow$	Hits@10 $\uparrow$
ELEm	0.02 $\pm$ 0.00	1.00 $\pm$ 0.00	1.00 $\pm$ 0.00	0.94 $\pm$ 0.01	-0.34 $\pm$ 0.01	0.06 $\pm$ 0.00	0.11 $\pm$ 0.01
Box2EL	0.39 $\pm$ 0.01	1.00 $\pm$ 0.00	0.91 $\pm$ 0.00	0.55 $\pm$ 0.01	-0.09 $\pm$ 0.02	0.05 $\pm$ 0.00	0.13 $\pm$ 0.01
EmEL++	0.05 $\pm$ 0.01	1.00 $\pm$ 0.00	1.00 $\pm$ 0.00	0.91 $\pm$ 0.02	-0.31 $\pm$ 0.03	0.06 $\pm$ 0.00	0.11 $\pm$ 0.00

Appendix

Table 8: GCI1, Pizza

Model name	$\rho_{P}$ $\uparrow$	MRR $\uparrow$	Hits@10 $\uparrow$
ELEm	-0.39 $\pm$ 0.02	0.08 $\pm$ 0.00	0.20 $\pm$ 0.01
Box2EL	0.12 $\pm$ 0.01	0.04 $\pm$ 0.00	0.06 $\pm$ 0.01
EmEL++	-0.40 $\pm$ 0.01	0.09 $\pm$ 0.00	0.20 $\pm$ 0.01

Appendix

Table 9: GCI1, GO-plus slice

Model name	$\mathrm{AUC}_{+/-}$ $\uparrow$	Adm@10 $\uparrow$	FVR $\downarrow$	Pair-FVR $\downarrow$	$\rho_{P}$ $\uparrow$	MRR $\uparrow$	Hits@10 $\uparrow$
ELEm	0.96 $\pm$ 0.00	1.00 $\pm$ 0.00	0.47 $\pm$ 0.01	0.08 $\pm$ 0.01	0.43 $\pm$ 0.00	0.03 $\pm$ 0.00	0.02 $\pm$ 0.00
Box2EL	1.00 $\pm$ 0.00	1.00 $\pm$ 0.00	0.17 $\pm$ 0.01	0.01 $\pm$ 0.00	0.41 $\pm$ 0.00	0.05 $\pm$ 0.00	0.01 $\pm$ 0.00
EmEL++	0.96 $\pm$ 0.00	1.00 $\pm$ 0.00	0.47 $\pm$ 0.01	0.07 $\pm$ 0.01	0.43 $\pm$ 0.00	0.03 $\pm$ 0.00	0.02 $\pm$ 0.00

Appendix

Table 10: GCI1 ⊥ , Pizza

Model name	$\mathrm{AUC}_{+/-}$ $\uparrow$	Adm@10 $\uparrow$	FVR $\downarrow$	Pair-FVR $\downarrow$	$\rho_{P}$ $\uparrow$	MRR $\uparrow$	Hits@10 $\uparrow$
ELEm	0.95 $\pm$ 0.01	1.00 $\pm$ 0.00	0.65 $\pm$ 0.01	0.06 $\pm$ 0.00	0.61 $\pm$ 0.01	0.01 $\pm$ 0.00	0.03 $\pm$ 0.01
Box2EL	0.99 $\pm$ 0.00	1.00 $\pm$ 0.00	0.50 $\pm$ 0.01	0.03 $\pm$ 0.00	0.73 $\pm$ 0.00	0.01 $\pm$ 0.00	0.04 $\pm$ 0.00
EmEL++	0.95 $\pm$ 0.01	1.00 $\pm$ 0.00	0.65 $\pm$ 0.01	0.06 $\pm$ 0.00	0.61 $\pm$ 0.01	0.01 $\pm$ 0.00	0.03 $\pm$ 0.01

Appendix

Table 11: GCI1 ⊥ , GO-plus slice

Model name	$\mathrm{AUC}_{+/-}$ $\uparrow$	Adm@10 $\uparrow$	FVR $\downarrow$	Pair-FVR $\downarrow$	$\rho_{P}$ $\uparrow$	MRR $\uparrow$	Hits@10 $\uparrow$
ELEm	0.75 $\pm$ 0.01	1.00 $\pm$ 0.00	0.71 $\pm$ 0.02	0.56 $\pm$ 0.03	0.26 $\pm$ 0.01	0.23 $\pm$ 0.03	0.65 $\pm$ 0.01
Box2EL	0.97 $\pm$ 0.00	1.00 $\pm$ 0.00	0.62 $\pm$ 0.01	0.55 $\pm$ 0.01	0.09 $\pm$ 0.01	0.39 $\pm$ 0.02	0.77 $\pm$ 0.02
EmEL++	0.79 $\pm$ 0.02	1.00 $\pm$ 0.00	0.68 $\pm$ 0.01	0.54 $\pm$ 0.01	0.31 $\pm$ 0.01	0.22 $\pm$ 0.02	0.60 $\pm$ 0.03

Appendix

Table 12: GCI3, Pizza

Model name	$\rho_{P}$ $\uparrow$	MRR $\uparrow$	Hits@10 $\uparrow$
ELEm	0.55 $\pm$ 0.01	0.01 $\pm$ 0.00	0.01 $\pm$ 0.00
Box2EL	0.42 $\pm$ 0.01	0.01 $\pm$ 0.00	0.01 $\pm$ 0.00
EmEL++	0.53 $\pm$ 0.00	0.01 $\pm$ 0.00	0.01 $\pm$ 0.00

Appendix

Table 13: GCI3, GO-plus slice

$x$	FVR $\downarrow$	MRR $\uparrow$
0.0	$0.7303\pm 0.0087$	$0.1710\pm 0.0076$
0.2	$0.7328\pm 0.0122$	$0.1701\pm 0.0093$
0.4	$0.7444\pm 0.0054$	$0.1721\pm 0.0067$
0.6	$0.7516\pm 0.0050$	$0.1743\pm 0.0066$
0.8	$0.7524\pm 0.0082$	$0.1728\pm 0.0048$
1.0	$0.7493\pm 0.0114$	$0.1748\pm 0.0057$

Appendix

Table 14: Multi-seed (5 seeds) sweep for Box2EL, Pizza ontology, GCI0.

x

is the fraction of random-corruption negatives, with the remaining

1-x

drawn from

\mathcal{S}_{\bot}

(matching Figure 1 ). Values are mean

\pm

standard deviation.

$x$	FVR $\downarrow$	MRR $\uparrow$
0.0	$0.7335\pm 0.0035$	$0.1401\pm 0.0024$
0.2	$0.7377\pm 0.0063$	$0.1426\pm 0.0030$
0.4	$0.7344\pm 0.0051$	$0.1439\pm 0.0057$
0.6	$0.7383\pm 0.0078$	$0.1431\pm 0.0049$
0.8	$0.7395\pm 0.0069$	$0.1470\pm 0.0083$
1.0	$0.7431\pm 0.0052$	$0.1452\pm 0.0041$

Appendix

Table 15: Multi-seed (5 seeds) sweep for ELEmbeddings, Pizza ontology, GCI0; conventions as in Table 14 .

$x$	FVR $\downarrow$	MRR $\uparrow$
0.0	$0.7304\pm 0.0038$	$0.1409\pm 0.0062$
0.2	$0.7357\pm 0.0068$	$0.1402\pm 0.0025$
0.4	$0.7340\pm 0.0023$	$0.1461\pm 0.0069$
0.6	$0.7354\pm 0.0074$	$0.1444\pm 0.0049$
0.8	$0.7357\pm 0.0077$	$0.1485\pm 0.0082$
1.0	$0.7398\pm 0.0032$	$0.1458\pm 0.0038$

Appendix

Table 16: Multi-seed (5 seeds) sweep for EmEL++, Pizza ontology, GCI0; conventions as in Table 14 .

$x$	FVR $\downarrow$	MRR $\uparrow$
0.0	$0.1695\pm 0.0042$	$0.0537\pm 0.0013$
0.2	$0.1707\pm 0.0051$	$0.0517\pm 0.0003$
0.4	$0.1725\pm 0.0087$	$0.0515\pm 0.0013$
0.6	$0.1694\pm 0.0070$	$0.0526\pm 0.0012$
0.8	$0.1746\pm 0.0075$	$0.0517\pm 0.0020$
1.0	$0.1789\pm 0.0066$	$0.0516\pm 0.0020$

Appendix

Table 17: Multi-seed (5 seeds) sweep for Box2EL, Pizza ontology, GCI1 ⊥ (disjointness); conventions as in Table 14 .

$x$	FVR $\downarrow$	MRR $\uparrow$
0.0	$0.4323\pm 0.0102$	$0.0351\pm 0.0008$
0.2	$0.4452\pm 0.0053$	$0.0341\pm 0.0020$
0.4	$0.4484\pm 0.0204$	$0.0343\pm 0.0022$
0.6	$0.4452\pm 0.0251$	$0.0340\pm 0.0024$
0.8	$0.4563\pm 0.0178$	$0.0335\pm 0.0035$
1.0	$0.4580\pm 0.0106$	$0.0325\pm 0.0009$

Appendix

Table 18: Multi-seed (5 seeds) sweep for ELEmbeddings, Pizza ontology, GCI1 ⊥ (disjointness); conventions as in Table 14 .

$x$	FVR $\downarrow$	MRR $\uparrow$
0.0	$0.4330\pm 0.0079$	$0.0351\pm 0.0014$
0.2	$0.4475\pm 0.0070$	$0.0339\pm 0.0019$
0.4	$0.4516\pm 0.0184$	$0.0339\pm 0.0012$
0.6	$0.4436\pm 0.0266$	$0.0346\pm 0.0028$
0.8	$0.4574\pm 0.0168$	$0.0331\pm 0.0034$
1.0	$0.4581\pm 0.0102$	$0.0333\pm 0.0018$

Appendix

Table 19: Multi-seed (5 seeds) sweep for EmEL++, Pizza ontology, GCI1 ⊥ (disjointness); conventions as in Table 14 .

$x$	FVR $\downarrow$	MRR $\uparrow$
0.0	$0.8723\pm 0.0119$	$0.0921\pm 0.0074$
0.2	$0.8866\pm 0.0128$	$0.0945\pm 0.0060$
0.4	$0.8916\pm 0.0094$	$0.0953\pm 0.0063$
0.6	$0.8865\pm 0.0089$	$0.0941\pm 0.0085$
0.8	$0.8891\pm 0.0030$	$0.0910\pm 0.0034$
1.0	$0.9023\pm 0.0026$	$0.0965\pm 0.0096$

Appendix

Table 20: Multi-seed (5 seeds) sweep for Box2EL, Pizza ontology, GCI2 (

C\sqsubseteq\exists r.D