EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks

Motivation

• Reusing one sparse graph fixes the topology, while rebuilding or resampling graphs can make sparsification costly and existing variation methods tie it to specific mechanisms or sparsity levels.On Reddit, AS-GCN spends 20.7 seconds per epoch sampling neighbors versus 3.5 seconds for the forward and backward pass.Source: §1 · p. 1

Approach

• EDiS extracts persistent, edge-disjoint subgraphs once and recombines them into training graphs with edge-budget constraints across epochs and retention ratios.The GNN architecture and loss remain unchanged; the sparse message-passing graph varies across epochs.Source: §1 · p. 2
• Its default construction uses feature-based scores and successive maximum-score covering forests, while its composition procedure supports alternative selectors and separates stored-decomposition guarantees from composed-graph bounds.The paper analyzes score-aware cut preservation for maximum-score residual forests and conditional retention and cut survival for any residual selector.Source: §1 · p. 2

Evaluation

• At 30% retention, EDiS-Lite achieves the highest mean benchmark score among ranked methods (average rank 2.53, gap 1.25 points).The evaluation covers 19 datasets and 17 baselines; gains from cacheable subgraphs and graph variation are largest at tight edge budgets.Source: §1 · p. 2

Sampling-based GNN training

• Sampling methods resample topology at each step, whereas EDiS organizes topology once and reuses precomputed subgraphs under an explicit edge budget.The cited alternatives include neighbor, layer-wise, and subgraph sampling; other efficiency methods cache embeddings, compress activations, repartition graphs, or compensate for missing messages.Source: §2 · p. 3

Graph sparsification

• Graph sparsification includes pre-training edge-removal methods and methods that learn retained edges jointly with graph learning; EDiS applies varied sparsification principles through a common composition step.The passage notes that no single method effectively preserves multiple graph properties of interest well.Source: §2 · p. 3

Stochastic topology variation

• DropEdge and dropout-induced subgraphs vary topology through independent random edge removal, while EDiS varies it through a controlled, cacheable partition.The cited stochastic-variation structures overlap substantially across epochs and carry no edge-budget or structural guarantee.Source: §2 · p. 3

Cacheable edge-disjoint decomposition

• Prior sparse-structure sequences include SpanGNN and GERN, but the passage distinguishes EDiS as decoupling one-time extraction from per-epoch composition of a persistent, budget-agnostic decomposition.The stated comparison concerns budget, reusability, exposure, and disjointness.Source: §2 · p. 3

3.1 ONE GNN, MANY SPARSE VIEWS

• EDiS separates one-time decomposition from per-epoch composition, so the GNN processes a fixed number of edges per epoch while seeing different structured subsets.The GNN parameters are shared, and only the sparse message-passing graph varies across epochs.Source: §3 · pp. 3–4

3.2 ONE-TIME STRUCTURAL DECOMPOSITION

• The default decomposition scores edges using shifted cosine similarity between endpoint features and extracts successive maximum-score covering forests from residual edges.The first forest is a high-score connectivity-preserving backbone; later forests span residual connected components using previously unused edges, and extraction choices are fixed independently of the budget.Source: §3.2 · pp. 4–5

3.3 AN EXACT-BUDGET GRAPH AT EVERY EPOCH

• At each epoch, EDiS draws subgraphs in weighted random order, adds them toward the edge budget, trims at most one subgraph if needed, and fills a shortfall uniformly from the residual pool.Higher-weighted subgraphs are more likely to appear early, but the order is not fixed; under the stated implementation conditions, composition scales with B and K rather than m.Source: §3.3 · pp. 5–6

3.4 STRUCTURAL PRESERVATION FOR DECOMPOSITION AND COMPOSITION

• For the default MaxCF selector, completed stored prefixes preserve score-threshold cut certificates; composition instead has a selector-agnostic conditional bound, but does not guarantee connectivity at a fixed budget.The composition bound conditions on subgraph order and uniform trimming; the two guarantees trade certificate strength for selector generality.Source: §3.4 · p. 6

4.1 EXPERIMENTAL SETUP

• The evaluation covers 19 node-classification datasets and 17 methods, using accuracy except ROC-AUC for Minesweeper, Questions, and ogbn-proteins; methods share architecture, optimizer, and epoch budgets.Source: §4.1 · pp. 6–7, Table 1 · p. 7

