EDiS decomposes a graph once into cacheable edge-disjoint subgraphs and tops 19 node-classification benchmarks at matched edge budgets

EDiS introduces a cacheable, edge-budget-agnostic graph decomposition: it extracts structural subgraphs once, then recomposes them into training graphs satisfying edge-budget constraints across epochs and retention ratios, without rerunning extraction or changing the GNN architecture or loss. Prior methods either fix one sparse graph (locking the topology) or resample/recompute structure every step; EDiS turns edge-disjointness from a one-off computational step into a cacheable training paradigm. The paper defines the decomposition and composition stages and proves that composition returns exactly the requested number of edges for every integer budget (Proposition 3, exact-budget feasibility).

EDiS's composition procedure is selector-agnostic: composition is independent of the extraction methods that build the subgraphs (e.g., maximum-score covering forests or random selection), and the same composition mechanism supports alternative edge-selection rules. The authors state this is the first method to separate extraction from composition, letting different selectors be swapped within the same pipeline. Appendix F.1 implements seven selectors (MaxCF, MinCF, Degree, k-NN, Spanner, Random, Hybrid) and five edge scores, all run through the same composition procedure.

The paper provides a combinatorial analysis of the sampler: under the default covering-forest selector, the stored decomposition deterministically preserves high-score cut edges (Theorem 1); for any residual selector, it derives a conditional bound on high-score cut survival in composed training graphs (Theorem 2). The two guarantees are deliberately decoupled: the stored decomposition carries a strong selector-specific certificate, while the composed graph carries a selector-agnostic bound, which is what allows selectors to be swapped freely. Theorem 1 rests on the bottleneck property of maximum-score covering forests and the successive-forest cut certificate; Theorem 2 needs only a uniform trim within each subgraph, not forest structure.

Across 19 node-classification benchmarks at the same edge budget against 17 baselines, EDiS-Lite achieves the highest mean benchmark score and the lowest average rank and gap-to-best; ablations show structural decomposition and epoch-to-epoch variation matter most at tight edge budgets. Matched-edge-budget controls (Frozen, Direct, Shuffled groups) test whether gains come from the decomposition structure and resampling rather than merely the number or size of edges. 19 datasets (six heterophilic, eight homophilic, five large-scale), with accuracy on 16 and ROC-AUC on Minesweeper, Questions, and ogbn-proteins; all methods share the same architecture, optimizer, and epoch budget.

The result targets node classification with message-passing GNNs trained under a fixed edge budget, on homophilic, heterophilic, and large-scale graphs, and can swap edge scores and residual selectors without changing the GNN architecture or objective. EDiS-Lite, which infers on the sparse composed graph, is the default; EDiS-Full switches to full-graph inference when the accuracy gain is worth the extra inference cost, with training cost unchanged. Composition is not adapted by the GNN loss, since edge scores, subgraphs, and weights are fixed before training, making the method suited to settings that want to organize the topology once and reuse it across epochs and retention ratios.

The composed graph is not guaranteed to stay connected at a fixed budget, and Theorem 2 is a fixed-cut statement rather than a simultaneous connectivity or path-survival guarantee; Theorem 1's strong certificate applies to the stored decomposition and does not automatically transfer to every epoch's composed graph. Predictive performance varies little across selectors and edge scores, with no single choice dominating; the effect of extraction depth on a fixed-budget graph differs by dataset, and more subgraphs do not always give a better graph. Future work mentions task-aware scores, dynamic (temporal) composition, and extensions to graph- and link-level prediction, whose results remain to be established.