CNN已老,GNN来了!清华大学孙茂松组一文综述GNN

2018 年 12 月 26 日 全球人工智能
CNN已老,GNN来了!清华大学孙茂松组一文综述GNN

来源:Arxiv ,新智元

深度学习的最大软肋是什么?


这个问题的回答仁者见仁,但图灵奖得主Judea Pearl大概有99.9%的几率会说,是无法进行因果推理。


对于这个问题,业界正在进行积极探索,而其中一个很有前景的方向就是图神经网络(Graph Neural Network, GNN)


最近,清华大学孙茂松教授组在 arXiv 发布了论文 Graph Neural Networks: A Review of Methods and Applications,作者对现有的GNN模型做了详尽且全面的综述。


作者:周界*、崔淦渠*、张正彦*,杨成,刘知远,孙茂松


“图神经网络是连接主义与符号主义的有机结合,不仅使深度学习模型能够应用在图这种非欧几里德结构上,还为深度学习模型赋予了一定的因果推理能力。”论文的共同第一作者周界说。


“在深度学习方法的鲁棒性与可解释性受到质疑的今天,图神经网络可能为今后人工智能的发展提供了一个可行的方向。”


GNN最近在深度学习领域受到了广泛关注。然而,对于想要快速了解这一领域的研究人员来说,可能会面临着模型复杂、应用门类众多的问题。


“本文希望为读者提供一个更高层次的视角,快速了解GNN领域不同模型的动机与优势。”周界告诉新智元:“同时,通过对不同的应用进行分类,方便不同领域的研究者快速了解将GNN应用到不同领域的文献。”


毫不夸张地说,论文中的图表对于想要了解学习GNN乃至因果推理等方向的研究者来说,简直应该高清打印过塑然后贴在墙上以作参考——


GNN的各种变体,通过比对各自的 aggregator & updater,就能轻松分辨不同的GNN模型。这只是这篇综述强大图表的一个示例。


想要快速了解GNN,看这篇文章绝对没错


在内容上,模型方面,本文从GNN原始模型的构建方式与存在的问题出发,介绍了对其进行不同改进的GNN变体,包括如何处理不同的图的类型、如何进行高效的信息传递以及如何加速训练过程。最后介绍了几个近年来提出的通用框架,它们总结概括了多个现有的方法,具有较强的表达能力。


在应用上,文章将GNN的应用领域分为了结构化场景、非结构化场景以及其他场景并介绍了诸如物理、化学、图像、文本、图生成模型、组合优化问题等经典的GNN应用。


典型应用场景介绍


文章最后提出了四个开放性问题,包括如何处理堆叠多层GNN造成的平滑问题,如何处理动态变化的图结构,如何使用通用的方法处理非结构化的数据以及如何将其扩展到更大规模的网络上。


作者还整理了一个GNN论文列表:

https://github.com/thunlp/GNNPapers


以下是小编对这篇综述的部分摘译,点击阅读原文查看 arXiv 论文


原始GNN及其局限性


GNN的概念首先是在F. Scarselli等人的论文The graph neural network model(F. Scarselli et. al. 2009)中提出的。在这里,我们描述了原始的GNN,并列举了原始GNN在表示能力和训练效率方面的局限性。


接着,我们介绍了几种不同的GNN变体,这些变体具有不同的图形类型,利用不同的传播函数和训练方法。


最后,我们介绍了三个通用框架,分别是message passing neural network (MPNN),non-local neural network (NLNN),以及graph network(GN)。MPNN结合了各种图神经网络和图卷积网络方法;NLNN结合了几种“self-attention”类型的方法;而图网络GN可以概括本文提到的几乎所有图神经网络变体。


图神经网络


如前所述,图神经网络(GNN)的概念最早是Scarselli等人在2009年提出的,它扩展了现有的神经网络,用于处理图(graph)中表示的数据。在图中,每个节点是由其特性和相关节点定义的。


虽然实验结果表明,GNN是建模结构化数据的强大架构,但原始GNN仍存在一些局限性。


首先,对于固定节点,原始GNN迭代更新节点的隐藏状态是低效的。如果放宽了固定点的假设,我们可以设计一个多层的GNN来得到节点及其邻域的稳定表示。


其次,GNN在迭代中使用相同的参数,而大多数流行的神经网络在不同的层中使用不同的参数,这是一种分层特征提取方法。此外,节点隐藏状态的更新是一个顺序过程,可以从RNN内核(如GRU 和 LSTM)中获益。


