mlsanityData to 14 Oct 2026

The Expressive Power of Random-Feature MPNNs Across Graph Sizes

arXiv 2610.12809 ↗First posted 8 Oct 2026cs.LGcited by 0

Not on the map. Why?

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.

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

23 of 36 references.

References · 23

  1. 2018How Powerful are Graph Neural Networks?cited by 4,393
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  3. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  4. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 222
  5. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  6. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  7. 2020Random Features Strengthen Graph Neural Networkscited by 186
  8. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 124
  9. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  10. 2019Neural Execution of Graph Algorithmscited by 121
  11. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 106
  12. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 97
11 more
  1. 2019Coloring graph neural networks for node disambiguationcited by 52
  2. 2024Transformers are Universal In-context Learnerscited by 43
  3. 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 24
  4. 2024Distinguished In Uniform: Self Attention Vs. Virtual Nodescited by 20
  5. 2025Graph neural networks extrapolate out-of-distribution for shortest pathscited by 11
  6. 2025On Transferring Transferability: Towards a Theory for Size Generalizationcited by 10
  7. 2025Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limitcited by 4
  8. 2026Which Algorithms Can Graph Neural Networks Learn?cited by 4
  9. 2026Any-Dimensional Invariant Universalitycited by 3
  10. 2026Universality and Approximation Rates of Graph Neural Networks with Random Featurescited by 3
  11. 2025Some remarks on the uncolored versions of the original CFI-graphscited by 1

Built on by

Not cited yet.