PaperlayerView exact revision on arXiv

Source-linked AI summary

A hierarchy of faithfulness criteria for knowledge base completion

Olga Mashkova, Robert Hoehndorf

arXiv:2609.27863v1cs.AI

TL;DR

Knowledge base completion needs to distinguish entailed, contradictory, and undetermined axioms, unlike graph completion’s treatment of unobserved facts as false. The paper defines a hierarchy of logical faithfulness criteria grounded in relative model counting. Its evaluations find that ranking accuracy does not imply faithfulness, and current models do not satisfy the hierarchy across logical constructs.

  • Problem

    Graph completion treats unobserved triples as false, but knowledge bases under the open world assumption include undetermined axioms that may be valid extensions.

    Source: §1 · pp. 1–2, §4.1 · p. 5

  • Method

    The paper defines four increasingly strict faithfulness criteria, grounds the strongest in relative model count, and evaluates models using reasoner-generated logical-status sets.

    Source: §1 · p. 2

  • Results

    Current models cluster near discrimination but violate monotonic logical faithfulness, model position varies by logical construct, and contradiction negatives improve faithfulness at a cost in ranking accuracy.

    Source: §1 · p. 2, §6.2 · p. 9, §7 · p. 11

  • Takeaways & Limitations

    Knowledge base completion is an evaluation target requiring logical correctness under the open world assumption, not just ranking observed triples above random corruptions.

    Source: §7 · pp. 10–11

    The relative model count uses a bounded Herbrand domain, a domain-closure assumption that differs from open-domain semantics and serves as a plausibility target rather than redefining entailment.

    Source: §4.2 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

Standard knowledge graph completion treats unobserved triples as false, but knowledge bases under the open world assumption distinguish entailed, contradictory, and undetermined axioms. The paper introduces a hierarchy for evaluating whether completion models respect these logical distinctions.

1 Introduction

  • Standard knowledge graph completion ranks observed triples against corrupted or unobserved triples, implicitly treating every unobserved triple as false.This applies both to common ranking metrics and to random-negative training.Source: §1 · p. 1
  • Under the open world assumption, candidate axioms are entailed, contradictory, or undetermined, so absence from a knowledge base does not establish falsity.An undetermined axiom is logically possible and can be a valid potential extension.Source: §1 · pp. 1–2
  • Conflating contradictions with undetermined axioms can cause downstream filters to accept logically impossible axioms as often as plausible novel ones.The paper distinguishes this semantic problem from calibration alone.Source: §1 · p. 2
  • The paper defines four increasingly strict faithfulness criteria, from discrimination through logical admissibility and monotonic logical faithfulness to probabilistic logical faithfulness grounded in relative model count.The relative model count ranks undetermined axioms between contradictions and entailed axioms.Source: §1 · p. 2

2 Related work

Prior work addresses open-world evaluation, consistency, and embedding geometries, but does not jointly distinguish entailed axioms from undetermined ones or rank the undetermined region. This paper uses relative model count as an evaluation target for embedding-based completion.

2 Related work

  • Consistency-aware filters and semantic-aware metrics test necessary admissibility conditions, but neither separates entailed axioms nor ranks undetermined candidates.The hierarchy makes the gap quantitative and identifies a failure to distinguish contradictions from undetermined axioms under binary negative-sampling losses.Source: §2 · p. 3
  • Geometric models encode logical structure, but their binary positive-versus-corrupted training leaves ranking within the undetermined region essentially unconstrained.The framework predicts that added logical structure may help monotonic faithfulness more than probabilistic faithfulness.Source: §2 · p. 3
  • The paper’s ranking-level faithfulness criterion differs from representation-level faithfulness, which asks whether a zero-loss embedding models the ontology and reproduces its entailments.A representation-faithful embedding may still rank an undetermined axiom no higher than a contradiction.Source: §2 · p. 3
  • The relative model count is a random-worlds degree of belief, repurposed here as a ground-truth evaluation target for embedding-based knowledge base completion.The paper presents this use as a novel contribution.Source: §2 · p. 3

3 Preliminaries

The preliminaries define description logic ontologies and distinguish knowledge base completion from graph link prediction. Knowledge base completion ranks candidate logical axioms, including schema-level constraints, rather than only missing graph edges.

