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