Directed Graph Grammars for Sequence-based Learning¶
会议: ICML 2025
arXiv: 2505.22949
代码: https://github.com/shiningsunnyday/induction
领域: 图生成 / 图表示学习 / 结构搜索
关键词: 有向无环图, 图文法, 序列化表示, 最小描述长度, 贝叶斯优化
一句话总结¶
提出 DIGGED，通过无歧义上下文无关图文法将 DAG 无损映射为唯一的产生式规则序列，结合 Transformer 解码器实现图生成/属性预测/贝叶斯优化，在神经架构搜索、贝叶斯网络和电路设计三个任务上全面超越现有方法。
研究背景与动机¶
领域现状：有向无环图（DAG）是许多实际问题的核心数据结构，包括神经架构搜索（NAS）、贝叶斯网络结构学习和模拟电路设计。目前主流的图生成方法分为两类：一类是自回归生成（AG），按某种顺序逐步添加节点和边；另一类是序列解码（SD），将图的邻接信息编码为某种节点排列的序列。
现有痛点：AG 方法缺乏严格性——同一个图可能对应指数级多的生成顺序，导致解码不确定性高；SD 方法依赖任意的节点排序（如拓扑序、BFS 序），任意序列无法保证解码出合法图。两类方法均无法同时保证一对一映射、确定性、合法性和无状态性。
核心矛盾：图是排列不变（permutation-invariant）的结构，强行赋予节点顺序会引入冗余和歧义。缺乏一个从图空间到序列空间的严格双射，使得序列模型（如 Transformer）的强大建模能力无法被图生成直接利用。
本文目标 设计一个同时满足五个理想性质——一对一（unambiguous）、满射（onto）、确定性（deterministic）、合法性（valid）、无状态（stateless）——的 DAG 到序列映射。
切入角度：作者观察到上下文无关图文法（edNCE grammar）天然支持确定性推导和合法性保证。如果能让文法对数据集无歧义，则每个 DAG 对应唯一一条推导序列，完美地将图问题化归为序列问题。
核心 idea：用最小描述长度（MDL）原则从数据中归纳无歧义 edNCE 图文法，将 DAG 无损压缩为唯一的产生式规则序列，从而将图建模问题完全转化为序列建模问题。
方法详解¶
整体框架¶
DIGGED 分两阶段：文法归纳和序列建模。
- 文法归纳阶段：输入一组 DAG 数据集 \(\mathcal{D} = \{H_1, H_2, \ldots\}\)，通过迭代压缩算法自动发现频繁子图模式（motif），建立产生式规则集合 \(P\)，并消除歧义，最终每个 DAG 被解析为一条唯一的规则序列。
- 序列建模阶段：将规则序列作为 token，搭建 VAE 框架——编码器可选 GNN（DAGNN）或 Transformer，解码器使用因果注意力的 Transformer 自回归解码规则序列。训练完成后支持无条件生成、属性预测和贝叶斯优化三大下游任务。
关键设计¶
-
频繁子图挖掘（Frequent Subgraph Mining）
- 功能：在当前复合图 \(H\)（所有 DAG 的并）中发现重复出现的子图模式。
- 核心思路：采用近似 FSM 库 Subdue 快速发现候选 motif，然后通过并行子图同构算法定位所有 motif 出现位置 \(D_1, D_2, \ldots, D_K\)。关键创新——对含非终结符节点的连通分量，只考虑包含该非终结符的子图，从而将解析树简化为根到叶的路径（rooted path），保证线性解析结构。
- 设计动机：线性解析树是实现"一对一映射"的基础。传统图文法允许分支解析树，同一图可能有多种推导，而路径解析树消除了这种结构性歧义。
-
兼容性最大化求解器（Compatibility Maximization Solver）
- 功能：对每个候选 motif，找到最大子集的出现，使它们能共享同一套连接指令（connection instructions）。
- 核心思路：edNCE 规则需要定义如何将 motif 连接到其邻域。不同出现位置的邻域连接模式可能冲突。作者将此建模为最大团问题（max clique problem）——每个节点代表一个 motif 出现及其边重定向方案，兼容的方案之间连边，最大团即为最大兼容集合。每个节点维护一个 inset（必须包含的指令）和 outset（必须排除的指令），通过 \(v_\text{inset} \cap v_\text{outset} = \emptyset\) 判断节点有效性，\(( u_\text{inset} \cup v_\text{inset}) \cap (u_\text{outset} \cup v_\text{outset}) = \emptyset\) 判断边兼容性。
- 设计动机：朴素方法会因连接模式不一致导致文法冲突。将兼容性判断转化为图上的组合优化问题，保证了诱导规则在所有使用位置上的一致性。
-
最小描述长度选择（MDL Selection）
- 功能：在所有候选 motif 及其最大兼容解中，选择压缩数据描述长度最多的那个。
- 核心思路：贪心目标 \(\max |C|(|D| - 1)\)，其中 \(|C|\) 是最大团大小（兼容出现数），\(|D|\) 是 motif 节点数。选中后，执行 motif 收缩——将每个出现替换为一个非终结符节点。迭代此过程直到没有 motif 的兼容出现数 \(\geq 2\)。
- 设计动机：MDL 原则（奥卡姆剃刀）是无监督图压缩的经典指导原则。压缩率越高，说明发现的模式越具代表性，归纳出的文法越紧凑。
-
消歧义程序（Disambiguation Procedure）
- 功能：修改文法 \(G \to G'\)，消除数据集中的歧义解析。
- 核心思路：虽然判断一般图文法的歧义性是不可判定的，但对给定数据可以穷举所有推导。作者设计了 DAG 版本的 CYK 动态规划解析算法，利用 DAG 的规范字符串表示实现哈希记忆化，并通过剪枝不连通/有环的中间图加速。找到所有推导后，通过最大打击集（maximum hitting set）问题确定需移除的最小规则集，使尽可能多的数据保留唯一解析。
- 设计动机：无歧义是"一对一映射"的核心保证。即使 NP-hard，通过 DAG 特有的结构性质（规范化、无环约束）可以有效求解。
损失函数 / 训练策略¶
VAE 标准训练：最大化证据下界（ELBO），包含重构损失（cross-entropy on rule sequence）和 KL 散度正则项。由于一对一映射保证，重构等价于规则序列的精确匹配。
推理时利用上下文无关文法的性质进行约束解码：首步仅允许以起始符 \(S\) 为左侧的规则，后续每步仅允许当前非终结符对应的规则，无非终结符时终止。还可添加领域约束（如电路中运算放大器的稳定性约束）来保证生成合法性。
实验关键数据¶
主实验：无条件生成¶
| 数据集 | 方法 | 准确度(%) | 有效率(%) | 唯一率(%) | 新颖率(%) |
|---|---|---|---|---|---|
| ENAS | D-VAE | 99.96 | 100 | 37.26 | 100 |
| ENAS | DAGNN | — | — | — | — |
| ENAS | DIGGED (GNN) | 100 | 100 | 98.7 | 99.9 |
| BN | D-VAE | 99.94 | 98.84 | 38.98 | 98.01 |
| BN | GraphRNN | 96.71 | 100 | 27.30 | 98.57 |
| BN | DIGGED (GNN) | 100 | 100 | 97.6 | 100 |
DIGGED 在唯一率上比次优方法高 50%+，同时保持 100% 有效率和接近 100% 新颖率。
电路设计：贝叶斯优化 FoM¶
| 方法 | DAG有效率(%) | 电路有效率(%) | 新颖率(%) | BO最优 FoM ↑ |
|---|---|---|---|---|
| PACE | 83.12 | 75.52 | 97.14 | 33.27 |
| CktGNN | 98.92 | 98.92 | 92.29 | 33.44 |
| CktGNN (CktBench301) | — | — | — | 190.24 |
| CktBench101 (max) | 100 | 100 | 0 | 326.67 |
| DIGGED (GNN) | 100 | 100 | 78.80 | 310.26 |
DIGGED 在 FoM 优化上超越 CktGNN 9 倍以上（310.26 vs 33.44），甚至逼近训练集最优设计（326.67），且生成的电路 100% 合法。
消融实验：序列描述方式对比¶
| 编码方式 | 有效率(%) | 唯一率(%) | 新颖率(%) | BO Top1 FoM |
|---|---|---|---|---|
| Graph2NS-Default | 80.2 (CKT) | 71.0 | 96.8 | 220.96 |
| Graph2NS-BFS | 0.1 (CKT) | 100 | 100 | — |
| Graph2NS-Random | 0 (CKT) | — | — | — |
| DIGGED | 100 | 100 | 78.8 | 306.32 |
对比说明：BFS 和随机排序几乎完全无法在电路任务上生成合法样本，而 DIGGED 的文法序列化消除了位置依赖问题，100% 有效 + 最优 FoM。
关键发现¶
- 唯一率是 DIGGED 最大优势：在 ENAS 上唯一率 98.7% vs D-VAE 的 37.26%，说明文法序列化几乎消除了生成冗余。
- GNN 编码器优于 Token 编码器：GNN 编码器构建的潜空间更适合属性预测和生成（Token 编码器在 ENAS 上 Pearson r 仅 0.049），但 Token 编码器仍有效验证了序列化思路的可行性。
- 压缩率反映结构复杂度：线性结构（ENAS）压缩率最高，密集图（BN）压缩率最低，但 BN 用最少规则（845 条）实现了大比例压缩。
- 描述长度与预测误差负相关：较长的规则序列包含更多结构信息，测试误差更低（Fig. 5），暗示 MDL 压缩是一种显式信息瓶颈机制。
亮点与洞察¶
- 图问题彻底化归为序列问题：通过形式语言理论中的无歧义图文法，首次实现了 DAG 到序列的严格双射。这意味着 Transformer 在序列任务上的一切进展（预训练、生成策略）都可以直接用于图任务，打开了一个全新的建模范式。
- MDL 作为无监督归纳目标：不需要标签或外部监督，仅靠"压缩数据集"就能发现有意义的图结构原语（motif），这种思路可迁移到任何需要发现可复用组件的结构化数据任务。
- 约束解码的优雅性：上下文无关文法天然支持逐步合法性检查。在电路设计中，稳定性约束可以被翻译为对候选规则的谓词，无需额外的后处理或拒绝采样，这比后验过滤（post-hoc filtering）高效得多。
- 兼容性最大化→最大团是一个巧妙的建模转换，将连接指令的一致性问题形式化为经典组合优化问题，既有理论保证又有实用的近似算法。
局限与展望¶
- 文法规模与数据规模的关系：在 ENAS 上归纳出 7504 条规则，导致 token 字典过大，Token 编码器效果差（Pearson r 仅 0.049）。需要探索更激进的文法压缩或分层文法结构来控制规则数量。
- 仅支持 DAG：方法依赖 DAG 的拓扑排序和无环性质（如规范字符串表示、中间图剪枝），无法直接扩展到一般有向图或无向图。
- 子问题均为 NP-hard：子图同构、最大团、打击集的计算复杂度限制了可扩展性。虽然提供了近似算法，但在大规模数据集上效率仍然是瓶颈。
- 消歧义不可判定性：只能针对训练数据消歧义，无法保证对测试数据也无歧义，存在泛化风险。
- 压缩率与子图复杂度的 trade-off 未被充分分析——何时应该停止压缩、最优的 motif 粒度是什么，缺乏理论指导。
相关工作与启发¶
- vs D-VAE/DAGNN：D-VAE 和 DAGNN 使用 GNN 编码 DAG 的拓扑结构，但解码仍依赖自回归顺序添加节点/边，同一图有多种生成顺序（不满足一对一），且需要追踪中间图状态。DIGGED 用文法推导替代了自回归解码，无状态且唯一。
- vs CktGNN：CktGNN 使用手工定义的电路子结构基作为 motif，领域知识依赖强。DIGGED 从数据中自动归纳 motif，更通用，且在 BO FoM 上大幅超越。
- vs 分子图文法（Jin et al. 2018, Sun et al. 2024）：这些工作将图文法用于分子生成但解码能力有限。DIGGED 首次将图文法与 Transformer 解码器结合，利用上下文无关文法的无状态性实现高效约束采样。
- 本文的"图→序列双射"思路对多模态 VLM 中的结构化数据（如知识图谱、场景图）的 token 化可能有启发意义。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次从形式语言理论角度建立 DAG 到序列的严格双射，视角全新
- 实验充分度: ⭐⭐⭐⭐ 三个真实任务（NAS、BN、电路）+ 详尽消融 + 案例分析，但缺少大规模图数据集验证
- 写作质量: ⭐⭐⭐⭐ 理论严谨、图示清晰，但符号体系较重，入门门槛高
- 价值: ⭐⭐⭐⭐ 提供了图生成建模的新范式，但 DAG 限制和可扩展性问题限制了即时影响力
相关论文¶
- [NeurIPS 2025] GSPN-2: Efficient Parallel Sequence Modeling
- [NeurIPS 2025] Graph Distance as Surprise: Free Energy Minimization in Knowledge Graph Reasoning
- [CVPR 2025] Parallel Sequence Modeling via Generalized Spatial Propagation Network
- [ICML 2025] Graph Generative Pre-trained Transformer (G2PT)
- [ICLR 2026] Generating Directed Graphs with Dual Attention and Asymmetric Encoding