本文转自雷锋网，如需转载请至雷锋网官网请求授权。

2019年肯定是图机器学习（GML）大火的一年，但凡学术会议，图神经网络的会场总会爆满。

图机器学习的研讨之所以在2019年忽然变得炽热，原因在于，在前几年虽然深度学习在欧氏空间中的数据方面取得了巨大的成功，但在许多实践的运用场景中的数据往往是从非欧式空间生成的。

正如阿里达摩院曾在2019年所提：“单纯的深度学习现已老练，而结合了深度学习的图研讨将端到端学习与归纳推理相结合，有望处理深度学习无法处理的联络推理、可解释性等一系列问题。”

在曩昔的一年里，图机器学习经过了繁荣的开展，这从各大顶会中图机器学习的火爆场面也能够看出。

而新的一年现已曩昔了一个月，那么2020年图机器学习的炽热还能继续吗？又将有哪些新的研讨趋势呢？即将于4月份在埃塞俄比亚举行的ICLR 2020是一个能够很好反映这些问题的会议。

这个会议是由深度学习三巨子之二的 Yoshua Bengio 和 Yann LeCun 牵头兴办，旨在重视有关深度学习各个方面的前沿研讨。

在ICLR 2020中共有150篇投稿与图机器学习有关，而其间有近1/3的论文都被录用了，这也阐明图机器学习炽热仍旧。

咱们无妨将这些论文依照理论、运用、常识图谱、图嵌入来区分，然后一窥图机器学习在2020年的研讨趋势。

注：文中触及论文，可重视雷锋网「AI科技谈论」微信大众号，并后台回复「2020年GML趋势」下载。

1、GNN理论常识会愈加厚实

从现在的办法看，图机器学习的范畴在老练的阳关大道上越走越远，可是图神经网络还有许多前进空间。曩昔的一年图神经网络不断改进，因而诞生了许多理论研讨，在咱们对2020年猜测之前，先来简略整理一下图神经网络的重要理论效果吧！

What graph neural networks cannot learn: depth vs width

https://openreview.net/forum?id=B1l2bp4YwS

洛桑联邦理工学院 Andreas Loukas 的这篇论文，不管在影响力、简洁性仍是对理论了解的深度上，无疑是论文中的模范。

它标明，当咱们用GNN核算一般的图问题时，节点嵌入的维数（网络的宽度，w）乘以层数（网络的深度，d）应该与图n的巨细成正比，即dW=O(n)。

但现实是当时的GNN的许多完成都无法到达此条件，因为层数和嵌入的尺度与图的巨细比较还不够大。另一方面，较大的网络在实践操作中不适宜的，这会引发有关怎么规划有用的GNN的问题，当然这个问题也是研讨人员未来作业的要点。需求阐明的是，这篇论文还从80年代的分布式核算模型中汲取了创意，证明了GNN本质上是在做相同的作业。

这篇文章还包含有许多有价值的定论，强烈主张去阅览原文。可重视雷锋网(大众号：雷锋网)「AI科技谈论」微信大众号，后台回复「2020年GML趋势」下载论文。

相同，在别的两篇论文中，Oono等人研讨了GNN的才能。榜首篇文章是《图神经网络在节点分类中失去了表达才能》，第二篇文章是《图神经网络的逻辑表达》。

Graph Neural Networks Exponentially Lose Expressive Power for Node Classification

https://openreview.net/forum?id=S1ldO2EFPr

这篇论文标明：“在已知某些条件下的权重，当层数增加时，GCN除了节点度和连通重量以外，将无法学习其他任何内容。”这一成果扩展了“马尔可夫进程收敛到仅有平衡点”的性质，并标明其间收敛速度由搬运矩阵的特征值决议。

The Logical Expressiveness of Graph Neural Networks

https://openreview.net/pdf?id=r1lZ7AEKvB

这篇论文展现了GNN与节点分类器类型之间的联络。在这之前，咱们现已了解GNN与WL同构查验相同强壮。可是GNN能够取得其他分类功用么？直观上不可，因为GNN是一种音讯传递机制，假如图的一个部分和另一个部分之间没有链接，那么两者之间就不会传递音讯。

因而论文提出一个简略处理计划：在邻域聚合之后增加一个读出操作，以便每个节点在更新一切要素时与图中一切其他节点都有联络。

其他在理论上的作业还有许多，包含Hou等人丈量GNN的图形信息的运用。以及 Srinivasan 和 Ribeiro提出的依据人物的节点嵌入和依据间隔的节点嵌入的等价性评论。

论文链接如下：

Measuring and Improving the Use of Graph Information in Graph Neural Networks

https://openreview.net/forum?id=rkeIIkHKvS

On the Equivalence between Positional Node Embeddings and Structural Graph Representationshttps://openreview.net/forum?id=SJxzFySKwH

2、新酷运用不断涌现

