Timezone: »
Poster
A Convergence Analysis of Gradient Descent on Graph Neural Networks
Pranjal Awasthi · Abhimanyu Das · Sreenivas Gollapudi
Graph Neural Networks~(GNNs) are a powerful class of architectures for solving learning problems on graphs. While many variants of GNNs have been proposed in the literature and have achieved strong empirical performance, their theoretical properties are less well understood. In this work we study the convergence properties of the gradient descent algorithm when used to train GNNs. In particular, we consider the realizable setting where the data is generated from a network with unknown weights and our goal is to study conditions under which gradient descent on a GNN architecture can recover near optimal solutions. While such analysis has been performed in recent years for other architectures such as fully connected feedforward networks, the message passing nature of the updates in a GNN poses a new challenge in understanding the nature of the gradient descent updates. We take a step towards overcoming this by proving that for the case of deep linear GNNs gradient descent provably recovers solutions up to error $\epsilon$ in $O(\text{log}(1/\epsilon))$ iterations, under natural assumptions on the data distribution. Furthermore, for the case of oneround GNNs with ReLU activations, we show that gradient descent provably recovers solutions up to error $\epsilon$ in $O(\frac{1}{\epsilon^2} \log(\frac{1}{\epsilon}))$ iterations.
Author Information
Pranjal Awasthi (Google)
Abhimanyu Das (University of Southern California)
Sreenivas Gollapudi (Google Research)
More from the Same Authors

2021 Spotlight: On the Existence of The Adversarial Bayes Classifier »
Pranjal Awasthi · Natalie Frank · Mehryar Mohri 
2021 Spotlight: Calibration and Consistency of Adversarial Surrogate Losses »
Pranjal Awasthi · Natalie Frank · Anqi Mao · Mehryar Mohri · Yutao Zhong 
2021 Poster: On the Existence of The Adversarial Bayes Classifier »
Pranjal Awasthi · Natalie Frank · Mehryar Mohri 
2021 Poster: Efficient Algorithms for Learning Depth2 Neural Networks with General ReLU Activations »
Pranjal Awasthi · Alex Tang · Aravindan Vijayaraghavan 
2021 Poster: Contextual Recommendations and LowRegret CuttingPlane Algorithms »
Sreenivas Gollapudi · Guru Guruganesh · Kostas Kollias · Pasin Manurangsi · Renato Leme · Jon Schneider 
2021 Poster: Neural Active Learning with Performance Guarantees »
Zhilei Wang · Pranjal Awasthi · Christoph Dann · Ayush Sekhari · Claudio Gentile 
2021 Poster: Calibration and Consistency of Adversarial Surrogate Losses »
Pranjal Awasthi · Natalie Frank · Anqi Mao · Mehryar Mohri · Yutao Zhong 
2020 Poster: Adaptive Probing Policies for Shortest Path Routing »
Aditya Bhaskara · Sreenivas Gollapudi · Kostas Kollias · Kamesh Munagala