The Expressive Power of Random-Feature MPNNs Across Graph Sizes
The research investigates Message-Passing Neural Networks (MPNNs) using continuous random node features. It proves that these continuous features can be effectively replaced by a finite set of 'colors' with small error, allowing researchers to transfer limitations from finite-color models to size-uniform approximation. The findings establish strict lower bounds on the required number of trials and colors for statistical distinguishability.