Equivariant Subgraph Aggregation Networks
arXiv:2110.02910
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.
arXiv commentPublished at ICLR 2022, Spotlight. 46 pages
References in corpus (33)
- Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
- Inductive Representation Learning on Large Graphs
- Neural Message Passing for Quantum Chemistry
- Geometric deep learning: going beyond Euclidean data
- Spectral Networks and Locally Connected Networks on Graphs
- Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
- Fast Graph Representation Learning with PyTorch Geometric
- Representation Learning on Graphs with Jumping Knowledge Networks
- Junction Tree Variational Autoencoder for Molecular Graph Generation
- DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
- Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
- Group Equivariant Convolutional Networks
- Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
- On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups
- Benchmarking Graph Neural Networks
- Universal Invariant and Equivariant Graph Neural Networks
- Invariant and Equivariant Graph Networks
- Covariant Compositional Networks For Learning Graphs
- A Survey on The Expressive Power of Graph Neural Networks
- On Learning Sets of Symmetric Elements
- Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity
- Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks
- Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings
- On the equivalence between graph isomorphism testing and function approximation with GNNs
- Natural Graph Networks
- Breaking the Limits of Message Passing Graph Neural Networks
- On the Equivalence between Positional Node Embeddings and Structural Graph Representations
- Expressive Power of Invariant and Equivariant Graph Neural Networks
- Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks
- Global Attention Improves Graph Networks Generalization
- Random Features Strengthen Graph Neural Networks
- Identity-aware Graph Neural Networks
- Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results