Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks

Abstract

The pairwise interaction paradigm of graph machine learning has predominantly governed the modelling of relational systems. However, graphs alone cannot capture the multi-level interactions present in many complex systems and the expressive power of such schemes was proven to be limited. To overcome these limitations, we propose Message Passing Simplicial Networks (MPSNs), a class of models that perform message passing on simplicial complexes (SCs). To theoretically analyse the expressivity of our model we introduce a Simplicial Weisfeiler-Lehman (SWL) colouring procedure for distinguishing non-isomorphic SCs. We relate the power of SWL to the problem of distinguishing non-isomorphic graphs and show that SWL and MPSNs are strictly more powerful than the WL test and not less powerful than the 3-WL test. We deepen the analysis by comparing our model with traditional graph neural networks (GNNs) with ReLU activations in terms of the number of linear regions of the functions they can represent. We empirically support our theoretical claims by showing that MPSNs can distinguish challenging strongly regular graphs for which GNNs fail and, when equipped with orientation equivariant layers, they can improve classification accuracy in oriented SCs compared to a GNN baseline.

ICML 2021. Contains 27 pages, 9 figures

References in corpus (9)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Fast Graph Representation Learning with PyTorch Geometric
• TUDataset: A collection of benchmark datasets for learning with graphs
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Graph Wavelet Neural Network
• Natural Graph Networks
• On the Number of Linear Regions of Convolutional Neural Networks
• Decimated Framelet System on Graphs and Fast G-Framelet Transforms
• MathNet: Haar-Like Wavelet Multiresolution-Analysis for Graph Representation and Learning

Cited by in corpus (13)

• What are higher-order networks?
• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Signal Processing on Cell Complexes
• Dirac synchronization is rhythmic and explosive
• Beltrami Flow and Neural Diffusion on Graphs
• Equivariant Subgraph Aggregation Networks
• Simplicial Complex Representation Learning
• Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes
• Weisfeiler and Lehman Go Cellular: CW Networks
• Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums
• Graph Self-Supervised Learning with Learnable Structural and Positional Encodings
• On the Expected Complexity of Maxout Networks
• Gaussian Processes on Hypergraphs