Can graph neural networks count substructures?
Can graph neural networks count substructures?
复制标题
DOI：
--
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Zhengdao Chen;Lei Chen;Soledad Villar;Joan Bruna
中科院分区：
文献类型：
--
作者：
Zhengdao Chen;Lei Chen;Soledad Villar;Joan Bruna
检测和计算图中某些子结构的能力对于解决图结构数据中的许多任务非常重要，特别是在计算化学和生物学以及社会网络分析的背景下。受此启发，我们建议通过计算属性图子结构的能力来研究图神经网络(GNN)的表达能力，扩展了最近在图同构测试和函数逼近方面检验其能力的工作。我们区分了两种子结构计数：诱导子图计数和子图计数，并为流行的GNN体系结构建立了肯定和否定的答案。具体地，我们证明了消息传递神经网络(MPNN)、2-Weisfeler-Lehman(2-WL)和2-不变图网络(2-IGN)不能对包含3个或更多结点的子结构进行诱导子图计数，而可以对星形子结构进行子图计数。作为中介，我们证明了2-WL和2-IGN在区分非同构图方面是等价的，部分回答了Maron等人提出的一个公开问题。(2019年)。我们还证明了k-WL和k-IGN的正结果，以及有限次迭代的k-WL的负结果。然后，我们进行了实验，支持了MPNN和2-IGN的理论结果。此外，在子结构计数的启发下，我们提出了一种局部关系池方法，该方法受到Murphy等人的启发。(2019)，并证明了它不仅对子结构计数有效，而且能够在实际任务中获得具有竞争力的性能。
The ability to detect and count certain substructures in graphs is important for solving many tasks on graph-structured data, especially in the contexts of computational chemistry and biology as well as social network analysis. Inspired by this, we propose to study the expressive power of graph neural networks (GNNs) via their ability to count attributed graph substructures, extending recent works that examine their power in graph isomorphism testing and function approximation. We distinguish between two types of substructure counting: induced-subgraph-count and subgraph-count, and establish both positive and negative answers for popular GNN architectures. Specifically, we prove that Message Passing Neural Networks (MPNNs), 2-Weisfeiler-Lehman (2-WL) and 2-Invariant Graph Networks (2-IGNs) cannot perform induced-subgraph-count of substructures consisting of 3 or more nodes, while they can perform subgraph-count of star-shaped substructures. As an intermediary step, we prove that 2-WL and 2-IGNs are equivalent in distinguishing non-isomorphic graphs, partly answering an open problem raised in Maron et al. (2019). We also prove positive results for k-WL and k-IGNs as well as negative results for k-WL with a finite number of iterations. We then conduct experiments that support the theoretical results for MPNNs and 2-IGNs. Moreover, motivated by substructure counting, we propose a local relational pooling approach with inspirations from Murphy et al. (2019) and demonstrate that it is not only effective for substructure counting but also able to achieve competitive performance on real-world tasks.