PaperlayerView exact revision on arXiv

Source-linked AI summary

Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning

Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, Shirui Pan

arXiv:2310.01061v2cs.CLcs.AI

TL;DR

LLMs’ reasoning is limited by outdated knowledge and hallucinations, while existing KG-based methods underuse graph structure. RoG grounds relation-path plans in KGs, retrieves valid reasoning paths, and enables faithful, interpretable reasoning; experiments on two benchmark KGQA datasets demonstrate superiority in reasoning ability and interpretability.

  • Problem

    LLMs lack up-to-date knowledge and hallucinate during reasoning, while existing KG-based methods overlook KGs’ structural information for reasoning.

  • Method

    RoG uses planning-retrieval-reasoning: it generates KG-grounded relation paths as plans, retrieves valid reasoning paths, and reasons over them.

  • Results

    RoG’s experiments on two benchmark KGQA datasets demonstrate superiority in reasoning ability and interpretability.

  • Takeaways & Limitations

    RoG combines KG structure and factual knowledge to support faithful reasoning with interpretable explanations and integration with arbitrary LLMs during inference.

  • Takeaways & Limitations

    The optimization framework assumes a uniform distribution over valid relation paths, and FiD approximates their contributions as independent.

Abstract

from arXiv · show

Large language models (LLMs) have demonstrated impressive reasoning abilities in complex tasks. However, they lack up-to-date knowledge and experience hallucinations during reasoning, which can lead to incorrect reasoning processes and diminish their performance and trustworthiness. Knowledge graphs (KGs), which capture vast amounts of facts in a structured format, offer a reliable source of knowledge for reasoning. Nevertheless, existing KG-based LLM reasoning methods only treat KGs as factual knowledge bases and overlook the importance of their structural information for reasoning. In this paper, we propose a novel method called reasoning on graphs (RoG) that synergizes LLMs with KGs to enable faithful and interpretable reasoning. Specifically, we present a planning-retrieval-reasoning framework, where RoG first generates relation paths grounded by KGs as faithful plans. These plans are then used to retrieve valid reasoning paths from the KGs for LLMs to conduct faithful reasoning. Furthermore, RoG not only distills knowledge from KGs to improve the reasoning ability of LLMs through training but also allows seamless integration with any arbitrary LLMs during inference. Extensive experiments on two benchmark KGQA datasets demonstrate that RoG achieves state-of-the-art performance on KG reasoning tasks and generates faithful and interpretable reasoning results.

1 INTRODUCTION

LLMs can reason through complex tasks but suffer from outdated knowledge and hallucinated steps, reducing performance and trustworthiness. RoG addresses these issues by grounding LLM reasoning in KG facts and structure through planned relation paths.

  • Motivation: LLMs’ lack of up-to-date knowledge and hallucinations can cause reasoning errors and diminish performance and trustworthiness in high-stakes scenarios.The paper cites legal judgment and medical diagnosis as examples of high-stakes settings.
  • Motivation: Knowledge graphs provide abundant factual knowledge in a structured format that can serve as a faithful source for LLM reasoning.
  • Limitations of Existing Methods: Existing KG-based approaches either generate potentially non-executable logical queries or retrieve triples while overlooking KG structural information for reasoning.Semantic parsing methods face syntax and semantic limitations, whereas retrieval-augmented methods treat KGs primarily as factual knowledge bases.
  • Limitations of Existing Methods: A relation path such as “child of→has son” can guide KG reasoning to answer questions such as who is Justin Bieber’s brother.
  • RoG: RoG uses a planning-retrieval-reasoning framework that generates KG-grounded relation-path plans, retrieves valid reasoning paths, and performs faithful reasoning.Its planning module distills KG knowledge into LLMs, while retrieval-reasoning optimization supports interpretable answers.

2 RELATED WORK

Prior KGQA work combines LLMs with graph retrieval, semantic parsing, or prompting, but RoG’s framework illustrates how graph structure can organize faithful reasoning and interpretable answers.

  • LLM Reasoning Prompt: LLM reasoning methods use prompting strategies such as plan-and-solve, task decomposition, and agent-style interaction to address complex tasks.
  • Knowledge Graph Question Answering: Conventional KGQA methods represent entities and relations in embeddings and use specialized architectures such as memory networks, sequential models, or graph neural networks.
  • Reasoning on Graphs: RoG organizes KGQA as grounded planning, reasoning-path retrieval, and faithful answer generation with interpretable explanations.Figure 2 marks question entities in orange and answer entities in red.
  • Knowledge Graph Question Answering: LLM-based KGQA methods include retrieval-augmented approaches that retrieve KG facts and semantic parsing approaches that convert questions into structural queries.UniKGQA is described as unifying graph retrieval and reasoning in one LLM-based model.

