KDD 2026论文解读:让大模型真正理解图结构的Graph Token方法｜浙江大学-阿里巴巴集团人工智能安全联合实验室专场直播回放(4)

虞 刚

集团安全部行为风控算法工程师，研究图算法/团伙挖掘、大模型自动构图、图增强大模型等技术在行为风险防控场景的应用。在WWW、KDD、ICASSP、CIKM、ECML等会议发表论文若干。 

今天带来的是在KDD 2026上刚录用的一篇工作，题为"Towards Next Graph Token Prediction: Discrete Graph Tokenization for Structural Reasoning"，即面向下一个Graph Token预测、用于大模型结构推理的离散图Token化方法。

图结构数据在真实世界中广泛存在，例如社交网络、化学分子网络以及电商图谱网络等，均可被建模为图结构数据。如何对图结构数据进行建模、挖掘和学习，是近年来被广泛关注的问题。在机器学习时代，一个重要的问题是如何将离散、非欧几里得的图信号处理为可被学习的表征。在2017年左右开始兴起的图神经网络（GNN）以及Graph Transformer等一系列模型被广泛用于图表征学习。这些表征可以被用于下游的具体任务，例如对图中某一节点的分类预测、整个子图的分类，以及图上节点之间是否存在关联的链路预测。

然而，GNN和Graph Transformer存在一些根本性的局限。一方面，作为黑盒模型，其端到端的过程本质上是不可解释的。另一方面，其可迁移性较弱——不同架构可能适用于不同的图数据和任务，在一种数据上训练得到的模型难以迁移到另一种数据上。随着大语言模型（LLM）时代的到来，LLM在自然语言任务上表现出良好的性能，包括逻辑推理、文本理解、代码生成等任务，同时具备良好的跨域推理能力以及结果的可解释性。

大模型的推理能力近期也被广泛拓展到语音、图像等多模态任务上，由此提出了多种多模态大模型。近期在图语言模型领域的工作中，研究者希望大模型同样能够针对图任务进行推理，从而弥补GNN或Graph Transformer在结果可解释性和跨域迁移能力上的短板。例如，当存在多个领域的图数据时，希望能够将其迁移到其他领域进行处理，这正是LLM上所探索的能力。

由此，提出了利用LLM进行图推理的设想。要实现这一目标，必须将非欧几里得的图转化为适配LLM的序列化表示，即Graph Tokenization。

直观的方法之一是直接用自然语言来描述图结构。例如使用邻接表（Adjacency List），将对应的节点列出，并将节点之间的关联关系列出，作为自然语言描述。然而，这种方式的信息密度很低，仅包含边的信息，对于深层结构难以进行有效表达，在推理过程中也比较容易丢失关键信息。

第二种方式是借助传统的图模型进行Embedding编码，即将图结构直接编码为一个高维向量。但编码后的图序列不具备可逆性，即LLM无法从图序列恢复到原始信号，可解释性较差。因此，需要探索一种能够在确保可逆性的同时实现结构语义高效编码的方法。一个自然的思路是让单个Token中存储更多的图结构信息，同时确保图可以被拆分为Token的形式。这样，对图的定义从边的集合转换为Graph Token序列，从而保证可逆性和高结构信息密度。由此，图上的任务从简单的"预测下一条边"转变为"预测下一个子结构"，即Next Graph Token Prediction。

具体来看，当输入一张图数据时，根据上述三种方式可以得到不同的表示。第一种是文本描述方式，但一方面会丢失聚焦信息，遗漏重要内容；另一方面对高阶语义无法进行有效理解。

第二种是通过GNN或Graph Transformer等进行Embedding编码，编码后作为高维向量输入。这是传统多模态领域常用的方式，但在图推理场景中很难恢复原始图结构的结构化语义，图的可解释性和可逆性未能得到很好的保留。因此，提出通过定义图上的基础图词表的形式，将图表示为多个图元（Graphlet）的组合，同时兼顾结构语义和可逆性，实现图在大模型上的推理。

整个工作分为几个大部分。第一部分是预定义的Graph Token Vocabulary（图词表），即图上的一些基础单元，可以类比自然语言中的字母或词组。进而将一个图拆分成多个基础Graph Token。接下来分为三个训练阶段：Pretrain（预训练）、SFT（监督微调）和RL（强化学习）。

Pretrain阶段的目标是让模型理解每个Graph Token的含义。词表中包含约31个Graph Token。在SFT阶段，通过具体任务，基于Token进行任务推理和微调。在RL阶段，考虑到SFT阶段可能会陷入固定模式的问题，通过奖励机制（如推理验证和基础正确性奖励）来赋予模型一定的泛化能力。

首先介绍Graph Tokenizer部分，即如何将一个图拆分成多个Token。具体方法是：首先抽取子图，优先选取密度最高的种子节点，从该节点出发进行贪心的广度优先搜索（BFS），搜索到对应的Token结构。接下来需要将检索到的子结构与Graph Token词表中的31个Token进行匹配。

