Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks

Siddhartha Shankar Das; Sai Karthik Navuluru; S M Ferdous; Ryan A. Rossi; Baris Coskunuzer; Lakshman Tamil; Edoardo Serra; Alex Pothen

cs.LGSep 25, 2026

Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks

Authors: Siddhartha Shankar Das, Sai Karthik Navuluru, S M Ferdous, Ryan A. Rossi, Baris Coskunuzer, Lakshman Tamil, Edoardo Serra, Alex Pothen, +2 more

Organizations: Pacific Northwest National Laboratory · University of Texas at Dallas · University of North Carolina at Charlotte · Adobe · Boise State University · Purdue University

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.

Figures & tables

Figure 1: Runtime, memory, and accuracy trade-off.

Figure 2: Support-graph features: (a) sparse support, (b) dilation, (c) edge congestion, and (d) node congestion. Darker edges and larger nodes indicate higher path loads; node loads exclude endpoints.

Figure 3: Starting from a spanning backbone, Scaffold repeatedly scores the omitted edges, retains the highest-scoring candidate, and refreshes the support until the target budget is reached.

Variant	Scoring / selection	Complexity	Graph $(n,m)$	Time (s)	Use
Greedy	dynamic, all; best one	$\mathcal{O}(TnC_{\mathrm{sp}})$	$(400,\,3.1\mathrm{K})$	0.78	reference
Heap	dynamic, affected; heap max.	$\mathcal{O}((n+T(\kappa+c))C_{\mathrm{sp}}+m\log m)$	$(4\mathrm{K},\,39.9\mathrm{K})$	25.16	small
Batch	dynamic, $b$ sampled; top- $r$	$\mathcal{O}(\lceil T/r\rceil bC_{\mathrm{sp}})$	$(10\mathrm{K},\,250\mathrm{K})$	31.01	medium/large
Fast	static on ${\mathcal{F}}$ ; top- $T$	$\mathcal{O}((m+n)\log n)$	$(200\mathrm{K},\,2.4\mathrm{M})$	2.30	large
Sample	static, $R$ forests; budgeted draw	$\mathcal{O}(R(m+n)\log n)$ pre.; $\mathcal{O}(m)$ draw	$(200\mathrm{K},\,2.4\mathrm{M})$	9.02	large

Table 1: Scaffold variants and measured runtime (

\delta=0.2

, 8 CPU workers).

Figure 4: Scaffold -1 uses one fixed

q

-edge support for training and inference, whereas Scaffold -

K

periodically refreshes

q

-edge supports, retains the validation-best

K

, and performs one inference pass on their union.

Panel of Figure 5 — Figure 5: Wilcoxon–Holm average-rank comparison over 19 datasets and 3 edge-retention ratios.

Ay (a) Dataset group I: Homophilic and Heterophilic

Method

Cora

CiteSeer

Am. Photo

WikiCS

Am. Comp.

Coauth. CS

PubMed

Coauth. Phys.

Chameleon

Squirrel

Target

\delta_{d}

0.7

0.7

0.3

0.3

0.3

0.5

0.5

0.3

0.3

0.3

|{\mathcal{V}}|/|{\mathcal{E}}|

2.71k/5.28k

3.33k/4.55k

7.65k/119.08k

11.70k/215.60k

13.75k/245.86k

18.33k/81.89k

19.72k/44.32k

34.49k/247.96k

0.89k/8.85k

2.22k/47.00k

Ref.

Full-graph

84.56 ±0.63

72.30 ±0.47

95.95 ±0.33

80.27 ±0.44

93.80 ±0.20

95.72 ±0.04

81.22 ±1.11

97.50 ±0.12

45.46 ±4.42

44.77 ±2.36

76.44

No graph

59.64 ±1.31

57.12 ±0.55

92.09 ±0.51

73.48 ±0.25

87.04 ±0.36

95.10 ±0.11

70.86 ±1.44

96.31 ±0.02

36.48 ±3.09

40.07 ±1.40

67.29

S. Forest

80.10 ±0.26

69.42 ±0.56

93.97 ±0.08

76.65 ±0.22

90.45 ±0.25

95.47 ±0.19

79.48 ±0.46

96.90 ±0.02

36.73 ±4.52

37.59 ±1.74

71.87

Table 2: Accuracy/ROC-AUC at dataset-specific targets

\delta_{d}\geq 0.3

above the spanning-forest floor. Scaffold -1 is ranked at the matched budget; Scaffold -

