Graph neural networks (GNNs) are effective models for representation learning
on relational data. However, standard GNNs are limited in their expressive
power, as they cannot distinguish graphs beyond the capability of the
Weisfeiler-Leman graph isomorphism heuristic. In order to break this
expressiveness barrier, GNNs have been enhanced with random node initialization
(RNI), where the idea is to train and run the models with randomized initial
node features. In this work, we analyze the expressive power of GNNs with RNI,
and prove that these models are universal, a first such result for GNNs not
relying on computationally demanding higher-order properties. This universality
result holds even with partially randomized initial node features, and
preserves the invariance properties of GNNs in expectation. We then empirically
analyze the effect of RNI on GNNs, based on carefully constructed datasets. Our
empirical findings support the superior performance of GNNs with RNI over
standard GNNs.

本文分析了具有随机节点初始化的 GNNs 的表达力，证明了这些模型是通用的，这是 GNNs 的首个不依赖于计算要求更高阶特性的结果。我们基于精心构建的数据集，对 RNI 对 GNNs 的影响进行了经验分析。我们的实证结果支持 RNI 对于 GNNs 的优异表现。