🤖 machine learning

CQD-SHAP: Explainable Complex Query Answering via Shapley Values

The paper proposes CQD-SHAP, a novel framework that leverages Shapley values from cooperative game theory to provide explainable complex query answering over incomplete knowledge graphs by quantifying the contribution of each query part to answer rankings, thereby addressing the interpretability limitations of existing black-box and neurosymbolic models.

Original authors: Parsa Abbasi, Stefan Heindorf

Published 2026-06-23

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Parsa Abbasi, Stefan Heindorf

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

The Big Picture: The "Black Box" Detective

Imagine you have a giant, messy library (a Knowledge Graph) where books are connected by strings. Sometimes, the library is missing pages or entire books (it's incomplete).

When you ask a simple question like, "Who wrote Harry Potter?", a computer can usually find the answer by just walking along the strings. But what if you ask a complex question like, "Which drugs treat diabetes AND cause kidney toxicity?"

To answer this, the computer has to do two things:

Walk the strings (Symbolic approach): Look for drugs that definitely treat diabetes and definitely cause kidney toxicity in the existing library.
Guess the missing links (Neural approach): Since the library is incomplete, the computer uses a "smart guesser" (a neural network) to infer connections that should be there but aren't written down yet.

The problem? The "smart guesser" is a black box. It gives you a list of answers (like "Insulin"), but it doesn't tell you why it picked that answer. Did it pick Insulin because the library explicitly said so? Or did it guess it because the computer thinks Insulin is related to kidney toxicity, even though that fact is missing from the library?

CQD-SHAP is a new tool designed to open that black box and explain exactly how much each part of the question contributed to the final answer.

The Core Idea: The "Team Score" Analogy

The authors use a concept from game theory called Shapley Values. Think of it like a group project where a team of students (the atoms of the question) works together to get a grade (the ranking of the answer).

In our example question ("Drugs for diabetes AND kidney toxicity"), there are two "students" (atoms):

Student A: "Drugs for diabetes."
Student B: "Drugs for kidney toxicity."

The final grade (the ranking of "Insulin") depends on how well both students perform. But how much credit does Student A deserve versus Student B?

CQD-SHAP acts like a fair referee. It runs thousands of mini-experiments to figure out the score:

Scenario 1: Student A does the work using the "Library Walk" (Symbolic), and Student B uses the "Smart Guesser" (Neural).
Scenario 2: Student A uses the "Smart Guesser," and Student B uses the "Library Walk."
Scenario 3: Both use the "Library Walk."
Scenario 4: Both use the "Smart Guesser."

By comparing these scenarios, CQD-SHAP calculates exactly how much the "Smart Guesser" improved the final grade for each student.

The "Aha!" Moment: Why This Matters

The paper claims that this method reveals something surprising. Sometimes, the "Smart Guesser" is doing all the heavy lifting, and sometimes it's actually hurting the result.

The Analogy of the "Noisy Neighbor":
Imagine you are trying to find a specific house (the answer).

The Library Walk is like reading the official address book. It's accurate but might not have the house listed if the book is old.
The Smart Guesser is like asking a neighbor who knows the area. They might know the house exists even if it's not in the book.

CQD-SHAP might tell you:

"For the answer 'Insulin', the 'Kidney Toxicity' part of your question got a massive boost (+450 points) because the Smart Guesser guessed the connection. However, the 'Diabetes' part actually got a slight penalty (-10 points) because the Smart Guesser got confused and suggested some wrong neighbors."

Without CQD-SHAP, you would just see "Insulin" at the top of the list and assume the computer is 100% sure. With CQD-SHAP, you realize: "Wait, the computer is mostly guessing on the kidney part. I should double-check that fact."

How They Tested It (The "Stress Test")

The authors tested this on real-world datasets (like Freebase and NELL) using various types of complex questions (some with "ANDs", some with "ORs").

They compared their method against other ways of guessing which part of the question was important (like picking the first part, the last part, or the part with the lowest score).

The Results:

Necessary Explanations: If you remove the "Smart Guesser" from the most important part of the question, the answer's rank should drop significantly. CQD-SHAP was much better at identifying these critical parts than the other methods.
Sufficient Explanations: If you only use the "Smart Guesser" on the most important part, the answer's rank should go up significantly. Again, CQD-SHAP won.

In simple terms: CQD-SHAP is the only method that consistently points to the right part of the question to explain why an answer is ranked high or low.

Key Takeaways

It's not just about the answer; it's about the "Why": It explains why a complex query returned a specific result by breaking down the contribution of each logical step.
It measures "Guessing Power": It specifically quantifies how much the neural network's ability to "guess" missing facts helped (or hurt) the final ranking compared to just looking at existing facts.
It's mathematically fair: It uses a rigorous mathematical formula (Shapley Values) to ensure the "credit" is distributed fairly among the parts of the question.
It catches errors: It can reveal when a high-ranking answer is actually based on a weak or noisy guess, helping users trust the system less blindly.

What It Is NOT (Based strictly on the paper)

It does not claim to cure diseases or diagnose patients. The "drug" example is just a metaphor for how the system works.
It does not say this will replace doctors or lawyers. It is a tool to help understand how an AI model is thinking.
It does not claim to solve the "black box" problem for all AI, only for this specific type of complex question-answering system.

In summary, CQD-SHAP is a transparency tool that acts like a "scorecard" for AI detectives, showing you exactly which clues (query parts) were real facts and which were smart guesses, so you know who to trust.

Technical Summary: CQD-SHAP

Problem Statement

Complex Query Answering (CQA) on Knowledge Graphs (KGs) extends beyond simple link prediction to handle queries requiring multi-hop reasoning and logical operators (conjunction, disjunction). While neurosymbolic approaches like CQD (Complex Query Decomposition) have emerged to address the incompleteness of real-world KGs by inferring missing links, they function largely as black-box models. Existing explainability methods for link prediction focus on identifying important triples or paths for single-hop predictions and do not directly apply to complex queries. Furthermore, current neurosymbolic CQA methods lack transparency regarding the specific contribution of different query components (atoms) to the final ranking of an answer. This opacity hinders user trust, debugging, and the ability of domain experts to identify gaps in the KG or refine queries.

Methodology: CQD-SHAP

The paper proposes CQD-SHAP, a framework that explains the results of neurosymbolic CQA models (specifically CQD) by quantifying the contribution of each query atom to the ranking of a specific answer entity using Shapley values from cooperative game theory.

Core Definitions

Players: The atoms (constituent parts) of a complex query $Q$ are treated as players in a cooperative game.
Coalitions: A subset of atoms $S$ is executed using the neural approach (inferring missing links via a link predictor), while the remaining atoms are executed using a symbolic approach (relying strictly on observed facts in the KG).
Value Function: The value of a coalition $S$ $S$ for a target entity $e_i$ $e_{i}$ is defined by the $\Delta$ Rank Quantity of Interest (QoI). This measures the improvement in the ranking position of $e_i$ $e_{i}$ when the atoms in $S$ $S$ are executed neurally compared to a purely symbolic execution of the entire query.
- Formally: $val_{e_i}(Q_S) = r_i(Q_{\emptyset}) - r_i(Q_S)$ , where $r_i$ is the rank of entity $e_i$ in a filtered setting.
Shapley Value Calculation: The contribution of a specific atom $a$ is calculated as the average marginal contribution of that atom across all possible coalitions of other atoms. This satisfies fundamental Shapley axioms, including efficiency (the sum of all atom contributions equals the total rank improvement gained by full neural execution).

Execution Details

Neural Execution: Uses a link predictor (e.g., from CQD) to assign scores to entities, allowing inference over incomplete graphs.
Symbolic Execution: Performs graph traversal on the observed (incomplete) KG, assigning constant scores to existing facts and low scores to non-existent ones.
Exact Computation: Due to the small number of atoms in complex queries (typically $\le 4$ ), the paper computes exact Shapley values without approximation.

Key Contributions

First Shapley-based Explanation for CQA: To the authors' knowledge, this is the first approach to explain neural complex query answering models using Shapley values.
Formal Definition of Atom-Level Explanations: The paper defines a formal explanation framework at the level of query atoms, distinguishing it from triple-level or path-level explanations used in link prediction.
Novel Metric (CQD-SHAP): Introduces a method to quantify how much the neural execution of a specific atom contributes to the ranking of a target answer compared to symbolic execution.
Redefinition of Evaluation Criteria: Extends the concepts of Necessary and Sufficient explanations from link prediction to the CQA domain:
- Necessary: Replacing the most important atom with symbolic execution causes a significant drop in the answer's ranking (measured by $\Delta$ MRR).
- Sufficient: Executing only the most important atom neurally (while others are symbolic) significantly improves the ranking compared to a fully symbolic baseline.

Experimental Results

The authors evaluated CQD-SHAP on FB15k-237, NELL995, and their harder variants (+H) across various query types (projections, intersections, unions).

Performance: CQD-SHAP consistently outperformed all baselines (First, Last, Random, and Score-based selection) in both necessary and sufficient evaluation scenarios.
- In the Necessary scenario, CQD-SHAP reduced Mean Reciprocal Rank (MRR) by up to 45.70% (for 2u queries on NELL995), significantly more than the best baseline.
- In the Sufficient scenario, it increased MRR by up to 58.90% (for 2u queries on NELL995+H).
Query Structure Sensitivity: The method demonstrated higher effectiveness for intersection queries (e.g., 3i, 4i) compared to projection queries. The authors attribute this to the structural nature of intersections (using t-norms), where a single critical branch acts as a strong filter, whereas projection queries often have alternative paths.
Efficiency: Despite the NP-hard nature of Shapley values, the small number of atoms allowed for exact computation with low latency (average ~30–140 ms per query-answer pair depending on the dataset).
Insight: The analysis revealed that the most important atom is not always a "missing link." In some cases, an atom corresponding to an existing fact in the KG can be the primary driver of the ranking due to embedding proximity or noise introduced by neural execution of other parts.

Significance and Claims

The paper claims that CQD-SHAP provides a mathematically rigorous and effective way to interpret neurosymbolic query answering. By satisfying Shapley axioms, it ensures a fair attribution of credit to query components. The authors assert that this approach:

Helps domain experts identify gaps in KGs by revealing which query parts rely heavily on inferred knowledge.
Assists in debugging queries by showing which atoms most influence the final ranking.
Provides a transparent view of how neural predictors leverage incomplete data compared to symbolic retrieval.

The authors explicitly state that this is the first work to apply Shapley values to explain complex query answering results, moving beyond the limitations of existing link prediction explanation methods. They note that while the current work focuses on local explanations (single answer), future directions include global explanations and natural language generation to make these values human-readable.