Paths-over-Graph: Knowledge Graph Empowered Large Language Model Reasoning

📄 arXiv: 2410.14211v4 📥 PDF

作者: Xingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu, Xin Yuan, Wenjie Zhang

分类: cs.CL

发布日期: 2024-10-18 (更新: 2025-03-12)

备注: Accepted by The Web Conference 2025 (WWW, 2025)

💡 一句话要点

提出Paths-over-Graph (PoG)，通过知识图谱路径增强LLM推理能力，解决幻觉和知识不足问题。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 知识图谱 大型语言模型 推理 多跳推理 知识增强 图神经网络 问答系统

📋 核心要点

  1. 现有基于知识图谱的LLM推理方法难以有效处理多跳推理、多实体问题，以及充分利用图结构。
  2. Paths-over-Graph (PoG)通过动态多跳路径探索，结合LLM固有知识与KG事实知识，增强推理能力。
  3. 实验表明，PoG在多个KGQA数据集上显著优于现有方法，平均准确率提升18.9%。

📝 摘要（中文）

大型语言模型(LLM)在各种任务中取得了显著成果，但仍存在幻觉问题和缺乏相关知识的问题，尤其是在深度复杂推理和知识密集型任务中。知识图谱(KG)以结构化格式捕获大量事实，为推理提供了可靠的知识来源。然而，现有的基于KG的LLM推理方法面临着处理多跳推理、多实体问题以及有效利用图结构等挑战。为了解决这些问题，我们提出了一种新颖的方法Paths-over-Graph (PoG)，通过整合来自KG的知识推理路径来增强LLM推理，从而提高LLM输出的可解释性和忠实性。PoG通过三阶段动态多跳路径探索来处理多跳和多实体问题，将LLM的固有知识与KG的事实知识相结合。为了提高效率，PoG首先从图探索中修剪掉不相关的信息，并引入了有效的三步修剪技术，该技术结合了图结构、LLM提示和预训练语言模型(例如SBERT)来有效地缩小探索的候选路径。这确保了所有推理路径都包含从KG捕获的高度相关的信息，从而使问题解决中的推理忠实且可解释。PoG创新性地利用图结构来修剪不相关的噪声，并且是第一个在KG上实现多实体深度路径检测以用于LLM推理任务的方法。在五个基准KGQA数据集上的综合实验表明，PoG在GPT-3.5-Turbo和GPT-4上均优于最先进的方法ToG，平均准确率提高了18.9%。值得注意的是，使用GPT-3.5-Turbo的PoG超越了使用GPT-4的ToG，提升高达23.9%。

🔬 方法详解

问题定义：论文旨在解决大型语言模型在知识密集型任务中存在的幻觉问题和知识不足的挑战，尤其是在需要多跳推理和处理多个实体的问题时。现有方法，如ToG，在处理复杂图结构和有效利用知识图谱中的信息方面存在局限性，导致推理结果不够准确和可信。

核心思路：PoG的核心思路是通过知识图谱中的推理路径来增强LLM的推理能力。它不是简单地将KG信息输入LLM，而是通过动态探索KG中的多跳路径，找到与问题最相关的知识，并将其整合到LLM的推理过程中。这种方法旨在提高LLM输出的可解释性和忠实性。

技术框架：PoG包含三个主要阶段：1) 图探索与剪枝：利用图结构、LLM提示和预训练语言模型（如SBERT）进行三步剪枝，减少不相关信息的干扰。2) 多跳路径生成：动态地探索知识图谱中的多跳路径，找到连接问题中多个实体的推理链。3) LLM推理：将探索到的知识路径输入LLM，引导LLM进行推理，生成最终答案。

关键创新：PoG的关键创新在于其动态多跳路径探索和三步剪枝策略。它能够有效地从知识图谱中提取与问题相关的知识，并利用图结构来减少噪声。此外，PoG是第一个在KG上实现多实体深度路径检测以用于LLM推理任务的方法。

关键设计：PoG的三步剪枝策略是其关键设计之一。第一步利用图结构进行初步剪枝，去除与问题无关的节点和边。第二步使用LLM提示来评估剩余路径的相关性，并去除低相关性的路径。第三步使用预训练语言模型（如SBERT）计算路径中实体和关系的语义相似度，进一步去除不相关的路径。此外，PoG还设计了一种动态多跳路径探索算法，能够有效地找到连接多个实体的推理链。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在五个基准KGQA数据集上的实验结果表明，PoG在GPT-3.5-Turbo和GPT-4上均优于最先进的方法ToG，平均准确率提高了18.9%。更值得注意的是，使用GPT-3.5-Turbo的PoG甚至超越了使用GPT-4的ToG，提升高达23.9%，这表明PoG能够更有效地利用知识图谱来增强LLM的推理能力。

🎯 应用场景

PoG可应用于问答系统、知识图谱补全、推荐系统等领域。通过增强LLM的推理能力和知识获取能力，可以提高这些应用的准确性和可靠性。未来，PoG可以扩展到更复杂的知识图谱和更广泛的推理任务中，例如医疗诊断、金融风险评估等。

📄 摘要（原文）

Large Language Models (LLMs) have achieved impressive results in various tasks but struggle with hallucination problems and lack of relevant knowledge, especially in deep complex reasoning and knowledge-intensive tasks. Knowledge Graphs (KGs), which capture vast amounts of facts in a structured format, offer a reliable source of knowledge for reasoning. However, existing KG-based LLM reasoning methods face challenges like handling multi-hop reasoning, multi-entity questions, and effectively utilizing graph structures. To address these issues, we propose Paths-over-Graph (PoG), a novel method that enhances LLM reasoning by integrating knowledge reasoning paths from KGs, improving the interpretability and faithfulness of LLM outputs. PoG tackles multi-hop and multi-entity questions through a three-phase dynamic multi-hop path exploration, which combines the inherent knowledge of LLMs with factual knowledge from KGs. In order to improve the efficiency, PoG prunes irrelevant information from the graph exploration first and introduces efficient three-step pruning techniques that incorporate graph structures, LLM prompting, and a pre-trained language model (e.g., SBERT) to effectively narrow down the explored candidate paths. This ensures all reasoning paths contain highly relevant information captured from KGs, making the reasoning faithful and interpretable in problem-solving. PoG innovatively utilizes graph structure to prune the irrelevant noise and represents the first method to implement multi-entity deep path detection on KGs for LLM reasoning tasks. Comprehensive experiments on five benchmark KGQA datasets demonstrate PoG outperforms the state-of-the-art method ToG across GPT-3.5-Turbo and GPT-4, achieving an average accuracy improvement of 18.9%. Notably, PoG with GPT-3.5-Turbo surpasses ToG with GPT-4 by up to 23.9%.