Weisfeiler and Lehman Go Cellular: CW Networks

Abstract

Graph Neural Networks (GNNs) are limited in their expressive power, struggle with long-range interactions and lack a principled way to model higher-order structures. These problems can be attributed to the strong coupling between the computational graph and the input graph structure. The recently proposed Message Passing Simplicial Networks naturally decouple these elements by performing message passing on the clique complex of the graph. Nevertheless, these models can be severely constrained by the rigid combinatorial structure of Simplicial Complexes (SCs). In this work, we extend recent theoretical results on SCs to regular Cell Complexes, topological objects that flexibly subsume SCs and graphs. We show that this generalisation provides a powerful set of graph "lifting" transformations, each leading to a unique hierarchical message passing procedure. The resulting methods, which we collectively call CW Networks (CWNs), are strictly more powerful than the WL test and not less powerful than the 3-WL test. In particular, we demonstrate the effectiveness of one such scheme, based on rings, when applied to molecular graph problems. The proposed architecture benefits from provably larger expressivity than commonly used GNNs, principled modelling of higher-order signals and from compressing the distances between nodes. We demonstrate that our model achieves state-of-the-art results on a variety of molecular datasets.

arXiv commentNeurIPS 2021. Contains 28 pages, 9 figures

References in corpus (17)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Neural Message Passing for Quantum Chemistry
• Geometric deep learning: going beyond Euclidean data
• Fast Graph Representation Learning with PyTorch Geometric
• Representation Learning on Graphs with Jumping Knowledge Networks
• Junction Tree Variational Autoencoder for Molecular Graph Generation
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Residual Gated Graph ConvNets
• Benchmarking Graph Neural Networks
• Strategies for Pre-training Graph Neural Networks
• Invariant and Equivariant Graph Networks
• A Survey on The Expressive Power of Graph Neural Networks
• Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks
• Hierarchical Inter-Message Passing for Learning on Molecular Graphs
• Natural Graph Networks
• Expressive Power of Invariant and Equivariant Graph Neural Networks

Cited by in corpus (2)

• Graph Neural Networks for Graph Drawing
• Graph Neural Networks with Learnable Structural and Positional Representations