K

is unranked.

Figure 6: Performance gap of Scaffold -1 and Scaffold -

K

to the full graph across

\delta

. Blue marks results within

1\%

; stars mark the first such

\delta

, and gray marks below the spanning-forest.

Figure 7: Runtime/memory profile of Scaffold-Fast -1 with Gather-Scatter/SpMM aggregation in comparison to the Full-GCN.

Figure 8: (a) Standalone sparsification cost relative to Scaffold-Fast , and (b) total end-to-end cost relative to Scaffold-Sample -1 over

300

epochs at

\delta=0.3

. More details are in Appendix G .

Figure 9: Dilation achieves the best individual performance, while combining dilation and edge congestion gives the strongest accuracy–structure trade-off and association with test performance.

Figure 10: Support quality at

\delta=0.7

from a common spanning-forest backbone. Lower dilation and edge congestion generally correspond to higher GNN accuracy.

Figure 11: Quality–cost trade-offs across variants and backbones. SF : spanning forest; RandSF : random spanning forest; RandSPF : random shortest-path forest; SLSF : scalable low-stretch forest.

Appendix figures & tables29 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}},{\bm{w}})$ ; $n,m$	Input graph with $n=\|{\mathcal{V}}\|$ nodes and $m=\|{\mathcal{E}}\|$ edges.
${\mathcal{H}}_{t}$ ; ${\mathcal{F}}$	Current sparse support and initial spanning-forest backbone.
$\delta$ ; $q=\lceil\delta m\rceil$	Edge-retention ratio and target edge budget.
${\mathcal{I}}_{t}={\mathcal{E}}\setminus{\mathcal{E}}_{{\mathcal{H}}_{t}}$	Candidate edges omitted from the current support.
$P_{e}$	Supporting path of omitted edge $e$ in ${\mathcal{H}}_{t}$ .
$D({\mathcal{H}}),\,C_{E}({\mathcal{H}}),\,C_{V}({\mathcal{H}})$	Maximum dilation, edge congestion, and node congestion.

Appendix

Table 3: Core notation used in Scaffold .

Figure 12: Controlled roles of dilation and congestion in GNN message passing. Each row varies one support quantity while matching the other two at the same edge budget. High dilation causes finite-hop under-reaching, while high edge or node congestion creates shared communication bottlenecks.

Figure 13: Support-forest backbones on a connected

8\times 8

grid. (a) Input; (b)–(h) spanning-forest constructions with

63

retained edges (blue) and

49

omitted edges (dashes). Since the input is connected, each forest contains one tree. Panels report dilation

D

, edge and node congestion

C_{E},C_{V}

, and

\Phi=(1+D)(1+C_{E})(1+C_{V})

before edge additions. Green marks the lowest

\Phi

. MaxSF and MinSF coincide under unit weights; LLSF refines GLSF through local swaps.

Figure 14: (a) Greedy recomputes all paths and scores after each insertion. (b) Heap caches priorities and selectively refreshes affected candidates. (c) Batch scores sampled batches and inserts their top-

r

edges. (d) Fast scores candidates once on the initial backbone. (e) Sample aggregates randomized-backbone signals for repeated sparse draws.

Figure 15: Scaffold variants at a fixed edge budget. (a) Input grid. (b)–(f) Each variant retains

84

edges (

\delta=0.75

): a shared RandSF backbone (blue) and

21

added edges (green); dashed edges are omitted. Panels report dilation

D

, edge and node congestion

C_{E},C_{V}

, and

\Phi=(1+D)(1+C_{E})(1+C_{V})

. Green shading marks the lowest

\Phi

in this example.

		Time (s)
Variant	Graph $(n,m)$	$P{=}1$	$P{=}4$	$P{=}8$	Speedup
Scaffold-Greedy	$(400,\,3.1\mathrm{K})$	1.63	1.01	0.78	$2.08\times$
Scaffold-Heap	$(4\mathrm{K},\,39.9\mathrm{K})$	25.09	25.02	25.16	$1.00\times$
Scaffold-Batch	$(10\mathrm{K},\,250\mathrm{K})$	206.12	57.54	31.01	$6.65\times$
Scaffold-Fast	$(200\mathrm{K},\,2.4\mathrm{M})$	3.53	2.78	2.30	$1.54\times$
Scaffold-Sample	$(200\mathrm{K},\,2.4\mathrm{M})$	33.77	11.81	9.02	$3.74\times$

