图神经网络分享系列-GGNN(GATED GRAPH SEQUENCE NEURAL NETWORKS)(二)

对于第k个输出步骤，节点注释矩阵表示为X(k) = [ $x_1^{(k)}$ ;...; $x_{|v|}^{(k)}$ ]⊤ ∈ R|V|×LV。使用两个GG-NN F_o(k)和F_x(k)：F_o(k)用于从X(k)预测o(k)，F_x(k)用于从X(k)预测X(k+1)。X(k+1)可视为从步骤k传递到步骤k+1的状态。

F_o(k)和F_x(k)均包含传播模型和输出模型。在传播模型中，第k个输出步骤的第t次传播步骤的节点向量矩阵记为H(k,t) = [ $h_1^{(k,t)}$ ;...; $h_{|v|}^{(k,t)}$ ]⊤ ∈ R|V|×D。在步骤k中，通过按节点0扩展X(k)来设置H(k,1)。模型概览如图2所示。

另一种方案是让F(k)和F(k)共享单一传播模型，仅保留独立的输出模型。这种简化变体训练和评估速度更快，且在许多情况下能达到与完整模型相近的性能水平。但当F(k)和F(k)所需的传播行为不同时，该变体可能表现不佳。

节点标注输出模型的描述

引入一种节点标注输出模型，用于从 ( $H^{(k,T)}$ ) 预测 ( $X^{(k+1)}$ )。该预测针对每个节点独立进行，采用神经网络实现。

神经网络的输入为 ( $h_v^{(k,T)}$ ) 和 ( $x_v^{(k)}$ )，输出为一组实值分数向量。

训练GGS-NN的两种设置

第一种设置指定所有中间标注 ( $X^{(k)}$ )，第二种设置仅给定初始标注 ( $X^{(1)}$ )、图结构和目标序列进行端到端训练。前者在具备领域知识（如节点内部状态应包含特定中间信息）时可提升性能，后者更具通用性。以下分别描述两种方法。

带观测标注的序列输出

在针对图的各部分依次生成预测的任务中，为确保每个部分仅被预测一次，可为每个节点分配一个二进制标记，表示该节点是否已被“解释”。某些场景下，少量标注足以捕捉输出过程的状态。此时，可通过目标中间标注直接将这些信息输入模型。若标注足够充分，可设计条件独立的GG-NN模型：给定标注 ( $X^{(k)}$ ) 时，序列预测任务可分解为单步预测任务，并作为独立的GG-NN训练。测试阶段，前一步预测的标注将作为下一步的输入。这与数据完全观测时训练有向图模型类似。

带隐标注的序列输出

更一般地，当训练时无法获取中间节点标注 ( $X^{(k)}$ )，可将其视为网络中的隐藏单元，通过反向传播对整个序列进行联合训练。

五、解释性应用示例

本节通过具体案例展示GGS-NNs的应用，重点关注bAbI人工智能测试任务（Weston等，2015）和两类图算法学习任务。

5.1 bAbI任务

bAbI任务旨在检验AI系统应具备的基础推理能力，包含20项测试，涵盖演绎、归纳、计数和路径查找等基本推理形式。

通过基础转换流程，bAbI任务可映射为GG-NNs或GGS-NNs的输入。采用bAbI代码中的--symbolic选项获取仅包含实体间关系序列的故事文本，随后将其转换为图结构：实体映射为节点，关系映射为带标签的边。完整故事被整合为单一图。问题由数据中的eval标记，包含问题类型（如has_fear）和参数（如一个或多个节点）。参数转换为初始节点标注——第i个参数节点的标注向量第i位设为1。例如，若eval行为eval E > A true，则节点E的初始标注为x_E = [1,0]^T，节点A为x_A = [0,1]^T，其余节点为x_v = [0,0]^T。问题类型为1（对应“>”），输出类别为1（对应“true”）。部分任务含多问题类型（如任务4含e、s、w、n四类），此时为每类训练独立GG-NN。所有实验均未使用强监督标签或中间标注。

