# Expressiveness and Approximation Properties of Graph Neural Networks

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

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 40 references that are in the map.
- First posted on arXiv 10 Apr 2022.

## Builds on (most cited first, 15 of 15)

- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [The expressive power of kth-order invariant graph networks](https://mlsanity.com/paper/2007.12035/) (2020)
- [FAQ: Questions Asked Frequently](https://mlsanity.com/paper/1504.04044/) (2015)
- [Homomorphisms Are a Good Basis for Counting Small Subgraphs](https://mlsanity.com/paper/1705.01595/) (2017)
- [On the expressive power of query languages for matrices](https://mlsanity.com/paper/1709.08359/) (2017)
- [On the expressive power of linear algebra on graphs](https://mlsanity.com/paper/1812.04379/) (2018)
- [Graded modal logic and counting bisimulation](https://mlsanity.com/paper/1910.00039/) (2019)
- [A Novel Higher-order Weisfeiler-Lehman Graph Convolution](https://mlsanity.com/paper/2007.00346/) (2020)

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

- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests](https://mlsanity.com/paper/2302.07090/) (2023)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [How does over-squashing affect the power of GNNs?](https://mlsanity.com/paper/2306.03589/) (2023)
- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [Linkless Link Prediction via Relational Distillation](https://mlsanity.com/paper/2210.05801/) (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)
- [An Empirical Study of Realized GNN Expressiveness](https://mlsanity.com/paper/2304.07702/) (2023)
- [Path Neural Networks: Expressive and Accurate Graph Neural Networks](https://mlsanity.com/paper/2306.05955/) (2023)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Weisfeiler and Leman Go Relational](https://mlsanity.com/paper/2211.17113/) (2022)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [On Representing Mixed-Integer Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2210.10759/) (2022)
- [Clifford Group Equivariant Simplicial Message Passing Networks](https://mlsanity.com/paper/2402.10011/) (2024)
- [Some Might Say All You Need Is Sum](https://mlsanity.com/paper/2302.11603/) (2023)
- [A Practical, Progressively-Expressive GNN](https://mlsanity.com/paper/2210.09521/) (2022)
- [Homomorphism Counts for Graph Neural Networks: All About That Basis](https://mlsanity.com/paper/2402.08595/) (2024)
- [Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs](https://mlsanity.com/paper/2406.05938/) (2024)
- [On the Expressive Power of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2406.04336/) (2024)
- [Bundle Neural Networks for message diffusion on graphs](https://mlsanity.com/paper/2405.15540/) (2024)
- [Agent-based Graph Neural Networks](https://mlsanity.com/paper/2206.11010/) (2022)
- [Homophily modulates double descent generalization in graph convolution networks](https://mlsanity.com/paper/2212.13069/) (2022)
- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [ReFactor GNNs: Revisiting Factorisation-based Models from a Message-Passing Perspective](https://mlsanity.com/paper/2207.09980/) (2022)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [Rethinking the Capacity of Graph Neural Networks for Branching Strategy](https://mlsanity.com/paper/2402.07099/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)

## Abstract (arXiv)

Characterizing the separation power of graph neural networks (GNNs) provides an understanding of their limitations for graph learning tasks. Results regarding separation power are, however, usually geared at specific GNN architectures, and tools for understanding arbitrary GNN architectures are generally lacking. We provide an elegant way to easily obtain bounds on the separation power of GNNs in terms of the Weisfeiler-Leman (WL) tests, which have become the yardstick to measure the separation power of GNNs. The crux is to view GNNs as expressions in a procedural tensor language describing the computations in the layers of the GNNs. Then, by a simple analysis of the obtained expressions, in terms of the number of indexes and the nesting depth of summations, bounds on the separation power in terms of the WL-tests readily follow. We use tensor language to define Higher-Order Message-Passing Neural Networks (or k-MPNNs), a natural extension of MPNNs. Furthermore, the tensor language point of view allows for the derivation of universality results for classes of GNNs in a natural way. Our approach provides a toolbox with which GNN architecture designers can analyze the separation power of their GNNs, without needing to know the intricacies of the WL-tests. We also provide insights in what is needed to boost the separation power of GNNs.