Quantifying and Optimizing Graph Neural Network Sparsification with an Approximation Framework

Abstract

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 GNN deployments in realistic tasks. However, these methods 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 confirm our theoretical findings on layer approximation bounds. Remarkably, our proposed optimal sparsification allocation reduces the representation error by up to 10× and retains better prediction accuracy compared to canonical sampling strategies. The code is available at https://github.com/Rechard16/QuOS/.