Invariant and Equivariant Graph Networks

Abstract

Invariant and equivariant networks have been successfully used for learning images, sets, point clouds, and graphs. A basic challenge in developing such networks is finding the maximal collection of invariant and equivariant linear layers. Although this question is answered for the first three examples (for popular transformations, at-least), a full characterization of invariant and equivariant linear layers for graphs is not known. In this paper we provide a characterization of all permutation invariant and equivariant linear layers for (hyper-)graph data, and show that their dimension, in case of edge-value graph data, is 2 and 15, respectively. More generally, for graph data defined on k-tuples of nodes, the dimension is the k-th and 2k-th Bell numbers. Orthogonal bases for the layers are computed, including generalization to multi-graph data. The constant number of basis elements and their characteristics allow successfully applying the networks to different size graphs. From the theoretical point of view, our results generalize and unify recent advancement in equivariant deep learning. In particular, we show that our model is capable of approximating any message passing neural network Applying these new linear layers in a simple deep neural network framework is shown to achieve comparable results to state-of-the-art and to have better expressivity than previous invariant and equivariant bases.

arXiv commentICLR 2019

Cited by in corpus (70)

• Graph Neural Networks: A Review of Methods and Applications
• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• DeeperGCN: All You Need to Train Deeper GCNs
• Benchmarking Graph Neural Networks
• Stability Properties of Graph Neural Networks
• Gauge Equivariant Convolutional Networks and the Icosahedral CNN
• Graph Neural Networks: Taxonomy, Advances and Trends
• Universal Invariant and Equivariant Graph Neural Networks
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• A Survey on The Expressive Power of Graph Neural Networks
• On Learning Sets of Symmetric Elements
• Generalization and Representational Limits of Graph Neural Networks
• Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks
• Universal approximations of permutation invariant/equivariant functions by deep neural networks
• Graph Neural Networks for Graph Drawing
• A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants
• A General Theory of Equivariant CNNs on Homogeneous Spaces
• Nested Graph Neural Networks
• Graph Neural Networks: Methods, Applications, and Opportunities
• Can Graph Neural Networks Count Substructures?
• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
• On the Universality of Rotation Equivariant Point Cloud Networks
• Expressive Power of Invariant and Equivariant Graph Neural Networks
• Building powerful and equivariant graph neural networks with structural message-passing
• Provably Powerful Graph Networks
• Set2Graph: Learning Graphs From Sets
• Graph Neural Networks with Local Graph Parameters
• BrainNNExplainer: An Interpretable Graph Neural Network Framework for Brain Network based Disease Analysis
• On the Universality of Invariant Networks
• Multiresolution Graph Transformers and Wavelet Positional Encoding for Learning Hierarchical Structures
• Equivariant Subgraph Aggregation Networks
• Universal Equivariant Multilayer Perceptrons
• Global Attention Improves Graph Networks Generalization
• Size-Invariant Graph Representations for Graph Classification Extrapolations
• Secure Deep Graph Generation with Link Differential Privacy
• Molecule Property Prediction and Classification with Graph Hypernetworks
• Regularizing Towards Permutation Invariance in Recurrent Models
• The Hintons in your Neural Network: a Quantum Field Theory View of Deep Learning
• Utilising Graph Machine Learning within Drug Discovery and Development
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results
• Weisfeiler and Lehman Go Cellular: CW Networks
• Lipschitz Normalization for Self-Attention Layers with Application to Graph Neural Networks
• Graph convolutions that can finally model local structure
• Quaternion Graph Neural Networks
• The expressive power of kth-order invariant graph networks
• The general theory of permutation equivarant neural networks and higher order graph variational encoders
• The Convolution Exponential and Generalized Sylvester Flows
• Unsupervised Joint $k$-node Graph Representations with Compositional Energy-Based Models
• Isometric Transformation Invariant and Equivariant Graph Convolutional Networks
• Walk Message Passing Neural Networks and Second-Order Graph Neural Networks
• Graph Random Neural Features for Distance-Preserving Graph Representations
• Circular-Symmetric Correlation Layer based on FFT
• SoGCN: Second-Order Graph Convolutional Networks
• Relational State-Space Model for Stochastic Multi-Object Systems
• Learning Augmentation Distributions using Transformed Risk Minimization
• Deep Constraint-based Propagation in Graph Neural Networks
• Equivariant Deep Dynamical Model for Motion Prediction
• Equivariant and Invariant Reynolds Networks
• Top-N: Equivariant set and graph generation without exchangeability
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs
• Neural Trees for Learning on Graphs
• Equivariant Networks for Pixelized Spheres
• Autoequivariant Network Search via Group Decomposition
• Distribution-Based Invariant Deep Networks for Learning Meta-Features
• Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters
• Improving the Expressive Power of Graph Neural Network with Tinhofer Algorithm
• Representing Unordered Data Using Complex-Weighted Multiset Automata
• Applications of Common Information to Computing Functions