Graph Neural Networks with Random Features Achieve Universal Approximation.

This paper explores the theoretical capabilities of message-passing Graph Neural Networks (GNNs) that incorporate random node features. Random features are known to improve GNN expressiveness both in theory and practice. The authors present a novel universality result specifically for permutation-equivariant neural networks (PENNs), a broad category of GNNs constructed from feedforward neural network components. The findings demonstrate that PENNs, when combined with partially random node features, can approximate any measurable permutation-invariant or permutation-equivariant function on fixed-size directed graphs with multi-dimensional node and edge features, doing so arbitrarily well in probability. Furthermore, for functions that are k-times continuously differentiable (where k is 2 or greater), the research provides upper bounds on the approximation rates. These bounds connect the complexity of the PENN's feedforward components, in terms of layer depth and the number of non-zero weights, to the desired level of approximation accuracy.