Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks

Graph neural networks (GNNs) tend to suffer from high computation costs due to the exponentially increasing scale of graph data and a large number of model parameters, which restricts their utility in practical applications. To this end, some recent works focus on sparsifying GNNs (including graph structures and model parameters) with the lottery ticket hypothesis (LTH) to reduce inference costs while maintaining performance levels. However, the LTH-based methods suffer from two major drawbacks: 1) they require exhaustive and iterative training of dense models, resulting in an extremely large training computation cost, and 2) they only trim graph structures and model parameters but ignore the node feature dimension, where vast redundancy exists. To overcome the above limitations, we propose a comprehensive graph gradual pruning framework termed CGP. This is achieved by designing a during-training graph pruning paradigm to dynamically prune GNNs within one training process. Unlike LTH-based methods, the proposed CGP approach requires no retraining, which significantly reduces the computation costs. Furthermore, we design a cosparsifying strategy to comprehensively trim all the three core elements of GNNs: graph structures, node features, and model parameters. Next, to refine the pruning operation, we introduce a regrowth process into our CGP framework, to reestablish the pruned but important connections. The proposed CGP is evaluated over a node classification task across six GNN architectures, including shallow models [graph convolutional network (GCN) and graph attention network (GAT)], shallow-but-deep-propagation models [simple graph convolution (SGC) and approximate personalized propagation of neural predictions (APPNP)], and deep models [GCN via initial residual and identity mapping (GCNII) and residual GCN (ResGCN)], on a total of 14 real-world graph datasets, including large-scale graph datasets from the challenging Open Graph Benchmark (OGB). Experiments reveal that the proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of the existing methods.

I. Introduction

Graph neural networks (GNNs) [1], [2], [3], [4] have achieved notable success in a variety of applications [5], [6], [7], [8] and have consequently become a rapidly growing area of research [9], [10], [11], [12]. Despite success, GNNs exhibit exponentially growing computation costs with the size of the graph data [13] and the complexity of the model structure increasing [14], [15], [16], during both training and inference [17]. This has proved prohibitive to their deployment in resource-constrained or time-sensitive applications. For example, a two-layer graph convolutional network (GCN) model [1] with 32 hidden units requires approximately 19 GFLOPs (flops: floating point operations) to process the Reddit graph [18], [19], twice as much as the requirements of the ResNet50 model [20] on ImageNet. If the number of layers of the GCN model increases to 64, the model requires approximately 73 GFLOPs. Such enormous computation costs of GNNs are primarily due to three aspects: 1) the large-scale adjacency matrix in real-world datasets (e.g., millions of edges in the OGB datasets [13]); 2) the high-dimensional node feature vectors (e.g., each node in the Citeseer graph has 3703 features); and 3) the sheer number of model parameters (e.g., a 64-layer GCN via initial residual and identity mapping (GCNII) [16] with 64 hidden units contains about 262144 parameters).