3 PRELIMINARY

The paper formalizes KGs as triples, relation paths as sequences of relations, reasoning paths as their graph instances, and KGQA as answer prediction from a question and graph.

  • Knowledge Graphs: A knowledge graph is represented as a set of triples G = {(e, r, e′)|e, e′ ∈E, r ∈R}, with entities E and relations R.
  • Relation Paths: A relation path is a sequence of relations z = {r1, r2, . . . , rl}, where each ri belongs to R and l is the path length.
  • Reasoning Paths: A reasoning path is an instance of a relation path in a KG, linking concrete entities through the specified relations.The example connects Alice, Bob, and Charlie through “marry to” and “father of.”
  • Knowledge Graph Question Answering: KGQA maps a natural-language question q and KG G to answers a ∈Aq based on graph knowledge.The formulation assumes question entities and answers are labeled and linked to corresponding KG entities.

4 APPROACH

RoG combines planning, KG retrieval, and LLM reasoning to generate faithful, interpretable answers. It grounds relation-path plans in KGs, retrieves matching reasoning paths, and trains the LLM through planning and retrieval-reasoning objectives.

  • Framework: RoG uses a planning-retrieval-reasoning framework with separate planning and retrieval-reasoning modules.The planning module generates KG-grounded relation paths, while the retrieval-reasoning module retrieves valid paths and produces answers with explanations.
  • Planning: Relation paths serve as faithful plans because they encode semantic relations and can be executed by retrieving matching KG paths.For “Who is the child of Alice,” RoG uses marry to → father of and retrieves a path leading to Charlie.
  • Optimization framework: RoG models answer generation as a sum over possible relation-path plans, combining plan probability with answer probability conditioned on the question, plan, and KG.Pθ(z|q) is learned by planning, while Pθ(a|q,z,G) is computed by retrieval-reasoning.
  • Optimization framework: The ELBO objective jointly encourages faithful plan generation and correct answer generation from relation paths and KGs.Its KL term supports planning optimization, while its expectation term supports retrieval-reasoning optimization.
  • Planning module: Planning optimization distills KG knowledge into the LLM by treating valid KG relation paths as supervision for faithful plans.Valid paths connect question and answer entities, and shortest paths are used as supervision signals.
  • Retrieval-reasoning module: The retrieval module follows planned relations from question entities using constrained breadth-first search, after which the reasoning module handles noisy or irrelevant retrieved paths.RoG trains retrieval-reasoning behavior to identify important paths and answer questions rather than relying only on majority voting.

5 EXPERIMENT

RoG is evaluated on two benchmark KGQA datasets against 21 baselines using Hits@1 and F1. Results assess overall performance, module contributions, plug-and-play integration, relation-path faithfulness, and interpretable reasoning.

  • RQ1: KGQA performance comparison: RoG improves WebQSP Hits@1 by 4.4% over DECAF and improves CWQ Hits@1 and F1 by 22.3% and 14.4% over UniKGQA.The method achieves the best performance across most metrics on both datasets.
  • RQ1: KGQA performance comparison: Retrieval-augmented methods outperform embedding-based methods, while relation-path retrieval improves performance and LLMs+KGs methods achieve the second-best performance.Semantic parsing performs better on WebQSP but worse on CWQ, where generating logical queries is more complex.
  • RQ3: Faithful reasoning and interpretable results: Increasing K raises retrieved-path counts and answer recall, but added noise and retrieval time reduce precision and contribute little to reasoning-F1.RoG therefore sets K = 3 in the experiments.
  • RQ3: Faithful reasoning and interpretable results: Case studies show RoG retrieves valid KG reasoning paths, filters noisy paths when necessary, and provides interpretable explanations while ChatGPT+CoT lacks knowledge or hallucinates.The examples cover both missing-knowledge and hallucination scenarios.

6 CONCLUSION

RoG synergizes LLMs with KGs through a planning-retrieval-reasoning framework for faithful and interpretable reasoning. It distills KG knowledge during training, integrates with arbitrary LLMs during inference, and demonstrates strong KG reasoning and interpretability results.

  • 6 CONCLUSION: RoG uses planning, retrieval, and reasoning to ground LLM reasoning in faithful plans and valid KG paths.The planning module generates KG-grounded relation paths, which guide retrieval of valid reasoning paths.
  • 6 CONCLUSION: RoG distills knowledge from KGs during training and integrates with any LLM during inference.
  • 6 CONCLUSION: Experiments on two benchmark KGQA datasets demonstrate RoG’s superiority in reasoning ability and interpretability.