在曩昔的一年中，GNN现已在一些实践使命中进行了运用。例如现已有一些程序运用于玩游戏、答复智商检验、优化TensorFlow核算图形、分子生成以及对话体系中的问题生成。

HOPPITY: LEARNING GRAPH TRANSFORMATIONS TO DETECT AND FIX BUGS IN PROGRAMS

https://openreview.net/pdf?id=SJeqs6EFvB

在论文中，作者其提出了一种在Javascript代码中一起检测和修正过错的办法。具体操作是将代码转换为笼统语法树，然后让GNN进行预处理以便取得代码嵌入，再经过多轮图形修正运算符（增加或删去节点，替换节点值或类型）对其进行修正。为了了解图形的哪些节点应该修正，论文作者运用了一个指针网络（Pointer network），该网络采用了图形嵌入来挑选节点，以便运用LSTM网络进行修正。当然，LSTM网络也承受图形嵌入和上下文修正。

LambdaNet: Probabilistic Type Inference using Graph Neural Networks

https://openreview.net/pdf?id=Hkx6hANtwH

类似的运用还表现在上面这篇论文中。来自得克萨斯大学奥斯汀分校的作者研讨了怎么揣度像Python或TypeScript此类言语的变量类型。更为具体的，作者给出了一个类型依靠超图（type dependency hypergraph），包含了程序作为节点的变量以及它们之间的联络，如逻辑联络、上下文束缚等；然后练习一个GNN模型来为图和或许的类型变量发生嵌入，并结合似然率进行猜测。

Abstract Diagrammatic Reasoning with Multiplex Graph Networks

https://openreview.net/pdf?id=ByxQB1BKwH

在智商检验类的运用中，上面这篇论文展现了GNN怎么进行IQ类检验，例如瑞文检验（RPM）和图三段论（DS）。具体的在RPM使命中，矩阵的每一行组成一个图形，经过前馈模型为其获取边际嵌入，然后进行图形汇总。因为最终一行有8个或许的答案，因而将创立8个不同的图，并将每个图与前两行衔接起来，以经过ResNet模型猜测IQ得分。如下图所示：

来自：https://openreview.net/pdf?id=ByxQB1BKwH

Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs

https://openreview.net/pdf?id=rkxDoJBYPBDeepMind

在上面的论文中提出了一种RL算法来优化TensorFlow核算图的开支。先经过规范GNN对图形进行处理，然后发生与图中每个节点的调度优先级相对应的离散化嵌入，最终将嵌入被馈送到遗传算法BRKGA中进行模型练习，然后优化得到的TensorFlow图的实践核算开支。值得注意的是该遗传算法决议每个节点的布局和调度。

类似的炫酷运用还有Chence Shi的分子结构生成和Jiechuan Jiang玩游戏以及Yu Chen的玩游戏等等。

论文链接如下：Graph Convolutional Reinforcement Learning

https://openreview.net/forum?id=HkxdQkSYDB

Reinforcement Learning Based Graph-to-Sequence Model for Natural Question Generation

https://openreview.net/forum?id=HygnDhEtvr

3、常识图谱将愈加盛行

在本年的ICLR会议上，有许多关于常识图谱推理的论文。

常识图谱比如（来历：https://arxiv.org/abs/1503.00759）

从本质上讲，常识图谱是一种结构化的标明现实的办法。与一般的图不同，常识图谱的节点和边实践上具有必定的意义，例如艺人的姓名、电影名等。常识图谱中一个常见的问题是，怎么答复一些复杂问题，例如“斯皮尔伯格哪些电影在2000年之前赢得了奥斯卡奖？”，这个问题翻译成逻辑查询言语则是：
∨ {Win(Oscar, V)∧ Directed(Spielberg, V)∧ProducedBefore(2000, V)}Query2box:

Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings

https://openreview.net/forum?id=BJgr4kSFDS

Query2Box 推理结构在斯坦福大学Hongyu Ren等人的作业中，他们主张将query嵌入到隐空间傍边，而不是作为单个的点（作为矩形框）。

QUERY2BOX的两种操作及间隔函数的几许示例这种办法使得能够天然地履行 交 操作（即合取∧），得到一个新的矩形框。可是关于 并 操作（即析取 ∨）却并不那么简略，因为它或许会发生非堆叠区域。

此外，要运用嵌入来对一切query进行准确建模，嵌入之间的间隔函数（经过VC维度进行衡量）的复杂性会与图谱中实体的数量成正比。

不过有一个不错的技巧能够将析取（ ∨）query转换为DNF办法，这时候只要在图核算的最终才会进行 并 操作，这能够有用削减每个子查询的间隔核算。

Differentiable Learning of Numerical Rules in Knowledge Graphs

https://openreview.net/forum?id=rJleKgrKwSCMU的Po-Wei

Wang等人在类似主题的一篇文章提出了一种处理数字实体和规矩的办法。