Appendix

Table 4: Complete Scaffold construction time at

\delta=0.2

Backbone	Complexity	$n=200\mathrm{K}$ $m=3.12\mathrm{M}$	$n=400$ $m=1.54\mathrm{K}$
		ms	ms
Fast-MaxSF/MinSF	$\mathcal{O}(m\alpha_{\rm UF}(n)+B)$	22.72–23.74	0.035–0.036
MaxSF/MinSF	$\mathcal{O}(m\log m)$	22.25–22.41	0.035
Fast-RandSF	$\mathcal{O}(m\alpha_{\rm UF}(n))$	98.76	0.113
RandSF	$\mathcal{O}(m\alpha_{\rm UF}(n))$	162	0.234
SPF	$\mathcal{O}(m+n\log n)$	817	1.13

Appendix

Table 5: Support-backbone construction time on unweighted graphs.

	Graph scale			Structure	Task
Dataset	$\|{\mathcal{V}}\|$	$\|{\mathcal{E}}\|$	$d$	${\mathcal{H}}_{\mathrm{adj}}$	$C$	$F$	Metric
Heterophilic small/medium
Roman-empire ( Platonov et al., 2023b )	22.66K	32.93K	2.91	-0.05	18	300	Acc
Squirrel ( Platonov et al., 2023b )	2.22K	47.00K	42.28	0.01	5	2.09K	Acc
Minesweeper ( Platonov et al., 2023b )	10.00K	39.40K	7.88	0.01	2	7	AUC
Questions ( Platonov et al., 2023b )	48.92K	153.54K	6.28	0.02	2	301	AUC

Appendix

Table 6: Dataset statistics for the 19 node-classification benchmarks.

	Protocol		Architecture			Optimization			Evaluation
Dataset	Epochs	Runs	$L$	$H$	Norm./Res.	Dropout	LR	WD	Metric
Heterophilic small/medium
Roman-empire	2500	3	9	512	bn, res ∗	0.50	1e-3	0	Acc
Squirrel	500	10	4	256	bn, res	0.70	1e-2	5e-4	Acc
Minesweeper	2000	3	12	64	bn, res	0.20	1e-2	0	AUC
Questions	1500	3	10	512	res ∗	0.30	3e-5	0	AUC

Appendix

Table 7: Per-dataset GCN training configurations shared by all methods.

	Method(s) GNN / budget Training and evaluation
Anchors	No Graph MLP; $T$ Feature-only prediction. Spanning Forest Shared GNN; $T$ One spanning-forest support for training and inference. Full Graph TunedGNN; $T$ Original graph without sparsification.
Topology	Random, Local Degree, Rank Degree, Forest Fire, SCAN Shared GNN; $\delta$ ; $T$ One support per run and budget, reused throughout training. L-Spar, G-Spar, L-Sim, Spectral (ER), $t$ -Spanner, DSpar Shared GNN; $\delta$ ; $T$ Each sparsifier is evaluated independently using the shared training preset.
Semantic	Unified-LTH Shared GNN preset Two 200-epoch mask-search rounds followed by $T$ ticket-training epochs; graph retention $\delta$ , no weight pruning. AdaGLT Shared GNN preset 400 mask-search epochs followed by $T$ retraining epochs; adjacency sparsity $1-\delta$ , no weight pruning. MoG Shared GNN; $\delta$ ; $T$ Three sparsifier experts at retention $[\delta,\delta,\delta]$ , trained jointly with the downstream GNN.
Sampling	Tuned-GraphSAGE Tuned-GraphSAGE; $T$ Dataset-specific neighborhood sampling on the original graph. Tuned-GraphSAINT Shared GNN; $T$ Random-walk subgraph sampling with dataset-specific settings.
Scaffold	Scaffold-Greedy Shared GNN; $\delta$ ; $T$ Full dynamic rescoring after every insertion. Scaffold-Heap Shared GNN; $\delta$ ; $T$ Cached priorities with selective refresh. Scaffold-Batch Shared GNN; $\delta$ ; $T$ Scores sampled batches and inserts top- $r$ edges. Scaffold-Fast Shared GNN; $\delta$ ; $T$ Scores once on the initial spanning-forest backbone. Scaffold-Sample Shared GNN; $\delta$ ; $T$ Reuses precomputed weights to draw exactly budgeted supports. Scaffold settings $(\alpha,\beta_{E},\beta_{V})=(1,1,0)$ Refreshed supports may be generated asynchronously. Scaffold- $1$ Shared GNN; $\delta$ ; $T$ One $q$ -edge support for training and inference. Scaffold- $K$ Shared GNN; $\delta$ per support; $T$ Refreshes every $\rho$ epochs, retains top- $K$ validation supports ( $K\in\{3,5,10\}$ ), and infers once on their union.