匹配方式采用WL哈希（Weisfeiler-Lehman Hash），通过约五轮迭代即可表达一个图的同构性。利用同构性进行快速匹配，避免逐一对比一个结构与其他所有结构的匹配程度。

第二部分是结构语义的预训练。预训练的任务设计如下：一个Token可以被拆分为多个子Token，多个子token也可以被合并为一个大的Graph Token；将Graph Token的拆解和合并过程作为预训练语料，使大模型能够理解每个Token在结构上的层级关系。

右侧展示了一些训练数据的示例。例如，一个包含三个节点的结构，从定义的节点及其对应的Graph Token类型出发，可以拆解为等于另外两个子结构的形式，不断进行拆解，使模型能够将复杂的大图拆解为不同的子模块，再根据子模块的结构进行推理，实现粗粒度的转换。

第三部分是监督微调（SFT）。仅具备结构知识不足以解决复杂问题，模型并不知道对于具体问题应该优先关注哪些Token，也不清楚如何逐步解题。因此我们精心设计了SFT数据，内含执行特定任务的CoT模板，模板设计原则是找到任务相关的Token，教会模型如何使用推理能力对Token进行拆解、重组和验证，使推理过程变得显式可解释。这样就可以赋予模型解决具体图任务的能力，例如最短路径是如何一步步推理出来的，或者如何判断成环的性质。

第四部分是强化学习。在SFT阶段，模型学会了固定的Chain-of-Thought推理模板，虽然具备了一定的基础能力，但仍较为依赖单一路径。这里结合GRPO（Group Relative Policy Optimization）算法进行优化，通过设计对应的奖励函数，对不同的推理策略设置奖励机制。

奖励主要分为三部分。第一部分是结果奖励：输出正确答案时给予奖励。第二部分是真实性奖励：强调推理过程中使用的Token均来自原始图的拆解结果，而非凭空捏造（例如出现不存在的三角形即为捏造）。第三部分是推理步骤检查：对中间步骤进行验证，例如推理过程中等式两边的相等性。总体而言，整个流程是将图拆分为不同的Graph Token，对Graph Token进行大模型预训练，预训练完成后进行SFT以执行图推理任务，最后通过强化学习约束推理步骤，从而实现大模型上的图结构推理。

实验部分主要在七个经典图推理任务上进行评测：连通性、环路检测、度计算、最短路径、图同构、最大团以及最大公共子图。GraphVulcan方法相比一阶编码方式具有更好的表现，相对于Baseline提升较为明显。一个显著的发现是，在SFT与GRPO的性能对比中，主要差异体现在最短路径任务上有较为明显的提升。对此的解释是：最短路径任务存在一个不断探索的过程，每一轮在不断向前探索，而通过强化学习获得的奖励机制能够赋予模型更好的探索能力。在对比实验中，分别使用了一阶编码方法以及GraphVulcan方法进行图推理任务。在性能和效率方面，GraphVulcan方法有显著提升。

此外还对比了各种条件下推理时间的变化。在绝大部分情况下，使用GRPO强化学习方式比SFT方式得到的推理时间更少。唯一的例外是在最短路径任务上耗时可能更多，这是因为模型在进行更优路径的探索，从而保证效果。在其他任务上，在保证效果的同时，时间上有较大的缩短。

在TUDataset上也初步验证了Graph Token在真实复杂任务上是否同样有效。我们在公开的Benchmark上对比了一阶编码形式和GraphVulcan方式，采用相同的SFT方式进行训练。GraphVulcan在三个数据集上均表现出较高的平均收益。其中提升最大的是Reddit-Binary数据集。通过统计数据集上不同种类Graph Token在各分类上的分布，可以发现分布上的差异。因此，通过Graph Token的方式可以表达图数据在整个类别上的特征分布，相比传统仅依赖边列表的形式，能够更好地表达不同图结构的变化。在Reddit-Binary数据上可以明显看出，两个分类之间的分布差异较大，这也解释了Graph Token在该二分类任务上效果更好的原因。

关于为何采用经典图任务进行评测这个问题，需要澄清的是替代经典图算法并不是GraphVulcan 的目标。我们之所以采用这些经典图任务，是因为我们好奇一个更基础、更底层的问题：GraphVulcan 首创的这条图词表路线，是否能真正赋予大语言模型对纯粹图结构的‘原生理解力’？事实证明这条路线是可行的。

最后阐述GraphVulcan的现实意义。一方面，该方法将图作为一种语言与大模型进行深度结合，而非将图以文本方式表达后作为大模型的输入，从而使图结构能够更好地进行结构上的推理，而非纯文本或间接推理。Graph Vulcan在现实任务中的适配也是后续要做的工作，例如将GraphToken图上的特征信息进行有效融合，以及为不同领域的图数据（如化学分子图等）设计其专用图词表。

📌往期推荐

AAIG课代表，获取最新动态就找她👇

关注公众号发现更多干货❤️