图神经网络火了?谈下它的普适性与局限性

图神经网络(GNN)是一类基于深度学习的图域信息处理方法。由于具有较好的性能和可解释性,GNN 已成为一种广泛应用的图分析方法。然而,再好的方法都存在一定的局限。来自洛桑联邦理工学院的研究者在 arXiv 上发表了一篇论文,指出了图神经网络在消息传递分布式系统中的图灵普适性和局限性。

本文得出了两个重要结论:

1. 在足够的深度、宽度、节点独立性和层表达条件下,GNN 是图灵普适(Turing universal)的;

2. 当 GNN 的深度和宽度受到限制时,它们的能力会大大降低。

为什么要研究 GNN 的局限性

机器学习中的一个基本问题是确定模型可以学习和不能学习的内容。在深度学习中,大量的研究工作都取得了正面的结果。例如,众所周知,具有足够深度和宽度的前馈神经网络可以逼近任何通用函数 。

最近,我们看到了研究图神经网络普适性的第一批结果,这些神经网络以图作为输入。针对层是线性的且输入排列是等变的深层网络,Maron 等人得出了一个不变量函数的通用近似定理。Keriven 和 Peyr'E也证明了等变函数的普适性,尽管这一次是在一个特定的浅层体系结构下。扩展到深集,Xu 等人还证明了由和聚集器组成的单图神经网络层的普适性,该结果后来由 Seo 等人扩展。这些研究从函数层面探究了 GNN 模型能学到什么,即 GNN 的普适性。

研究 GNN 的普适性使我们能够在有限的范围内把握模型的能力。理论上,只要有足够的数据和正确的学习算法,一个普适的网络就可以解决它所面临的任何任务。然而,这些结果带来的洞察也可能是有限的。知道一个足够大的网络可以用来解决任何问题,并不能在实践中指导神经网络设计。当然也不能保证该网络能够在给定的学习算法(如随机梯度下降)下解决给定的任务。

然而,通过研究模型的局限性通常更容易获得对模型的洞察。毕竟,网络所不能学到的关于特定特征的知识在应用时独立于训练过程。此外,通过帮助我们理解与模型相关的任务的难度,不可能性结果(impossibility result)有助于得出关于如何选择模型超参数的实用建议。

以图分类问题为例。训练一个图分类器需要识别是什么构成了一个类,即在同一个类而非其他类中找到图共享的属性,然后决定新的图是否遵守所学习到的属性。然而,如果可以通过一定深度的图神经网络(且测试集足够多样化)证明上述决策问题是不可能的,那么我们可以确定,同一个网络将不会学习如何正确地对测试集进行分类,这与使用了什么学习算法无关。因此,在进行实验时,我们应该把重点放在比下限更深的网络上。

本文两大结论

本文研究了图神经网络的计算能力局限。作者没有聚焦于特定的架构,这里所考虑的网络属于消息传递框架的范畴。选择该模型是因为它足够通用,能够涵盖几个最先进的网络,包括 GCN、Chebynet、门控图神经网络、分子指纹、相互作用网络、分子图卷积等。本文提出的不可能性陈述(impossibility statement)源于一种新的技术,它能使理论计算机科学的成果重新定位。这将引出涉及图的一系列决策、优化和估计问题的下界。值得注意的是,这些问题中的一些被认为是不可能的,除非 GNN 的深度和宽度的乘积超过了图的大小;即使对于看起来很简单的任务或在考虑近似值时,这种依赖性仍然很强。

具体来讲,本文主要得出了两大结论。

GAN 在什么情况下具有图灵普适性

如果满足一定的条件,GNN 就可以在其输入上计算任何可由图灵机计算的函数。这个结果不同于最近的普适性结果,后者考虑了在特定的函数类(不变和等变)和特定的体系结构上的近似(而不是可计算性)。这一主张遵循一种直接的方式,即建立 GNN 与 LOCAL的图灵等价,这是分布式计算中的一个经典模型,本身就是图灵通用模型。简而言之,如果满足以下四个强条件,GNN 就被证明是图灵普适的:(i)有足够的层;(ii)所述层有足够的宽度;(iii)节点之间互相独立;(iv)每层计算的函数具有足够的表现力。

哪些情况下 GNN 学习能力会下降

为了了解更多,作者研究了对不使用读出函数的 GNN 的深度 d 和宽度 w 进行限制的含义。具体来说,当乘积 dw 受到限制时,GNN 的能力会大打折扣。该分析依赖于一个新的引理,该引理能够将不可能性结果从 LOCAL 转换到 GNN。这种方法的主要好处是,它允许我们重新使用从理论计算机科学到图神经网络设置的几个重要下界。