第三,在边上也有一些无法在原始GNN中建模的信息特征。此外,如何学习边的隐藏状态也是一个重要的问题。


最后,如果我们把焦点放在节点的表示上而不是图形上,就不适合使用固定点,因为在固定点上的表示的分布在数值上是平滑的,区分每个节点的信息量也比较少。


图神经网络的变体


在这一节,我们提出图神经网络的几种变体。首先是在不同图类型上运行的变体,这些变体扩展了原始模型的表示能力。其次,我们列出了在传播步骤进行修改(卷积、门机制、注意力机制和skip connection)的几种变体,这些模型可以更好地学习表示。最后,我们描述了使用高级训练方法的标题,这些方法提高了训练效率。


图2概述了GNN的不同变体。


一览GNN的不同变体


图的类型(Graph Types)


在原始GNN中,输入的图由带有标签信息的节点和无向的边组成,这是最简单的图形格式。然而,世界上有许多不同的图形。这里,我们将介绍一些用于建模不同类型图形的方法。


图类型的变体


  • 有向图(Directed Graphs )


图形的第一个变体是有向图。无向边可以看作是两个有向边,表明两个节点之间存在着关系。然而,有向边比无向边能带来更多的信息。例如,在一个知识图中,边从head实体开始到tail实体结束,head实体是tail实体的父类,这表明我们应该区别对待父类和子类的信息传播过程。有向图的实例有ADGPM (M. Kampffmeyer et. al. 2018)。


  • 异构图(Heterogeneous Graphs)


图的第二个变体是异构图,异构图有几种类型的节点。处理异构图最简单的方法是将每个节点的类型转换为与原始特征连接的一个one-hot特征向量。异构图如GraphInception。


  • 带边信息的图(Edge-informative Graph)


图的另外一个变体是,每条边都有信息,比如权值或边的类型。例如G2S和R-GCN。


使用不同训练方法的图变体


训练方法变体


在传播步骤进行修改的GNN变体


传播步骤变体


GNN的三大通用框架


除了图神经网络的不同变体之外,我们还介绍了几个通用框架,旨在将不同的模型集成到一个框架中。


J. Gilmer等人(J. Gilmer et. al. 2017)提出了消息传递神经网络(message passing neural network, MPNN),统一了各种图神经网络和图卷积网络方法。


X. Wang等人(X. Wang et. al. 2017)提出了非局部神经网络(non-local neural network, NLNN),它结合了几种“self-attention”风格的方法。


P. W. Battaglia等人(P. W. Battaglia et. al. 2018)提出了图网络(graph network, GN),它统一了统一了MPNN和NLNN方法以及许多其他变体,如交互网络(Interaction Networks),神经物理引擎(Neural Physics Engine),CommNet,structure2vec,GGNN,关系网络(Relation Network),Deep Sets和Point Net。


几个尚未解决的问题


尽管GNN在不同领域取得了巨大成功,但值得注意的是,GNN模型还不能在任何条件下,为任何图任务提供令人满意的解决方案。这里,我们将陈述一些开放性问题以供进一步研究。

 

浅层结构

 

传统的深度神经网络可以堆叠数百层,以获得更好的性能,因为更深的结构具备更多的参数,可以显著提高网络的表达能力。然而,GNN总是很浅,大多数不超过三层。


实验显示,堆叠多个GCN层将导致过度平滑,也就是说,所有顶点将收敛到相同的值。尽管一些研究人员设法解决了这个问题,但这仍然是GNN的最大局限所在。设计真正的深度GNN对于未来的研究来说是一个令人兴奋的挑战,并将对进一步深入理解GNN做出相当大的贡献。

 

动态图形另一个具有挑战性的问题是如何处理具有动态结构的图形。静态图总是稳定的,因此对其进行建模是可行的,而动态图引入了变化的结构。当边和节点出现或消失时,GNN不能自适应地做出改变。目前对动态GNN的研究也在积极进行中,我们认为它是一般GNN的具备稳定性和自适应性的重要里程碑。

 

非结构性场景

 

