# On dimensionality of feature vectors in MPNNs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 13 references that are in the map.
- First posted on arXiv 6 Feb 2024.

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

- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [On the Expressive Power of Geometric Graph Neural Networks](https://mlsanity.com/paper/2301.09308/) (2023)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem](https://mlsanity.com/paper/2306.06529/) (2023)
- [Weisfeiler and Leman Go Relational](https://mlsanity.com/paper/2211.17113/) (2022)
- [Is Distance Matrix Enough for Geometric Deep Learning?](https://mlsanity.com/paper/2302.05743/) (2023)
- [Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks](https://mlsanity.com/paper/2211.03232/) (2022)

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

- [FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network](https://mlsanity.com/paper/2410.09118/) (2024)
- [On the H"older Stability of Multiset and Graph Neural Networks](https://mlsanity.com/paper/2406.06984/) (2024)
- [Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit](https://mlsanity.com/paper/2505.00291/) (2025)
- [A note on the VC dimension of 1-dimensional GNNs](https://mlsanity.com/paper/2410.07829/) (2024)
- [On the (Non) Injectivity of Piecewise Linear Janossy Pooling](https://mlsanity.com/paper/2505.20150/) (2025)
- [Message Passing on the Edge: Towards Scalable and Expressive GNNs](https://mlsanity.com/paper/2510.13615/) (2025)
- [Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture](https://mlsanity.com/paper/2610.16993/) (2026)

## Abstract (arXiv)

We revisit the classical result of Morris et al.~(AAAI'19) that message-passing graphs neural networks (MPNNs) are equal in their distinguishing power to the Weisfeiler--Leman (WL) isomorphism test. Morris et al.~show their simulation result with ReLU activation function and O(n)-dimensional feature vectors, where n is the number of nodes of the graph. By introducing randomness into the architecture, Aamand et al.~(NeurIPS'22) were able to improve this bound to O(log n)-dimensional feature vectors, again for ReLU activation, although at the expense of guaranteeing perfect simulation only with high probability. Recently, Amir et al.~(NeurIPS'23) have shown that for any non-polynomial analytic activation function, it is enough to use just 1-dimensional feature vectors. In this paper, we give a simple proof of the result of Amit et al.~and provide an independent experimental validation of it.