知识图谱驱动的深度推理：ToG算法的创新与应用

LLMs通过预训练技术在大量文本语料库上生成连贯且符合上下文的响应。然而，面对需要复杂知识推理的任务时，它们存在明显的局限性。这些问题包括对超出预训练阶段的专业知识的准确回答失败，以及缺乏责任性、可解释性和透明度。为了解决这些问题，研究者们提出了将外部知识图谱（KG）引入LLM推理的新范式。本论文提出了一种名为“Think-on-Graph”（ToG）的新方法，该方法将LLM视为在知识图谱上交互探索相关实体和关系的代理，并基于检索到的知识执行推理。

三种LLM推理范式的代表性工作流程：
(a) LLM-only，例如仅使用链式思考提示（Chain-of-Thought prompting）；
(b) LLM ⊕ KG，例如通过LLM生成的SPARQL查询进行知识库问答（KBQA）；
(c) LLM ⊗ KG，例如Think-on-Graph（ToG）。
这个图表说明了ToG方法如何通过结合LLM的推理能力和知识图谱（KG）的信息来提高推理的准确性

方法

下图展示了 ToG（Think-on-Graph）的一个示例工作流程。在这个流程中，发光的实体是每个迭代（深度）开始搜索的中心实体，而加粗的实体是剪枝后选择的下一个迭代的中心实体。在每个剪枝步骤中，边的暗度代表了 LLM（大型语言模型）给出的排名分数，而虚线表示由于评分低而被剪枝的关系。

ToG 工作流程如下：

初始化搜索（Initialization of Search）:ToG 从问题中识别出初始实体，并以这些实体作为搜索的起点。
探索阶段（Exploration Phase）:在每个迭代深度，ToG 探索与当前中心实体相关的所有可能的关系和实体。探索过程包括搜索（Search）和剪枝（Prune）两个子步骤：
1. 在剪枝阶段，ToG 根据 LLM 分配的分数来选择最相关的几个关系，并将这些关系保留在推理路径中。
2. 在搜索阶段，ToG 寻找与尾部实体相关联的所有关系。
推理阶段（Reasoning Phase）:一旦收集到足够的信息，ToG 会进入推理阶段，LLM 将评估当前的推理路径是否足以回答问题。如果 LLM 认为信息充足，则会使用这些路径生成答案；如果不足，ToG 将继续探索更多的路径。
剪枝（Pruning）:在剪枝步骤中，根据 LLM 给出的评分，去除那些对问题贡献较小的关系和实体。边的暗度表示 LLM 分配的分数，分数越高，边越暗，表示该关系对回答问题越重要。被剪掉的关系用虚线表示，这些是因为评分低而被认为对当前问题不太相关或重要性较低的关系。
生成答案（Generate Answer）:当 ToG 确定已经找到了足够的信息来回答问题时，它会使用 LLM 根据检索到的知识和图谱中的路径生成最终答案。
迭代过程（Iterative Process）:ToG 的整个过程是迭代的，每一层迭代都可能增加推理路径的深度，直到找到正确的答案或达到预设的最大搜索深度。

ToG首先使用底层的语言模型（LLM）来定位知识图谱上的初始实体，作为推理路径的起点。这一步骤可以看作是推理路径集合P的初始化。ToG会提示LLM自动提取问题中的主题实体，并获取一组主题实体。

在第D次迭代开始时，每条路径由 D−1 个三元组组成，表示为 =，其中和分别表示主体和客体实体，是它们之间的特定关系。

关系探索是 ToG 算法中的一个关键环节，它使用束搜索来找出与问题相关的关系。这个过程分为两个阶段：搜索和剪枝。

搜索阶段：ToG 从上一轮迭代中得到的实体出发，寻找与之相关的关系。例如，如果当前的实体是“堪培拉”，ToG 就会搜索所有与“堪培拉”直接相连的关系。
剪枝阶段：在搜索到所有相关的关系后，ToG 需要决定哪些关系对于回答问题最有用。它使用大型语言模型（LLM）来评估这些关系的有用性，然后选择最重要的几个关系。这些被选中的关系将被保留，并用于下一轮的实体探索。

接下来是实体探索，它同样包括搜索和剪枝两个步骤：

搜索阶段：在确定了与问题相关的关系后，ToG 会根据这些关系来寻找相关的实体。例如，如果关系是“首都”，ToG 就会搜索所有与这个关系相连的实体。
剪枝阶段：在搜索到所有可能的实体后，ToG 再次使用 LLM 来评估这些实体的相关性，并选择最重要的几个实体。这些实体将被用来扩展当前的推理路径。

通过探索过程获得当前推理路径P后，ToG提示LLM评估当前推理路径是否足够生成答案。如果评估结果是肯定的，则提示LLM使用推理路径和查询作为输入生成答案。如果评估结果是否定的，则重复探索和推理步骤，直到评估结果为正或达到最大搜索深度。

