🤖 AI

Rethinking Explanations: Formalizing Contrast in Description Logics

This paper proposes a user-centered framework for contrastive explanations in Description Logics that addresses the limitations of existing justification and abductive reasoning methods by formally defining and evaluating how to explain why a fact holds true instead of an alternative foil.

Original authors: Yasir Mahmood, Arnab Sharma, Axel-Cyrille Ngonga Ngomo, Balram Tiwari

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yasir Mahmood, Arnab Sharma, Axel-Cyrille Ngonga Ngomo, Balram Tiwari

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking through a giant, magical library where every book represents a rule about how the world works. This library is built on a very strict, logical language called Description Logic (DL). In this library, a computer can look at a person (let's call him Alice) and a set of rules, and it can tell you, "Yes, Alice is hired!"

The Old Way: "Why?"

Usually, if you ask the computer, "Why is Alice hired?", it gives you a Justification. It pulls out the specific pages from the library that prove Alice is hired.

Analogy: It's like a teacher showing you the exact steps in a math problem to prove the answer is 5. It's accurate, but it only tells you about the "winner."

The New Problem: "Why Alice and not Bob?"

The authors of this paper noticed something humans do naturally: we don't just want to know why something happened; we want to know why it happened instead of something else.

Imagine Alice gets the job, but her friend Bob doesn't.

If you ask, "Why Alice?", the computer lists Alice's great skills.
If you ask, "Why not Bob?", the computer lists Bob's missing skills.
But Bob is confused. He doesn't want two separate lists. He wants to know: "Why Alice and not me?" He wants to see the difference between them.

The paper argues that giving two separate answers is unsatisfying. You need a Contrastive Explanation (CE) that highlights the specific gap between the two.

The Solution: The "Difference Finder"

The researchers created a new way to formalize this "Why P instead of Q?" question. They call the thing that happened the Fact (Alice) and the thing that didn't happen the Foil (Bob).

To explain the difference, they look at three things:

What Alice had that Bob didn't: (e.g., Alice published in AI).
What Bob had that Alice didn't: (e.g., Bob published in pure Math).
What Bob was missing that would have made him hired: (e.g., Bob needed to publish in AI).

The Creative Analogy: The Race
Imagine a race between Alice and Bob.

Fact: Alice won.
Foil: Bob lost.
Old Explanation: "Alice ran fast." (True, but doesn't explain why Bob lost).
New Contrastive Explanation: "Alice ran fast because she trained on hills, whereas Bob trained on flat ground. If Bob had trained on hills (the missing piece), he would have won, but he didn't."

The paper formalizes this by taking the "proof" for Alice and the "proof" for Bob (even though Bob's proof is hypothetical) and finding the symmetric difference. They strip away the things both of them share (like "both are qualified") and focus only on the unique factors that decided the outcome.

The "What If" Scenario (Abduction)

Sometimes, the computer has to guess what would make the Foil true. This is called Abduction.

Analogy: If Bob didn't get hired, the computer asks, "What would have to be true for Bob to get hired?" It might say, "If Bob had published in AI."
The paper's method combines the real proof for Alice with this "what if" scenario for Bob to show exactly where the paths diverged.

Handling Glitches (Inconsistencies)

Sometimes, the rules in the library are tricky. What if the rules say "You can't be an AI Expert and a Theorist at the same time"?

If Bob is a Theorist, and the computer says, "If Bob were an AI Expert, he would be hired," there is a conflict.
The paper adds a safety net: it identifies these conflicts. It tells you, "Bob would be hired if he were an AI Expert, BUT that contradicts his nature as a Theorist." This prevents the explanation from breaking the logic of the library.

What They Actually Did

The authors didn't just write theory; they built a prototype (a working computer program) to test this.

They tested it on about 40 different real-world knowledge bases (like medical or technical databases).
They found that their method works quickly (in less than a second for most cases) and produces very short, easy-to-read explanations (usually just 1 or 2 sentences of logic).
They proved mathematically that for certain types of logic (called EL), this process is efficient and doesn't get stuck in an endless loop.

Summary

This paper is about upgrading how computers explain decisions. Instead of just saying "Here is why X happened," they now say, "Here is why X happened instead of Y." They do this by mathematically comparing the "winning" evidence with the "losing" (or hypothetical) evidence, stripping away the common parts, and showing you exactly what made the difference. They built a tool to do this, and it works fast and accurately on complex data.

Technical Summary: Rethinking Explanations: Formalizing Contrast in Description Logics

Problem Statement
Existing explanation formalisms for Description Logic (DL) knowledge bases (KBs) primarily focus on justifications (explaining why an axiom $P$ is true) and abductive reasoning (explaining why a missing axiom $P$ could be true). However, these approaches lack a user-centered perspective. They fail to address the specific cognitive needs of an inquirer who is often surprised by a fact $P$ because they anticipated an alternative event $Q$ . Providing separate explanations for "why $P$ " and "why not $Q$ " is often unsatisfactory, as users seek to understand the specific difference between the actual outcome and the expected alternative. While contrastive explanations (CEs) are well-studied in machine learning and argumentation frameworks, they remain largely unexplored in the context of DLs, despite DLs being the foundation for ontologies like OWL used in critical domains such as healthcare (e.g., SNOMED CT).

Methodology
The authors propose a formal framework for generating contrastive explanations within DL KBs, adapting Peter Lipton's philosophical model of contrastive explanation to the logical setting of DLs.

Formalization of Contrastive Questions (CQs):
A CQ is defined as a pair $(P, Q)$ where $P$ is a fact (an entailed ABox assertion, e.g., $C(x)$ ) and $Q$ is a foil (a non-entailed assertion). The paper focuses on two specific types of foils:
- Entity Contrasts: $Q$ is $C(y)$ , contrasting the same concept against a different individual.
- Concept Contrasts: $Q$ is $D(x)$ , contrasting a different concept for the same individual.
Defining the Contrastive Explanation (CE):
The authors move beyond a simple symmetric difference between the justification of $P$ and the abductive hypothesis for $Q$ . They introduce a tuple-based definition $E = \langle E_{fact}, E_{foil+}, E_{foil-} \rangle$ (and optionally a conflict set $C$ ) based on three principles:
- Difference Condition: The explanation must cite the difference between the reasons for $P$ and the missing facts for $Q$ .
- Known vs. Assumed Knowledge: The explanation must distinguish between axioms that are true in the KB regarding the foil ( $E_{foil+}$ ) and the missing axioms required to entail the foil ( $E_{foil-}$ ).
- Accounting for Similar Axioms: The framework introduces a "renamed set difference" operator ( $\ddagger$ ). This operator removes axioms that are structurally similar between the fact and foil (e.g., $C(x)$ and $C(y)$ , or $E \sqsubseteq C$ and $E \sqsubseteq D$ ) to ensure the explanation highlights only the distinguishing factors.
Handling Inconsistencies:
If adding the missing axioms for the foil ( $E_{foil-}$ ) creates a conflict with the existing KB, the framework includes a conflict set $C$ . This set represents the minimal subset of existing ABox assertions that must be removed to make the foil entailed, effectively modeling a counterfactual scenario.
Preference Criteria:
To select among multiple possible CEs, the authors propose a syntactic divergence metric ( $\sigma_{div}$ ). This metric measures the symmetric difference between the axioms relevant to the fact and those relevant to the foil. A preferred CE is one that minimizes this divergence, aligning the reasoning structures of the fact and foil as closely as possible to facilitate comparison.

Key Contributions

Formal Definitions: The paper provides the first formal definitions of contrastive explanations for DL KBs, specifically addressing both entity and concept contrasts.
General Scheme: It presents a general scheme for CEs that integrates justifications and abductive hypotheses while distinguishing between true and missing assertions.
Complexity Analysis: The authors analyze the computational complexity of CEs in two DLs:
- $\mathcal{EL}$ : They prove that deciding the existence of a CE of a given size is NP-complete for concept contrasts. However, for entity contrasts, a $\sigma_{div}$ -preferred CE (with divergence 0) can be computed in polynomial time.
- $\mathcal{ALC}$ : The problem of deciding the existence of a CE of a given size is shown to be ExpTime-complete.
Implementation and Evaluation: A prototype implementation in Java (using OWL API and ELK reasoner) was developed. Experiments were conducted on approximately 41 real-world OWL KBs.

Results
The experimental evaluation yielded the following findings:

Efficiency: The prototype computes CEs efficiently, with an average runtime of approximately 392 ms.
Explanation Size: The generated explanations are compact, typically spanning up to four ABox axioms.
Commonality: The "Common Axioms ratio" (the overlap between fact and foil justifications) was found to be low (average 13.5%), suggesting that in many cases, the fact and foil rely on distinct sets of assertions.
Consistency: The conflict rate was low (4.00%), indicating that in most cases, the missing axioms for the foil do not contradict the existing KB.

Significance and Claims
The paper claims to bridge a significant gap in the literature by introducing contrastive explanations to the domain of Description Logics. The authors argue that this approach offers a more intuitive and user-centered way to explain reasoning outcomes by explicitly modeling the inquirer's expectations (the foil).

The work is presented as a preliminary step in this area. The authors modestly note that while their definitions extend to any DL supporting abductive hypotheses, further work is needed to handle more expressive DLs (e.g., with cardinality restrictions) and to develop algorithms that scale efficiently to large datasets. They also identify the need for future user studies to validate whether these contrastive explanations are indeed preferred over standard justifications by end-users. The paper concludes that their framework provides a rigorous, formal mechanism for combining justifications to explain the difference between a fact and a foil, laying the groundwork for more informed decision-making in semantic web applications.