Source-linked AI summary
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, Robert Rallo, Mahantesh M Halappanavar
TL;DR
GNN sparsification must reduce edge-dependent costs while retaining useful communication structure, including when labels cannot identify task-specific edges. Scaffold selects sparse supports using dilation and congestion, and reports strong performance at low edge budgets with reduced memory and training cost. A general approximation guarantee for its full objective remains open.
Problem
Sparsification can reduce GNN costs, but objectives may overlook communication structure, and unsupervised settings lack labels or downstream task information for identifying task-specific edge importance.
Source: §1 · pp. 1–2Method
Scaffold constructs topology-based sparse supports by prioritizing edges whose removal would require long or highly congested supporting paths.
Source: §1 · p. 2Results
Takeaways & Limitations
At a fixed edge budget, how omitted connections are represented by the retained graph matters for GNN performance.
Source: §6 · p. 9A general approximation guarantee for the full dilation–congestion objective remains open, and structural bounds do not imply monotonic improvement in downstream GNN accuracy.
Source: §3.4 · p. 5
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
GNN sparsification must reduce edge-dependent costs while retaining communication structure, especially when task labels cannot guide edge selection. Scaffold applies support-graph dilation and congestion to this problem and evaluates scalable variants across benchmarks.
1 INTRODUCTION
- Sparsification is motivated by edge-dependent GNN computation and by the risk that equal-sized sparse graphs create long detours or concentrate rerouted paths on a few edges or hubs.The need is especially pertinent in the unsupervised setting, where labels and downstream task information are unavailable for identifying task-specific edge importance.Source: §1 · pp. 1–2
- Scaffold prioritizes edges whose removal would force endpoints onto long or highly congested supporting paths, preserving short routes while avoiding communication bottlenecks.It explicitly controls dilation and congestion under a prescribed edge budget.Source: §1 · p. 2
- Five realizations—Greedy, Heap, Batch, Fast, and Sample—offer different scalability regimes and support fixed sparsification or stochastic sparse views.The variants provide different quality-cost trade-offs.Source: §1 · p. 2
- The framework is topology-based and unsupervised, translating support-graph theory into a scalable approach for graph representation learning.Source: §1 · p. 2
- Scaffold characterizes how dilation and edge congestion bound structural and communication distortion, then studies their implications for GNN message passing.Source: §1 · p. 2
- Across 19 datasets and 20 related baselines, Scaffold performs strongly; at 30% and 50% edge retention, it comes within one percentage point of full-graph performance on 12/19 and 16/19 datasets, respectively.The paper also reports reduced memory and end-to-end training cost.Source: §1 · p. 2
2 PRELIMINARIES
The preliminaries define a sparse support as a spanning subgraph in which each omitted edge is represented by a path. They describe dilation and congestion as measures of rerouting length and path concentration.
Sparse support and supporting paths
- For a target budget q, Scaffold seeks a spanning subgraph H and represents each omitted edge by a shortest path in the current support connecting its endpoints.Source: §2 · p. 2
Dilation and congestion
- Dilation measures rerouting distance, while edge and node congestion measure how strongly rerouted paths concentrate on the retained support.Node congestion is additionally considered for GNN message passing; the figure depicts support, dilation, edge congestion, and node congestion.Source: §2 · p. 3, Figure 2 · p. 3
Sparsification objective
- Given edge budget q, the objective seeks a support whose omitted edges have short, lightly congested paths, with weights controlling dilation and edge- and node-congestion contributions.Setting βV = 0 recovers the dilation–edge-congestion objective.Source: §2 · p. 3
3 PROPOSED METHOD FOR SPARSIFICATION: SCAFFOLD
Scaffold replaces expensive global support optimization with candidate-wise path scoring and scalable construction variants. It supplies fixed or refreshed sparse supports for GNNs, with structural bounds and costs characterized separately from downstream accuracy.
3.1 FROM THE GLOBAL OBJECTIVE TO A GREEDY SURROGATE
- Exact marginal-gain evaluation is expensive, so Scaffold uses a current-support surrogate that partially captures cross-candidate rerouting by refreshing paths and scores.The exact global objective is NP-hard, and even dilation-only reduction is non-submodular, so standard submodular-greedy guarantees do not apply.Source: §3 · p. 3, §3.1 · pp. 3–4
- Candidate scores use shortest supporting paths, path dilation, and power-mean aggregates of edge and node congestion; larger exponents emphasize stronger bottlenecks.A zero exponent disables that component, allowing the dilation–edge-congestion criterion without node congestion.Source: §3.1 · pp. 3–4
3.2 FAMILY OF SCAFFOLD ALGORITHMS
- Five realizations trade recomputation for scale: Greedy recomputes fully, Heap refreshes affected candidates, Batch scores batches, Fast uses static tree-prefix scoring, and Sample derives sampling weights.Fast scores on the initial forest in O((m + n) log n), while Sample supports exactly budgeted sparse draws in O(m) after preprocessing.Source: §3.2 · p. 5
3.3 SCAFFOLD FOR GNN TRAINING AND INFERENCE
- Scaffold-1 uses one fixed q-edge support, whereas Scaffold-K periodically refreshes supports and runs inference once on the union of its validation-best K supports.The union's realized edge count may exceed q.Source: §3.3 · p. 5, Figure 4 · p. 5
3.4 STRUCTURAL PROPERTIES AND COMPLEXITY
- For supports preserving connected components, dilation and edge congestion bound Laplacian distortion; the general full-objective approximation guarantee remains open, and structural bounds do not ensure better GNN accuracy.Separate path arguments bound graph distances and edge-cut sizes.Source: §3.4 · p. 5
- On a q-edge support, per-epoch message passing costs O(Lqd) rather than O(Lmd), graph-dependent memory falls from O(m) to O(q), and refresh cost amortizes as CScaffold/ρ.Support generation can also run asynchronously with GNN training.Source: §3.4 · p. 5
4 RELATED WORK
Scaffold brings support-graph theory from combinatorial preconditioning to GNN sparsification, jointly considering dilation and congestion under a fixed edge budget. The related-work landscape also includes topology-based, semantic-based, and sampling-based approaches.
4 RELATED WORK
- Scaffold jointly controls dilation and congestion under a fixed edge budget, extending beyond graph spanners' focus on dilation.The paper presents it as the first GNN sparsifier to use this joint criterion for the graph used directly in learning.Source: §4 · p. 6
- The paper groups GNN sparsification approaches as topology-based, semantic-based, or sampling-based, with Scaffold in the topology-based group.Scaffold scores how well omitted edges are represented by paths in the retained support.Source: §4 · p. 6
- Support-graph theory originated in combinatorial preconditioners, while related support-tree and low-stretch methods construct sparse backbones with short replacement paths.The passage cites Vaidya (1991), Boman & Hendrickson (2003), and Bern et al. (2006) for support-graph theory.Source: §4 · p. 6
5 EXPERIMENTAL RESULTS
Across 19 node-classification benchmarks, Scaffold is evaluated against sparsification and related baselines at matched edge budgets. Scaffold-1 has the highest geometric mean among matched-budget methods, while experiments also report near-full-graph performance, efficiency gains, and structural trade-offs.
5 EXPERIMENTAL RESULTS
- The evaluation covers 19 node-classification benchmarks: eight homophilic, six heterophilic, and five large-scale graphs.Comparisons use shared splits, architecture, optimization, and training budget across sparsifiers.Source: §5 · p. 6
5.1 PREDICTIVE PERFORMANCE UNDER SPARSIFICATION
- At δ = 0.3 and 0.5, Scaffold-K is within one percentage point of full-graph performance on 12/19 and 16/19 datasets, respectively.At those same ratios, Scaffold-1 reaches that range on 9/19 and 13/19 datasets.Source: §5.1 · p. 6, Figure 6 · p. 8
- Scaffold-1 achieves the highest geometric mean among matched-budget methods, with average ranks compared across 19 datasets and three retention ratios.The main table uses dataset-specific targets at or above the spanning-forest floor; the rank comparison covers 57 dataset-budget evaluations.Source: §5.1 · p. 6, Table 2 · p. 7, Figure 5 · p. 7
5.2 RUNTIME AND MEMORY EFFICIENCY
- Reducing retained-edge ratio lowers message-passing time and peak GPU memory on REDDIT and OGBN-PRODUCTS, and end-to-end cost remains lower after including support construction.Savings are greatest at lower retention ratios, on large graphs, and over long runs, when per-epoch savings amortize sparsification overhead.Source: §5.2 · p. 7, Figure 7 · p. 8, Figure 8 · p. 8
5.3 ABLATION AND STRUCTURAL ANALYSIS
- With the same spanning-forest backbone and budget, lower dilation and edge congestion generally accompany higher accuracy; dilation has the strongest association, while node congestion adds limited benchmark benefit.The reported association does not establish that structural scores determine predictive performance.Source: §5.3 · p. 8, Figure 9 · p. 9, Figure 10 · p. 9
- Heap and Batch offer stronger structural refinement at higher runtime, while Fast and Sample reduce construction cost at some structural-quality trade-off.Predictive performance is not strictly determined by structural score; backbone choice and stochasticity also matter.Source: §5.3 · p. 8, Figure 11 · p. 9
6 CONCLUSIONS
Scaffold uses dilation and congestion to build sparse communication graphs for GNNs. Across benchmarks it maintains strong performance at low edge budgets while reducing memory and end-to-end training cost, but its full-objective approximation guarantee and broader evaluation scope remain limited.
6 CONCLUSIONS
- Scaffold is an unsupervised, topology-based sparsifier that uses support-theoretic dilation and congestion to construct sparse GNN communication graphs.Across benchmarks, it maintains strong performance at low edge budgets while reducing memory and end-to-end training cost.Source: §6 · p. 9
- The theory does not yet provide a general approximation guarantee for the full dilation–congestion objective, and evaluation focuses on static, undirected, unweighted node-classification graphs.Task-aware, localized, and broader graph-learning extensions are left for future work.Source: §6 · p. 9
AI USE DISCLOSURE
The authors used generative AI tools to assist with manuscript polishing, software implementation, and experimental workflows, then reviewed and validated the assisted content and code.
AI USE DISCLOSURE
- The authors report reviewing and validating AI-assisted manuscript, software, and experimental work, independently verifying results and claims, and taking responsibility for the final work.AI assistance included polishing the manuscript, software implementation, and experimental workflows.Source: AI USE DISCLOSURE · p. 10
REPRODUCIBILITY STATEMENT
The supplementary material documents reproducibility resources and support-graph concepts underlying Scaffold. It describes weighted extensions and the edge-budget condition for preserving connected components.
REPRODUCIBILITY STATEMENT
- Two repositories provide the standalone Scaffold package and GNN benchmark integrations, including baselines and configurations; validation data alone guides support, variant, and checkpoint selection.Test labels are never used for model or method selection.Source: REPRODUCIBILITY STATEMENT · p. 10
A.2 SUPPORT-THEORETIC BACKGROUND
- Support theory interprets omitted edges through paths in the retained graph, whose lengths and overlap are captured by dilation and congestion.Scaffold uses the sparse support as the GNN communication graph, favoring short paths that avoid heavily shared portions.Source: §A.2 · p. 16
A.3 WEIGHTED FORMULATION OF SC A F F O L D
- The weighted formulation assigns positive path lengths and routing loads, then computes weighted congestion and applies the normalized objective; unit lengths and loads recover the unweighted surrogate.The weighted candidate-wise surrogate uses the same power-mean aggregation and normalized objective as the unweighted formulation.Source: §A.3 · p. 17
- A spanning-forest support requires at least n − c(G) edges to preserve every connected component; below that floor, Scaffold enforces the budget without spanning-support guarantees.The supplementary material also introduces background and notation for its support-theoretic formulation.Source: A SUPPLEMENTARY PRELIMINARIES · p. 16, Table 3 · p. 16, §A.3 · p. 17
A.4 WHY THE SUPPORT QUANTITIES MATTER FOR GNNS
The supplementary material connects Scaffold’s support quantities to communication failures, structural guarantees, and scalable construction variants. It also delineates which guarantees apply and compares variant support quality in an example.
A.4 WHY THE SUPPORT QUANTITIES MATTER FOR GNNS
- The controlled examples isolate three communication failures: long detours cause finite-hop under-reaching, shared edges bottleneck rerouting, and shared hubs make targets indistinguishable.Dilation rises from 2 to 8 as accuracy falls from 100% to chance; edge congestion rises from 5 to 7, and node congestion from 3 to 12.Source: §A.4 · p. 17
B.1 OPTIMIZATION OF THE GLOBAL OBJECTIVE IS NP-HARD
- Optimizing the global objective is NP-hard even on connected unweighted graphs with zero congestion weights and a tree-sized edge budget.The reduction makes the objective equivalent to minimizing maximum-stretch spanning-tree dilation.Source: §B.1 · p. 18
B.2 DILATION REDUCTION IS NON-SUBMODULAR
- Dilation reduction is not submodular in general, so the standard submodular-greedy approximation guarantee does not apply.The exhibited marginal gain increases after another edge has already been selected.Source: §B.2 · p. 19
B.3 GUARANTEE FOR DILATION-ONLY SELECTION
- For dilation-only selection, choosing maximum-current-dilation candidates or the top initial dilations bounds returned-support dilation by the (T + 1)th initial dilation.The bound applies to dilation-only selection, not the full dilation–congestion rule.Source: §B.3 · p. 19
B.5 EFFECTIVE-RESISTANCE, DISTANCE, AND CONGESTION CONSEQUENCES
- The structural guarantees do not establish a general approximation ratio for the full selection rule or monotonic improvement in downstream GNN accuracy.For unweighted graphs, communication distance in the support is bounded by max{1, D(H)} times the original distance.Source: §B.5 · p. 20
B.6 SUPPORT QUALITY UNDER EDGE UNIONS
- Taking the inference-support union cannot worsen any constituent support’s support-number approximation, but this structural result does not imply better GNN predictive performance.The comparison concerns supports that preserve connected components and retain original edge weights.Source: §B.6 · p. 21
C.1.2 VARIANT MECHANISMS
- Scaffold variants trade recomputation for speed: Heap refreshes affected candidates, Batch scores sampled candidates, Fast fixes initial forest scores, and Sample reuses randomized-forest signals.Backbones may be deterministic, randomized, weight-aware, or low-stretch; the example comparison holds the backbone and budget fixed.Source: §C.1.2 · pp. 21, 22, 24, §C.1.1 · p. 21
C.1.3 EXAMPLE SUPPORT QUALITY ACROSS SC A F F O L D VARIANTS
- Greedy attains the lowest dilation–congestion objective in the example; Heap stays close, while Batch, Fast, and Sample yield higher objective values at the same sparsity.The comparison uses the same RandSF backbone and edge budget.Source: §C.1.3 · p. 24
C.2 SCAFFOLD-1 AND SCAFFOL D-K TRAINING AND INFERENCE
Scaffold-1 uses one sparse support throughout training and inference, while Scaffold-K refreshes supports and evaluates on a validation-selected union. The appendices describe scalable construction, evaluation protocols, benchmark comparisons, and an unresolved connectivity issue for localized supports.
C.2 SCAFFOLD-1 AND SCAFFOL D-K TRAINING AND INFERENCE
- Scaffold-1 keeps one q-edge support for training and inference; Scaffold-K periodically generates supports and evaluates on the union of up to K validation-ranked supports.The union cannot worsen support-number approximation relative to any constituent support (Proposition B.5).Source: §C.2 · p. 24
C.3 RUNTIME AND SCALABILITY
- Heap and Batch reduce dynamic rescoring, while Fast and Sample avoid repeated full rescoring; total construction time also includes backbone construction.The stated complexities cover selection, and measured runtimes include fresh backbone construction.Source: §C.3 · pp. 24, 26
C.4 POSSIBLE EXTENSION: LOCALIZED OR PARTITIONED SUPPORTS
- Localized supports face a cross-partition connectivity problem: disconnected endpoints give an omitted edge infinite dilation, requiring an added connectivity mechanism.Possible mechanisms include a sparse global skeleton, selected boundary edges, or separate scoring of cross-partition edges; design and analysis are left for future work.Source: §C.4 · p. 26
D APPENDIX RELATED WORK
- The related-work review positions Scaffold among topology, semantic, and sampling approaches, while noting that the experiments compare representative methods rather than every graph-reduction paradigm.Sampling methods primarily limit computation per iteration rather than construct a single global sparse support.Source: D APPENDIX RELATED WORK · p. 27
- Scaffold evaluates omitted edges by their supporting paths and jointly considers dilation and congestion, unlike distance-only sparsification; its variants trade quality against construction cost.The paper states that prior GNN sparsifiers have not explicitly used this joint criterion to construct message-passing graphs.Source: D APPENDIX RELATED WORK · p. 27
E.1 DATASETS AND SHARED TRAINING SETTINGS
- Evaluation covers 19 node-classification datasets, with shared splits, architectures, optimization settings, and training budgets for ranked fixed-budget sparsifiers.Graphs are made undirected and self-loop-free; semantic methods keep native optimization procedures but are matched to the edge-retention ratio.Source: §E.1 · p. 27, §E.2 · p. 27
E.2 BASELINE TRAINING SETTINGS
- Benchmark settings distinguish Scaffold-1’s fixed, matched-budget support from Scaffold-K’s refreshed supports and potentially larger inference union.Scaffold-K is reported separately because its union can exceed the target budget; test labels are not used for support or checkpoint selection.Source: §E.2 · p. 28
F.1 RESULTS ON HOMOPHILIC GRAPHS
- Tables 9–11 report detailed comparisons at specified edge-retention ratios across homophilic, heterophilic, and large-scale graphs.The supplied passages identify the tables’ scope but do not provide their cell values.Source: §F.1 · p. 29, §F.2 · p. 29, §F.3 · p. 29
F.4 CASE STUDY OF PERFORMANCE OF DIFFERENT DATASETS
The case studies show that performance depends on more than the edge budget and varies with dataset and support choice. Runtime results distinguish the costly first preparation of Scaffold-Sample from its cheaper repeated support generation.
F.4 CASE STUDY OF PERFORMANCE OF DIFFERENT DATASETS
- On MINESWEEPER at δ = 0.7, local similarity-based sparsifiers outperform Scaffold-1, suggesting neighborhood edge distribution can matter more than global support paths for some tasks.The results also include cases where edge budget alone does not explain performance.Source: §F.4 · p. 33
- On CHAMELEON and SQUIRREL, Scaffold-1, Spectral, and MoG perform similarly, while several degree- or similarity-based sparsifiers are weaker.Scaffold-1 uses a low-stretch SLSF backbone on these two small heterophilic graphs.Source: §F.4 · p. 33
F.5 REALIZED INFERENCE UNION SIZE OF SC A F F O L D-K
- Scaffold-K’s realized inference union ranges from nearly one q-edge support to almost the full graph, motivating its separate reporting from matched-budget Scaffold-1.Refreshing supports generally helps but is dataset-dependent; Scaffold-K slightly underperforms on some datasets and improves substantially on others.Source: §F.5 · p. 33, §F.4 · p. 33, Table 12 · p. 33
G.1 SPARSIFICATION TIME AND SCALING OF SC A F F O L D
- Scaffold-Sample has a larger one-time startup cost, but subsequent supports are substantially cheaper to generate using its precomputed sampling state.Among Scaffold variants, Sample is fastest for standalone sparsification on all five large-scale graphs at δ = 0.3.Source: §G.1 · p. 34, Table 14 · p. 34
G.2 TRAINING PROFILE BREAKDOWN OF SC A F F O L D-FA S T-1 AND FULL-GCN.
The runtime and ablation results show that sparsification overhead, support refresh, and inference topology have dataset-dependent effects. Across the reported end-to-end comparisons, Scaffold variants reduce runtime relative to Full-GCN despite initial sparsification cost.
G.2 TRAINING PROFILE BREAKDOWN OF SC A F F O L D-FA S T-1 AND FULL-GCN.
- The profiling comparison breaks out support generation and training costs, and reports that Scaffold’s benefits are greatest on large graphs, low retention ratios, and long runs.The profile covers two large datasets over 300 epochs and distinguishes COO Gather-Scatter from CSR/CSC SpMM.Source: §G.2 · p. 34, Table 15 · p. 35
G.3 SPARSIFICATION AND END-TO-END RUNTIME
- At δ = 0.3 over 300 epochs, Scaffold variants reduce end-to-end runtime versus Full-GCN on REDDIT, OGBN-PRODUCTS, and OGBN-ARXIV, including sparsification cost.Scaffold-Sample takes 287.1 s versus 713.4 s on REDDIT, 642.0 s versus 1154.0 s on OGBN-PRODUCTS, and 76.7 s versus 96.7 s on OGBN-ARXIV.Source: §G.3 · p. 35, Table 17 · p. 36
H.1 SCAFFOLD VARIANTS AND SUPPORT BACKBONES WITH GR E E D Y
- Greedy, Heap, and Batch generally achieve stronger dilation and congestion reductions than Fast and Sample, which trade structural refinement for lower construction cost.Predictive performance does not strictly follow the structural score and also depends on dataset and backbone.Source: §H.1 · p. 36, Figure 16 · p. 36
H.2 EFFECT OF THE PATH NODE AND EDGE CONGESTION PARAMETER pE, pV
- Changing pE and pV aggregation orders affects congestion and accuracy, but larger values do not guarantee higher accuracy; the default is pE = pV = 2.Larger pE emphasizes highly loaded edges, while larger pV emphasizes highly loaded nodes.Source: §H.2 · pp. 36–37, Figure 17 · p. 36
H.3 SENSITIVITY TO THE NUMBER OF SUPPORTS K
- Increasing K raises CORA’s peak coverage from 70% to nearly 100%; accuracy rises by 0.58 points for Fast and 1.20 for Sample.On AMAZON-COMPUTERS, both variants gain 0.85 points by K = 4; on Coauthor-CS, accuracy is lower at K = 20 than K = 16 despite higher peak coverage.Source: §H.3 · p. 37, Table 18 · p. 37
H.3.1 EVALUATION ON THE FULL GRAPH
- Full-graph inference does not consistently yield higher scores than evaluation on selected sparse supports.The paper suggests that validation-selected supports may exclude noisy edges; for small graphs with larger K, their union can cover most or all of the graph.Source: §H.3.1 · p. 37, Table 19 · p. 37
H.4 SUPPORT-REFRESH FREQUENCY
- On CORA, every-epoch refresh reduces the full-graph accuracy gap to 0.89 points, versus 2.09 and 3.79 points for refresh every 10 and 50 epochs.Matched-support controls show every-epoch refresh improves accuracy by 2.65 points over every 50 epochs and by 1.06 points over every 10 epochs.Source: §H.4 · p. 38, Figure 18 · p. 38
H.5 IMPACT OF SYNCHRONOUS VS. ASYNCHRONOUS SUPPORT GENERATION
- Asynchronous generation reduces AMAZON-COMPUTERS runtime by 7.9× for Fast and 1.4× for Sample, with negligible accuracy changes.Synchronization has little runtime effect on Cora; the smaller Sample speedup reflects its cheaper sampling step.Source: §H.5 · p. 38, Table 20 · p. 38
H.6 TRAINING SUPPORT REFRESH AND INFERENCE TOPOLOGY
Training refresh and inference topology interact differently across datasets, and full-graph inference is most beneficial after training on a fixed support. Additional experiments examine random sampling, communication structure, and compatibility across GNN architectures.
H.6 TRAINING SUPPORT REFRESH AND INFERENCE TOPOLOGY
- Inference topology interacts with training refresh: full-graph inference helps both training setups on CORA, while on CHAMELEON it helps fixed-support training but adds almost no gain after every-epoch refresh.On CHAMELEON, fixed-support accuracy rises from 38.90% to 43.93%, while refreshed-training results are 43.22% versus 43.17%; AMAZON-PHOTO shows small differences among inference choices, and best-5 supports perform best on SQUIRREL after refresh.Source: §H.6 · pp. 38–39, Figure 19 · p. 39
H.7 SCAFFOLD-K VS RANDOM SPARSE SAMPLE AT EVERY EPOCH
- The Random-K comparison tests whether edge choice matters beyond repeated sampling, using uniform random 30%-edge samples and a validation-selected union of five samples.The comparison matches the main-table GCN settings, splits, and training budgets; the union may exceed the per-sample edge budget.Source: §H.7 · p. 39, Table 21 · p. 39
H.8 STRUCTURAL IMPLICATIONS OF SC A F F O L D
- Above the spanning-forest floor, the backbone preserves connected components, while low dilation keeps more omitted relations within a GNN’s finite-hop receptive field.On CORA at δ = 0.7, refreshing RandSF improves accuracy by 2.13 points and approaches full-graph performance while increasing four-hop coverage.Source: §H.8 · p. 39, Figure 20 · p. 39
H.9 COMPATIBILITY OF SCAFFOLD ACROSS GNN ARCHITECTURES
- Across GCN, GAT, GIN, and GraphSAGE, Scaffold generally reduces runtime while remaining competitive in accuracy on AMAZON-COMPUTERS and OGBN-ARXIV.Scaffold-K can recover some accuracy relative to Scaffold-1 through support refresh; comparisons use matched settings within each dataset and architecture.Source: §H.9 · p. 40, Table 22 · p. 40