  Due to the significant computational challenge of training large-scale graph
neural networks (GNNs), various sparse learning techniques have been exploited
to reduce memory and storage costs. Examples include \textit{graph
sparsification} that samples a subgraph to reduce the amount of data
aggregation and \textit{model sparsification} that prunes the neural network to
reduce the number of trainable weights. Despite the empirical successes in
reducing the training cost while maintaining the test accuracy, the theoretical
generalization analysis of sparse learning for GNNs remains elusive. To the
best of our knowledge, this paper provides the first theoretical
characterization of joint edge-model sparse learning from the perspective of
sample complexity and convergence rate in achieving zero generalization error.
It proves analytically that both sampling important nodes and pruning neurons
with the lowest-magnitude can reduce the sample complexity and improve
convergence without compromising the test accuracy. Although the analysis is
centered on two-layer GNNs with structural constraints on data, the insights
are applicable to more general setups and justified by both synthetic and
practical citation datasets.
