We study the convergence of message passing graph neural networks on random graph models to their continuous counterpart as the number of nodes tends to infinity. Until now, this convergence was only known for architectures with aggregation functions in the form of degree-normalized means. We extend such results to a very large class of aggregation functions, that encompasses all classically used message passing graph neural networks, such as attention-based mesage passing or max convolutional message passing on top of (degree-normalized) convolutional message passing. Under mild assumptions, we give non asymptotic bounds with high probability to quantify this convergence. Our main result is based on the McDiarmid inequality. Interestingly, we treat the case where the aggregation is a coordinate-wise maximum separately, at it necessitates a very different proof technique and yields a qualitatively different convergence rate.


翻译:普通聚合下具有消息传递图神经网络在大型随机图上的收敛 翻译后的摘要: 我们研究了具有消息传递图神经网络在随机图模型上的收敛性,当节点数趋近于无穷大时,网络趋近于连续极限。至今为止,这种收敛只针对具有形式为度归一化均值的聚合函数的体系架构已知。我们将这些结果扩展到了一个非常大的聚合函数类上,其中包含了所有经典的消息传递图神经网络,例如基于注意力的消息传递或在(度规则化)卷积消息传递之上的最大卷积消息传递。在温和的假设下,我们用高概率非渐近界定来定量此收敛。我们的主要结果基于麦克迪尔米德不等式。有趣的是,我们单独处理了协调式最大值的聚合情况,因为它需要一种非常不同的证明技巧,并产生了质量不同的收敛速度。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【IJCAJ 2020】多通道神经网络 Multi-Channel Graph Neural Networks
专知会员服务
25+阅读 · 2020年7月19日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
【NeurIPS2019】图变换网络:Graph Transformer Network
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年6月2日
Arxiv
10+阅读 · 2021年11月3日
Interest-aware Message-Passing GCN for Recommendation
Arxiv
12+阅读 · 2021年2月19日
Arxiv
38+阅读 · 2020年12月2日
Position-aware Graph Neural Networks
Arxiv
15+阅读 · 2019年6月11日
Arxiv
24+阅读 · 2018年10月24日
Arxiv
23+阅读 · 2018年10月1日
VIP会员
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
【NeurIPS2019】图变换网络:Graph Transformer Network
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
相关论文
Arxiv
0+阅读 · 2023年6月2日
Arxiv
10+阅读 · 2021年11月3日
Interest-aware Message-Passing GCN for Recommendation
Arxiv
12+阅读 · 2021年2月19日
Arxiv
38+阅读 · 2020年12月2日
Position-aware Graph Neural Networks
Arxiv
15+阅读 · 2019年6月11日
Arxiv
24+阅读 · 2018年10月24日
Arxiv
23+阅读 · 2018年10月1日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员