# CQD-SHAP: Explainable Complex Query Answering via Shapley Values

arXiv: https://arxiv.org/abs/2510.15623 · HTML: https://mlsanity.com/paper/2510.15623/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 22 of its 40 references that are in the map.
- First posted on arXiv 17 Oct 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 22 of 22)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings](https://mlsanity.com/paper/2002.05969/) (2020)
- [Embedding Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/1806.01445/) (2018)
- [Complex Query Answering with Neural Link Predictors](https://mlsanity.com/paper/2011.03459/) (2020)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization](https://mlsanity.com/paper/2212.09567/) (2022)
- [Logical Message Passing Networks with One-hop Inference on Atomic Formulas](https://mlsanity.com/paper/2301.08859/) (2023)
- [Investigating Robustness and Interpretability of Link Prediction via Adversarial Modifications](https://mlsanity.com/paper/1905.00563/) (2019)
- [PaGE-Link: Path-based Graph Neural Network Explanation for Heterogeneous Link Prediction](https://mlsanity.com/paper/2302.12465/) (2023)
- [The Shapley Value of Tuples in Query Answering](https://mlsanity.com/paper/1904.08679/) (2019)
- [Adapting Neural Link Predictors for Data-Efficient Complex Query Answering](https://mlsanity.com/paper/2301.12313/) (2023)
- [Computing the Shapley Value of Facts in Query Answering](https://mlsanity.com/paper/2112.08874/) (2021)
- [Path-based Explanation for Knowledge Graph Completion](https://mlsanity.com/paper/2401.02290/) (2024)
- [Message Passing Query Embedding](https://mlsanity.com/paper/2002.02406/) (2020)
- [Is Complex Query Answering Really Complex?](https://mlsanity.com/paper/2410.12537/) (2024)
- [LitCQD: Multi-Hop Reasoning in Incomplete Knowledge Graphs with Numeric Literals](https://mlsanity.com/paper/2304.14742/) (2023)
- [RankingSHAP -- Listwise Feature Attribution Explanations for Ranking Models](https://mlsanity.com/paper/2403.16085/) (2024)
- [RankSHAP: Shapley Value Based Feature Attributions for Learning to Rank](https://mlsanity.com/paper/2405.01848/) (2024)
- [Shapley Value Computation in Ontology-Mediated Query Answering](https://mlsanity.com/paper/2407.20058/) (2024)
- [ShaRP: Explaining Rankings and Preferences with Shapley Values](https://mlsanity.com/paper/2401.16744/) (2024)
- [Enriching Wikidata with Linked Open Data](https://mlsanity.com/paper/2207.00143/) (2022)

## Abstract (arXiv)

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.