2020 年才刚刚开始，但我们已经可以通过最新的研究论文看到图形机器学习（GML）的趋势。以下是我对 2020 年 GML 的重要性的看法以及对这些论文的讨论。
前 言
本文的目的不是介绍 GML 的基本概念，如图神经网络（GNNs），而是揭示我们可以在顶级科学会议上看到的前沿研究。首先，我将资料提交给 ICLR2020，这是一个在 GML 领域最负盛名的会议。在前面的文章（https://medium.com/@sergei.ivanov_24894/iclr-2020-graph-papers-9bc2e90e56b0 ）中，我已经描述了关于这个域的一些简单的信息，但是这里有一个简短的版本：
在 GML 领域有 150 份论文被提交，其中三分之一被接收。大约占了所有被接收论文的 10% 。
我阅读了大部分 GML 论文，以下是我对 2020 年趋势的认知：
-
对 GNN 更扎实的理论理解
-
GNN 的最新应用
-
知识图谱越来越流行
-
图嵌入的新框架
让我们看看这些趋势。
1.对 GNN 更扎实的理论理解
我特别高兴地看到这一趋势，因为它表明 GML 领域已经成熟，以前的启发式方法正在被新的理论解决方案所取代。关于图神经网络还有很多需要了解的地方，但是关于 GNNs 是如何工作的已经有很多重要的结果。
我将从我的最爱开始：Andreas Loukas 的「什么图形神经网络无法学习：深度 VS 宽度」。这篇论文在技术的简单性、实践影响力和理论见解的深远性之间取得了显著的平衡。
它表明，如果我们希望 GNN 能够计算出流行图问题（如循环检测、直径估计、顶点覆盖等）的解，那么节点嵌入的维数（网络宽度，w）乘以层数（网络深度，d）应该与图 n 的大小成正比，即 dw=O（n）。
因此，许多 GNN 的当前实现未能达到此条件，这是由于与图的大小相比，层的数量（在许多实现中约为 2-5 层）和嵌入的维度（约为 100-1000 层）不够大。另一方面，在目前的环境下，更大的网络令人望而却步，这就提出了一个问题：我们应该如何设计高效的 GNN，这是我们未来需要解决的问题。让人信服的是，本文还从 80 年代的分布式计算模型中得到启示，说明 GNN 在本质上做了同样的事情。里面有更多的结果，所以我建议你看看。
类似地，其他两篇论文，Oono&Suzuki 和 Barcelóet al. 也研究了 GNN。第一篇文章「Graph Neural Networks Exponentially Lose Expressive Power for Node Classification」中写道：：
在一定的权值条件下，当层数增加时，GCN 除了节点度和连接分量（由 Laplacian 谱确定）外，不能学习任何东西。
这个结果推广了 Markov 过程收敛到唯一平衡点这一众所周知的性质，其中收敛速度由转移矩阵的特征值决定。
在第二篇关于图神经网络逻辑表达的论文中，作者展示了 GNN 与它们能够捕获的节点分类器的类型之间的联系。我们已经知道，有些 GNN 和 WL 同构检验一样强大，即当且仅当两个节点被 GNN 分为同一类时，WL 才对它们着色。但是，GNN 可以捕获其他分类函数吗？例如，假设有一个布尔函数，当且仅当一个图有一个孤立的顶点时，该函数才将 true 赋给所有节点。GNN 能捕获这个逻辑吗？直觉上不能，因为 GNN 是一种消息传递机制，如果图的一部分和另一部分（两个连接的组件）之间没有链接，那么这两个部分之间就不会有消息传递。因此，一个简单的解决方案是在邻域聚集之后添加一个读出操作，这样，现在每个节点在更新所有特征时都有关于图中所有其他节点的信息。
其他理论方面的工作包括 Hou 等人测量 GNN 中图形信息的使用（
https://openreview.net/forum?id=rkeIIkHKvS
），以及 Srinivasan 和 Ribeiro 提出的基于角色和距离的节点嵌入的等价性（
https://openreview.net/forum?id=SJxzFySKwH
）。
2.GNN 的最新应用
看看 GNN 如何应用于实际任务也很棒。今年，它在 JavaScript bug 修复、玩游戏、IQ 类测试回答、优化张量流计算图、分子生成和对话系统中的问题生成都有应用。
在 Dinella 等人的文章「HOPPITY: Learning Graph Transformations to Detect and Fix Bugs in Programs」中提出了一种在 Javascript 代码中同时检测和修复错误的方法。代码被转换为抽象语法树，然后由 GNN 对其进行预处理，得到代码嵌入。
该方法给出了一个处于初始状态的图，通过多轮图编辑操作（添加或删除节点、替换节点值或类型）对其进行修改。为了理解应该修改图中的哪些节点，它们使用指针网络，该网络接受图嵌入和编辑历史并选择节点。然后，使用 LSTM 网络执行修复，该网络还接受图嵌入和编辑的上下文。作者对 GitHub 提交的方法进行了验证，发现它显示出对其他不太通用基线的显著提升。这和 Wei 等人的文章「LambdaNet: Probabilistic Type Inference using Graph Neural Networks」类似。在这片文章中，作者提出了一种依赖超图，它包含程序变量作为节点，还包含它们之间的关系，如逻辑（如布尔类型）或上下文（如相似变量名）约束。然后，首先训练 GNN 模型来产生图的变量和可能的类型的嵌入，然后用它来预测具有最高似然的类型。在实验中，LambdaNet 在标准变量类型（例如 boolean）和用户定义类型中的性能都更高。
在 Wang 等人的论文「Abstract Diagrammatic Reasoning with Multiplex Graph Networks」中，用多重图网络推理演示了如何在类智商测试中用 GNN 进行推理。在 RPM 任务中，为矩阵的每一行组成一个图，其中的边嵌入是通过一个前馈模型获得的，随后是图摘要。因为最后一行有 8 个可能的答案，所以创建了 8 个不同的图，每个图都与前两行连接起来，通过 ResNet 模型得到 IQ 分数的预测。
图片来自 Wang 等人的「Abstract Diagrammatic Reasoning with Multiplex Graph Networks」
DeepMind 的一篇论文「Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs」提出了一种 RL 算法来优化张量流计算图的花销。这些图通过标准消息传递 GNN 进行处理，GNN 生成与图中每个节点的调度优先级相对应的离散化嵌入。这些嵌入被输入到遗传算法 BRKGA 中，BRKGA 决定每个节点的设备布局和调度。训练该模型以优化所得到的张量流图的实际计算成本。
图片来自 Paliwal 等人的「Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs」
3.知识图谱越来越流行
今年有不少关于知识图谱推理的论文。从本质上讲，知识图谱是表示事实的结构化方法。与一般图不同，在知识图谱中，节点和边实际上具有一些含义，如演员的名字或电影中的表演（见下图）。知识图谱上的一个常见问题是回答复杂的问题，例如「2000 年前 Steven Spielberg 的哪部电影获得了奥斯卡奖？」可以转换为逻辑查询「{Win（Oscar，V）∧Directed（Spielberg，V）∧ProducedBefore（2000，V）}」。
