Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth

Keyulu Xu, Mozhi Zhang, Stefanie Jegelka, Kenji Kawaguchi
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:11592-11602, 2021.

Abstract

Graph Neural Networks (GNNs) have been studied through 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-xu21k, title = {Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth}, author = {Xu, Keyulu and Zhang, Mozhi and Jegelka, Stefanie and Kawaguchi, Kenji}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {11592--11602}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/xu21k/xu21k.pdf}, url = {https://proceedings.mlr.press/v139/xu21k.html}, abstract = {Graph Neural Networks (GNNs) have been studied through 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.} }
Endnote
%0 Conference Paper %T Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth %A Keyulu Xu %A Mozhi Zhang %A Stefanie Jegelka %A Kenji Kawaguchi %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-xu21k %I PMLR %P 11592--11602 %U https://proceedings.mlr.press/v139/xu21k.html %V 139 %X Graph Neural Networks (GNNs) have been studied through 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.
APA
Xu, K., Zhang, M., Jegelka, S. & Kawaguchi, K.. (2021). Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:11592-11602 Available from https://proceedings.mlr.press/v139/xu21k.html.

Related Material