由于消息传递—图神经网络(MPNN)应用在稀疏图时相对于节点数量具有线性复杂性,因此它们已被广泛使用, 不过它们的理论表达能力bounded by一阶 Weisfeiler-Lehman 检验 (1-WL)。

在本文中,我们表明,如果自定义特征值相关的非线性函数设计图卷积supports并使用任意大的感受野进行掩蔽,则 MPNN 在理论上比 1-WL 测试更强大。实验表明该方法与3-WL 同样强大,同时能够保持空间局部化(spatially localized)。此外,通过设计自定义滤波器函数,输出可以具有各种频率分量,从而允许卷积过程学习给定输入图信号与其相关属性的不同关系。

目前,最好的 3-WL 等效图神经网络的计算复杂度为 O(n^3 ),内存使用量为 O(n^2 ),考虑非局部更新机制,并且不提供输出的频谱。但是本文所提出的方法克服了所有上述问题,并在许多下游任务中达到了最先进的结果。

http://honeine.fr/paul/publi/21.icml.gnn.pdf

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

相关内容

专知会员服务
36+阅读 · 2021年7月17日
专知会员服务
16+阅读 · 2021年7月13日
专知会员服务
52+阅读 · 2021年6月14日
专知会员服务
29+阅读 · 2021年5月21日
专知会员服务
50+阅读 · 2021年5月19日
专知会员服务
81+阅读 · 2021年5月10日
专知会员服务
37+阅读 · 2020年11月24日
专知会员服务
28+阅读 · 2020年8月8日
【KDD2020】图神经网络生成式预训练
专知
22+阅读 · 2020年7月3日
【GNN】MPNN:消息传递神经网络
深度学习自然语言处理
17+阅读 · 2020年4月11日
基于 GNN 的图表示学习
DataFunTalk
9+阅读 · 2020年1月17日
图注意力网络
科技创新与创业
35+阅读 · 2017年11月22日
Arxiv
0+阅读 · 2021年7月29日
Arxiv
8+阅读 · 2021年2月19日
Heterogeneous Graph Transformer
Arxiv
27+阅读 · 2020年3月3日
Arxiv
15+阅读 · 2020年2月5日
Arxiv
10+阅读 · 2018年2月4日
Arxiv
4+阅读 · 2015年8月25日
VIP会员
相关主题
相关VIP内容
专知会员服务
36+阅读 · 2021年7月17日
专知会员服务
16+阅读 · 2021年7月13日
专知会员服务
52+阅读 · 2021年6月14日
专知会员服务
29+阅读 · 2021年5月21日
专知会员服务
50+阅读 · 2021年5月19日
专知会员服务
81+阅读 · 2021年5月10日
专知会员服务
37+阅读 · 2020年11月24日
专知会员服务
28+阅读 · 2020年8月8日
相关资讯
【KDD2020】图神经网络生成式预训练
专知
22+阅读 · 2020年7月3日
【GNN】MPNN:消息传递神经网络
深度学习自然语言处理
17+阅读 · 2020年4月11日
基于 GNN 的图表示学习
DataFunTalk
9+阅读 · 2020年1月17日
图注意力网络
科技创新与创业
35+阅读 · 2017年11月22日
相关论文
Arxiv
0+阅读 · 2021年7月29日
Arxiv
8+阅读 · 2021年2月19日
Heterogeneous Graph Transformer
Arxiv
27+阅读 · 2020年3月3日
Arxiv
15+阅读 · 2020年2月5日
Arxiv
10+阅读 · 2018年2月4日
Arxiv
4+阅读 · 2015年8月25日
微信扫码咨询专知VIP会员