题目: Logical Expressiveness of Graph Neural Networks

摘要:

图神经网络(Graph Neural Networks, GNNs)是近年来在分子分类、知识图谱补全等结构化数据处理领域中流行起来的一类机器学习体系结构。最近关于GNNs表达能力的研究已经建立了它们对图中节点进行分类的能力与用于检查图同构的WeisfeilerLehman (WL)测试之间的紧密联系。具体来说,这两篇论文的作者分别观察到,WL测试产生的节点分类总是细化了任何GNN产生的分类,而且有GNN可以重现WL测试。这些结果表明,GNNs在节点分类方面与WL测试一样强大。然而,这并不意味着GNNs可以表达任何通过WL测试改进的分类器。我们的工作旨在回答以下问题:什么是可以用GNNs捕获的节点分类器?在本文中,我们从逻辑的角度来看待这个问题,将其限制在FOC2中可表达的属性上,即具有计数能力的一阶逻辑的两变量片段进行研究。

作者:

Pablo Barceló是智利天主教大学工程学院和数学学院数学与计算工程研究所所长,研究领域为数据库理论、计算机科学中的逻辑、自动机理论。

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

相关内容

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

知识荟萃

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

更多

查看相关VIP内容、论文、资讯等
【ICML2020】持续图神经网络,Continuous Graph Neural Networks
专知会员服务
146+阅读 · 2020年6月28日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
153+阅读 · 2020年5月26日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
论文浅尝 | GMNN: Graph Markov Neural Networks
开放知识图谱
20+阅读 · 2020年2月14日
重新思考图卷积网络:GNN只是一种滤波器
新智元
28+阅读 · 2019年6月3日
基于注意力机制的图卷积网络
科技创新与创业
73+阅读 · 2017年11月8日
Arxiv
9+阅读 · 2020年2月15日
Signed Graph Attention Networks
Arxiv
7+阅读 · 2019年9月5日
Position-aware Graph Neural Networks
Arxiv
15+阅读 · 2019年6月11日
Arxiv
23+阅读 · 2018年10月1日
Arxiv
26+阅读 · 2018年2月27日
VIP会员
相关资讯
相关论文
微信扫码咨询专知VIP会员