4.2 PREDICTIVE PERFORMANCE

• EDiS-Lite achieves the highest mean benchmark score among ranked methods at both budgets, with average ranks of 2.53/3.32 and gaps of 1.25/1.23 points at ρ = 0.3/0.5.Source: §4.2 · pp. 7–8, Table 2 · p. 8
• At tight budgets, EDiS-Full recovers much of EDiS-Lite’s gap to Full GCN, but increases evaluation time and peak GPU memory mildly while leaving training cost unchanged.Source: Figure 3 · p. 8, §4.2 · p. 8

4.3 ABLATIONS AND GENERALITY

• EDiS-Lite matches or leads Frozen, Direct, and Shuffled across measured budgets, with the largest margin at tight budgets; removing epoch variation hurts most there.Source: Figure 4 · p. 8, §4.3 · p. 9
• Across seven selectors and five scores, most choices lie within a couple of points of the best per dataset, and no selector or score dominates.Source: Figure 5 · p. 9
• The experiments also compare extraction depth at ρ = 0.3 and backbones within EDiS-Lite; Figure 6 reports means with standard-deviation bars and uses panel-specific scales.Source: Figure 6 · p. 9, Figure 7 · p. 9

• EDiS caches structural extraction once, then composes sparse training graphs across epochs and retention levels without changing the GNN architecture or objective.Source: §5 · p. 10
• Across 19 node-classification benchmarks, EDiS-Lite has the highest mean benchmark score among ranked methods at both retention levels.Source: §5 · p. 10
• The conclusion identifies task-aware decomposition scores, dynamic composition, and graph- or link-level prediction as future directions.Source: §5 · p. 10

• AI tools assisted with manuscript polishing, software implementation, and experimental workflows; authors reviewed the work and independently verified reported results and claims.Source: AI USE DISCLOSURE · p. 11

ETHICS STATEMENT

• Experiments use publicly available benchmark graphs under their original licenses and involve no human subjects, personal data, or new data collection.Source: ETHICS STATEMENT · p. 11

A NOTATION

• The notation appendix groups symbols by where they are introduced and reuses H as a generic placeholder for the current graph.Source: A NOTATION · p. 17, Table 3 · p. 17

• Unlike methods that repeatedly resample structures, EDiS organizes topology once into non-overlapping subgraphs and recomposes them under an explicit retained-edge budget.Source: B EXTENDED RELATED WORK · p. 18
• Sampling methods process only part of a graph at once, while EDiS organizes the topology itself and controls which precomputed subgraphs are used.Source: B EXTENDED RELATED WORK · p. 18
• Classical cut sparsifiers repeatedly extract maximum spanning forests for cut-size guarantees; EDiS keeps each forest as a separate, cacheable training subgraph.Source: B EXTENDED RELATED WORK · p. 18
• DropEdge and dropout-induced subgraphs vary across training steps, but their structures can substantially overlap; EDiS reuses non-overlapping subgraphs under an explicit edge budget.Source: B EXTENDED RELATED WORK · p. 18
• AGS-GS-Disjoint uses a dual-channel sampler and random residual edges, whereas EDiS composes subgraphs into exact-B-edge graphs with selector-independent guarantees.AGS-GS-Disjoint does not guarantee an exact edge count or provide attached structural theory.Source: B EXTENDED RELATED WORK · p. 19
• SpanGNN, MoG, and GERN also use multiple sparse structures, but EDiS addresses allocating a fixed retained-edge budget across a cacheable collection of non-overlapping subgraphs.Table 4 compares these methods across budget, reuse, multiple structures, and edge-disjointness.Source: B EXTENDED RELATED WORK · p. 19, Table 4 · p. 19

C.1 GRAPH, GNN, AND EDGE BUDGET

• The edge budget B is an integer from 0 to m; a retention ratio ρ sets B = ⌈ρm⌉ while nodes and features stay fixed across epochs.Source: §C.1 · p. 20

D WORKED EXAMPLES OF STRUCTURAL SELECTORS

• EDiS pairs fixed edge scores with residual selectors that may ignore scores or return non-forests; worked examples compare seven selectors, with MaxCF and Spanner producing the same subgraphs in that example.The examples are illustrative, not predictive rankings, and stored-subgraph guarantees need not hold after composition.Source: §C.2 · p. 20, D WORKED EXAMPLES OF STRUCTURAL… · p. 23

