【MIT】图神经网络的泛化与表示极限，《Generalization and Representational Limits of Graph Neural Networks》

题目

图神经网络的泛化与表示极限，《Generalization and Representational Limits of Graph Neural Networks》

关键字

图神经网络，泛化与表示，深度学习，人工智能，图论

简介

我们讨论了图神经网络的两个基本问题。首先，我们证明了几个重要的图属性不能由完全依赖于局部信息的GNNs来计算。这些gnn包括标准的消息传递模型，以及更强大的空间变体，它们利用局部图结构(例如，通过消息的相对方向或本地端口排序)来区分每个节点的邻居。我们的研究包括一种新的图论形式。其次，我们为消息传递GNNs提供了第一个数据相关泛化界限。该分析明确地解释了GNNs的局部排列不变性。我们的界限比现有的基于vc维的GNNs保证要严格得多，并且可与递归神经网络的Rademacher界限相媲美。

作者

Vikas K. Garg, Stefanie Jegelka, Tommi Jaakkola