Random Features Strengthen Graph Neural Networks
Random Features Strengthen Graph Neural Networks
复制标题
DOI：
10.1137/1.9781611976700.38
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
R. Sato;M. Yamada;H. Kashima
中科院分区：
文献类型：
--
作者：
R. Sato;M. Yamada;H. Kashima
图神经网络（GNN）是用于各种图学习任务的强大机器学习模型。最近，各种 GNN 模型的表达能力的局限性被揭示出来。例如，GNN 无法区分一些非同构图，也无法学习有效的图算法，并且已经提出了几种 GNN 模型来克服这些限制。在本文中，我们证明只需向每个节点添加随机特征，GNN 就会变得强大。我们证明，随机特征使 GNN 能够在逼近率方面学习针对最小支配集问题和最大匹配问题的几乎最优多项式时间逼近算法。我们的方法的主要优点是它可以与现成的 GNN 模型相结合，只需稍加修改。通过实验，我们表明随机特征的添加使 GNN 能够解决普通 GNN（包括 GCN 和 GIN）无法解决的各种问题。
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, and several GNN models have been proposed to overcome these limitations. 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 the approximation ratio. 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 GCNs and GINs, cannot solve.