C.3 MAXIMUM-SCORE RESIDUAL FORESTS

• The default extraction repeatedly selects maximum-score covering forests by greedy graphic-matroid optimization, yielding reusable successive residual forests but not a minimum-cardinality forest partition.Subgraphs, their weights, and the residual pool are computed once and reused across training epochs and feasible budgets.Source: §C.3 · p. 20

C.4 CLASSICAL FOREST PROPERTIES

• Successive residual covering forests provide a cut certificate, but their union is not necessarily jointly optimal among edge sets of the same size.Source: §C.4 · p. 21

C.5 EXACT STOCHASTIC BUDGETED COMPOSITION

• Composition samples subgraphs without replacement until their total size reaches the budget, trims excess uniformly from at most one subgraph, and samples residual edges when the budget exceeds stored edges.The stored decomposition and weights support subsequent budget–epoch queries without rerunning the selector, and composition returns exactly B edges, including when the stored decomposition is empty.Source: §C.5 · p. 21, §E.1 · p. 24

C.6 STRUCTURAL PRESERVATION OF THE STORED DECOMPOSITION

• Under the default maximum-score forest selector, every stored prefix certifies threshold-qualified cut crossings and preserves each cut’s top-k crossing-score values with multiplicity.The threshold certificate applies simultaneously to every nontrivial cut; the score-threshold and top-k guarantees require maximum-score residual covering forests with fixed scores.Source: §C.6 · p. 22, §E.2 · p. 24, §E.3 · p. 25

C.7 RETENTION AFTER BUDGETED COMPOSITION

• Conditioned on the sampled order, decomposition, weights, and budget, composition has a selector-agnostic bound on high-score cut-edge survival.The bound applies because partial trimming retains a uniform random subset; it does not establish that weighted ordering is superior to uniform ordering or that spreading edges across subgraphs is always beneficial.Source: §C.7 · p. 22, §E.5 · p. 26

E.4 EQUIVALENT INTERPRETATIONS

• For a fixed cut, the capped crossing-edge count is monotone submodular and the stored prefix saturates it; under a pure maximum-score schedule, omitted edges also have k edge-disjoint endpoint paths of at-least-equal scores.The paths may share vertices, have unbounded hop length, and are not guaranteed to survive composition; the certificate does not establish useful prediction influence.Source: §E.4 · pp. 25–26

E.5 COMPOSITION RETENTION

• A vertex is isolated exactly when its singleton cut is empty, so its cut-retention probability also bounds how often aggregation uses only that vertex’s features.The identities bound retention at each cut individually, not the joint event that every cut retains an edge.Source: §E.5 · p. 26
• Corollary 12 states a high-score cut-survival result under the same conditions, separately from any guarantee of graph-wide connectivity.The supplied passage identifies the corollary but does not include its full bound.Source: §E.5 · pp. 26–27
• For a fixed cut, conditional survival probability is at least 1 − δ when μ ≥ log(1/δ), for 0 < δ < 1.The bound is weak for small μ and equals zero when μ = 0; it is not a simultaneous connectivity or path-survival guarantee.Source: §E.5 · p. 27

E.6 OPTIONAL COMPOSITION VARIANTS

• Certificate-core composition retains the largest complete maximum-score forest prefix that fits the budget, preserving deterministic cut guarantees at the cost of cross-epoch variability.A separate average-score rule maximizes expected retained score by filling subgraphs in descending average score, but this does not establish accuracy-optimal allocation.Source: §E.6 · p. 27

F.1 FAMILY OF RESIDUAL SELECTORS

• MaxCF and MinCF build score-ordered covering forests, while k-NN selects each node’s top remaining edges and Hybrid schedules MaxCF, k-NN, then degree-normalized selection.The covering-forest property applies per extraction round, not necessarily to the budget-limited training graph.Source: §F.1 · p. 28
• Other residual selectors include stretch-bounded spanners, degree-normalized sampling, and uniform random selection; several traversal-, clustering-, or ranking-based alternatives are not implemented within EDiS construction.The selector interface allows the implemented residual-selection rules to be substituted without changing the rest of the pipeline.Source: §F.1 · p. 28

F.2 COST OF CONSTRUCTION AND EPOCH COMPOSITION

