# Expressive Power of Invariant and Equivariant Graph Neural Networks

arXiv: https://arxiv.org/abs/2006.15646 · HTML: https://mlsanity.com/paper/2006.15646/

## Key facts

- Cited by 100 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2020.

## Built on by (most cited first, 30 of 100)

- [GemNet: Universal Directional Graph Neural Networks for Molecules](https://mlsanity.com/paper/2106.08903/) (2021)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [Equivariant Architectures for Learning in Deep Weight Spaces](https://mlsanity.com/paper/2301.12780/) (2023)
- [A Generalization of ViT/MLP-Mixer to Graphs](https://mlsanity.com/paper/2212.13350/) (2022)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Polynormer: Polynomial-Expressive Graph Transformer in Linear Time](https://mlsanity.com/paper/2403.01232/) (2024)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests](https://mlsanity.com/paper/2302.07090/) (2023)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Geometrically Equivariant Graph Neural Networks: A Survey](https://mlsanity.com/paper/2202.07230/) (2022)
- [Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs](https://mlsanity.com/paper/2210.13978/) (2022)
- [How does over-squashing affect the power of GNNs?](https://mlsanity.com/paper/2306.03589/) (2023)
- [Graph Neural Networks with Local Graph Parameters](https://mlsanity.com/paper/2106.06707/) (2021)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness](https://mlsanity.com/paper/2401.08514/) (2024)
- [Equivariant Polynomials for Graph Neural Networks](https://mlsanity.com/paper/2302.11556/) (2023)
- [A graphon-signal analysis of graph neural networks](https://mlsanity.com/paper/2305.15987/) (2023)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [Explainable Equivariant Neural Networks for Particle Physics: PELICAN](https://mlsanity.com/paper/2307.16506/) (2023)
- [On Representing Mixed-Integer Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2210.10759/) (2022)
- [Is Distance Matrix Enough for Geometric Deep Learning?](https://mlsanity.com/paper/2302.05743/) (2023)
- [A Practical, Progressively-Expressive GNN](https://mlsanity.com/paper/2210.09521/) (2022)
- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)

## Abstract (arXiv)

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.