# A Simple Proof of the Universality of Invariant/Equivariant Graph Neural Networks

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2019.

## Built on by (most cited first, 19 of 19)

- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [SE(3) Equivariant Graph Neural Networks with Complete Local Frames](https://mlsanity.com/paper/2110.14811/) (2021)
- [Reconstruction for Powerful Graph Representations](https://mlsanity.com/paper/2110.00577/) (2021)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [Equivariant Polynomials for Graph Neural Networks](https://mlsanity.com/paper/2302.11556/) (2023)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Weisfeiler and Leman Go Relational](https://mlsanity.com/paper/2211.17113/) (2022)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [Neural Trees for Learning on Graphs](https://mlsanity.com/paper/2105.07264/) (2021)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [Cycle Invariant Positional Encoding for Graph Representation Learning](https://mlsanity.com/paper/2311.14333/) (2023)
- [Equivariant and Invariant Reynolds Networks](https://mlsanity.com/paper/2110.08092/) (2021)
- [Any-Dimensional Invariant Universality](https://mlsanity.com/paper/2605.23156/) (2026)
- [Abelian Neural Networks](https://mlsanity.com/paper/2102.12232/) (2021)
- [Current Symmetry Group Equivariant Convolution Frameworks for Representation Learning](https://mlsanity.com/paper/2409.07327/) (2024)
- [Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters](https://mlsanity.com/paper/2111.03317/) (2021)
- [Learning to Approximate Uniform Facility Location via Graph Neural Networks](https://mlsanity.com/paper/2602.13155/) (2026)

## Abstract (arXiv)

We present a simple proof for the universality of invariant and equivariant tensorized graph neural networks. Our approach considers a restricted intermediate hypothetical model named Graph Homomorphism Model to reach the universality conclusions including an open case for higher-order output. We find that our proposed technique not only leads to simple proofs of the universality properties but also gives a natural explanation for the tensorization of the previously studied models. Finally, we give some remarks on the connection between our model and the continuous representation of graphs.