GNN 精确执行图算法首获可学习性证明,覆盖 BFS 与 Bellman–Ford

kfountou · x · 2026-09-03

作者发布自称最后一篇 GNN 论文《Learning to Execute Graph Algorithms Exactly with Graph Neural Networks》,延续 Petar Veličković 推动的神经算法推理方向。论文给出首个「梯度训练后精确可学习性」的正结果:在图度数有界、数值精度有限的假设下,LOCAL 模型中的图算法(如 flooding、BFS、DFS、Bellman–Ford)可被 GNN 精确学会执行。训练采用局部信息,是神经算法推理领域首个精确可学习性结论。