该转换虽简单，但会丢失部分故事信息（如输入的时间顺序），且难以处理三元及以上关系（例如“昨天约翰去了花园”无法直接映射为简单边）。需注意的是，将自然语言泛化为符号形式本身具有挑战性，因此该方法无法直接推广至任意自然语言场景。突破这些限制是未来研究方向。

即便如此，通过此转换仍可构建多种bAbI任务，包括最难的“路径查找”（任务19）。实验表明符号表示对RNN或LSTM性能提升有限，而GGS-NNs能在少量训练样本下解决问题。此外，开发了两项类bAbI新任务：图上的最短路径输出，以及随机连通2-正则图上的欧拉回路生成。这些实验旨在展示GGS-NNs处理多样化问题的能力。

示例 1

以下是符号数据集中的实例，来自 bAbI 任务 15（基本演绎推理）。

输入数据说明

前8行描述事实关系，GG-NN模型将利用这些事实构建图结构。大写字母代表节点，"is"和"has fear"被解释为边的标签或边类型。

问题描述

最后4行是4个基于输入数据提出的问题。其中"has fear"被解释为问题类型。每个问题中仅有一个特殊节点（例如"eval B has fear"中的B），需为该特殊节点的注释向量赋值为1，其他所有节点赋值为0。

序列模型处理

对于RNN和LSTM模型，数据需转换为如下所示的token序列格式：

节点用 n<id> 表示，边用 e<id> 表示，问题类型用 q<id> 表示。额外添加了标记 eol（行结束符）和 ans（答案），以便 RNN 和 LSTM 能够访问数据集中完整的可用信息。最后的数字是类别标签。

示例 2
以下是第二个示例，展示了 bAbI 任务 19（路径查找）的符号数据集中的一个实例。

边缘类型与路径问题

前四行描述边缘类型，s、n、w、e（此例未出现e）代表不同的边类型。最后一行是路径问题，答案为一组方向序列（如w,s），表示从B到A的路径需先向西到E，再向南到A。问题中的s、n、w、e被视为输出类别。

训练细节

所有任务生成1000个训练样本和1000个测试样本，其中50个训练样本用于验证。评估模型性能时，若单个bAbI任务包含多个问题，每个问题的预测独立评估。由于数据集生成存在随机性，每个任务生成10组数据集，最终报告10组评估结果的均值与标准差。

训练规模与目标

解释性任务初始仅用50个训练样本训练模型，逐步增加至100、250、500、950（保留50个验证样本），直至测试准确率达到95%或更高（符合Weston等人2015年提出的bAbI成功标准）。记录各方法达到95%准确率所需的最小训练样本量及对应准确率。所有实验的传播过程展开5步。

模型配置

bAbI任务4,15,16,18,19：使用GG-NN，节点向量维度分别设为D=4、D=5、D=6、D=3和D=6。
GGS-NN：采用简化变体，F_o(k)与F_x(k)共享单一传播模型。
最短路径与欧拉回路任务：节点向量维度D=20。

训练策略

所有模型使用Adam优化器充分训练，通过验证集选择最佳模型以避免过拟合。

5.1.1 单步输出

选取了四个符合上述限制条件且仅需单步输出的bAbI任务：任务4（二元关系）、任务15（基础演绎）、任务16（基础归纳）和任务18（大小推理）。对于任务4、15和16，采用节点选择型GG-NN（图神经网络）；任务18则使用图级分类版本。所有GG-NN模型的参数量均少于600个。

作为基线，使用RNN和LSTM模型在原始序列形式的符号数据上进行训练。RNN和LSTM采用50维嵌入向量和50维隐藏层，在序列末尾预测单步输出，并作为分类问题处理，损失函数为交叉熵。RNN和LSTM的参数量分别约为5千和3万。

测试结果如表1所示。在所有任务中，GG-NN仅需50个训练样本即达到完美测试准确率，而RNN/LSTM基线模型要么需要更多训练样本（任务4），要么无法完成任务（任务15、16和18）。

