Graph neural networks speed up by cutting less important connections
Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks
Machine Learning
Summary
Graph neural networks work by sharing information along connected paths. The authors developed Scaffold, a method that carefully removes some connections to make networks faster and use less memory without hurting how well they work. Scaffold keeps communication efficient by balancing how much information detours and how crowded those detours get after removals. Their tests show Scaffold matches or gets close to full network performance while speeding up training and using less memory on many different graphs.
What this means in practice
- •For machine learning engineers: Cut training time and memory usage for graph neural networks in large-scale applications by using Scaffold sparsification without losing accuracy.
- •For social network analysts: Analyze large social graphs faster by reducing graph complexity while preserving important communication paths with Scaffold.
Authors
Siddhartha Shankar Das, Sai Karthik Navuluru, S M Ferdous, Ryan A. Rossi, Baris Coskunuzer, Lakshman Tamil, Edoardo Serra, Alex Pothen, Robert Rallo, Mahantesh M Halappanavar
Abstract
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 Scaffold, a topology-based, unsupervised graph sparsification framework derived from support graph theory preconditioners. 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, Scaffold preserves short communication paths while avoiding structural bottlenecks. To our knowledge, 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, Scaffold achieves the best aggregate rank among the evaluated sparsification and related methods. Using only 10%-50% of the original edges per sparse support, 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 https://github.com/siddhartha047/Scaffold.