我们讨论了GNN在非结构场景中的应用,但我们没有找到从原始数据中生成图的最佳方法。在图像域中,一些研究可以利用CNN获取特征图,然后对其进行上采样,形成超像素作为节点,还有的直接利用一些对象检测算法来获取对象节点。在文本域中,有些研究使用句法树作为句法图,还有的研究采用全连接图。因此,关键是找到图生成的最佳方法,使GNN在更广泛的领域发挥更大的作用。

 

可扩展性问题

 

如何将嵌入式算法应用于社交网络或推荐系统这类大规模网络环境,是几乎所有图形嵌入算法面对的一个致命问题,GNN也不例外。对GNN进行扩展是很困难的,因为涉及其中的许多核心流程在大数据环境中都要消耗算力。


这种困难体现在几个方面:首先,图数据并不规则,每个节点都有自己的邻域结构,因此不能批量化处理。其次,当存在的节点和边数量达到数百万时,计算图的拉普拉斯算子也是不可行的。此外,我们需要指出,可扩展性的高低,决定了算法是否能够应用于实际场景。目前已经有一些研究提出了解决这个问题的办法,我们正在密切关注这些新进展。


结论


在过去几年中,GNN已经成为图领域机器学习任务的强大而实用的工具。这一进展有赖于表现力,模型灵活性和训练算法的进步。在本文中,我们对图神经网络进行了全面综述。对于GNN模型,我们引入了按图类型、传播类型和训练类型分类的GNN变体。


此外,我们还总结了几个统一表示不同GNN变体的通用框架。在应用程序分类方面,我们将GNN应用程序分为结构场景、非结构场景和其他18个场景,然后对每个场景中的应用程序进行详细介绍。最后,我们提出了四个开放性问题,指出了图神经网络的主要挑战和未来的研究方向,包括模型深度、可扩展性、动态图处理和对非结构场景的处理能力。

广告 & 商务合作请加微信:kellyhyw    

投稿请发送至:mary.hu@aisdk.com


登录查看更多
13

相关内容

图神经网络 (GNN) 是一种连接模型,它通过图的节点之间的消息传递来捕捉图的依赖关系。与标准神经网络不同的是,图神经网络保留了一种状态,可以表示来自其邻域的具有任意深度的信息。近年来,图神经网络(GNN)在社交网络、知识图、推荐系统、问答系统甚至生命科学等各个领域得到了越来越广泛的应用。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等

题目: Introduction to Graph Neural Networks

简介:

在复杂的实际应用中,图是有用的数据结构,例如对物理系统进行建模,学习分子指纹,控制交通网络以及在社交网络中推荐朋友。但是,这些任务需要处理包含元素之间的丰富关系信息且无法通过传统深度学习模型(例如卷积神经网络(CNN)或递归神经网络(RNN))妥善处理的非欧氏图数据。图中的节点通常包含有用的特征信息,这些信息在大多数无监督的表示学习方法(例如,网络嵌入方法)中无法很好地解决。提出了图神经网络(GNN)来结合特征信息和图结构,以通过特征传播和聚集学习更好的图表示。由于其令人信服的性能和高解释性,GNN最近已成为一种广泛应用的图形分析工具。本书全面介绍了图神经网络的基本概念,模型和应用。首先介绍了香草GNN模型。然后介绍了vanil la模型的几种变体,例如图卷积网络,图递归网络,图注意力网络,图残差网络和一些通用框架。还包括不同图类型的变体和高级训练方法。对于GNN的应用,该书将min分为结构,非结构和其他场景,然后介绍了解决这些任务的几种典型模型。最后,最后几章提供了GNN的开放资源以及一些未来方向的展望。

深度学习在许多领域都取得了可喜的进展,例如计算机视觉和自然语言处理。这些任务中的数据通常以欧几里得表示。但是,许多学习任务需要处理包含元素之间丰富的关系信息的非欧氏图数据,例如建模物理系统,学习分子指纹,预测蛋白质界面等。图神经网络(GNN)是基于深度学习的方法,在图域上运行。由于其令人信服的性能和高解释性,GNN最近已成为一种广泛应用的图形分析方法。本书全面介绍了图神经网络的基本概念,模型和应用。它从数学模型和神经网络的基础开始。在第一章中,它对GNN的基本概念进行了介绍,目的是为读者提供一个概览。然后介绍了GNN的不同变体:图卷积网络,图递归网络,图注意力网络,图残差网络和一些通用框架。这些最差的结果是将通用的深度学习技术转化为图形,例如卷积神经网络,递归神经网络,注意力机制和跳过连接。此外,这本书介绍了GNN在结构场景(物理,化学,知识图谱),非结构场景(图像,文本)和其他场景(生成模型,组合优化)中的不同应用。最后,这本书列出了相关的数据集,开源平台和GNN的实现。本书组织如下。在第1章中进行了概述之后,在第2章中介绍了数学和图论的一些基本知识。在第3章中介绍了神经网络的基础,然后在第4章中简要介绍了香草GNN。四种类型的模型分别在第5、6、7和8章中介绍。在第9章和第10章中介绍了不同图类型和高级训练方法的其他变体。然后在第11章中提出了几种通用的GNN框架。第12、13和14章介绍了GNN在结构场景,非结构场景和其他场景中的应用。最后,我们在第15章提供了一些开放资源,并在第16章总结了这本书。

