Graph Neural Networks (GNNs) for representation learning of graphs broadly follow a neighborhood aggregation framework, where the representation vector of a node is computed by recursively aggregating and transforming feature vectors of its neighboring nodes. Many GNN variants have been proposed and have achieved state-of-the-art results on both node and graph classification tasks. However, despite GNNs revolutionizing graph representation learning, there is limited understanding of their representational properties and limitations. Here, we present a theoretical framework for analyzing the expressive power of GNNs in capturing different graph structures. Our results characterize the discriminative power of popular GNN variants, such as Graph Convolutional Networks and GraphSAGE, and show that they cannot learn to distinguish certain simple graph structures. We then develop a simple architecture that is provably the most expressive among the class of GNNs and is as powerful as the Weisfeiler-Lehman graph isomorphism test. We empirically validate our theoretical findings on a number of graph classification benchmarks, and demonstrate that our model achieves state-of-the-art performance.


翻译:用于代表图形的图形神经网络(GNNs)大致遵循一个周边聚合框架,在此框架下,节点的表示矢量通过相邻节点的递归和变换特性矢量来计算。许多GNN变量已经提出,并且在节点和图形分类任务方面都取得了最先进的结果。然而,尽管GNNs将图形表达学习革命化,但对其代表性属性和局限性的了解有限。在这里,我们提出了一个理论框架,用于分析GNNs在捕捉不同图形结构方面的表达力。我们的结果体现了GNN变量的流行性能,例如Greab Convolutional 网络和GreagraphSAGE,表明它们无法学会区分某些简单的图形结构。我们随后开发了一个简单的结构,在GNNS类别中最能表达,而且像Weisfeiler-Lehman图形的形态测试一样强大。我们从经验上验证了我们关于一些图表分类基准的理论结论,并表明我们的模型达到了最先进的性能。

23
下载
关闭预览

相关内容

【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
153+阅读 · 2020年5月26日
【阿尔托大学】图神经网络,Graph Neural Networks,附60页ppt
专知会员服务
179+阅读 · 2020年4月26日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
Graph Neural Networks 综述
计算机视觉life
29+阅读 · 2019年8月13日
Graph Neural Network(GNN)最全资源整理分享
深度学习与NLP
339+阅读 · 2019年7月9日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
ICLR2019最佳论文出炉
专知
11+阅读 · 2019年5月6日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
【论文】图上的表示学习综述
机器学习研究会
12+阅读 · 2017年9月24日
Geometric Graph Convolutional Neural Networks
Arxiv
10+阅读 · 2019年9月11日
Self-Attention Graph Pooling
Arxiv
13+阅读 · 2019年6月13日
A Comprehensive Survey on Graph Neural Networks
Arxiv
13+阅读 · 2019年3月10日
Simplifying Graph Convolutional Networks
Arxiv
12+阅读 · 2019年2月19日
Arxiv
23+阅读 · 2018年10月24日
Arxiv
10+阅读 · 2018年2月4日
Arxiv
7+阅读 · 2018年1月10日
VIP会员
相关VIP内容
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
153+阅读 · 2020年5月26日
【阿尔托大学】图神经网络,Graph Neural Networks,附60页ppt
专知会员服务
179+阅读 · 2020年4月26日
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
Graph Neural Networks 综述
计算机视觉life
29+阅读 · 2019年8月13日
Graph Neural Network(GNN)最全资源整理分享
深度学习与NLP
339+阅读 · 2019年7月9日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
ICLR2019最佳论文出炉
专知
11+阅读 · 2019年5月6日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
【论文】图上的表示学习综述
机器学习研究会
12+阅读 · 2017年9月24日
相关论文
Geometric Graph Convolutional Neural Networks
Arxiv
10+阅读 · 2019年9月11日
Self-Attention Graph Pooling
Arxiv
13+阅读 · 2019年6月13日
A Comprehensive Survey on Graph Neural Networks
Arxiv
13+阅读 · 2019年3月10日
Simplifying Graph Convolutional Networks
Arxiv
12+阅读 · 2019年2月19日
Arxiv
23+阅读 · 2018年10月24日
Arxiv
10+阅读 · 2018年2月4日
Arxiv
7+阅读 · 2018年1月10日
Top
微信扫码咨询专知VIP会员