Universality and Approximation Rates of Graph Neural Networks with Random Features
Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber
cs.LG, stat.ML
Submitted: 2026-07-29
Comments: 57 pages, 3 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: We investigate message-passing graph neural networks with random node features.
Terminology
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 at least 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.
Sources
- The Surprising Power of Graph Neural Networks with Random Node Initialization
- Relational inductive biases, deep learning, and graph networks
- On the Utilization of Unique Node Identifiers in Graph Neural Networks
- Graph Positional and Structural Encoder
- Coloring graph neural networks for node disambiguation
- Fast Graph Representation Learning with PyTorch Geometric
- Semi-Supervised Classification with Graph Convolutional Networks
- What graph neural networks cannot learn: depth vs width
- Invariant and Equivariant Graph Networks
- Global Attention Improves Graph Networks Generalization
- Graph Attention Networks
- A Review on Graph Neural Network Methods in Financial Applications
- How Powerful are Graph Neural Networks?
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks