Equivariant Subgraph Aggregation Networks
Preprint
Abstract
Message-passing neural networks (MPNNs) are the leading architecture for deep learning on graph-structured data, in large part due to their simplicity and scalability. Unfortunately, it was shown that these architectures are limited in their expressive power. This paper proposes a novel framework called Equivariant Subgraph Aggregation Networks (ESAN) to address this issue. Our main observation is that while two graphs may not be distinguishable by an MPNN, they often contain distinguishable subgraphs. Thus, we propose to represent each graph as a set of subgraphs derived by some predefined policy, and to process it using a suitable equivariant architecture. We develop novel variants of the 1-dimensional Weisfeiler-Leman (1-WL) test for graph isomorphism, and prove lower bounds on the expressiveness of ESAN in terms of these new WL variants. We further prove that our approach increases the expressive power of both MPNNs and more expressive architectures. Moreover, we provide theoretical results that describe how design choices such as the subgraph selection policy and equivariant neural architecture affect our architecture's expressive power. To deal with the increased computational cost, we propose a subgraph sampling scheme, which can be viewed as a stochastic version of our framework. A comprehensive set of experiments on real and synthetic datasets demonstrates that our framework improves the expressive power and overall performance of popular GNN architectures.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Improving Graph Neural Network Expressivity via Subgraph Isomorphism CountingIEEE Transactions on Pattern Analysis and Machine Intelligence, 2022
- Learning the Relevant Substructures for Tasks on Graph Data2021
- Graph neural networks in particle physicsMachine Learning: Science and Technology, 2021
- On Weisfeiler-Leman invariance: Subgraph counts and related graph propertiesJournal of Computer and System Sciences, 2020
- Automatic Chemical Design Using a Data-Driven Continuous Representation of MoleculesACS Central Science, 2018
- ZINC 15 – Ligand Discovery for EveryoneJournal of Chemical Information and Modeling, 2015
- Propagation kernels: efficient graph kernels from propagated informationMachine Learning, 2015
- Learning task-dependent distributed representations by backpropagation through structure2002
- Supervised neural networks for the classification of structuresIEEE Transactions on Neural Networks, 1997
- An optimal lower bound on the number of variables for graph identificationCombinatorica, 1992