Universal Invariant and Equivariant Graph Neural Networks

Abstract

Graph Neural Networks (GNN) come in many flavors, but should always be either invariant (permutation of the nodes of the input graph does not affect the output) or equivariant (permutation of the input permutes the output). In this paper, we consider a specific class of invariant and equivariant networks, for which we prove new universality theorems. More precisely, we consider networks with a single hidden layer, obtained by summing channels formed by applying an equivariant linear operator, a pointwise non-linearity and either an invariant or equivariant linear operator. Recently, Maron et al. (2019) showed that by allowing higher-order tensorization inside the network, universal invariant GNNs can be obtained. As a first contribution, we propose an alternative proof of this result, which relies on the Stone-Weierstrass theorem for algebra of real-valued functions. Our main contribution is then an extension of this result to the equivariant case, which appears in many practical applications but has been less studied from a theoretical point of view. The proof relies on a new generalized Stone-Weierstrass theorem for algebra of equivariant functions, which is of independent interest. Finally, unlike many previous settings that consider a fixed number of nodes, our results show that a GNN defined by a single set of parameters can approximate uniformly well a function defined on graphs of varying size.

References in corpus (12)

• Geometric deep learning: going beyond Euclidean data
• Spectral Networks and Locally Connected Networks on Graphs
• Graph Neural Networks: A Review of Methods and Applications
• Interaction Networks for Learning about Objects, Relations and Physics
• Group Equivariant Convolutional Networks
• Graph networks as learnable physics engines for inference and control
• On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups
• Equivariance Through Parameter-Sharing
• Invariant and Equivariant Graph Networks
• Covariant Compositional Networks For Learning Graphs
• Deep Models of Interactions Across Sets
• Universal approximations of permutation invariant/equivariant functions by deep neural networks

Cited by in corpus (51)

• Graph Neural Networks: A Review of Methods and Applications
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Stability Properties of Graph Neural Networks
• Graph Neural Networks: Taxonomy, Advances and Trends
• Differentiable Graph Module (DGM) for Graph Convolutional Networks
• Understanding Pooling in Graph Neural Networks
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
• A Survey on The Expressive Power of Graph Neural Networks
• GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training
• Representation Learning for Dynamic Graphs: A Survey
• SCENE: Reasoning about Traffic Scenes using Heterogeneous Graph Neural Networks
• Thermodynamics-informed graph neural networks
• On Learning Sets of Symmetric Elements
• Universal approximations of permutation invariant/equivariant functions by deep neural networks
• On the equivalence between graph isomorphism testing and function approximation with GNNs
• A General Theory of Equivariant CNNs on Homogeneous Spaces
• Natural Graph Networks
• Can Graph Neural Networks Count Substructures?
• Neural Networks Enforcing Physical Symmetries in Nonlinear Dynamical Lattices: The Case Example of the Ablowitz-Ladik Model
• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
• Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization
• A GNN Approach for Cell-Free Massive MIMO
• What graph neural networks cannot learn: depth vs width
• Expressive Power of Invariant and Equivariant Graph Neural Networks
• Building powerful and equivariant graph neural networks with structural message-passing
• Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
• Provably Powerful Graph Networks
• How hard is to distinguish graphs with graph neural networks?
• Set2Graph: Learning Graphs From Sets
• On the universality of $S_n$-equivariant $k$-body gates
• A Simple Proof of the Universality of Invariant/Equivariant Graph Neural Networks
• Equivariant Subgraph Aggregation Networks
• Universal Equivariant Multilayer Perceptrons
• Discriminative structural graph classification
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• On Universal Equivariant Set Networks
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results
• Graph Convolution with Low-rank Learnable Local Filters
• Graph Homomorphism Convolution
• Disentangling by Subspace Diffusion
• A Computationally Efficient Neural Network Invariant to the Action of Symmetry Subgroups
• Reconstruction for Powerful Graph Representations
• Graph Random Neural Features for Distance-Preserving Graph Representations
• Deformation Robust Roto-Scale-Translation Equivariant CNNs
• Neural Trees for Learning on Graphs
• Capacity of Group-invariant Linear Readouts from Equivariant Representations: How Many Objects can be Linearly Classified Under All Possible Views?
• Equivariant Deep Dynamical Model for Motion Prediction
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
• Interferometric Graph Transform for Community Labeling
• Distribution-Based Invariant Deep Networks for Learning Meta-Features
• Autoequivariant Network Search via Group Decomposition