虽然我们才刚刚进入 2020 年，但已经可以在最新的研究论文中看到图机器学习（Graph Machine Learning，GML）的趋势了。本文是我对 2020 年图机器学习的重要内容以及对有关这些论文的讨论的看法。

引言

本文写作目的并非介绍图机器学习的基本概念，如图神经网络（Graph Neural Network，GNN），而是揭示我们可以在*学术会议上看到的前沿研究。

在阅读了大部分关于图机器学习的论文之后，我整理出了 2020 年图机器学习的趋势，如下所列：

**对图神经网络将有更为扎实的理论认识；
图神经网络将会出现新奇炫酷的应用；
知识图谱将会变得更加流行；
将出现用于图嵌入的新框架。
让我们来看看这些趋势。**

1. 对图神经网络将有更为扎实的理论认识

对于这一趋势，我感到特别兴奋，因为它意味着图机器学习领域已经成熟，以前的启发式方法正被新的理论解决方案所取代。关于图神经网络的研究还有很多工作要做，但关于图神经网络的工作原理，已经有了一些重要的研究结果。

我将从我最喜欢的论文开始：《图神经网络无法学习的内容：深度与宽度》（What graph neural networks cannot learn: depth vs width）（作者：Andreas Loukas）。这篇论文在技术简单性、高实用性和深远的理论见解之间取得了惊人的平衡。

论文地址： https://openreview.net/forum?id=B1l2bp4YwS

• 论文表明，如果我们希望图神经网络能够计算一个流行的图问题（如循环检测、直径估计、顶点覆盖等等），那么节点嵌入的维数（网络宽度 w）乘以层数（网络深度 d) 应与图 n 的大小成正比，即 dw=O(n)。

结果，当前许多图神经网络的实现都无法满足这一条件，因为层数（在许多实现中为 ~2-5）和嵌入维度（~100-1000）与图的大小相比，还不够大。另一方面，较大的网络在目前的环境下是过于禁止的，这就引出了一个问题，即，我们应该如何设计高效的图神经网络？这是我们未来需要解决的问题。相当有说服力的是，这篇论文还从 20 世纪 80 年代的分布式计算模型中获得了灵感，证明了图神经网络本质上也是如此。论文中还有更多的研究结果，我建议你去阅读这篇论文。

与此类似，Oono 与 Suzuki、Barcelo 等人的另外两篇论文也研究了图神经网络的威力。在第一篇论文《图神经网络在节点分类的表达能力呈指数级下降》（Graph Neual Networks Exponentially Lose Expressive Power for Node Classification）中，论文指出：

论文地址： https://openreview.net/forum?id=S1ldO2EFPr

• 在一定的权重条件下，当层数增加时，GCN 只能学习节点度和连通分量（由拉普拉斯谱（the spectra of the Laplacian）确定），除此之外什么也学不到。

这个结果推广了马尔科夫过程（Markov Processes）收敛到唯一平衡点的著名性质，其中收敛速度由转移矩阵的特征值决定。

在第二篇论文《图神经网络的逻辑表达》（The Logical Expressiveness of Graph Neural Network）中，作者展示了图神经网络和它们可以捕获的节点分类器类型之间的联系。我们已经知道，一些图神经网络和图同构的威斯费勒 - 莱曼（Weisfeiler-Leman，WL）算法一样强大，也就是说，当且仅当两个节点被图神经网络分类为相同时，威斯费勒 - 莱曼算法才会将它们着色为相同的颜色。但是，图神经网络可以捕获其他分类函数吗？例如，假设一个布尔函数，当且仅当一个图有一个孤立的顶点时，该函数才会将 ture 赋值给所有的节点。图神经网络能捕捉到这一逻辑吗？从直观上来看是不能，因为图神经网络是一种消息传递机制，如果图的一部分和另一部分（两个连接的组件）之间没有链接，那么这两者之间将不会传递消息。因此，一个建议的简单解决方案是在邻域聚合之后添加一个读出操作，这样当每个节点更新所有特性时，它就拥有了关于图中所有其他节点的信息。

论文地址： https://openreview.net/forum?id=r1lZ7AEKvB

• 理论方面的其他工作包括 Hou 等人的图神经网络测量图信息的使用，以及 Srinivasan 与 Ribeiro 提出的基于角色和基于距离的节点嵌入的等价性。

2. 图神经网络将会出现新奇炫酷的应用

我们还可以看到图神经网络将如何应用于实际任务，这也是一件很棒的事情。今年的应用程序包括修复 JavaScript 中的 Bug、玩游戏、回答类似 IQ 的测试、优化 TensorFlow 计算图、分子生成以及对话系统中的问题生成等。

