论文标题
随机特征增强图形神经网络
Random Features Strengthen Graph Neural Networks
论文作者
论文摘要
图形神经网络（GNN）是针对各种图形学习任务的强大机器学习模型。最近，已经揭示了各种GNN模型的表达能力的局限性。例如，GNN无法区分某些非晶格图，也无法学习有效的图形算法。在本文中，我们仅通过向每个节点添加一个随机功能来证明GNN变得强大。我们证明，随机特征使GNN能够学习最低统治设置问题的几乎最佳多项式近似算法，并且就近似值而言。我们方法的主要优点是它可以与现成的GNN型号结合使用，并进行稍微修改。通过实验，我们表明，随机特征的添加使GNN可以解决正常GNN（包括图形卷积网络（GCN）和图形同构网络（GINS））的各种问题。
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.
