SNACK框架：用序列模型生成图结构的统一新范式

图生成一直是深度学习的硬骨头——图数据没有天然的序列顺序，节点和边的离散特征让传统序列模型难以直接套用。最近提出的SNACK（Sequential Notation for Adjacency and Connectivity Knowledge）框架，通过一种巧妙的字符串表示方法，把图生成问题转化为序列建模问题，同时解决了有效性和效率两大痛点。

核心思路：把邻接矩阵"拉直"成字符串

SNACK的基本操作很直观：只编码下三角邻接矩阵中的非零元素，将其线性化为一个序列。这个设计建立了一个双射——合法的SNACK序列与有序邻接矩阵一一对应。

这意味着什么？任何符合语法的序列都必然对应一个合法的图，反之亦然。这种双向映射是整个框架的基石，它让序列模型（如Transformer、RNN）可以无缝迁移到图生成任务上。相比之前需要复杂图神经网络编码器的方法，SNACK直接用语言模型的架构就能处理图结构数据。

下三角邻接矩阵是指只保留邻接矩阵中对角线及其以下部分（不包含对角线）的三角形区域。对于包含 n 个节点的无向图，其邻接矩阵是对称的，上三角与下三角信息完全冗余。因此，仅保留下三角的非零元素即可无损地还原整个图结构。同时，下三角中元素的自然行优先遍历顺序隐式地为节点赋予了某种排列，从而将无序的图结构转换成一条确定的序列。这一选择避免了图的对称性引发的重复编码问题，使得同一个图只对应一个规范形式的下三角序列，是 SNACK 能够建立双射的关键。

双射（Bijection） 指的是两个集合之间的一一对应关系：每个合法 SNACK 序列唯一确定一个有序邻接矩阵，反之每个有序邻接矩阵也唯一确定一个合法 SNACK 序列。这个性质保证了序列空间与图空间在结构上等价，因此用序列模型建模图生成问题时，不会引入表达能力上的损失，也不会产生表示上的歧义。没有双射，序列模型就可能生成无法映射回图的序列，或者多个不同序列表示同一个图，导致训练目标混乱。

无效logit掩码：确保100%合法输出

序列生成模型的一个常见问题是会产出不符合约束的输出。在分子生成场景中，这表现为生成违反化学价规则的原子连接；在一般图生成中，则可能产生不符合排序规则的邻接结构。

SNACK通过无效logit掩码机制解决这个问题。在解码每一步时，模型会根据已生成的部分序列动态计算哪些token在结构上是合法的，将非法token的logit设为负无穷。这种约束是精确的——论文声称可以保证100%的生成序列都是合法的。

这个特性的实际价值很大。传统方法通常需要后处理步骤来修正非法输出，或者依赖强化学习中的惩罚项来间接引导模型，而SNACK把结构约束直接编码进了生成过程本身。

Logit 是指神经网络在输出层（尤其是分类任务中）产生的未经归一化的原始分数，通常再经过 Softmax 函数转换为概率。在序列生成模型中，每一步需要对词表大小个 token 分别计算 logit。如果直接根据概率采样，模型可能选择结构上非法的 token，例如分子生成中让某原子超出最大价数。

失效 logit 掩码（Invalid Logit Masking） 是一种在解码阶段强制施加约束的技术：对当前步骤所有可能 token，根据已生成前缀判断每个 token 是否会导致非法结构，将非法 token 对应的 logit 设为负无穷大（-∞）。这样，经过 Softmax 后这些 token 的概率为 0，模型永远不会采样到它们。该方法将图结构的语法约束直接嵌入到生成过程中，而无需在事后检查或修正输出，因此论文可以声称 100% 的合法性保证。相较于强化学习中的惩罚项，掩码是硬约束，不依赖模型学习，更可靠且可解释。

GFlowNet训练：显式处理节点排序对称性

SNACK另一个重要贡献是让GFlowNet可以直接在字符串空间上训练。GFlowNet是一类用于学习概率分布的生成模型，其目标是让生成概率与目标奖励成比例。

图数据有一个固有难题：同一个图可以有多种节点排序方式，但它们在本质上等价。SNACK显式地考虑了这种节点排序对称性，使得GFlowNet的训练目标能够正确处理这种等价关系。实验表明，相比直接在图上操作的方法，SNACK在GFlowNet训练吞吐量上有显著提升。

GFlowNet（Generative Flow Network） 是一类基于流匹配的生成模型，其学习目标是使生成某个对象 x 的概率正比于给定的奖励函数 R(x)，即 P(x) ∝ R(x)。训练时通常构造一个前向策略（从初始状态生成对象）和一个反向策略（从对象回溯到初始状态），并令两者在流守恒约束下一致。在图生成任务中，奖励可以定义为分子性质、图的有效性等。

节点排序对称性 指的是同一张图在邻接矩阵的不同节点排列下会呈现出不同的矩阵形式，但它们在语义上是同一个图。如果生成模型不考虑这种对称性，就会把同一图的不同排序当作不同样本，导致概率分配错误。SNACK 通过将图固定为下三角邻接矩阵的规范排序（例如按节点索引顺序），隐式消除了这种对称性。因此，GFlowNet 在字符串空间训练时无需额外的对称性处理，每个图只对应一个序列，这既简化了训练目标，又避免了学习冗余的多重表示，显著提升了训练效率。

实验表现：质量与效率兼得

在标准图生成任务和分子分布学习基准上，SNACK取得了有竞争力的样本质量。更关键的是效率提升——由于序列生成可以利用成熟的序列模型基础设施（如KV缓存、并行解码等），其吞吐量远超基于图的生成方法。

探测分析（probing analysis）揭示了一个有意思的现象：仅在序列监督下训练的模型，内部表征中仍然编码了有意义的局部和全局图结构信息。这说明序列化并没有丢失图的结构信息，模型能够从字符串序列中"学会"图的内在规律。

探测分析（Probing Analysis） 是一种用于理解神经网络内部表征的常用技术：在模型的隐藏层表示上训练简单的分类器（如线性分类器），用以预测某些预定义的结构属性（例如节点度、最短路径长度、局部子图类型等）。如果简单分类器能高准确率地预测这些属性，说明模型内部已经自发地编码了这些信息。在 SNACK 实验中，探测分析揭示了纯序列监督训练出的模型，其内部表示仍然包含有意义的局部和全局图结构信息，这证明序列化并没有丢失图的关键结构特征，模型从字符串序列中学会了图的规律。这一发现增强了对序列模型处理图数据能力的信心。

为什么值得关注

SNACK的意义在于它提供了一条务实的技术路线：不需要设计复杂的图专用架构，而是把图转化为序列，复用序列模型领域多年积累的工程优化和架构创新。

当然，SNACK也有其适用范围——它目前主要针对节点和边特征为离散值的图。连续特征图、动态图等场景是否适用，还需要进一步探索。但作为概率图生成的一个通用框架，SNACK在序列模型与图结构之间架起了一座简洁而有效的桥梁。