Can You Tell the Difference? Contrastive Explanations for ABox Entailments

AI summary

Overview

Research area: Knowledge representation and reasoning — specifically explanation of reasoning over description logic (DL) ontologies, sitting at the intersection of explainable AI, ontological reasoning, and computational complexity theory.

Technical level: Advanced. The paper assumes familiarity with description logics (ℰℒ, ℰℒ⊥, 𝒜ℒ𝒞, 𝒜ℒ𝒞ℐ), model-theoretic semantics, ABox/TBox terminology, and complexity classes such as P, NP, coNP, ExpTime and coNExpTime.

Scope: The paper introduces contrastive ABox explanations — a formal account of "why is a an instance of C but b is not?" — and characterizes the computational complexity of verifying and computing such explanations across several DLs, variants and optimality criteria, plus a first implementation evaluated on generated problems over realistic knowledge bases.

What This Paper Is About

Existing explanation methods for DL knowledge bases answer why something is entailed (justifications, proofs, Craig interpolants) and why not something is entailed (abduction) separately. The authors argue that answering both questions jointly produces better explanations, because it forces the explanation to focus on what the fact individual and the foil individual have in common and where they differ, rather than giving two unrelated reasons. The paper formalizes this as the contrastive ABox explanation problem, studies its variants and optimality criteria, proves complexity results for lightweight and expressive DLs, and reports a first implemented method evaluated on generated problems.

Key Contributions

1. A new formal notion of contrastive ABox explanations (CEs). A CE is a tuple consisting of a commonality pattern q_com(x→), a difference pattern q_diff(x→), fact evidence c→, foil evidence d→, and a conflict set 𝒞, subject to five conditions (C1–C5) covering entailment of the fact, entailment of the foil, what the KB already provides, and subset-minimality of both the pattern and the conflict set. The framework also distinguishes a syntactic from a semantic variant (Definition 3), the latter allowing implicit, entailed information to appear in explanations.

2. A set of optimality criteria for choosing among CEs. Definition 6 introduces difference-minimality (the smallest difference), conflict-minimality (the smallest conflict set), and commonality-maximality (the largest commonality), each defined both with respect to the subset relation and with respect to cardinality.

3. A complexity characterization spanning five dimensions — variants, preference measures, types of optimality, DLs (ℰℒ, ℰℒ⊥, 𝒜ℒ𝒞, 𝒜ℒ𝒞ℐ) and concept types — summarized in Table 1, covering the verification problem "is this given CE optimal for this criterion?".

4. A first practical method and evaluation. The authors implemented a method for computing one variant of CEs and evaluated it on generated problems for realistic knowledge bases.

Main Findings

• Semantic CEs reduce to syntactic CEs in polynomial time. Lemma 5 shows that, given an entailment oracle for the DL, one can compute in polynomial time an extended ABox such that every semantic CE for the original problem is a syntactic CE for the new problem and vice versa. This is why most of the paper focuses on syntactic CEs.

• Every syntactic CE embeds into a polynomial-size "super-structure." Definition 7 builds a maximal candidate explanation E_m whose variables correspond to pairs of individual names from the ABox; Lemma 8 shows every syntactic CE without fresh individual names embeds into it. Two lemmas (Lemma 9 and Lemma 10) identify "safe" variable subsets that simultaneously guarantee the foil remains entailed and that the pattern stays consistent with the TBox.

• Difference-minimality is tractable under the subset criterion. Theorem 11 states that for any DL, given an entailment oracle, one can (1) compute a difference-minimal syntactic CE in polynomial time, and (2) decide difference-minimality of a given syntactic CE in polynomial time. This is achieved by a four-step procedure (P1–P4) that prunes the super-structure down while preserving the required entailments.

• Difference-minimality becomes intractable under cardinality minimization. Theorem 12: deciding whether a syntactic CE is difference-minimal with respect to cardinality is coNP-complete for ℰℒ and ℰℒ⊥, and ExpTime-complete for 𝒜ℒ𝒞. Hardness already holds for contrastive problems whose concept is a concept name.

• The same bounds hold for complex concepts and semantic CEs. Theorem 13: for contrastive problems with complex concepts, deciding cardinality-based difference-minimality of a given semantic CE is coNP-complete for ℰℒ/ℰℒ⊥ and ExpTime-complete for 𝒜ℒ𝒞.

• Conflict-minimality is harder and may require fresh individuals. Example 14 shows a conflict-free syntactic CE that needs a fresh individual in the foil evidence because the foil cannot otherwise satisfy the required pattern without creating a conflict. The paper reduces from signature-based (flat) ABox abduction (Definition 15), a problem also studied as instance query emptiness, to show that conflict-minimality may require exponentially many fresh individual names. Table 1 reports ExpTime-completeness for ℰℒ⊥ and coNExpTime-completeness for 𝒜ℒ𝒞/𝒜ℒ𝒞ℐ when fresh individuals are allowed; without fresh individuals, coNP-completeness for ℰℒ⊥ and ExpTime-completeness for 𝒜ℒ𝒞/𝒜ℒ𝒞ℐ.

• Commonality-maximality. Table 1 reports ExpTime-completeness for 𝒜ℒ𝒞/𝒜ℒ𝒞ℐ (Theorem 20); for ℰℒ⊥ the table lists an open case alongside a coNP-completeness result.

• ExpTime-hardness for 𝒜ℒ𝒞 holds in all cases by a reduction to entailment, as noted in the discussion following Table 1.

