We present a novel graph neural network we call AgentNet, which is designed specifically for graph-level tasks. AgentNet is inspired by sublinear algorithms, featuring a computational complexity that is independent of the graph size. The architecture of AgentNet differs fundamentally from the architectures of traditional graph neural networks. In AgentNet, some trained \textit{neural agents} intelligently walk the graph, and then collectively decide on the output. We provide an extensive theoretical analysis of AgentNet: We show that the agents can learn to systematically explore their neighborhood and that AgentNet can distinguish some structures that are even indistinguishable by 2-WL. Moreover, AgentNet is able to separate any two graphs which are sufficiently different in terms of subgraphs. We confirm these theoretical results with synthetic experiments on hard-to-distinguish graphs and real-world graph classification tasks. In both cases, we compare favorably not only to standard GNNs but also to computationally more expensive GNN extensions.


翻译:我们展示了一个我们称为Agentneal的新型图形神经网络,我们把它称为AgentNet, 专门设计用于图形层面的任务。 AgentNet 受亚线性算法的启发,它具有与图形大小无关的计算复杂性。 AgentNet 的架构与传统的图形神经网络的结构有根本的不同。 在AgentNet, 一些经过训练的“textit{neural代理商” 以智慧的方式在图形中走过, 然后共同决定输出。 我们对AgentNet 进行了广泛的理论分析。 我们对AgentNet 提供了广泛的理论分析: 我们显示, Agent Net 能够学会系统探索他们的邻居, 而AgentNet 可以区分一些甚至无法区分为 2-WL 的建筑结构。 此外, AgentNet 能够分离任何两个在子图谱上差异很大的图表。 我们用硬到差异的图形和真实世界的图形分类任务的合成实验证实了这些理论结果。 在这两种情况下,我们不仅比较标准 GNNS, 而且还比较了更昂贵的计算 GNNNN。</s>

0
下载
关闭预览

相关内容

【IJCAJ 2020】多通道神经网络 Multi-Channel Graph Neural Networks
专知会员服务
25+阅读 · 2020年7月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
2+阅读 · 2009年12月31日
Arxiv
13+阅读 · 2021年7月20日
Arxiv
13+阅读 · 2021年6月14日
Arxiv
38+阅读 · 2020年12月2日
Arxiv
19+阅读 · 2020年7月13日
Arxiv
27+阅读 · 2020年6月19日
Position-aware Graph Neural Networks
Arxiv
15+阅读 · 2019年6月11日
Arxiv
17+阅读 · 2019年3月28日
Arxiv
31+阅读 · 2018年11月13日
Arxiv
24+阅读 · 2018年10月24日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
相关论文
Arxiv
13+阅读 · 2021年7月20日
Arxiv
13+阅读 · 2021年6月14日
Arxiv
38+阅读 · 2020年12月2日
Arxiv
19+阅读 · 2020年7月13日
Arxiv
27+阅读 · 2020年6月19日
Position-aware Graph Neural Networks
Arxiv
15+阅读 · 2019年6月11日
Arxiv
17+阅读 · 2019年3月28日
Arxiv
31+阅读 · 2018年11月13日
Arxiv
24+阅读 · 2018年10月24日
相关基金
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
2+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员