TY - JOUR
T1 - Graph over-parameterization
T2 - Why the graph helps the training of deep graph convolutional network
AU - Lin, Yucong
AU - Li, Silu
AU - Xu, Jiaxing
AU - Xu, Jiawei
AU - Huang, Dong
AU - Zheng, Wendi
AU - Cao, Yuan
AU - Lu, Junwei
N1 - Publisher Copyright:
© 2023 Elsevier B.V.
PY - 2023/5/14
Y1 - 2023/5/14
N2 - Recent studies show that gradient descent can train a deep neural network (DNN) to achieve small training and test errors when the DNN is sufficiently wide. This result applies to various over-parameterized neural network models including fully-connected neural networks and convolutional neural networks. However, existing theory does not apply to graph convolutional networks (GCNs), as GCNs is built according to the topological structures of the data. It has been empirically observed that GCNs can outperform vanilla neural networks when the underlying graph captures geometric information of the data. However, there is few theoretical justification of such observation. In this paper, we establish theoretical guarantees of the high-probability convergence of gradient descent for training over-parameterized GCNs. Specifically, we introduce a novel measurement of the relation between the graph and the data, called the “graph disparity coefficient”, and show that the convergence of GCN is faster when the graph disparity coefficient is smaller. Our analysis provides novel insights into how the graph convolution operation in a GCN helps training, and provides useful guidance for GCN training in practice.
AB - Recent studies show that gradient descent can train a deep neural network (DNN) to achieve small training and test errors when the DNN is sufficiently wide. This result applies to various over-parameterized neural network models including fully-connected neural networks and convolutional neural networks. However, existing theory does not apply to graph convolutional networks (GCNs), as GCNs is built according to the topological structures of the data. It has been empirically observed that GCNs can outperform vanilla neural networks when the underlying graph captures geometric information of the data. However, there is few theoretical justification of such observation. In this paper, we establish theoretical guarantees of the high-probability convergence of gradient descent for training over-parameterized GCNs. Specifically, we introduce a novel measurement of the relation between the graph and the data, called the “graph disparity coefficient”, and show that the convergence of GCN is faster when the graph disparity coefficient is smaller. Our analysis provides novel insights into how the graph convolution operation in a GCN helps training, and provides useful guidance for GCN training in practice.
KW - Graph convolutional neural network
KW - Over-parameterization
UR - https://www.scopus.com/pages/publications/85149840724
U2 - 10.1016/j.neucom.2023.02.054
DO - 10.1016/j.neucom.2023.02.054
M3 - Article
AN - SCOPUS:85149840724
SN - 0925-2312
VL - 534
SP - 77
EP - 85
JO - Neurocomputing
JF - Neurocomputing
ER -