Appendix

Table 8: Training configurations of evaluated baselines.

T

is the dataset-specific epoch budget in Table 7 ;

\delta

is the retained-edge ratio.

	Method	Cora	CiteSeer	PubMed	Amazon Computer	Amazon Photo	Coauthor CS	Coauthor Physics	WikiCS	GM
Retention ratio $\delta=0.3$ † below the spanning-forest floor here: Cora, CiteSeer, PubMed
Semantic	Unified-LTH	72.12 ±3.47	63.76 ±1.19	75.26 ±0.67	86.88 ±0.74	91.94 ±0.36	94.99 ±0.37	96.49 ±0.00	75.49 ±0.17	81.32
	AdaGLT	72.74 ±0.63	65.26 ±1.00	75.84 ±0.56	91.53 ±0.42	94.16 ±0.19	95.13 ±0.08	96.65 ±0.00	76.48 ±0.13	82.67
	MoG	73.66 ±0.77	65.28 ±1.50	71.56 ±0.54	92.55 ±0.05	95.45 ±0.29	94.94 ±0.20	96.93 ±0.10	77.48 ±0.66	82.60

Topology	Random	73.40 ±0.51	65.86 ±0.95	74.26 ±0.62	91.05 ±0.15	94.38 ±0.16	94.71 ±0.04	96.66 ±0.05	77.04 ±0.63	82.64

Appendix

Table 9: Homophilic graphs: complete mean

\pm

standard deviation results (%) over eight datasets.

	Method	Squirrel	Chameleon	Roman empire	Amazon ratings	Minesweeper	Questions	GM
Retention ratio $\delta=0.3$ † below the spanning-forest floor here: Roman empire, Questions
Semantic	Unified-LTH	38.17 ±2.09	37.61 ±3.67	65.43 ±0.58	40.49 ±0.52	69.70 ±1.12	72.42 ±0.64	51.75
	AdaGLT	42.30 ±3.91	38.03 ±4.12	81.43 ±0.00	48.05 ±0.35	62.60 ±1.27	72.34 ±0.33	55.27
	MoG	43.25 ±1.12	43.40 ±3.13	70.44 ±0.60	51.24 ±0.33	74.02 ±0.32	68.90 ±1.68	57.07

Topology	Random	40.90 ±1.70	37.85 ±3.35	67.07 ±0.24	48.40 ±0.43	72.39 ±1.04	71.89 ±0.90	54.48

Appendix

Table 10: Heterophilic graphs: complete mean

\pm

standard deviation results (%) over six datasets.

	Method	Reddit	ogbn- products	ogbn- arxiv	ogbn- proteins	Pokec	GM
Retention ratio $\delta=0.1$ † below the spanning-forest floor here: ogbn-arxiv
Semantic	Unified-LTH	91.90 ±0.00	71.72 ±0.00	55.53 ±0.00	66.46 ±0.00	65.50 ±0.00	69.26
	AdaGLT	71.45 ±0.00	61.17 ±0.00	55.94 ±0.00	63.58 ±0.00	62.99 ±0.00	62.83
	MoG	85.15 ±0.07	63.45 ±0.09	56.25 ±0.15	71.12 ±0.08	64.14 ±0.01	67.36

Topology	Random	93.13 ±0.08	71.93 ±0.03	61.64 ±0.04	76.50 ±0.72	68.86 ±0.01	73.71

Appendix

Table 11: Large-scale graphs: complete mean

\pm

standard deviation results (%) over five datasets.

Dataset	$\delta_{d}$	Scaffold-Batch			Scaffold-Fast			Scaffold-Sample
		$K$	$\delta_{\cup}$	$\|E_{\cup}\|/q$	$K$	$\delta_{\cup}$	$\|E_{\cup}\|/q$	$K$	$\delta_{\cup}$	$\|E_{\cup}\|/q$