• Commonality-maximality matters even for concept-name concepts. Example 4 shows that when the concept in the problem is a concept name, a semantic explanation can always be produced trivially; commonality-maximality is what forces a more informative explanation (in that example, explaining that the foil did not need to be a professor).

• No specific experimental figures are reported in the provided text. The paper states only that a first method for computing one CE variant was implemented and evaluated on generated problems for realistic knowledge bases; full proofs and details of the experimental evaluation are placed in the technical appendix at the end of the PDF.

Methodology in Plain English

The authors start from a familiar setting: a knowledge base consisting of a TBox (general rules, e.g. "someone who is qualified and has published at a journal gets interviewed") and an ABox (concrete facts, e.g. "Alice published at AIJ", "AIJ is a journal"). They define a contrastive problem as a triple of a concept C plus a fact individual a that is an instance and a foil individual b that is not.

Rather than explaining the two cases separately, they explain them through a single ABox pattern — a set of assertions with variables in place of individuals — which is instantiated once for the fact and once for the foil. Part of the pattern is the commonality (what holds for both) and part is the difference (what only the fact has and the foil lacks). To keep explanations relevant, the instantiated pattern for the fact must be a subset-minimal set of assertions sufficient to entail C(a), and the conflict set — the facts about the foil that contradict the proposed difference — must be subset-minimal too.

Because different candidate explanations can differ in the fact evidence and foil evidence, the authors cannot simply fix the other components while optimizing one. Their technical device is a "super-structure" that contains all possible explanations over the ABox signature at once, and then a sequence of minimization steps (P1–P4) that shrink it while preserving the two key requirements: consistency with the TBox and entailment of the foil's concept assertion. For the complexity analysis, they reduce the verification questions — "is this explanation optimal?" — to standard entailment checks and, for the harder cardinality-based versions, to combinatorial problems whose known complexity they can borrow. Conflict-minimality is connected to ABox abduction and to instance query emptiness to transfer size bounds on fresh individuals. Finally, they implement one variant and test it on generated problems built from realistic ontologies.

Why This Matters

Impact on research. The paper opens a formal, complexity-theoretic line of work on contrastive explanation for description logic reasoning, complementing the separate literatures on justifications, proofs and interpolation for positive entailments, and on ABox, TBox, KB and concept abduction for missing entailments. It also supplies the first complexity map for verifying optimality of such explanations, which tells follow-up work which variants are worth implementing and which are provably hard. The connection drawn to Lipton's original notion of contrastive explanation and to counterfactual accounts in answer set programming and machine learning situates ABox explanation inside the broader explainable-AI landscape.

Real-world applications (the first two are the motivations the paper itself gives; the others follow from the setting):

• Concept learning: the paper notes that contrastive problems arise naturally when learning a concept from positive and negative examples, since CEs explain the learned concept in the light of one positive and one negative example.
• Medical domain: the paper mentions patient-history comparisons — seeing why a certain treatment is possible for one patient but not another.
• Decision and screening pipelines: the paper's running example is a hiring process that decides which candidates get an interview, where an explanation like "Alice's publication is at a journal and Bob's is not, and only Alice receives funding" is far more actionable to a rejected candidate than two separate, unrelated justifications.
• Ontology and knowledge-graph engineering: debugging ABox entailments by highlighting the smallest factual difference that separates a classified from an unclassified individual.

Industry relevance. Knowledge graphs and ontologies underpin data integration, biomedical data management and semantic search. When such systems classify or reject entities, tool builders need explanations that are cheap to verify. The paper's Theorem 11 result — polynomial-time computation and verification of difference-minimal explanations given an entailment oracle — is directly relevant to deployment, while the hardness results (coNP- and ExpTime-completeness, and the exponential fresh-individual requirement for conflict-free explanations) warn against promising conflict-free explanations as a default feature.

Future Directions

• Close the open case in Table 1. The complexity of commonality-maximality verification for ℰℒ⊥ is left open, so determining its exact complexity is a clear next step.

• Turn the theory into a scalable toolchain. The paper implements only one variant of CEs; extending the implementation to other optimality criteria — and studying whether the exponential fresh-individual blow-up for conflict-minimality can be mitigated in practice — is an obvious follow-up.

• Extend beyond ABox entailments. The authors restrict themselves explicitly to ABox reasoning; TBox and mixed KB entailments are natural generalizations, and the relationship to the existing TBox and KB abduction literature would need to be worked out.

• Broaden the experimental picture. The evaluation reported here is on generated problems for realistic knowledge bases; testing on naturally occurring ontologies and on the applications the paper motivates (concept learning, patient-history comparison) would show whether the contrastive format is useful to human readers, not just formally well behaved.

Target Audience

Researchers and graduate students in knowledge representation, description logic, and explainable AI; complexity theorists interested in explanation problems; and developers of ontology-based or knowledge-graph-based systems who need principled, verifiable explanations for classification outcomes. Readers should be comfortable with DL syntax and semantics and with standard complexity classes; the paper is not an introductory treatment of either.

Authors’ abstract

We introduce the notion of contrastive ABox explanations to answer questions of the type "Why is a an instance of C, but b is not?". While there are various approaches for explaining positive entailments (why is C(a) entailed by the knowledge base) as well as missing entailments (why is C(b) not entailed) in isolation, contrastive explanations consider both at the same time, which allows them to focus on the relevant commonalities and differences between a and b. We develop an appropriate notion of contrastive explanations for the special case of ABox reasoning with description logic ontologies, and analyze the computational complexity for different variants under different optimality criteria, considering lightweight as well as more expressive description logics. We implemented a first method for computing one variant of contrastive explanations, and evaluated it on generated problems for realistic knowledge bases.