剖析图神经网络的表达能力和Weisfeiler-Lehman检验

转载 2020-07-16 10:51  阅读 56 次 评论 0 条

你是否觉得在图上进行深度学习是一堆有时可以起作用的启发式方法,但是没人知道为什么吗?在本文中,我将讨论图同构问题,用于图同构测试的Weisfeiler-Lehman启发式方法,以及如何将其用于分析图神经网络的表达能力。

剖析图神经网络的表达能力和Weisfeiler-Lehman检验

传统前馈网络(多层感知器)是通用近似器:它们可以将任何平滑函数近似为任何所需的精度。对于最近出现的图神经网络,人们对表示特性的了解较少。在实验中经常会发现,图神经网络在某些数据集上表现出色,而在其他数据集上却表现令人失望。为了了解这种行为的根源,必须回答一个问题:图神经网络的功能有多强大?

挑战之一是,应用程序中遇到的图形是连续和离散结构(分别是节点和边缘特征以及连通性)的组合,因此可以用不同的方式提出这个问题。一种可能的表述是图神经网络是否可以区分不同类型的图结构。这是图论中的经典问题,称为图同构问题,旨在确定两个图在拓扑上是否等效。两个同构图具有相同的连通性,并且仅因其节点的排列而不同。

令人惊讶的是,图同构问题的确切复杂度类别是未知的。不知道它在多项式时间内是可解的,也不是NP完全的,有时归因于特殊的“ GI类”。

Weisfeiler-Lehman检验。

1968年Boris Weisfeiler和 Andrey Lehman的开创性论文提出了一种有效的启发式方法,现在称为Weisfeiler-Lehman(WL)测试,最初被认为是图同构问题的多项式时间解。一年后发现了一个反例;但是,从概率的角度来看,WL测试似乎适用于几乎所有图形。

剖析图神经网络的表达能力和Weisfeiler-Lehman检验

在两个同构图上执行Weisfeiler-Lehman检验的示例。弯括号表示多组。着色不变后,算法停止并产生输出(颜色的直方图)。两个图的相等输出表明它们可能是同构的。

WL测试基于迭代图形重新着色(图形理论中的"颜色"是指离散的节点标签),并从所有颜色相同的节点开始。在每个步骤中,该算法将节点及其邻域的颜色汇总为多集,并将汇总的颜色多集散列为唯一的新颜色。该算法在达到稳定的着色时停止。如果此时两个图的颜色不同,则认为这些图是非同构的。但是,如果颜色相同,则这些图可能(但不一定)是同构的。

换句话说,WL测试是图同构的必要但不充分的条件。

存在一些非同构图,其中WL测试会产生相同的着色,因此将它们视为"可能同构"。据说在这种情况下测试失败。下图显示了一个这样的示例:

剖析图神经网络的表达能力和Weisfeiler-Lehman检验

从其产生的相同颜色可以明显看出,两个WL图同构测试失败的非同构图。在化学上,这些图代表两种不同化合物的分子结构,十氢化萘(左)和双环戊基(右)。

图同构网络

Keyulu Xu 和Christopher Morris 注意到 WL测试与通过神经网络的图消息传递图形非常相似,这是进行卷积的一种方法。

就像对图形的操作一样。在消息传递层中,通过汇总邻居的特征来更新每个节点的特征。聚合和更新操作的选择至关重要:只有多集内射函数使其等效于WL算法。有些文献中使用的一些流行的聚合器选择(例如,最大值或均值)实际上不如WL强大,并且无法区分非常简单的图结构:

剖析图神经网络的表达能力和Weisfeiler-Lehman检验

无法通过最大值进行区分但可以通过均值聚合器(第一和第二)进行区分,以及既不能通过最大值,也不能通过均值(第一和第三)进行区分的图结构示例。原因是从黑节点的邻居以这种方式聚合的特征将是相同的。

Keyulu Xu提出了一种聚合和更新特征的选择,这些特征使消息传递神经网络等效于WL算法,将它们称为图同构网络(GIN)。这与标准的消息传递神经网络所具有的功能一样强大。

但是,不仅仅是一种新的体系结构,主要的影响是在一个简单的环境中提出了表达性问题,这可能与图论中的经典问题有关。这个想法已经激发了许多后续工作。

Weisfeiler-Lehman层次结构

扩展Xu和Morris结果的一个方向是使用更强大的图形同构测试。由LászlóBabai提出的k-WL检验是Weisfeiler-Lehman算法的高阶扩展,该算法适用于k个元组而不是单个节点。

与1-WL和2-WL测试,是等效的,除外(k+1)-WL比k-WL更严格更强,对于任何k ≥2,即存在着在其上的图形的例子k -WL失败,但(k +1)-WL成功,反之亦然。因此,k-WL是一个层次结构或特征越来越强大的图同构测试,有时也称为Weisfeiler-Lehman层次结构。

可以设计遵循k -WL测试的图神经网络,因此比消息传递体系结构更强大。Morris提出了一个这样的第一个架构,k -GNN。通过神经网络和诸如高阶GNNS传统消息之间的主要差异是,它们是非本地,作为k -WL算法上操作k节点的元组。这对算法的实现及其计算和内存复杂性都具有重大影响:k -GNN需要(nᵏ)个内存。为了减少复杂性,Morris设计了k-GNN的局部版本,基于局部邻域的聚合,但是其表达能力不如k -WL。

Haggai Maron提出了一些不同的高阶图体系结构。我于2019年9月参加了会议。Maron 基于k阶张量定义了一类不变图网络(IGN),并显示出它们与k -WL 一样强大。IGNs从一个不同的变体衍生k -WL ,并且在与它们的复杂性方面更有利k -GNNs。尤其是,等效于3-WL的IGN具有"仅"二次复杂度,这可能是唯一实际上比消息传递更强大的,实用的图神经网络架构,但与前者的线性复杂度相去甚远。

从理论上讲,可证明强大的图神经网络的工作提供了严格的数学框架,可以帮助解释和比较不同的算法。有许多后续工作使用图论和分布式局部算法的方法扩展了这些结果。

但是,从实际的角度来看,这些新架构几乎没有产生重大影响:例如,最新的基准测试表明,最近可证明强大的算法实际上不及旧技术。在机器学习中,这并不是一种罕见的情况,在理论和实践之间通常存在很大的差距。一种解释可能是基准本身的不足。但是,也许更深刻的原因是,更好的表现力并不一定能提供更好的概括性(有时恰恰相反),此外,图同构模型可能无法正确捕捉特定应用中图相似性的实际概念。

可以肯定的是,这一系列工作对于建立与其他学科的桥梁以及将以前在深度学习领域中未使用的方法引入图上而言是非常富有成果的。

本文地址:http://51blog.com/?p=11033
关注我们:请关注一下我们的微信公众号:扫描二维码广东高校数据家园_51博客的公众号,公众号:数博联盟
温馨提示:文章内容系作者个人观点,不代表广东高校数据家园_51博客对观点赞同或支持。
版权声明:本文为转载文章,来源于 AI火箭营 ,版权归原作者所有,欢迎分享本文,转载请保留出处!

发表评论


表情