mlsanityData to 7 Oct 2026

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

arXiv 2105.04550 ↗First posted 10 May 2021cs.LG cs.CV math.OCcited by 55

Not on the map. Why?

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.

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

Builds on

58 of 72 references.

References · 58

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  7. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  8. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  9. 2019Simplifying Graph Convolutional Networkscited by 1,470
  10. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  11. 2020Simple and Deep Graph Convolutional Networkscited by 857
  12. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
38 more
  1. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  2. 2013Exact solutions to the nonlinear dynamics of learning in deep linear neural networkscited by 748
  3. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  4. 2018On Lazy Training in Differentiable Programmingcited by 671
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  6. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  8. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  9. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
  10. 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
  11. 2019Provably Powerful Graph Networkscited by 385
  12. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
  13. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  14. 2020DeeperGCN: All You Need to Train Deeper GCNscited by 249
  15. 2016Molecular Graph Convolutions: Moving Beyond Fingerprintscited by 238
  16. 2016Deep Learning without Poor Local Minimacited by 233
  17. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  18. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  19. 2020Random Features Strengthen Graph Neural Networkscited by 184
  20. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  21. 2018Adaptive Sampling Towards Fast Graph Representation Learningcited by 180
  22. 2018A Convergence Analysis of Gradient Descent for Deep Linear Neural Networkscited by 180
  23. 2019Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networkscited by 177
  24. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  25. 2020Directional convergence and alignment in deep learningcited by 172
  26. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  27. 2019What Can Neural Networks Reason About?cited by 155
  28. 2020On the linearity of large non-linear models: when and why the tangent kernel is constantcited by 129
  29. 2020GraphNorm: A Principled Approach to Accelerating Graph Neural Network Trainingcited by 116
  30. 2016Identity Matters in Deep Learningcited by 107
  31. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  32. 2018Attention-based Graph Neural Network for Semi-supervised Learningcited by 100
  33. 2019Dynamics of Deep Neural Networks and Neural Tangent Hierarchycited by 96
  34. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
  35. 2017Deep linear neural networks with arbitrary loss: All local minima are globalcited by 64
  36. 2018N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classificationcited by 54
  37. 2019Width Provably Matters in Optimization for Deep Linear Neural Networkscited by 52
  38. 2018Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networkscited by 44

50 most cited of 58 All 58 (JSON)

Built on by

Cited by year

Citing papers per year: 2021: 12; 2022: 10; 2023: 16; 2024: 9; 2025: 8.

55 papers.

Sort:

  1. 2021Training Graph Neural Networks with 1000 Layerscited by 169
  2. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  3. 2022Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphscited by 144
  4. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  5. 2022A Survey on Graph Representation Learning Methodscited by 66
  6. 2021When Do Extended Physics-Informed Neural Networks (XPINNs) Improve Generalization?cited by 57
  7. 2021How Powerful is Graph Convolution for Recommendation?cited by 50
  8. 2022Augmented Physics-Informed Neural Networks (APINNs): A gating network-based soft domain decomposition methodologycited by 43
  9. 2022Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPscited by 42
  10. 2021Bag of Tricks for Training Deeper Graph Neural Networks: A Comprehensive Benchmark Studycited by 36
  11. 2023Graph Neural Networks with Learnable and Optimal Polynomial Basescited by 36
  12. 2021Deep Active Learning by Leveraging Training Dynamicscited by 32
38 more
  1. 2023Multi-agent Reinforcement Learning: A Comprehensive Surveycited by 30
  2. 2021Scalable deeper graph neural networks for high-performance materials property predictioncited by 26
  3. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  4. 2023Graph Neural Banditscited by 20
  5. 2021Evaluating Deep Graph Neural Networkscited by 19
  6. 2023Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networkscited by 16
  7. 2023Expressive Sign Equivariant Networks for Spectral Geometric Learningcited by 15
  8. 2025Graph ODEs and Beyond: A Comprehensive Survey on Integrating Differential Equations with Graph Neural Networkscited by 14
  9. 2022RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computationscited by 12
  10. 2023Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptronscited by 12
  11. 2021Understanding Dynamics of Nonlinear Representation Learning and Its Applicationcited by 11
  12. 2023BeMap: Balanced Message Passing for Fair Graph Neural Networkcited by 11
  13. 2023The Snowflake Hypothesis: Training Deep GNN with One Node One Receptive fieldcited by 11
  14. 2024SG-PGM: Partial Graph Matching Network with Semantic Geometric Fusion for 3D Scene Graph Alignment and Its Downstream Taskscited by 10
  15. 2023Are GATs Out of Balance?cited by 9
  16. 2022Neural Bandit with Arm Group Graphcited by 8
  17. 2023Deep graphical regression for jointly moderate and extreme Australian wildfirescited by 8
  18. 2024Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networkscited by 8
  19. 2023Centered Self-Attention Layerscited by 7
  20. 2022Structure and position-aware graph neural network for airway labelingcited by 6
  21. 2021What training reveals about neural network complexitycited by 5
  22. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  23. 2023LON-GNN: Spectral GNNs with Learnable Orthonormal Basiscited by 4
  24. 2023How Graph Neural Networks Learn: Lessons from Training Dynamicscited by 3
  25. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  26. 2025Accurate and Scalable Graph Neural Networks via Message Invariancecited by 3
  27. 2025Efficient Mixed Precision Quantization in Graph Neural Networkscited by 3
  28. 2021Label Propagation across Graphs: Node Classification using Graph Neural Tangent Kernelscited by 2
  29. 2025Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block modelcited by 2
  30. 2025Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?cited by 2
  31. 2025Understanding Generalization in Node and Link Predictioncited by 2
  32. 2021AnchorGAE: General Data Clustering via O(n) Bipartite Graph Convolutioncited by 1
  33. 2022Dimensionality Reduction Meets Message Passing for Graph Node Embeddingscited by 1
  34. 2023DURENDAL: Graph deep learning framework for temporal heterogeneous networkscited by 1
  35. 2023Degree-based stratification of nodes in Graph Neural Networkscited by 1
  36. 2024On provable privacy vulnerabilities of graph representationscited by 1
  37. 2024Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approachcited by 1
  38. 2024Causality-based Subject and Task Fingerprints using fMRI Time-series Datacited by 1

50 most cited of 55 All 55 (JSON)