文章总结： 本文提出首个用强化学习指导LLM在图上推理的框架G1，并发布迄今最大规模真实图论数据集Erdős。通过GRPO算法与基于规则的结果奖励模型，G1-7B在50类图任务上全面超越70B级模型，零样本迁移至GraphWiz、GraphArena及节点分类、连接预测等真实任务仍领先，且仅在图任务上训练即可恢复并提升通用推理能力，为构建高效通用图推理器提供新范式。 综合评分： 92 文章分类： AI安全,漏洞分析,安全工具,数据安全,安全建设

论文解读 | 用强化学习指导LLM在图上推理

谢天阳

北邮 GAMMA Lab

2026年1月13日 13:56 北京

论文解读 | Teaching LLMs to Reason on Graphs with Reinforcement Learning

一、简介

尽管大语言模型在各类任务上进步飞快，但是在图相关的任务中的推理能力有限。为了克服这一点，以往的尝试有预训练图基础模型、监督微调等，但这些措施都面临一个难题：缺乏大规模的、通用的图数据。本文首次探索使用强化学习来解决图推理任务。并基于此提出了新模型G1。此外，本文还提出了目前规模最大、覆盖最全面的图论数据集Erdős，为图推理的训练和评估提供了可靠的平台。

图一：G1模型在Erdős数据集上的表现，Base Model选择为Qwen2.5-7B-Instruct

二、本文主要贡献

2.1 Erdős：基于真实世界图的图论推理任务集合

任务分类

作者根据图论任务的内在复杂度以及当前LLM解决问题的能力，将这些任务分为Easy、Medium、Hard和Challenging四个等级。在训练集部分，Erdős包含十万对问答样本，均匀分布在50个任务上，每个任务包含2000个样例。文章中精选了NetworkX库中50种图论推理任务，构建了迄今为止最全面的图论任务集合。详细任务列表见图一。

答案生成

为了生成问题的标准答案，使用NetworkX自带的求解器自动解决问题。如果某个问题存在多个可行解，使用基于NetworkX的验证程序逐一检查解答的正确性。采用这种方法避免了人工标注的高成本，也避免了依赖LLM评估带来的漏洞。

图数据来源

以往的以往的图论数据集或Baseline大多采用随机图模型生成图结构，例如 Erdős–Rényi 模型或 Barabási–Albert 模型。 然而，这些随机图往往与真实世界中的图结构差距较大。 为缩小这一差距，本文中使用来自 Network Repository 的真实世界图数据，这是目前规模最大的网络数据仓库，涵盖三十多个领域的上千个图样本。 由于原始图可能过大，不适合 LLM 直接处理，文章中还采用了带有重启机制的随机游走的方法进行子图采样，并生成包含 5 至 35 个节点的子图，遵循了以往工作的通用的设置。

2.2 G1模型：图上的大语言模型结合强化学习

类似DeepSeek R1，G1的训练流程很简洁，分为两个阶段。

阶段一：强化学习阶段，使用GRPO算法，对生成正确结果的模型输出基于奖励。

阶段二：可选的监督微调阶段(SFT)：在训练初期进行预热。如果跳过了阶段二，模型则被称为G1-Zero。

针对图论推理任务，本文为强化学习设计了基于规则的结果奖励模型，并结合了三种不同类型的评估策略：

严格数值匹配

适用于答案为单一数值的任务，比如图节点计数。当模型答案与标准答案完全一致，给予+1奖励，否则为0。

集合匹配

当任务的答案为集合时，比如求两节点的公共邻居节点。此时使用Jaccard指数。奖励定义为预测集合与真实集合的Jaccard指数。 这样即使不是完美解，也能获得一定分数。

算法验证

适用于存在多个正确解并且无法穷举的任务，比如最短路径。实现了基于NetworkX的算法验证器来检验模型输出的正确性。例如：对于哈密顿路径任务，通过检查路径中的边是否全部存在、每个节点是否恰好访问一次来判断答案的正确性。

在阶段一采用的GRPO算法，具体步骤如下：

S1：从训练集中抽取一个问题Q

S2：模型根据q生成答案

S3：根据评估策略计算获得的奖励

S4：根据奖励计算相对优劣，从而更新模型

