Universality and Approximation Rates of Graph Neural Networks with Random Features

arXiv cs.LG Papers
graph-neural-networks random-features universality approximation-rates permutation-equivariance message-passing

Summary

This paper proves that graph neural networks with random node features can universally approximate permutation-invariant or equivariant functions on directed graphs, and provides approximation rate bounds for differentiable functions.

arXiv:2607.26699v1 Announce Type: new Abstract: 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\geq 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.
Original Article
View Cached Full Text

Cached at: 07/30/26, 10:00 AM 

# Universality and Approximation Rates of Graph Neural Networks with Random Features
Source: [https://arxiv.org/abs/2607.26699](https://arxiv.org/abs/2607.26699)
[View PDF](https://arxiv.org/pdf/2607.26699)

> Abstract: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\\geq 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\.

## Submission history

From: Niklas Weber \[[view email](https://arxiv.org/show-email/b16baa18/2607.26699)\] **\[v1\]**Wed, 29 Jul 2026 09:46:07 UTC \(72 KB\)

Similar Articles

Distance-Preserving Embeddings in Inhomogeneous Random Graphs

arXiv cs.LG

This paper analyzes distance-preserving embeddings in inhomogeneous random graphs, providing tighter distortion bounds than classical worst-case results and introducing a GNN-augmented variant that learns universal features from small graphs.

Generalized Neurons

ML at Berkeley

The article explores the Universal Approximation Theorem in deep learning, analyzing the representation capacity of individual neurons and neural network layers using ReLU activation functions.

Any-Dimensional Invariant Universality

arXiv cs.LG

This paper develops a systematic framework for establishing universality of machine learning models that handle inputs of varying dimensions (e.g., graphs with different node counts). It shows that many existing architectures fail to be universal and proposes simple modifications to restore universality.