火爆的图机器学习,2020年将有哪些研究趋势?

 火爆的图机器学习,2020年将有哪些研究趋势?

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

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得分。如下图所示:

火爆的图机器学习,2020年将有哪些研究趋势?

来自: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图的实际计算开销。值得注意的是该遗传算法决定每个节点的布局和调度。

火爆的图机器学习,2020年将有哪些研究趋势?

类似的炫酷应用还有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会议上,有很多关于知识图谱推理的论文。 

火爆的图机器学习,2020年将有哪些研究趋势?

知识图谱例子(来源: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

火爆的图机器学习,2020年将有哪些研究趋势?

Query2Box 推理框架 在斯坦福大学Hongyu Ren等人的工作中,他们建议将query嵌入到隐空间当中,而不是作为单个的点(作为矩形框)。

火爆的图机器学习,2020年将有哪些研究趋势?

QUERY2BOX的两种操作及距离函数的几何示例 这种方法使得可以自然地执行 交 操作(即合取 ∧),得到一个新的矩形框。但是对于 并 操作(即析取 ∨)却并不那么简单,因为它可能会产生非重叠区域。

此外,要使用嵌入来对所有query进行精确建模,嵌入之间的距离函数(通过VC维度进行度量)的复杂性会与图谱中实体的数量成正比。

不过有一个不错的技巧可以将析取( ∨)query转换为DNF形式,这时候只有在图计算的最后才会进行 并 操作,这能够有效减少每个子查询的距离计算。

Differentiable Learning of Numerical Rules in Knowledge Graphs

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

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

火爆的图机器学习,2020年将有哪些研究趋势?

引用知识图谱(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

在今年的图神经网络(或者说机器学习)中经常出现的一个研究方向是:对现有模型的重新评估,以及在一个公平环境中进行测评。

火爆的图机器学习,2020年将有哪些研究趋势?

上面这篇文章即是其中一个,他们的研究表明,新模型的性能往往取决于试验训练中的“次要”细节,例如损失函数的形式、正则器、采样的方案等。

在他们进行的大型消融研究中,作者观察到将旧的方法(例如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等人提出了一种改善运行时间和准确率的方法,可以应用到任何无监督嵌入方法的节点分类问题。 这篇文章的总体思路是,首先将原始图简化为更小的图,这样可以快速计算节点嵌入,然后再回复原始图的嵌入。

火爆的图机器学习,2020年将有哪些研究趋势?

最初,根据属性相似度,对原始图进行额外的边扩充,这些便对应于节点的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模型进行了重新评估。

火爆的图机器学习,2020年将有哪些研究趋势?

他们的研究表明,一个不利用图的拓扑结构(仅适用聚合节点特征)的简单基线能获得与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

相关推荐