CQD-SHAP: Explainable Complex Query Answering via Shapley Values

• URL: http://arxiv.org/abs/2510.15623v1
• Date: Fri, 17 Oct 2025 13:09:26 GMT
• Title: CQD-SHAP: Explainable Complex Query Answering via Shapley Values
• Authors: Parsa Abbasi, Stefan Heindorf,
• Abstract summary: Complex query answering (CQA) goes beyond the well-studied link prediction task.<n>We propose CQD-SHAP, a novel framework that computes the contribution of each query part to the ranking of a specific answer.
• Score: 2.015325869229528
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Complex query answering (CQA) goes beyond the well-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 the fundamental Shapley axioms. Automated evaluation of these explanations in terms of necessary and sufficient explanations, and comparisons with various baselines, shows the effectiveness of this approach for most query types.

Related papers

• The benefits of query-based KGQA systems for complex and temporal questions in LLM era [55.20230501807337]
  Large language models excel in question-answering (QA) yet still struggle with multi-hop reasoning and temporal questions.<n> Query-based knowledge graph QA (KGQA) offers a modular alternative by generating executable queries instead of direct answers.<n>We explore multi-stage query-based framework for WikiData QA, proposing multi-stage approach that enhances performance on challenging multi-hop and temporal benchmarks.
  arXiv  Detail & Related papers  (2025-07-16T06:41:03Z)
• Transformers for Complex Query Answering over Knowledge Hypergraphs [48.55646194244594]
  Triple KGs, as the classic KGs composed of entities and relations of arity 2, have limited representation of real-world facts.<n>We propose a two-stage transformer model, the Logical Knowledge Hypergraph Transformer (LKHGT), which consists of a Projection for atomic projection and a Logical for complex logical operations.<n> Experimental results on CQA datasets show that LKHGT is a state-of-the-art CQA method over KHG and is able to generalize to out-of-distribution query types.
  arXiv  Detail & Related papers  (2025-04-23T09:07:21Z)
• Shapley Value Computation in Ontology-Mediated Query Answering [3.1952340441132474]
  The Shapley value, originally introduced in cooperative game theory for wealth distribution, has found use in KR and databases. We present a detailed complexity analysis of Shapley value computation (SVC) in the query answering setting.
  arXiv  Detail & Related papers  (2024-07-29T14:45:14Z)
• Adapting Neural Link Predictors for Data-Efficient Complex Query Answering [45.961111441411084]
  We propose a parameter-efficient score emphadaptation model optimised to re-calibrate neural link prediction scores for the complex query answering task. CQD$mathcalA$ produces significantly more accurate results than current state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-01-29T00:17:16Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  We propose a framework for complex query answering that decomposes the Knowledge Graph embeddings from neural set operators. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning. Our approach yields the new state-of-the-art neural CQA model.
  arXiv  Detail & Related papers  (2023-01-21T02:34:06Z)
• UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph [89.98762327725112]
  Multi-hop Question Answering over Knowledge Graph(KGQA) aims to find the answer entities that are multiple hops away from the topic entities mentioned in a natural language question. We propose UniKGQA, a novel approach for multi-hop KGQA task, by unifying retrieval and reasoning in both model architecture and parameter learning.
  arXiv  Detail & Related papers  (2022-12-02T04:08:09Z)
• Neural-Symbolic Entangled Framework for Complex Query Answering [22.663509971491138]
  We propose a Neural and Entangled framework (ENeSy) for complex query answering. It enables the neural and symbolic reasoning to enhance each other to alleviate the cascading error and KG incompleteness. ENeSy achieves the SOTA performance on several benchmarks, especially in the setting of the training model only with the link prediction task.
  arXiv  Detail & Related papers  (2022-09-19T06:07:10Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  We show that our model answers queries requiring complex reasoning patterns more effectively than existing KG completion algorithms. The proposed model outperforms or performs competitively with state-of-the-art models on several KBQA benchmarks.
  arXiv  Detail & Related papers  (2022-02-22T01:34:35Z)
• Improving Embedded Knowledge Graph Multi-hop Question Answering by introducing Relational Chain Reasoning [8.05076085499457]
  Knowledge Base Question Answer (KBQA) to answer userquestions from a knowledge base (KB) by identifying reasoning between topic entity and answer. As a complex branchtask of KBQA, multi-hop KGQA requires reasoning over multi-hop relational chains preserved in structured KG.
  arXiv  Detail & Related papers  (2021-10-25T06:53:02Z)
• Counterfactual Variable Control for Robust and Interpretable Question Answering [57.25261576239862]
  Deep neural network based question answering (QA) models are neither robust nor explainable in many cases. In this paper, we inspect such spurious "capability" of QA models using causal inference. We propose a novel approach called Counterfactual Variable Control (CVC) that explicitly mitigates any shortcut correlation.
  arXiv  Detail & Related papers  (2020-10-12T10:09:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.