# The Expressive Power of Random-Feature MPNNs Across Graph Sizes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 36 references that are in the map.
- First posted on arXiv 8 Oct 2026.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [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)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Building powerful and equivariant graph neural networks with structural message-passing](https://mlsanity.com/paper/2006.15107/) (2020)
- [Coloring graph neural networks for node disambiguation](https://mlsanity.com/paper/1912.06058/) (2019)
- [Transformers are Universal In-context Learners](https://mlsanity.com/paper/2408.01367/) (2024)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [Distinguished In Uniform: Self Attention Vs. Virtual Nodes](https://mlsanity.com/paper/2405.11951/) (2024)
- [Graph neural networks extrapolate out-of-distribution for shortest paths](https://mlsanity.com/paper/2503.19173/) (2025)
- [On Transferring Transferability: Towards a Theory for Size Generalization](https://mlsanity.com/paper/2505.23599/) (2025)
- [Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit](https://mlsanity.com/paper/2505.00291/) (2025)
- [Which Algorithms Can Graph Neural Networks Learn?](https://mlsanity.com/paper/2602.13106/) (2026)
- [Any-Dimensional Invariant Universality](https://mlsanity.com/paper/2605.23156/) (2026)
- [Universality and Approximation Rates of Graph Neural Networks with Random Features](https://mlsanity.com/paper/2607.26699/) (2026)
- [Some remarks on the uncolored versions of the original CFI-graphs](https://mlsanity.com/paper/2507.01459/) (2025)

## Abstract (arXiv)

Continuous random node features increase the expressivity of message-passing neural networks (MPNNs), but existing theoretical analyses are not fine-grained enough to capture their limitations, particularly in approximating functions across graph sizes or under a fixed number of random bits. We develop a population-level framework for size-uniform approximation. For MPNNs with a graph-size-independent Lipschitz bound in their initial features, including standard mean, max, and order-normalized sum architectures, we show that continuous random features can be quantized to finitely many colors with arbitrarily small uniform error in expected output. This reduction lets us transfer limitations on finite-color distinguishability to limitations on size-uniform approximation with continuous random features. We use this framework to prove that these MPNNs are not size-uniformly universal, analyze the expressivity gains from colors and independent trials, and establish incomparability between random-color MPNNs and higher-order Weisfeiler-Leman methods. We also give finite-color MPNN constructions for tree subgraph isomorphism via color coding and a local MST task.