机器之心报道
机器之心编辑部
图神经网络 (GNN) 与动态规划 (DP)之间的关系应该如何描述？DeepMind 的研究者推导出了一个通用的积分变换图，证明 GNN 和 DP 之间存在着错综复杂的联系，远远超出对个别算法如 Bellman-Ford 的最初观察。
近年来，基于图神经网络 (GNN) 的神经算法推理的进步得益于算法式对齐（algorithmic alignment）概念的提出。从广义上讲，如果神经网络的各个组件与目标算法很好地对齐，那么神经网络将更好地学习执行推理任务（就样本复杂度而言）。具体来说，GNN 被认为与动态规划 (DP) 一致，而后者是一种表达多项式时间算法的通用问题解决策略。然而，这种对齐方式是否真正得到了证明和理论上的量化？
来自 DeepMind 的研究者使用范畴论和抽象代数的方法表明，GNN 和 DP 之间存在着错综复杂的联系，远远超出了 Bellman-Ford 等单个算法的最初观察结果。得知这种联系后，很容易验证文献中一些之前的发现，DeepMind 希望它能成为构建更强大算法式对齐 GNN 的基础。
论文地址：https://arxiv.org/pdf/2203.15544.pdf
总结而言，该研究描述了使用范畴论和抽象代数来显式地扩展 GNN-DP 连接，这在以前主要是在特定的例子上才能使用。该研究推导出了一个通用的积分变换图（基于标准的范畴概念，如拉回、推前和交换半群），并讨论了为什么它足够通用，可以同时支持 GNN 和 DP 计算。有了这个图，我们就可以立即将之前的大量工作统一起来，简单地在积分变换中操作一个箭头。
图神经网络是动态规划器
GNN 与 DP 连接的难点
在神经网络和 DP 之间建立严格的对应关系是比较困难的，因为它们的计算差异巨大。神经网络是基于实数线性代数构建而成，而 DP 通常是寻径（path-finding）问题的一种泛化，它通常发生在 (N∪{∞}，min， +) 这样的对象上，在数学中，这些对象通常被归为欧几里德空间的退化。GNN 与 DP 不能直接用简单的方程式进行连接。
然而，如果我们定义一个任意的潜在空间 R 并做出尽可能少的假设，我们可以观察到，对于 GNN 和 DP，我们关心的许多行为都是通过查看函数 S R 产生的，其中 S 是一个有限集。在 GNN 下，R 可以看作是一组实值向量；在 DP 下，R 可以看作是热带数（tropical numbers）。所以 DeepMind 的主要研究对象是有限集类别以及 R 值的量化。这里的类别是指对象集合（所有有限集）以及可组合箭头（有限集之间的函数）的概念。
为了绘制 GNN-DP 连接，首先需要设计一个抽象对象，该对象可以捕获 GNN 的消息传递 / 聚合阶段（等式 1）和 DP 的评分 / 重组阶段（等式 2）。
DeepMind 将通过组合输入特征的变换来构建积分变换，这种方式将最小程度地依赖于 R 的特定选择。在此过程中，DeepMind 构建了一个计算图，该图将适用于 GNN 和 DP(以及它们自己选择的 R)，这种方式使得该研究将重点放在这些图的组件尽可能对齐上。
积分变换、拉回和前推
积分变换的一般情况是称为 span 的图，如下所示：
这里 V、E、W 是任意有限集，s、t 是任意函数。请注意，当 W = V 时，这正是 (V, E) 有向多重图结构所需的数据，其中 s(e)解释为边的源，而 t(e)则是一条边的目标。
这里需要描述两个操作，一个是沿着 s 的拉回（ pullback ） s^* 和一个沿着 t 的前推（pushforward） t_ 。对定义在 V 上的数据执行拉回的结果就是定义在 E 上的数据。然后前推应该获取 E 上定义的数据并给出 W 上定义的数据，尽管我们会看到它实际上给出了一个需要聚合的数据包。方便的是，这个过程自然会与 GNN 的聚合步骤以及 DP 的重组步骤保持一致。
数据包含函数 f : V R，这使得定义拉回变得简单：s ^ f := f s （将边映射到它的发送节点，然后在 f 中查找特征 ）。
然而，前推是有问题的，因为 t 在使用函数组合时面临错误的方向。为了得到一个指向正确的箭头，需要原像（ preimage ） t^-1 : W P(E)，它取 E 的幂集的值。原像定义为 t^-1 (w) = 。
完成转换所缺少的只是一个聚合器，。正如我们将在下一节中看到的，指定一个表现良好的聚合器与在 R 上施加一个可交换的幺半群结构相同。
积分变换的四个箭头
如前所述，有向图 G = (V, E)等价于 span：其中 s 和 t 分别为每条边的发送节点和接收节点。
从一些输入特征 f : V R 开始，现在可以使用前面描述的所有对象来描述 f 的积分变换。最初，该研究关注重点是沿边 e ∈ E 发送的消息仅取决于发送者而不是接收者节点的情况。
该研究首先定义一个核变换 k：[E, R] [E, R]，其在边缘特征上执行一些计算，例如在 Bellman-Ford 的情况下，将发送者距离 d_s(e)（之前通过 s^ 拉回边缘）添加到边缘权重 w_s(e)t(e)。这里 DeepMind 使用 [E, R] 作为函数集 E R 的简写符号。使用核，我们可以完成下图：
这四个箭头构成了整体变换：从节点特征开始，在边缘上执行计算，最后在接收器中聚合边缘消息。在此过程中，DeepMind 更新了初始节点特征（它们是 [V, R] 的元素）。
s^ 是先前定义的拉回箭头，如前所述，DeepMind 使用源函数预先组合节点特征。也就是说，(s^*f)(v) := f(s(v))。然后，将核应用于生成的边缘特征，将发送者的特征与任何提供的边缘特征（例如边缘权重）集成。
在应用核之后，将会得到边缘消息 m : E R 作为结果。现在需要将这些消息发送到接收节点，DeepMind 为此使用了前推。如前所述，他们定义，并将其解释为中的形式和。直观地说，(t_ m)(v) 是 v 处的传入值包。
最后，DeepMind 对每个接收器逐点应用先前定义的聚合器来计算每个节点的更新特征。
上述设计的积分变换既能描述 GNN(公式 1)又能描述 DP(公式 2)，这使得 GNN 架构在算法上与目标 DP 算法对齐。也许最清楚的是最后一个箭头，聚合器 ()。如果我们让 GNN 选择的聚合函数与目标算法使用的函数匹配，这应该会立即提高样本复杂性和泛化能力。事实上，这与算法推理中最早的研究路线之一非常吻合：将 GNN 与问题一致的聚合器部署。在组织现有研究和提出未来工作时，任何以这种方式分析 GNN 和 DP 的投入都可以提供丰厚的回报。
更多内容请参考论文原文。
营业执照公示信息