Expressive Power of Invariant and Equivariant Graph Neural Networks

Abstract

Various classes of Graph Neural Networks (GNN) have been proposed and shown to be successful in a wide range of applications with graph structured data. In this paper, we propose a theoretical framework able to compare the expressive power of these GNN architectures. The current universality theorems only apply to intractable classes of GNNs. Here, we prove the first approximation guarantees for practical GNNs, paving the way for a better understanding of their generalization. Our theoretical results are proved for invariant GNNs computing a graph embedding (permutation of the nodes of the input graph does not affect the output) and equivariant GNNs computing an embedding of the nodes (permutation of the input permutes the output). We show that Folklore Graph Neural Networks (FGNN), which are tensor based GNNs augmented with matrix multiplication are the most expressive architectures proposed so far for a given tensor order. We illustrate our results on the Quadratic Assignment Problem (a NP-Hard combinatorial problem) by showing that FGNNs are able to learn how to solve the problem, leading to much better average performances than existing algorithms (based on spectral, SDP or other GNNs architectures). On a practical side, we also implement masked tensors to handle batches of graphs of varying sizes.

Appears in: Proceedings of the 9th International Conference on Learning Representations, ICLR 2021. 39 pages

References in corpus (10)

• Semi-Supervised Classification with Graph Convolutional Networks
• Benchmarking Graph Neural Networks
• On Learning Sets of Symmetric Elements
• Generalization and Representational Limits of Graph Neural Networks
• The Weisfeiler-Lehman Method and Graph Isomorphism Testing
• Can Graph Neural Networks Count Substructures?
• A Simple Proof of the Universality of Invariant/Equivariant Graph Neural Networks
• Universal Equivariant Multilayer Perceptrons
• The expressive power of kth-order invariant graph networks
• Walk Message Passing Neural Networks and Second-Order Graph Neural Networks

Cited by in corpus (9)

• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
• Graph Neural Networks with Learnable Structural and Positional Representations
• Graph Neural Networks with Local Graph Parameters
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Equivariant Subgraph Aggregation Networks
• Weisfeiler and Lehman Go Cellular: CW Networks
• Faster algorithms for the alignment of sparse correlated Erdös-Rényi random graphs
• Graph Self-Supervised Learning with Learnable Structural and Positional Encodings
• Neural Trees for Learning on Graphs