Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth
Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth
复制标题
DOI：
--
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Keyulu Xu;Mozhi Zhang;S. Jegelka;Kenji Kawaguchi
中科院分区：
文献类型：
--
作者：
Keyulu Xu;Mozhi Zhang;S. Jegelka;Kenji Kawaguchi
图形神经网络（GNN）已从表达能力和概括的镜头进行了研究。但是，它们的优化属性知之甚少。我们通过研究GNN的梯度动力学迈出了分析GNN培训的第一步。首先，我们分析了线性化的GNN，并证明，尽管训练没有跨度，但在我们在现实世界图上验证的温和假设下，保证以线性速率收敛到全球最低。其次，我们研究可能影响GNNS训练速度的原因。我们的结果表明，通过跳过连接，更深的深度和/或良好的标签分布，GNN的训练被隐式加速。经验结果证实，我们线性化GNN的理论结果与非线性GNN的训练行为保持一致。我们的结果为GNN在优化方面具有跳过连接的成功提供了第一个理论支持，并建议具有跳过连接的深度GNN在实践中有希望。
Graph Neural Networks (GNNs) have been studied from the lens of expressive power and generalization. However, their optimization properties are less well understood. We take the first step towards analyzing GNN training by studying the gradient dynamics of GNNs. First, we analyze linearized GNNs and prove that despite the non-convexity of training, convergence to a global minimum at a linear rate is guaranteed under mild assumptions that we validate on real-world graphs. Second, we study what may affect the GNNs' training speed. Our results show that the training of GNNs is implicitly accelerated by skip connections, more depth, and/or a good label distribution. Empirical results confirm that our theoretical results for linearized GNNs align with the training behavior of nonlinear GNNs. Our results provide the first theoretical support for the success of GNNs with skip connections in terms of optimization, and suggest that deep GNNs with skip connections would be promising in practice.