在 Dinella 等人的论文《HOPPITY：学习图转换来检测和修复程序中的 Bug（HOPPITY: Learning Graph Transformations to Detect and Fix Bugs in Programs）中，提供了一种同时检测并修复 JavaScript 代码中 Bug 的方法。代码被转换为抽象语法树，然后由图神经网络进行预处理以获得代码嵌入。这一想法是给出一个处于初始状态的图，通过多轮图编辑操作符（如添加或删除节点、替换节点值或类型等）来对其进行修改。为了了解图中的哪些节点应该被修改，他们使用了一个指针网络，该网络采用图嵌入和迄今为止的编辑历史，并选择节点。然后，使用长短期记忆网络（Long Short-Term Memory，LSTM）进行修复，该网络还采用图嵌入和编辑的上下文。作者在 GitHub 的提交上验证了这个方法，显示了对其他不太通用的基线的显著提升。在精神上与 Wei 等人所做的理论工作相似：《LambdaNet：使用图神经网络的概率类型推断》（LambdaNet: Probabilistic Type Inference using Graph Neural Networks）论文研究了 如何推断 Python 或 TypeScript 等语言的变量类型。作者提出了一个类型依赖超图，其中包含了作为节点的程序变量以及它们之间的关系，如逻辑（例如布尔类型）或上下文（例如类似的变量名）约束。然后，首先训练图神经网络模型来产生图变量和可能类型的嵌入，然后将其用于预测最有可能的类型。在实验中，LambdaNet 在标准变量类型（如布尔类型）和用于定义类型方面表现更好。

在 Wang 等人的论文《基于多重图网络的抽象图解推理》（Abstract Diagrammatic Reasoning with Multiplex Graph Networks）演示了 如何使用图神经网络在类似 IQ 的测试（瑞文推理测验（Raven Progressive Matrices，RPM））和图解三段论（Diagram Syllogism，DS）。在瑞文推理测验任务中，为矩阵的每一行组成一个图，其中的边嵌入由一个前馈模型获得，然后进行图摘要（Graph summarization）。因为最后一行有 8 个可能的答案，因此创建了 8 个不同的图，每个图与前两行连接起来，通过 ResNet 模型得到 IQ 得分的预测。

《基于多重图网络的抽象图解推理》，Wang 等人

DeepMind 的一篇论文《用于优化计算图的增强遗传算法学习》（Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs）提出了 一种强化学习算法，可以优化 TensorFlow 计算图的成本。这些图是通过标准的消息传递图神经网络来处理的，图神经网络生成与图中每个节点的调度优先级相对应的离散化嵌入。这些嵌入被输入到一个遗传算法 BRKGA 中，该算法决定每个节点的设备放置和调度。通过对该模型进行训练，优化得到的 TensorFlow 图的实际计算成本。

《用于优化计算图的增强遗传算法学习》，作者：Paliwal 等人

图神经网络的其他有趣的应用还包括分子生成（作者：Shi 等人）、打游戏（作者：Jiang 等人）、对话系统（作者：Chen 等人）等。

3. 知识图谱将会变得更加流行

今年关于知识图谱中推理的论文不少。从本质上讲，知识图谱是一种表示事实的结构化方法。与一般的图不同，知识图谱中的节点和边实际上具有某种意义，例如，演员的名字或在电影中的表演（见下图）。知识图谱的一个常见问题是回答一些复杂的查询，例如“在 2000 年前，Steven Spielberg 的哪些电影获得了奥斯卡奖？”可以将其转换成逻辑查询 ∨ {Win(Oscar, V) ∧ Directed(Spielberg, V) ∧ ProducedBefore(2000, V) }。

知识图谱的一个例子（来源：Nickel 等人）

在 Ren 等人的论文《Query2box：基于框嵌入的向量空间中知识图谱的推理》（Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings）中，作者建议 将查询嵌入到潜在空间中作为矩形框形式，而不是作为单点形式。这种方法允许执行自然的相交操作，即合取 ∧，因为它会产生新的矩形框。但是，对联合（即析取 ∨）进行建模并不是那么简单，因为它可能会导致不重叠的区域。此外，为了精确建模任何带有嵌入的查询，用 VC 维（Vapnik-Chervonenkis Dimension）度量的嵌入之间的距离函数的复杂度应与图中实体的数量成正比。取而代之的一个很好的技巧是，将一个析取式查询替换为 DNF 形式，其中只有在计算图的末尾才会出现联合，这可以有效地减少对每个子查询的简单举例计算。

《Query2box：基于框嵌入的向量空间中知识图谱的推理》，作者：Ren 等人

在类似的主题中，Wang 等人在题为《知识图谱中数字规则的可微学习》（Differentiable Learning of Numerical Rules in Knowledge Graphs）中，提出了一种使用处理数值实体和规则的方法。例如，对于引用知识图谱，可以有一个规则 influences(Y,X) ← colleagueOf(Z,Y) ∧ supervisorOf(Z,X) ∧ hasCitation>(Y,Z)，它指出，学生 X 通常会受到他们的导师 Z 的同事 Y 的影响，后者被引用的次数更多。这个规则右边的每个关系都可以表示为一个矩阵，寻找缺失链接的过程可以通过实体向量的连续矩阵乘法，这一过程称为规则学习（Rule Learning）。由于矩阵的构造方式，神经方法只能在诸如 colleagueOf(z,y) 这样的分类规则下工作。该论文作者的贡献在于，他们提出了一种新颖的方法，通过显示实际上无需显式地物化这样的矩阵，显著地减少了运行时间，从而有效地利用 hasCitation(y,z) 和否定运算符等数值规则。

