选自towardsdatascience
作者：Sergei Ivanov
机器之心编译
参与：魔王、杜伟
2020 年已经过去了一个多月，但我们已经可以从最近的研究论文中一窥图机器学习（Graph Machine Learning，GML）的趋势。机器学习研究科学家 Sergei Ivanov 对 2020 年 GML 的发展趋势发表了自己的看法，并讨论了近期的相关研究论文。
本文的写作目的不是介绍 GML 的基础概念，如图神经网络（GNN），而是推介顶会前沿研究。作者简要总结了学术顶会 ICLR 2020 提交论文中图论文的统计概况：
共有 150 篇 GML 研究提交至此次 ICLR 会议，接收率为 1/3，约占全部接收论文的 10%。
作者阅读了其中的大部分论文，并列出了他对 2020 年 GML 研究趋势的判断：
- 对 GNN 有更坚实的理论理解；
- 出现新的 GNN 应用；
- 知识图谱更加流行；
- 新的图嵌入框架诞生。
本文作者、机器学习研究科学家 Sergei Ivanov。
现在我们来一一探究（以下以第一人称视角讲述）。
对 GNN 有更坚实的理论理解
我尤其对这一趋势感到振奋，因为它表明 GML 领域的成熟，先前的启发式方法正在被新的理论解决方案取代。要想理解图神经网络，还有很长的路要走，但关于 GNN 的工作原理已经出现多项重要研究成果。
首先来看我最喜欢的一项研究：Andreas Loukas 的论文《What graph neural networks cannot learn: depth vs width》。这篇论文在技术简洁性、强大的实践影响力和意义深远的理论见解三者之间实现了完美的平衡。
该研究证明，如果我们想让 GNN 为常见的图问题（如环检测、直径估计、顶点覆盖等）提供解决方案，则节点嵌入的维度（即网络宽度 w）与层数（即网络深度 d）的乘积应与图大小 n 成正比，即 dw = O(n)。
目前很多 GNN 实现无法达到该条件，因为层数（很多实现中的层数大约为 2–5）和嵌入维度（约 100–1000）与图大小相差甚远。另一方面，在当前设置下大型网络的代价高昂，这就引出了一个问题：如何设计高效 GNN？这是我们未来需要解决的任务。
另外，这篇论文从上世纪 80 年代的分布式计算模型中汲取灵感，充分证明 GNN 实际上可以做到同样的事。论文列出了更多结果，推荐大家阅读。
类似的还有以下两篇论文，这两篇文章的主题是 GNN 的力量。
第一篇论文《Graph Neural Networks Exponentially Lose Expressive Power for Node Classification》证明：
在特定权重条件下，当层数增加时，受拉普拉斯谱的影响，GCN 只能学习节点度（node degree）和连通分支（connected component）。
该结果是马尔可夫过程收敛至唯一均衡这一著名特性的泛化，其中收敛速率由转移矩阵的特征值决定。
论文链接：https://openreview.net/pdf?id=S1ldO2EFPr
第二篇论文《The Logical Expressiveness of Graph Neural Networks》展示了 GNN 和多种节点分类器之间的联系。我们已经知道一些 GNN 和同构的 WL test 一样强大，即当且仅当两个节点被 GNN 判断为同一类别时，WL 赋予二者相同的颜色。
那么 GNN 具备其他分类功能吗？例如，当且仅当图具备孤立顶点时，布尔函数向所有节点分配真值。GNN 具备这样的逻辑吗？直观来看不具备，因为 GNN 使用消息传递机制，当图的两个部分没有链接时（即两个连通分量，connected component），二者之间不会出现消息传递。
该研究提出了一种简单的修复方法：在邻域聚合之后添加 readout 函数，这样当每个节点更新所有特征时，它具备图中其他节点的信息。
论文链接：https://openreview.net/pdf?id=r1lZ7AEKvB
其他理论研究还包括：衡量 GNN 中图信息的使用（Hou 等人的论文《Measuring and Improving the Use of Graph Information in Graph Neural Networks》），以及基于角色和基于距离的节点嵌入的等价性（Srinivasan 和 Ribeiro 的论文《On the Equivalence between Positional Node Embeddings and Structural Graph Representations》）。
GNN 的新应用
看到 GNN 被应用于现实任务也很令人兴奋。2020 年 GNN 将应用于修复 Javascript 中的 bug、玩游戏、回答 IQ 类测试题、优化 TensorFlow 计算图、分子生成，以及对话系统中的问题生成。
Dinella 等人的研究《HOPPITY: Learning Graph Transformations to Detect and Fix Bugs in Programs》展示了一种检测出 Javascript 代码中的 bug 并同步修复的新方法：先将代码转换成抽象语法树，然后用 GNN 执行预处理得到代码嵌入。其思路是给出一张初始状态的图，通过多轮图编辑操作（添加或删除节点、替换节点值或节点类型）进行修改。
为了了解哪些图节点需要修改，研究者使用指针网络（Pointer network），该网络以图嵌入和当前编辑历史为输入，然后选择节点。接下来，使用 LSTM 网络执行修复工作，LSTM 网络也以图嵌入和编辑历史为输入。论文作者基于 GitHub commit 验证了该方法，证明其相比其他通用性较差的基线方法有显著提升。
论文链接：https://openreview.net/pdf?id=SJeqs6EFvB
类似的研究还有 Wei 等人的《LambdaNet: Probabilistic Type Inference using Graph Neural Networks》，它主要探讨如何为 Python 或 TypeScript 等语言推断变量类型。
作者展示了一种类型依赖超图（type dependency hypergraph），图节点是程序变量，该图还编码了变量之间的关系，如逻辑约束（布尔类型）或语境约束（如相似的变量名称）。先训练一个 GNN 模型为图中的变量和可能的变量类型生成嵌入，然后利用嵌入预测具备最高似然的类型。实验结果表明，LambdaNet 在标准变量类型（如布尔类型）和用户自定义类型中均获得了更好的性能。
论文链接：https://openreview.net/pdf?id=Hkx6hANtwH
Wang 等人的研究《Abstract Diagrammatic Reasoning with Multiplex Graph Networks》展示了如何使用 GNN 在 IQ 测试中进行推理。在瑞文推理测验（Raven Progressive Matrices，RPM）任务中，研究者为矩阵的每一行构建一个图（其中边嵌入通过前馈模型获得），然后执行图摘要。由于最后一行有 8 个可能答案，因此创建了 8 个不同的图，每个图和前两行连接，然后通过 ResNet 模型得到 IQ 分数预测结果。
论文链接：https://openreview.net/pdf?id=ByxQB1BKwH
图源：论文《Abstract Diagrammatic Reasoning with Multiplex Graph Networks》
DeepMind 的论文《Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs》提出一种强化学习算法，用来优化 TensorFlow 计算图的成本。首先通过标准的消息传递 GNN 处理图，生成的离散嵌入对应图中每个节点的调度优先级。然后将这些嵌入传输到遗传算法 BRKGA 中，由该算法决定每个节点的布局和调度（placement and scheduling）。该模型用于优化 TensorFlow 图的真实计算成本。
图源：论文《Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs》
GNN 的其他有趣应用还包括分子生成（论文《GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation》）、玩游戏（论文《Graph Convolutional Reinforcement Learning》）和对话系统（论文《Reinforcement Learning Based Graph-to-Sequence Model for Natural Question Generation》）。
以上三篇论文的链接分别如下：
- https://openreview.net/pdf?id=S1esMkHYPr
- https://openreview.net/pdf?id=HkxdQkSYDB
- https://openreview.net/pdf?id=HygnDhEtvr
知识图谱更加流行
这一年涌现出大量有关知识图谱的论文。知识图谱本质上是一种表示事实的结构化方式。与一般的图不同，知识图谱的节点和边均包含意义，如演员姓名或参演电影（参见下图）。知识图谱的常见任务是回答复杂的 query，如「2000 年之前，史蒂文·斯皮尔伯格凭借哪部电影获得奥斯卡奖？」，这个问题可以转换成逻辑 query：∨ {Win(Oscar, V) ∧ Directed(Spielberg, V) ∧ ProducedBefore(2000, V) }。
知识图谱示例。（图源：论文《A Review of Relational Machine Learning for Knowledge Graphs》）
Ren 等人的论文《Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings》提出，将 query 作为矩形框嵌入潜在空间，而不是作为一个点。该方法允许执行自然交运算（即合取 ∧），借助它可以得到新的矩形框。
但是，建模并运算（即析取 ∨）就没有那么直接了，因为它可能导致非重叠区域。此外，要想精确建模任意 query 的嵌入，嵌入之间距离函数的复杂度（由 VC 维度衡量）应与图中实体数成正比。不过，有一个 trick 可以将析取式 query 替换为 DNF，并运算（union）只在计算图的最后一步中出现，因此我们只需对每个子查询执行简单的距离计算即可。
论文链接：https://openreview.net/pdf?id=BJgr4kSFDS
图源：论文《Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings》
在类似的主题中，Wang 等人的论文《Differentiable learning of numerical rules in knowledge graphs》提出了一种处理数值实体和规则的方式。
例如，引用知识图谱具备规则 influences(Y,X) ← colleagueOf(Z,Y) ∧ supervisorOf(Z,X)∧ hasCitation>(Y,Z)，该规则表示学生 X 受到导师 Z 的同事 Y 的影响，Y 的论文引用量更多。规则右侧的每一个关系都可以表示为矩阵，寻找缺失链接的过程可以形式为关系的连续矩阵与实体向量相乘，该过程又叫规则学习（Rule Learning）。由于矩阵构建方式的缘故，神经方法仅能处理类别规则，如 colleagueOf(Z,Y)。
该论文的贡献是：提出了一种高效处理数值规则（如 hasCitation>(Y,Z)）和否定运算符的新方法，该方法证明在现实中没必要将此类矩阵显式具体化，从而极大地减少了运行时间。
论文链接：https://openreview.net/pdf?id=rJleKgrKwS
在机器学习和 GML 领域中出现频率更高的另一个主题是重新评估现有模型及其在公平环境中的性能。Ruffinelli 等人的论文《You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings》证明，新模型的性能通常依赖于实验训练的「小」细节，如损失函数、正则化项和采样机制的形式。在大型控制变量实验中，作者观察到旧有方法（如 RESCAL 模型）在适当调参后可以达到 SOTA 性能。
论文链接：https://openreview.net/pdf?id=BkxSmlBFvr
该领域还有很多有趣的研究工作。
Allen 等人的论文《On Understanding Knowledge Graph Representation》基于近期对词嵌入的见解来更多地理解学得关系和实体表示的潜在空间。
论文链接：https://openreview.net/pdf?id=SygcSlHFvS
Asai 等人的论文《Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering》展示了，模型如何基于能够回答给定 query 的 Wikipedia 图来检索推理路径。
论文链接：https://openreview.net/pdf?id=SJgVHkrYDH
Tabacof 和 Costabello 的论文《Probability Calibration for Knowledge Graph Embedding Models》涉及一个重要主题：图嵌入模型的概率校准（probability calibration）。该研究证明，使用 sigmoid 函数将 logits 转换为概率的常用嵌入模型 TransE 和 ComplEx 并未得到很好地校准，即事实出现的概率被低估或高估了。该研究提出首先生成受损三元组（corrupted triple），并将其作为负例，然后利用 Platt scaling 方法（一种将模型输出转化为基于类别的概率分布的方法）和保序回归方法来校准概率。
论文链接：https://openreview.net/pdf?id=S1g8K1BFwS
新的图嵌入框架
图嵌入是图机器学习领域中的老话题了，今年关于如何学习图表示出现了一些新的观点。
Deng 等人的论文《GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding》提出一种新方法，可以为任意无监督嵌入方法缩短运行时间、提升节点分类准确率。其整体思路是：先将原始图缩小，以便快速计算节点嵌入，然后恢复原始图的嵌入。
先使用额外边增强原始图，这些边对应基于属性相似度得到的节点 k 最近邻之间的链接。然后把图粗糙化：通过局部谱方法将每个节点投影到更低维空间中，并聚合为簇。使用任意无监督图嵌入方法（如 DeepWalk 或 Deep Graph Infomax）均可获得缩小图的节点嵌入。最后，使用平滑算子将获得的节点嵌入（它们本质上表示簇嵌入）迭代地广播回去，以防止不同节点具备相同嵌入。
实验证明，GraphZoom 框架比 node2vec 方法提速 40 倍，准确率比 DeepWalk 方法高出 10%。
论文链接：https://openreview.net/pdf?id=r1lGO0EKDH
图源：论文《GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding》
多篇论文检查了图分类问题的之前结果。Errica 等人的论文《A Fair Comparison of Graph Neural Networks for Graph Classification》就该问题对 GNN 模型进行了公平的重新评估，证明未使用图拓扑（即仅利用聚合节点特征）的简单基线方法的性能与 SOTA GNN 无异。（早在 2015 年 Orlova 等人就发表过这一惊人的现象，但当时并未吸引大量关注。）
该研究的杰出成果包括：提供了模型在常用数据集上的公平 SOTA 结果和 PyTorch-Geometric 代码，方便以后的论文进行模型对比。
论文链接：https://openreview.net/pdf?id=HygDF6NFPB
我们的研究《Understanding Isomorphism Bias in Graph Data Sets》还发现，在常用数据集（如 MUTAG 或 IMDB）中，大量图拥有同构复印件，甚至节点属性也是同构的。此外，在这些同构图中，很多图的目标标签不同，从而给分类器引入了标签噪声。这表明使用网络的所有可用元信息（如节点属性或边属性）对提高模型性能的重要性。
论文链接：https://openreview.net/pdf?id=rJlUhhVYvS
另一项研究《Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification》证明，如果将非线性邻域聚合函数替换为其线性版本（包含邻域度和传播得到的图属性），模型性能不会下降。这与之前的说法一致，即很多图数据集对于图分类无关紧要，这就引出了一个问题：对该任务提供恰当的验证框架。
论文链接：https://openreview.net/pdf?id=BJxQxeBYwH
结论
随着顶会提交论文的增长，预计 2020 年 GML 领域将出现很多有趣的研究。我们已经看到该领域从图深度学习的启发式应用转向了更合理的方法和关于图模型范畴的基础性问题。GNN 成为很多实际问题的解决方案，不过我认为 GML 才刚刚触及到图理论和机器学习交叉领域的皮毛，我们应该更多地关注即将出现的研究成果。
原文链接：https://towardsdatascience.com/top-trends-of-graph-machine-learning-in-2020-1194175351a3
本文为机器之心编译，转载请联系本公众号获得授权。
✄------------------------------------------------
加入机器之心（全职记者 / 实习生）：hr@jiqizhixin.com
投稿或寻求报道：content@jiqizhixin.com
广告 & 商务合作：bd@jiqizhixin.com
