Random features limit graph neural network power across graph sizes
The Expressive Power of Random-Feature MPNNs Across Graph Sizes
Machine Learning
Summary
Graphs are like networks of connected points, and special neural networks called MPNNs try to understand them. Adding random features to these networks helps, but it turns out there are clear limits, especially when graphs get bigger or when we try to keep randomness simple. The authors developed a way to study these limits more precisely and found that even with random features, these networks can’t perfectly handle all graph sizes or problems. They also compared these methods to other complex graph analysis techniques and showed when one is better than the other.
What this means in practice
- •For graph neural network engineers: Design better graph neural networks by understanding expressivity limits related to graph sizes and random features.
- •For algorithm developers: Use finite-color MPNN constructions to detect tree-like structures in graph data efficiently.
A theory result. No direct application yet.
Authors
Robert R. Nerem, Mitchell Black, Antonis Vasileiou, Christopher Morris, Yusu Wang
Abstract
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.