GCoder: Improving Large Language Model for Generalized Graph Problem Solving

📄 arXiv: 2410.19084v1 📥 PDF

作者: Qifan Zhang, Xiaobin Hong, Jianheng Tang, Nuo Chen, Yuhan Li, Wenzhong Li, Jing Tang, Jia Li

分类: cs.CL

发布日期: 2024-10-24

🔗 代码/项目: GITHUB

💡 一句话要点

GCoder：提升大语言模型在通用图问题求解中的能力

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 图计算 大语言模型 代码生成 强化学习 图神经网络 编译器反馈 泛化能力

📋 核心要点

  1. 现有图问题求解方法依赖推理步骤，存在步骤不可验证、长期推理受限以及泛化能力差等问题。
  2. GCoder通过构建大规模图数据集GraphWild，并结合监督微调和强化学习，训练代码生成式大语言模型。
  3. 实验结果表明，GCoder在图计算问题上显著优于GPT-4o，平均准确率提升16.42%，并能处理大规模图。

📝 摘要（中文）

本文提出GCoder，一种基于代码的大语言模型，旨在提升其在通用图计算问题中的求解能力。传统图问题求解范式受限于不可验证的步骤、有限的长期推理以及对图变化的泛化能力不足。为了克服这些限制，我们构建了一个包含多样图格式和算法的大规模训练数据集GraphWild。我们采用多阶段训练过程，包括监督微调（SFT）和基于编译器反馈的强化学习（RLCF），以优化模型能力。对于未见过的任务，使用混合检索技术来增强性能。实验表明，GCoder优于GPT-4o，在各种图计算问题上的平均准确率提高了16.42%。此外，GCoder能够有效管理具有数百万个节点和多样输入格式的大规模图，克服了先前模型专注于推理步骤范式的局限性。

🔬 方法详解

问题定义：论文旨在解决大语言模型在通用图计算问题求解中存在的泛化能力不足的问题。现有方法通常依赖于推理步骤，但这些步骤难以验证，长期推理能力有限，并且难以适应不同的图结构和算法。这些局限性阻碍了大语言模型在实际图问题中的应用。

核心思路：论文的核心思路是利用代码生成的方式，让大语言模型学习如何通过编写代码来解决各种图计算问题。通过代码，可以更清晰地表达算法逻辑，并且代码的执行结果可以作为反馈信号，从而提高模型的准确性和泛化能力。此外，论文还通过构建大规模、多样化的图数据集来增强模型的学习能力。

技术框架：GCoder的整体框架包括数据构建、模型训练和推理三个阶段。数据构建阶段，构建了GraphWild数据集，包含多种图格式和算法。模型训练阶段，首先进行监督微调（SFT），然后使用基于编译器反馈的强化学习（RLCF）进一步优化模型。推理阶段，对于未见过的任务，采用混合检索技术来增强性能。

关键创新：GCoder的关键创新在于使用代码生成的方式来解决图计算问题，并结合编译器反馈进行强化学习。与传统的推理步骤方法相比，代码生成更具表达力，并且可以通过编译器进行验证和优化。此外，混合检索技术可以有效地利用已有的知识，提高模型在未见任务上的性能。

关键设计：在数据构建方面，GraphWild数据集包含了多种图格式（如邻接矩阵、邻接表等）和算法（如最短路径、最小生成树等）。在模型训练方面，SFT阶段使用交叉熵损失函数，RLCF阶段使用奖励函数来鼓励模型生成正确的代码。混合检索技术结合了语义检索和代码检索，以找到与当前任务最相关的代码示例。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，GCoder在各种图计算问题上的平均准确率比GPT-4o提高了16.42%。此外，GCoder能够有效处理具有数百万个节点的大规模图，并且能够适应不同的图输入格式。这些结果表明，GCoder在图计算问题求解方面具有显著的优势。

🎯 应用场景

GCoder在图数据分析、社交网络分析、推荐系统、交通网络优化等领域具有广泛的应用前景。它可以帮助研究人员和工程师更高效地解决复杂的图计算问题，并为开发智能图应用提供强大的技术支持。未来，GCoder有望成为图计算领域的重要工具。

📄 摘要（原文）

Large Language Models (LLMs) have demonstrated strong reasoning abilities, making them suitable for complex tasks such as graph computation. Traditional reasoning steps paradigm for graph problems is hindered by unverifiable steps, limited long-term reasoning, and poor generalization to graph variations. To overcome these limitations, we introduce GCoder, a code-based LLM designed to enhance problem-solving in generalized graph computation problems. Our method involves constructing an extensive training dataset, GraphWild, featuring diverse graph formats and algorithms. We employ a multi-stage training process, including Supervised Fine-Tuning (SFT) and Reinforcement Learning from Compiler Feedback (RLCF), to refine model capabilities. For unseen tasks, a hybrid retrieval technique is used to augment performance. Experiments demonstrate that GCoder outperforms GPT-4o, with an average accuracy improvement of 16.42% across various graph computational problems. Furthermore, GCoder efficiently manages large-scale graphs with millions of nodes and diverse input formats, overcoming the limitations of previous models focused on the reasoning steps paradigm. This advancement paves the way for more intuitive and effective graph problem-solving using LLMs. Code and data are available at here: https://github.com/Bklight999/WWW25-GCoder/tree/master.