设 G 为神经网络的输入。本文给出了以下问题的下界:

  • 检测 G 是否包含特定长度的循环;

  • 验证给定的 G 子图是否连接,是否包含循环,是否为生成树,是否为二分体,是否为一条简单的路径,是否对应于 G 的割或哈密顿循环;

  • 近似两个顶点之间的最短路径,最小割和最小生成树

  • 找到最大独立集、最小顶点覆盖或 G 的着色;

  • 计算或近似 G 的直径和周长;

表 1:主要结果总结。

图 1:给出下界的图例。


论文链接:https://arxiv.org/abs/1907.03199


理论深度学习其他智能领域局限性论文图神经网络
3
相关数据
哈密顿人物

William Rowan Hamilton爵士MRIA(1805年8月4日 - 1865年9月2日)是一位爱尔兰数学家,他为经典力学、光学和代数做出了重要贡献。 虽然哈密顿不是物理学家(他认为自己是一个纯粹的数学家)他的工作对物理学起着至关重要的作用,特别是他对牛顿力学的重新定义,现在称为哈密顿力学。 这项工作已被证明是对电磁学等经典场论的现代研究以及量子力学发展的核心。 在纯数学中,他最出名的是四元数的发明者。

最小生成树技术

最小生成树是一副连通加权无向图中一棵权值最小的生成树。一个连通图可能有多个生成树。当图中的边具有权值时,总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言,对于非连通无向图来说,它的每一连通分量同样有最小生成树。以有线电视电缆的架设为例,若只能沿着街道布线,则以街道为边,而路口为顶点,其中必然有一最小生成树能使布线成本最低。简单点说有几个城市你要设计一个路线,这个路线能走完所有的这几个城市,而且路程最短,这个路线就会是最小生成树。

超参数技术

在机器学习中,超参数是在学习过程开始之前设置其值的参数。 相反,其他参数的值是通过训练得出的。 不同的模型训练算法需要不同的超参数,一些简单的算法(如普通最小二乘回归)不需要。 给定这些超参数,训练算法从数据中学习参数。相同种类的机器学习模型可能需要不同的超参数来适应不同的数据模式,并且必须对其进行调整以便模型能够最优地解决机器学习问题。 在实际应用中一般需要对超参数进行优化,以找到一个超参数元组(tuple),由这些超参数元组形成一个最优化模型,该模型可以将在给定的独立数据上预定义的损失函数最小化。

图灵机技术

图灵机,又称确定型图灵机,是英国数学家艾伦·图灵于1936年提出的一种抽象计算模型,其更抽象的意义为一种数学逻辑机,可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。

随机梯度下降技术

梯度下降(Gradient Descent)是遵循成本函数的梯度来最小化一个函数的过程。这个过程涉及到对成本形式以及其衍生形式的认知,使得我们可以从已知的给定点朝既定方向移动。比如向下朝最小值移动。 在机器学习中,我们可以利用随机梯度下降的方法来最小化训练模型中的误差,即每次迭代时完成一次评估和更新。 这种优化算法的工作原理是模型每看到一个训练实例,就对其作出预测,并重复迭代该过程到一定的次数。这个流程可以用于找出能导致训练数据最小误差的模型的系数。

生成树技术

在图论的数学领域中,如果连通图 G的一个子图是一棵包含G 的所有顶点的树,则该子图称为G的生成树(SpanningTree)。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历,可以得到不同的生成树。

分类问题技术

分类问题是数据挖掘处理的一个重要组成部分,在机器学习领域,分类问题通常被认为属于监督式学习(supervised learning),也就是说,分类问题的目标是根据已知样本的某些特征,判断一个新的样本属于哪种已知的样本类。根据类别的数量还可以进一步将分类问题划分为二元分类(binary classification)和多元分类(multiclass classification)。

前馈神经网络技术

前馈神经网络(FNN)是人工智能领域中最早发明的简单人工神经网络类型。在它内部,参数从输入层经过隐含层向输出层单向传播。与递归神经网络不同,在它内部不会构成有向环。FNN由一个输入层、一个(浅层网络)或多个(深层网络,因此叫作深度学习)隐藏层,和一个输出层构成。每个层(除输出层以外)与下一层连接。这种连接是 FNN 架构的关键,具有两个主要特征:加权平均值和激活函数。

图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构,它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图,并通过在整张图上传递、转换和聚合节点特征信息,从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入,并用于节点分类或预测节点之间的连接,完整的模型可以通过端到端的方式训练。

推荐文章
暂无评论
暂无评论~