您当前的位置:首页 > 电脑百科 > 人工智能

图神经网络的表达能力,究竟有多强大?

时间:2020-08-16 15:11:54  来源:  作者:
图神经网络的表达能力,究竟有多强大?

作者 | Mr Bear

编辑 | 丛 末

近年来,随着图神经网络在各个领域的火热应用,越来越多的学者试图从图论的角度对图神经网络的表达能力进行理论分析,并基于这些理论分析开发出了性能强大的模型。然而,在实际应用中,这些在理论上非常强大的模型的性能往往会受到计算复杂度等因素的限制。

本文作者 Michael Bronstein 是一名来 自帝国理工学院的教授,同时也是 Twitter 图机器学习项目组的负责人。在本文中,他深入浅出地介绍了近年来分析图神经网络表达能力的工作,并介绍了他们对于该领域未来发展方向的思考。

 

1图神经网络和 WL 图同构测试之间的关系

图神经网络的表达能力,究竟有多强大?

众所周知,传统的前馈神经网络(多层感知机)是一种通用函数近似器:它们能够以任意的准确率逼近任意的平滑函数。对于近期兴起的图神经网络来说,其表征性质还不太为人所知。在实验中,我们经常可以看到图神经网络在某些数据集上性能优异,但同时又在另一些数据集上表现令人失望。

为了探究造成这种现象的根本原因,我们不得不思考一个问题:图神经网络究竟有多强大?

在探究这一问题的过程中,我们所面临的一个挑战是:实际应用场景下使用的图往往是连续结构和离散结构(节点、边特征、连通性)的组合。因此,该问题可以被表述为不同的形式。一种可能的形式化定义是:图神经网络是否能够区分不同类型的图结构。在图论中,这是一种被称为「图同构问题」的经典问题,旨在判断两个图在拓扑意义上是否等价。两个同构的图拥有相同的连通性,其差别仅仅可能是节点的排列不同。

稍令人惊讶的是,我们尚不知晓精确的图同构问题的复杂度级别。该问题在多项式时间内不可解,它也不是一个 NP 完全(NPC)问题。有时,我们将其复杂度称为一种特殊的「GI 级」(GI class)。

 

1、Weisfeiler-Lehman 测试

Boris Weisfeiler 和 Andrey Lehman 于 1968 年发表的具有开创性意义的论文「The reduction of a graph to canonical form and the algebra which Appears therein 」),提出了一种高效的启发式算法,我们现在将其称为「WL 测试」。

最初,人们认为 WL 测试可以在多项式时间内求解图同构问题。但一年之后,人们就举出了一个反例。然而,从概率意义上说,似乎 WL 测试对于几乎所有的图都有效。

图神经网络的表达能力,究竟有多强大?

图 1:在两个同构图上执行 WL 测试的示例。包含弧线的 hash 圆括号代表多重集。在着色情况不再变化后算法会终止,并给出输出结果(颜色直方图)。若将两图输入给该算法得到的输出相同,则说明两图可能同构。

WL 测试是建立在迭代式的图重着色(图论中的「着色」指的是一种离散的节点标签)基础上的,在初始状态下,每个节点的颜色均不相同。在每一步迭代中,算法会聚合节点及其邻居节点的颜色,并将它们表征为多重集,然后将聚合得到的颜色多重集通过 Hash 函数映射到某种唯一的新颜色上。当达到稳定的着色状态(各节点着色状态不再变化)后,算法终止。当算法终止后,若两图的着色情况不同,则我们认为它们「非同构」。如果两图着色情况相同,它们可能(但并不一定)是同构的。换句话说,WL 测试是图同构的必要非充分条件。有一些非同构的图在接受 WL 测试后得到的着色情况也是相同的,而在这种情况下 WL 测试就失效了,因此我们只能认为它们「可能同构」。下图展示了其中的一种可能性:

图神经网络的表达能力,究竟有多强大?

图 2:显然,WL 图同构测试会为上面的两个非同构图生成相同的着色结果,此时 WL 测试失效。在化学领域中,这两个图分别代表两种不同的化合物「decalin」(左图)和「bicyclopentyl」(右图)的分子结构。

2、图同构网络(GIN)

Keyulu Xu 等人发表的论文「 How powerful are graph neural networks?」和 Christopher Morris 等人发表的论文,以及 Thomas 在他至少两年前撰写的博客「GRAPH CONVOLUTIONAL NETWORKS」,中注意到,WL 测试与图消息传递神经网络有惊人的相似之处,它们都在图上进行了一种类似于卷积的操作。

相关论文/文章链接:

https://arxiv.org/abs/1810.00826

https://tkipf.github.io/graph-convolutional-networks/