表2进一步展示了任务4中基线模型在不同训练数据量下的性能表现。虽然RNN和LSTM最终能近乎完美地解决该任务，但GG-NN在数据量显著更少的情况下即可达到100%准确率。

5.1.2 序列输出

bAbI任务19（路径寻找）被认为是所有bAbI任务中最具挑战性的任务（例如，Sukhbaatar等人2015年的研究指出，在不使用强监督的情况下，所有方法的准确率均低于20%）。本研究将GGS-NN应用于该问题，数据仍采用符号形式（因此结果无法与Sukhbaatar等人的研究直接对比）。每个输出序列的末尾额外添加了“结束”类别；测试时，网络将持续生成预测，直至输出“结束”类别。

实验结果

表3展示了该任务的结果。RNN和LSTM在此任务上均表现失败。然而，仅使用50个训练样本的GGS-NN在测试准确率上显著优于RNN和LSTM。

5.2 学习图算法

基于图的算法问题，进一步开发了两个新的类bAbI任务：最短路径和欧拉回路。
针对最短路径任务，通过生成随机图并构建包含图中所有边的故事描述。问题通过随机选择两个节点A和B，要求给出连接两节点的最短路径（以节点序列表示）。数据生成时限制仅包含存在唯一最短路径（长度至少为2）的问题。

欧拉回路任务中，生成一个随机的2-正则连通图和一个独立的干扰图。问题给出两个起始节点A和B，要求返回从A到B开始的给定子图上的欧拉回路（同样以节点序列表示）。

表3结果显示，RNN和LSTM在两项任务上均失败，而GGS-NN仅用50个训练样本即实现了完美预测。

六、基于GGS-NN的程序验证

GGS-NN的研究动机源于程序验证的实际应用需求。在自动化程序验证中，推断程序不变量是关键步骤，这些不变量用于近似描述程序执行过程中可达的状态集合。针对数据结构的不变量推导仍是一个开放性问题。以右侧的简单C函数为例：

要证明该程序确实能连接链表a和b，且所有指针解引用操作有效，需在循环的每次迭代中对程序堆内存进行数学表征。为此，需使用分离逻辑（O'Hearn等，2001；Reynolds，2002），其通过归纳谓词描述抽象数据结构。例如，链表段的定义为：
ls(x,y) ≡ x = y ∨ ∃v,n. ls(n,y) ∗ x ↦ {val : v, next : n}
其中，x ↦ {val : v, next : n} 表示指针x指向一个包含val和next字段的内存区域，字段值分别为v和n。连接符∗类似于布尔逻辑中的∧，但额外要求操作数指向堆内存的“分离”部分。因此，ls(cur, NULL)意味着cur为NULL，或指向堆中的两个值v和n，而n又由ls递归描述。公式 ∃t. ls(a, cur) ∗ ls(cur, NULL) ∗ ls(b, t) 是该循环的不变量（即进入循环时及每次迭代后均成立）。借此可证明程序不会因解引用未分配内存地址而失败（该性质称为内存安全），并通过霍尔式验证方案（Hoare，1969）证明函数确实实现了链表连接。

此过程中最困难的部分是生成描述数据结构的公式，这正是机器学习技术的应用场景。给定一个程序，通过多次运行并提取关键程序位置的内存状态（以图形式表示），可预测分离逻辑公式。静态程序分析工具（如Piskac等，2014）可验证候选公式是否足以证明目标性质（如内存安全）。

6.1 形式化：堆状态表示为图

输入为有向图（可能含环），用于表示程序的堆内存状态。这类图可从程序内存状态自动构建。每个节点 $v$ 对应一个内存地址，存储指针序列 $v_0, \ldots, v_k$ （非指针值在此工作中被忽略）。图的边反映指针值，即节点 $v$ 带有标签 $0, \ldots, k$ 的边分别指向 $v_0, \ldots, v_k$ 。部分节点被标记为程序变量。

示例输入图如图3中的“Input”所示。节点内显示其ID（即内存地址）。边标签对应程序中的特定字段，例如标签0对应前一节示例函数中的next指针。对于二叉树，还存在left和right指针，分别指向树节点的左右子节点。

