图注意力网络一作：图表征学习在算法推理领域的研究进展

这是一份来自 DeepMind 研究员、图注意力网络一作 Petar Veličković 的演讲，他为我们介绍了图表征学习在算法推理领域的研究进展。Veličković 指出，算法推理是图表征学习的一个令人激动的新领域，他希望自己的这次演讲能够吸引更多的人了解或关注这个领域，为该领域的研究贡献一份力量。

前段时间，图注意力网络（GAT）一作 Petar Veličković 在 Twitter 上晒出了自己的博士论文——《The resurgence of structure in deep neural networks》。在那篇论文中，他汇总了自己近年来在图神经网络领域的研究，包括 GAT、Deep Graph Infomax 等重要工作。

其实，在此之前，Petar Veličković 还在 WWW'20 上做过一个时长为 48 分钟的演讲。这个演讲的主题是，如何利用目前图表征学习的最新研究来支撑并增强算法推理类型的任务，同时讨论从长远来看这对神经网络框架会带来哪些益处。这个演讲和 Veličković 的博士论文互为补充，可以帮你了解更多关于图神经网络的内容。

演讲 PPT 链接：https://petar-v.com/talks/Algo-WWW.pdf

在 Veličković看来，解决问题的方向通常可分为两种：一种是针对特定问题硬编码，另一种是使用机器学习的方法，动态地学会适应特定原始输入到输出之间的映射关系。这两种方法似乎截然不同，而且各有优缺点。

Veličković 试图为我们解答：神经网络能否像常规算法一样稳健地推理？

本次演讲分为四个部分：图神经网络基准测试、强泛化能力、多任务学习和算法探索。

图神经网络基准测试

第一部分主要讨论的是，Cora 和 Cite 这类 GNN 基准测试数据集的不足，以及使用神经网络模拟算法推理的优势。

强泛化能力

在这一节中，Veličković 讲述了使用神经网络学习一个算法，并不是去学习输入 - 输出之间映射关系，而是去模仿算法特定的运算操作，这赋予了它很强的泛化能力。从下图的表 1 中可以看出，图表征学习在不同规模的任务下性能表现都很好。

多任务学习

大量算法的子流程存在许多相似的地方，使用图表征学习能够复用这些流程，实现多任务学习。下面的幻灯片内容展示了两个不同算法之间的比较，从伪代码中可以看到，这两个算法存在大量类似的流程。

算法探索

当我们能够做到多任务学习，那么实现算法探索也就变得不再那么遥不可及了。在本节中，Veličković 重点讨论了以下三篇论文在算法推理领域的最新研究进展，他将其分为了 Algo-level、Step-level 与 Unit-level。

第一篇文章探讨了最适合于推理任务的神经网络结构，更优的网络结构往往意味着更强的泛化性能。

实验结果显示，GNN 在众多任务中性能表现都非常好，尤其是在动态规划任务中。反观 MLP，其在动态规划中似乎没有学到任何东西。由此可见，使用 GNN 来模拟动态规划算法不失为一种良好的选择。

下一篇论文的一作是 Veličković 本人。论文中所提算法框架如下图所示，左边表示 Bellman-Ford 算法，右边为使用标准 GNN 执行的运算，该论文的工作是使用监督学习对 GNN 每一步的近似输出值进行修正，经过多次迭代后使其能够模拟特定算法的运算方式。论文中假设，由于算法具有许多复杂的运算操作，信息传递单元（message-passing unit）将会是一种更为通用且有效的结构。

研究者将不同方法在包含 20 个节点的最短路径算法（Bellman-Ford 算法）上进行训练，之后比较了当节点扩展到 50/100 个时它们的性能表现。不难看出，很多算法虽然在 20 个节点的最短路径算法训练中表现良好，然而扩展到更多节点时准确率急剧下降。

最后，Veličković 介绍了第三篇论文—神经执行引擎（Neural Execution Engine，NEE），该框架能够在 Unit-level 模拟众多简单运算操作（如求和、求积或取最小运算），之后将其组合为更加复杂的算法，能够实现「100%」的强大泛化性能（某些任务）。该框架在选择排序任务上的工作流程如下图所示。

下图展示了 NEE 与 Transformer 在选择排序任务上的性能比较，所有算法均在长度为 8 的序列上进行训练。可以看到，普通 Transformer 和改进后的 Transformer 在训练时均有较高准确率，当在长度为 100 的序列上测试时，两者的性能表现急剧下降，而 NEE 仍然具有 100% 的准确率，泛化能力十分强大。

由于演讲内容较长，很多内容本文无法全面覆盖，读者可自行点击视频观看：

参考链接：

https://www.reddit.com/r/MachineLearning/comments/gegxuf/graph_representation_learning_for_algorithmic/

https://www.youtube.com/watch?v=IPQ6CPoluok

理论图表示学习推理DeepMind表征学习