🤖 machine learning

Universality and Approximation Rates of Graph Neural Networks with Random Features

This paper establishes that message-passing graph neural networks with partially random node features possess universal approximation capabilities for permutation-invariant and equivariant functions on fixed-size directed graphs, while also deriving theoretical upper bounds on their approximation rates based on network complexity.

Original authors: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

Published 2026-07-30

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Puzzle of the Shape-Shifting Crowd

Imagine you are trying to teach a computer to understand the world not as a grid of pixels or a list of words, but as a web of connections. This is the realm of Graph Neural Networks (GNNs), a branch of artificial intelligence designed to handle data that looks like a map of friends, molecules, or traffic routes. In these maps, the most important thing isn't just what an individual item is, but how it connects to its neighbors.

However, there is a tricky rule these computers must follow: symmetry. If you have a group of friends and you swap their names, the group is still the same group. A good graph AI shouldn't care who is sitting in chair A or chair B; it should only care about the pattern of who is talking to whom. This is called permutation invariance (for the whole group) or permutation equivariance (for the individuals). The problem is that standard AI models are terrible at this. They often get confused by the order in which data arrives, failing to recognize that two different-looking lists of names actually describe the exact same social circle.

To fix this, scientists have tried giving the AI "random noise" or "random IDs" to help it tell nodes apart, much like giving every person in a crowd a temporary, unique sticker. But until now, we didn't fully know if this trick could make the AI smart enough to learn any possible pattern, or if there were limits to how well it could learn complex rules. This paper dives deep into that question, asking: "If we give these graph-reading computers random stickers, can they learn to be perfect at understanding any graph structure?"

The Magic of Random Stickers

The authors of this paper, Lukas Gonon, Thilo Meyer-Brandis, and Niklas Weber, set out to prove that a specific type of graph AI, called a Permutation-Equivariant Neural Network (PENN), becomes incredibly powerful when you give it random node features. Think of a PENN as a team of detectives trying to solve a mystery on a map. Usually, if two suspects look identical and have the same friends, the detectives can't tell them apart. But if you give each suspect a random, unique sticker (a random feature), the detectives can finally distinguish them and solve the case.

The paper's main discovery is a "universal" guarantee. The authors proved mathematically that if you feed these PENNs random stickers, they can approximate any measurable function on a graph of a fixed size with arbitrarily high probability. In plain English: if you want the AI to learn a specific rule about a network (like predicting which molecule is toxic or which financial network is at risk), and you give it enough random stickers, there is a PENN architecture that can learn that rule almost perfectly. This holds true even if the rule is messy or complex, and even if the data has many different types of features attached to the nodes and edges.

How Good is "Good Enough"?

But the paper doesn't just say "it works"; it tells you how big the AI needs to be to get the job done. The authors looked at functions that are smooth and well-behaved (mathematically speaking, "k-times continuously differentiable," where $k \ge 2$ ). They derived a formula for the approximation rates, which is basically a speed limit on how fast the AI can learn as you make it bigger.

They found that the depth of the network (the number of layers) only needs to grow logarithmically as you demand more accuracy. This is great news: if you want to be twice as accurate, you don't need to double the size of the brain; you just need a tiny bit more depth. However, the number of connections (nonzero weights) grows polynomially as you demand more accuracy. Specifically, the complexity scales with a power of $1/\epsilon$ , where $\epsilon$ is your desired error margin. The paper notes that this power depends on the "smoothness" of the rule you are trying to learn ( $k$ ) and the size of the graph ( $N$ ). Essentially, for very complex, jagged rules or very large graphs, you need a lot more connections, but for smooth rules, the AI remains efficient.

The "Average" Trick for Safety

One of the paper's most playful and practical insights addresses a side effect of using random stickers. Because the stickers are random, if you run the AI once, it might give a slightly different answer than if you run it again with different stickers. This breaks the symmetry rule: the AI might treat the same group of friends differently just because the stickers changed.

The authors suggest a clever fix: averaging. If you run the AI many times with different random stickers and take the average of the results, the randomness cancels out, and the AI becomes perfectly symmetric again. They proved that this "average" version still retains the superpower of being able to learn any rule. It's like asking a crowd of people to guess the weight of a pumpkin; one person might be way off, but if you average the guesses of a hundred people, you get a very accurate answer. The paper shows that you can get this perfect symmetry and perfect learning ability simultaneously by simply averaging a few runs.

What This Means for the Future

The authors are careful to state that this is a theoretical proof, not a simulation of a specific dataset. They have mathematically demonstrated that the potential exists for these models to be universal approximators. They explicitly rule out the idea that you need complex, custom-built architectures to achieve this; the standard PENN structure, when augmented with random features, is sufficient.

They also clarify that while random features break the "perfect symmetry" of a single run, they don't break the "symmetry in expectation" (the average behavior). This suggests that in practice, using random features is a robust strategy. The paper concludes that PENNs with random features should be considered a strong baseline for graph learning tasks. They aren't just a theoretical curiosity; they offer a concrete, mathematically backed blueprint for building graph AIs that are both powerful and flexible, capable of learning complex patterns in networks ranging from chemical molecules to financial systems.

Technical Summary: Universality and Approximation Rates of Graph Neural Networks with Random Features

Problem Statement

