EDIS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks

Sparse GNN training reduces computation, but deciding which edges to keep can be costly. Reusing one sparse graph is cheap but locks training to a fixed topology, while varying it across epochs can require repeated sampling or recomputation. We introduce EDiS (Edge-Disjoint Subgraph sparsification framework), which separates one-time structural extraction from per-epoch graph composition. EDiS decomposes the graph once into cacheable edge-disjoint subgraphs, then recombines them into graphs with edge-budget constraints across epochs and retention ratios without re-extracting structure. Our default construction uses feature-based scores and successive maximum-score covering forests, while the same composition mechanism also supports alternative edge-selection rules. We provide a combinatorial analysis of the per-epoch sampler, the composition step that draws a training graph from the cached decomposition. We show that the stored decomposition deterministically preserves the graph’s cut structure and that any training graph composed from it, regardless of the edge-selection rule used, retains a guaranteed share of that structure. Across 19 homophilic, heterophilic, and large-scale node-classification benchmarks against 17 baselines under the same edge budget, EDiS ranks first in aggregate accuracy, average rank, and gap to the best method. Ablations show the clearest benefits of structural decomposition and epoch variation at tight edge budgets. Code is available at https://anonymous.4open.science/r/EDSparse-9FB0/README.md.