ETHICS STATEMENT

The study addresses scientific problems without human subjects, animals, or environmentally sensitive materials, and reports no anticipated ethical risks or conflicts of interest.

  • ETHICS STATEMENT: The research involves no human subjects, animals, or environmentally sensitive materials.
  • ETHICS STATEMENT: The authors anticipate no potential ethical risks or conflicts of interest.
  • ETHICS STATEMENT: The study states that it follows standards of scientific integrity and ethical conduct.

REPRODUCIBILITY STATEMENT

The paper describes formalization and supplementary implementation details, including datasets, baselines, settings, and configurations, and reports public release of code and model weights.

  • REPRODUCIBILITY STATEMENT: The model is formalized in the main text to support clarity and comprehensive understanding.
  • REPRODUCIBILITY STATEMENT: Appendices A.4 to A.6 provide dataset, baseline, experimental-setting, and model-configuration details.
  • REPRODUCIBILITY STATEMENT: The code and pre-trained model weights have been publicized.

A.1 DETAILED DERIVATION OF THE PLANNING MODULE

The planning-module derivation approximates an intractable expectation over valid relation paths using shortest KG paths and simplifies the optimization by dropping a constant term.

  • A.1 DETAILED DERIVATION OF THE PLANNING MODULE: The planning derivation approximates Q(z) with Q(z|a,q,G) before calculating the KL divergence.
  • A.1 DETAILED DERIVATION OF THE PLANNING MODULE: Because valid relation paths are numerous, the expectation is approximated using shortest paths between eq and ea in the KG.
  • A.1 DETAILED DERIVATION OF THE PLANNING MODULE: Assuming a uniform distribution over shortest paths Z∗, the derivation rewrites the objective accordingly.
  • A.1 DETAILED DERIVATION OF THE PLANNING MODULE: The constant term is omitted from final optimization because it does not contribute to the loss.

A.2.1 LLM REASONING PROMPT

LLM reasoning prompts motivate structured decomposition, while KGQA methods combine graph retrieval or semantic parsing with LLMs. RoG retrieves KG-grounded reasoning paths and shows transferability, training-data, hop, answer-count, and retrieval-cost trade-offs.

  • A.2.1 LLM REASONING PROMPT: Prompting methods decompose complex reasoning into chains, trees, or sub-tasks, but hallucinations and missing knowledge can reduce reasoning faithfulness.The related-work discussion includes Chain-of-Thought, Tree of Thoughts, plan-and-solve, and DecomP.
  • A.2.2 KNOWLEDGE GRAPH QUESTION ANSWERING: KGQA approaches include embedding-based models, retrieval-augmented methods, and semantic parsing methods that execute generated structural queries on knowledge graphs.Embedding-based methods use specialized architectures, retrieval methods obtain relevant KG facts, and semantic parsing methods generate executable queries such as SPARQL.
  • A.3 RETRIEVAL ALGORITHM: RoG retrieves reasoning paths by initializing a queue with question entities and expanding paths according to each relation in a KG-grounded relation-path plan.Constrained breadth-first search stops when the reasoning path reaches the relation-path length.
  • A.4 DATASETS: RoG is evaluated on WebQSP and CWQ over Freebase, with MetaQA-3hop used to test transfer to Wiki-Movies KGs.The experiments follow established train/test splits and construct reduced KG subgraphs around question entities.
  • A.7.1 TRANSFERABILITY TO OTHER KGS: 2 hours of transfer training on Wiki-Movies follows 38 hours of training on Freebase, demonstrating efficient transfer of RoG to another KG.The paper compares training time on Freebase with transferring the model to Wiki-Movies.
  • A.7.2 PERFORMANCE WITH DIFFERENT TRAINING DATA: Joint training on WebQSP and CWQ improves performance beyond single-dataset training, while single-dataset RoG still outperforms UniKGQA.The comparison uses RoG trained jointly or separately on the two datasets.
  • A.7.3–A.7.6 PERFORMANCE ANALYSES: RoG outperforms finetuned LLMs, performs better across question-hop counts especially beyond 3 hops, and remains stronger across varying answer numbers.The hop results support the importance of relation paths, while answer-count results distinguish planning and reasoning contributions.
  • A.7.4 RETRIEVAL COSTS / A.10 PROMPTS: Retrieval time increases with the number of top-K relation paths, so the experiments choose K = 3 to balance retrieval time and retrieved-path count.RoG also formats retrieved reasoning paths as structural sentences and uses an instruction template for interpretable reasoning outputs.
Loading 2310.01061v2…