Quantifying and Optimizing Graph Neural Network Sparsification with An Approximation Framework

Layer-wise approximation bounds and policies for general GNN sparsification.

Graph Neural Networks (GNNs) have shown promising performance in learning from graph-structured data, but at the cost of prohibitive computational overhead due to a series of graph-scale operators. To reduce redundant graph operations, previous studies attempt to sparsify the graph by pruning or sampling graph edges, which enables popular and practical GNN deployments in realistic tasks. However, these methods and their specific designs are mostly empirical, lacking a theoretical framework for bounding approximation precision and guiding sparsification policy. In this work, we present the first approximation theory for GNN sparsification that unifies both pruning and sampling paradigms, directly characterizing the representation error deviation in a layer-wise manner. Our theoretical bounds reveal that the pattern of error accumulation throughout iterative graph operators varies with key GNN model properties. Based on our framework, we further derive an optimal sparsification policy that minimizes the layer-wise approximation error under fixed computational constraints. Experimental evaluations on synthetic and real-world datasets confirm our theoretical findings on layer approximation bounds. Remarkably, our proposed optimal sparsification allocation reduces the representation error by up to $10\times$ and retains better prediction accuracy compared to canonical sampling strategies.