Cora	0.7	10	0.998	1.43	10	0.870	1.24	10	0.844	1.21
CiteSeer	0.7	10	0.981	1.40	10	0.910	1.30	10	0.752	1.07
Amazon Photo	0.3	10	0.905	3.02	10	0.808	2.69	10	0.695	2.32
WikiCS	0.3	10	0.329	1.10	10	0.300	1.00	10	0.821	2.74
Amazon Computers	0.3	10	0.442	1.47	10	0.436	1.45	5	0.570	1.90

Appendix

Table 12: Realized union size for Scaffold-

K

at the targets

\delta_{d}

Variant / stage	CPU workers
	1	2	4	8	16	32
Reddit
Scaffold-Fast	498.38	284.13	213.08	196.54	201.54	182.08
Scaffold-Batch	630.43	355.01	265.93	242.33	232.81	216.50
Sample : first support	504.96	358.56	232.61	139.49	124.69	87.25
Sample : subsequent support	1.40	1.27	1.22	1.20	1.18	1.16

Appendix

Table 13: CPU scaling of Scaffold support generation at

\delta=0.3

Stage	CPU workers
	1	2	4	8	16	32
Reddit
First support (total)	504.96	358.56	232.61	139.49	124.69	87.25
Forests + weights	472.57	320.16	195.16	107.40	87.36	54.80
Save weights	25.70	30.71	30.91	25.53	30.79	25.71
Other first-support work	6.73	6.60	6.57	6.53	6.54	6.53

Appendix

Table 14: Scaffold-Sample startup and reuse costs at

\delta=0.3

Variant	$\delta$	$S$	Gather-Scatter				SpMM
			Agg.	Rest	Total	GPU	Agg.	Rest	Total	GPU
reddit
Scaffold-Fast-1	0.1	133.9	37.5	70.8	242.3	9.98	12.6	64.6	211.2	3.97
Scaffold-Fast-1	0.3	174.8	138.4	132.1	445.3	24.52	27.2	106.9	308.9	5.54
Scaffold-Fast-1	0.5	223.5	236.7	190.3	650.5	39.09	41.5	146.8	411.7	7.35
Full-GCN	1.0	0.0	553.0	336.2	889.3	75.43	77.0	249.8	326.8	11.84

Appendix

Table 15: Gather-Scatter/SpMM values for Figure 7 . Times are seconds over 300 epochs; GPU is peak allocated memory (GiB).

Method	Reddit	ogbn- products	ogbn- arxiv	ogbn- proteins	Pokec
Random	1.23	1.37	0.015	0.819	0.582
Local degree	41.20	30.39	0.543	24.01	10.02
Rank degree	249.83	69.20	4.05	169.86	27.50
Forest Fire	2501.61	—	10.33	1414.05	692.14
SCAN	78.66	47.57	0.649	40.52	13.32
L-Spar	80.46	49.19	0.594	40.83	11.48

Appendix

Table 16: Sparsification time (s) at

\delta=0.3

on five large-scale graphs.

Method	Reddit			ogbn-products			ogbn-arxiv
	$S$	$T_{300}$	$E_{300}$	$S$	$T_{300}$	$E_{300}$	$S$	$T_{300}$	$E_{300}$
Full-GCN	0.0	713.4	713.4	0.0	1154.0	1154.0	0.0	96.7	96.7
Scaffold-Fast-1	72.0	237.0	309.0	153.1	549.0	702.0	6.3	76.3	82.6
Scaffold-Batch-1	208.8	235.3	444.2	250.7	522.4	773.1	9.3	72.8	82.1
Scaffold-Sample-1	48.8	238.3	287.1	133.9	508.1	642.0	6.1	70.7	76.7
DSpar	4.0	224.4	228.4	4.1	491.8	496.0	0.1	70.4	70.5

Appendix

Table 17: End-to-end runtime (s) at

\delta=0.3

over 300 epochs.

S

: sparsification;

T_{300}

: training;

E_{300}=S+T_{300}

Figure 16: Scaffold variants across support backbones. Extension of Figure 11 including the full Greedy reference on Cora and Chameleon, where its computational cost remains tractable.

Figure 17: Effect of path congestion aggregation. (a–b) vary

p_{E}

with

p_{V}=2

; (c–d) vary

p_{V}

with

p_{E}=2

. Changes are relative to

p_{E}=p_{V}=2

Panel of Table 18 — Table 18: Sensitivity to $K$ . Accuracy is mean $\pm$ standard deviation (%). Cov. is the maximum logged union edge coverage (%), excluding self-loops. Green boxes pair each column’s best accuracy with its coverage at the same $K$ .

