Classical graph algorithms work well for combinatorial problems that can be thoroughly formalized and abstracted. Once the algorithm is derived, it generalizes to instances of any size. However, developing an algorithm that handles complex structures and interactions in the real world can be challenging. Rather than specifying the algorithm, we can try to learn it from the graph-structured data. Graph Neural Networks (GNNs) are inherently capable of working on graph structures; however, they struggle to generalize well, and learning on larger instances is challenging. In order to scale, we focus on a recurrent architecture design that can learn simple graph problems end to end on smaller graphs and then extrapolate to larger instances. As our main contribution, we identify three essential techniques for recurrent GNNs to scale. By using (i) skip connections, (ii) state regularization, and (iii) edge convolutions, we can guide GNNs toward extrapolation. This allows us to train on small graphs and apply the same model to much larger graphs during inference. Moreover, we empirically validate the extrapolation capabilities of our GNNs on algorithmic datasets.


翻译:古典图形算法对于可彻底正规化和抽象的组合问题效果良好。 一旦算法产生, 它就会概括到任何大小的例子。 但是, 开发一个处理真实世界中复杂结构和相互作用的算法可能会是挑战性的。 我们不用指定算法, 我们可以尝试从图形结构的数据中学习它。 图形神经网络( GNN) 具有内在能力, 可以对图形结构开展工作; 但是, 它们很难将它加以概括化, 而在更大的案例中学习是一个挑战。 为了扩大规模, 我们专注于一个经常性的建筑设计, 可以学习简单的图形问题, 结束在小图表中, 然后将它推到更大的例子中。 作为我们的主要贡献, 我们为经常性的 GNNS 找到三种基本技术。 通过使用 (i) 跳过连接, (ii) 状态正规化, 和 (iii) 边缘共变, 我们可以引导 GNNNs 进行外推。 这使我们能够对小图表进行培训, 并在推算过程中将同样的模型应用到大得多的图表中。 此外, 我们通过实验来验证我们的 GNNNN的外推法的外推能力。

0
下载
关闭预览

相关内容

强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
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日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
国家自然科学基金
4+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年2月9日
Arxiv
23+阅读 · 2022年2月24日
Arxiv
37+阅读 · 2021年2月10日
Arxiv
20+阅读 · 2019年11月23日
Arxiv
17+阅读 · 2019年3月28日
A Comprehensive Survey on Graph Neural Networks
Arxiv
21+阅读 · 2019年1月3日
Arxiv
53+阅读 · 2018年12月11日
Arxiv
24+阅读 · 2018年10月24日
VIP会员
相关资讯
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
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日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
相关论文
Arxiv
0+阅读 · 2023年2月9日
Arxiv
23+阅读 · 2022年2月24日
Arxiv
37+阅读 · 2021年2月10日
Arxiv
20+阅读 · 2019年11月23日
Arxiv
17+阅读 · 2019年3月28日
A Comprehensive Survey on Graph Neural Networks
Arxiv
21+阅读 · 2019年1月3日
Arxiv
53+阅读 · 2018年12月11日
Arxiv
24+阅读 · 2018年10月24日
相关基金
国家自然科学基金
4+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员