# Universality and Approximation Rates of Graph Neural Networks with Random Features

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 51 references that are in the map.
- First posted on arXiv 29 Jul 2026.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [A Review on Graph Neural Network Methods in Financial Applications](https://mlsanity.com/paper/2111.15367/) (2021)
- [Coloring graph neural networks for node disambiguation](https://mlsanity.com/paper/1912.06058/) (2019)
- [Graph Positional and Structural Encoder](https://mlsanity.com/paper/2307.07107/) (2023)
- [Global Attention Improves Graph Networks Generalization](https://mlsanity.com/paper/2006.07846/) (2020)
- [On the Utilization of Unique Node Identifiers in Graph Neural Networks](https://mlsanity.com/paper/2411.02271/) (2024)

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

- [Multi-Attractor GNNs: Set-Valued Expressivity Beyond Unique Equilibria](https://mlsanity.com/paper/2609.35274/) (2026)
- [The Expressive Power of Random-Feature MPNNs Across Graph Sizes](https://mlsanity.com/paper/2610.12809/) (2026)
- [When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors](https://mlsanity.com/paper/2610.13765/) (2026)

## Abstract (arXiv)

We investigate message-passing graph neural networks with random node features. Random node features are known to enhance the expressiveness of graph neural networks (GNNs) both theoretically and empirically. Here, we establish a novel universality result focusing on permutation-equivariant neural networks (PENNs), a class of GNNs built from feedforward neural network components that subsumes many prominent GNN architectures. We show that PENNs, combined with partially random node features, can approximate arbitrarily well in probability any measurable permutation-invariant or permutation-equivariant function on directed graphs of fixed size with multidimensional node and edge features. For k-times continuously differentiable functions, k≥ 2, we also derive upper bounds on the approximation rates, relating the complexity of the feedforward components of a PENN in terms of layer depth and number of nonzero weights to the desired approximation accuracy.