EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks

AI summary

Overview

Research area: Graph machine learning — specifically graph sparsification for efficient training of Graph Neural Networks (GNNs).

Technical level: Intermediate. The framework is conceptually simple (decompose once, recombine per epoch), but full appreciation requires familiarity with GNN message passing, edge-budget sparsification, spanning forests, and cut-based graph theory.

Scope: The paper introduces EDiS, a framework that decomposes a graph once into cacheable edge-disjoint subgraphs and recombines them into exact-edge-budget training graphs at every epoch, evaluated against 17 baselines on 19 node-classification benchmarks.

What This Paper Is About

Training a GNN is expensive because computation scales with the number of edges the model passes messages along. Sparsifying the graph reduces that cost, but deciding which edges to keep is itself costly — and the paper reports that on Reddit (233K nodes, 11.6M edges), the sampling-based method AS-GCN spends 20.7 seconds per epoch sampling neighbors versus 3.5 seconds for the forward and backward pass. The alternatives are unsatisfying: building one sparse graph and reusing it every epoch locks training into a single fixed topology, while resampling a fresh sparse graph each epoch can make sparsification as expensive as the training it was meant to accelerate.

EDiS aims to break that trade-off by extracting graph structure once, caching it as a library of non-overlapping (edge-disjoint) subgraphs, and then cheaply recombining those subgraphs into a different sparse graph at each epoch under an explicit edge-budget constraint — without rerunning extraction.

Key Contributions

1. A cacheable, edge-budget-agnostic graph decomposition. EDiS extracts structural subgraphs once, then recomposes them into training graphs with edge-budget constraints across epochs and sparsity levels, without rerunning extraction or changing the GNN architecture or loss.
2. A selector-agnostic composition procedure. To the authors' knowledge, EDiS is the first method to separate extraction from composition, so composition is independent of the mechanism that built the subgraphs (for example, maximum spanning forests or random selection).
3. A combinatorial analysis of the sampler. For maximum-score residual forests, the authors prove score-aware cut preservation for the stored decomposition; for any residual selector, they characterize conditional retention and high-score cut survival in the composed graph.
4. A controlled empirical study of structural reuse. Matched-edge-budget experiments across 17 baselines and 19 datasets test whether a cacheable structural decomposition plus epoch variation justify their construction cost.

Main Findings

• EDiS-Lite leads the ranked baselines at both tested budgets. At retention ratio ρ = 0.30, EDiS-Lite attains a mean benchmark score of 75.95, an average rank of 2.53, and an average gap to the best ranked method of 1.25 points. At ρ = 0.50, it attains 77.76, rank 3.32, and gap 1.23. Rank and gap are computed per dataset against the best ranked method and then averaged.

• Highest geometric and arithmetic means over 19 datasets at ρ = 0.30. Ranking excludes the four reference rows (MLP with no graph, Spanning Tree, Full GCN, and EDiS-Full). For reference context from the same table: MLP no-graph AM 65.82 / GM 63.49; Spanning Tree AM 73.77 / GM 71.31; Full GCN AM 80.17 / GM 78.17; EDiS-Full AM 78.13 / GM 76.16.

• Full-graph inference recovers accuracy lost to sparsification, at a cost. EDiS-Lite and EDiS-Full share the same trained model and differ only at inference (sparse composed graph versus full graph). At tight budgets EDiS-Lite can trail the independently tuned Full GCN reference, most visibly on Minesweeper (EDiS-Lite 73.82 versus Full GCN 97.49) and Pokec; switching to the full graph recovers much of the difference without retraining, and the gap shrinks as ρ grows. Recovery is not free: evaluation time rises and peak GPU memory increases mildly, while training cost is unchanged. Reddit is described as a mild exception, where EDiS-Lite already sits close to Full GCN.

• Structure and resampling, not just edge count, drive the gains. Against three matched-budget controls — Frozen (one sampled graph reused for the whole run), Direct (score-based edge sampling without forming subgraphs), and Shuffled groups (identical subgraph sizes but scrambled membership) — EDiS-Lite matches or leads across the measured budget range, with the largest margin at tight budgets. Removing epoch variation (Frozen) hurts most at small budgets. Shuffled groups is consistently the weakest control despite matching EDiS's subgraph sizes exactly.

• Results are robust to selector and score choice. Sweeping seven selectors (MaxCF, MinCF, Degree, k-NN, Spanner, Random, Hybrid) and five edge scores (cosine, Euclidean, Dot, Uniform, MLP-score) through the identical composition procedure, most combinations land within a couple of points of the best choice on a given dataset, and no single selector or score dominates. The default MaxCF plus cosine pairing stays competitive throughout.

• Extraction depth is not monotonically helpful. Varying the extraction cap K_max on five large graphs at ρ = 0.30, more subgraphs help on some datasets and hurt on others, and EDiS-Lite and EDiS-Full do not always agree. Once extraction stops before the cap, a larger K_max changes nothing.

• The framework is backbone-agnostic. Fixing MaxCF and cosine similarity but switching the backbone from GCN to GraphSAGE, both backbones improve with budget and stay close, with neither better overall.

• Two separate theoretical guarantees. Theorem 1 shows that when each subgraph is a maximum-score covering forest of the current residual graph, stored prefixes preserve score-threshold cut certificates: cuts that mattered in the full graph retain crossing edges once enough subgraphs are kept. Theorem 2 is selector-agnostic and conditional on the sampled subgraph order, giving a bound on the probability that a cut's high-score edges survive composition — but it gives no guarantee that the composed graph stays connected at any fixed budget.

Methodology in Plain English

EDiS splits the problem into two stages that run at completely different frequencies.

