CQD-SHAP: Explainable Complex Query Answering via Shapley Values

AI summary

Overview

Research area: Explainable AI for knowledge graph reasoning, specifically complex query answering (CQA) over incomplete knowledge graphs using neurosymbolic models and Shapley values from cooperative game theory. Authored by Parsa Abbasi and Stefan Heindorf at Paderborn University, Germany.

Technical level: Intermediate. The paper is formal (defining a cooperative game, Shapley values, and rank-based value functions) but the core idea is intuitive: treat each part of a query as a "player" and measure how much each one contributes to an answer's rank.

Scope: The paper introduces CQD-SHAP, a framework that assigns a Shapley value to every atom of a complex query, quantifying how much using a neural link predictor for that atom improves the ranking of a specific answer entity compared to answering it symbolically.

What This Paper Is About

Neural and neurosymbolic complex query answering (CQA) models can answer multi-hop logical queries over incomplete knowledge graphs (KGs), but they behave like black boxes — it is unclear why one answer outranks another. Existing explanation methods for link prediction identify important triples in the KG, but they are not designed for complex queries, where the relevant evidence may differ across parts of the query.

The paper's goal is to explain CQA results at the level of query atoms (the individual constituent projections of a query), revealing which atoms most strongly drive the ranking of a given answer because a neural model inferred missing knowledge for them.

Key Contributions

1. The authors state this is the first approach to explaining the results of neural complex query answering models using Shapley values.
2. A formal definition of explanation for the CQA task at the level of query atoms.
3. CQD-SHAP itself, which quantifies the contribution of using a neural model for each query atom to the ranking of a target answer.
4. Comprehensive experiments on FB15k-237, NELL995, and their harder variants (FB15k-237+H, NELL995+H), evaluating explanations via necessity and sufficiency criteria across query types.

All resources are publicly available in the authors' GitHub repository.

Main Findings

• CQD-SHAP outperforms all baselines in every case. Across the studied datasets and query types, selecting the atom with the highest Shapley value for a different execution was more effective than the First, Last, Random, and Score-based baselines in both the necessary and sufficient evaluation scenarios.

• Range of effects. Considering all datasets, CQD-SHAP explanations reduce MRR by between 2.24% (for 3p on FB15k-237+H) and 45.70% (for 2u on NELL995) in the necessary scenario, and increase MRR by between 2.31% (for 4p on FB15k-237+H) and 58.90% (for 2u on NELL995+H) in the sufficient scenario.

• Largest gains over the best baseline. For 3i queries on FB15k-237, the best baseline (Score) achieves -22.42% necessary and +23.49% sufficient, while CQD-SHAP reaches -37.14% and +42.27% — an additional decrease of 14.72 percentage points and an additional increase of 18.78 percentage points. On NELL995, the additional decrease and increase over the best baseline (Score) are 13.72 and 15.18 percentage points.

• Harder benchmarks show smaller absolute effects. On the +H variants, absolute ΔMRR values are generally smaller. The paper explains this by noting that in the standard benchmarks many 3p queries have only one missing link, whereas in the harder benchmarks only a subset of queries is reducible this way and others require two or all links to be inferred, so modifying a single atom has a smaller effect.

• Intersection queries are explained more effectively than projection queries. For example, on FB15k-237 the necessary and sufficient metrics for 3p are -11.14% and +26.68%, versus -37.14% and +42.27% for 3i. On the harder variant, the corresponding values are -2.24% and +2.43% for 3p and -9.07% and +6.04% for 3i.

• Single-level query types collapse some baselines. Because 2u, 2i, 3i, and 4i queries have only one level of atoms, the First and Last baselines coincide with Random for those types.

• Efficiency gives a verifiable sum. The sum of Shapley values over all atoms for a given answer equals the difference in that answer's rank between fully neurosymbolic execution and purely symbolic execution.

Methodology in Plain English

The work builds on CQD, a neurosymbolic complex query answering model that decomposes a query into atomic link predictions (neural execution) and combines their scores with fuzzy logic operations — t-norms for conjunctions and t-conorms for disjunctions.

CQD-SHAP treats each atom of a query as a player in a cooperative game. For any subset (coalition) of atoms, a "partial query" is constructed in which atoms inside the subset are answered using the neural link predictor and atoms outside it are answered symbolically by simply looking up facts in the observed graph. When a symbolic atom is executed, entities connected via that relation receive a constant score of 1 while all others receive a low score close to 0; if the atom does not contain the target variable, the top-k candidates are returned, matching CQD's beam search behavior. The observed graph used for symbolic execution is the validation graph when a test query is being explained, and the training graph when a validation query is being explained.

The value of a coalition is a Quantity of Interest (QoI) called ΔRank: the difference between the rank of the target answer under the partial query and its rank under the fully symbolic query. This anchors the empty coalition at zero, as the Shapley framework requires. Following the filtered evaluation setting, rankings exclude all easy answers (answers reachable symbolically on the observed graph) and all hard answers except the current target. The authors adopt the QoI definitions of Pliatsika et al., which have been shown to satisfy the fundamental Shapley axioms, and note that because the number of atoms in a complex query is relatively small, exact Shapley values can be computed without approximation.

