CQD-SHAP: Explainable Complex Query Answering via Shapley Values

Researchers introduce CQD-SHAP, a framework that explains how neural models answer complex queries over incomplete knowledge graphs by computing the contribution of each query component using Shapley values from game theory. This approach addresses the black-box nature of existing complex query answering methods and demonstrates consistent effectiveness across multiple datasets.

CQD-SHAP represents a meaningful advancement in making knowledge graph reasoning systems more transparent and trustworthy. Complex query answering over incomplete knowledge graphs requires multi-hop reasoning—a task significantly more challenging than simple link prediction—yet existing neural and neurosymbolic methods operate largely as unexplainable black boxes, creating friction for adoption in high-stakes applications. This research bridges that gap by applying Shapley values, a foundational concept from cooperative game theory, to quantify how each component of a query contributes to ranking specific answers.

The framework builds on prior work like CQD (Complex Query Decomposition) but adds a critical explanatory layer. While CQD allows intermediate results to be tracked, it doesn't articulate why those results matter or how much weight each query part carries. CQD-SHAP addresses this by formally computing marginal contributions, satisfying all fundamental Shapley axioms—ensuring mathematical rigor and fairness in explanations. This matters because it demonstrates the value of neural inference on incomplete graphs versus purely symbolic approaches limited to existing facts.

For the AI and knowledge graph communities, this work has practical implications. Explainability is increasingly demanded in enterprise and scientific settings where decision-making depends on complex reasoning. The paper's automated evaluation methodology—testing necessary and sufficient explanations across multiple datasets and query types—suggests the approach generalizes well rather than optimizing for specific cases. The consistent effectiveness across diverse scenarios indicates this could become a standard approach for auditing and validating knowledge graph systems, particularly in domains where understanding reasoning chains matters more than raw accuracy.

• →CQD-SHAP applies game-theoretic Shapley values to explain neural complex query answering over incomplete knowledge graphs.
• →The framework quantifies each query component's contribution to answer rankings, addressing the black-box nature of existing CQA methods.
• →Automated evaluation demonstrates consistent effectiveness across multiple datasets and query types.
• →The approach mathematically satisfies all fundamental Shapley axioms, ensuring principled and fair explanations.
• →Explainability advances enable deployment of sophisticated reasoning systems in high-stakes domains requiring auditable decision-making.