3.1 Description logics

  • Description logic ontologies use concept, role, and individual names; EL permits top, conjunction, and existential restriction, with polynomial-time subsumption checking.An ontology contains terminological axioms, role axioms, and assertions, and the paper assumes it is consistent.Source: §3.1 · p. 4

3.2 Knowledge base completion

  • Knowledge base completion extends graph link prediction to missing logical axioms, including complex concepts and schema-level constraints.A candidate axiom may be an assertion or a TBox axiom, and the method scores candidate extensions relative to a knowledge base.Source: §3.2 · p. 4

4 The logical status of candidate axioms and relative model counting

The section establishes the open-world trichotomy for candidate axioms and refines it with relative model counting. Bounded Herbrand interpretations make the count finite while leaving classical entailment as the paper’s logical standard.

4.1 The logical status of candidate axioms

  • Under the open world assumption, each candidate axiom is entailed, contradictory, or undetermined, partitioning candidates into three disjoint status classes.Standard random corruption suppresses contradictions and undetermined axioms together.Source: §4.1 · p. 5

4.2 Bounded-domain model counting

  • The model-counting setup restricts interpretations to a finite Herbrand domain over named individuals, making the model count finite and well-defined.This domain-closure assumption differs from open-domain semantics; relative counts serve as plausibility targets, not as a redefinition of classical entailment.Source: §4.2 · p. 5

4.3 Relative model count

  • Relative model count recovers the trichotomy at its endpoints: 1 for entailed axioms, 0 for contradictions, and values between 0 and 1 for undetermined axioms.For fragments with the finite model property and a sufficiently large domain, Herbrand entailment coincides with classical entailment; intermediate values grade how constraining an undetermined axiom is.Source: §4.3 · pp. 5–6
  • Exact model counting is #P-complete, so tractability depends on the size of the bounded Herbrand domain rather than the counting algorithm.The paper uses exact counts in its evaluation settings.Source: §4.3 · p. 6

5 A hierarchy of faithfulness criteria

The section defines four increasingly strict criteria for ranking candidate axioms, culminating in scores ordered by relative model count. It proves that each criterion strictly implies the preceding one, with no implication reversible.

5.1 The four criteria

  • Discrimination ranks entailed axioms above contradictions, while logical admissibility also keeps every contradiction below all consistent candidates.Classical MRR and Hits@k approximate discrimination but are silent about undetermined axioms; admissibility permits a threshold that accepts consistent candidates without contradictions.Source: §5.1 · p. 6
  • MLF strictly orders contradictions below undetermined axioms and those below entailed axioms, but imposes no ranking within the undetermined class.Thus MLF is ordinal across the three classes, whereas undetermined axioms can differ substantially in plausibility.Source: §5.1 · pp. 6–7
  • PLF requires model scores to preserve relative-model-count order, distinguishing undetermined axioms according to how many knowledge-base models satisfy them.The count is 0 for contradictions, 1 for entailed axioms, and intermediate for undetermined axioms; PLF is silent on pairs with identical counts.Source: §5.1 · p. 7

5 A hierarchy of faithfulness criteria

  • L0–L2 can be tested with reasoner-generated entailment classes when entailment is decidable, but L3 requires a #P-complete count and is treated as a benchmark criterion.The scoring function assigns higher scores to candidates judged more plausible.Source: §5 · p. 6, §5.2 · p. 7

5.2 The hierarchy theorem

  • PLF ⇒ MLF ⇒ logical admissibility ⇒ discrimination is a strict chain: none of the implications can be reversed.The theorem assumes a consistent knowledge base, a well-defined relative model count, and non-empty entailment classes; otherwise the criteria degenerate.Source: §5.2 · p. 7

6 Experimental evaluation

The evaluation tests geometric and logic-geometric completion models on reasoner-generated entailment classes across two EL ontology datasets. Ranking accuracy does not ensure logical faithfulness, and contradiction-focused negative sampling reduces violations but does not by itself achieve faithfulness.

