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

成为VIP会员查看完整内容
28

相关内容

图神经网络 (GNN) 是一种连接模型,它通过图的节点之间的消息传递来捕捉图的依赖关系。与标准神经网络不同的是,图神经网络保留了一种状态,可以表示来自其邻域的具有任意深度的信息。近年来,图神经网络(GNN)在社交网络、知识图、推荐系统、问答系统甚至生命科学等各个领域得到了越来越广泛的应用。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等
【ICML2020】持续图神经网络,Continuous Graph Neural Networks
专知会员服务
145+阅读 · 2020年6月28日
【IJCAI2020】图神经网络预测结构化实体交互
专知会员服务
42+阅读 · 2020年5月13日
注意力图神经网络的多标签文本分类
专知会员服务
111+阅读 · 2020年3月28日
图神经网络表达能力的研究综述,41页pdf
专知会员服务
167+阅读 · 2020年3月10日
赛尔笔记 | 一文读懂图神经网络
哈工大SCIR
81+阅读 · 2019年7月12日
图神经网络综述:方法及应用 | Deep Reading
AI100
34+阅读 · 2019年3月17日
SepNE: Bringing Separability to Network Embedding
Arxiv
3+阅读 · 2019年2月26日
Arxiv
5+阅读 · 2018年4月22日
VIP会员
微信扫码咨询专知VIP会员