[Paper] 图神经网络能够学习哪些算法？

发布: 3天前 (2026年2月14日 GMT+8 01:09)

9 分钟阅读

原文: arXiv

Source: arXiv - 2602.13106v1

概述

一项新的理论研究精确探讨了 消息传递图神经网络（MPNN）能够学习哪些经典图算法。通过将形式化的学习保证与最短路径、最小生成树和背包等算法任务相结合，作者阐明了在何种情况下，在小规模图上训练的 MPNN 能够可靠地推广到更大规模的实例——这是将算法推理嵌入真实世界 AI 流程的关键一步。

通用学习框架：提供了足够条件，使得 MPNN 能够从有限的、小图训练集学习目标算法，并在任意大的输入上进行近似。
广泛的算法覆盖：展示该框架适用于单源最短路径（SSSP）、最小生成树（MST）以及一大类动态规划问题（例如 0‑1 背包）。
不可能性结果：证明标准 MPNN 无法学习若干自然的算法任务，指出导致失败的表达能力差距。
增强架构：引入对 MPNN 信息传递方案的适度扩展，以克服已识别的不可能性障碍。
对 Bellman‑Ford 的细化分析：推导出学习 Bellman‑Ford 单源最短路径算法所需的训练集规模大幅降低，并加入可微分的正则化损失，扩展了先前的工作。
实证验证：在合成和真实图数据集上的实验验证了理论预测，展示了成功的泛化以及标准 MPNN 的局限性。

Problem formalisation
- 将算法视为一个 function，将图（以及可能的辅助数据）映射到输出（例如距离标签）。
- 定义一个 training distribution，其由从有界族中抽取的小图组成。
Learning model
- 使用具有固定消息传递轮数的 MPNN。
- 网络使用标准监督损失（例如均方误差）在每个训练图的算法输出上进行训练。
Theoretical analysis
- 利用 uniform convergence 和 sample‑complexity 工具来界定 MPNN 在任意更大图上近似目标算法所需的训练样本数量。
- 识别 algorithmic properties（例如信息传播的局部性、单调性），以保证所需的样本复杂度为多项式级。
- 通过构造任务证明 negative results，即在这些任务中，所需信息无法被标准 MPNN 有限感受野捕获。
Architectural extensions
- 添加 global read‑out 向量、higher‑order messages 或 learnable attention，在保持模型置换等变性的同时提升表达能力。
Experiments
- 在小型合成图（≤ 20 个节点）上训练基线 MPNN 与所提扩展。
- 在更大规模的图（多达数千节点）上测试 SSSP、MST 和背包问题，测量准确率和运行时开销。

Algorithm	Standard MPNN (baseline)	Extended MPNN	Training‑set size needed*
Bellman‑Ford (SSSP)	在约 30 个节点后无法泛化	在最多 5 k 节点上完美学习	O(log
Kruskal‑style MST	在超过 15 个节点的环上出现系统性错误	在 2 k 节点的图上得到正确的 MST 边	Polynomial in max degree
0‑1 Knapsack (DP)	无法表示最优选择	在大规模实例上实现 > 95 % 最优性	Requires only O(1)‑size training set due to DP locality

*论文中推导的理论界限；实验曲线与预测相符。

关键要点

大型 AI 系统中的算法模块 – 开发者现在可以将学习到的单源最短路径（SSSP）或背包求解器嵌入端到端流水线的可微分组件中（例如，物流中的路径规划，云编排中的资源分配）。
速度‑内存权衡 – 学习到的 Bellman‑Ford 变体在 GPU 上运行，延迟与标准 GNN 前向传播相同，为大规模批处理图提供了相较于传统 CPU 实现的潜在加速。
对图规模的鲁棒性 – 由于理论保证了泛化，工程师可以在廉价的合成数据上训练，并在规模更大的生产图上部署，从而降低数据收集成本。
模型设计指引 – 不可能性结果引导实践者避免在需要全局排序的任务中使用纯粹的 MPNN，转而采用提出的扩展（全局 token、注意力）。
可微分正则化 – 改进的 Bellman‑Ford 分析加入了平滑正则项，使得将学习到的求解器集成到基于梯度的优化循环中更为容易（例如，路径规划与需求预测的联合学习）。