  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.

Machine Learning