又一年即将结束，再过三天我们就要告别2021。各个AI领域也迎来了年度总结和未来展望。今天要说的是AI圈一直很火的图机器学习（GraphML）。2021年，图机器学习领域涌现了数万篇论文，召开了大量的学术会议和研讨会，取得了一些重大进展。2022年，图机器学习领域将走向何方？麦吉尔大学博士后研究员、专注于知识图谱和图神经网络（GNN）研究的学者Mila和MichaelGalkin在博客中阐述了自己的观点。在本文中，作者对图机器学习进行了结构化分析，并重点介绍了该领域的主要进展和热点趋势。作者希望本文能为图机器学习领域的研究者提供一个很好的参考。此图像由ruDALL-E生成。作者主要从以下12个部分进行详细梳理：GraphTransformers+positionfeatureequivariantGNNsmoleculargenerationmodelGNNs+combinatorialoptimization&algorithmsubgraphGNN:beyond1-WLscalableanddeepGNN:layers100andaboveKnowledgeGraphs用酷研究GNNs新的数据集、挑战和任务课程和书籍存储库和开源如何保持更新GraphTransformers+locationfeaturesGNNs在（通常是稀疏的）图上运行，而GraphTransformers(GT)在完全连接的图上运行，其中每个节点都连接到图中的每个其他节点。一方面，在具有N个节点的图中，图的复杂度为O(N^2)。另一方面，GT不会过度平滑，这是长途消息传递的常见问题。全连接图意味着你有来自原始图的真实边和从全连接转换中添加的假边，你需要区分它们。更重要的是，您需要一种方法将一些位置特征注入节点，否则GT将不会优于GNN。今年最流行的两个图形转换器模型是SAN和Graphormer。Kreuzer,Beaini等人提出的SAN。使用拉普拉斯算子的top-k个特征值和特征向量。SAN将光谱特征与输入节点特征连接起来，在许多分子任务上优于稀疏GNN。Ying等人提出的Graphormer。采用空间特征。首先，节点特征丰富了中心编码；然后，注意机制有两个偏差项：节点i和节点j之间的最短路径距离；边缘特征编码取决于可用的最短路径。Graphormer实现2021GraphML大满贯：OGB大型挑战赛和OpenCatalyst挑战赛获胜等变GNN等变性有何独特之处，以至于GeoffreyHinton对其赞不绝口？通常，等方差是在一些变换集上定义的，例如，3D旋转形成SO(3)集，特殊正交在3D中组合。等变模型在2021年席卷了ML，并且在图机器学习的许多分子任务中尤其具有开创性。当应用于分子时，等变GNN需要额外的节点特征输入，即分子物理坐标的某种表示，将在n维空间中旋转/反射/平移。在等变模型中，尽管转换顺序不同，我们都到达了相同的最终状态。图片来源：Satorras,Hoogeboom,andWellingSatorras,Hoogeboom,andWelling提出了EGNN，E(n)equivariantGNN，它与普通GNN的区别在于在消息传递和更新步骤中加入了物理坐标。等式3将相对平方距离添加到消息m，等式4更新位置特征。EGNN在建模n体系统、作为自动编码器和量子化学任务（QM9数据集）方面显示出令人印象深刻的结果。与普通GNN的主要区别：等式3和4结合了物理坐标添加到消息传递和更新步骤中。图片来源：Satorras、Hoogeboom和Welling另一种选择是合并原子之间的角度，就像Klicpera、Becker和Günnemann在GemNet中所做的那样。这可能需要将输入图转换为折线图，例如边图，其中来自原始图的边成为折线图中的节点。这样，我们就可以在新图中使用角度作为边缘特征。GemNet正在研究分子动力学，包括COLL、MD17和OpenCatalyst20显然，等变GNN才刚刚起步，我们将在2022年看到更多进展！分子生成模型得益于几何深度学习，整个药物发现领域将在2021年实现巨大飞跃。药物发现的众多关键挑战之一是生成具有所需特性的分子（图）。这个领域很大，这里只提到模型的三个分支。归一化流Satorras、Hoogeboom等。应用上述等变框架来创建E(n)等变归一化流，能够生成具有位置和特征的3D分子。石，罗，等。研究了给定2D图生成3D构象异构体（即3D结构）的问题。ConfGF模型估计原子坐标对数密度的梯度场。这些场是旋转平移等变的，作者想出了一种将这种等变性质纳入估计器的方法。Conformer采样本身是通过退火Langevin动力学采样完成的。RL方法以非常不科学的方式描述，这些方法通过递增地附加“构建块”来生成分子。这些方法可以根据它们如何调节构建过程进行大致分类。例如，Gao、Mercado、Coley以可合成为条件构建过程，即是否可以在实验室中实际创建这样的分子。为此，他们首先学习了如何创建构建块的合成树（一种模板）。YoshuaBengio领导的Mila和Stanford团队提出了一个更通用的框架，他们引入了GenerativeFlowNetworks(GFlowNets)。这很难用几句话来概括：首先，当我们想要对不同的候选者进行采样时，GFlowNets可以用于主动学习案例，并且采样概率与奖励函数成正比。此外，该团队最近的NeurIPS'21论文证明了GFlowNets对于分子生成任务的有用性。EmmanuelBengio的博文更详细地描述了该框架并提供了更多实验证据：http://folinoid.com/w/gflownet/GNNs+CombinatorialOptimization&Algorithms2021年对于这个新兴的子领域来说是重要的一年。在他们的ICLR'21论文中，Xu等人研究了神经网络中的外推并得出了一些令人印象深刻的结论。基于算法对齐的概念，作者表明GNN可以很好地与动态规划(DP)对齐（如下图所示）。其实对比经典的Bellman-Ford算法寻找最短路径的迭代和信息通过GNN的聚合组合步骤，你会发现很多共同点。此外，作者表明，在建模特定DP算法时，为GNN选择合适的聚合函数至关重要，例如对于Bellman-Ford，需要一个最小聚合器。作者StefanieJegelka在2021年深度学习和组合优化研讨会上详细介绍了这项工作的主要成果：https://www.youtube.com/watch?v=N67CAjI3Axw要对该领域进行更全面的介绍，请重点介绍Cappart的一项研究等人在IJCAI'21，一项涵盖GNN组合优化的调查。这篇论文最初是作为神经算法推理的蓝图出现的，后来在Veli?kovi?和Blundell的Patterns立场文件中进行了描述。该蓝图解释了神经网络如何在嵌入空间中模拟和增强一般离散算法的执行。在编码-处理-解码方法中，抽象输入（从自然输入中获得）由神经网络（处理器）处理，其输出被解码为抽象输出，然后可以映射到更自然的特定于任务的输出。例如，如果抽象输入和输出可以表示为图形，则GNN可以成为处理器网络。离散算法的一个常见预处理步骤是将我们对问题的了解转化为标量，如“距离”或“边际容量”，然后在这些标量上运行算法。相反，矢量表示和神经执行可以轻松启用高维输入而不是简单的标量，并通过额外的反向传播来优化处理器。目前，该蓝图已得到越来越多的采用，一些很酷的工作出现在NeurIPS'21上。Xhonneux等人研究了迁移学习是否可用于将学习到的神经执行器泛化到新任务；Deac等人发现了强化学习中算法推理和隐式规划之间的联系。相信在2022年会出现更多相关的研究。子图GNN：超越1-WL如果说2020年是第一次尝试1-WL-landia远离GNNs的表现力，那么2021年就是超越1WL的一年-landia。这些连接已被证明是有用的，我们现在拥有一些强大且更具表现力的GNN架构，可将消息传递扩展到更高阶结构，例如单纯复合体（例如Bodnar、Frasca、Wang等人的MPSN网络、细胞复合体（Bodnar的CW网络）,Frascaetal.))或子图。可扩展性和深度GNN如果你在使用2-4层GNN时羡慕深度ResNet或100层大Transformer，那么2021年有两篇论文给我们带来了好消息，一篇是关于随机训练100-1000层GNNs的论文，另一个关于几乎恒定大小的邻域采样。李等。提出了两种在训练极深超参数化网络时减少GPU内存消耗的新机制：将L层网络的O(L)减少到O(1)。作者展示了如何在CV或高效的Transformer架构（如Reformer）中使用可逆层并在层之间共享权重（权重绑定）来训练多达1000层的GNN。下图显示了基于GPU需求的层数缩放。资料来源：李等。论文《 Training Graph Neural Networks with 1000 Layers 》Godwin等人。提出了一种使用递归学习深度GNN的方法——在块中组织消息传递步骤，每个块可以有M个消息传递层。然后循环应用N个块，这意味着有多个块共享权重。如果你有10个消息层和10个块，你最终会得到一个100层的GNN。其中一个重要组成部分是噪声节点正则化技术，它扰乱节点和边缘的特征并计算额外的去噪损失。该架构更适合分子任务，研究团队还在QM9和OpenCatalyst20数据集上对其进行了评估。最后，如果你想将任何GNN扩展到非常大的图，你只有一个选择——采样子图。一般来说，对k-hop子图进行采样会导致内存成本和计算图大小呈指数增长，PyG的作者MatthiasFey等人创建了GNNAutoScale，这是一个用于在恒定时间内使用历史嵌入和图聚类缩放GNN的框架。该方法在预处理过程中将图划分为B个簇（小批量），以最小化簇之间的连接性；在这些集群上运行消息传递与全批设置一样好，并且显着降低了内存需求（约小50倍），这使得在商品级GPU上安装深度GNN和大型图形成为可能。Knowledgegraph(KG)2021年之前，根据归纳偏差、架构和训练机制，模型明确分为转导和归纳两大类。换句话说，转导模型没有机会适应看不见的实体，而归纳模型在中型到大型图上的训练成本太高。2021年，两种新架构可用于转导和感应环境。两种架构都不需要节点特征，可以像转导模式一样在归纳模式下进行训练，并扩展到真实世界的KG大小。一种是Zhu等人的神经Bellman-Ford网络，它将经典的Bellman-Ford泛化到更高级别的框架，并展示了其他经典方法（如Katz度量、PPR、最宽路径等）的效果。更重要的是，研究表明广义的Bellman-Ford本质上是一种关系型GNN架构。NBFNet不学习实体嵌入，这允许模型通过泛化到看不见的图来获得泛化。该模型在关系图和非关系图上的链接预测任务上表现良好。在KG的应用上，NBFNet在FB15k-237和WN18RR这两个数据集上带来了2019年以来最大的性能提升，同时将参数减少了100倍。另一个是Galkin等人提出的新方法。受到NLP中标记化算法的启发。当应用于KG时，NodePiece将每个节点表示为一组前k个最近的锚节点和节点周围的m个唯一关系类型。锚点和关系类型被编码为节点表示，可用于任何下游任务（分类、链接预测、关系预测等）和任何归纳/转导设置。NodePiece特征可以直接被RotatE等非参数解码器使用，或者发送给GNN进行消息传递。该模型在归纳链接预测数据集上的性能与NBFNet相当，并在大型图上表现出高参数效率——OGBWikiKG2上的NodePiece模型只需要浅层转导模型的一小部分参数1%。Huang、He等人在ICLR'21Correct&Smooth上展示了GNNs的酷研究——一个通过标签传播改进模型预测的简单程序。仅与MLP配对，此方法在不使用任何GNN且参数少得多的情况下以最高分登上了OGB排行榜！如今，几乎所有OGB节点分类赛道上的顶级模型都使用Correct&Smooth来压缩更多的点。图片来源：Huang、He等人Knyazev等人在前向传递中预测各种神经网络架构参数的工作震惊了ML社区。他们不是随机初始化模型，而是使用预测参数，这优于随机模型。参数预测实际上是一个图学习任务——任何神经网络架构（ResNet、ViT、Transformers）都可以表示为一个计算图，其中节点是具有可学习参数的模块，节点特征是那些参数，网络有一堆节点类型（例如，线性层、卷积层等，作者使用了大约15种节点类型）。参数预测是一个节点回归任务。使用GatedGNN对计算图进行编码，并将其新表示发送到解码器模块。为了进行训练，作者收集了一个包含1M架构（图表）的新数据集。这种方法适用于任何神经网络架构，甚至是其他GNN。预测未知模型参数的管道。图片来源：Knyazev等人。DeepMind和谷歌通过将道路网络建模为超分段图并在其上应用GNN，极大地提高了谷歌地图中ETA的质量。在Pinion等人的论文中，任务被定义为节点级和图级回归。除此之外，作者还描述了一些需要解决的工程挑战，以便在Google地图的规模上部署该系统。应用GNN解决数百万用户面临的现实问题。论文地址：https://arxiv.org/pdf/2108.11482.pdf来源：Pinionetal.部分资料总结在文章的最后，作者介绍了一些相关资料，包括数据集、课程和书籍，以及一些实用的图书馆。如果你不习惯Cora、Citeseer、Pubmed数据集，请考虑以下内容：OGB数据集包含3个非常大的图，可用于节点分类（240M节点）、链接预测（整个Wikidata，90M节点）和图回归（4M分子）任务。在KDD杯中，大多数获胜队伍使用10-20个模型组合；由MetaAI发起的OpenCatalystNeurIPS'21Challenge提供了大规模分子任务给定的初始结构，预测其松弛态能量。这个数据集庞大且计算密集，但组织者暗示将发布一个较小的版本，这将对GPU预算有限的小型实验室更加友好。事实上，Graphormer在OGBLSC和OpenCatalyst'21中都获得了第一名，并在2021年赢得了GraphMLGrandSlam；GLB2021带来了一组新的数据集，包括Lim等人。非同源图，Tsitsulin等人提出的图模拟，以及Rozemberczki等人提出的时空图；NeurIPS'21dataandbenchmarktrack带来了一个新的数据集，MalNet可用于图分类，数据集平均图Size为15k个节点和35k条边；ATOM3D可用于3D分子任务；RadGraph可用于从放射学报告中提取信息。MichaelBronstein、JoanBruna、TacoCohen和PetarVeli?kovi?撰写的关于几何深度学习的原型书和课程，包括12个讲座、实践教程和研讨会。书籍地址：https://arxiv.org/pdf/2104.13478.pdf课程地址：https://geometricdeeplearning.com/lectures/另外，更有价值的书籍和课程还有18位学者新写的知识图谱书：https：//kgbook.org/WilliamHamilton的GraphRepresentation学习手册：https://www.cs.mcgill.ca/~wlh/grl_book/2021年发布的库包括TensorFlowGNN、TorchDrug。TensorFlowGNN地址：https://github.com/tensorflow/gnnTorchDrug地址：https://torchdrug.ai/2021年持续更新的库包括：PyG2.0——现在支持异构图，GraphGym，以及一系列改进和新模型；DGL0.7—GPU上的图形采样，更快的内核，更多的模型；PyKEEN1.6—更多模型、数据集、指标和NodePiece支持；