Graph Neural Networks (GNNs), particularly message-passing architectures, have achieved significant empirical success but face theoretical limitations regarding their expressive power. Standard message-passing GNNs are limited by the 1-Weisfeiler–Leman (1-WL) test, meaning they cannot distinguish certain non-isomorphic graph structures. While strategies exist to overcome this—such as higher-order architectures or enriching node features—there is a lack of rigorous theoretical results establishing the universal approximation capabilities of specific, practical GNN architectures when augmented with random features. Furthermore, existing universality results often rely on restrictive assumptions, such as requiring target functions to be continuous, domains to be compact, or features to be finite-dimensional, and often fail to address approximation rates (complexity bounds) for these models.

Methodology

The authors investigate Permutation-Equivariant Neural Networks (PENNs), a class of GNNs that generalizes many popular message-passing architectures (e.g., GCN, GIN, GraphSAGE, GAT). The core methodological innovation is the augmentation of standard node features with random node features.

Architecture Definition: The paper defines PENNs as functions composed of feedforward neural network (FNN) components ( $\rho, \phi, \alpha, \psi$ ) that aggregate information from neighborhoods and global graph attributes. This structure subsumes the Aggregate-Combine-Readout (ACR) framework.
Random Features: The authors introduce random node features $R$ that provide "finite unique node features." This means that with high probability (or almost surely), the random features assign distinct identifiers to distinct nodes, effectively breaking the symmetry that limits standard GNNs. The framework accommodates both independent and identically distributed (i.i.d.) random features and deterministic unique identifiers (or their random permutations).
Approximation Framework: The study leverages classical universal approximation theorems for FNNs (e.g., Leshno et al., 1993) but adapts them to the graph domain. The key insight is that if node features are unique, any permutation-equivariant function can be represented as a composition of FNNs acting on these unique features.
Expectation-Based Equivariance: Recognizing that pathwise permutation equivariance is broken by fixed random features, the authors analyze permutation equivariance in expectation. They propose averaging PENNs over multiple resampled random features to recover equivariance properties while retaining high expressiveness.

Key Contributions

1. Universal Approximation Theorems

The paper establishes that PENNs augmented with random features are universal approximators for measurable permutation-invariant and permutation-equivariant functions on directed graphs with fixed size and multidimensional node/edge features.

Generality: Unlike prior work (e.g., Abboud et al., 2020; Puny et al., 2020), this result does not require the target function to be continuous, nor does it assume compactness or finiteness of the feature space. It applies to measurable functions on unbounded domains.
Concrete Architecture: The authors specify a concrete architecture (PENNs) for which universality holds, rather than merely asserting the existence of some abstract architecture.
Probability: The approximation holds with arbitrarily high probability, provided the random features induce unique node identifiers.

2. Approximation Rates and Complexity Bounds

For $k$ -times continuously differentiable functions ( $k \ge 2$ ) defined on compact domains, the paper derives explicit upper bounds on the complexity of the PENN components required to achieve a desired approximation error $\varepsilon$ .

Depth: The required number of layers grows logarithmically with respect to $1/\varepsilon$ ( $O(\log(1/\varepsilon))$ ).
Width/Weights: The number of nonzero weights grows polynomially with respect to $1/\varepsilon$ , specifically as $O(\varepsilon^{-c/(k-1)})$ , where $c$ depends on the graph dimensions ( $N, d, d'$ ).
Curse of Dimensionality: The bounds reflect a form of the curse of dimensionality regarding the graph domain, but the severity is mitigated for functions with higher regularity ( $k$ ).

3. Permutation Equivariance in Expectation

The paper addresses the trade-off between expressiveness and symmetry. While a single realization of a PENN with random features is not pathwise permutation-equivariant, the authors prove that the expectation of the PENN output (conditional on the graph input) is permutation-equivariant. Furthermore, they show that averaging over a finite number of i.i.d. random feature samples preserves the universal approximation property while improving the bias toward equivariance.

Results

Theorem 9: Establishes that for any measurable permutation-equivariant function $f$ and any $\varepsilon, \delta > 0$ , there exists a PENN with random features such that the probability of the approximation error exceeding $\varepsilon$ is at most $\delta$ .
Theorem 11: Provides a measure-theoretic version of the universality result, applicable when the graph distribution itself induces unique node features.
Theorem 16: Demonstrates that the averaged PENN (using $M$ i.i.d. copies of random features) also satisfies the universal approximation property, with the probability of error bounded by $\delta$ .
Theorem 18: Provides the quantitative approximation rates. It proves that for sufficiently regular functions, PENNs with specific architectural constraints (depth and width) can uniformly approximate the target function with high probability. The complexity bounds mirror those known for standard feedforward neural networks.

Significance and Claims

The authors claim that this work fills substantial gaps in the theoretical understanding of GNNs:

Bridging Theory and Practice: By proving universality for a concrete, memory-efficient architecture (PENNs) rather than abstract models, the results provide a theoretical foundation for using random features in practical GNN applications.
Generalization of Existing Results: The results generalize previous universality theorems by relaxing assumptions on continuity, compactness, and the nature of the target functions (measurable vs. continuous).
Practical Guidance: The derived approximation rates offer theoretical guidance for selecting hyperparameters (depth and width) based on the desired accuracy and the regularity of the target function.
Benchmarking: The authors suggest that PENNs with random features should be considered strong baselines for graph learning tasks, either as competitive alternatives to state-of-the-art models or as a reference point to validate the capabilities of other architectures.

The paper concludes that while random features may introduce a loss of pathwise equivariance, the resulting models possess superior expressive power and, when averaged, retain desirable symmetry properties, making them a robust theoretical and practical tool for graph learning.