清华朱文武组一文综述GraphDL五类模型

新智元报道

来源:arxiv 编辑:文强,肖琴,金磊

【新智元导读】今天新智元介绍清华大学朱文武教授组的一篇预印版综述论文,全面回顾图(graph)深度学习,从半监督、无监督和强化学习三大角度,系统介绍了GNN、GCN、图自编码器(GAE)等5大类模型及其应用和发展。

要说最近学界值得关注的趋势,图神经网络(Graph Neural Network, GNN)或者说图深度学习(Graph Deep Learning)绝对算得上一个。

昨天,

阿里巴巴达摩院发布2019十大技术趋势

,其中就包括“超大规模图神经网络系统将赋予机器常识”:

单纯的深度学习已经成熟,而结合了深度学习的图神经网络将端到端学习与归纳推理相结合,有望解决深度学习无法处理的关系推理、可解释性等一系列问题。强大的图神经网络将会类似于由神经元等节点所形成网络的人的大脑,机器有望成为具备常识,具有理解、认知能力的AI。

此前,新智元曾经报道过清华大学孙茂松教授组对图神经网络(GNN)的综述(arxiv预印版),全面阐述了GNN及其方法和应用,便于读者快速了解GNN领域不同模型的动机与优势。

今天,新智元再介绍另一篇清华大学与GNN有关的综述,这次是朱文武教授组发布在arxiv的预印版论文Deep Learning on Graphs: A Survey

作者:张子威,崔鹏,朱文武

在这项工作中,作者全面回顾了应用于图(graph)的各种深度学习方法,从以下三方面系统阐述这些方法及其差异:

半监督方法,包括图神经网络(GNN)和图卷积网络(GCN)

无监督方法,包括图自动编码器(GAE)

最新进展,包括图递归神经网络(Graph RNN)和图强化学习(Graph RL)

从互联网、供应链、化合物的分子结构、感染的传播途径,到世界上最复杂的结构——人脑神经系统,都可以用图(Graph)来表示。

然而,由于图的特殊性,将其应用于深度学习并非易事。图深度学习的潜力巨大已无需赘言,想要快速入门并掌握相关线索,这无疑又是一份极好的资料。

作者在论文中写道,

我们的研究与已有文献的不同之处在于,我们系统而全面地回顾了Graph的不同深度学习架构,而不是专注于一个特定的分支

其次,我们关注的是不同的深度学习模型可以如何应用于图,这与传统的网络嵌入不同。后者指将节点嵌入到低维向量空间中,可以被视为图深度学习的具体例子(而且它们也可以使用非深度学习方法)。

关于网络嵌入,可以参考朱文武老师组另一篇综述:Peng Cui, Xiao Wang, Jian Pei, Wenwu Zhu. A Survey on Network Embedding. IEEE TKDE, 2018”

以下是新智元对这篇综述的摘译。

三大角度,全面回顾图深度学习(GraphDL)

在过去10年中,深度学习一直是人工智能和机器学习领域“皇冠上的明珠”,在声学、图像和自然语言处理中表现出优越的性能。深度学习从底层数据提取复杂模式的表达能力已经得到充分认识。

另一方面,图(graph)[注1:“图”(Graphs)也被称为“网络”(networks),本文交替采用这两个术语] 在现实世界中无处不在,它代表着各种对象及其相互关系,如社交网络、电子商务网络、生物网络和交通网络。

图具有复杂的结构,其中包含丰富的潜在价值。

因此,如何利用深度学习方法进行图数据分析,在过去的几年里引起了相当多的研究关注。

这个问题非常重要,因为将传统的深度学习架构应用到图中存在几个挑战:

不规则域(Irregular domain)。与图像、音频、文本等具有清晰网格结构的数据不同,图处于不规则的域中,使得很难将一些基本的数学运算推广到图中。例如,卷积神经网络(CNN)中的基本操作“卷积”和“池化”,在图数据中并不能直接地定义。这通常被称为几何深度学习问题。

不同的结构和任务。图本身具有复杂的结构。例如,图可以是异质的或同质的,加权的或不加权的,有符号的或无符号的。此外,图的任务也有很大的不同,可以是node-focused问题,如节点分类和链接预测,也可以是graph-focused问题,如图分类和图生成。不同的结构和任务需要不同的模型架构来处理特定的问题。

可扩展性和并行化。在大数据时代,真实的图很容易就会有数百万个节点和边,例如社交网络或电子商务网络。因此,如何设计具有线性时间复杂度的可扩展模型,成为一个关键问题。此外,由于图的节点和边是相互连接的,通常需要作为一个整体进行建模,因此,如何进行并行计算是另一个关键问题。

跨学科性。图常常与其他学科相关联,例如生物学、化学或社会科学。跨学科性既带来机遇,也带来了挑战:领域知识可以被用来解决特定的问题,但是集成领域知识可能使得模型设计更加困难。例如,在生成分子图(molecular graphs)时,目标函数和化学约束通常是不可微的,因此不容易应用基于梯度的训练方法。

为了应对这些挑战,研究人员在这一领域做出了巨大的努力,产生了丰富的相关论文和方法的文献。采用的架构也有很大的差异,从监督到无监督,从卷积到递归。然而,据我们所知,很少有人系统地总结这些不同方法之间的差异和联系。

本文试图通过对图深度学习方法进行全面回顾来填补这一空白。

如图1所示,我们将现有的方法分为三大类:半监督方法、无监督方法和最近的进展

图1:图深度学习方法的分类

具体来说,半监督方法包括图神经网络(GNN)和图卷积网络(GCN);无监督方法主要有图自编码器(GAE);最近的进展包括图递归神经网络图强化学习

那么这些分类有什么区别呢?先看下这张表:

一些图深度学习方法的主要区别

从广义上来看,GNN和GCN是半监督的,因为它们利用节点属性和节点标签来针对特定任务端到端地训练模型参数。

而GAE主要关注学习使用无监督方法的表示。最新提出的方法则使用其他一些独特算法。

在接下来的部分,我们将详细介绍这些方法,主要介绍它们的发展历史,以及这些方法如何解决图的挑战。我们还分析了这些模型之间的差异,以及如何组合不同的架构。最后,我们简要概述了这些方法的应用,并讨论了未来的研究方向。

清晰图表,详尽阐述 GNN、GCN、GAE等5类模型

图神经网络(GNN)

图神经网络是图数据最原始的半监督深度学习方法。

GNN的思路很简单:为了编码图的结构信息,每个节点可以由低维状态向量表示。对于以图为中心的任务,建议添加一个特殊节点,这个节点具有与整个图相对应的唯一属性。

回顾过去,GNN统一了一些处理图数据的早期方法,如递归神经网络和马尔可夫链。

展望未来,GNN中的概念具有深远的启示:许多最先进的GCN实际上遵循与邻近节点交换信息的框架。事实上,GNN和GCN可以统一到一个通用框架中,GNN相当于GCN使用相同层来达到的稳定状态。

从概念角度来看,GNN是非常重要的,但它也有几个缺点: