Compositional Chain-of-Relations for Faithful Knowledge Graph Question Answering with Large Language Models

• URL: http://arxiv.org/abs/2608.22762v1
• Date: Mon, 24 Aug 2026 03:34:19 GMT
• Title: Compositional Chain-of-Relations for Faithful Knowledge Graph Question Answering with Large Language Models
• Abstract summary: This paper introduces a relation-centric exploration paradigm, which uses relations rather than entities as search units.<n> Experiments on four KGQA benchmarks show that CCoR consistently improves accuracy, faithfulness, and efficiency over strong baselines.
• Score: 15.198501576080451
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Knowledge graph question answering (KGQA) is a key task for evaluating KG-augmented Large Language Models (LLMs), and complex KGQA that requires multi-hop reasoning is especially challenging. Solving a complex query involves two coupled phases: candidate retrieval, which locates answer candidates over the KG, and constraint handling, which filters these candidates against the query constraints. Faithful reasoning requires grounding both phases in the KG. However, existing agent-based methods ground candidate retrieval through entity-centric exploration, while leaving constraint handling to the LLM's internal knowledge, which leads to two critical limitations. (1) Unreliable entity pruning: entity-centric exploration uses entities as search units and must prune them to a fixed-size subset at each hop. Because entity information in KGs is often incomplete and a fixed-size subset cannot retain all valid entities, such pruning inevitably drops valid entities and ultimately leads to wrong answers. (2) Ungrounded constraint handling: query constraints are resolved from the LLM's internal knowledge rather than the KG, leaving the final answers unverifiable and prone to hallucination. To address these limitations, this paper introduces a relation-centric exploration paradigm, which uses relations rather than entities as search units and thus avoids unreliable entity pruning. Built on this paradigm, this paper proposes Compositional Chain-of-Relations (CCoR), a simple and effective framework that grounds both phases in the KG with two relation chains: a main chain for candidate retrieval and a constraint chain that verifies query constraints through explicit KG exploration. Experiments on four KGQA benchmarks show that CCoR consistently improves accuracy, faithfulness, and efficiency over strong baselines, with more pronounced gains on complex queries.

Related papers

• Code-on-Graph: Iterative Programmatic Reasoning via Large Language Models on Knowledge Graphs [79.8277120258141]
  Knowledge Graphs (KGs) are widely used to mitigate the limitations of Large Language Models (LLMs)<n>Existing LLM-KG integration frameworks rely on predefined operators to retrieve factual knowledge from KGs and inject it into prompts for answer generation.<n>We propose Code-on-Graph (CoG) as a programmatic reasoning framework for LLM-KG integration.
  arXiv  Detail & Related papers  (2026-06-02T14:22:29Z)
• ROG: Retrieval-Augmented LLM Reasoning for Complex First-Order Queries over Knowledge Graphs [14.25887925588904]
  We propose a retrieval-augmented framework that combines query-aware neighborhood retrieval with large language model (LLM) chain-of-thought reasoning.<n>ROG decomposes a multi-operator query into a sequence of single-operator sub-queries.<n> Intermediate answer sets are cached and reused across steps, improving consistency on deep reasoning chains.
  arXiv  Detail & Related papers  (2026-02-02T17:45:43Z)
• CoT-Seg: Rethinking Segmentation with Chain-of-Thought Reasoning and Self-Correction [50.67483317563736]
  This paper aims to explore a system that can think step-by-step, look up information if needed, generate results, self-evaluate its own results, and refine the results.<n>We introduce CoT-Seg, a training-free framework that rethinks reasoning segmentation by combining chain-of-thought reasoning with self-correction.
  arXiv  Detail & Related papers  (2026-01-24T11:41:54Z)
• A Large Language Model Based Method for Complex Logical Reasoning over Knowledge Graphs [16.929901817693334]
  Reasoning over knowledge graphs (KGs) with first-order logic (FOL) queries is challenging due to the inherent incompleteness of real-world KGs.<n>We propose ROG (Reasoning Over knowledge Graphs with large language models), an ensemble-style framework that combines query-aware KG neighborhood retrieval with large language model (LLM)-based chain-of-thought reasoning.
  arXiv  Detail & Related papers  (2025-12-22T07:01:05Z)
• Reasoning-enhanced Query Understanding through Decomposition and Interpretation [87.56450566014625]
  ReDI is a Reasoning-enhanced approach for query understanding through Decomposition and Interpretation.<n>We compiled a large-scale dataset of real-world complex queries from a major search engine.<n> Experiments on BRIGHT and BEIR demonstrate that ReDI consistently surpasses strong baselines in both sparse and dense retrieval paradigms.
  arXiv  Detail & Related papers  (2025-09-08T10:58:42Z)
• LogiCoL: Logically-Informed Contrastive Learning for Set-based Dense Retrieval [54.2765452810124]
  We introduce LogiCoL, a logically-informed contrastive learning objective for dense retrievers.<n>We show that models trained with LogiCoL yield improvement both in terms of retrieval performance and logical consistency in the results.
  arXiv  Detail & Related papers  (2025-05-26T07:00:32Z)
• CR-LT-KGQA: A Knowledge Graph Question Answering Dataset Requiring Commonsense Reasoning and Long-Tail Knowledge [21.73770363188049]
  We create a novel Commonsense Reasoning (CR) and Long-Tail (LT) KGQA dataset with two subtasks -- question answering and claim verification. While existing KGQA methods are not applicable due to their lack of commonsense inference support, baseline evaluation of LLMs on CR-LT KGQA demonstrate a high rate of hallucination.
  arXiv  Detail & Related papers  (2024-03-03T04:47:01Z)
• Learning Federated Neural Graph Databases for Answering Complex Queries from Distributed Knowledge Graphs [53.03085605769093]
  We propose to learn Federated Neural Graph DataBase (FedNGDB), a pioneering systematic framework that empowers privacy-preserving reasoning over multi-source graph data.<n>FedNGDB leverages federated learning to collaboratively learn graph representations across multiple sources, enriching relationships between entities, and improving the overall quality of graph data.
  arXiv  Detail & Related papers  (2024-02-22T14:57:44Z)
• 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)
• Reasoning over Multi-view Knowledge Graphs [59.99051368907095]
  ROMA is a novel framework for answering logical queries over multi-view KGs. It scales up to KGs of large sizes (e.g., millions of facts) and fine-granular views. It generalizes to query structures and KG views that are unobserved during training.
  arXiv  Detail & Related papers  (2022-09-27T21:32:20Z)
• 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)
• 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)

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.