Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning

By Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, Shirui Pan. International Conference on Learning Representations, 2023

535 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/b47e96762351b2dbf7e863ece4640df6194bcc0c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Shirui Pan
2. Heng Ji
3. Xindong Wu
4. Jiawei Han
5. Linhao Luo
6. Meng Jiang
7. Bowen Jin
8. Chi Han

Citations in the corpus

• Time-LLM: Time Series Forecasting by Reprogramming Large Language Models (2023, background): “Harnessing these skills could allow making highly precise fore-casts by leveraging learned higher-level concepts.”
• Unifying Large Language Models and Knowledge Graphs: A Roadmap (2023, methodology): “To better reason on graphs, RoG [112] presents a planning-retrieval-reasoning framework.”
• Large Language Models on Graphs: A Comprehensive Survey (2023, methodology): “CoT [124]–[126], [128], [131], [132], Self-Consistency [124], BaG [124], [131], RoG [129], StructGPT [130], ToG [132] Algorithmic Reasoning Algorithmic Prompting [124], Graph-ToolFormer [127] Text-RichGraphs”
• A Survey on the Memory Mechanism of Large Language Model-based Agents (2024, unknown): “RoG [100] and ToG [145] directly incorporate external knowledge graphs to achieve more faithful and interpretable reasoning.”
• Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph (2023, unknown): “Early studies (Peters et al., 2019; Huang et al., 2024; Luo et al., 2024; Zhang et al., 2021; Li et al., 2023b; Liu et al., 2020) embed structured knowledge from KGs into the underlying neural networks during the pretraining or fine-tuning process.”
• G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering (2024, unknown): “It was proposed by Yih et al. [48] and, following Luo et al. [28], utilizes a subset of Freebase, encompassing facts within 2-hops of entities mentioned in the questions.”
• Retrieval-Augmented Generation for Large Language Models: A Survey (2023, background): “Lastly, there’s a risk of generation models overly depending on augmented information, potentially resulting in outputs that merely reiterate the retrieved content without providing new value or synthesized information.”
• Graph Retrieval-Augmented Generation: A Survey (2024, unknown): “In contrast, generative models, including GPT-3 [10] and GPT-4 In the early stages, RAG and GraphRAG focused on improving pre-training techniques for discriminative language models [22, 97, 129].”
• MG2-RAG: Multi-Granularity Graph for Multimodal Retrieval-Augmented Generation (2026, unknown): “Iterative graph exploration [35, 63], planning over structured representations [8, 52], memory-inspired architectures [24, 25], and agentic frameworks [15] demonstrate that explicit relational modeling significantly enhances reasoning depth and inter-pretability.”
• Retrieval And Structuring Augmented Generation with Large Language Models (2025, unknown): “Complementing neural approaches, rule-based methods used explicit reasoning paths over KGs. MHGRN [56] implemented multi-hop graph relation networks that performed explicit message passing between entities relevant to the query.”
• RAS: Retrieval-And-Structuring for Knowledge-Intensive LLM Generation (2025, unknown): “• [SUBQ] q 0 = Q : If M plan assesses that the query cannot be satisfactorily answered with its own knowledge, we start the iteration with the main query Q as the initial subquery, and move to the next stage (§3.2).”
• ArchRAG: Attributed Community-based Hierarchical Retrieval-Augmented Generation (2025, unknown): “These include using LLMs for KG construction [86], and employing KG to enhance the LLM reasoning [27, 29, 41, 45, 58, 67, 69].”