【MIT-ICML2020】图神经网络的泛化与表示的局限

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