6.1 Setup

  • The evaluation uses Pizza and a connected GO-plus slice, bounded domain |∆|=2, and reasoner-generated entailed, contradictory, and undetermined test sets.Relative model counts are computed exactly for both datasets; the GO-plus slice has no negatives for GCI1, GCI2, and GCI3 normal forms, so full metrics are reported only for GCI0 and GCI1⊥ there.Source: §6.1 · p. 8
  • Seven evaluated models span geometric KGC, hybrid BoxE, and logic-geometric KBC approaches.The models are TransE, DistMult, ComplEx, BoxE, ELEmbeddings, EmEL++, and Box2EL.Source: §6.1 · p. 8
  • AUC+/−, Adm@k, FVR, and ρP assess L0–L3 respectively, while MRR and Hits@k serve as ranking-accuracy checks.Pair-FVR isolates undetermined-versus-contradiction confusion within the L2 violation rate.Source: §6.1 · p. 8
  • The intervention sweep was run at a single seed, unlike the multi-seed training used for the other configurations.A five-seed replication of the full sampler sweep is reported in the appendix.Source: §6.1 · p. 9, §6.3 · p. 10

6.2 Results

  • Ranking accuracy did not predict faithfulness: model ordering by MRR differed from Pair-FVR and ρP, and no setting reached ρP close to 1.On atomic subsumption, TransE had the highest MRR yet scored undetermined axioms no higher than contradictions.Source: Table 1 · p. 9, §6.2 · pp. 9–10
  • On conjunctive subsumption, ELEmbeddings and EmEL++ inverted entailment-versus-contradiction ranking (AUC+/− near 0.02–0.05), while Box2EL scored 0.39.The authors link the ball-based models’ inversion to their released loss for conjunctive subsumption, which ignores the size of the right-hand concept.Source: §6.2 · p. 9

6.3 Training-time interventions

  • The stratified sampler replaces some random corruptions with contradiction negatives; all 12 settings had lower FVR with contradiction-only negatives, but responses were non-monotone.The largest absolute reduction was 0.13 for Box2EL on GCI3; even at that endpoint, FVR stayed above 0.43 in most settings.Source: §6.3 · p. 10

7 Discussion and conclusion

The discussion reframes KBC as logical evaluation under OWA and deductive closure, then reports that current models satisfy discrimination but violate MLF, with performance depending on the logical construct.

7 Discussion and conclusion

  • Ranking observed triples above random corruptions is insufficient once OWA and deductive closure are in scope; L0–L2 use the reasoner-computable trichotomy, while L3 requires relative model counts.L0–L2 are applicable at deployment scale; exact model counting is #P-complete and infeasible at scale, making L3 a reference criterion where computable.Source: §7 · pp. 10–11
  • The evaluation scope is EL; ALC/SROIQ and broader EL/EL++ validation remain future work, and sampling contradiction negatives requires disjointness axioms absent from natural candidates such as GALEN.The relative model count is a plausibility target, not a redefinition of entailment.Source: §7 · p. 11
  • The hierarchy constrains the scoring function alone, so it can also assess neuro-symbolic methods whose logical layers differ from the embeddings evaluated here.Representative frameworks are placed on the hierarchy, with requirements identified for reaching MLF and PLF.Source: §7 · p. 11
  • Current models cluster near discrimination yet violate MLF; faithfulness varies by logical construct, and contradiction negatives improve it at a cost in ranking accuracy.The discussion frames logical correctness, rather than ranking in a TBox-stripped graph, as the broader goal.Source: §7 · p. 11

A Model counting example (extended)

The example counts models of an ontology and of a candidate axiom to compute a relative model count, illustrating how PLF ranks undetermined axioms.

A Model counting example (extended)

  • Exact #SAT with Ganak computes relative counts for the bounded Pizza and GO-plus test axioms; approximate counting or reasoner-derived trichotomy are fallbacks beyond that scale.Approximate counting is described for medium ontologies; trichotomy alone supports MLF but not PLF beyond bounded samples.Source: A Model counting example (extended) · p. 14
  • The ontology has 576 models: nine valid assignments to the A and B atoms, multiplied by 64 assignments to the unconstrained C and role atoms.The ontology contains two clauses from A ⊑ B, each with three satisfying assignments out of four.Source: A Model counting example (extended) · p. 14
  • 425/576 = 0.7378 of the bounded models satisfy the candidate, making it Herbrand-undetermined and placing it among undetermined axioms by its relative model count.A PLF-faithful model ranks it above undetermined axioms with lower counts and below those with higher counts.Source: A Model counting example (extended) · p. 15

B Proof of Theorem 1

The proof establishes that each stronger faithfulness criterion implies the next weaker one, then gives counterexamples showing that none of the implications reverses.