成为VIP会员查看完整内容
Introduction to Graph Neural Networks.pdf
0
187

题目: Graph Neural Networks:A Review of Methods and Applications

简介: 许多学习任务需要处理图形数据,该图形数据包含元素之间的关系信息。对物理系统进行建模,学习分子指纹,预测蛋白质界面以及对疾病进行分类,都需要从图输入中学习模型。在诸如从文本和图像之类的非结构数据中学习的其他领域中,对提取结构的推理,例如句子的依存关系树和图像的场景图,是一个重要的研究课题,它也需要图推理模型。图神经网络(GNN)是连接器模型,可通过在图的节点之间传递消息来捕获图的依赖性。与标准神经网络不同,图神经网络保留一种状态,该状态可以表示来自其邻域的任意深度的信息。尽管已经发现难以训练原始图神经网络来固定点,但是网络体系结构,优化技术和并行计算的最新进展已使他们能够成功学习。近年来,基于图卷积网络(GCN)和门控图神经网络(GGNN)的系统已经在上述许多任务上展示了突破性的性能。在本综述中,我们对现有的图神经网络模型进行了详细的回顾,对应用程序进行了系统分类,并提出了四个未解决的问题,供以后研究。

作者简介: 周杰,教授,清华大学自动化系党委书记,教授,博士生导师。

成为VIP会员查看完整内容
0
376
小贴士
相关资讯
相关VIP内容
【新书】图神经网络导论,清华大学刘知远老师著作
专知会员服务
290+阅读 · 2020年6月12日
专知会员服务
115+阅读 · 2020年5月26日
专知会员服务
124+阅读 · 2020年3月10日
五篇 ICCV 2019 的【图神经网络(GNN)+CV】相关论文
专知会员服务
12+阅读 · 2020年1月9日
注意力机制模型最新综述
专知会员服务
200+阅读 · 2019年10月20日
深度学习自然语言处理综述,266篇参考文献
专知会员服务
161+阅读 · 2019年10月12日
相关论文
Filippo Maria Bianchi,Daniele Grattarola,Cesare Alippi
23+阅读 · 2020年6月3日
Hyper-SAGNN: a self-attention based graph neural network for hypergraphs
Ruochi Zhang,Yuesong Zou,Jian Ma
12+阅读 · 2019年11月6日
Saurabh Verma,Zhi-Li Zhang
4+阅读 · 2019年9月25日
Self-Attention Graph Pooling
Junhyun Lee,Inyeop Lee,Jaewoo Kang
10+阅读 · 2019年6月13日
Ryoma Sato,Makoto Yamada,Hisashi Kashima
7+阅读 · 2019年5月24日
HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
Naganand Yadati,Madhav Nimishakavi,Prateek Yadav,Vikram Nitin,Anand Louis,Partha Talukdar
9+阅读 · 2019年5月22日
Generative Graph Convolutional Network for Growing Graphs
Da Xu,Chuanwei Ruan,Kamiya Motwani,Evren Korpeoglu,Sushant Kumar,Kannan Achan
3+阅读 · 2019年3月6日
Vachik S. Dave,Baichuan Zhang,Pin-Yu Chen,Mohammad Al Hasan
4+阅读 · 2018年4月23日
Jiaxuan You,Rex Ying,Xiang Ren,William L. Hamilton,Jure Leskovec
6+阅读 · 2018年2月24日
Ruoyu Li,Sheng Wang,Feiyun Zhu,Junzhou Huang
5+阅读 · 2018年1月10日
Top
微信扫码咨询专知VIP会员