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


图神经网络火?谈论其普遍性和局限性

来自arXiv

作者:Andreas Loukas

机器的核心编译

参与:韩芳,张倩

图神经网络(GNN)是一种基于深度学习的地图域信息处理方法。由于其良好的性能和可解释性,GNN已成为一种广泛使用的图形分析方法。然而,即使最好的方法也有一定的局限性。来自洛桑联邦理工学院的研究人员发表了一篇关于arXiv的论文,指出了图神经网络在消息传递分布式系统中的普遍性和局限性。

本文得出两个重要结论:

1. GNN在足够的深度,宽度,节点独立性和层表达下具有图灵性;

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

841fab6928f746b98c11f409145d730c.jpeg

为什么要研究GNN的局限性

机器学习的一个基本问题是确定模型能够学习什么,不能学习什么。在深度学习中,许多研究工作取得了积极成果。例如,众所周知,具有足够深度和宽度的前馈神经网络可以近似任何一般函数。

最近,我们已经看到了研究图神经网络普遍性的第一个结果,它使用图形作为输入。对于层为线性且输入排列相同的深层网络,Maron等。推导出不变函数的一般近似定理。 Keriven和Peyr'E也证明了等变函数的普遍性,尽管这次它是在一个特定的浅层架构下。延伸到深层,徐等人。还证明了由图像和聚合器组成的单图像神经网络层的普遍性,后来由Seo等人进行了扩展。这些研究探讨了GNN模型可以从功能层面学到什么,即GNN的普遍性。

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

但是,通过研究模型的局限性,通常更容易深入了解模型。毕竟,有关网络无法学习的特定功能的知识与应用时的培训过程无关。此外,通过帮助我们理解与模型相关的任务的难度,不可能性结果有助于提出关于如何选择模型超参数的实用建议。

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

本文的两个主要结论

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

具体来说,本文主要得出两个主要结论。

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

件,GNN被证明是图灵的普遍性:(i)有足够的层次; (ii)各层的宽度足够; (iii)节点是相互独立的; (iv)每层计算函数都具有足够的表达能力。

在什么情况下GNN学习能力会下降

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

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

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

验证给定的G子图是否已连接,是否包含循环,是否为生成树,是否为二进制,是否为简单路径,是否对应G的切割或哈密顿环;

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

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

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

表1:主要结果摘要。

f0edf49e17e74073a9ff1f3878c87088.png

图1:显示下限的图例。

11: 42

来源:同步机器的心脏

图神经网络火?谈论其普遍性和局限性

来自arXiv

作者:Andreas Loukas

机器的核心编译

参与:韩芳,张倩

图神经网络(GNN)是一种基于深度学习的地图域信息处理方法。由于其良好的性能和可解释性,GNN已成为一种广泛使用的图形分析方法。然而,即使最好的方法也有一定的局限性。来自洛桑联邦理工学院的研究人员发表了一篇关于arXiv的论文,指出了图神经网络在消息传递分布式系统中的普遍性和局限性。

本文得出两个重要结论:

1. GNN在足够的深度,宽度,节点独立性和层表达下具有图灵性;

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

841fab6928f746b98c11f409145d730c.jpeg

为什么要研究GNN的局限性

机器学习的一个基本问题是确定模型能够学习什么,不能学习什么。在深度学习中,许多研究工作取得了积极成果。例如,众所周知,具有足够深度和宽度的前馈神经网络可以近似任何一般函数。

最近,我们已经看到了研究图神经网络普遍性的第一个结果,它使用图形作为输入。对于层为线性且输入排列相同的深层网络,Maron等。推导出不变函数的一般近似定理。 Keriven和Peyr'E也证明了等变函数的普遍性,尽管这次它是在一个特定的浅层架构下。延伸到深层,徐等人。还证明了由图像和聚合器组成的单图像神经网络层的普遍性,后来由Seo等人进行了扩展。这些研究探讨了GNN模型可以从功能层面学到什么,即GNN的普遍性。

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

但是,通过研究模型的局限性,通常更容易深入了解模型。毕竟,有关网络无法学习的特定功能的知识与应用时的培训过程无关。此外,通过帮助我们理解与模型相关的任务的难度,不可能性结果有助于提出关于如何选择模型超参数的实用建议。

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

本文的两个主要结论

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

具体来说,本文主要得出两个主要结论。

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

件,GNN被证明是图灵的普遍性:(i)有足够的层次; (ii)各层的宽度足够; (iii)节点是相互独立的; (iv)每层计算函数都具有足够的表达能力。

在什么情况下GNN学习能力会下降

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

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

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

验证给定的G子图是否已连接,是否包含循环,是否为生成树,是否为二进制,是否为简单路径,是否对应G的切割或哈密顿环;

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

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

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

表1:主要结果摘要。

f0edf49e17e74073a9ff1f3878c87088.png

图1:显示下限的图例。

只提供信息存储空间服务。

神经

网络

功能

模型

下界

阅读()

投诉