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

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

https://arxiv.org/abs/2002.06157

专知便捷查看

便捷下载，请关注专知公众号（点击上方蓝色专知关注）

• 后台回复“GRLGNN” 可以获取《图神经网络的泛化与表示的局限》专知下载链接索引

专知，专业可信的人工智能知识分发，让认知协作更快更好！欢迎注册登录专知www.zhuanzhi.ai，获取5000+AI主题干货知识资料！

欢迎微信扫一扫加入专知人工智能知识星球群，获取最新AI专业干货知识教程资料和与专家交流咨询！

点击“阅读原文”，了解使用专知，查看获取5000+AI主题知识资源