• Scoring costs O(md0) once, while composition can run in O(K log(K + 1) + B) under stated implementation conditions; composition and reciprocal expansion recur each epoch.The composition bound depends on implementation choices; copying candidate pools or generating full-pool permutations can add costs up to m.Source: §F.2 · p. 29

G.1 DATASET

• The evaluation uses 19 node-classification benchmarks spanning six heterophilic, eight homophilic, and five large-scale graphs, with accuracy or ROC-AUC depending on dataset.ogbn-proteins has 112 binary prediction tasks; Minesweeper, Questions, and ogbn-proteins use ROC-AUC.Source: §G.1 · p. 29

G.2 BASELINE SETTINGS

• Baselines are grouped as graph-independent anchors, jointly learned semantic methods, and topology-based methods; sampling methods are excluded from matched-edge-budget comparisons because they control minibatch or neighborhood size.GraphSAGE, GraphSAINT, and Cluster-GCN appear as examples of sampling-based methods; GraphSAGE is used only as an alternate backbone in RQ7.Source: §G.2 · p. 30

G.3 PROPAGATION AND EVALUATION SETTINGS

• For full-batch GCN, retained undirected edges are added in both directions, self-loops are added, and adjacency normalization is recomputed for each epoch’s topology.Edge scores guide selection rather than acting as propagation weights; the architecture and training objective remain unchanged.Source: §G.3 · p. 30

G.4 HYPERPARAMETER SETTINGS

• Methods share per-dataset training settings for each backbone, GCN is the default, and the extraction round cap varies by dataset from 10 to 80.The learned MLP edge score uses labeled endpoint pairs and is unavailable for PubMed because its split has too few training labels for the balanced sample.Source: §G.4 · pp. 30–31

G.5 COMPLETE NUMERICAL RESULTS

• Tables 9–11 report mean and standard deviation results for homophilic, heterophilic, and large-scale node-classification benchmarks.The homophilic table reports test accuracy at retention 0.3, 0.5, and 0.7; the heterophilic and large-scale tables include ROC-AUC for specified datasets.Source: §G.5 · p. 31, Table 9 · p. 32, Table 10 · p. 33

H RUNTIME AND MEMORY DETAILS

• The runtime appendix covers Lite-versus-Full inference trade-offs, end-to-end runtime and memory across retention budgets, and matched-hardware comparisons against external baselines.It identifies Figure 9 and Tables 12–16 as the relevant analyses.Source: H RUNTIME AND MEMORY DETAILS · p. 35

H.1 LITE VERSUS FULL EVALUATION TRADE-OFF

• Full-graph evaluation can recover accuracy lost by Lite on comparatively sparse graphs, while on already dense graphs it can add little or no accuracy despite extra evaluation cost.The trade-off varies with graph density, and the Lite-Full evaluation gap shrinks as retention increases until the variants match at ρ = 1.Source: §H.1 · p. 35, Figure 9 · p. 35

H.2 END-TO-END RUNTIME AGAINST BASELINES

• At ρ = 0.3, EDiS-Lite’s one-time extraction costs more than simple degree- or neighborhood-based heuristics, is comparable to or below Spectral, and is far below Forest Fire.The extraction is reused across epochs and retention budgets, so its cost is considered alongside training savings.Source: §H.2 · p. 36, Table 15 · p. 36
• On Reddit, EDiS-Lite trains at 1.73 s per epoch versus 2.38 s for Full-GCN, but its 300-epoch total is 832.4 s versus 713.4 s because setup is not yet amortized.The totals cross below Full-GCN after roughly 480 epochs; on OGBN-ARXIV and OGBN-PRODUCTS, EDiS-Lite’s 300-epoch end-to-end runtime is lower than Full-GCN’s.Source: §H.2 · p. 36, Table 16 · p. 36

I ABLATIONS AND ADDITIONAL PROFILES

• Across the ablations, the selector comparison covers 14 homophilic and heterophilic datasets, while the broader ablation sweeps selector, score, mechanism, inference graph, and backbone axes.The five large-scale graphs are profiled separately for extraction depth and decomposition reuse.Source: I ABLATIONS AND ADDITIONAL PROFILES · p. 37

I.1 EXTENDED SELECTOR ABLATION