对于一些难度等级为Challenging的任务，基础模型的初始准确率非常低。从而无法为强化学习提供奖励信号。为了解决这个问题，可以采用更强的基础模型。但是这样大大增加了计算成本。本文提出了通过在正式进行强化学习前增加监督微调阶段。以下为两种不同类型的监督微调策略：

直接监督微调

这种方法在(q,a)问答对上进行直接微调，其中q为图论问题的文字描述，a是最终答案。因为没有包含推理过程，无法显式地教模型如何进行逐步推理，只能学习到从q到a的映射。

思维链监督微调

通过采样获得三元组(q.c.a)其中c为思维链，采用自然语言描述，由性能更强的LLM生成。在本文中，采用了Qwen2.5-32B-Instruct模型生成样本。

三、实验部分

3.1 G1模型在图论任务上的基准测试

通过图二可以看到，G1-7B在所有难度级别上都显著超越了大部分模型。即使是G1-3B，平均准确率也达到了59.76%，优于Qwen2.5-72B-Instruct和LIama-3.1-70B-Instruct两个70B的模型

图二：G1模型基准测试

将思维链监督微调换成直接监督微调，G1模型的表现也非常突出。这说明即使只是直接拟合答案，LLM也能够在图任务中学到一些有效的模式。然而，当把模型参数从3B提升到7B时，并没有有效的提升。而采用思维链的G1模型尽管得分较低，但是具有更好的扩展性与泛化性。

使用32个不同随机种子重复实验，结果在所有模型和任务难度上标准差均<1%，紧接着为了验证对prompt的鲁棒性，让 GPT-4o 生成三个语义等价的提示，测试结果标准差 <1.5%，说明模型对语句变化不敏感。

以Qwen2.5-32B-Instruct为基础模型进行扩展训练，得到G1-Zero-32B，实验结果见图三。

图三：G1-Zero-32B和Qwen-2.5-32B-Instruct在Erdős数据集上对比

3.2 G1在陌生领域和任务上的可迁移性

3.2.1 G1在其他图推理数据集上的迁移能力

在两个图推理数据集GraphWiz和GraphArena上进行实验，实验结果见图四图五。由此可见，G1有很强的零样本泛化能力。

图四：在GraphWiz上的准确率

图五：在GraphArena上的准确率

3.2.2 G1在基于真实世界的、非图论任务上的表现

选取两个标准问题：节点分类和连接预测。使用 Wang 等人提出的标准基准数据集.每个样本包含： 目标节点或节点对的 ID 与标题以及相邻节点的文本与结构特征。实验结果见图六。可以看到，G1模型的表现依然优越。G1-3B超过了Qwen2.5-3B-Instruct。而G1-7B有着87.29%的最高平均分数。

图六：节点分类和连接预测任务的测试结果

3.2.3 G1在图以外领域的推理能力

选用了三个广泛使用的基准数据集，GSM8K：小学到中学水平的数学文字题；MATH：高中到竞赛级别的数学问题以及MMLU-Pro：涵盖化学、经济学、计算机科学等多个领域的大型多任务数据集。全面评估G1的通用推理能力。实验结果见图七。

图七：在图之外的任务上的测试结果

作者发现，基于思维链监督微调训练，会导致模型的通用能力出现一定程度的下降。 这种退化可能是因为这种方法倾向于让模型记忆模式，而不是激励其学习真正可泛化的推理技能。

然而，随后的强化学习阶段尽管只在图任务上进行训练 却恢复了 3B 和 7B 两个模型的推理能力。 尤其是 G1-7B 模型，在三个通用推理基准上全面超越了初始的 Qwen-7B 模型：

并且，G1-7B 在一些与图推理几乎无关的非 STEM 任务上（如经济学）， 也显著优于 Qwen-7B-Instruct。

四、总结

本文探索了使用强化学习来提升大语言模型在图推理任务上的能力，并全面评估了G1模型在多种场景下的迁移能力。结果显示：模型具有强大的零样本泛化能力。这种方法可以为今后开发高效、通用的图推理器提供指导。

文章链接：https://arxiv.org/abs/2505.18499

本期责任编辑：杨成

本期编辑：赵明宇

北邮 GAMMA Lab 公众号

主编：石川

责任编辑：杨成

编辑：赵明宇

免责声明：

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。

任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。

本文转载自：北邮 GAMMA Lab 谢天阳《论文解读 | 用强化学习指导LLM在图上推理》