Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks

Graph neural networks (GNNs) rely on message passing over graph edges, making their computational and memory costs strongly dependent on graph density. Graph sparsification offers a natural way to reduce these costs, but removing edges indiscriminately can distort important communication structure and degrade predictive performance. We introduce $\text{Scaffold}$, a topology-based, unsupervised graph sparsification framework derived from support graph theory preconditioners. $\text{Scaffold}$ explicitly controls two complementary structural quantities: *dilation*, which measures the length of rerouting paths induced by removed edges, and *congestion*, which measures how strongly these rerouted paths concentrate on the retained support. By jointly controlling dilation and congestion, $\text{Scaffold}$ preserves short communication paths while avoiding structural bottlenecks. To our knowledge, $\text{Scaffold}$ is the first scalable GNN sparsification framework to use a joint supporting-path dilation-congestion criterion. Across $19$ homophilic and heterophilic benchmarks spanning small to large graphs, $\text{Scaffold}$ achieves the best aggregate rank among the evaluated sparsification and related methods. Using only 10%-50% of the original edges per sparse support, $\text{Scaffold}$ recovers or closely approaches full-graph GNN performance while using less than half the memory of full-graph training and reducing end-to-end training time, including sparsification overhead. We provide an open-source software package at [anonymous.4open.science/r/Scaffold-B6DB](https://anonymous.4open.science/r/Scaffold-B6DB/README.md).