• Selector performance depends on the dataset: MaxCF is a strong default, not a universal winner, and selectors diverge most at low retention before converging as ρ approaches 1.The selector comparison fixes GCN, cosine scores, and 30% retention; Figure 10 extends it over the measured retention range.Source: §I.1 · p. 37, Table 17 · p. 37, Figure 10 · p. 37

I.2 EXTENDED EDGE-SCORE ABLATION

• 83.70 ± 1.57 ROC-AUC for MLP versus 73.82 ± 0.97 for cosine on Minesweeper, a 9.88-point gap that persists across most retention ratios.Which score performs best depends on the dataset; cosine is a strong default, not a universal winner.Source: §I.2 · p. 38, Figure 11 · p. 38

I.3 EXTENDED MECHANISM ABLATION

• At 30% retention, EDiS-Lite has a higher reported mean than Frozen on 13 of 14 datasets, Direct on 11, and Shuffled groups on 12.Its largest control advantage is 0.72 points over Shuffled groups on Squirrel; the comparisons also show that neither decomposition nor resampling is uniformly beneficial.Source: §I.3 · p. 39, Figure 12 · p. 39

I.4 EXTENDED INFERENCE-GRAPH ABLATION

• Full-graph inference generally recovers accuracy over EDiS-Lite, with gains largest at low retention and shrinking toward zero as the graphs converge.The recovery varies greatly by dataset and does not always close the gap to the independently tuned Full GCN reference.Source: §I.4 · p. 40, Figure 13 · p. 40, Table 20 · p. 40

I.5 EXTENDED BACKBONE COMPARISON

• GCN and GraphSAGE are close substitutes on most datasets, neither dominates the panel, and the stronger backbone depends on the dataset-architecture match.The largest backbone gap is on Squirrel; GCN wins on both heterophilic and homophilic examples, so homophily alone does not determine the winner.Source: §I.5 · p. 41, Figure 14 · p. 41

I.6 SELECTOR AND SCORE ROBUSTNESS UNDER GRAPHSAGE

• Under GraphSAGE, no single selector or score wins on every dataset, and the Minesweeper MLP advantage also appears, making it dataset- rather than backbone-specific.The GraphSAGE sweep finds different selector winners than under GCN, while defaults remain reasonable rather than universally best.Source: §I.6 · p. 42, Table 22 · p. 42, Table 23 · p. 42

I.7 EXTRACTION DEPTH ON LARGE GRAPHS

• Across five large graphs, Kmax = 20 remains within one percentage point of the best observed mean for both Lite and Full, while mainly trading precomputation time against composition time.Arxiv, Products, and Pokec saturate below the cap at 43, 114, and 67 subgraphs; Proteins and Reddit reach 320.Source: §I.7 · p. 43, Table 25 · p. 43

I.8 COVERAGE, OVERLAP, AND DECOMPOSITION REUSE

• At ρ = 0.3, EDiS covers 99–100% of edges with consecutive-epoch Jaccard overlap of 0.22–0.34, versus Direct’s 0.17–0.18.Figure 15 contrasts coverage and overlap; Figure 16 shows that EDiS pays extraction once, while rebuilding for each edge budget accumulates cost linearly.Source: §I.8 · p. 44, Figure 15 · p. 44, Figure 16 · p. 44

J.1 COMPARISON WITH SPANGNN AND GERN; J.2 COMPARISON WITH MOG UNDER GRAPHSAGE

• AGS-GNN is omitted because its submodular precomputation did not finish within the evaluation hardware budget; SpanGNN and GERN are compared under full-graph inference, while MoG’s published GraphSAGE results provide an additional reference.The MoG comparison is against EDiS-Lite under the same backbone, datasets, and evaluation.Source: §J.1 · p. 45, §J.2 · p. 45, Table 27 · p. 45

K LIMITATIONS

• The empirical study covers node classification and GCN and GraphSAGE backbones; graph- and link-level prediction benefits and broader architectural validation remain unestablished.Source: K LIMITATIONS · p. 46
• The default score, residual selector, and extraction-depth cap come from empirical sweeps, no choice dominates across datasets, and automatic tuning remains open.Source: K LIMITATIONS · p. 46
• Composed graphs are not guaranteed connected at every fixed budget, the trimming alternative was not tested, and EDiS assumes the full graph is available before extraction.Inductive and streaming settings with later-arriving edges are not addressed.Source: K LIMITATIONS · p. 46