GNNs + Combinatorial Optimization & Algorithms

Xu 等人在他们 ICLR’21 论文中研究了神经网络的外推并得出了几个惊人的结果。使用算法对齐的概念，作者表明 GNN 与动态规划 (DP) 良好对齐（查看插图 ）。与 ICLR’20 论文相比，作者在这里讨论了更强的外推条件 - 与 DP 的线性对齐。事实上比较经典 Bellman-Ford 算法的迭代以寻找最短路径和通过 GNN 的消息的聚合组合步骤 - 你会发现很多共同点。作者还表明，在建模特定 DP 算法时，为 GNN 选择合适的聚合函数至关重要，例如对于 Bellman-Ford，需要一个最小聚合器。

为了对该领域进行更全面的介绍，我想重点介绍 Cappart 等人在 IJCAI'21 上进行的一项全面调查，该调查涵盖了优化组合中的 GNN。这篇文章首次出现了神经算法推理蓝图，后来在 Veličković 和 Blundell 的 Patterns 中的论文中进行了描述。

该蓝图解释了神经网络如何模仿和授权嵌入空间中通常离散算法的执行过程。在编码-处理-解码方式中，抽象输入（从自然输入获得）由神经网络（处理器）处理，其输出被解码为抽象输出，然后可以映射到更自然的任务特定输出。例如如果抽象输入和输出可以表示为图形，那么 GNN 可以是处理器网络。离散算法的一个常见预处理步骤是将我们对问题的了解压缩为“距离”或“边容量”等标量，并在这些标量上运行算法。相反向量表示和神经执行可以轻松启用高维输入而不是简单的标量，并附加反向传播以优化处理器。有关更多信息，请参阅 Petar Veličković 的演讲。

这个蓝图正在被越来越多的人使用——例如NeurIPS’21 有一些很酷的作品！Xhonneux 等人研究了迁移学习是否可用于将学习到的神经执行器泛化到新任务；Deac 等人发现了强化学习中算法推理和隐式规划之间的联系。2022 年还会有更多！

Scalability and Deep GNNs: 100 Layers and More

如果你在使用 2-4 层 GNN 时嫉妒深度 ResNets 或 100 层以上的巨大 Transformer，那么是时候欢呼了！2021 年为我们带来了 2 篇随意训练 100-1000 层 GNN 的论文，以及一篇关于几乎恒定大小的邻域采样的工作。

Li 等人提出了两种机制，在训练极深的过参数化网络时，可以将GPU内存消耗从L层的O(L)大幅降低到O(1)。作者展示了如何使用在 CV 或高效的 Transformer 架构（如 Reformer）中使用了多年的可逆层；在层之间共享权重。然后可以训练多达 1000 层的 GNN 。下面的图表展示了对 GPU 要求适中的层数的不断扩展。

Godwin 等人介绍了一种利用递归学习深度 GNN 的方法——消息传递步骤被组织成块，每个块可以有 M 个消息传递层。然后循环应用 N 个块，这意味着块之间共享权重。如果有 10 个消息传递层和 10 个块将得到一个 100 层的 GNN。这里面其中一个重要的组成部分是噪声节点正则化技术，它扰动节点和边的特征并计算额外的去噪损失。

该架构适合更好的分子任务，并在 QM9 和 OpenCatalyst20 数据集上进行了评估。

如果我们想要将任意GNN缩放到非常大的图，我们没有其他选择只能对子图进行采样。如果采样k-hop子图会导致指数级的内存开销和计算图的大小。

PyG的作者Matthias Fey等人创建了GNNAutoScale，它利用历史嵌入(缓存以前消息传递步骤)和图聚类(著名的METIS算法)在恒定时间内缩放gnn的框架。在预处理时将图划分为B个簇(小批量)，使簇之间的连通性最小化。然后通过这些簇运行消息，在缓存中跟踪更新的节点特性。经过实验证明深度网络(最多64层)的GNNAutoScale性能与完整批量一样好，但内存需求显著降低(大约是普通GPU的50倍)，因此可以将深度gnn和大型图放置消费级GPU上。

知识图谱

基于kg的表征学习终于突破了转换的极限。在2021年之前，模型被明确地分为直推式型和归纳型并且具有不同的归纳偏差、架构和训练方式。直推式模型没有机会适应看不见的实体，而归纳模型对于训练中大型图来说太昂贵了。

2021年出现了很多方法对这两种架构的改进：

在直推和归纳环境中工作

不需要节点特征

可以在归纳模式中以与直推模式相同的方式进行训练

可扩展到现实世界的 KG 大小

Zhu 等人的 Neural Bellman-Ford 找到了一种非常优雅的方法将经典的 Bellman-Ford 推广到更高级别的框架，并展示了如何通过使用特定运算符实例化框架来获得其他知名方法，如 Katz 指数、PPR 或最宽路径。更重要的是，他们的论文表明广义 Bellman-Ford 本质上是一个关系 GNN 架构（GNN 和动态规划之间算法对齐的另一个确认）。

NBFNet 不学习实体嵌入（仅关系和 GNN 权重），这使模型可以通过设计和泛化到看不见的图并具有归纳性。该模型在关系图和非关系图上的链接预测任务上都表现出色。

在 KG的应用中，NBFNet 从 2019 年开始为 FB15k-237 和 WN18RR 带来最大的性能提升，同时参数减少了 100 倍。

Galkin 等人（本文的作者是论文的作者之一）的另一种方法的灵感来自 NLP 中的标记化算法，该算法包含了固定的能够标记任何单词的词汇表，那些在训练时看不见的单词也包括在里面。将这种方法应用于 KG，NodePiece 将每个节点表示为一组前 k 个最近的锚节点（在预处理步骤中采样）和节点周围的 m 个唯一关系类型。锚点和关系类型被编码为可用于任何下游任务（分类、链接预测、关系预测等）和任何归纳/直推设置的节点表示。

NodePiece的特征可以被像RotatE这样的非参数****直接使用也可以发送到gnn进行消息传递。该模型在归纳链接预测数据集上具有与NBFNet相当的性能，在大型图上具有较高的参数效率——OGB WikiKG 2上的NodePiece模型需要的参数比浅层的直推模型少约100倍。

一些其他的GNN的研究

本节提到了几个特别有意思的作品，它们使用了 GNN但不属于某个特定类别。

Huang、He 等人在 ICLR’21 上展示了 Correct & Smooth - 一个通过标签传播改进模型预测的简单程序。该方法在没有使用任何gnn和更少的参数的情况下，仅与一个MLP配对并以最高分数横扫OGB排行榜!目前几乎所有OGB的节点分类上的顶级模型都使用了Correct & Smooth来获得更多一点的分数。

11月，Knyazev等人在通过一次前向传递预测各种神经网络架构参数的工作震动了ML社区。与其随机初始化模型还不如直接使用预测好的参数，而且这样的模型已经大大优于随机模型

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。