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 and inspired by Murphy et al. (2019), we propose the Local Relational
Pooling model and demonstrate that it is not only effective for substructure
counting but also able to achieve competitive performance on molecular
prediction tasks.

本文研究了一种基于图神经网络的图形子结构计数方法，探讨了各种常见图神经网络的表达能力和局限性，提出了一种新的本地化关系池化模型并在分子预测任务上取得了有竞争力的性能。