输出表示

目标是通过数学形式描述堆的形状。模型采用语法受限的分离逻辑公式，形式为：
$\exists x_1, \ldots, x_n. a_1 * \ldots * a_m$
其中每个原子公式 $a_i$ 为以下之一：

$\text{ls}(x, y)$ （从 $x$ 到 $y$ 的链表）
$\text{tree}(x)$ （以 $x$ 为根的二叉树）
$\text{none}(x)$ （ $x$ 处无数据结构）

存在量词用于命名堆节点，这些节点需描述形状但未被程序变量标记。例如，描述“平底链表”（尾部带环的链表）时，需命名环上的首个节点，分离逻辑中可表示为 $\exists t. \text{ls}(x, t) * \text{ls}(t, t)$ 。

数据生成

可通过合成（标记）数据集生成解决此问题。具体步骤包括：

固定一组谓词（如ls、tree，可扩展为双向链表段、多叉树等）及其归纳定义。
枚举使用给定程序变量的分离逻辑公式实例化这些谓词。
对每个公式，枚举满足该公式的堆图。最终得到由堆图与关联公式组成的配对数据集，供学习过程使用。

6.2 作为GGS-NN的公式化表达

从数据生成过程中可以轻松获取中间预测步骤的节点标注。因此，训练了一个带观测标注的GGS-NN变体（训练时观测，测试时不观测），用于从堆图中推断分离逻辑公式。另一种选择是使用无观测的GGS-NN变体进行端到端学习。

该流程将分离逻辑公式的生成分解为多个步骤。决定是否声明存在性变量，若声明则选择对应变量的节点。声明存在性变量后，遍历所有变量名并生成描述当前变量对应节点数据结构的分离逻辑公式。

完整预测分离逻辑公式的算法见算法1。使用了三种显式节点标注：is-named（堆节点被程序变量或声明的存在量化变量标记）、active（参照算法）和is-explained（堆节点已被预测为数据结构的一部分）。初始节点标签可直接从输入图计算得出：is-named对程序变量标记的节点开启，active和is-explained始终关闭（第2行实现）。算法中带注释的行通过GG-NN实现，即算法1是GGS-NN模型的一个实例。图3展示了算法运行的初始阶段示例，每个步骤对应算法中的一行。

6.3 模型设置细节

GGS-NN模型的实现细节

采用完整的GGS-NN模型架构，其中F(k)和F(k)使用独立的传播模型。所有GG-NN组件在GGS-NN流程中的传播过程均展开10个时间步长。

节点表示维度配置

步骤(†)（判断是否需要声明更多存在量化变量）和步骤(‡)（确定哪些节点需声明为存在量化变量）相关的GGS-NN模块采用D=16维节点表示。其余所有GGS-NN组件均使用D=8维表示。

训练优化设置

使用Adam优化器（Kingma & Ba, 2014）进行参数优化，训练过程采用20个图的小批量，直至训练误差降至极低水平。针对图级别分类任务，通过人工平衡类别使每个小批量包含均等的各类样本。

模型规模与性能

所有GGS-NN组件参数量均控制在5k以下，训练过程中未观察到过拟合现象。该配置在保持模型轻量化的同时确保了训练稳定性。

6.4 批量预测细节

在实际应用中，输入通常为一组堆图（heap graphs），系统需输出一个能描述并兼容所有输入图的统一公式。这些堆图可能来自程序执行过程中不同时间点的堆状态快照，或同一程序在不同输入下的多次运行结果。这种模式被称为“批量预测”，与主论文中针对单图的预测场景形成对比。

批量预测实现方法

为执行批量预测，系统并行运行多个GGS-NN模型（每个堆图对应一个模型）。在每一步预测时，所有图中对应GGS-NN的输出会被聚合：

