【PUC-牛津-ICLR2020】图神经网络的逻辑表达性，The Logical Expressiveness of GNN

The Logical Expressiveness of Graph Neural Networks

https://openreview.net/forum?id=r1lZ7AEKvB

这也是一篇满分的工作。是由常年战斗在图领域的大佬 Pablo Barceló 团队贡献的。图神经网络（GNN）区分图节点的能力最近已经通过用于检查图同构性的 Weisfeiler-Lehman（WL）测试进行了表征。但是，这种表征并不能解决哪些布尔节点分类器可以由 GNN 来表示 （即，将图中的节点分类为真或假的函数）的问题。这篇文章专注于研究布尔分类器来解决上述问题。首先研究的是流行的GNNs（文中称为 AC-GNNs）开始，在该类 GNN 中仅根据邻居的特征，在连续的层中更新图中每个节点的特征。实验表明，这类 GNN 太弱而无法捕获所有 FOC2（一种一阶逻辑研究） 分类器，并提供了 AC-GNNs 可以捕获的 FOC2 分类器最大子类的语法表征。然后，研究人员研究了，需要在 AC-GNNs 中添加什么来实现捕获所有的 FOC2 分类器，实验表明，添加 readout 就可以了。不仅可以更新节点的邻居，还可以更新全局属性向量。文章称这类 GNNs 为 ACR-GNNs。

专知便捷查看

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

• 后台回复“GNNLE” 就可以获取《【PUC-牛津-ICLR2020】图神经网络的逻辑表达性，The Logical Expressiveness of GNN》专知下载链接

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

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

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