Panel of Table 19 — Table 19: Scaffold evaluation at each dataset’s target retention $\delta$ . Scaffold -1 uses one fixed support for training and evaluation; Scaffold - $K$ refreshes supports and evaluates their validation-selected union ( $K=10$ ). Scaffold -Full trains on sparse supports and evaluates on the full graph. Full-GCN trains and evaluates on the full graph. Reported mean $\pm$ SD (%).

Figure 18: Support-refresh ablation on Cora with fast approximation of random forest ( RandSF ) at a 70% edge budget. (a) Accuracy across refresh schedules. (b) Matched-support comparisons with identical support sets.

Dataset	$\bm{\delta}$	Method	Accuracy (%)		Time (s)
			Sync	Async	Sync	Async
Cora	0.7	Scaffold-Fast	82.92 ±0.47	82.94 ±0.90	12.6	12.3
		Scaffold-Sample	83.28 ±0.26	83.00 ±0.29	11.8	11.4
Amazon-Computers	0.3	Scaffold-Fast	92.09 ±0.09	92.18 ±0.15	280.6	35.7
		Scaffold-Sample	92.52 ±0.28	92.55 ±0.36	50.0	36.8

Appendix

Table 20: Synchronous versus asynchronous support generation. Accuracy is mean

\pm

SD; runtime is mean seconds per run.

Figure 19: Training support refresh and inference topology at a 70% edge budget. Models are trained on either a fixed support or a new support each epoch and evaluated on the corresponding sparse support, the best-5 supports, or the full graph.

Method	Chameleon	Squirrel
Random-1	37.85 ±3.35	40.90 ±1.70
Scaffold-1	42.50 ±4.38	44.62 ±1.67
Random- $K$	43.09 ±3.30	43.24 ±2.03
Scaffold- $K$	43.89 ±2.40	43.99 ±1.59
Full-GCN	45.46 ±4.42	44.77 ±2.36

Appendix

Table 21: Sampling comparison at

\delta=0.3

. Test accuracy (mean

\pm

SD, %), with 10 runs per setting. Scaffold uses the Sample variant.

Figure 20: The spanning backbone preserves connectivity; low-dilation maintains finite-hop access, and randomized refresh exposes complementary communication routes across repeated sparse views.

Method	Amazon Computers		ogbn-arxiv
	$\delta_{d}=0.3$		$\delta_{d}=0.3$
	$\|V\|$ 13.8K $\|E\|$ 245.9K		$\|V\|$ 169.3K $\|E\|$ 1.2M
	Acc.	Time	Acc.	Time
GCN	93.77 ±0.03	39.4 s	72.58 ±1.57	1.9 min
Scaf.-GCN 1	92.86 ±0.44 -0.91	34.9 s 1.13 $\times$	69.83 ±0.36 -2.75	1.8 min 1.06 $\times$
Scaf.-GCN K,async	93.51 ±0.08 -0.25	36.3 s 1.08 $\times$	72.15 ±0.46 -0.43	1.7 min 1.16 $\times$

Appendix

Table 22: Scaffold across GNN architectures at

\delta=0.3

. Accuracy is mean

\pm

SD; time is mean wall-clock runtime. Raised annotations show accuracy gap (pp) and speedup relative to the corresponding full-graph model.

Explore similar work

Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines
Mar 7, 2026Yuhang Song, Naima Abrar Shami, Romaric Duvignau +1Graph Sparsification Graph Neural Networks
Boston University · Chalmers University of Technology
EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks
Oct 6, 2026Sai Karthik Navuluru, Siddhartha Shankar Das, Franck Dernoncourt +7Graph Sparsification Graph Neural Networks
University of Texas at Dallas · Pacific Northwest National Laboratory · Adobe Research +3
On Efficient Scaling of GNNs via IO-Aware Layers Implementations
May 29, 2026Daria Fomina, Daniil Krasylnikov, Alexey Boykov +3Graph Attention Networks GPU Kernel Optimization
1Yandex · 2HSE University · 3ITMO University

Mar 7, 2026J/K move · Enter open · S save

Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines

Yuhang Song, Naima Abrar Shami, Romaric Duvignau, Vasiliki Kalavri

Boston University · Chalmers University of Technology

Graph Sparsification Graph Neural Networks

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines

EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks

On Efficient Scaling of GNNs via IO-Aware Layers Implementations