本文发表于ICML 2020。本文讨论关于图神经网络的两个基本问题。首先，本文证明了几个重要的图属性是不能由完全依赖于局部信息的GNN计算的。这样的GNN包括标准的消息传递模型，以及更强大的空间变体，利用本地图结构来区分每个节点的邻居。本文的处理包括一种新的图论形式主义。其次，本文为消息传递GNN提供了第一个依赖数据的泛化边界。该分析明确地说明了GNN的局部置换不变性。本文的边界比现有的基于VC维的GNN保证更紧，并且可与递归神经网络的Rademacher边界相媲美。

内容中包含的图片若涉及版权问题，请及时与我们联系删除