引证常识图谱（Citation KG）示例举例来说，以引证常识图谱（Citation KG），能够有一条规矩：influences(Y,X)←colleagueOf(Z,Y)∧supervisorOf(Z,X)∧hasCitation>(Y,Z)这是一个典型的状况，即学生X遭到其导师Z的搭档Y（Y有较高的引证率）的影响。

这个规矩右边的每个联络都能够标明为一个矩阵，而寻觅缺失衔接（missing links）的进程能够标明为联络与实体向量的接连矩阵乘积，这个进程称为规矩学习。因为矩阵的结构办法，神经网络的办法只能在分类规矩colleagueOf(Z,Y)下作业。

作者的奉献在于，他们经过一种新颖的办法证明了，在实践中并不需求显式地标明这些矩阵，然后有用地处理了类似hasCitation>(Y,Z)、求反运算这样的数字规矩，这大大降低了运转时刻。

You CAN Teach an Old Dog New Tricks!

On Training Knowledge Graph Embeddingshttps://openreview.net/forum?id=BkxSmlBFvr

在本年的图神经网络（或者说机器学习）中经常呈现的一个研讨方向是：对现有模型的从头评价，以及在一个公正环境中进行测评。

上面这篇文章便是其间一个，他们的研讨标明，新模型的功能往往取决于试验练习中的“非必须”细节，例如丢失函数的办法、正则器、采样的计划等。

在他们进行的大型融化研讨中，作者观察到将旧的办法（例如RESCAL模型）的超参数进行恰当调整就能够取得SOTA功能。当然在这个范畴还有许多其他风趣的作业，Allen et al. 依据对词嵌入的最新研讨，进一步探求了联络与实体的学习标明的隐空间。Asai et al. 则展现了模型怎么在答复给定query的Wikipedia图谱上检索推理途径。

Tabacof 和 Costabello 评论了图嵌入模型的概率标定中的一个重要问题，他们指出，现在盛行的嵌入模型TransE 和ComplEx（经过将logit函数转换成sigmoid函数来取得概率）均存在误校，即对现实的存在猜测缺乏或猜测过度。

论文链接如下：On Understanding Knowledge Graph Representation

https://openreview.net/forum?id=SygcSlHFvS

Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering

https://openreview.net/forum?id=SJgVHkrYDH

Probability Calibration for Knowledge Graph Embedding Models

https://openreview.net/forum?id=S1g8K1BFwS

4、图嵌入的新结构

图嵌入是图机器学习的一个长时刻的研讨主题，本年有一些关于咱们应该怎么学习图标明的新观念呈现。

GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding

https://openreview.net/forum?id=r1lGO0EKDH

康奈尔的Chenhui Deng等人提出了一种改进运转时刻和准确率的办法，能够运用到任何无监督嵌入办法的节点分类问题。这篇文章的整体思路是，首先将原始图简化为更小的图，这样能够快速核算节点嵌入，然后再回复原始图的嵌入。

开始，依据特点类似度，对原始图进行额定的边扩大，这些便对应于节点的k近邻之间的链接。随后对图进行粗化：经过部分谱办法将每个节点投影到低维空间中，并聚组成簇。任何无监督的图嵌入办法（例如DeepWalk、Deep Graph Infomax）都能够在小图上取得节点嵌入。在最终一步，得到的节点嵌入（本质上标明簇的嵌入）用滑润操作符迭代地进行播送，然后避免不同节点具有相同的嵌入。在试验中，GraphZoom结构比较node2vec和DeepWalk，完成了惊人的 40 倍的加快，准确率也进步了 10%。

A Fair Comparison of Graph Neural Networks for Graph Classification

https://openreview.net/forum?id=HygDF6NFPB

已有多篇论文对图分类问题的研讨效果进行了具体的剖析。比萨大学的Federico Errica 等人在图分类问题上，对GNN模型进行了从头评价。

他们的研讨标明，一个不使用图的拓扑结构（仅适用聚合节点特征）的简略基线能取得与SOTA GNN差不多的功能。现实上，这个让人惊奇的发现，Orlova等人在2015年就现已宣布了，但没有引起我们的广泛重视。

Understanding Isomorphism Bias in Graph Data Sets

https://openreview.net/forum?id=rJlUhhVYvSSkolkovo

科学技术研讨院的Ivanov Sergey等人在研讨中发现，在MUTAG和IMDB等常用数据会集，即便考虑节点特点，许多图也都会具有同构副本。并且，在这些同构图中，许多都有不同的target标签，这天然会给分类器引进标签噪声。这标明，使用网络中一切可用的元信息（如节点或边特点）来进步模型功能是非常重要的。

Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification

https://openreview.net/forum?id=BJxQxeBYwH

别的还有一项作业是UCLA孙怡舟团队的作业。这项作业显现假如用一个线性近邻聚合函数替代原有的非线性近邻聚合函数，模型的功能并不会下降。这与之前我们普遍认为“图数据集对分类的影响并不大”的观念是相反的。一起这项作业也引发一个问题，即怎么为此类使命找到一个适宜的验证结构。