节点选择输出：通过共享的命名变量关联不同图中的节点，这是批量预测聚合的关键。命名变量t的得分计算为 $o_t = \sum _g o^{g}_{V_g(t)}$ ，其中 $V_g(t)$ 将变量名t映射到图g中的节点， $o^g_{V_g(t)}$ 为图g中变量t的输出得分。对得分 $o_t$ 应用softmax等价于计算联合概率 $p(\text{toselect}=t) = \prod_g p_g(\text{toselect}=V_g(t))$ 。
图级分类输出：将同一类别在所有图中的得分相加，即 $p(\text{class}=k) = \prod_g p_g(\text{class}=k)$ 。
节点标注更新：各图的节点标注独立更新（因节点集不同），但当算法更新某一命名变量的标注时，所有图中与该变量关联的节点会同步更新。

训练与扩展

训练时，中间步骤的标签可从数据生成过程中获取，因此训练过程仍可分解为单图单输出的模式。对于嵌套数据结构（如列表的列表）的更复杂场景，可参考Brockschmidt等（2015）的研究。GGS-NN模型已成功扩展至此类场景，详见附录C。

6.5 实验部分

本研究构建了一个包含327个涉及三个程序变量的分离逻辑公式数据集，每个公式对应498个堆图，共生成约16万组公式/堆图组合。评估时采用6:2:2的比例将数据按公式划分为训练集、验证集和测试集（测试集中的公式未出现在训练集中）。正确性通过预测公式与真实值是否逻辑等价来衡量：具体方法是对变量名和公式顺序进行规范化后检查完全匹配。

方法对比

基于GGS-NN的新模型与此前提出的方法（Brockschmidt等，2015）进行了对比。旧方法将每个预测步骤视为标准分类任务，需依赖复杂的人工特征工程，准确率为89.11%；而新模型无需特征工程且仅需极少领域知识，准确率提升至89.96%。

实例与应用

图4展示了GGS-NN模型对嵌套数据结构的堆图及其对应分离逻辑公式的预测结果，该实例运用了前文提出的批处理扩展技术。

新模型已成功应用于程序验证框架，通过为定理证明器提供所需的程序不变量，验证了插入排序等链表操作算法的正确性。表4列出了一组链表操作基准程序及其对应的分离逻辑不变量（由GGS-NN生成），这些不变量在验证框架中被成功用于证明程序正确性。

当前管线的进一步扩展已被证明能够成功验证更复杂的程序，例如排序程序和各种其他列表操作程序。

下一篇会详细讨论相关研究和一些附录细节：

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

最新 AI 论文盘点（2026-04-09）：5 篇新作看个性化对齐、Agent 在线训练、多模态病理与视频运动控制

AI研究正从"泛能力堆高"转向"系统瓶颈拆解"。5篇新论文聚焦关键问题：1)个性化奖励模型仅75.94%准确率，揭示通用与个性化对齐差异；2)Android Agent在线训练通过单状态多动作采样提升1.4倍效率；3)视频生成需解耦物体/相机运动与因果关系；4)病理WSI的MoE路由需显式约束防失衡；5)LLM难以稳定执行语法规则转导，低资源翻译需谨慎。这些

AtomGit开源社区

[具身智能-306]：Token详解

简单来说，Token 是大模型处理文本的最小信息单元。计算机并不认识“字”或“词”，它只认识数字。为了让模型理解人类语言，我们需要把一段文本“切碎”成一个个小块，这些小块就是 Token。它不是单纯的“字”或“词”英文中：一个 Token 可能是一个单词（如 "Apple"），也可能是单词的一部分（如 "Trans" 和 "former" 组成了 "Transformer"），甚至可能包含标点符号

AtomGit开源社区

如果你只想少折腾，学 AI 编程最省事的方式是什么？

说到底，学 AI 编程最省事的方式，不是一个绝对统一的答案，而是看你现在处在什么阶段。想高控制感、后面要深度接入：选自己配 API想先体验 AI 能力：选现成客户端想少折腾、快开始、先做出项目：优先选现成平台如果你只是想尽快开始，而不是先把前面所有东西都研究明白，那“少折腾”本身，就是最适合新手的路径。