Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling
Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling
复制标题
DOI：
10.48550/arxiv.2207.03584
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Hongkang Li;M. Wang;Sijia Liu;Pin-Yu Chen;Jinjun Xiong
中科院分区：
文献类型：
--
作者：
Hongkang Li;M. Wang;Sijia Liu;Pin-Yu Chen;Jinjun Xiong
图卷积网络（GCN）最近在学习图结构数据方面取得了巨大的实证成功。为了解决由于相邻特征的递归嵌入而导致的可扩展性问题，人们提出了图拓扑采样来降低训练GCN的内存和计算成本，并且在许多实证研究中，它取得了与未进行拓扑采样相当的测试性能。据我们所知，本文首次从理论上证明了在训练（至多）三层用于半监督节点分类的GCN时进行图拓扑采样的合理性。我们正式描述了图拓扑采样的一些充分条件，使得GCN训练能够导致泛化误差减小。此外，我们的方法解决了层间权重的非凸相互作用问题，这在现有的GCN理论分析中尚未得到充分探讨。本文明确阐述了图结构和拓扑采样对泛化性能和样本复杂度的影响，并且理论发现也通过数值实验得到了验证。
Graph convolutional networks (GCNs) have recently achieved great empirical success in learning graph-structured data. To address its scalability issue due to the recursive embedding of neighboring features, graph topology sampling has been proposed to reduce the memory and computational cost of training GCNs, and it has achieved comparable test performance to those without topology sampling in many empirical studies. To the best of our knowledge, this paper provides the first theoretical justification of graph topology sampling in training (up to) three-layer GCNs for semi-supervised node classification. We formally characterize some sufficient conditions on graph topology sampling such that GCN training leads to a diminishing generalization error. Moreover, our method tackles the nonconvex interaction of weights across layers, which is under-explored in the existing theoretical analyses of GCNs. This paper characterizes the impact of graph structures and topology sampling on the generalization performance and sample complexity explicitly, and the theoretical findings are also justified through numerical experiments.