在一个消息传递层中,每个节点的特征会以聚合其邻居节点特征的方式被更新。对聚合和更新操作的选择是十分重要的:只有使用多重集的单射函数才能使其与 WL 算法等价。在前人的研究中,「取最最大值」或「取均值」等聚合操作都是一定弱于 WL 的能力,它们甚至不能区分非常简单的图结构:

图神经网络的表达能力,究竟有多强大?

图 3:通过「取最大值」操作无法区分左图、中图、右图,通过「取均值」聚合函数可以区分左图和中图、通过「取最大值」和「取均值」操作均无法区分左图和右图。这是因为通过这些方法从黑色节点的邻居中聚合而来的特征将会是相同的。

Xu 提出了一种聚合和更新函数的选择方案,它使得消息传递神经网络与 WL 算法等价,该网络被称为「图同构网络」(GIN)。该网络和标准的消息传递神经网络一样强大。但是,GIN 不仅仅是一种新的网络架构,其主要影响在于它通过一种简单的设定形式化定义了图神经网络表达能力的问题,这种设定与图论中的经典问题相关。该网络的思路也启发了许多后续的工作。

3、Weisfeiler-Lehman 层次结构

使用更加强大的图同构测试,是扩展 Xu 和 Morris 等人工作的一个方向。因此,László Babai 提出了 k-WL 测试,这是 WL 算法在高阶上的扩展,它在 k 元组上进行操作,而非操作单个节点。除了 1-WL 和 2-WL 测试是等价的,(k+1)-WL 始终严格强于 k-WL(k≥2),即对于某些图而言 k-WL 测试失效,而 (k+1)-WL 测试可以成功判定图是否同构,但反之则不然。因此,k-WL 是一种层次结构的或随着 k 的增大而逐渐更加强大的图同构测试,有时被称为「Weisfeiler-Lehman 层次结构」。

我们可以设计出遵循 k-WL 测试的图神经网络,这种网络是一定比消息传递架构更加强大的。Morris 等人在论文「 Weisfeiler and Leman go neural: Higher-order graph neural networks 」中提出了第一种这样的架构 k-GNN。

相关论文链接:

https://aaai.org/ojs/index.php/AAAI/article/view/4384/4262

传统的消息传递神经网络和这种高阶图神经网络之间最关键的区别在于:由于 k-WL 算法在节点的 k 元组上进行操作,所以这种高阶图神经网络是非局部的(non-local)。这对算法的实现及其计算复杂度和存储复杂度都有重要的影响:k-GNN 需要



