Can graph neural networks count substructures?

By Zhengdao Chen, Lei Chen, Soledad Villar, Joan Bruna. Neural Information Processing Systems, 2020

381 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Materials Chemistry

View Paper: https://www.semanticscholar.org/paper/536da0e76290aea9cbe75c29bac096aeb45ef875

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Jure Leskovec
2. Michael M. Bronstein
3. William L. Hamilton
4. Yoshua Bengio
5. Jian Tang
6. Pan Li
7. Tommi S. Jaakkola
8. Petar Velickovic

In Materials Chemistry

1. Jure Leskovec
2. Jian Tang
3. Tommi S. Jaakkola
4. Muhan Zhang
5. Xiyuan Wang
6. Michael M. Bronstein
7. Pan Li
8. Hongwei Wang

Citations in the corpus

• On the equivalence between graph isomorphism testing and function approximation with GNNs (2019, methodology): “Then, we let (1)A later work [7] contains a simpler proof.”
• How Powerful are Spectral Graph Neural Networks (2022, methodology): “Some models with more complex acceleration techniques for computing PPR are introduced, like GBP (Chen et al., 2020a).”
• Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks (2021, background): “In particular, they are limited in their capability of detecting graph structure such as triangles or cliques (Chen et al., 2020).”
• Principal Neighbourhood Aggregation for Graph Nets (2020, methodology): “Finally, we detail the design of graph convolutional layers which leverage the proposed Principal Neighbourhood Aggregation.”
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “k-WL tests in comparison to other graph invariants [18], [76], [77], [78], while recently [19] approached GNN expressivity by studying their ability to count substructures.”
• Utilizing graph machine learning within drug discovery and development (2021, background): “These issues have limited the expressivity of traditional GNNs [235, 236].”
• Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, neutral): “The former was refined in (Chen et al., 2020).”
• DiGress: Discrete Denoising diffusion for graph generation (2022, methodology): “One example of this limitation is the difficulty for standard message passing networks (MPNNs) to detect simple substructures such as cycles (Chen et al., 2020), which raises concerns about their ability to accurately capture the properties of the data distribution.”
• Generalization and Representational Limits of Graph Neural Networks (2020, methodology): “Despite addressing complex graphs instead of sequences, generalization bounds for GNNs and RNNs are comparable, so the empirical success of GNNs is not surprising.”
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (2020, background): “We break from the convention that previous works characterize and further improve the power of GNNs by intimating different-order WL tests [26,27,30,58].”