eduzhai > Applied Sciences > Engineering >

Fast Learning of Graph Neural Networks with Guaranteed Generalizability One-hidden-layer Case

  • Save

... pages left unread,continue reading

Document pages: 30 pages

Abstract: Although graph neural networks (GNNs) have made great progress recently onlearning from graph-structured data in practice, their theoretical guarantee ongeneralizability remains elusive in the literature. In this paper, we provide atheoretically-grounded generalizability analysis of GNNs with one hidden layerfor both regression and binary classification problems. Under the assumptionthat there exists a ground-truth GNN model (with zero generalization error),the objective of GNN learning is to estimate the ground-truth GNN parametersfrom the training data. To achieve this objective, we propose a learningalgorithm that is built on tensor initialization and accelerated gradientdescent. We then show that the proposed learning algorithm converges to theground-truth GNN model for the regression problem, and to a model sufficientlyclose to the ground-truth for the binary classification problem. Moreover, forboth cases, the convergence rate of the proposed learning algorithm is provento be linear and faster than the vanilla gradient descent algorithm. We furtherexplore the relationship between the sample complexity of GNNs and theirunderlying graph properties. Lastly, we provide numerical experiments todemonstrate the validity of our analysis and the effectiveness of the proposedlearning algorithm for GNNs.

Please select stars to rate!

         

0 comments Sign in to leave a comment.

    Data loading, please wait...
×