对于 Graph ML 来说2021年是重要的一年——成千上万的论文、无数的会议和研讨会......说明这个领域是在蓬勃的发展。我将Graph ML 这一年的进展进行结构化的展示，并重点介绍 🔥 趋势和主要进步。
无论您是在研究细分的主题还是刚开始使用 Graph ML - 我们都希望这篇文章是一个很好的参考点。这个领域太大了如果我错过了一些重要的东西，请在评论中告诉我们！
Graph Transformers + Positional Features
GNN 在通常是稀疏的图上运行，而 Graph Transformers (GT) 在全连接图上运行，其中每个节点都连接到图中的每个其他节点。一方面，这带来了节点 N 数量的 O (N²) 复杂度。另一方面，GT 不会遭受过度平滑，这是长距离消息传递的常见问题。全连接图意味着我们有来自原始图的“真”边和从全连接变换中获得的“假”边。我们还需要一种方法来为节点注入一些位置特征，否则 GT 会落后于 GNN（如 Dwivedi 和 Bresson 的 2020 年论文所示）。
今年最引人注目的两个Graph Transformers模型可能是 SAN（Spectral Attention Nets）和 Graphormer。
Kreuzer、Beaini 等人的 SAN 使用了拉普拉斯算子的 top-k 特征值和特征向量，表明单独的谱特征（spectral features）可以区分被 1-WL 检验确定是否同构的图。SAN 将光谱特征与输入节点特征连接起来，在许多分子任务上优于稀疏 GNN。
Ying 等人的 Graphormer 采用了不同的方法并使用了空间特征。节点特征丰富了中心性编码（centrality encoding）——可学习的入度和出度嵌入。注意力机制有两个偏置项：1、节点 i 和 j 之间最短路径的距离；2、取决于一条可用最短路径的边特征编码。
Graphormer完成了2021年Graph ML大满贯:OGB large Challenge和Open Catalyst Challenge图回归任务第一名!(以下将详细介绍这些挑战)
SAN 和 Graphormer 在分子级别的任务上进行了评估，图相当小（平均 50-100 个节点），这样计算量不会特别大，例如运行 O (N³) Floyd-Warshall 所有对最短路径。Graph Transformers 仍然受到 O (N²) 注意力机制的限制。缩放到大于分子的图形可能会解决这些问题。来自 NLP的思想可能会有所帮助，但由于他们从未实现注意力矩阵，因此需要找到一种聪明的方法将边缘特征置于此类模型中。在 2022 年应该会看到更多关于这方面的研究！
Equivariant GNNs
Geoffrey Hinton 提出的equivariance有何独特之处？
equivariance在 2021 年掀起了 ML 的风暴，在 Graph ML 中，它在许多molecular tasks中尤其具有破坏性。等变 GNN 需要一个额外的节点特征输入——即物理坐标的一些表示，这些表示将在 n 维空间中旋转/反射/平移。
Satorras、Hoogeboom 和 Welling 提出了 EGNN、E(n) 等变 GNN，其与普通 GNN 的重要区别在于将物理坐标添加到消息传递和更新步骤。方程 3 将相对平方距离添加到消息 m，方程 4 更新位置特征。EGNN 在建模 n 体系统、作为自动编码器和量子化学任务（QM9 数据集）方面显示出令人印象深刻的结果。
另一种选择是合并原子之间的角度，如 Klicpera、Becker 和 Günnemann 在 GemNet 中所做的那样。这可能需要将输入图转换为折线图，例如边图，其中来自原始图的边变成折线图中的节点。这样就可以将角度作为新图中的边特征。
GemNet 在分子动力学任务上取得了不错的成绩：COLL、MD17 和 Open Catalyst20。显然equivariance才刚刚起步🛫，我们将在 2022 年看到更多进步！
Generative Models for Molecules
由于几何深度学习，整个药物发现 (DD) 领域在 2021 年得到了显着的发展。DD 的众多关键挑战之一是生成具有所需属性的分子（图）。这个领域很大，所以我们只强调模型的三个分支。
Normalizing Flows.
Satorras、Hoogeboom 等人应用上述equivariance框架来创建 E(n) 等变归一化流，能够生成具有位置和特征的 3D 分子
概率模型
Shi、Luo 等人研究了在给定 2D 图形的情况下生成 3D 构象异构体（即 3D 结构）的问题。模型 ConfGF 估计原子坐标对数密度的梯度场。作者想出了一种方法将这种旋转平移等变属性合并到估计器中。
RL方法
用一种非常不科学的方式来描述，这些方法通过逐步添加“构建块”来生成分子。我们可以根据这种构建过程的条件对这些方法进行广泛的分类。例如Gao、Mercado和Coley将构建过程设定在合成能力上，也就是说否能够在实验室中创造这个分子。他们首先学习如何创建构建块的合成树(类似模板)。
由Yoshua Bengio领导的Mila和Stanford研究团队提出了一个更通用的框架，Yoshua Bengio介绍了GFlowNets。这很难用几句话来概括——当想要对不同的候选人进行抽样时，GFlowNets可以用于主动学习案例并且抽样概率与奖励函数成正比。他们最近在NeurIPS发表的21篇论文显示了GFlowNets应用于分子生成任务的好处。
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社区。与其随机初始化模型还不如直接使用预测好的参数，而且这样的模型已经大大优于随机模型👀。如果你用n个SGD步骤优化一个随机初始化的网络，你会得到更好的结果，但本文的主要贡献是通常可以找到合适的参数而不训练这个特定的架构。
参数预测实际上是一个图学习任务，任何神经网络架构(ResNet, ViT, transformer，还有你的模型)都可以表示为一个计算图，其中节点是具有可学习参数的模块，节点的特征就是那些参数。我们有一堆节点类型(例如，线性层，Conv层，BN，作者大概整理了~15个节点类型)。参数预测是一个节点回归任务，计算图用GatedGNN编码，它的新表示被发送到解码器模块。为了训练作者收集了一个新的包含了100万架构(图)的数据集，结果表明这种方法适用于任何神经网络架构，甚至适用于其他gnn !
DeepMind 和谷歌通过将道路网络建模为超分段图并在其上应用 GNN，极大地提高了谷歌地图中 ETA 的质量。在 Derrow-Pinion 等人的论文中，该任务被定义为节点级和图级回归。作者还描述了许多需要解决的工程挑战，以便在谷歌地图规模上部署系统。这个论文可以作为应用 GNN 解决数百万用户面临的实际问题的完美示例！
Transgene 和 NEC 最近宣布了 GNN 在癌症研究中的另一个潜在影响应用。根据 NEC 首席研究员 Mathias Niepert 的说法，GNN 被用于通过嵌入传播来估算丢失的患者数据。
最后，DeepMind 的 Davies 等人最近使用 GNN 来帮助制定与核心数学问题有关的猜想，实际上确实找到并证明了一个新定理！这表明，GNN 也可以处理非常抽象的问题
新数据集、挑战和任务
如果您厌倦了 Cora、Citeseer 和 Pubmed - 2021 年带来了大量不同大小和特征的新数据集。
OGB 在 KDD'21 上组织了大规模挑战，其中包含 3 个非常大的图用于节点分类（240M 节点）、链接预测（整个 Wikidata，90M 节点）和图回归（4M 分子）。在 KDD 中，大多数获胜团队使用 10-20 个模型的集成。新版本的 LSC 数据集现在可用于新的排行榜！
Meta AI 发起的 Open Catalyst NeurIPS’21 Challenge 提供了一项大型分子任务——在给定具有原子位置的初始结构的情况下预测松弛态能量。数据集很大需要大量的计算，但组织者暗示会发布一个更小的版本，这对 GPU 预算有限的小型实验室会更友好一些。Graphormer 在 OGB LSC 和 OpenCatalyst’21 中都获得了第 1 名，几乎在 2021 年收集了 Graph ML 的大满贯 🏅
Graph Learning Benchmarks Workshop @ The WebConf 2021 带来了一系列新数据集，包括 Lim 等人的非同质图、Tsitsulin 等人的图模拟、Rozemberczki 等人的时空图等等
NeurIPS 的 21 Datasets & Benchmarking Track 就像一个新数据集的 SXSW 节：今年我们有 MalNet - 图分类，其中平均图大小为 15k 节点和 35k 边，比分子大得多；ATOM3D - 一系列新的 3D 分子任务；RadGraph - 从放射学报告中提取信息。Liu 等人描述了了创建图学习数据集分类法的挑战。
新的开源库
2021 年发布的新库：
TensorFlow GNN - 作为 Tensorflow 世界中的一等公民的 GNN。
TorchDrug - 用于分子和 KG 任务的基于 PyTorch 的 GNN 库
已建立的 Graph ML 库已更新：
PyG 2.0 - 现在支持异构图、GraphGym 以及一系列改进和新模型
DGL 0.7 - GPU 上的图形采样、更快的内核、更多模型
PyKEEN 1.6 - 用于训练 KG 嵌入的首选库：更多模型、数据集、指标和 NodePiece 支持！
Jraph - JAX 爱好者的 GNN
以上就是2021年的总结，通过以上可以看到2022年将注定时Graph ML不平凡的一年
作者：Michael Galkin