基于之前基于语义解析的KBQA方法，作者提出了基于关系的ToG (ToG-R)，它从主题实体开始探索顶级关系链，而不是基于三元组的推理路径。ToG-R在每次迭代中顺序执行关系搜索、关系剪枝和实体搜索，然后基于通过实体搜索获得的所有候选推理路径执行推理步骤。

如果LLM确定检索到的候选推理路径不包含足够信息以回答问题，我们将从候选实体中随机采样N个实体并继续到下一次迭代。假设每个实体集合中的实体可能属于同一实体类别并具有相似的邻近关系，剪枝实体集合的结果可能对随后的关系探索影响不大。因此，ToG-R使用随机束搜索而不是ToG中的LLM约束束搜索进行实体剪枝，称为随机剪枝。

实验

作者选择了多个数据集来测试 ToG 在多跳知识密集型推理任务上的能力，包括五个知识库问答（KBQA）数据集（四个多跳和一个单跳），以及其他类型的数据集，如开放域问答、槽填充和事实核查数据集。评估指标采用的是精确匹配准确率（Hits@1）。

ToG 与多种方法进行了比较，包括标准提示（IO prompt）、思维链提示（Chain-of-Thought prompting, CoT prompt）和自洽性（Self-Consistency, SC）方法。还与之前在各个数据集上达到最佳状态的方法（SOTA）进行了比较。

ToG在不同数据集上的性能，包括多跳知识库问答（KBQA）、单跳KBQA、开放域问答（Open-Domain QA）、实体填充（Slot Filling）和事实核查（Fact Checking）等任务。表格中列出了不同方法在各个数据集上的表现，包括ToG和ToG-R在不同LLM模型上的结果

他们使用了三种不同的大型语言模型（LLMs）：ChatGPT、GPT-4和Llama-2-70B-Chat，并利用OpenAI API调用了ChatGPT和GPT-4模型。对于Llama2-70B-Chat，作者在一个没有量化的8 A100-40G GPU集群上运行模型，设置了特定的温度参数以在探索过程中增加多样性，并在推理过程中确保可重复性。他们还规定了生成的最大令牌长度为256，并为所有数据集的ToG推理提示设置了5个示例。在知识图谱的选择上，使用了Freebase和Wikidata两个知识库，分别对应不同的数据集。实验中，作者还设置了束搜索的宽度N和最大搜索深度Dmax为3，以平衡搜索的广度和计算成本。

ToG 在多个数据集上与基于微调和基于提示的方法进行了比较。即使 ToG 是一种无需额外训练的基于提示的方法，它仍然在六个数据集上达到了新的最佳性能，并且在其他数据集上的性能也非常接近最佳状态。

对比了在CWQ和WebQSP数据集上，使用不同LLM模型（如ChatGPT、GPT-4和Llama2-70B-Chat）时ToG的性能。表格显示了不同模型大小对ToG性能的影响，以及ToG相对于传统提示方法（如CoT）的性能提升

作者还探讨了不同规模的大型语言模型（LLMs）对ToG算法性能的影响。实验使用了ChatGPT、GPT-4和Llama-2-70B-Chat三种模型，发现随着模型规模的增大（即参数数量的增加），ToG的性能得到了提升，显示出更强大的模型能够更有效地挖掘知识图谱的潜力。即使使用较小的模型，ToG的性能也显示出了超越大型模型如GPT-4的潜力，尤其是在特定场景下，这表明ToG算法能够有效利用不同规模的模型来实现成本效益和性能的平衡。

消融研究中，作者通过一系列控制实验来分析ToG算法中各个组成部分的贡献和重要性。这些实验包括改变搜索深度和宽度、使用不同的知识图谱、以及不同的提示设计和剪枝工具。结果表明，搜索深度和宽度对ToG性能有显著影响，而不同的知识图谱对性能的影响则各有不同。消融研究还发现，使用LLM作为剪枝工具比使用传统的文本相似度模型如BM25或SentenceBERT更有效，尽管这会增加计算成本。这些发现有助于理解ToG算法的内部工作机制，并为进一步优化提供了指导。

ToG在CWQ和WebQSP数据集上使用不同知识源（如Freebase和WikiData）时的性能。表格说明了不同知识源对ToG性能的影响

ToG 的一个有趣特性是其在 LLM 推理过程中提供了知识可追溯性和可更正性。这允许用户或专家发现并纠正 ToG 答案中的潜在错误或不确定性。ToG通过明确的推理路径，增强了推理过程的可解释性，使得用户或专家能够在发现潜在错误或不确定性时，回溯并检查推理路径，找出并纠正错误的知识三元组。例如，如果ToG给出了错误答案，可以通过分析推理路径来定位问题所在，然后利用LLM的知识库或专家反馈来修正知识图谱中的错误信息。这种能力不仅提升了LLM结合知识图谱时的推理准确性，而且也为知识图谱的构建和维护提供了一种成本效益更高的方法，即通过ToG算法本身来提高知识图谱的质量。