Tags:神经网络   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
SimpleAI.人工智能、机器学习、深度学习还是遥不可及?来这里看看吧~ 从基本的概念、原理、公式,到用生动形象的例子去理解,到动手做实验去感知,到著名案例的学习,到用所学来实现...【详细内容】
2021-10-19  Tags: 神经网络  点击:(47)  评论:(0)  加入收藏
MNIST 这里就不多展开了,我们上几期的文章都是使用此数据集进行的分享。手写字母识别EMNIST数据集Extended MNIST (EMNIST), 因为 MNIST 被大家熟知,所以这里就推出了 EMNIST...【详细内容】
2021-09-08  Tags: 神经网络  点击:(182)  评论:(0)  加入收藏
理解什么是人工智能,以及机器学习和深度学习如何影响它,是一种不同凡响的体验。在 Mate Labs 我们有一群自学有成的工程师,希望本文能够分享一些学习的经验和捷径,帮助机器学习...【详细内容】
2021-06-09  Tags: 神经网络  点击:(128)  评论:(0)  加入收藏
资料来源:getwallpapers.com 深度学习是机器学习中重要分支之一。它的目的是教会计算机做那些对于人类来说相当自然的事情。深度学习也是无人驾驶汽车背后的一项关键性技术,...【详细内容】
2021-04-13  Tags: 神经网络  点击:(168)  评论:(0)  加入收藏
私有虚拟网络(VPN)是在公用网络基础之上建立的私有加密通信隧道网络,企业对于自管辖网络中个人使用VPN软件行为具有监管责任,但技术上却很难识别VPN的加密与通信方式,因此利用人工智能(AI)领域的神经网络技术从网络流量中识...【详细内容】
2021-01-07  Tags: 神经网络  点击:(193)  评论:(0)  加入收藏
深层神经网络的模型概括,过度拟合和正则化方法的挑战> Source 在完成了与神经网络有关的多个AI项目之后,我意识到模型的概括能力对于AI项目的成功至关重要。 我想写这篇文章来...【详细内容】
2020-10-30  Tags: 神经网络  点击:(101)  评论:(0)  加入收藏
本文最初发表于 Towards Data Science 博客,经原作者 Andre Ye 授权,InfoQ 中文站翻译并分享。卷积神经网络(Convolutional Nerual Network,CNN)构成了图像识别的基础,这无疑是深...【详细内容】
2020-10-16  Tags: 神经网络  点击:(115)  评论:(0)  加入收藏
本报告讨论了非常厉害模型优化技术 —— 知识蒸馏,并给大家过了一遍相关的TensorFlow的代码。...【详细内容】
2020-09-25  Tags: 神经网络  点击:(92)  评论:(0)  加入收藏
算法算法从1950年代的早期研究开始,机器学习的所有工作似乎都随着神经网络的创建而积累起来。 从逻辑回归到支持向量机,相继提出了新算法之后的算法,但是从字面上看,神经网络是...【详细内容】
2020-09-17  Tags: 神经网络  点击:(90)  评论:(0)  加入收藏
卷积神经网络(CNN)广泛应用于深度学习和计算机视觉算法中。虽然很多基于CNN的算法符合行业标准,可以嵌入到商业产品中,但是标准的CNN算法仍然有局限性,在很多方面还可以改进。这篇文章讨论了语义分割和编码器-解码器架构...【详细内容】
2020-09-17  Tags: 神经网络  点击:(93)  评论:(0)  加入收藏
▌简易百科推荐
作为数据科学家或机器学习从业者,将可解释性集成到机器学习模型中可以帮助决策者和其他利益相关者有更多的可见性并可以让他们理解模型输出决策的解释。在本文中,我将介绍两个...【详细内容】
2021-12-17  deephub    Tags:AI   点击:(15)  评论:(0)  加入收藏
基于算法的业务或者说AI的应用在这几年发展得很快。但是,在实际应用的场景中,我们经常会遇到一些非常奇怪的偏差现象。例如,Facebook将黑人标记为灵长类动物、城市图像识别系统...【详细内容】
2021-11-08  数据学习DataLearner    Tags:机器学习   点击:(32)  评论:(0)  加入收藏
11月2日召开的世界顶尖科学家数字未来论坛上,2013年诺贝尔化学奖得主迈克尔·莱维特、2014年诺贝尔生理学或医学奖得主爱德华·莫索尔、2007年图灵奖得主约瑟夫·斯发斯基、1986年图灵奖得主约翰·霍普克罗夫特、2002...【详细内容】
2021-11-03  张淑贤  证券时报  Tags:人工智能   点击:(39)  评论:(0)  加入收藏
鉴于物联网设备广泛部署、5G快速无线技术闪亮登场,把计算、存储和分析放在靠近数据生成的地方来处理,让边缘计算有了用武之地。 边缘计算正在改变全球数百万个设备处理和传输...【详细内容】
2021-10-26    计算机世界  Tags:边缘计算   点击:(45)  评论:(0)  加入收藏
这是几位机器学习权威专家汇总的725个机器学习术语表,非常全面了,值得收藏! 英文术语 中文翻译 0-1 Loss Function 0-1损失函数 Accept-Reject Samplin...【详细内容】
2021-10-21  Python部落    Tags:机器学习   点击:(43)  评论:(0)  加入收藏
要开始为开源项目做贡献,有一些先决条件:1. 学习一门编程语言:由于在开源贡献中你需要编写代码才能参与开发,你需要学习任意一门编程语言。根据项目的需要,在后期学习另一种语言...【详细内容】
2021-10-20  TSINGSEE青犀视频    Tags:机器学习   点击:(37)  评论:(0)  加入收藏
SimpleAI.人工智能、机器学习、深度学习还是遥不可及?来这里看看吧~ 从基本的概念、原理、公式,到用生动形象的例子去理解,到动手做实验去感知,到著名案例的学习,到用所学来实现...【详细内容】
2021-10-19  憨昊昊    Tags:神经网络   点击:(47)  评论:(0)  加入收藏
语言是人类思维的基础,当计算机具备了处理自然语言的能力,才具有真正智能的想象。自然语言处理(Natural Language Processing, NLP)作为人工智能(Artificial Intelligence, AI)的核心技术之一,是用计算机来处理、理解以及运...【详细内容】
2021-10-11    36氪  Tags:NLP   点击:(48)  评论:(0)  加入收藏
边缘计算是什么?近年来,物联网设备数量呈线性增长趋势。根据艾瑞测算, 2020年,中国物联网设备的数量达74亿,预计2025年突破150亿个。同时,设备本身也变得越来越智能化,AI与互联网在...【详细内容】
2021-09-22  汉智兴科技    Tags:   点击:(54)  评论:(0)  加入收藏
说起人工智能,大家总把它和科幻电影中的机器人联系起来,而实际上这些科幻场景与现如今的人工智能没什么太大关系。人工智能确实跟人类大脑很相似,但它们的显著差异在于人工智能...【详细内容】
2021-09-17  异步社区    Tags:人工智能   点击:(57)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条