【麻省理工学院MIT】图神经网络的泛化与表示极限，Generalization Representation limit GNN- 专知

【麻省理工学院MIT】图神经网络的泛化与表示极限，Generalization Representation limit GNN

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

地址：

https://arxiv.xilesou.top/abs/2002.06157