B Proof of Theorem 1

  • PLF implies MLF because relative model counts are 0 for contradictions, between 0 and 1 for undetermined axioms, and 1 for entailed axioms.Applying PLF to the two strict count inequalities yields the MLF ordering.Source: B Proof of Theorem 1 · p. 15
  • MLF implies logical admissibility, which implies discrimination: both steps follow by applying the relevant ordering to contradictions and consistent or entailed axioms.The proof assumes the contradiction, undetermined, and entailed sets are non-empty.Source: B Proof of Theorem 1 · p. 15
  • Each converse fails: MLF can misorder undetermined axioms by their counts, admissibility can misorder undetermined and entailed axioms, and discrimination can still rank a contradiction above an undetermined axiom.These counterexamples establish that the implication chain is strict.Source: B Proof of Theorem 1 · p. 15

C Implementation deviations and corrections

The implementation discussion traces a GCI1 inversion in ball-based embeddings to an omitted loss term, records implementation corrections, and considers how neuro-symbolic frameworks could fit the hierarchy.

C Implementation deviations and corrections

  • ELEmbeddings and EmEL++ omit GCI1 term (iv), so their scores ignore E’s radius and invert GCI1 discrimination; Box2EL avoids near-total inversion but remains somewhat below 0.5.Term (iv) should ensure the intersection of C and D lies within E; the defect is also present in the released original code.Source: C Implementation deviations and… · p. 16
  • Negating GCI1 scores would require normal-form-specific handling; restoring term (iv) penalizes an undersized E, while the atomic-subsumption loss already uses the superclass radius.The omission is specific to the conjunctive normal form.Source: C Implementation deviations and… · pp. 16–17
  • The released implementations use a corrected NF4 loss and corrected jcel normalisation; deviations are confined to NF2 and NF4, leaving box-based and translational baselines unaffected.The normaliser bug would have corrupted normal-form datasets, deductive closure, and relative model counts.Source: C Implementation deviations and… · p. 17

D Working example

  • In the working example, Professor(alice) is contradictory, TeachingAssistant(alice) undetermined, and Student(alice) entailed, so faithful scores order them in that sequence.The example also gives corresponding contradictory, entailed, and undetermined TBox candidates.Source: D Working example · p. 17

E Placing neuro-symbolic frameworks on the hierarchy

  • Exact logical layers can in principle reach MLF, while PLF additionally requires alignment with relative model counts; fuzzy or weighted layers reach L0, with MLF depending on contradiction collapse.DeepProbLog’s weighted model counting is identified as a possible route to PLF; translating existential DL axioms into ProbLog programs is non-trivial.Source: E Placing neuro-symbolic frameworks on… · p. 18
  • These are ceiling placements based on logical-layer expressivity; empirical placement also depends on training regime and coverage of contradictory and undetermined axioms.The evaluation pipeline accepts any scoring function, making experimental placement a stated extension of the work.Source: E Placing neuro-symbolic frameworks on… · pp. 17–18

F Dataset statistics

The evaluation splits distinguish entailed, contradictory, and undetermined candidates, with coverage depending on the ontology and normal form.

F Dataset statistics

  • Each split defines reasoner-generated entailed, contradictory, and undetermined candidate sets for evaluating L0–L3.The bounded Herbrand domain size |∆| is also reported for model counting.Source: F Dataset statistics · p. 18
  • Axiom counts exclude reflexive subsumptions and trivial axioms involving ⊤ or ⊥.Source: F Dataset statistics · p. 18
  • GO-plus has a full trichotomy only for GCI0 and GCI1⊥; Pizza has contradictory candidates for every normal form.For GO-plus GCI1, GCI2, and GCI3, only T+ and T? are defined and reduced metrics are reported.Source: F Dataset statistics · p. 18

G Full experimental results

Across the negative-sampling sweep, contradiction-only training lowers FVR at the endpoint in every model–construct setting, although the response is not monotone. Results also vary by logical construct: disjointness is handled faithfully, while conjunctive subsumption inverts.

G Full experimental results

  • The full results report metrics across models, normal forms, and datasets; geometric baselines cover GCI0 and GCI2, while other forms use reduced metrics.Source: G Full experimental results · p. 18

Multi-seed intervention-1 sweep

G Full experimental results

  • On Pizza, disjointness is the only construct handled faithfully, while conjunctive subsumption inverts, with AUC below 0.5 and negative ρP.The inversion is driven by the ball models’ loss.Source: Table 3 · p. 22
Loading 2609.27863v1…