Timezone: »

 
Poster
Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case
shuai zhang · Meng Wang · Sijia Liu · Pin-Yu Chen · Jinjun Xiong

Tue Jul 14 07:00 AM -- 07:45 AM & Tue Jul 14 06:00 PM -- 06:45 PM (PDT) @
in Poster Session 1 »

Although graph neural networks (GNNs) have made great progress recently on learning from graph-structured data in practice, their theoretical guarantee on generalizability remains elusive in the literature. In this paper, we provide a theoretically-grounded generalizability analysis of GNNs with one hidden layer for both regression and binary classification problems. Under the assumption that there exists a ground-truth GNN model (with zero generalization error), the objective of GNN learning is to estimate the ground-truth GNN parameters from the training data. To achieve this objective, we propose a learning algorithm that is built on tensor initialization and accelerated gradient descent. We then show that the proposed learning algorithm converges to the ground-truth GNN model for the regression problem, and to a model sufficiently close to the ground-truth for the binary classification problem. Moreover, for both cases, the convergence rate of the proposed learning algorithm is proven to be linear and faster than the vanilla gradient descent algorithm. We further explore the relationship between the sample complexity of GNNs and their underlying graph properties. Lastly, we provide numerical experiments to demonstrate the validity of our analysis and the effectiveness of the proposed learning algorithm for GNNs.

Keywords: Learning Theory · Non-convex Optimization · Optimization · Semi-supervised learning · Unsupervised and Semi-supervised Learning

Author Information

shuai zhang (Rensselaer Polytechnic Institute)
Meng Wang (Rensselaer Polytechnic Institute)
Sijia Liu (MIT-IBM Watson AI Lab)

Sijia Liu is a Research Staff Member at MIT-IBM Watson AI Lab, IBM research. Prior to joining in IBM Research, he was a Postdoctoral Research Fellow at the University of Michigan, Ann Arbor. He received the Ph.D. degree (with All University Doctoral Prize) in electrical and computer engineering from Syracuse University, NY, USA, in 2016. His recent research interests include deep learning, adversarial machine learning, gradient-free optimization, nonconvex optimization, and graph data analytics. He received the Best Student Paper Finalist Award at Asilomar Conference on Signals, Systems, and Computers (Asilomar'13). He received the Best Student Paper Award at the 42nd IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP'17). He served as a general chair of the Symposium 'Signal Processing for Adversarial Machine Learning' at GlobalSIP, 2018. He is also the co-chair of the workshop 'Adversarial Learning Methods for Machine Learning and Data Mining' at KDD, 2019.

Pin-Yu Chen (IBM Research AI)
Jinjun Xiong (IBM Thomas J. Watson Research Center)

More from the Same Authors