The authors evaluate explanations in two ways, extending necessity and sufficiency notions from link prediction. A necessary explanation means that executing the single most important atom symbolically makes the hard answer drop in the ranking, measured by the decrease in MRR. A sufficient explanation means that executing only the most important atom neurally increases MRR compared to a fully symbolic baseline. Unlike prior work, they evaluate all query–answer pairs rather than restricting to cases where the model already ranks the target at the top (necessary) or fails to do so (sufficient), making the evaluation more rigorous. Baselines include First (randomly choosing an anchor-containing atom), Last (randomly choosing an atom containing the target variable), Random, and Score-based (choosing the atom with the lowest link prediction score, except for union queries such as 2u and 2u1p, where the higher score between the union atoms is selected to reflect t-conorm behavior).

The paper also motivates the approach with an example: for the query "Which drugs are prescribed for diabetes and cause kidney toxicity?", the method might assign a contribution score of +10 to the first atom and +450 to the second, indicating the latter drove the high rank of the answer Insulin far more.

Why This Matters

Impact on research. The paper opens a new explanation target for knowledge graph reasoning: rather than asking which triples in the KG matter, it asks which parts of a query matter. It connects Shapley-value research on ranking and retrieval (RankingSHAP, RankSHAP, and the QoI framework of Pliatsika et al.) to neurosymbolic query answering, and it argues that existing explainable link prediction methods (Kelpie, CRIAGE, Power-Link, PaGE-Link) are not directly applicable to complex queries because these require multiple projections whose contributions interact. The authors note that no prior work directly attempted to explain complex query answering over KGs, though Shapley values have been used to explain database facts or tuples rather than queries themselves.

Real-world applications.

• Drug safety and pharmacology: the paper's running example shows how a user could see whether a drug's high rank came from its genuine indication (prescribed for diabetes) or from a misleading association (causing kidney toxicity).
• Knowledge graph curation: explanations help domain experts identify gaps in the KG by revealing which parts of a query rely most strongly on inferred knowledge.
• Query debugging: users and domain experts can see which atoms most influence a final ranking, supporting debugging and refinement of queries.
• Model development: data scientists can use atom attributions to debug and improve complex query answering models.

Industry relevance. The paper touches on trust concerns around black-box models, which matter for enterprise and biomedical KG deployments where both performance and transparency are required. The concrete statistics given illustrate the scale of the underlying problem: in Freebase, among more than 3 million persons, only 25% have a recorded nationality and only 6% have information about their parents; in Wikidata, only 50% of artists have a recorded place of birth. Because CQD-SHAP builds on CQD, it can be applied to derived methods such as CQD^A and QTO, which differ mainly in score normalization or search pruning strategies.

Future Directions

• Extending to other neurosymbolic CQA models. The authors state that CQD-SHAP can explain the outputs of models such as CQD^A and QTO in a similar manner, but a systematic evaluation across such models is not reported.
• Scaling beyond small queries. Exact Shapley values are feasible because complex queries contain relatively few atoms; how the framework would need approximation strategies for queries with many more atoms is not addressed.
• Combining atom-level and triple-level explanations. The paper distinguishes its atom-level explanation from triple-level explainable link prediction and notes that its approach is partially related to path-based methods, leaving open how the two views could be combined.
• Human evaluation of the explanations. The paper motivates its explanations through domain-expert use cases but evaluates them automatically via necessity and sufficiency, so user studies on whether the attributions actually help experts are not reported.

Target Audience

Researchers and practitioners in explainable AI, knowledge graph reasoning, and neurosymbolic methods who want to understand attributions at the query-component level rather than at the triple level. It is also relevant to applied scientists working with incomplete KGs in biomedical, search, or enterprise settings who need to audit why a particular entity is returned. Readers should be comfortable with embeddings, logical query decomposition, and the basic idea of Shapley values; the more detailed dataset statistics, implementation and hyperparameter settings, formal evaluation definitions, and the case study are deferred to the paper's appendices.

Authors’ abstract

Complex query answering (CQA) goes beyond the widely studied link prediction task by addressing more sophisticated queries that require multi-hop reasoning over incomplete knowledge graphs (KGs). Research on neural and neurosymbolic CQA methods is still an emerging field. Almost all of these methods can be regarded as black-box models, which may raise concerns about user trust. Although neurosymbolic approaches like CQD are slightly more interpretable, allowing intermediate results to be tracked, the importance of different parts of the query remains unexplained. In this paper, we propose CQD-SHAP, a novel framework that computes the contribution of each query part to the ranking of a specific answer. This contribution explains the value of leveraging a neural predictor that can infer new knowledge from an incomplete KG, rather than a symbolic approach relying solely on existing facts in the KG. CQD-SHAP is formulated based on Shapley values from cooperative game theory and satisfies all fundamental Shapley axioms. Automated evaluation of these explanations in terms of necessary and sufficient explanations, and comparisons with various baselines, show the consistent effectiveness of this approach across all studied datasets and query types.