总体而言，在机器学习中以及今年在图机器学习中出现的另一个主题，是对现有模型的重新评估，以及它们在公平环境中的表现。像这样的论文，你可以查看 Ruffinelli 等人的论文《你可以教会老狗新把戏！关于知识图谱嵌入的训练》（You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings），论文表明，新模型的性能往往取决于试验训练的“次要”细节，如损失函数的形式、正则化函数和采样方案的形式。在一项大规模的消融研究中，作者观察到，RESCAL 模型等旧方法只要适当调整超参数，就可以实现 SOTA 性能。

在这个领域还有许多其他有趣的研究结果。Allen 等人基于对词嵌入的最新见解，进一步了解了更多关于关系和实体的学习表征的潜在空间。Asai 等人展示了模型如何在 Wikipedia 图谱上检索回答给定查询的推理路径。Tabacof 与 Costaello 论述了图嵌入模型的概率校准这一重要课题。他们指出，目前流行的嵌入模型 TransE 和 ComplEx，都是通过 logit 与 sigmoid 函数进行变换来获得概率的，但这些模型的标定能力很差，即对事实的存在预测不足或预测过度。他们的方法依赖于生成被破坏的三元组作为负数，这些负数被普拉特缩放（Platt scaling）和保序回归（Isotonic regression）等已知方法来校准概率。

4. 将出现用于图嵌入的新框架

图嵌入一直是图机器学习的一个长期主题，今年我们对该如何学习图表示有了新的观点。

针对任何无监督嵌入方法，Deng 等人提出了一种改进节点分类问题的运行时间和正确率的方法：《GraphZoom：一种用于正确且可扩展的图嵌入的多级谱方法》（GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding）。该论文的总体思路是：首先将原始图缩小为更小的图，这样可以快速计算节点嵌入，然后恢复原始图的嵌入。首先，根据属性相似度，对原始图进行扩充，增加对应于节点 K 最近邻之间链接的附加边。然后，对图进行粗化：每个节点通过局部谱方法投影到低维空间，并聚集成集合。任何无监督的图嵌入方法，如 DeepWalk 或 Deep Graph Infomax，都可以用来获得小图上的节点嵌入。在最后一步中，通过平滑算子迭代地广播所获得的节点嵌入（本质上代表集合的嵌入），以防止不同的节点具有相同的嵌入。在实验中，GraphZoom 框架在 node2vec 和 DeepWalk 方法的基础上实现了 40 倍加速，正确率提高了 10%。

关于图分类问题，已有多篇论文对前人的研究成果进行了详细的研究。Errica 等人的论文《图神经网络用于图分类的公平比较》（A Fair Comparison of Graph Neural Networks for Graph Classification），在这一问题上对图神经网络模型的公平重新评估上做出了贡献，表明了不利用图的拓扑结构的简单基线（即它在聚合节点特征上工作）的性能与 SOTA 图神经网络相当。这一令人惊讶的现象显然是 Orlova 等人在 2015 年发表的，但当时并没有吸引到大量的读者。这项工作带来的一个很好的结果是，在流行的数据集上公平的 SOTA 结果和方便的 PyTorch-Geometric 代码库，以便在将来的论文中运行模型的比较。在我们的研究论文《理解图数据集中的同构偏差》（Understanding Isomorphism Bias in Graph Data Sets）中，我们还发现，在常用数据集（如 MUTAG 或 IMDB）中，即使考虑节点属性，许多图也具有同构副本。而且，在这些同构图中，很多都具有不同的目标标签，这自然会给分类器引入了标签噪声。这表明了利用网络中所有可用的元信息（如节点或边属性）对于提高模型性能的重要性。另一项研究成果——Chen 等人的论文《强大的图神经网络是必要的吗？图分类的剖析》（Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification），论文指出，如果将非线性邻域聚合函数替换为线性邻域聚合函数，包括邻域的度数和传播的图属性，则模型的性能并不会降低——这与之前的陈述一致，即许多图数据集对于分类来说都是微不足道的，并提出了一个问题，即是否有合适的验证框架来完成这项任务。

结 语

随着顶会的论文提交率的增长，我们可以预计，2020 年图机器学习领域将会涌现许多有趣的结果。我们已经目睹这一领域的转变，从图的深度学习的启发式应用，到更合理的方法和关于图波形范围的基本问题。图神经网络找到了它的位置，作为一个有效的解决许多实际问题的方法，这些问题可以用图来表达，但我认为，总体而言，图机器学习只不过是触及了我们可以实现的图论和机器学习的交叉点上所能取得的成果的皮毛，我们应该继续关注即将到来的结果。

原文链接：https://www.infoq.cn/article/YaapLQEtEHQR0og9WBFv
原文链接：https://towardsdatascience.com/top-trends-of-graph-machine-learning-in-2020-1194175351a3