Graph neural networks (GNNs) are powerful machine learning models for various
graph learning tasks. Recently, the limitations of the expressive power of
various GNN models have been revealed. For example, GNNs cannot distinguish
some non-isomorphic graphs and they cannot learn efficient graph algorithms. In
this paper, we demonstrate that GNNs become powerful just by adding a random
feature to each node. We prove that the random features enable GNNs to learn
almost optimal polynomial-time approximation algorithms for the minimum
dominating set problem and maximum matching problem in terms of approximation
ratios. The main advantage of our method is that it can be combined with
off-the-shelf GNN models with slight modifications. Through experiments, we
show that the addition of random features enables GNNs to solve various
problems that normal GNNs, including the graph convolutional networks (GCNs)
and graph isomorphism networks (GINs), cannot solve.

本文研究了图神经网络的表达能力，发现其存在局限性。作者提出为每个节点添加随机特征，这样 GNN 就能够学习一些最优多项式时间近似算法，同时该方法方便与其他 GNN 模型结合使用。经实验证明，加入随机特征的 GNN 能够解决一些无法被传统的 GNN 模型解决的问题。