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

arXiv: https://arxiv.org/abs/2105.04550 · HTML: https://mlsanity.com/paper/2105.04550/

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 72 references that are in the map.
- First posted on arXiv 10 May 2021.

## Builds on (most cited first, 30 of 58)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [Molecular Graph Convolutions: Moving Beyond Fingerprints](https://mlsanity.com/paper/1603.00856/) (2016)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)

## Built on by (most cited first, 30 of 55)

- [Training Graph Neural Networks with 1000 Layers](https://mlsanity.com/paper/2106.07476/) (2021)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs](https://mlsanity.com/paper/2202.05441/) (2022)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [When Do Extended Physics-Informed Neural Networks (XPINNs) Improve Generalization?](https://mlsanity.com/paper/2109.09444/) (2021)
- [How Powerful is Graph Convolution for Recommendation?](https://mlsanity.com/paper/2108.07567/) (2021)
- [Augmented Physics-Informed Neural Networks (APINNs): A gating network-based soft domain decomposition methodology](https://mlsanity.com/paper/2211.08939/) (2022)
- [Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs](https://mlsanity.com/paper/2212.09034/) (2022)
- [Bag of Tricks for Training Deeper Graph Neural Networks: A Comprehensive Benchmark Study](https://mlsanity.com/paper/2108.10521/) (2021)
- [Graph Neural Networks with Learnable and Optimal Polynomial Bases](https://mlsanity.com/paper/2302.12432/) (2023)
- [Multi-agent Reinforcement Learning: A Comprehensive Survey](https://mlsanity.com/paper/2312.10256/) (2023)
- [Deep Active Learning by Leveraging Training Dynamics](https://mlsanity.com/paper/2110.08611/) (2021)
- [Scalable deeper graph neural networks for high-performance materials property prediction](https://mlsanity.com/paper/2109.12283/) (2021)
- [Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling](https://mlsanity.com/paper/2207.03584/) (2022)
- [Graph Neural Bandits](https://mlsanity.com/paper/2308.10808/) (2023)
- [Evaluating Deep Graph Neural Networks](https://mlsanity.com/paper/2108.00955/) (2021)
- [Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks](https://mlsanity.com/paper/2302.02922/) (2023)
- [Expressive Sign Equivariant Networks for Spectral Geometric Learning](https://mlsanity.com/paper/2312.02339/) (2023)
- [Graph ODEs and Beyond: A Comprehensive Survey on Integrating Differential Equations with Graph Neural Networks](https://mlsanity.com/paper/2503.23167/) (2025)
- [RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations](https://mlsanity.com/paper/2210.10737/) (2022)
- [Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons](https://mlsanity.com/paper/2306.13926/) (2023)
- [Understanding Dynamics of Nonlinear Representation Learning and Its Application](https://mlsanity.com/paper/2106.14836/) (2021)
- [BeMap: Balanced Message Passing for Fair Graph Neural Network](https://mlsanity.com/paper/2306.04107/) (2023)
- [The Snowflake Hypothesis: Training Deep GNN with One Node One Receptive field](https://mlsanity.com/paper/2308.10051/) (2023)
- [Are GATs Out of Balance?](https://mlsanity.com/paper/2310.07235/) (2023)
- [SG-PGM: Partial Graph Matching Network with Semantic Geometric Fusion for 3D Scene Graph Alignment and Its Downstream Tasks](https://mlsanity.com/paper/2403.19474/) (2024)
- [Neural Bandit with Arm Group Graph](https://mlsanity.com/paper/2206.03644/) (2022)
- [Deep graphical regression for jointly moderate and extreme Australian wildfires](https://mlsanity.com/paper/2308.14547/) (2023)
- [Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks](https://mlsanity.com/paper/2401.03350/) (2024)

## Abstract (arXiv)

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.