Stage one — decomposition (once). Every edge gets a fixed score. The default is a shifted cosine similarity between the two endpoint feature vectors; other scores are also supported. A residual selector then repeatedly carves out one subgraph at a time from the edges not yet used. The default selector extracts a maximum-score covering forest from the remaining edges — effectively a high-score backbone that keeps the graph connected — removes those edges, and repeats on what is left. This produces an edge-disjoint collection of K subgraphs plus a leftover residual pool. Each subgraph also gets a weight equal to the sum of its edge scores, floored at a small positive value ε so sampling weights stay strictly positive. Subgraphs, weights, and the residual pool are computed once and stay fixed, independent of the edge budget.

Stage two — composition (every epoch). At each epoch, EDiS draws a weighted random ordering of the subgraphs without replacement, adds them one at a time until the edge budget is reached or exceeded, trims excess by removing the lowest-weighted subgraph in full and partially trimming at most one subgraph, or fills any shortfall uniformly from the residual pool. The result always matches the budget exactly. The GNN architecture, parameters, and loss are unchanged; only the sparse adjacency used for message passing differs from epoch to epoch.

Why this matters conceptually. A 30% edge budget does not mean the model sees the same 30% of edges all run; it means each epoch processes 30% of the edges, while different epochs are exposed to different parts of the original graph. Over T epochs, the total number of distinct edges seen can be far larger than the per-epoch budget. The authors also note a deterministic alternative that always takes the top subgraphs would repeat the same subgraphs every epoch, collapsing the epoch-to-epoch diversity that drives most of the gain at tight budgets; and that at very small budgets one high-weight subgraph may already fill the budget, so variation comes mainly from trimming within that subgraph rather than subgraph choice.

Evaluation. The study uses 19 node-classification benchmarks — six heterophilic, eight homophilic, and five large-scale — with accuracy as the metric except for Minesweeper, Questions, and ogbn-proteins, where ROC-AUC is used. Baselines comprise three reference anchors (graph-free MLP, spanning tree, tuned full-graph GCN), 11 topology-guided sparsifiers, and three semantic-guided sparsifiers. All methods share the same architecture, optimizer, and epoch budget per dataset; predictive runs are matched in count across methods and averaged per dataset.

Why This Matters

Impact on research. Most sparsification work searches for a single good sparse graph to stand in for the original. EDiS reframes the goal as building a reusable structural library that generates many sparse views. That shift — plus the deliberate split of guarantees between the stored decomposition (strong, selector-specific, established once) and the composed graph (weaker but selector-agnostic) — gives a template for decoupling construction cost from training-time flexibility. The edge-disjointness constraint is what makes the library cacheable and cheap to recombine.

Real-world applications.

• Large-scale social and recommendation graphs. Training GNNs on graphs with hundreds of thousands of nodes and millions of edges (the paper's Reddit example has 233K nodes and 11.6M edges) is where neighbor-sampling overhead dominates; a cached decomposition avoids paying that cost every epoch.
• Repeated model retraining on a stable topology. When the underlying graph changes rarely but models are retrained or hyperparameter-tuned repeatedly, the one-time decomposition can be amortized across many runs.
• Resource-constrained deployment and edge inference. Edge budgets give explicit control over memory and compute, and EDiS-Lite versus EDiS-Full offers a documented accuracy-versus-inference-cost dial, relevant for latency-sensitive inference.
• Domain graphs with informative node features. Because the default edge score uses endpoint feature similarity, the method is well positioned for citation, co-purchase, protein, and web-link graphs where feature similarity is a meaningful signal — the exact benchmark families tested here.

Industry relevance. The framework requires no change to GNN architecture, optimizer, or loss, which lowers adoption friction. The composition step is reported to scale with the edge budget B and the number of subgraphs K rather than the total edge count m, so decomposition cost amortizes across epochs and budgets. That directly targets the cost structure practitioners care about in production training pipelines.

Future Directions

• Task-aware edge scores for decomposition. The current scores are feature-based and fixed before training; adapting scoring to the downstream task is left open.
• Dynamic (temporal) composition. Extending the composition mechanism to graphs that change over time is listed as future work.
• Extensions beyond node classification. The authors propose graph-level and link-level prediction as next targets, since the current evaluation is entirely node classification.
• Practical limits of the guarantees. Theorem 2 gives no guarantee that the composed training graph stays connected at a fixed budget, and the paper reports that additional stored subgraphs do not always produce a better graph — both point to open questions about how to choose extraction depth and how to close the gap between the stored decomposition's certificate and what the composed graph actually preserves. The paper also notes that full-graph inference recovery has a cost measured in evaluation time and peak GPU memory; details of the runtime and memory breakdowns and of the cost analysis sit in appendices not included in this excerpt, and specific figures are not reported in the text above.

Target Audience

Researchers and practitioners working on scalable GNN training, graph sparsification, and graph sampling will get the most from this paper. It is also relevant to systems-oriented machine learning engineers who need explicit control over per-epoch compute and memory budgets without retraining from scratch, and to theoreticians interested in cut-preservation guarantees that separate offline structure construction from online graph sampling. Readers should be comfortable with GNN message passing, edge-budget notation, and basic spanning-forest and graph-cut concepts; the mathematical content is concentrated in two theorems and their appendices rather than spread across the whole paper.

Authors’ abstract

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, under the default covering-forest selector, the stored decomposition deterministically preserves high-score cut edges, and we derive a selector-agnostic conditional bound on high-score cut survival in composed training graphs. Across 19 homophilic, heterophilic, and large-scale node classification benchmarks against 17 baselines under the same edge budget, EDiS achieves the highest mean benchmark score (accuracy/ROC-AUC) and the lowest average rank and gap-to-best among ranked methods. Ablations show the clearest benefits of structural decomposition and epoch variation at tight edge budgets.