CodeGraph: Enhancing Graph Reasoning of LLMs with Code

📄 arXiv: 2408.13863v1 📥 PDF

作者: Qiaolong Cai, Zhaowei Wang, Shizhe Diao, James Kwok, Yangqiu Song

分类: cs.CL, cs.AI

发布日期: 2024-08-25

备注: In Progress

💡 一句话要点

CodeGraph：利用代码增强大语言模型在图推理任务中的能力

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

关键词: 图推理 大语言模型 代码生成 程序执行 少样本学习

📋 核心要点

  1. 现有方法将图数据转换为文本，LLM进行推理计算，但易在算术环节出错，且推理过程难以控制和解释。
  2. CodeGraph将图问题解决方案编码为代码，通过学习范例、生成程序并执行来解决问题。
  3. 实验表明，CodeGraph在图推理任务中性能提升显著，最高达58.6%，尤其在算术问题上表现突出。

📝 摘要（中文）

随着大型语言模型（LLMs）的日益普及，对基本图算法问题进行推理是评估其处理和推断复杂图推理任务能力的重要中间步骤。现有方法通常将图结构化数据转换为文本描述，然后使用LLMs进行推理和计算。然而，LLMs在基本图算法问题（如计算边数）的算术部分经常产生计算错误。此外，它们难以控制或理解推理过程的输出，引发了对LLMs是否只是猜测的担忧。本文介绍了一种名为CodeGraph的方法，该方法将图问题解决方案编码为代码。该方法通过学习范例、生成程序并通过程序解释器执行程序来解决新的图问题。在少样本设置下，我们使用GPT-3.5 Turbo、Llama3-70B Instruct、Mixtral-8x22B Instruct和Mixtral-8x7B Instruct作为基础LLM评估CodeGraph。在GraphQA数据集上的六个任务和六种图编码方法的实验结果表明，CodeGraph可以将LLMs在图推理任务中的性能提高1.3%到58.6%，具体取决于任务。与现有方法相比，CodeGraph在图任务的算术问题上表现出强大的性能，并为推理过程提供了一种更可控和可解释的方法。

🔬 方法详解

问题定义：论文旨在解决大型语言模型（LLMs）在图推理任务中，尤其是在涉及算术计算的图算法问题上的不足。现有方法依赖于将图结构数据转换为文本描述，然后让LLMs进行推理和计算，但这种方法容易导致计算错误，并且LLMs的推理过程缺乏可控性和可解释性。现有方法无法保证LLM真正理解图结构和算法逻辑，还是仅仅在猜测。

核心思路：CodeGraph的核心思路是将图问题的解决方案表示为可执行的代码。通过学习少量示例，LLM可以生成解决新图问题的程序。这些程序随后通过程序解释器执行，从而得到最终结果。这种方法将推理过程显式化，提高了可控性和可解释性，并减少了算术错误的发生。

技术框架：CodeGraph的整体框架包括以下几个主要阶段：1) 示例学习：从少量示例中学习图问题和对应代码解决方案的模式。2) 程序生成：利用LLM生成解决新图问题的代码程序。3) 程序执行：使用程序解释器执行生成的代码，得到最终结果。4) 结果验证：对结果进行验证，确保其正确性。

关键创新：CodeGraph最重要的创新在于将图推理问题转化为代码生成和执行问题。与直接使用LLM进行文本推理相比，这种方法具有以下优势：1) 更高的精度：通过程序执行，可以避免LLM在算术计算中出现的错误。2) 更好的可控性：可以清晰地了解程序的执行过程，从而更好地控制推理过程。3) 更强的可解释性：代码本身就是对解决方案的一种解释，可以帮助理解LLM的推理逻辑。

关键设计：CodeGraph的关键设计包括：1) 图编码方法：论文使用了多种图编码方法，将图结构数据转换为LLM可以理解的输入格式。2) 程序生成策略：设计了合适的提示工程（prompt engineering）策略，引导LLM生成正确的代码程序。3) 程序解释器：选择或构建合适的程序解释器，用于执行生成的代码。4) 少样本学习：采用少样本学习策略，使LLM能够快速适应新的图问题。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，CodeGraph在GraphQA数据集的六个任务上，相对于直接使用LLMs进行推理，性能提升了1.3%到58.6%。尤其是在涉及算术计算的任务上，CodeGraph的提升更为显著。例如，在某些任务上，CodeGraph的准确率超过了现有方法20%以上。这些结果表明，CodeGraph是一种有效的图推理增强方法。

🎯 应用场景

CodeGraph具有广泛的应用前景，例如智能交通、社交网络分析、生物信息学等领域。它可以用于解决各种复杂的图推理问题，例如路径规划、社区发现、蛋白质结构预测等。通过提高LLMs在图推理任务中的性能，CodeGraph可以帮助人们更好地理解和利用图结构数据，从而推动相关领域的发展。

📄 摘要（原文）

With the increasing popularity of large language models (LLMs), reasoning on basic graph algorithm problems is an essential intermediate step in assessing their abilities to process and infer complex graph reasoning tasks. Existing methods usually convert graph-structured data to textual descriptions and then use LLMs for reasoning and computation. However, LLMs often produce computation errors on arithmetic parts in basic graph algorithm problems, such as counting number of edges. In addition, they struggle to control or understand the output of the reasoning process, raising concerns about whether LLMs are simply guessing. In this paper, we introduce CodeGraph, a method that encodes graph problem solutions as code. The methods solve new graph problems by learning from exemplars, generating programs, and executing them via a program interpreter. Using the few-shot setting, we evaluate CodeGraph with the base LLM being GPT-3.5 Turbo, Llama3-70B Instruct, Mixtral-8x22B Instruct, and Mixtral-8x7B Instruct. Experimental results on six tasks with six graph encoding methods in the GraphQA dataset demonstrate that CodeGraph can boost performance on graph reasoning tasks inside LLMs by 1.3% to 58.6%, depending on the task. Compared to the existing methods, CodeGraph demonstrates strong performance on arithmetic problems in graph tasks and offers a more controllable and interpretable approach to the reasoning process.