图神经网络 (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) = {e | t(e) = 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 的投入都可以提供丰厚的回报。
更多内容请参考论文原文。
