As graphs scale to billions of nodes and edges, graph Machine Learning workloads are constrained by the cost of multi-hop traversals over exponentially growing neighborhoods. While various system-level and algorithmic optimizations have been proposed to accelerate Graph Neural Network (GNN) pipelines, data management and movement remain the primary bottlenecks at scale. In this paper, we explore whether graph sparsification, a well-established technique that reduces edges to create sparser neighborhoods, can serve as a lightweight pre-processing step to address these bottlenecks while preserving accuracy on node classification tasks. We develop an extensible experimental framework that enables systematic evaluation of how different sparsification methods affect the performance and accuracy of GNN models. We conduct the first comprehensive study of GNN training and inference on sparsified graphs, revealing several key findings. First, sparsification often preserves or even improves predictive performance. As an example, random sparsification raises the accuracy of the GAT model by 6.8% on the PubMed graph. Second, benefits increase with scale, substantially accelerating both training and inference. Our results show that the K-Neighbor sparsifier improves model serving performance on the Products graph by 11.7x with only a 0.7% accuracy drop. Importantly, we find that the computational overhead of sparsification is quickly amortized, making it practical for very large graphs.
Figures & tables
Figure 1. Overview of our experimental framework
Dataset
Nodes
Edges
Feature Dim.
File Size
PubMed
19.7K
44.3K
500
54.5 MB
CoauthorCS
18.3K
81.9K
6805
477.8 MB
Arxiv
169.3K
1.2M
128
79.2 MB
Products
2.4M
61.9M
100
1.4 GB
Papers100M
111.1M
1.6B
128
56.2 GB
Table 1. Datasets we use in this study
Model
Architecture
PubMed
CoauthorCS
Arxiv
Products
Papers100M
GraphSAGE
Layers
2
2
5
5
3
Hidden size
256
64
128
256
256
Fanout
10
4
20
5
[15,10,5]
GAT
Layers
2
2
4
3
3
Hidden size
1024
64
256
128
256
Num heads
4
4
2
2
4
Table 2. Model hyperparameters for different datasets
Figure 2. Comparison of test accuracy and convergence speedup ratio of models trained on sparsified graphs over models trained on the original graphs. The star markers indicate configurations that achieved the best performance for each dataset-model pair. Light gray bars in the speedup plot indicate cases where the sparsification causes accuracy degradation above 1% .
Figure 3. Accuracy–time trade-off across graph sparsification methods. Each point shows a dataset-model-method result, with test accuracy on the y-axis and time to converge on the x-axis (log scale in seconds).
Figure 4. Time-to-target accuracy speedup across graph sparsification methods. Each panel corresponds to a dataset, with grouped bars showing the speedup factor for each sparsification method per model. The dashed line marks speedup =1× (no speedup). An “X” marker indicates that the method could not reach the target accuracy defined by the original graph.
Figure 5. Time to accuracy on the Products dataset. Each panel shows one model, with per-epoch test accuracy plotted against cumulative training time. The dashed horizontal line marks the target accuracy (best test accuracy on the original graph). Sparsification methods that cross the target line sooner achieve faster time to accuracy.
Figure 6. Cross-graph inference comparison grouped by model. Each subplot shows results for a single GNN architecture across all datasets, making it easy to compare how sparsification methods affect each model. Light gray bars in the speedup plot indicate more than 1% accuracy drop.
Figure 7. Stacked-bar breakdown of summarization overhead by component for each dataset. Bars include an "Others" segment to account for any residual time not captured by the measured components.
Dataset
Model
Single-run amortization
Random
K-Neighbor
Rank
Local
PubMed
GCN
✗
✗
✓
✗
GraphSAGE
✓
✗
✓
✓
GAT
✗
✗
✗
✗
SGformer
✓
✓
✗
✓
CoauthorCS
GCN
✗
✗
✓
✗
Table 3. Single-run amortization of processing costs. Checkmarks (✓) indicate that pre-processing overhead is amortized within a single training run; crosses (✗) indicate pre-processing cost exceeds single-run savings.
Figure 8. Sparsification parameter sweep on the Products dataset. Each panel shows one method with dual axes: scatter points on the left axis show test accuracy for GCN ( ∙ ), GraphSAGE ( ■ ), GAT ( ▲ ), and SGformer ( ⧫ ); gold bars on the right axis (inverted) show the edge reduction percentage. Dashed horizontal lines mark each model’s original-graph accuracy baseline.