0
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）}」。
知识图谱示例（来源：Nickel 等人的论文）
在 Ren 等人的论文「Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings」中，建议将查询作为矩形。此方法允许执行自然交叉操作，因为它会生成新的矩形框。但是，对并集进行建模并不是那么简单，因为它可能导致不重叠的区域。此外，为了精确地模拟任何嵌入的查询，由 VC 维度测量的嵌入之间的距离函数的复杂性应该与图中实体的数量成正比。相反，有一个很好的技巧可以将析取查询替换为 DNF 形式，其中联合只发生在计算图的末尾，这有效地减少了到每个子查询的简单距离计算。
图片来源于 Ren 等人的论文「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 的影响，Z 有更多的引用。这个规则右边的每一个关系都可以表示为一个矩阵，寻找缺失链接的过程可以表示为一个连续的矩阵乘以实体向量的关系，这个过程称为规则学习。由于矩阵的构造方式，神经方法只能处理分类规则，如 collagueof（Z，Y）。作者的贡献是在一种新的方法上在数值规则上有效地工作，表明在现实中没有必要显式具体化类似 hasCitation>(Y,Z) 这样的矩阵，这大大减少了运行时间。
另一个在机器学习 GML 中更频繁出现的主题是对现有模型的重新评估，以及它们如何在公平的环境中执行。例如 Ruffinelli 等人的论文「You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings」表明，新模型的性能通常取决于实验训练的「次要」细节，如损失函数、正则化器和采样方案的形式。在一项大型研究中，作者观察到，像 RESCAL 模型这样的旧方法只要适当地调整超参数就可以达到 SOTA 的性能。
在这个领域还有许多其他有趣的作品。例如 Allen 等人的文章在词嵌入的最新见解的基础上，了解更多关于关系和实体学习表示的潜在空间。Asai 等人演示了模型如何通过回答给定查询的 Wikipedia 图检索推理路径等等。
4.图嵌入的新框架
图的嵌入一直是图机器学习的一个长期课题，今年对于如何学习图的表示有了新的观点。
Deng 等人在文章「GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding」中，针对工作图缩放中的任意无监督嵌入方法，提出了一种提高节点分类问题运行时间和分类精度的方法。其总体思路是先将原始图缩小为一个更小的图，这样可以快速计算节点嵌入，然后恢复原始图的嵌入。首先，基于属性相似度，在原图中增加与节点 k 近邻之间的链接相对应的附加边。然后，对图进行粗化：通过局部谱方法将每个节点投影到一个低维空间，并聚集成簇。任何无监督的图嵌入方法，如 DeepWalk 或 Deep graph Infomax，都可以用来获取小图上的节点嵌入。最后，使用平滑算子将得到的节点嵌入（本质上表示集群的嵌入）迭代回来，以防止不同节点具有相同的嵌入。在实验中，GraphZoom 框架相比 node2vec 和 DeepWalk 方法实现了惊人的 40 倍加速，精度提高了 10%。
图片来源于 Deng 等人的论文「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 GNNs 相同。这一令人惊讶的现象显然是由 Orlova 等人在之前发表的。它被发表于 2015 年，但没有吸引到大量关注。这项工作的一个很好的结果是在流行的数据集上的公平的 SOTA 结果和 PyTorch Geometric 中方便的代码库，以便为将来的论文运行模型的比较。在理解图数据集的同构偏差的工作中，我们还发现在 MUTAG 或 IMDB 等常用的数据集中，即使考虑节点属性，也有许多图具有同构副本。此外，在这些同构图中，许多图都有不同的目标标记，这自然会给分类器引入标记噪声。这表明使用网络的所有可用元信息（如节点或边缘属性）对于提高模型性能的重要性。Chen 等人的另一篇文章「Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification」表明，如果用包含邻域度和传播图属性的线性邻域聚合函数代替非线性邻域聚合函数，则模型的性能不会降低，这与之前的说法一致，即许多图形数据集对于分类来说都是微不足道的。文章还提出了一个关于此任务的正确验证框架的问题。
结论
随着顶级会议提交量的增长，我们可以预见到 2020 年 GML 领域将会有许多有趣的成果。我们已经可以看到这个领域从图深度学习的启发式应用到更合理的方法，以及关于图模型范围的基本问题的转变。GNN 找到了它的位置，作为一个有效的解决许多实际问题的方法，它可以用图表来表达，但是我希望 GML 大体上已经触及了我们在图论和机器学习交叉点，我们应该继续关注即将到来的结果。
via：https://towardsdatascience.com/top-trends-of-graph-machine-learning-in-2020-1194175351a3
雷锋网雷锋网雷锋网
雷峰网版权文章，未经授权禁止转载。详情见转载须知。
