Learning Graph Neural Networks with Approximate Gradient Descent

• DOI: 10.1609/aaai.v35i10.17025
• Publication Date: 2022-09-08T19:19:30Z
• Authors: Qunwei Li; Shaofeng Zou; Wenliang Zhong
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology; Machine Learning (cs.LG)

The first provably efficient algorithm for learning graph neural networks (GNNs) with one hidden layer node information convolution is provided in this paper. Two types of GNNs are investigated, depending on whether labels attached to nodes or graphs. A comprehensive framework designing and analyzing convergence GNN training algorithms developed. proposed applicable a wide range activation functions including ReLU, Leaky Sigmod, Softplus Swish. It shown that the guarantees linear rate underlying true parameters GNNs. For both GNNs, sample complexity terms number graphs characterized. impact feature dimension structure also theoretically Numerical experiments further validate our theoretical analysis.