EDiS：面向图神经网络的边缘不相交子图稀疏化框架

# EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks
Source: [https://arxiv.org/html/2610.09059](https://arxiv.org/html/2610.09059)
Sai Karthik Navuluru, Siddhartha Shankar Das, Franck Dernoncourt, S M Ferdous, Ryan A\. Rossi, Nesreen K\. Ahmed, Baris Coskunuzer, Alex Pothen, Lakshman Tamil, Mahantesh M HalappanavarUniversity of Texas at Dallas Pacific Northwest National Laboratory Adobe ResearchUniversity of North Carolina at Charlotte Cisco Purdue University

###### 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 introduceEDiS\(Edge\-DisjointSubgraph sparsification framework\), which separates*one\-time structural extraction*from*per\-epoch graph composition*\.EDiSdecomposes 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\.

## 1Introduction

Graph neural networks \(GNNs\) propagate information along the edges of the graph\([Kipf and Welling, 2017](https://arxiv.org/html/2610.09059#bib.bib1)\), which determines the amount of information computed, exchanged, and stored at each epoch during training of the GNN\. Sparsifying the graph, by selectively removing edges, can therefore reduce the computational costs\([Chen et al\., 2021](https://arxiv.org/html/2610.09059#bib.bib14)\), but adds a different cost of deciding*which*edges to keep \(or remove\)\. In some sampling\-based methods, this cost dominates training itself\. For example, on Reddit, a graph with 233K nodes and 11\.6M edges, the sampling\-based method AS\-GCN\([Huang et al\., 2018](https://arxiv.org/html/2610.09059#bib.bib4)\)spends 20\.7 seconds per epoch for sampling neighbors, versus 3\.5 seconds for the forward and backward pass\([Zeng et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib6)\)\. Thus, a sparsified graph does not guarantee economical training if the graph must be rebuilt frequently\.

One option is to build a sparse graph once and reuse it every epoch to amortize the cost of sparsification\. However, this also locks the GNN into the same set of edges for the entire training run\([Chen et al\., 2021](https://arxiv.org/html/2610.09059#bib.bib14);[Seo et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib50)\)\. Another option is to change the sparse graph over time using different approaches such as repeated subgraph sampling in GraphSAINT\([Zeng et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib6)\), incrementally grown spanning subgraph in SpanGNN\([Gu et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib48)\), or computing a fresh random spanning tree at each epoch in GERN\([Bonchi et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib41)\)\. While these methods show the value of varying sparse views during training, each couples graph variation to a particular sampling or structural\-update mechanism at a fixed sparsity level\. To the best of our knowledge, existing methods do not formulate the problem as a persistent, edge\-disjoint structural library that is built once and efficiently recombined into different sparse graphs during training\. This leads to an important question:*Can we extract graph structure once and reuse it to cheaply generate many different training graphs with specific edge\-budget constraints?*

EDiS\(Edge\-DisjointSubgraph sparsification framework\) addresses this question by turning edge\-disjointness from a one\-off computational step into a*cacheable training paradigm*\. It decomposes the original graph into persistent and non\-overlapping structural subgraphs only once\. It then repeatedly recombines them into training graphs with edge\-budget constraints across epochs and retention ratios, without recomputing the decomposition\. In our default setup, subgraphs are successive connectivity\-preserving sparse backbones, extracted from residual edges and cached before the GNN training begins\.

While GNN architecture, parameters, and training objectives remain the same, the sparse message\-passing graph changes across epochs\. For example, a30%30\\%edge budget does not mean the model is stuck with the same30%30\\%of edges for the entire run, but that it processes30%30\\%of edges per epoch, while different epochs are exposed to different parts of the original graph \(Figure[1](https://arxiv.org/html/2610.09059#S1.F1)\)\.

Figure 1:EDiSgenerates sparse training graphs under a fixed edge budget\.EDiShas three main components:*edge scoring*,*structural extraction*, and*budgeted composition*\. While the first two are a one\-time computation, budgeted composition is repeated at every epoch with specific edge\-budgets\. Edge scores rank connections, a residual selector groups them into cacheable subgraphs, and composition selects a training graph from those subgraphs\. The subgraphs in extraction are disjoint, but edges can be repeated over time in the composed graphs \(𝒢B\(t\)\\mathcal\{G\}\_\{B\}^\{\(t\)\}\)\.

Our default algorithm pairs feature\-based cosine scores with successive maximum\-score covering forests\. The first forest provides a high\-score, connectivity\-preserving backbone of the original graph, and once these edges are removed, later forests span the connected components of the residual graph using previously unused edges\. During training, the stored subgraphs are sampled with score\-dependent priority and combined until the target budget is reached, trimming excess edges and filling any shortfall from the residual pool \(detailed in Section[3](https://arxiv.org/html/2610.09059#S3)\)\.

EDiSis not tied to one scoring or selection function: edge scoring and residual selection functions are modular, so any combination shares the same edge\-budget\-constrained procedure \(Section[3](https://arxiv.org/html/2610.09059#S3)\)\. Separating extraction from composition also clarifies what we can guarantee: for maximum\-score residual forests, stored prefixes preserve score\-threshold cut certificates, and since a single epoch’s graph may omit or trim these forests, we separately characterize conditional edge retention and fixed\-cut survival under composition for any residual selector\. Matched\-budget ablations provide empirical evidence that structural grouping and epoch resampling contribute to predictive performance \(Section[4\.3](https://arxiv.org/html/2610.09059#S4.SS3)\)\.

We evaluateEDiSagainst 17 baselines on 19 datasets spanning homophilic, heterophilic, and large\-scale graphs, separating sparse\-graph inference \(EDiS\-Lite\) from full\-graph inference \(EDiS\-Full\), while isolating structural decomposition, epoch resampling, selector choice, and edge scoring through matched\-edge\-budget ablations\. At30%30\\%retention,EDiS\-Lite achieves the highest mean benchmark score among ranked methods \(average rank2\.532\.53, gap1\.251\.25points\), whileEDiS\-Full serves as a reference \(Section[4](https://arxiv.org/html/2610.09059#S4)\)\. Cacheable subgraphs and graph variation give the largest gains at tight edge\-budgets, while fixed graphs or simpler sampling remain competitive elsewhere\.

Our contributions are as follows\.

- •A cacheable, edge\-budget\-agnostic graph decomposition:EDiSextracts 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\.
- •A novel, selector\-agnostic composition procedure:To the best of our knowledge,EDiSis the first method to separate extraction from composition: composition is independent of the extraction methods that build the subgraphs \(e\.g\., maximum spanning forests or random selection\)\.
- •A combinatorial analysis of the sampler:For maximum\-score residual forests, we prove score\-aware cut preservation for the stored decomposition; for any residual selector, we characterize conditional retention and high\-score cut survival in the composed graph\.
- •A controlled empirical study of structural reuse:Matched\-edge\-budget experiments across 17 baselines and 19 datasets test whether a cacheable structural decomposition and epoch variation justify their construction cost\.

## 2Related Work

Existing methods either decide which part of the graph to use every step, or decide once and fix the graph beforehand via sparsification\.EDiSsits between these two settings, deciding once but still varying the graph every epoch\. It builds a cacheable edge\-disjoint structural library once, then composes an exact\-budget graph at each epoch\. This section relatesEDiSto four lines of work\.

Sampling\-based GNN training\.Neighbor sampling bounds neighbors per node\([Hamilton et al\., 2017](https://arxiv.org/html/2610.09059#bib.bib2)\)\. Layer\-wise sampling instead scores whole node layers\([Chen et al\., 2018](https://arxiv.org/html/2610.09059#bib.bib3)\), and LADIES conditions each layer on the layer above it to stay connected\([Zou et al\., 2019](https://arxiv.org/html/2610.09059#bib.bib43)\)\. Subgraph methods sample subgraphs directly\([Chiang et al\., 2019](https://arxiv.org/html/2610.09059#bib.bib5)\)or correct the resulting bias\([Zeng et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib6)\), and attribute\-guided sampling prioritizes edges by similarity and diversity\([Das et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib40)\)\. All of these resample the full topology at every step, rather than keeping an altered one\. Other work avoids resampling by caching past embeddings\([Fey et al\., 2021](https://arxiv.org/html/2610.09059#bib.bib9)\), quantizing or compressing activations\([Ding et al\., 2021](https://arxiv.org/html/2610.09059#bib.bib10);[Liu et al\., 2022](https://arxiv.org/html/2610.09059#bib.bib13)\), repartitioning across workers\([Wan et al\., 2022](https://arxiv.org/html/2610.09059#bib.bib11)\), or compensating for missing cross\-partition messages\([Shi et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib12)\)\.EDiSinstead organizes the topology once and reuses precomputed subgraphs under an explicit edge\-budget, rather than resampling every step\.

Graph sparsification\.A large family of methods target edge removal before training begins, which includes degree\- and similarity\-based heuristics\([Hamann et al\., 2016](https://arxiv.org/html/2610.09059#bib.bib18);[Satuluri et al\., 2011](https://arxiv.org/html/2610.09059#bib.bib20);[Liu et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib23)\), spectral and distance\-preserving sparsifiers\([Spielman and Srivastava, 2008](https://arxiv.org/html/2610.09059#bib.bib22);[Peleg and Schäffer, 1989](https://arxiv.org/html/2610.09059#bib.bib39)\), and cut sparsifiers built by repeatedly extracting a maximum spanning forest\([Benczúr and Karger, 1996](https://arxiv.org/html/2610.09059#bib.bib49);[Forster and de Vos, 2023](https://arxiv.org/html/2610.09059#bib.bib31)\)\. In contrast, some methods learn which edges to retain jointly with graph learning\([Chen et al\., 2021](https://arxiv.org/html/2610.09059#bib.bib14);[Seo et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib50);[Zhang et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib24);[Das et al\., 2026](https://arxiv.org/html/2610.09059#bib.bib51);[Zhang et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib25)\)\. However, no single method effectively preserves multiple graph properties of interest well\([Chen et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib16)\)\.EDiSemploys similar sparsification principles, such as degree\-, neighbor/similarity\-, spanner\-, and forest\-based residual selection, and its composition step treats them identically regardless of the method used to build the library\.

Stochastic topology variation\.DropEdge\([Rong et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib42)\)and dropout\-induced subgraphs\([Luo et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib28)\)vary the topology by removing edges independently at random at each epoch\. Other methods instead learn edge predictors\([Chen et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib46)\)or stabilize message passing under a changing structure\([Lee et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib47)\)\. These structures overlap substantially across epochs and carry no edge\-budget or structural guarantee\. By contrast,EDiS’s epoch\-to\-epoch variation comes from a controlled, cacheable partition rather than independent per\-edge noise\.

Cacheable edge\-disjoint decomposition\.A few methods train over a sequence of sparse structures\. For example, SpanGNN\([Gu et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib48)\)trains on grown subgraphs and GERN\([Bonchi et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib41)\)trains on random spanning trees, but neither is persistent\. Prior edge\-disjoint methods use disjoint structures as sampled or sequential objects, not as a persistent, budget\-agnostic decomposition recomposed into exact\-budget graphs across epochs and retention ratios\. To the best of our knowledge,EDiSis the first approach to decouple one\-time extraction from per\-epoch composition, so it stays cached and reused throughout training\. Appendix[B](https://arxiv.org/html/2610.09059#A2)\(Table[4](https://arxiv.org/html/2610.09059#A2.T4)\) compares these methods by budget, reusability, exposure, and disjointness\. Appendixadds quantitative comparisons against SpanGNN and GERN, and discusses our attempted AGS\-GNN evaluation\.

## 3EDiS: A Structured Sparsification Framework

Sparse GNN training poses a tradeoff between computational cost and graph coverage\. While reusing a sparse graph built once for the entire training is cheap, it significantly limits learning by fixing the graph structure for every epoch\. Thus, changing the sparse graph over time exposes the GNN to more of the original topology\. However, rebuilding from scratch at every epoch can make sparsification as expensive as the training it was meant to speed up\.

EDiSaddresses this tradeoff using two main components:*Decomposition*, a one\-time step that builds the cached structural library; and*Composition*, a per\-epoch step that composes a graph from the library\. We extract structural information once, organize it into cacheable edge\-disjoint subgraphs, and recombine them into an exact\-budget graph each epoch\. The GNN then processes only a fixed number of edges at a time, while seeing many structured subsets of the graph\. The same GNN parameters are trained throughout, and only the sparse message\-passing graph varies across epochs, illustrated in Figure[2](https://arxiv.org/html/2610.09059#S3.F2)\.

Figure 2:Overview of theEDiSpipeline\.### 3\.1One GNN, Many Sparse Views

Let𝒢=\(𝒱,ℰ,𝐗\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\},\\mathbf\{X\}\)be an undirected graph withnnnodes,mmedges, and node features𝐗\\mathbf\{X\}\. An edge\-retention ratioρ∈\(0,1\]\\rho\\in\(0,1\]sets the training budgetB=⌈ρ​m⌉B=\\lceil\\rho m\\rceil, the maximum number of edges used for a given epoch\.EDiS*does not pick oneBB\-edge graph and train on it for the whole run*\. Instead, the same GNN trains on a sequence of different sparse graphs, a different one for each epochtt,

𝒢B\(t\)=\(𝒱,ℰB\(t\),𝐗\),\|ℰB\(t\)\|=B,\\mathcal\{G\}\_\{B\}^\{\(t\)\}=\\bigl\(\\mathcal\{V\},\\mathcal\{E\}\_\{B\}^\{\(t\)\},\\mathbf\{X\}\\bigr\),\\qquad\|\\mathcal\{E\}\_\{B\}^\{\(t\)\}\|=B,\(1\)whereℰB\(t\)\\mathcal\{E\}\_\{B\}^\{\(t\)\}is freshly composed each epoch\.

The GNN’s parameters are shared across all epochs, and a GCN layer at epochttstill uses

𝐇ℓ\+1=σ⁡\(𝐀^B\(t\)​𝐇ℓ​𝐖ℓ\),𝐇0=𝐗,\\mathbf\{H\}\_\{\\ell\+1\}=\\sigma\\\!\\left\(\\widehat\{\\mathbf\{A\}\}\_\{B\}^\{\(t\)\}\\mathbf\{H\}\_\{\\ell\}\\mathbf\{W\}\_\{\\ell\}\\right\),\\qquad\\mathbf\{H\}\_\{0\}=\\mathbf\{X\},where only the sparse adjacency𝐀^B\(t\)\\widehat\{\\mathbf\{A\}\}\_\{B\}^\{\(t\)\}changes from epoch to epoch, while the learned weights𝐖ℓ\\mathbf\{W\}\_\{\\ell\}are updated through backpropagation\. OverTTepochs, the total number of distinct edges seen,\|⋃t=1TℰB\(t\)\|\\bigl\|\\bigcup\_\{t=1\}^\{T\}\\mathcal\{E\}\_\{B\}^\{\(t\)\}\\bigr\|, can therefore be much larger thanBB, even though each epoch is limited byBB\.

The challenge is to generate new sparse graphs without rerunning extraction for each epoch\.EDiSsplits the method into two stages, a one\-time decomposition \(parametrized by edge scoressand residual selectorℱ\\mathcal\{F\}, defined next\), and an efficient per\-epoch composition\.

𝒟=Decompose\(𝒢;s,ℱ\),ℰB\(t\)=Compose\(𝒟,B;ξt\)\.\\boxed\{\\mathcal\{D\}=\\operatorname\{Decompose\}\(\\mathcal\{G\};s,\\mathcal\{F\}\),\\qquad\\mathcal\{E\}\_\{B\}^\{\(t\)\}=\\operatorname\{Compose\}\(\\mathcal\{D\},B;\\xi\_\{t\}\)\.\}\(2\)The decomposition𝒟\\mathcal\{D\}is computed once, and each epoch then needs only randomnessξt\\xi\_\{t\}to compose a newBB\-edge graph from it\. This composition is*not*adapted by the GNN loss, since the edge scores, subgraphs, and weights it draws on are all fixed before training begins\.

### 3\.2One\-Time Structural Decomposition

Each original edgee=\(u,v\)e=\(u,v\)gets a fixed scoreses\_\{e\}, with higher scores preferred by the selector\. Our default score is a shifted cosine similarity between endpoint features,

su​v=12​\(1\+𝐱u⊤​𝐱v‖𝐱u‖2​‖𝐱v‖2\)\.s\_\{uv\}=\\frac\{1\}\{2\}\\left\(1\+\\frac\{\\mathbf\{x\}\_\{u\}^\{\\top\}\\mathbf\{x\}\_\{v\}\}\{\\\|\\mathbf\{x\}\_\{u\}\\\|\_\{2\}\\,\\\|\\mathbf\{x\}\_\{v\}\\\|\_\{2\}\}\\right\)\.\(3\)Thus, the default score also depends on both the node features and graph topology\. In Section[4](https://arxiv.org/html/2610.09059#S4)we evaluate other scoring methods\. Scores alone, however, do not decide the subgraphs\. A*residual selector*ℱ\\mathcal\{F\}picks one subgraph at a time from remaining edges, mapping it to a subset at roundkk,

ℰk=ℱ⁡\(𝒱,ℰrem\(k−1\),s\)⊆ℰrem\(k−1\)\.\\mathcal\{E\}\_\{k\}=\\mathcal\{F\}\\bigl\(\\mathcal\{V\},\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(k\-1\)\},s\\bigr\)\\subseteq\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(k\-1\)\}\.\(4\)
The selector may usessor ignore it entirely, and need not return a forest or a fixed edge count\.EDiStreats all selectors the same way during training, supporting degree\-based, neighbor\-based, spanner, and random selectors \(detailed in Appendix[F\.1](https://arxiv.org/html/2610.09059#A6.SS1)\)\.

Our default selector,ℱmax\\mathcal\{F\}\_\{\\max\}, groups edges into*structural subgraphs*rather than picking high\-score edges one at a time\. At each round, it extracts a maximum\-score covering forest \(MaxCF\) from the remaining edges\. At roundkk,

ℰk=ℱmax\(𝒱,ℰrem\(k−1\),s\)∈arg​maxF​covering forest∑e∈Fse,ℰrem\(k\)=ℰrem\(k−1\)∖ℰk\.\\mathcal\{E\}\_\{k\}=\\mathcal\{F\}\_\{\\max\}\\bigl\(\\mathcal\{V\},\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(k\-1\)\},s\\bigr\)\\in\\operatorname\*\{arg\\,max\}\_\{F\\text\{ covering forest\}\}\\sum\_\{e\\in F\}s\_\{e\},\\qquad\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(k\)\}=\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(k\-1\)\}\\setminus\\mathcal\{E\}\_\{k\}\.\(5\)Extraction stops when the per\-round limit is reached, the coverage target is met, or no edges remain, givingKKsubgraphs\. These choices are fixed once, independent ofBB\. This independence, rather than the absence of choices, is what*budget\-agnostic*means in this context\. The first subgraphℰ1\\mathcal\{E\}\_\{1\}is thus a high\-score, connectivity\-preserving backbone\. After removing those edges,ℰ2\\mathcal\{E\}\_\{2\}gives an alternative backbone from remaining edges, and so on\. The result is an edge\-disjoint collection,

ℰ=ℰ1⊔⋯⊔ℰK⊔ℰres,\\mathcal\{E\}=\\mathcal\{E\}\_\{1\}\\sqcup\\cdots\\sqcup\\mathcal\{E\}\_\{K\}\\sqcup\\mathcal\{E\}\_\{\\mathrm\{res\}\},\(6\)whereℰres\\mathcal\{E\}\_\{\\mathrm\{res\}\}holds any edges not assigned to a stored subgraph\. Each subgraph also receives a weight,

wk=max⁡\{∑e∈ℰkse,ε\},w\_\{k\}=\\max\\Bigl\\\{\\textstyle\\sum\_\{e\\in\\mathcal\{E\}\_\{k\}\}s\_\{e\},\\ \\varepsilon\\Bigr\\\},\(7\)sowkw\_\{k\}is the subgraph’s total score, floored at a smallε\>0\\varepsilon\>0to keep sampling weights strictly positive\. This floor is not a maximum over individual edges, sowkw\_\{k\}always reflects the subgraph’s aggregate score, not that of any single edge\. The subgraphs, weights, and residual pool are computed once and stay fixed\.

### 3\.3An Exact\-Budget Graph at Every Epoch

At epochtt,EDiSdecides which subgraphs to include, and in what order, by drawing a weighted random ordering without replacement\. IfRrR\_\{r\}is the set of subgraphs still available before drawrr,

π\(t\)=\(k1,…,kK\),Pr⁡\(kr=k∣Rr\)=wk∑j∈Rrwj\.\\pi^\{\(t\)\}=\(k\_\{1\},\\ldots,k\_\{K\}\),\\qquad\\Pr\(k\_\{r\}=k\\mid R\_\{r\}\)=\\frac\{w\_\{k\}\}\{\\sum\_\{j\\in R\_\{r\}\}w\_\{j\}\}\.\(8\)Higher\-weighted subgraphs are thus more likely to appear early, but no fixed order is imposed\. We weight by total score, not average score\. We add subgraphs one at a time in this order, stopping once the edge count reaches or surpassesBB\. If it overshootsBB, we remove edges starting with the lowest\-weighted subgraph\. Each low\-weight subgraph is removed in full until the remaining excess is smaller than the next subgraph, which is then trimmed by that amount and kept\. At most one subgraph ends up partially trimmed\. Every higher\-weighted subgraph remains in its entirety\. If instead there is a shortfall, it is filled uniformly fromℰres\\mathcal\{E\}\_\{\\mathrm\{res\}\}\. Either way, the result satisfies

\|ℰB\(t\)\|=B\.\\boxed\{\|\\mathcal\{E\}\_\{B\}^\{\(t\)\}\|=B\.\}\(9\)A deterministic alternative that always takes the top subgraphs will repeat the same subgraphs for every epoch, thus collapsing the epoch\-to\-epoch diversity that drives most ofEDiS’s gain at tight budgets \(Appendix[E\.6](https://arxiv.org/html/2610.09059#A5.SS6), Appendix\)\. Exact construction and boundary cases appear in Appendix[C\.5](https://arxiv.org/html/2610.09059#A3.SS5)\. A worked example in Appendix[D](https://arxiv.org/html/2610.09059#A4)shows different selectors producing different subgraphs that still compose into the same edge budget\. At small budgets, one high\-weight subgraph may already fillBB, so variation comes mainly from trimming within that subgraph, not the choice of subgraph itself\. AsBBgrows and several subgraphs are needed, epoch\-to\-epoch variation increasingly comes from the differences at the subgraph\-level\.

The distinction from a fixed sparsifier matters\. A one\-shot method trains the GNN on the same set of edges every epoch,

ℰB,ℰB,…,ℰB,\\mathcal\{E\}\_\{B\},\\mathcal\{E\}\_\{B\},\\ldots,\\mathcal\{E\}\_\{B\},\(10\)whereasEDiStrains the same GNN on a different graph at each epoch,

ℰB\(1\),ℰB\(2\),…,ℰB\(T\)\.\\mathcal\{E\}\_\{B\}^\{\(1\)\},\\mathcal\{E\}\_\{B\}^\{\(2\)\},\\ldots,\\mathcal\{E\}\_\{B\}^\{\(T\)\}\.\(11\)EDiSthus pairs sparse per\-epoch computation with exposure to many structured views of the graph\. Under the implementation conditions of Appendix[F\.2](https://arxiv.org/html/2610.09059#A6.SS2), per\-epoch composition scales withBBandKKrather thanmm, so decomposition costs amortize across epochs and budgets\.

### 3\.4Structural Preservation for Decomposition and Composition

Since composition can omit or trim subgraphs for a smaller budget, the structural guarantees for the cached decomposition𝒟\\mathcal\{D\}may not hold for the composed graphℰB\(t\)\\mathcal\{E\}\_\{B\}^\{\(t\)\}, which is processed by the GNN at each epoch\. We therefore analyze these two objects separately\.

Both guarantees below concern cuts carrying many high\-score edges, so we index by a score thresholdτ\\tau\. LetUk=ℰ1∪⋯∪ℰkU\_\{k\}=\\mathcal\{E\}\_\{1\}\\cup\\cdots\\cup\\mathcal\{E\}\_\{k\}, and letℰ≥τ=\{e∈ℰ:se≥τ\}\\mathcal\{E\}\_\{\\geq\\tau\}=\\\{e\\in\\mathcal\{E\}:s\_\{e\}\\geq\\tau\\\},𝒢≥τ=\(𝒱,ℰ≥τ\)\\mathcal\{G\}\_\{\\geq\\tau\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{\\geq\\tau\}\), andUk,≥τ=Uk∩ℰ≥τU\_\{k,\\geq\\tau\}=U\_\{k\}\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\. For a nontrivial node setS⊊𝒱S\\subsetneq\\mathcal\{V\}and graphHH,δH​\(S\)\\delta\_\{H\}\(S\)denotes the edges ofHHcrossing the cut induced bySS\.

The stored decomposition\.MaxCFs satisfy a bottleneck property \(Fact[1](https://arxiv.org/html/2610.09059#Thmfact1)\)\. Together with the successive\-forest cut certificate \(Fact[2](https://arxiv.org/html/2610.09059#Thmfact2)\), which yields the guarantee below\.

###### Theorem 1\(Score\-threshold cut preservation\)\.

If each subgraph is a MaxCF of the current residual graph, then for every completed round1≤k≤K1\\leq k\\leq K, thresholdτ\\tau, and a nontrivial cutSS,

\|δUk,≥τ​\(S\)\|≥min⁡\{k,\|δ𝒢≥τ​\(S\)\|\}\.\\bigl\|\\delta\_\{U\_\{k,\\geq\\tau\}\}\(S\)\\bigr\|\\geq\\min\\bigl\\\{k,\\,\|\\delta\_\{\\mathcal\{G\}\_\{\\geq\\tau\}\}\(S\)\|\\bigr\\\}\.\(12\)

\(Proof and top\-kkcorollary are in Appendices[E\.2](https://arxiv.org/html/2610.09059#A5.SS2)–[E\.3](https://arxiv.org/html/2610.09059#A5.SS3)\)\. Informally, cuts that mattered in𝒢\\mathcal\{G\}retain crossing edges once enough subgraphs are kept\. This holds for the default covering\-forest selector\.

The composed training graph\.OnceB<\|UK\|B<\|U\_\{K\}\|, the sparse\-budget regime this paper targets,ℰB\(t\)\\mathcal\{E\}\_\{B\}^\{\(t\)\}need not contain anyUkU\_\{k\}\. We therefore bound retention for the composed graph directly, conditioning on the sampled subgraph orderπ\(t\)\\pi^\{\(t\)\}\. Index the residual edge set ask=0k=0alongside theKKstored subgraphs\. Letθk\\theta\_\{k\}be setkk’s retained fraction after trimming andxk​\(S,τ\)x\_\{k\}\(S,\\tau\)its edges crossingSSwith score at leastτ\\tau\.

###### Theorem 2\(Conditional retention under composition\)\.

Condition on the subgraph orderπ\(t\)\\pi^\{\(t\)\}and trim each subgraph uniformly at random to its retained size\. For any nontrivial cutSSand thresholdτ\\tau, the probability that the composed edge setℰB\(t\)\\mathcal\{E\}\_\{B\}^\{\(t\)\}keeps a high\-score edge crossingSSsatisfies

Pr\(ℰB\(t\)∩δ𝒢\(S\)∩ℰ≥τ≠∅\|π\(t\)\)≥1−exp\(−∑k=0Kθkxk\(S,τ\)\)\.\\Pr\\\!\\left\(\\mathcal\{E\}\_\{B\}^\{\(t\)\}\\cap\\delta\_\{\\mathcal\{G\}\}\(S\)\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\\neq\\varnothing\\;\\middle\|\\;\\pi^\{\(t\)\}\\right\)\\geq 1\-\\exp\\\!\\left\(\-\\sum\_\{k=0\}^\{K\}\\theta\_\{k\}\\,x\_\{k\}\(S,\\tau\)\\right\)\.\(13\)

\(Proof and the expected\-retention identity are detailed in Appendix[E\.5](https://arxiv.org/html/2610.09059#A5.SS5)\.\) Informally, a cut with enough high\-score edges is unlikely to be fully severed, so the message\-passing channel across it usually survives composition too, though no single subgraph’s survival is guaranteed\. Unlike Theorem[1](https://arxiv.org/html/2610.09059#Thmtheorem1), this bound is selector\-agnostic, needing only a uniform trim within each subgraph, not forest structure, but it gives no guarantee that𝒢B\(t\)\\mathcal\{G\}\_\{B\}^\{\(t\)\}stays connected at any fixedBB\(Appendix[E\.5](https://arxiv.org/html/2610.09059#A5.SS5)\)\.

Together, Theorems[1](https://arxiv.org/html/2610.09059#Thmtheorem1)and[2](https://arxiv.org/html/2610.09059#Thmtheorem2)deliberately decouple two guarantees typically bundled together, each scoped to where it holds\. The stored decomposition carries a strong, selector\-specific certificate established once at extraction time\. The composed graph instead carries a selector\-agnostic bound that holds for any selector, trading certificate strength for that generality, which is exactly what letsEDiSswap selectors freely\.

## 4Experimental Results

### 4\.1Experimental Setup

We perform empirical evaluation on 19 benchmark datasets \(six heterophilic, eight homophilic, and five large\-scale\) and node\-classification as the task, which is similar in spirit to[Luo et al\. \(2024\)](https://arxiv.org/html/2610.09059#bib.bib27)\. We use accuracy as the metric, except for Minesweeper, Questions, and ogbn\-proteins where we use ROC\-AUC as the metric\. Complete details are listed in Table[6](https://arxiv.org/html/2610.09059#A7.T6)\(Appendix[G](https://arxiv.org/html/2610.09059#A7)\)\. We compareEDiSagainst 17 other methods, including 3 reference anchors \(graph\-free MLP, spanning tree, and tuned full\-graph GCN\), 11 topology\-guided sparsifiers, and 3 semantic\-guided sparsifiers \(Appendix[G](https://arxiv.org/html/2610.09059#A7)\)\.

Our default pairs a GCN backbone with the MaxCF selector and cosine\-similarity as edge scores \(Theorem[1](https://arxiv.org/html/2610.09059#Thmtheorem1)\)\.EDiS\-LiteandEDiS\-Fullshare this pipeline and differ only at inference, using the sparse composed graph or the complete graph\.Full GCNis a separately tuned complete\-graph reference, distinct fromEDiSat100%100\\%retention\. Every method shares the same architecture, optimizer, and epoch budget per dataset \(Appendix[G\.4](https://arxiv.org/html/2610.09059#A7.SS4)\)\. Full\-batch training recomputes normalized adjacency from the current epoch graph, with scores guiding selection only \(not propagation\) \(Appendix[G\.3](https://arxiv.org/html/2610.09059#A7.SS3)\)\. Predictive runs, matched in count across methods, are averaged per dataset\.

### 4\.2Predictive Performance

\(RQ1, EDiS vs\. 17 baselines\) Does decoupling decomposition from composition cost accuracy at a matched budget?We benchmarkEDiSagainst all 17 baselines atρ=0\.30\\rho=0\.30on 19 datasets, reporting the geometric mean \(GM\) and arithmetic mean \(AM\) across all 19 datasets while excluding reference anchors\. Table[1](https://arxiv.org/html/2610.09059#S4.T1)shows EDiS\-Lite attaining the best GM and AM, ahead of every topology\- and semantic\-guided sparsifier at the same budget\.

MethodCoraCiteSeerAmazonPhotoWikiCSAmazonComp\.CoauthorCSPubMedChameleonSquirrelMinesweeperRef\.MLP \(No graph\)60\.14 ±2\.6257\.00 ±1\.1392\.16 ±0\.2473\.10 ±0\.1986\.99 ±0\.3995\.11 ±0\.0569\.82 ±1\.8636\.59 ±3\.3239\.77 ±1\.5951\.34 ±0\.77Spanning Tree80\.86 ±1\.1770\.50 ±0\.6492\.46 ±0\.1275\.05 ±0\.2389\.76 ±0\.3094\.68 ±0\.1480\.40 ±0\.9934\.72 ±2\.8136\.93 ±1\.5870\.73 ±0\.21Full GCN84\.26 ±0\.6672\.50 ±0\.3695\.95 ±0\.1480\.57 ±0\.0693\.70 ±0\.3195\.61 ±0\.3680\.76 ±0\.5544\.67 ±3\.8444\.79 ±1\.8297\.49 ±0\.18EDiS\-Full \(Ours\)84\.08 ±0\.8370\.88 ±0\.7896\.14 ±0\.1980\.39 ±0\.2993\.59 ±0\.0595\.98 ±0\.1580\.20 ±0\.4643\.13 ±2\.5343\.26 ±2\.4382\.62 ±1\.09Topology\-guidedRandom73\.40 ±0\.5165\.86 ±0\.9594\.38 ±0\.1677\.04 ±0\.6391\.05 ±0\.1594\.71 ±0\.0474\.26 ±0\.6237\.85 ±3\.3540\.90 ±1\.7072\.39 ±1\.04Rank Deg\.76\.34±0\.7865\.10 ±0\.2493\.79 ±0\.0576\.13 ±0\.5388\.04 ±0\.2894\.68 ±0\.0676\.38 ±0\.4640\.35 ±3\.8240\.17 ±1\.8971\.09 ±0\.21Local Deg\.73\.52 ±0\.4764\.76 ±0\.8494\.49 ±0\.0375\.69 ±0\.4889\.28 ±0\.3394\.93 ±0\.2277\.32±1\.0841\.37 ±2\.5941\.80 ±1\.6672\.53 ±1\.15Forest Fire71\.98 ±0\.3963\.82 ±1\.0595\.40 ±0\.2279\.20 ±0\.5892\.57 ±0\.1294\.67 ±0\.3373\.46 ±0\.8541\.28 ±1\.9643\.15 ±1\.9070\.76 ±0\.29G\-Spar72\.02 ±1\.0564\.28 ±0\.5793\.42 ±0\.3774\.91 ±0\.3991\.02 ±0\.2194\.78 ±0\.0873\.48 ±0\.9038\.62 ±4\.1339\.77 ±1\.5778\.97±0\.51L\-Sim75\.18 ±0\.7266\.06 ±0\.4294\.88 ±0\.1378\.71 ±0\.9693\.04 ±0\.0795\.02 ±0\.2976\.98 ±0\.7439\.71 ±3\.9739\.23 ±2\.3877\.17 ±0\.41SCAN71\.38 ±0\.6764\.54 ±0\.3794\.01 ±0\.2275\.08 ±0\.4491\.60 ±0\.1895\.09 ±0\.0274\.32 ±0\.5036\.05 ±3\.4139\.50 ±1\.1078\.53±0\.35L\-Spar71\.38 ±1\.4864\.32 ±0\.5794\.07 ±0\.2075\.10 ±0\.2590\.95 ±0\.2295\.03 ±0\.2273\.48 ±0\.9036\.11 ±3\.0639\.17 ±1\.3178\.45 ±0\.86Spectral72\.86 ±0\.8566\.82±0\.4495\.24 ±0\.2978\.80 ±0\.4792\.13 ±0\.1194\.68 ±0\.1375\.04 ±1\.4342\.98 ±3\.6043\.94±1\.1870\.48 ±1\.94tt\-Spanner72\.60 ±0\.9065\.70 ±0\.6394\.95 ±0\.2478\.07 ±0\.2391\.51 ±0\.1194\.64 ±0\.2774\.74 ±0\.5938\.71 ±3\.7242\.65 ±2\.0171\.13 ±1\.03DSpar73\.90 ±0\.3664\.70 ±1\.2295\.62±0\.3379\.47±0\.6893\.17±0\.0894\.52 ±0\.1277\.86±0\.4639\.73 ±3\.8743\.48±1\.5672\.56 ±2\.00Semantic\[\-2pt\]guidedUnified\-LTH72\.12 ±3\.4763\.76 ±1\.1991\.94 ±0\.3675\.49 ±0\.1786\.88 ±0\.7494\.99 ±0\.3775\.26 ±0\.6737\.61 ±3\.6738\.17 ±2\.0969\.70 ±1\.12AdaGLT72\.74 ±0\.6365\.26 ±1\.0094\.16 ±0\.1976\.48 ±0\.1391\.53 ±0\.4295\.13±0\.0875\.84 ±0\.5638\.03 ±4\.1242\.30 ±3\.9162\.60 ±1\.27MoG73\.66 ±0\.7765\.28 ±1\.5095\.45 ±0\.2977\.48 ±0\.6692\.55 ±0\.0594\.94 ±0\.2071\.56 ±0\.5443\.40±3\.1343\.25 ±1\.1274\.02 ±0\.32EDiS\-Lite \(Ours\)77\.16±0\.9866\.08±1\.2395\.60±0\.1580\.25±0\.7993\.35±0\.2195\.72±0\.0677\.28 ±0\.5743\.75±4\.1442\.63 ±2\.0473\.82 ±0\.97
MethodCoauthorPhys\.RomanAmazonRatingsQuestionsProteinsArxivRedditPokecProductsAMGMRef\.MLP \(No graph\)96\.36 ±0\.0166\.23 ±0\.0750\.32 ±0\.2469\.69 ±0\.3572\.91 ±0\.1755\.60 ±0\.1669\.66 ±0\.0962\.31 ±0\.0245\.46 ±0\.1965\.8263\.49Spanning Tree96\.94 ±0\.0287\.36 ±0\.2351\.73 ±0\.3774\.85 ±0\.2474\.13 ±0\.1667\.27 ±0\.1286\.07 ±0\.1469\.36 ±0\.0167\.79 ±0\.0973\.7771\.31Full GCN97\.51 ±0\.0790\.74 ±0\.0353\.52 ±0\.4278\.49 ±0\.1877\.48 ±0\.0672\.83 ±0\.2095\.44 ±0\.0586\.24 ±0\.0480\.67 ±0\.1080\.1778\.17EDiS\-Full \(Ours\)97\.45 ±0\.0375\.00 ±0\.5153\.16 ±0\.6877\.70 ±0\.5376\.56 ±0\.2273\.29 ±0\.3095\.16 ±0\.0184\.45 ±0\.1981\.38 ±0\.1378\.1376\.16Topology\-guidedRandom96\.66 ±0\.0567\.07 ±0\.2448\.40 ±0\.4371\.89 ±0\.9076\.83 ±0\.0867\.77 ±0\.1894\.69 ±0\.0276\.33 ±0\.0579\.08 ±0\.0673\.7171\.47Rank Deg\.96\.40 ±0\.1770\.53 ±0\.3351\.23 ±0\.5271\.49 ±0\.4866\.01 ±0\.7862\.59 ±0\.0777\.28 ±0\.0467\.29 ±0\.1063\.13 ±0\.0270\.9569\.05Local Deg\.96\.30 ±0\.1870\.79 ±0\.3151\.47 ±0\.7174\.39±0\.8371\.10 ±0\.0068\.34 ±0\.1790\.82 ±0\.1580\.07±0\.0977\.62 ±0\.1674\.0372\.11Forest Fire96\.91 ±0\.0367\.43 ±0\.6248\.37 ±0\.2271\.34 ±0\.4678\.25±0\.3268\.75 ±0\.2195\.41±0\.0079\.43 ±0\.1080\.65±0\.0574\.3672\.27G\-Spar96\.73 ±0\.0672\.20 ±0\.4249\.64 ±0\.6170\.35 ±1\.7770\.39 ±0\.5665\.86 ±0\.0690\.05 ±0\.0167\.35 ±0\.0172\.55 ±0\.0572\.4470\.31L\-Sim96\.83 ±0\.0671\.33 ±0\.2151\.66±0\.0975\.39±0\.6077\.95±0\.1170\.69±0\.0894\.35 ±0\.0576\.56 ±0\.0679\.20 ±0\.0975\.2673\.06SCAN96\.84 ±0\.0373\.37±0\.2350\.25 ±0\.6172\.72 ±0\.4570\.62 ±0\.4267\.36 ±0\.3790\.28 ±0\.0168\.56 ±0\.0272\.56 ±0\.1572\.7770\.50L\-Spar96\.74 ±0\.0572\.24 ±0\.6649\.84 ±0\.1970\.29 ±1\.8270\.80 ±0\.3965\.82 ±0\.0590\.06 ±0\.0167\.42 ±0\.0272\.64 ±0\.0272\.3170\.03Spectral96\.74 ±0\.0866\.72 ±0\.4246\.86 ±0\.4174\.00 ±0\.8877\.09 ±0\.6669\.88 ±0\.1595\.41±0\.0379\.65 ±0\.0780\.00 ±0\.1574\.7072\.69tt\-Spanner96\.75 ±0\.1067\.09 ±0\.4547\.96 ±1\.0172\.42 ±0\.6177\.43 ±0\.1267\.51 ±0\.0994\.72 ±0\.0176\.38 ±0\.0779\.30 ±0\.0173\.9171\.74DSpar96\.84 ±0\.0567\.07 ±0\.0947\.71 ±0\.6172\.77 ±0\.4751\.94 ±1\.1655\.19 ±0\.1395\.22 ±0\.0169\.39 ±0\.0377\.43 ±0\.0872\.0369\.64Semantic\[\-2pt\]guidedUnified\-LTH96\.49 ±0\.0065\.43 ±0\.5840\.49 ±0\.5272\.42 ±0\.6467\.15 ±0\.0056\.37 ±0\.0092\.68 ±0\.0068\.23 ±0\.0075\.26 ±0\.0070\.5568\.02AdaGLT96\.65 ±0\.0081\.43±0\.0048\.05 ±0\.3572\.34 ±0\.3352\.31 ±0\.0055\.93 ±0\.0085\.09 ±0\.0064\.42 ±0\.0066\.74 ±0\.0070\.3768\.05MoG96\.93±0\.1070\.44 ±0\.6051\.24 ±0\.3368\.90 ±1\.6872\.72 ±1\.7556\.42 ±0\.1690\.13 ±0\.0866\.94 ±0\.0768\.27 ±0\.0572\.2970\.39EDiS\-Lite \(Ours\)97\.06±0\.0968\.58 ±0\.1252\.31±0\.8574\.12 ±0\.8876\.43 ±0\.2271\.41±0\.2695\.61±0\.0381\.19±0\.0880\.78±0\.4275\.9574\.01

Table 1:Mean±\\pmstandard deviation \(%\) at retention ratio 0\.30\. The metric is accuracy, except ROC\-AUC on Minesweeper, Questions, and Proteins\. Best, second\-best, and third\-best results are shaded blue/bold, gray/underlined, and tan, respectively\. AM and GM denote the arithmetic and geometric means across all 19 datasets\. The first four reference rows are excluded from ranking\.Table 2:Summary of Table[1](https://arxiv.org/html/2610.09059#S4.T1)over all 19 datasetsatρ=0\.3\\rho=0\.3/0\.50\.5\. Score is the mean of per\-dataset accuracy or ROC\-AUC\. Rank and Gap are to the best ranked method per dataset, averaged; shading as in Table[1](https://arxiv.org/html/2610.09059#S4.T1)\.𝝆=0\.3\\boldsymbol\{\\rho=0\.3\}𝝆=0\.5\\boldsymbol\{\\rho=0\.5\}MethodScore↑\\uparrowRank↓\\downarrowGap↓\\downarrowScore↑\\uparrowRank↓\\downarrowGap↓\\downarrowTopology\-guidedRandom73\.718\.503\.4975\.957\.553\.04Local Degree74\.037\.053\.1776\.607\.182\.39Rank Degree70\.9510\.246\.2673\.369\.875\.63Forest Fire74\.367\.082\.8477\.104\.421\.89SCAN72\.778\.794\.4375\.718\.083\.28L\-Spar72\.3110\.244\.8974\.6010\.504\.39G\-Spar72\.4410\.554\.7674\.4910\.924\.50L\-Sim75\.264\.741\.9477\.624\.631\.37Spectral74\.706\.132\.5076\.396\.162\.60tt\-Spanner73\.917\.663\.3075\.897\.503\.10DSpar72\.037\.165\.1774\.407\.164\.60SemguidedUnified\-LTH70\.5511\.876\.6571\.1912\.767\.81AdaGLT70\.379\.896\.8371\.7611\.377\.23MoG72\.297\.584\.9174\.028\.584\.97EDiS\-Lite75\.952\.531\.2577\.763\.321\.23\(RQ2\) How large is the average margin?Table[2](https://arxiv.org/html/2610.09059#S4.T2)aggregates results over all 19 datasets\. The mean benchmark score averages per\-dataset scores, which are accuracy on 16 datasets and ROC\-AUC on Minesweeper, Questions, and ogbn\-proteins\. Among the ranked methods, EDiS\-Lite achieves the highest mean benchmark score at both budgets\. Since rank and gap are computed per dataset relative to the best ranked method and then averaged, EDiS\-Lite attains average ranks of2\.532\.53/3\.323\.32and average gaps of only1\.251\.25/1\.231\.23points atρ=0\.3\\rho=0\.3/0\.50\.5, respectively\. Per\-dataset ranks are easier to interpret across the two metrics\.

\(RQ3, EDiS\-Lite vs\. EDiS\-Full\) What does full\-graph inference recover over sparse\-graph inference, and what does it cost?

Both variants share the same trained model and differ only at inference\. At tight budgets, EDiS\-Lite can trail significantly behind the independently tuned Full GCN reference, most visibly on Minesweeper and Pokec\. Switching the evaluation graph to the full graph \(EDiS\-Full\) recovers much of it without retraining, and the gap shrinks asρ\\rhogrows \(Figure[3](https://arxiv.org/html/2610.09059#S4.F3)\)\. Reddit is a mild exception, where EDiS\-Lite already sits close to Full GCN\. That recovery is not free\. Evaluation time rises and peak GPU memory increases mildly, while training cost is unchanged\. These results make EDiS\-Lite the default, with EDiS\-Full reserved for cases where the accuracy gain is worth the extra inference cost\. Full curves and the runtime and memory breakdown are in Appendicesand\.

Figure 3:Full\-graph evaluation across regimes\.MaxCFwith cosine scores\.
### 4\.3Ablations and Generality

\(RQ4, EDiS\-Lite vs\. matched\-budget controls\) Do cacheable subgraphs and per\-epoch resampling drive the gains, or would any same\-budget sampling do as well?We compare EDiS\-Lite against three controls that fix the backbone, scores, and budget\.Frozenreuses one sampled graph for the entire run,Directsamples edges by score without forming subgraphs, andShuffled groupskeeps subgraph sizes constant but scrambles which edges belong to each subgraph, thus separating structure from size\.

Figure 4:Decomposition and resampling across edge budgets\.Figure[4](https://arxiv.org/html/2610.09059#S4.F4)shows EDiS\-Lite matching or leading all three controls across the measured budget range, with the largest margin at tight budgets where each epoch graph holds few edges\. Removing epoch variation \(Frozen\) hurts most under small budgets\. Dropping subgraph formation \(Direct\) leaves a gap that closes only near the full graph\. Shuffled groups, despite matching EDiS’s subgraph sizes exactly, is consistently the weakest control\. These results indicate that the gain comes from the structure of the decomposition and from resampling it every epoch, not merely from the number or size of edges available\. Full results are given in Appendix\.

\(RQ5, selectors and edge scores\) How sensitive isEDiS’s predictive performance to the residual selector and edge\-scoring function?Theorem[2](https://arxiv.org/html/2610.09059#Thmtheorem2)applies across selectors, but does not establish comparable predictive performance, so we evaluate this empirically by sweeping seven selectors \(MaxCF, MinCF, Degree,kk\-NN, Spanner, Random, Hybrid\) and five edge scores \(cosine, Euclidean, Dot, Uniform, MLP\-score\) through the same composition procedure, changing nothing else\.

![Refer to caption](https://arxiv.org/html/2610.09059v1/selector_heatmap.png)Figure 5:Selector and score sensitivity\.GCN atρ=0\.3\\rho=0\.3\. Cells show the gap to the best mean per row and panel \(pp, lower is better\)\. Outlines mark defaults\. N/A marks PubMed–MLP\-score, which is not applicable\.Figure[5](https://arxiv.org/html/2610.09059#S4.F5)reports the observed sensitivity\. Across all seven selectors and five scores, most cells sit within a couple of points of the best choice on a given dataset, and no single selector or score dominates\. The default MaxCF and cosine pairing stays competitive throughout\. This extends to other datasets and to the GraphSAGE backbone \(Appendix–,\)\.

\(RQ6\) How does extraction depth affect a fixed\-budget graph?The capKmaxK\_\{\\max\}sets how many subgraphs we extract, and the budgetBBsets how many edges each epoch uses\. A larger cap moves edges from the residual pool into subgraphs\. We varyKmaxK\_\{\\max\}on five large graphs atρ=0\.3\\rho=0\.3\(Figure[6](https://arxiv.org/html/2610.09059#S4.F6)\)\. More subgraphs help on some datasets and hurt on others, and Lite and Full do not always agree\. Thus, additional subgraphs do not always give a better graph, and once extraction stops before the cap, a largerKmaxK\_\{\\max\}changes nothing \(Appendix\)\.

![Refer to caption](https://arxiv.org/html/2610.09059v1/kmax_sensitivity.png)Figure 6:Extraction depth atρ=0\.3\\rho=0\.3\.Reported means with standard\-deviation bars\. Proteins uses ROC\-AUC, others accuracy\. Each panel has its own scale\.\(RQ7\) Does the method work only with GCN?We fix MaxCF and cosine\-similarity but switch the backbone from GCN to GraphSAGE \(Figure[7](https://arxiv.org/html/2610.09059#S4.F7)\)\. Both backbones improve with the budget and stay close, and neither is better overall\.EDiStherefore works with either backbone \(Appendix\)\.

Figure 7:Backbone comparison within EDiS\-Lite\.Further analysis\.The appendix reports more experiments\. It covers runtime and memory by budget \(Appendix\), a cost analysis of construction and composition \(Appendix[F\.2](https://arxiv.org/html/2610.09059#A6.SS2)\), the full ablation study \(Appendix\), complete per\-dataset results \(Appendix[G](https://arxiv.org/html/2610.09059#A7)\), and its limitations \(Appendix\)\.

## 5Conclusion

We introducedEDiS, a framework that separates one\-time structural extraction from per\-epoch graph composition\. We extract structure once, then compose many sparse graphs from it for training, avoiding both a fixed topology and repeated extraction\. The same cached library supplies exact\-budget graphs at every epoch and retention level without changing the GNN architecture or objective\. Our default MaxCF construction is just one instance of this framework, which stays modular across scores and selectors\.

Across 19 node\-classification benchmarks under the same edge\-budget, EDiS\-Lite achieves the highest mean benchmark score among the ranked methods at both retention levels\. EDiS\-Full, reported as a reference using full\-graph for inference, shows how much accuracy can be recovered when sparsification is restricted to training, and at a modest extra cost for inference\. Structural decomposition and epoch\-to\-epoch variation matter most at tighter edge\-budgets\. More broadly, a cacheable structural representation that generates many sparse views can be more effective than searching for a single sparse graph to replace the original\. Our future work will consider task\-aware scores for decomposition, dynamic \(temporal\) composition, and extensions to graph\- and link\-level prediction\.

## AI Use Disclosure

Generative AI tools were used to assist with polishing the manuscript and supporting research execution, including software implementation and experimental workflows\. All AI\-assisted content and code were reviewed, revised, and validated by the authors\. The authors independently verified the reported results and claims and take full responsibility for the final content of this work\.

## Ethics Statement

This work does not involve human subjects, personal data, or new data collection\. All experiments use publicly available benchmark graphs under their original licenses\. We are not aware of ethical risks specific to this methodology beyond those inherent to downstream applications of graph learning\.

## References

- A\. A\. Benczúr and D\. R\. KargerApproximating s\-t Minimum Cuts inO~​\(n2\)\\tilde\{O\}\(n^\{2\}\)Time\.InProceedings of the 28th Annual ACM Symposium on Theory of Computing,pp\. 47–55\.External Links:[Document](https://dx.doi.org/10.1145/237814.237827)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Bonchiet al\.\(2025\)F\. Bonchi, C\. Gentile, F\. P\. Nerini, A\. Panisson, and F\. VitaleFast and Effective GNN Training through Sequences of Random Path Graphs\.InProceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\.1,pp\. 49–60\.External Links:[Document](https://dx.doi.org/10.1145/3690624.3709301)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px3.p3.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.29.1.1.1),[§1](https://arxiv.org/html/2610.09059#S1.p2.1),[§2](https://arxiv.org/html/2610.09059#S2.p5.1)\.
- Chenet al\.\(2018\)J\. Chen, T\. Ma, and C\. XiaoFastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling\.In6th International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=rytstxWAW)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px1.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.12.1.1.1),[§2](https://arxiv.org/html/2610.09059#S2.p2.1)\.
- Chenet al\.\(2021\)T\. Chen, Y\. Sui, X\. Chen, A\. Zhang, and Z\. WangA Unified Lottery Ticket Hypothesis for Graph Neural Networks\.InProceedings of the 38th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.139,pp\. 1695–1706\.External Links:[Link](https://proceedings.mlr.press/v139/chen21p.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p2.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.17.1.1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1),[§1](https://arxiv.org/html/2610.09059#S1.p1.1),[§1](https://arxiv.org/html/2610.09059#S1.p2.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Chenet al\.\(2023\)Y\. Chen, H\. Ye, S\. Vedula, A\. Bronstein, R\. Dreslinski, T\. Mudge, and N\. TalatiDemystifying Graph Sparsification Algorithms in Graph Properties Preservation\.Proceedings of the VLDB Endowment17\(3\),pp\. 427–440\.External Links:[Document](https://dx.doi.org/10.14778/3632093.3632106)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p3.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.8.1.1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Chenet al\.\(2025\)Z\. Chen, Z\. Wu, Y\. Sadikaj, C\. Plant, H\. Dai, S\. Wang, Y\. Cheung, and W\. GuoADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks\.IEEE Transactions on Knowledge and Data Engineering37\(9\),pp\. 4948–4961\.External Links:[Document](https://dx.doi.org/10.1109/TKDE.2025.3586369)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p4.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.25.1.1.1),[§2](https://arxiv.org/html/2610.09059#S2.p4.1)\.
- Chianget al\.\(2019\)W\. Chiang, X\. Liu, S\. Si, Y\. Li, S\. Bengio, and C\. HsiehCluster\-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks\.InProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp\. 257–266\.External Links:[Document](https://dx.doi.org/10.1145/3292500.3330925)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px1.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.14.1.1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p2.1),[§2](https://arxiv.org/html/2610.09059#S2.p2.1)\.
- Daset al\.\(2026\)S\. S\. Das, N\. A\. Arafat, M\. Rahman, S\. M\. Ferdous, A\. Pothen, M\. M\. Halappanavar, and D\. B\. RawatSGS\-GNN: A Supervised Graph Sparsifier for Graph Neural Networks\.InProceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\.2,pp\. 755–766\.External Links:[Document](https://dx.doi.org/10.1145/3770855.3818110)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p2.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.27.1.1.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Daset al\.\(2024\)S\. S\. Das, S\. M\. Ferdous, M\. M\. Halappanavar, E\. Serra, and A\. PothenAGS\-GNN: Attribute\-guided Sampling for Graph Neural Networks\.InProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,pp\. 538–549\.External Links:[Document](https://dx.doi.org/10.1145/3637528.3671940)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px1.p1.1),[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px3.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.20.1.1.1),[§2](https://arxiv.org/html/2610.09059#S2.p2.1)\.
- Dinget al\.\(2021\)M\. Ding, K\. Kong, J\. Li, C\. Zhu, J\. Dickerson, F\. Huang, and T\. GoldsteinVQ\-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization\.InAdvances in Neural Information Processing Systems,Vol\.34,pp\. 6733–6746\.External Links:[Link](https://proceedings.neurips.cc/paper/2021/hash/3569df159ec477451530c4455b2a9e86-Abstract.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p2.1)\.
- Edmonds \(1968\)J\. EdmondsMatroid Partition\.InMathematics of the Decision Sciences: Part I,G\. B\. Dantzig and A\. F\. Veinott \(Eds\.\),Lectures in Applied Mathematics, Vol\.11,pp\. 335–345\.Cited by:[§C\.3](https://arxiv.org/html/2610.09059#A3.SS3.p1.1)\.
- Edmonds \(1971\)J\. EdmondsMatroids and the Greedy Algorithm\.Mathematical Programming1\(1\),pp\. 127–136\.External Links:[Document](https://dx.doi.org/10.1007/BF01584082)Cited by:[§C\.3](https://arxiv.org/html/2610.09059#A3.SS3.p1.1),[§F\.1](https://arxiv.org/html/2610.09059#A6.SS1.SSS0.Px1.p1.1),[Fact 1](https://arxiv.org/html/2610.09059#Thmfact1)\.
- Feyet al\.\(2021\)M\. Fey, J\. E\. Lenssen, F\. Weichert, and J\. LeskovecGNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings\.InProceedings of the 38th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.139,pp\. 3294–3304\.External Links:[Link](https://proceedings.mlr.press/v139/fey21a.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p2.1)\.
- Forster and de Vos \(2023\)S\. Forster and T\. de VosFaster Cut Sparsification of Weighted Graphs\.Algorithmica85\(4\),pp\. 929–964\.External Links:[Document](https://dx.doi.org/10.1007/s00453-022-01053-4)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.18.1.1.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Franket al\.\(1993\)A\. Frank, T\. Ibaraki, and H\. NagamochiOn Sparse Subgraphs Preserving Connectivity Properties\.Journal of Graph Theory17\(3\),pp\. 275–281\.External Links:[Document](https://dx.doi.org/10.1002/jgt.3190170302)Cited by:[Fact 2](https://arxiv.org/html/2610.09059#Thmfact2)\.
- Guet al\.\(2024\)X\. Gu, H\. Li, S\. Gao, X\. Zhang, L\. Chen, and Y\. ShaoSpanGNN: Towards Memory\-Efficient Graph Neural Networks via Spanning Subgraph Training\.InMachine Learning and Knowledge Discovery in Databases\. Research Track,Lecture Notes in Computer Science, Vol\.14943,pp\. 250–266\.External Links:[Document](https://dx.doi.org/10.1007/978-3-031-70352-2%5F15)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px3.p3.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.23.1.1.1),[§1](https://arxiv.org/html/2610.09059#S1.p2.1),[§2](https://arxiv.org/html/2610.09059#S2.p5.1)\.
- Hamannet al\.\(2016\)M\. Hamann, G\. Lindner, H\. Meyerhenke, C\. L\. Staudt, and D\. WagnerStructure\-Preserving Sparsification Methods for Social Networks\.Social Network Analysis and Mining6\(1\)\.External Links:[Document](https://dx.doi.org/10.1007/s13278-016-0332-2)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.9.1.1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Hamiltonet al\.\(2017\)W\. L\. Hamilton, R\. Ying, and J\. LeskovecInductive Representation Learning on Large Graphs\.InAdvances in Neural Information Processing Systems,Vol\.30\.External Links:[Link](https://proceedings.neurips.cc/paper/2017/hash/5dd9db5e033da9c6fb5ba83c7a7ebea9-Abstract.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px1.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.11.1.1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p2.1),[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.24.1),[§2](https://arxiv.org/html/2610.09059#S2.p2.1)\.
- Hossainet al\.\(2024\)T\. Hossain, K\. M\. Saifuddin, M\. I\. K\. Islam, F\. Tanvir, and E\. AkbasTackling Oversmoothing in GNN via Graph Sparsification\.InMachine Learning and Knowledge Discovery in Databases\. Research Track and Demo Track,Lecture Notes in Computer Science, Vol\.14948,pp\. 161–179\.External Links:[Document](https://dx.doi.org/10.1007/978-3-031-70371-3%5F10)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p3.1)\.
- Huet al\.\(2020\)W\. Hu, M\. Fey, M\. Zitnik, Y\. Dong, H\. Ren, B\. Liu, M\. Catasta, and J\. LeskovecOpen Graph Benchmark: Datasets for Machine Learning on Graphs\.InAdvances in Neural Information Processing Systems,Vol\.33,pp\. 22118–22133\.External Links:[Link](https://proceedings.neurips.cc/paper/2020/hash/fb60d411a5c5b72b2e7d3527cfc84fd0-Abstract.html)Cited by:[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.20.1),[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.21.1.1),[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.22.1)\.
- Huanget al\.\(2018\)W\. Huang, T\. Zhang, Y\. Rong, and J\. HuangAdaptive Sampling Towards Fast Graph Representation Learning\.InAdvances in Neural Information Processing Systems,Vol\.31\.External Links:[Link](https://proceedings.neurips.cc/paper/2018/hash/01eee509ee2f68dc6014898c309e86bf-Abstract.html)Cited by:[§1](https://arxiv.org/html/2610.09059#S1.p1.1)\.
- Jamadandiet al\.\(2024\)A\. Jamadandi, C\. Rubio\-Madrigal, and R\. BurkholzSpectral Graph Pruning Against Over\-Squashing and Over\-Smoothing\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 10348–10379\.External Links:[Document](https://dx.doi.org/10.52202/079017-0331),[Link](https://proceedings.neurips.cc/paper_files/paper/2024/hash/140aac600566125915df7e74ff538f66-Abstract-Conference.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p3.1)\.
- Kipf and Welling \(2017\)T\. N\. Kipf and M\. WellingSemi\-Supervised Classification with Graph Convolutional Networks\.In5th International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=SJU4ayYgl)Cited by:[§1](https://arxiv.org/html/2610.09059#S1.p1.1),[Definition 2](https://arxiv.org/html/2610.09059#Thmdefinition2.p1.1)\.
- Kruskal \(1956\)J\. B\. KruskalOn the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem\.Proceedings of the American Mathematical Society7\(1\),pp\. 48–50\.External Links:[Document](https://dx.doi.org/10.1090/S0002-9939-1956-0078686-7)Cited by:[§C\.3](https://arxiv.org/html/2610.09059#A3.SS3.p1.1),[§F\.1](https://arxiv.org/html/2610.09059#A6.SS1.SSS0.Px1.p1.1),[Fact 1](https://arxiv.org/html/2610.09059#Thmfact1)\.
- Leeet al\.\(2025\)D\. Lee, M\. Kong, S\. Hamid, C\. Lee, and J\. YooAggregation Buffer: Revisiting DropEdge with a New Parameter Block\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 33181–33204\.External Links:[Link](https://proceedings.mlr.press/v267/lee25n.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p4.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.26.1.1.1),[§2](https://arxiv.org/html/2610.09059#S2.p4.1)\.
- Leskovec and Faloutsos \(2006\)J\. Leskovec and C\. FaloutsosSampling from Large Graphs\.InProceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp\. 631–636\.External Links:[Document](https://dx.doi.org/10.1145/1150402.1150479)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.3.1.1.1),[§F\.1](https://arxiv.org/html/2610.09059#A6.SS1.SSS0.Px7.p1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1)\.
- Lianget al\.\(2025\)L\. Liang, F\. Bu, Z\. Song, Z\. Xu, S\. Pan, and K\. ShinMitigating Over\-Squashing in Graph Neural Networks by Spectrum\-Preserving Sparsification\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 37051–37070\.External Links:[Link](https://proceedings.mlr.press/v267/liang25a.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p3.1)\.
- Limet al\.\(2021\)D\. Lim, F\. Hohne, X\. Li, S\. L\. Huang, V\. Gupta, O\. Bhalerao, and S\. LimLarge Scale Learning on Non\-Homophilous Graphs: New Benchmarks and Strong Simple Methods\.InAdvances in Neural Information Processing Systems,Vol\.34,pp\. 20887–20902\.External Links:[Link](https://proceedings.neurips.cc/paper/2021/hash/ae816a80e4c1c56caa2eb4e1819cbb2f-Abstract.html)Cited by:[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.23.1.1)\.
- Liuet al\.\(2023\)Z\. Liu, K\. Zhou, Z\. Jiang, L\. Li, R\. Chen, S\. Choi, and X\. HuDSpar: An Embarrassingly Simple Strategy for Efficient GNN Training and Inference via Degree\-Based Sparsification\.Transactions on Machine Learning Research\.External Links:[Link](https://openreview.net/forum?id=SaVEXFuozg)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.19.1.1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Liuet al\.\(2022\)Z\. Liu, K\. Zhou, F\. Yang, L\. Li, R\. Chen, and X\. HuEXACT: Scalable Graph Neural Networks Training via Extreme Activation Compression\.In10th International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=vkaMaq95_rX)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p2.1)\.
- Luoet al\.\(2024\)Y\. Luo, L\. Shi, and X\. WuClassic GNNs are Strong Baselines: Reassessing GNNs for Node Classification\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 97650–97669\.Note:Datasets and Benchmarks TrackExternal Links:[Document](https://dx.doi.org/10.52202/079017-3098),[Link](https://proceedings.neurips.cc/paper_files/paper/2024/hash/b10ed15ff1aa864f1be3a75f1ffc021b-Abstract-Datasets_and_Benchmarks_Track.html)Cited by:[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1),[§G\.4](https://arxiv.org/html/2610.09059#A7.SS4.p1.1),[§4\.1](https://arxiv.org/html/2610.09059#S4.SS1.p1.1)\.
- Luoet al\.\(2025\)Y\. Luo, X\. Wu, and H\. ZhuBeyond Random Masking: When Dropout meets Graph Convolutional Networks\.In13th International Conference on Learning Representations,pp\. 11149–11168\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2025/hash/1ddcd22e3a0f830db8ecd3fd242c2c56-Abstract-Conference.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p4.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.24.1.1.1),[§2](https://arxiv.org/html/2610.09059#S2.p4.1)\.
- Mernyei and Cangea \(2020\)P\. Mernyei and C\. CangeaWiki\-CS: A Wikipedia\-Based Benchmark for Graph Neural Networks\.Note:arXiv:2007\.02901Presented at the ICML 2020 Workshop on Graph Representation Learning and Beyond \(GRL\+\)External Links:[Document](https://dx.doi.org/10.48550/arXiv.2007.02901),[Link](https://arxiv.org/abs/2007.02901),2007\.02901Cited by:[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.18.1.1)\.
- Nagamochi and Ibaraki \(1992\)H\. Nagamochi and T\. IbarakiA Linear\-Time Algorithm for Finding a Sparse k\-Connected Spanning Subgraph of a k\-Connected Graph\.Algorithmica7\(1\-6\),pp\. 583–596\.External Links:[Document](https://dx.doi.org/10.1007/BF01758778)Cited by:[Fact 2](https://arxiv.org/html/2610.09059#Thmfact2)\.
- Nemhauseret al\.\(1978\)G\. L\. Nemhauser, L\. A\. Wolsey, and M\. L\. FisherAn Analysis of Approximations for Maximizing Submodular Set Functions—I\.Mathematical Programming14\(1\),pp\. 265–294\.External Links:[Document](https://dx.doi.org/10.1007/BF01588971)Cited by:[Proposition 9](https://arxiv.org/html/2610.09059#Thmtheorem9)\.
- Peleg and Schäffer \(1989\)D\. Peleg and A\. A\. SchäfferGraph Spanners\.Journal of Graph Theory13\(1\),pp\. 99–116\.External Links:[Document](https://dx.doi.org/10.1002/jgt.3190130114)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.2.1.1.1),[§F\.1](https://arxiv.org/html/2610.09059#A6.SS1.SSS0.Px3.p1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Platonovet al\.\(2023\)O\. Platonov, D\. Kuznedelev, M\. Diskin, A\. Babenko, and L\. ProkhorenkovaA Critical Look at the Evaluation of GNNs under Heterophily: Are We Really Making Progress?\.In11th International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=tJbbQfw-5wv)Cited by:[§G\.1](https://arxiv.org/html/2610.09059#A7.SS1.p1.1),[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.3.1)\.
- Ronget al\.\(2020\)Y\. Rong, W\. Huang, T\. Xu, and J\. HuangDropEdge: Towards Deep Graph Convolutional Networks on Node Classification\.In8th International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=Hkx1qkrKPr)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p4.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.15.1.1.1),[§2](https://arxiv.org/html/2610.09059#S2.p4.1)\.
- Satuluriet al\.\(2011\)V\. Satuluri, S\. Parthasarathy, and Y\. RuanLocal Graph Sparsification for Scalable Clustering\.InProceedings of the 2011 ACM SIGMOD International Conference on Management of Data,pp\. 721–732\.External Links:[Document](https://dx.doi.org/10.1145/1989323.1989399)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.6.1.1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.7.1.1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Seoet al\.\(2024\)H\. Seo, J\. Yun, and E\. YangTEDDY: Trimming Edges with Degree\-based Discrimination Strategy\.In12th International Conference on Learning Representations,pp\. 33937–33959\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2024/hash/90d1fc07f46e31387978b88e7e057a31-Abstract-Conference.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p2.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.21.1.1.1),[§1](https://arxiv.org/html/2610.09059#S1.p2.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Shchuret al\.\(2018\)O\. Shchur, M\. Mumme, A\. Bojchevski, and S\. GünnemannPitfalls of Graph Neural Network Evaluation\.Note:arXiv:1811\.05868Presented at the NeurIPS 2018 Workshop on Relational Representation Learning \(R2L\)External Links:[Document](https://dx.doi.org/10.48550/arXiv.1811.05868),[Link](https://arxiv.org/abs/1811.05868),1811\.05868Cited by:[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.14.1.1),[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.15.1),[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.16.1.1),[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.17.1)\.
- Shiet al\.\(2023\)Z\. Shi, X\. Liang, and J\. WangLMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence\.In11th International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=5VBBA91N6n)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p2.1)\.
- Spielman and Srivastava \(2008\)D\. A\. Spielman and N\. SrivastavaGraph Sparsification by Effective Resistances\.InProceedings of the 40th Annual ACM Symposium on Theory of Computing,pp\. 563–568\.External Links:[Document](https://dx.doi.org/10.1145/1374376.1374456)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.5.1.1.1),[§F\.1](https://arxiv.org/html/2610.09059#A6.SS1.SSS0.Px7.p1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Voudigariet al\.\(2016\)E\. Voudigari, N\. Salamanos, T\. Papageorgiou, and E\. J\. YannakoudakisRank Degree: An Efficient Algorithm for Graph Sampling\.In2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining \(ASONAM\),pp\. 120–129\.External Links:[Document](https://dx.doi.org/10.1109/ASONAM.2016.7752223)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.10.1.1.1),[§F\.1](https://arxiv.org/html/2610.09059#A6.SS1.SSS0.Px7.p1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1)\.
- Wanet al\.\(2022\)C\. Wan, Y\. Li, A\. Li, N\. S\. Kim, and Y\. LinBNS\-GCN: Efficient Full\-Graph Training of Graph Convolutional Networks with Partition\-Parallelism and Random Boundary Node Sampling\.InProceedings of Machine Learning and Systems,Vol\.4,pp\. 673–693\.External Links:[Link](https://proceedings.mlsys.org/paper_files/paper/2022/hash/676638b91bc90529e09b22e58abb01d6-Abstract.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p2.1)\.
- Xuet al\.\(2007\)X\. Xu, N\. Yuruk, Z\. Feng, and T\. A\. J\. SchweigerSCAN: A Structural Clustering Algorithm for Networks\.InProceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp\. 824–833\.External Links:[Document](https://dx.doi.org/10.1145/1281192.1281280)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.4.1.1.1),[§F\.1](https://arxiv.org/html/2610.09059#A6.SS1.SSS0.Px7.p1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1)\.
- Yanget al\.\(2016\)Z\. Yang, W\. W\. Cohen, and R\. SalakhutdinovRevisiting Semi\-Supervised Learning with Graph Embeddings\.InProceedings of the 33rd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.48,pp\. 40–48\.External Links:[Link](https://proceedings.mlr.press/v48/yanga16.html)Cited by:[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.11.1),[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.12.1.1),[Table 6](https://arxiv.org/html/2610.09059#A7.T6.2.1.1.1.1.1.1.13.1)\.
- Zenget al\.\(2020\)H\. Zeng, H\. Zhou, A\. Srivastava, R\. Kannan, and V\. PrasannaGraphSAINT: Graph Sampling Based Inductive Learning Method\.In8th International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=BJe8pkHFwS)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px1.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.16.1.1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p2.1),[§1](https://arxiv.org/html/2610.09059#S1.p1.1),[§1](https://arxiv.org/html/2610.09059#S1.p2.1),[§2](https://arxiv.org/html/2610.09059#S2.p2.1)\.
- Zhanget al\.\(2025\)G\. Zhang, X\. Sun, Y\. Yue, C\. Jiang, K\. Wang, T\. Chen, and S\. PanGraph Sparsification via Mixture of Graphs\.In13th International Conference on Learning Representations,pp\. 92735–92763\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2025/hash/e7947b5e1d30864ebbe8714dbdd611d9-Abstract-Conference.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p2.1),[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px3.p3.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.28.1.1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Zhanget al\.\(2024\)G\. Zhang, K\. Wang, W\. Huang, Y\. Yue, Y\. Wang, R\. Zimmermann, A\. Zhou, D\. Cheng, J\. Zeng, and Y\. LiangGraph Lottery Ticket Automated\.In12th International Conference on Learning Representations,pp\. 31044–31068\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2024/hash/83c230118e9f6688ba8f20bfef99e6da-Abstract-Conference.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px2.p2.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.22.1.1.1),[§G\.2](https://arxiv.org/html/2610.09059#A7.SS2.p1.1),[§2](https://arxiv.org/html/2610.09059#S2.p3.1)\.
- Zouet al\.\(2019\)D\. Zou, Z\. Hu, Y\. Wang, S\. Jiang, Y\. Sun, and Q\. GuLayer\-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks\.InAdvances in Neural Information Processing Systems,Vol\.32\.External Links:[Link](https://proceedings.neurips.cc/paper/2019/hash/91ba4a4478a66bee9812b0804b6f9d1b-Abstract.html)Cited by:[Appendix B](https://arxiv.org/html/2610.09059#A2.SS0.SSS0.Px1.p1.1),[Table 4](https://arxiv.org/html/2610.09059#A2.T4.2.13.1.1.1),[§2](https://arxiv.org/html/2610.09059#S2.p2.1)\.

###### Appendix Contents

1. [1Introduction](https://arxiv.org/html/2610.09059#S1)
2. [2Related Work](https://arxiv.org/html/2610.09059#S2)
3. [3EDiS: A Structured Sparsification Framework](https://arxiv.org/html/2610.09059#S3)1. [3\.1One GNN, Many Sparse Views](https://arxiv.org/html/2610.09059#S3.SS1) 2. [3\.2One\-Time Structural Decomposition](https://arxiv.org/html/2610.09059#S3.SS2) 3. [3\.3An Exact\-Budget Graph at Every Epoch](https://arxiv.org/html/2610.09059#S3.SS3) 4. [3\.4Structural Preservation for Decomposition and Composition](https://arxiv.org/html/2610.09059#S3.SS4)
4. [4Experimental Results](https://arxiv.org/html/2610.09059#S4)1. [4\.1Experimental Setup](https://arxiv.org/html/2610.09059#S4.SS1) 2. [4\.2Predictive Performance](https://arxiv.org/html/2610.09059#S4.SS2) 3. [4\.3Ablations and Generality](https://arxiv.org/html/2610.09059#S4.SS3)
5. [5Conclusion](https://arxiv.org/html/2610.09059#S5)
6. [References](https://arxiv.org/html/2610.09059#bib)
7. [ANotation](https://arxiv.org/html/2610.09059#A1)
8. [BExtended Related Work](https://arxiv.org/html/2610.09059#A2)
9. [CFormal Definitions and Construction](https://arxiv.org/html/2610.09059#A3)1. [C\.1Graph, GNN, and Edge Budget](https://arxiv.org/html/2610.09059#A3.SS1) 2. [C\.2Edge Scores and Residual Selectors](https://arxiv.org/html/2610.09059#A3.SS2) 3. [C\.3Maximum\-Score Residual Forests](https://arxiv.org/html/2610.09059#A3.SS3) 4. [C\.4Classical Forest Properties](https://arxiv.org/html/2610.09059#A3.SS4) 5. [C\.5Exact Stochastic Budgeted Composition](https://arxiv.org/html/2610.09059#A3.SS5) 6. [C\.6Structural Preservation of the Stored Decomposition](https://arxiv.org/html/2610.09059#A3.SS6) 7. [C\.7Retention After Budgeted Composition](https://arxiv.org/html/2610.09059#A3.SS7)
10. [DWorked Examples of Structural Selectors](https://arxiv.org/html/2610.09059#A4)
11. [ETheoretical Understanding and Proofs](https://arxiv.org/html/2610.09059#A5)1. [E\.1Reuse and Exact\-Budget Feasibility](https://arxiv.org/html/2610.09059#A5.SS1) 2. [E\.2Score\-Threshold Certificate](https://arxiv.org/html/2610.09059#A5.SS2) 3. [E\.3Top\-kkCut\-Score Corollary](https://arxiv.org/html/2610.09059#A5.SS3) 4. [E\.4Equivalent Interpretations](https://arxiv.org/html/2610.09059#A5.SS4) 5. [E\.5Composition Retention](https://arxiv.org/html/2610.09059#A5.SS5) 6. [E\.6Optional Composition Variants](https://arxiv.org/html/2610.09059#A5.SS6)
12. [FSelectors and Computational Cost](https://arxiv.org/html/2610.09059#A6)1. [F\.1Family of Residual Selectors](https://arxiv.org/html/2610.09059#A6.SS1) 2. [F\.2Cost of Construction and Epoch Composition](https://arxiv.org/html/2610.09059#A6.SS2)
13. [GExperimental Details](https://arxiv.org/html/2610.09059#A7)1. [G\.1Dataset](https://arxiv.org/html/2610.09059#A7.SS1) 2. [G\.2Baseline Settings](https://arxiv.org/html/2610.09059#A7.SS2) 3. [G\.3Propagation and Evaluation Settings](https://arxiv.org/html/2610.09059#A7.SS3) 4. [G\.4Hyperparameter Settings](https://arxiv.org/html/2610.09059#A7.SS4) 5. [G\.5Complete numerical results](https://arxiv.org/html/2610.09059#A7.SS5)

## Appendix ANotation

This appendix collects the notation used throughoutEDiS, including the symbols introduced for the proofs in Appendix[E](https://arxiv.org/html/2610.09059#A5)\. Table[3](https://arxiv.org/html/2610.09059#A1.T3)lists the main symbols, grouped by where each is introduced\. Symbols that appear only in a single appendix result are instead defined locally, at the point where they are used\. The letterHHis intentionally reused as a generic placeholder for the current graph\.

SymbolMeaningGraph and edge\-budget𝒢=\(𝒱,ℰ,𝐗\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\},\\mathbf\{X\}\)Attributed undirected graph \(𝒱,𝐗\\mathcal\{V\},\\mathbf\{X\}fixed; only the edge set varies below\)n=\|𝒱\|n=\|\\mathcal\{V\}\|,m=\|ℰ\|m=\|\\mathcal\{E\}\|Number of nodes and edgesρ\\rhoEdge\-retention ratioB=⌈ρ​m⌉B=\\lceil\\rho m\\rceilNumber of active edges per epochOne\-time edge decompositionses\_\{e\}Score assigned to edgeeeℱ\\mathcal\{F\},ℱk\\mathcal\{F\}\_\{k\}Residual selector \(ℱk\\mathcal\{F\}\_\{k\}: round\-dependent schedule\)ℰrem\(k\)\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(k\)\}Edges remaining after decomposition roundkkℰk\\mathcal\{E\}\_\{k\}Subgraph extracted at roundkkKKNumber of extracted subgraphsKmaxK\_\{\\max\}Cap on extraction rounds \(K≤KmaxK\\leq K\_\{\\max\}\)ℰres\\mathcal\{E\}\_\{\\mathrm\{res\}\}Residual edges after the final roundUk=ℰ1∪⋯∪ℰkU\_\{k\}=\\mathcal\{E\}\_\{1\}\\cup\\cdots\\cup\\mathcal\{E\}\_\{k\}Union of the firstkksubgraphs \(UKU\_\{K\}: full stored union\)Per\-epoch graph constructionTTTotal number of training epochsDecompose\\operatorname\{Decompose\}One\-time decomposition of𝒢\\mathcal\{G\}under scoressand selectorℱ\\mathcal\{F\}into the stored𝒟\\mathcal\{D\}Compose\\operatorname\{Compose\}Budgeted composition, mapping the stored decomposition andBBtoℰB\(t\)\\mathcal\{E\}\_\{B\}^\{\(t\)\}𝒟\\mathcal\{D\}Edge partition with cached subgraph weights, reused across edge\-budgetswkw\_\{k\}Positive subgraph weightmax⁡\{∑e∈ℰkse,ε\}\\max\\\{\\sum\_\{e\\in\\mathcal\{E\}\_\{k\}\}s\_\{e\},\\varepsilon\\\}RrR\_\{r\},krk\_\{r\}Remaining subgraph indices and the subgraph selected at drawrrξt\\xi\_\{t\}Epoch randomness, includingπ\(t\)\\pi^\{\(t\)\}and within\-pool drawsA\(t\)A^\{\(t\)\}Subgraph indices selected at epochttℰ~k\(t\)\\widetilde\{\\mathcal\{E\}\}\_\{k\}^\{\(t\)\}Selected subgraph edges remaining after trimmingQB\(t\)Q\_\{B\}^\{\(t\)\}Residual edges used to complete the per\-epoch edge\-budgetπ\(t\)\\pi^\{\(t\)\}Weighted subgraph order for epochttℰB\(t\)\\mathcal\{E\}\_\{B\}^\{\(t\)\}Active edge set at epochtt𝒢B\(t\)\\mathcal\{G\}\_\{B\}^\{\(t\)\}Graph for message passing at epochtt\(𝒱,𝐗\\mathcal\{V\},\\mathbf\{X\}unchanged\)𝐀^B\(t\)\\widehat\{\\mathbf\{A\}\}\_\{B\}^\{\(t\)\}Normalized adjacency of𝒢B\(t\)\\mathcal\{G\}\_\{B\}^\{\(t\)\}used for message passingScore\-aware guaranteeτ\\tauEdge\-score thresholdℰ≥τ=\{e∈ℰ:se≥τ\}\\mathcal\{E\}\_\{\\geq\\tau\}=\\\{e\\in\\mathcal\{E\}:s\_\{e\}\\geq\\tau\\\}Edges with score at leastτ\\tau𝒢≥τ=\(𝒱,ℰ≥τ\)\\mathcal\{G\}\_\{\\geq\\tau\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{\\geq\\tau\}\),Uk,≥τ=Uk∩ℰ≥τU\_\{k,\\geq\\tau\}=U\_\{k\}\\cap\\mathcal\{E\}\_\{\\geq\\tau\}Threshold graph and the stored union restricted to itaj​\(S\)a\_\{j\}\(S\),bj​\(S\)b\_\{j\}\(S\)jj\-th largest crossing score at cutSSin𝒢\\mathcal\{G\}and inUkU\_\{k\}Tk​\(S,A\)=∑j=1min⁡\{k,\|δA​\(S\)\|\}s\(j\)​\(δA​\(S\)\)T\_\{k\}\(S;A\)=\\textstyle\\sum\\nolimits\_\{j=1\}^\{\\min\\\{k,\|\\delta\_\{A\}\(S\)\|\\\}\}s\_\{\(j\)\}\(\\delta\_\{A\}\(S\)\)Sum of themin⁡\{k,⋅\}\\min\\\{k,\\cdot\\\}largest scores crossingSSinAAδH​\(S\)\\delta\_\{H\}\(S\)Edges ofHHcrossing the cut\(S,𝒱∖S\)\(S,\\mathcal\{V\}\\setminus S\)dH​\(v\)d\_\{H\}\(v\)Degree ofvvinHHProof\-specific notation \(Appendix[E](https://arxiv.org/html/2610.09059#A5)\)ssAdditive score function, extendingses\_\{e\}to edge setsω⁡\(F\)=∑e∈Fωe\\omega\(F\)=\\sum\_\{e\\in F\}\\omega\_\{e\}Generic additive edge\-weight functionDkD\_\{k\}Stored subgraphkk, withD0=ℰresD\_\{0\}=\\mathcal\{E\}\_\{\\mathrm\{res\}\}andDk=ℰkD\_\{k\}=\\mathcal\{E\}\_\{k\}fork≥1k\\geq 1nk=\|Dk\|n\_\{k\}=\|D\_\{k\}\|Size of subgraphkkrkr\_\{k\}Number of edges retained from subgraphkkθk=rk/nk\\theta\_\{k\}=r\_\{k\}/n\_\{k\}Retained fraction / inclusion probability given the order \(0 if the pool is empty\)xk​\(S,τ\)=\|Dk∩δ𝒢​\(S\)∩ℰ≥τ\|x\_\{k\}\(S,\\tau\)=\|D\_\{k\}\\cap\\delta\_\{\\mathcal\{G\}\}\(S\)\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\|Edges of subgraphkkcrossingSSwith score at leastτ\\tauTable 3:Main notation used inEDiS\.
## Appendix BExtended Related Work

#### Sampling\-based GNN training\.

Many GNN methods reduce training cost by processing only part of the graph at a time rather than constructing a new topology\. Neighbor sampling selects a limited number of neighbors per node at every GNN layer\([Hamilton et al\., 2017](https://arxiv.org/html/2610.09059#bib.bib2)\)\. Layer\-wise sampling instead selects a fixed number of nodes by importance\([Chen et al\., 2018](https://arxiv.org/html/2610.09059#bib.bib3)\)\. LADIES extends this idea by picking each layer’s nodes based on which nodes were kept in the layer above it, so the sampled nodes stay connected from one layer to the next\([Zou et al\., 2019](https://arxiv.org/html/2610.09059#bib.bib43)\)\. Other methods divide the graph into clusters and train on these smaller parts\([Chiang et al\., 2019](https://arxiv.org/html/2610.09059#bib.bib5)\), or sample training subgraphs and pass messages only within them\([Zeng et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib6)\)\. AGS\-GNN\([Das et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib40)\)guides node and subgraph sampling by feature similarity and diversity, and reappears below as an edge\-disjoint variant\. Related approaches reuse historical node representations\([Fey et al\., 2021](https://arxiv.org/html/2610.09059#bib.bib9)\), quantize activations\([Ding et al\., 2021](https://arxiv.org/html/2610.09059#bib.bib10)\)or compress them further\([Liu et al\., 2022](https://arxiv.org/html/2610.09059#bib.bib13)\), or repartition the graph across workers\([Wan et al\., 2022](https://arxiv.org/html/2610.09059#bib.bib11)\)or compensate for missing cross\-partition messages\([Shi et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib12)\)\.

These methods reduce how much of the graph is processed at once, but the resulting structures are repeatedly resampled from the original topology\.EDiSinstead organizes the topology itself and controls which precomputed subgraphs are used under a specified edge\-retention budget\.

#### Graph sparsification and topology modification\.

A second group of methods changes which edges are used for message passing\. Sparsification methods remove edges while preserving structural or task\-relevant information\. Classical topology\-based approaches include uniform random removal, Local Degree\([Hamann et al\., 2016](https://arxiv.org/html/2610.09059#bib.bib18)\), Rank Degree\([Voudigari et al\., 2016](https://arxiv.org/html/2610.09059#bib.bib17)\), Forest Fire\([Leskovec and Faloutsos, 2006](https://arxiv.org/html/2610.09059#bib.bib19)\), and SCAN\([Xu et al\., 2007](https://arxiv.org/html/2610.09059#bib.bib21)\)\. Similarity\-based approaches include L\-Spar, G\-Spar, and L\-Sim, which retain edges using neighborhood similarity\([Satuluri et al\., 2011](https://arxiv.org/html/2610.09059#bib.bib20)\)\. Other structural approaches include spectral sparsification via effective resistance\([Spielman and Srivastava, 2008](https://arxiv.org/html/2610.09059#bib.bib22)\),tt\-spanners\([Peleg and Schäffer, 1989](https://arxiv.org/html/2610.09059#bib.bib39)\), and degree\-based DSpar\([Liu et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib23)\)\. A classical line of work builds cut sparsifiers by repeatedly extracting a maximum spanning forest from what is left of the graph, which gives provable guarantees on how well cut sizes are preserved\([Benczúr and Karger, 1996](https://arxiv.org/html/2610.09059#bib.bib49);[Forster and de Vos, 2023](https://arxiv.org/html/2610.09059#bib.bib31)\)\.EDiSreuses this same repeated\-forest\-extraction idea, but keeps each extracted forest as a separate, cacheable training subgraph instead of merging them into one fixed sparsifier\.

A separate line learns or adapts which elements to retain\. UGS\([Chen et al\., 2021](https://arxiv.org/html/2610.09059#bib.bib14)\), from the Unified Lottery Ticket framework, prunes edges and model parameters together over repeated training rounds\. TEDDY\([Seo et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib50)\)instead removes edges in a single pass using a degree\-based rule, avoiding UGS’s repeated pruning cycles\. AdaGLT\([Zhang et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib24)\)adds adaptive, automated sparsification\. SGS\-GNN\([Das et al\., 2026](https://arxiv.org/html/2610.09059#bib.bib51)\)learns which edges to keep using supervision and lets the user directly set the target sparsity\. MoG\([Zhang et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib25)\)combines sparsification experts with different pruning criteria and sparsity levels into task\-adaptive graphs\.

Different sparsification methods preserve different graph properties, and no single method preserves all of them well\([Chen et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib16)\)\. Removing edges therefore affects not only training cost but also how information propagates\. Sparsification has also been used against oversmoothing and oversquashing, via spectrum\-preserving pruning\([Liang et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib15);[Jamadandi et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib45)\)or a truss\-based approach that removes edges outside dense subgraphs\([Hossain et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib44)\)\. These methods generally focus on identifying or adapting a useful sparse topology for message passing, rather than on how that topology is exposed to the GNN across training steps\.

A related line changes the topology stochastically during training\. DropEdge removes a random subset of edges at each iteration\([Rong et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib42)\)\. Even feature dropout, which does not explicitly remove edges, induces different stochastic subgraphs across feature dimensions\. A theoretical analysis attributes part of dropout’s ability to mitigate oversmoothing in GCNs to this variation\([Luo et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib28)\)\. Other methods replace random removal with learned edge predictors\([Chen et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib46)\), or add parameters to stabilize message passing under changing structures\([Lee et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib47)\)\.

Structures generated by DropEdge or dropout\-induced subgraphs at different training steps can substantially overlap in the edges they use\.EDiSinstead decomposes the graph once and reuses the resulting non\-overlapping subgraphs, composing them under an explicit edge\-retention budget that lets the message\-passing topology vary while directly controlling the number of retained edges\.

#### Cacheable edge\-disjoint decomposition\.

A smaller body of work trains GNNs using multiple graph structures rather than one sparse topology\. The AGS\-GNN sampling framework\([Das et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib40)\)introduced above also includes AGS\-GS\-Disjoint, which sequentially constructs sparse subgraphs with different heuristics, removing selected edges before constructing the next\.

Our objective still differs, and so does the intent behind the construction itself\. AGS\-GS\-Disjoint’s edge\-disjoint subgraphs feed a dual\-channel sampler that uses submodular function maximization to select similar and diverse neighborhoods, adapting to homophily and heterophily\. Its per\-epoch sample draws a fixed number of these cached subgraphs padded with random residual edges, with no exact\-edge\-count guarantee or attached structural theory\.EDiSinstead studies edge\-disjoint decomposition as a general sparsification primitive\. Any residual selector composes into an exact\-BB\-edge training graph, with a proven cut\-preservation guarantee for the stored decomposition and a retention guarantee for the composed graph that holds regardless of selector\. This lets us directly compare organizing a fixed number of retained edges into non\-overlapping subgraphs against alternative ways of using the same budget, rather than optimizing for informative neighborhoods\.

SpanGNN\([Gu et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib48)\)trains using spanning subgraphs to reduce memory, and MoG\([Zhang et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib25)\)combines sparsification experts to produce adaptive sparse graphs\. GERN\([Bonchi et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib41)\)also exposes a GNN to multiple sparse structures, progressively training over a sequence of random spanning trees transformed into path graphs\. UnlikeEDiS, it does not build a persistent edge\-disjoint repository, progressing instead through independently generated sparse path structures toward efficient training rather than budget\-controlled composition of a fixed repository\. To our knowledge, none of them partitions the original edge set into a persistent, mutually edge\-disjoint collection that is later recombined under a retained\-edge constraint\.

These approaches confirm that exposing a GNN to multiple sparse structures can help, though each still addresses a different question fromEDiS, namely how to allocate a fixed retained\-edge budget across a cacheable collection of non\-overlapping subgraphs\. The graph is decomposed once, unused edges remain explicitly accounted for in a residual subgraph, and the subgraphs are recomposed under the same edge\-budget constraint at every epoch, so different training\-graph constructions can be compared under the same retained\-edge count\. Table[4](https://arxiv.org/html/2610.09059#A2.T4)compares these methods along these axes\.

MethodTypeEdgebudgetReusableMulti\-struct\.Edge\-disjointtt\-Spanner\([Peleg and Schäffer, 1989](https://arxiv.org/html/2610.09059#bib.bib39)\)Sparsification✓✓✗N/AForest Fire\([Leskovec and Faloutsos, 2006](https://arxiv.org/html/2610.09059#bib.bib19)\)Sampling✗✗✗N/ASCAN\([Xu et al\., 2007](https://arxiv.org/html/2610.09059#bib.bib21)\)Sparsification✓✓✗N/ASpectral\([Spielman and Srivastava, 2008](https://arxiv.org/html/2610.09059#bib.bib22)\)Sparsification✓✓✗N/AL\-Spar\([Satuluri et al\., 2011](https://arxiv.org/html/2610.09059#bib.bib20)\)Sparsification✓✓✗N/AG\-Spar\([Satuluri et al\., 2011](https://arxiv.org/html/2610.09059#bib.bib20)\)Sparsification✓✓✗N/AL\-Sim\([Chen et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib16)\)Sparsification✓✓✗N/ALocal Degree\([Hamann et al\., 2016](https://arxiv.org/html/2610.09059#bib.bib18)\)Sparsification✓✓✗N/ARank Degree\([Voudigari et al\., 2016](https://arxiv.org/html/2610.09059#bib.bib17)\)Sampling✗✗✗N/ANeighbor Sampling\([Hamilton et al\., 2017](https://arxiv.org/html/2610.09059#bib.bib2)\)Sampling✗✗✓✗FastGCN\([Chen et al\., 2018](https://arxiv.org/html/2610.09059#bib.bib3)\)Sampling✗✗✓✗LADIES\([Zou et al\., 2019](https://arxiv.org/html/2610.09059#bib.bib43)\)Sampling✗✗✓✗Cluster\-GCN\([Chiang et al\., 2019](https://arxiv.org/html/2610.09059#bib.bib5)\)Sampling✗✓✓✗DropEdge\([Rong et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib42)\)Stochastic✗✗✓✗GraphSAINT\([Zeng et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib6)\)Sampling✗✗✓✗Unified\-LTH / UGS\([Chen et al\., 2021](https://arxiv.org/html/2610.09059#bib.bib14)\)Learned sparsif\.✓✓✗N/ACut Sparsification\([Forster and de Vos, 2023](https://arxiv.org/html/2610.09059#bib.bib31)\)Sparsification✓✓✗N/ADSpar\([Liu et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib23)\)Sparsification✓✓✗N/AAGS\-GS\-Disjoint\([Das et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib40)\)Sampling✗✓✓✓TEDDY\([Seo et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib50)\)Learned sparsif\.✓✓✗N/AAdaGLT\([Zhang et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib24)\)Learned sparsif\.✓✓✗N/ASpanGNN\([Gu et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib48)\)Multi\-structure✗✓✓✗Feature Dropout\([Luo et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib28)\)Stochastic✗✗✓✗Learned Edge Predictors\([Chen et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib46)\)Learned stochastic✗✗✓✗Aggregation Buffering\([Lee et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib47)\)StabilizationN/AN/AN/AN/ASGS\-GNN\([Das et al\., 2026](https://arxiv.org/html/2610.09059#bib.bib51)\)Learned sparsif\.✓✓✗N/AMoG\([Zhang et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib25)\)Learned sparsif\.✓✓✓✗GERN\([Bonchi et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib41)\)Multi\-structure✗✓✓✗EDiS \(ours\)Sparsification✓✓✓✓Table 4:Comparison of graph sampling, sparsification, and multi\-structure training methods surveyed in Section[2](https://arxiv.org/html/2610.09059#S2)and Appendix[B](https://arxiv.org/html/2610.09059#A2)\.*Budget*: exposes an explicit target edge count or ratio\.*Reusable*: the structure is computed once and reused rather than resampled from scratch every step\.*Multi\-struct\.*: training exposes the GNN to more than one structural view\.*Edge\-disjoint*: multiple structures, when used, share no edges\. “N/A” marks a column that does not apply to a given method\.

## Appendix CFormal Definitions and Construction

This appendix gives the formal definitions and exact composition rules underlying the intuitive description in Section[3](https://arxiv.org/html/2610.09059#S3)\.

### C\.1Graph, GNN, and Edge Budget

###### Definition 1\(Graph\)\.

Let𝒢=\(𝒱,ℰ,𝐗\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\},\\mathbf\{X\}\)be a finite, loopless, undirected graph withn=\|𝒱\|n=\|\\mathcal\{V\}\|nodes,m=\|ℰ\|m=\|\\mathcal\{E\}\|edges, and𝐗∈ℝn×d0\\mathbf\{X\}\\in\\mathbb\{R\}^\{n\\times d\_\{0\}\}\. Each undirected edge is counted once\.

###### Definition 2\(Graph neural network\)\.

A message\-passing GNN updates node representations using their neighbors\. A graph convolutional layer\([Kipf and Welling, 2017](https://arxiv.org/html/2610.09059#bib.bib1)\)uses

𝐇ℓ\+1=σ⁡\(𝐀^​𝐇ℓ​𝐖ℓ\),𝐇0=𝐗,\\mathbf\{H\}\_\{\\ell\+1\}=\\sigma\\bigl\(\\hat\{\\mathbf\{A\}\}\\mathbf\{H\}\_\{\\ell\}\\mathbf\{W\}\_\{\\ell\}\\bigr\),\\qquad\\mathbf\{H\}\_\{0\}=\\mathbf\{X\},\(14\)where𝐀^\\hat\{\\mathbf\{A\}\}is normalized adjacency,𝐖ℓ\\mathbf\{W\}\_\{\\ell\}is a learned weight matrix, andσ\\sigmais a nonlinearity\.

###### Definition 3\(Edge budget\)\.

At epochtt, nodes and features remain fixed while training uses

𝒢B\(t\)=\(𝒱,ℰB\(t\),𝐗\),ℰB\(t\)⊆ℰ,\|ℰB\(t\)\|=B\.\\mathcal\{G\}\_\{B\}^\{\(t\)\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{B\}^\{\(t\)\},\\mathbf\{X\}\),\\qquad\\mathcal\{E\}\_\{B\}^\{\(t\)\}\\subseteq\\mathcal\{E\},\\qquad\|\\mathcal\{E\}\_\{B\}^\{\(t\)\}\|=B\.\(15\)The integer budget satisfies0≤B≤m0\\leq B\\leq m\. A retention ratioρ∈\(0,1\]\\rho\\in\(0,1\]setsB=⌈ρ​m⌉B=\\lceil\\rho m\\rceil\. Indiceskkandttdenote extraction rounds and training epochs\.

### C\.2Edge Scores and Residual Selectors

EDiSseparates edge scoring from structural extraction\.

###### Definition 4\(Edge score\)\.

A fixed scores:ℰ→ℝs:\\mathcal\{E\}\\rightarrow\\mathbb\{R\}assigns larger values to preferred edges, computed once before extraction\. Uniform scores setse=1s\_\{e\}=1\. Our default is shifted cosine similarity between endpoint features \(Section[3\.2](https://arxiv.org/html/2610.09059#S3.SS2)\)\.

###### Definition 5\(Residual selector\)\.

At extraction roundkk, a residual selectorℱk\\mathcal\{F\}\_\{k\}maps the current residual graph and edge scores to

ℰk=ℱk​\(𝒱,ℰrem\(k−1\),s\)⊆ℰrem\(k−1\),\\mathcal\{E\}\_\{k\}=\\mathcal\{F\}\_\{k\}\\bigl\(\\mathcal\{V\},\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(k\-1\)\},s\\bigr\)\\subseteq\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(k\-1\)\},\(16\)after which

ℰrem\(k\)=ℰrem\(k−1\)∖ℰk\.\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(k\)\}=\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(k\-1\)\}\\setminus\\mathcal\{E\}\_\{k\}\.\(17\)The selector may usessor ignore it and need not return a forest or a fixed number of edges\.

The framework initializes the residual edge set toℰrem\(0\)=ℰ\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(0\)\}=\\mathcal\{E\}and pairs any fixed score with any residual selector\. Implemented scores include cosine, Euclidean, dot\-product, uniform, and learned preferences\. Implemented selectors include maximum\- and minimum\-weight covering forests, uniform sampling, degree\-based selection, top\-kkneighbors, spanners, and a hybrid chaining several of these \(Appendix[F\.1](https://arxiv.org/html/2610.09059#A6.SS1)\)\.

### C\.3Maximum\-Score Residual Forests

###### Definition 6\(Covering forest\)\.

GivenH=\(𝒱,EH\)H=\(\\mathcal\{V\},E\_\{H\}\), let

𝔉⁡\(H\)=\{F⊆EH:F​is acyclic and connects every connected component of​H\}\.\\mathfrak\{F\}\(H\)=\\left\\\{F\\subseteq E\_\{H\}:F\\text\{ is acyclic and connects every connected component of \}H\\right\\\}\.\(18\)

###### Definition 7\(Principal selector\)\.

The default selectorℱmax\\mathcal\{F\}\_\{\\max\}returns a maximum\-score covering forest,

F⋆∈arg​maxF∈𝔉⁡\(H\)∑e∈Fse\.F^\{\\star\}\\in\\operatorname\*\{arg\\,max\}\_\{F\\in\\mathfrak\{F\}\(H\)\}\\sum\_\{e\\in F\}s\_\{e\}\.\(19\)

This forest is obtained by classical maximum\-weight graphic\-matroid greedy\([Edmonds, 1971](https://arxiv.org/html/2610.09059#bib.bib35)\), equivalently by Kruskal’s algorithm in decreasing score order\([Kruskal, 1956](https://arxiv.org/html/2610.09059#bib.bib34)\)\. Repeating this extraction produces a partition into successive residual forests, giving the edge\-disjoint decomposition and subgraph weights of Section[3\.2](https://arxiv.org/html/2610.09059#S3.SS2)\(Eq\. \([6](https://arxiv.org/html/2610.09059#S3.E6)\)\)\. It does not assert a minimum\-cardinality forest partition\. That stronger guarantee instead comes from matroid partition\([Edmonds, 1968](https://arxiv.org/html/2610.09059#bib.bib33)\)\.

The subgraphs, their weights, and the residual pool are computed once and reused across all training epochs and all feasible budgets\. Because composition \(Appendix[C\.5](https://arxiv.org/html/2610.09059#A3.SS5)\) never re\-invokes the selector, this holds regardless of how many budget\-epoch pairs\(B,t\)\(B,t\)are subsequently queried, and distinct epochs need not compose the same graph \(Proposition[7](https://arxiv.org/html/2610.09059#Thmtheorem7), Appendix[E\.1](https://arxiv.org/html/2610.09059#A5.SS1)\)\.

### C\.4Classical Forest Properties

###### Fact 1\(Bottleneck property\([Kruskal, 1956](https://arxiv.org/html/2610.09059#bib.bib34);[Edmonds, 1971](https://arxiv.org/html/2610.09059#bib.bib35)\)\)\.

Lete=\(u,v\)e=\(u,v\)be an edge omitted by a maximum\-score covering forestF⋆F^\{\\star\}, and letPF⋆​\(u,v\)P\_\{F^\{\\star\}\}\(u,v\)denote the unique path betweenuuandvvinside the corresponding tree\. Then

mina∈PF⋆​\(u,v\)⁡sa≥se\.\\min\_\{a\\in P\_\{F^\{\\star\}\}\(u,v\)\}s\_\{a\}\\geq s\_\{e\}\.\(20\)

###### Fact 2\(Cut certificate\([Nagamochi and Ibaraki, 1992](https://arxiv.org/html/2610.09059#bib.bib29);[Frank et al\., 1993](https://arxiv.org/html/2610.09059#bib.bib30)\)\)\.

Letℰ1,…,ℰk\\mathcal\{E\}\_\{1\},\\ldots,\\mathcal\{E\}\_\{k\}be covering forests extracted successively from the residual graph\. For every nonempty properS⊊𝒱S\\subsetneq\\mathcal\{V\},

\|δUk​\(S\)\|≥min⁡\{k,\|δ𝒢​\(S\)\|\}\.\|\\delta\_\{U\_\{k\}\}\(S\)\|\\geq\\min\\left\\\{k,\|\\delta\_\{\\mathcal\{G\}\}\(S\)\|\\right\\\}\.\(21\)

The bottleneck property concerns a single maximum\-score forest, whereas the cut certificate concerns the union of successive residual forests\. Neither claims thatUkU\_\{k\}is jointly optimal among all edge sets of the same size\.

### C\.5Exact Stochastic Budgeted Composition

At epochtt,EDiSdraws an orderingπ\(t\)=\(k1,…,kK\)\\pi^\{\(t\)\}=\(k\_\{1\},\\ldots,k\_\{K\}\)without replacement, where, withRrR\_\{r\}the subgraph indices remaining before drawrr,

Pr⁡\(kr=k∣Rr\)=wk∑j∈Rrwj,k∈Rr\.\\Pr\(k\_\{r\}=k\\mid R\_\{r\}\)=\\frac\{w\_\{k\}\}\{\\sum\_\{j\\in R\_\{r\}\}w\_\{j\}\},\\qquad k\\in R\_\{r\}\.\(22\)WithN=\|UK\|N=\|U\_\{K\}\|, subgraphs accumulate in sampled order until their total size first reaches or exceedsBB, at round

rB\(t\)=min⁡\{r∈\{1,…,K\}:∑ℓ=1r\|ℰkℓ\|≥B\},r\_\{B\}^\{\(t\)\}=\\min\\left\\\{r\\in\\\{1,\\ldots,K\\\}:\\textstyle\\sum\_\{\\ell=1\}^\{r\}\|\\mathcal\{E\}\_\{k\_\{\\ell\}\}\|\\geq B\\right\\\},\(23\)giving the selected subgraphs and their candidate edges

A\(t\)=\{∅,B=0,\{k1,…,krB\(t\)\},0<B≤N,\{1,…,K\},N<B≤m,CB\(t\)=⨆k∈A\(t\)ℰk\.A^\{\(t\)\}=\\begin\{cases\}\\varnothing,&B=0,\\\\ \\\{k\_\{1\},\\ldots,k\_\{r\_\{B\}^\{\(t\)\}\}\\\},&0<B\\leq N,\\\\ \\\{1,\\ldots,K\\\},&N<B\\leq m,\\end\{cases\}\\qquad C\_\{B\}^\{\(t\)\}=\\bigsqcup\_\{k\\in A^\{\(t\)\}\}\\mathcal\{E\}\_\{k\}\.\(24\)
If\|CB\(t\)\|\>B\|C\_\{B\}^\{\(t\)\}\|\>B, the excessΔB\(t\)=\|CB\(t\)\|−B\\Delta\_\{B\}^\{\(t\)\}=\|C\_\{B\}^\{\(t\)\}\|\-Bis removed from selected subgraphs in increasing\(wk,k\)\(w\_\{k\},k\)order, dropping whole subgraphs until the remaining excess fits inside one subgraph, then trimming that subgraph uniformly without replacement, so at most one selected subgraph is partially retained\. IfB\>NB\>Ninstead, all stored edges are kept and the remainingB−NB\-Nedges are sampled uniformly without replacement fromℰres\\mathcal\{E\}\_\{\\mathrm\{res\}\}into a residual completion setQB\(t\)Q\_\{B\}^\{\(t\)\}, otherwiseQB\(t\)=∅Q\_\{B\}^\{\(t\)\}=\\varnothing\.

Writingℰ~k\(t\)\\widetilde\{\\mathcal\{E\}\}\_\{k\}^\{\(t\)\}for the retained part of subgraphkkafter trimming \(empty fork∉A\(t\)k\\notin A^\{\(t\)\}\), the final epoch graph is

ℰB\(t\)=\(⨆k=1Kℰ~k\(t\)\)⊔QB\(t\)\.\\boxed\{\\mathcal\{E\}\_\{B\}^\{\(t\)\}=\\left\(\\bigsqcup\_\{k=1\}^\{K\}\\widetilde\{\\mathcal\{E\}\}\_\{k\}^\{\(t\)\}\\right\)\\sqcup Q\_\{B\}^\{\(t\)\}\.\}\(25\)
###### Proposition 3\(Exact\-budget feasibility\)\.

For every integer0≤B≤m0\\leq B\\leq m,

\|ℰB\(t\)\|=B\.\|\\mathcal\{E\}\_\{B\}^\{\(t\)\}\|=B\.\(26\)

The edge\-disjoint partition prevents duplicates, and whenB\>NB\>Nthe residual pool always contains at leastB−NB\-Nedges becausem−N≥B−Nm\-N\\geq B\-N\. A complete proof is given in Appendix[E\.1](https://arxiv.org/html/2610.09059#A5.SS1)\.

### C\.6Structural Preservation of the Stored Decomposition

To track only the edges a threshold cares about, fixτ∈ℝ\\tau\\in\\mathbb\{R\}and focus only on the high\-score subgraph and its stored counterpart,

ℰ≥τ=\{e∈ℰ:se≥τ\},𝒢≥τ=\(𝒱,ℰ≥τ\),Uk,≥τ=Uk∩ℰ≥τ\.\\mathcal\{E\}\_\{\\geq\\tau\}=\\\{e\\in\\mathcal\{E\}:s\_\{e\}\\geq\\tau\\\},\\qquad\\mathcal\{G\}\_\{\\geq\\tau\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{\\geq\\tau\}\),\\qquad U\_\{k,\\geq\\tau\}=U\_\{k\}\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\.Theorem[1](https://arxiv.org/html/2610.09059#Thmtheorem1)in Section[3](https://arxiv.org/html/2610.09059#S3)states that every stored prefix certifies a lower bound on the number of threshold\-qualified crossing edges within this restricted view\. For every completed round, threshold, and nontrivial cut,

\|δUk,≥τ​\(S\)\|≥min⁡\{k,\|δ𝒢≥τ​\(S\)\|\}\.\|\\delta\_\{U\_\{k,\\geq\\tau\}\}\(S\)\|\\geq\\min\\left\\\{k,\|\\delta\_\{\\mathcal\{G\}\_\{\\geq\\tau\}\}\(S\)\|\\right\\\}\.The exchange proof and the treatment of ties are given in Appendix[E\.2](https://arxiv.org/html/2610.09059#A5.SS2)\.

The threshold certificate above only bounds how many high\-score edges survive\. To state a stronger guarantee on their exact values, letaj​\(S\)a\_\{j\}\(S\)andbj​\(S\)b\_\{j\}\(S\)denote thejj\-th largest crossing score at cutSSinℰ\\mathcal\{E\}and inUkU\_\{k\}, respectively\.

###### Corollary 4\(Top\-kkcut\-score preservation\)\.

Under the assumptions of Theorem[1](https://arxiv.org/html/2610.09059#Thmtheorem1),

bj​\(S\)=aj​\(S\),1≤j≤min⁡\{k,\|δ𝒢​\(S\)\|\}\.b\_\{j\}\(S\)=a\_\{j\}\(S\),\\qquad 1\\leq j\\leq\\min\\\{k,\|\\delta\_\{\\mathcal\{G\}\}\(S\)\|\\\}\.\(27\)

Thus every cut’s top\-kkcrossing\-score values are preserved with multiplicity\. The proof is given in Appendix[E\.3](https://arxiv.org/html/2610.09059#A5.SS3)\.

### C\.7Retention After Budgeted Composition

The deterministic certificates above concern the stored prefixUkU\_\{k\}\. A composed epoch graph may omit or trim subgraphs, so it need not contain that prefix\. Theorem[2](https://arxiv.org/html/2610.09059#Thmtheorem2)in Section[3](https://arxiv.org/html/2610.09059#S3)instead bounds the conditional probability that a fixed cut keeps at least one qualifying crossing edge inℰB\(t\)\\mathcal\{E\}\_\{B\}^\{\(t\)\}\. We now state the exact identity behind that guarantee\.

Condition on the sampled orderπ\(t\)\\pi^\{\(t\)\}together with the decomposition, subgraph weights, and budget, leaving uniform trimming or residual completion as the remaining source of randomness\. We index the residual set alongside theKKstored subgraphs by writing

D0=ℰres,Dk=ℰk​\(1≤k≤K\),nk=\|Dk\|,rk=\|Dk∩ℰB\(t\)\|,D\_\{0\}=\\mathcal\{E\}\_\{\\mathrm\{res\}\},\\qquad D\_\{k\}=\\mathcal\{E\}\_\{k\}\\ \(1\\leq k\\leq K\),\\qquad n\_\{k\}=\|D\_\{k\}\|,\\qquad r\_\{k\}=\|D\_\{k\}\\cap\\mathcal\{E\}\_\{B\}^\{\(t\)\}\|,soD0,…,DKD\_\{0\},\\ldots,D\_\{K\}are theK\+1K\+1sets composition draws from,nkn\_\{k\}is each one’s size, andrkr\_\{k\}counts how many of its edges the composed graph actually keeps\. The retained fraction is

θk=\{rk/nk,nk\>0,0,nk=0,\\theta\_\{k\}=\\begin\{cases\}r\_\{k\}/n\_\{k\},&n\_\{k\}\>0,\\\\ 0,&n\_\{k\}=0,\\end\{cases\}\(28\)and, for cutSSand thresholdτ\\tau, the number of subgraph\-kkedges that would matter for that cut is

xk​\(S,τ\)=\|Dk∩δ𝒢​\(S\)∩ℰ≥τ\|\.x\_\{k\}\(S,\\tau\)=\|D\_\{k\}\\cap\\delta\_\{\\mathcal\{G\}\}\(S\)\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\|\.\(29\)Given the sampled order, everynkn\_\{k\}andrkr\_\{k\}is fixed, and at most one subgraph contributes a randomly trimmed subset\.

###### Theorem 5\(Conditional retention under composition, in full\)\.

For any fixed additive edge weightω\\omega,

𝔼⁡\[ω⁡\(ℰB\(t\)\)∣π\(t\)\]=∑k=0Kθk​ω​\(Dk\)\.\\mathbb\{E\}\\left\[\\omega\(\\mathcal\{E\}\_\{B\}^\{\(t\)\}\)\\mid\\pi^\{\(t\)\}\\right\]=\\sum\_\{k=0\}^\{K\}\\theta\_\{k\}\\omega\(D\_\{k\}\)\.\(30\)Moreover,

Pr⁡\(ℰB\(t\)∩δ𝒢​\(S\)∩ℰ≥τ=∅\|π\(t\)\)=∏k=0K\(nk−xk​\(S,τ\)rk\)\(nkrk\)\.\\Pr\\\!\\left\(\\mathcal\{E\}\_\{B\}^\{\(t\)\}\\cap\\delta\_\{\\mathcal\{G\}\}\(S\)\\cap\\mathcal\{E\}\_\{\\geq\\tau\}=\\varnothing\\;\\middle\|\\;\\pi^\{\(t\)\}\\right\)=\\prod\_\{k=0\}^\{K\}\\frac\{\\binom\{n\_\{k\}\-x\_\{k\}\(S,\\tau\)\}\{r\_\{k\}\}\}\{\\binom\{n\_\{k\}\}\{r\_\{k\}\}\}\.\(31\)

###### Corollary 6\(Per\-cut high\-score edge survival\)\.

Under the same conditioning,

Pr\(ℰB\(t\)∩δ𝒢\(S\)∩ℰ≥τ≠∅\|π\(t\)\)≥1−exp\(−∑k=0Kθkxk\(S,τ\)\)\.\\Pr\\\!\\left\(\\mathcal\{E\}\_\{B\}^\{\(t\)\}\\cap\\delta\_\{\\mathcal\{G\}\}\(S\)\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\\neq\\varnothing\\;\\middle\|\\;\\pi^\{\(t\)\}\\right\)\\geq 1\-\\exp\\left\(\-\\sum\_\{k=0\}^\{K\}\\theta\_\{k\}x\_\{k\}\(S,\\tau\)\\right\)\.\(32\)This is the bound displayed as Theorem[2](https://arxiv.org/html/2610.09059#Thmtheorem2)in Section[3](https://arxiv.org/html/2610.09059#S3)\.

The quantity∑k=0Kθk​xk​\(S,τ\)\\sum\_\{k=0\}^\{K\}\\theta\_\{k\}x\_\{k\}\(S,\\tau\)is the conditional expected number of retained high\-score crossings\. Neither result uses any property specific to maximum\-score forests, since composition retains a uniform random subset within each partially trimmed subgraph regardless of selector\. Both therefore hold unchanged for every selector in Appendix[F\.1](https://arxiv.org/html/2610.09059#A6.SS1)\. These results characterize what survives budgeted composition\. They do not by themselves imply that weighted ordering is superior to uniform ordering, or that spreading edges across subgraphs is always beneficial\. Those questions are tested empirically in Section[4](https://arxiv.org/html/2610.09059#S4), with proofs in Appendix[E\.5](https://arxiv.org/html/2610.09059#A5.SS5)\.

## Appendix DWorked Examples of Structural Selectors

Seven selectors share the same scored input, three extraction rounds, and six\-edge sample budget\. Figure[8](https://arxiv.org/html/2610.09059#A4.F8)shows the stored subgraphs and two six\-edge samples from the same decomposition\.

Figure 8:Structural selection and exact\-budget composition in EDiS\.Colors and line styles identify edge\-disjoint subgraphs, extracted in order\(1,2,3\)\(1,2,3\)and reused across epochs\. The two illustrative epochs sample subgraph orders\(3,1,2\)\(3,1,2\)and\(1,2,3\)\(1,2,3\), adding subgraphs until six edges are reached and trimming any excess uniformly from the lowest\-weight subgraph\. Samples may overlap and are not guaranteed to differ\. These examples illustrate the rules, not predictive rankings\.Settings\.MaxCF selects a residual covering forest with the largest total score\. MinCF selects one with the smallest total score\. Thekk\-NN example usesk=1k=1without adjusting the edge count\. Random and DegreeNorm select up to five edges per round\. Random gives each residual edge equal weight\. DegreeNorm uses1/dH​\(u\)\+1/dH​\(v\)1/d\_\{H\}\(u\)\+1/d\_\{H\}\(v\), held fixed during each round\. The example spanner processes edges from shortest to longest using length1/se1/s\_\{e\}\. It adds an edge when the current path between its endpoints is longer than2/se2/s\_\{e\}\. This illustrative procedure differs from the randomized benchmark routine\. Hybrid applies MaxCF, then11\-NN, then DegreeNorm\.

The table gives the shared edge scores\. Each subgraph weight is the sum of its edge scores\.

Edgea​baba​cacb​cbcd​eded​fdfe​fefc​dcda​eaeb​fbfa​dadc​ecec​fcfScore121110987654321MaxCF and Spanner produce the same subgraphs in this example\. Thekk\-NN decomposition leaves one residual edge\. No sample needs residual completion\. Guarantees for stored subgraphs may not hold after composition\. Appendix[F\.1](https://arxiv.org/html/2610.09059#A6.SS1)describes each selector’s procedure\.

## Appendix ETheoretical Understanding and Proofs

A cut’s crossing edges are the only channel through which one layer of message passing can move information between its two sides, so the results below characterize threshold\-qualified crossings in stored maximum\-score forest prefixes and their conditional retention under composition\.

All graphs are finite, undirected, and loopless, withn≥2n\\geq 2vertices, and every undirected edge is counted once\. Decomposition results apply to each realized extraction sequence satisfying the corresponding hypotheses\. Ordinary cut certificates require successive residual covering forests\. Score\-threshold, top\-kkscore, and score\-qualified path results require maximum\-score residual covering forests under fixed real scores\. Randomized tie\-breaking among maximizers is allowed\. Arbitrary randomized or non\-forest selectors do not inherit these guarantees\. Sampling results condition on the realized decomposition, cached weights, and edge\-budget\.

### E\.1Reuse and Exact\-Budget Feasibility

###### Proposition 7\(Cacheable stochastic support generation\)\.

Fix a stored decomposition𝒟\\mathcal\{D\}\. Any number of subsequent edge\-budget–epoch queries can be answered without reevaluating the structural selector\. For fixedBB, letμB\\mu\_\{B\}be the support distribution induced by composition\. If epochs are independent draws from this same distribution andμB\\mu\_\{B\}is non\-degenerate, then fort≠t′t\\neq t^\{\\prime\},

Pr⁡\(ℰB\(t\)≠ℰB\(t′\)\)=1−∑𝒮μB​\(𝒮\)2\>0\.\\Pr\(\\mathcal\{E\}\_\{B\}^\{\(t\)\}\\neq\\mathcal\{E\}\_\{B\}^\{\(t^\{\\prime\}\)\}\)=1\-\\sum\_\{\\mathcal\{S\}\}\\mu\_\{B\}\(\\mathcal\{S\}\)^\{2\}\>0\.\(33\)

###### Proof\.

The selector is invoked only during decomposition, while composition operates on the stored partition and weights\. Independent draws fromμB\\mu\_\{B\}coincide with probability∑𝒮μB​\(𝒮\)2\\sum\_\{\\mathcal\{S\}\}\\mu\_\{B\}\(\\mathcal\{S\}\)^\{2\}\. Taking its complement proves the identity\. Non\-degeneracy makes this collision probability strictly less than one\. ∎

###### Proof of Proposition[3](https://arxiv.org/html/2610.09059#Thmtheorem3)\.

The stored subgraphs and residual form an edge\-disjoint partition ofℰ\\mathcal\{E\}, so every returned edge is original and no edge is counted twice\. ForB=0B=0, composition returns the empty set\. If0<B≤\|UK\|0<B\\leq\|U\_\{K\}\|, the selected subgraphs reach the edge\-budget and trimming removes exactly\|CB\(t\)\|−B\|C\_\{B\}^\{\(t\)\}\|\-Bedges\. If\|UK\|<B≤m\|U\_\{K\}\|<B\\leq m, all structural subgraphs are retained and the residual supplies the deficit, since\|ℰres\|=m−\|UK\|≥B−\|UK\|\|\\mathcal\{E\}\_\{\\mathrm\{res\}\}\|=m\-\|U\_\{K\}\|\\geq B\-\|U\_\{K\}\|\. These cases includeK=0K=0and yield exactlyBBedges\. ∎

### E\.2Score\-Threshold Certificate

Throughout this proof,FiF\_\{i\}denotes theii\-th extracted subgraphℰi\\mathcal\{E\}\_\{i\}andUkU\_\{k\}its stored union⋃i≤kℰi\\bigcup\_\{i\\leq k\}\\mathcal\{E\}\_\{i\}, matching the maximum\-score covering\-forest notation of Fact[2](https://arxiv.org/html/2610.09059#Thmfact2)under the defaultℱmax\\mathcal\{F\}\_\{\\max\}selector\.

###### Proof of Theorem[1](https://arxiv.org/html/2610.09059#Thmtheorem1)\.

Fixτ\\tauand letFiτ:=Fi∩ℰ≥τF\_\{i\}^\{\\tau\}:=F\_\{i\}\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\.

SupposeFiτF\_\{i\}^\{\\tau\}does not span a component of\(𝒱,ℰrem\(i−1\)∩ℰ≥τ\)\\bigl\(\\mathcal\{V\},\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(i\-1\)\}\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\\bigr\)\. Then somee∈ℰrem\(i−1\)∩ℰ≥τe\\in\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(i\-1\)\}\\cap\\mathcal\{E\}\_\{\\geq\\tau\}joins two components ofFiτF\_\{i\}^\{\\tau\}\. SinceFiF\_\{i\}is a covering forest of the residual graph,Fi\+eF\_\{i\}\+econtains a unique cycle, and sinceeecreates no cycle inFiτF\_\{i\}^\{\\tau\}, that cycle contains somef∈Fi∖Fiτf\\in F\_\{i\}\\setminus F\_\{i\}^\{\\tau\}, sosf<τ≤ses\_\{f\}<\\tau\\leq s\_\{e\}\. Hence

s⁡\(Fi−f\+e\)=s⁡\(Fi\)−sf\+se\>s⁡\(Fi\),s\(F\_\{i\}\-f\+e\)=s\(F\_\{i\}\)\-s\_\{f\}\+s\_\{e\}\>s\(F\_\{i\}\),\(34\)contradicting the maximum\-score optimality ofFiF\_\{i\}\. Therefore

Fiτ∈𝔉⁡\(𝒱,ℰrem\(i−1\)∩ℰ≥τ\)\.F\_\{i\}^\{\\tau\}\\in\\mathfrak\{F\}\\bigl\(\\mathcal\{V\},\\ \\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(i\-1\)\}\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\\bigr\)\.\(35\)
Also

ℰrem\(i−1\)∩ℰ≥τ=ℰ≥τ∖⋃j<iFjτ,\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(i\-1\)\}\\cap\\mathcal\{E\}\_\{\\geq\\tau\}=\\mathcal\{E\}\_\{\\geq\\tau\}\\setminus\\bigcup\_\{j<i\}F\_\{j\}^\{\\tau\},\(36\)soF1τ,…,FkτF\_\{1\}^\{\\tau\},\\ldots,F\_\{k\}^\{\\tau\}are successive residual covering forests of𝒢≥τ\\mathcal\{G\}\_\{\\geq\\tau\}for every completed round1≤k≤K1\\leq k\\leq K\. Applying Fact[2](https://arxiv.org/html/2610.09059#Thmfact2)inside𝒢≥τ\\mathcal\{G\}\_\{\\geq\\tau\}toUk,≥τ=⋃i≤kFiτU\_\{k,\\geq\\tau\}=\\bigcup\_\{i\\leq k\}F\_\{i\}^\{\\tau\},

\|δUk,≥τ​\(S\)\|≥min⁡\{k,\|δ𝒢≥τ​\(S\)\|\}\.∎\\boxed\{\|\\delta\_\{U\_\{k,\\geq\\tau\}\}\(S\)\|\\ \\geq\\ \\min\\\{k,\|\\delta\_\{\\mathcal\{G\}\_\{\\geq\\tau\}\}\(S\)\|\\\}\.\}\\qed\(37\)

This exchange uses maximum\-score optimality alone, so no sign assumption onssand no tie\-breaking rule enter the argument\. A non\-maximum\-score covering forest still gives the ordinary count certificate, but not the score\-threshold form above\.

The guarantee holds simultaneously for every nontrivial cut in the stored prefix\. Its crossing edges provide potential one\-hop message\-passing connections between the two sides\. Whether the retained connections carry useful evidence for node classification depends on the features, task, and model\. The certificate itself concerns edge scores and cut counts\.

### E\.3Top\-kkCut\-Score Corollary

For an edge setAA, define the sum of its largest crossing scores by

Tk​\(S,A\)=∑j=1min⁡\{k,\|δA​\(S\)\|\}s\(j\)​\(δA​\(S\)\)\.T\_\{k\}\(S;A\)=\\sum\_\{j=1\}^\{\\min\\\{k,\|\\delta\_\{A\}\(S\)\|\\\}\}s\_\{\(j\)\}\(\\delta\_\{A\}\(S\)\)\.For a graph,AAdenotes its edge set\. Scores are ordered with multiplicity, so tied edges contribute separately\. Leta1​\(S\)≥a2​\(S\)≥⋯a\_\{1\}\(S\)\\geq a\_\{2\}\(S\)\\geq\\cdotsbe the scores of the original crossing edges of a cutSSandb1​\(S\)≥b2​\(S\)≥⋯b\_\{1\}\(S\)\\geq b\_\{2\}\(S\)\\geq\\cdotsthose kept inUkU\_\{k\}\.

###### Corollary 8\(Top\-kkcut\-score preservation, restated\)\.

For every completed round1≤k≤K1\\leq k\\leq Kand nonempty proper cutSS,

bj​\(S\)=aj​\(S\),1≤j≤min⁡\{k,\|δ𝒢​\(S\)\|\}\.b\_\{j\}\(S\)=a\_\{j\}\(S\),\\qquad 1\\leq j\\leq\\min\\\{k,\|\\delta\_\{\\mathcal\{G\}\}\(S\)\|\\\}\.\(38\)

###### Proof of Corollary[8](https://arxiv.org/html/2610.09059#Thmtheorem8)\.

FixSSand writeM=\|δ𝒢​\(S\)\|M=\|\\delta\_\{\\mathcal\{G\}\}\(S\)\|\. Forj≤min⁡\{k,M\}j\\leq\\min\\\{k,M\\\}setτ=aj​\(S\)\\tau=a\_\{j\}\(S\)\. Then

\|δ𝒢≥τ​\(S\)\|≥j,\|\\delta\_\{\\mathcal\{G\}\_\{\\geq\\tau\}\}\(S\)\|\\geq j,\(39\)so by Theorem[1](https://arxiv.org/html/2610.09059#Thmtheorem1),\|δUk,≥τ​\(S\)\|≥j\|\\delta\_\{U\_\{k,\\geq\\tau\}\}\(S\)\|\\geq j, givingbj​\(S\)≥aj​\(S\)b\_\{j\}\(S\)\\geq a\_\{j\}\(S\)\. SinceUk⊆ℰU\_\{k\}\\subseteq\\mathcal\{E\}, alsobj​\(S\)≤aj​\(S\)b\_\{j\}\(S\)\\leq a\_\{j\}\(S\)\. Hence

bj\(S\)=aj\(S\),j≤min\{k,M\}\.\\boxed\{b\_\{j\}\(S\)=a\_\{j\}\(S\),\\qquad j\\leq\\min\\\{k,M\\\}\.\}\(40\)Takingτ\\taubelow every score givesM≥\|δUk​\(S\)\|≥min⁡\{k,M\}M\\geq\|\\delta\_\{U\_\{k\}\}\(S\)\|\\geq\\min\\\{k,M\\\}, somin⁡\{k,\|δUk​\(S\)\|\}=min⁡\{k,M\}\\min\\\{k,\|\\delta\_\{U\_\{k\}\}\(S\)\|\\\}=\\min\\\{k,M\\\}, and summing \([40](https://arxiv.org/html/2610.09059#A5.E40)\) term by term,

Tk​\(S,Uk\)=Tk​\(S,𝒢\)\.∎\\boxed\{T\_\{k\}\(S;U\_\{k\}\)=T\_\{k\}\(S;\\mathcal\{G\}\)\.\}\\qed\(41\)

The equality preserves the top\-kkcrossing\-score values with multiplicity\. With tied scores, it need not preserve particular edge identities\. For the cosine default, this means preserving the largest feature\-similarity scores across each cut\. The usefulness of that preference for prediction is evaluated empirically\.

### E\.4Equivalent Interpretations

###### Proposition 9\(Submodular reading\([Nemhauser et al\., 1978](https://arxiv.org/html/2610.09059#bib.bib32)\)\)\.

For a fixed cutSSand integerk≥1k\\geq 1, letg⁡\(A\)=\|δA​\(S\)\|g\(A\)=\|\\delta\_\{A\}\(S\)\|andϕ⁡\(z\)=min⁡\{z,k\}\\phi\(z\)=\\min\\\{z,k\\\}\. ThenfS,k:=ϕ∘gf\_\{S,k\}:=\\phi\\circ gis monotone submodular\. If1≤k≤K1\\leq k\\leq KandUkU\_\{k\}is a prefix of successive residual covering forests, thenfS,k​\(Uk\)=fS,k​\(ℰ\)f\_\{S,k\}\(U\_\{k\}\)=f\_\{S,k\}\(\\mathcal\{E\}\)\.

###### Proof\.

ggis modular andϕ\\phiis nondecreasing and concave, so

fS,k​\(A\)=min⁡\{\|δA​\(S\)\|,k\}f\_\{S,k\}\(A\)=\\min\\\{\|\\delta\_\{A\}\(S\)\|,k\\\}\(42\)is monotone submodular, and so is any nonnegative combination∑SαS​fS,k\\sum\_\{S\}\\alpha\_\{S\}f\_\{S,k\}\. Fact[2](https://arxiv.org/html/2610.09059#Thmfact2)gives

fS,k​\(Uk\)=fS,k​\(ℰ\)\.∎\\boxed\{f\_\{S,k\}\(U\_\{k\}\)=f\_\{S,k\}\(\\mathcal\{E\}\)\.\}\\qed\(43\)

This is an interpretation of the stored certificate, not the objectiveEDiSoptimizes\.

###### Proposition 10\(Edge\-disjoint path reading\)\.

Under a pureℱmax\\mathcal\{F\}\_\{\\max\}schedule with fixed real scores, let1≤k≤K1\\leq k\\leq Kande=\(u,v\)∈ℰ∖Uke=\(u,v\)\\in\\mathcal\{E\}\\setminus U\_\{k\}\. ThenUkU\_\{k\}containskkedge\-disjointuu–vvpaths whose edges all have score at leastses\_\{e\}\.

###### Proof\.

e∉Uke\\notin U\_\{k\}gives

e∈ℰrem\(i−1\)∀i≤k\.e\\in\\mathcal\{E\}\_\{\\mathrm\{rem\}\}^\{\(i\-1\)\}\\qquad\\forall\\,i\\leq k\.\(44\)By the bottleneck property \(Fact[1](https://arxiv.org/html/2610.09059#Thmfact1)\), eachFiF\_\{i\}carries a pathPi​\(u,v\)⊆FiP\_\{i\}\(u,v\)\\subseteq F\_\{i\}withminf∈Pi​\(u,v\)⁡sf≥se\\min\_\{f\\in P\_\{i\}\(u,v\)\}s\_\{f\}\\geq s\_\{e\}\. SinceFi∩Fj=∅F\_\{i\}\\cap F\_\{j\}=\\varnothingfori≠ji\\neq j, the pathsP1,…,PkP\_\{1\},\\ldots,P\_\{k\}are edge\-disjoint\. HenceUkU\_\{k\}holdskkedge\-disjointuu–vvpaths of score at leastses\_\{e\}\. ∎

In plain terms, for any original edgeeeoutside the stored prefixUkU\_\{k\}, the stored prefixUkU\_\{k\}already containskkdifferent routes between its two endpoints, no two of which share an edge, and every edge on every route scores at least as well aseeitself\. Droppingeecannot disconnectuufromvvthrough routes this good unless at leastkkof those routes are also removed\. This is the path\-side mirror of the cut certificate above\. The cut version counts surviving edges across a fixed cut, while the path version exhibits the actual routes behind that count\. Two of thekkpaths may still share an intermediate vertex, since the guarantee covers edges rather than vertices, and it holds only for the pureℱmax\\mathcal\{F\}\_\{\\max\}schedule with fixed real scores\.

These paths establish alternative routes in the stored prefix\. The proposition does not bound their hop lengths or their survival after composition\. A path can support propagation in anLL\-layer message\-passing GNN only if its length is at mostLLand all its edges are retained\. Even then, reachability alone does not guarantee useful influence on the prediction\.

### E\.5Composition Retention

All probabilities condition on the realized decomposition, cached subgraph weights, and edge\-budget in addition to the displayedπ\(t\)\\pi^\{\(t\)\}\. Trimming uses increasing\(wk,k\)\(w\_\{k\},k\)order, so this conditioning fixes all retained counts\. ForB=0B=0, the identities hold trivially\. The displayed ordering may then be regarded as an unused latent weighted permutation\. ForK=0K=0, this permutation is empty\. WriteA\(t\)A^\{\(t\)\}for the selected structural indices\. Fornk=0n\_\{k\}=0, setrk=0r\_\{k\}=0andθk=0\\theta\_\{k\}=0\. We use\(00\)=1\\binom\{0\}\{0\}=1and\(ab\)=0\\binom\{a\}\{b\}=0for integersb\>a≥0b\>a\\geq 0\. Thus an empty pool contributes a factor of one to cut avoidance\.

Fix𝒟\\mathcal\{D\}, its weights, andBB, and condition onπ\(t\)\\pi^\{\(t\)\}\. SetD0=ℰresD\_\{0\}=\\mathcal\{E\}\_\{\\mathrm\{res\}\}andDk=ℰkD\_\{k\}=\\mathcal\{E\}\_\{k\}for1≤k≤K1\\leq k\\leq K, withnk=\|Dk\|n\_\{k\}=\|D\_\{k\}\|, retained countrkr\_\{k\}, andθk=rk/nk\\theta\_\{k\}=r\_\{k\}/n\_\{k\}fornk\>0n\_\{k\}\>0\(zero otherwise\)\. For a cutSSand thresholdτ\\tau, letxk​\(S,τ\)=\|Dk∩δ𝒢​\(S\)∩ℰ≥τ\|x\_\{k\}\(S,\\tau\)=\|D\_\{k\}\\cap\\delta\_\{\\mathcal\{G\}\}\(S\)\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\|count its high\-score crossing edges\.

###### Theorem 11\(Conditional retention under composition, restated\)\.

For any fixed additive edge weightω\\omega, cutSS, and thresholdτ\\tau,

𝔼⁡\[ω⁡\(ℰB\(t\)\)∣π\(t\)\]=∑k=0Kθk​ω​\(Dk\),Pr⁡\(ℰB\(t\)∩δ𝒢​\(S\)∩ℰ≥τ=∅∣π\(t\)\)=∏k=0K\(nk−xk​\(S,τ\)rk\)\(nkrk\)\.\\mathbb\{E\}\[\\omega\(\\mathcal\{E\}\_\{B\}^\{\(t\)\}\)\\mid\\pi^\{\(t\)\}\]=\\sum\_\{k=0\}^\{K\}\\theta\_\{k\}\\,\\omega\(D\_\{k\}\),\\qquad\\Pr\\bigl\(\\mathcal\{E\}\_\{B\}^\{\(t\)\}\\cap\\delta\_\{\\mathcal\{G\}\}\(S\)\\cap\\mathcal\{E\}\_\{\\geq\\tau\}=\\varnothing\\mid\\pi^\{\(t\)\}\\bigr\)=\\prod\_\{k=0\}^\{K\}\\frac\{\\binom\{n\_\{k\}\-x\_\{k\}\(S,\\tau\)\}\{r\_\{k\}\}\}\{\\binom\{n\_\{k\}\}\{r\_\{k\}\}\}\.\(45\)

###### Proof of Theorem[11](https://arxiv.org/html/2610.09059#Thmtheorem11)\.

Condition onπ\(t\)\\pi^\{\(t\)\}, fixingA\(t\)A^\{\(t\)\}and the retained counts0≤rk≤nk0\\leq r\_\{k\}\\leq n\_\{k\},0≤k≤K0\\leq k\\leq K, with∑k=0Krk=B\\sum\_\{k=0\}^\{K\}r\_\{k\}=B\. Depletion removes whole subgraphs before partially trimming at most one subgraph\. Uniform deletion leaves a uniform retained subset of that subgraph\. All other structural pool subsets are deterministic\. Residual completion occurs only when every structural subgraph is fully retained, so only the residual subset can then be non\-degenerate\. Thus at most one pool subset is non\-degenerate under the conditioning, and the pool subsets are conditionally independent\. Each pool contributes a uniformrkr\_\{k\}\-subset, including the unique empty or full subset whenrk=0r\_\{k\}=0orrk=nkr\_\{k\}=n\_\{k\}\. Hence

Pr⁡\(e∈ℰB\(t\)∣π\(t\)\)=θk∀e∈Dk\.\\Pr\(e\\in\\mathcal\{E\}\_\{B\}^\{\(t\)\}\\mid\\pi^\{\(t\)\}\)=\\theta\_\{k\}\\qquad\\forall\\,e\\in D\_\{k\}\.\(46\)By linearity of expectation onω\(ℰB\(t\)\)=∑eωe𝟏\{e∈ℰB\(t\)\}\\omega\(\\mathcal\{E\}\_\{B\}^\{\(t\)\}\)=\\sum\_\{e\}\\omega\_\{e\}\\mathbf\{1\}\\\{e\\in\\mathcal\{E\}\_\{B\}^\{\(t\)\}\\\},

𝔼⁡\[ω⁡\(ℰB\(t\)\)∣π\(t\)\]=∑k=0Kθk​ω​\(Dk\)\.\\boxed\{\\mathbb\{E\}\\bigl\[\\omega\(\\mathcal\{E\}\_\{B\}^\{\(t\)\}\)\\mid\\pi^\{\(t\)\}\\bigr\]=\\sum\_\{k=0\}^\{K\}\\theta\_\{k\}\\,\\omega\(D\_\{k\}\)\.\}\(47\)
For a cutSSand thresholdτ\\tau, mark thexk​\(S,τ\)=\|Dk∩δ𝒢​\(S\)∩ℰ≥τ\|x\_\{k\}\(S,\\tau\)=\|D\_\{k\}\\cap\\delta\_\{\\mathcal\{G\}\}\(S\)\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\|crossing edges in eachDkD\_\{k\}\. Exactly\(nk−xk​\(S,τ\)rk\)\\binom\{n\_\{k\}\-x\_\{k\}\(S,\\tau\)\}\{r\_\{k\}\}of the\(nkrk\)\\binom\{n\_\{k\}\}\{r\_\{k\}\}retained subsets avoid them, so

hk:=h⁡\(nk,rk,xk​\(S,τ\)\)=\(nk−xk​\(S,τ\)rk\)\(nkrk\)h\_\{k\}:=h\\bigl\(n\_\{k\},r\_\{k\},x\_\{k\}\(S,\\tau\)\\bigr\)=\\frac\{\\binom\{n\_\{k\}\-x\_\{k\}\(S,\\tau\)\}\{r\_\{k\}\}\}\{\\binom\{n\_\{k\}\}\{r\_\{k\}\}\}\(48\)is the probability that subgraphkkretains none of them\. Independence across subgraphs gives

Pr⁡\(no retained​τ​\-qualified crossing of​S∣π\(t\)\)=∏k=0Khk\.∎\\boxed\{\\Pr\\bigl\(\\text\{no retained \}\\tau\\text\{\-qualified crossing of \}S\\mid\\pi^\{\(t\)\}\\bigr\)=\\prod\_\{k=0\}^\{K\}h\_\{k\}\.\}\\qed\(49\)

A vertex is isolated exactly when its singleton cut is empty, soS=\{v\}S=\\\{v\\\}withτ\\taubelow every score gives its isolation probability\. An isolated vertex receives no neighbor messages that epoch, so this same identity also bounds how often a node’s aggregation degenerates to its own features alone\. These identities bound retention at each cut individually rather than the joint event of every cut retaining an edge, so connectivity of𝒢B\(t\)\\mathcal\{G\}\_\{B\}^\{\(t\)\}at a givenBBis a separate, cut\-by\-cut question\.

###### Corollary 12\(High\-score cut survival, restated\)\.

Under the same conditions,

Pr\(ℰB\(t\)∩δ𝒢\(S\)∩ℰ≥τ≠∅∣π\(t\)\)≥1−exp\(−∑k=0Kθkxk\(S,τ\)\)\.\\Pr\\bigl\(\\mathcal\{E\}\_\{B\}^\{\(t\)\}\\cap\\delta\_\{\\mathcal\{G\}\}\(S\)\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\\neq\\varnothing\\mid\\pi^\{\(t\)\}\\bigr\)\\geq 1\-\\exp\\Bigl\(\-\\textstyle\\sum\_\{k=0\}^\{K\}\\theta\_\{k\}x\_\{k\}\(S,\\tau\)\\Bigr\)\.\(50\)

###### Proof of Corollary[12](https://arxiv.org/html/2610.09059#Thmtheorem12)\.

Forn=0n=0orr=0r=0the factor and its exponential bound are one\. Forn\>0n\>0andr\>n−xr\>n\-x,h⁡\(n,r,x\)=0h\(n,r,x\)=0and the bound is immediate\. Otherwise0≤r≤n−x0\\leq r\\leq n\-xand

h⁡\(n,r,x\)=\(n−xr\)\(nr\)=∏i=0r−1n−x−in−i\.h\(n,r,x\)=\\frac\{\\binom\{n\-x\}\{r\}\}\{\\binom\{n\}\{r\}\}=\\prod\_\{i=0\}^\{r\-1\}\\frac\{n\-x\-i\}\{n\-i\}\.\(51\)Sincen−x−in−i≤1−xn\\frac\{n\-x\-i\}\{n\-i\}\\leq 1\-\\frac\{x\}\{n\}for0≤i<n0\\leq i<n,

h\(n,r,x\)≤\(1−xn\)r≤e−rx/n\.h\(n,r,x\)\\leq\\Bigl\(1\-\\frac\{x\}\{n\}\\Bigr\)^\{r\}\\leq e^\{\-rx/n\}\.\(52\)Hence

∏k=0Khk≤exp\(−∑k=0Kθkxk\(S,τ\)\),\\prod\_\{k=0\}^\{K\}h\_\{k\}\\leq\\exp\\Bigl\(\-\\sum\_\{k=0\}^\{K\}\\theta\_\{k\}x\_\{k\}\(S,\\tau\)\\Bigr\),\(53\)and complementing \([49](https://arxiv.org/html/2610.09059#A5.E49)\),

Pr\(∃retained edge crossingSwithse≥τ∣π\(t\)\)≥1−exp\(−∑k=0Kθkxk\(S,τ\)\)\.∎\\boxed\{\\Pr\\bigl\(\\exists\\text\{ retained edge crossing \}S\\text\{ with \}s\_\{e\}\\geq\\tau\\mid\\pi^\{\(t\)\}\\bigr\)\\ \\geq\\ 1\-\\exp\\Bigl\(\-\\sum\_\{k=0\}^\{K\}\\theta\_\{k\}x\_\{k\}\(S,\\tau\)\\Bigr\)\.\}\\qed\(54\)

Writingμ=∑k=0Kθk​xk​\(S,τ\)\\mu=\\sum\_\{k=0\}^\{K\}\\theta\_\{k\}x\_\{k\}\(S,\\tau\), the bound gives conditional survival probability at least1−δ1\-\\deltawhenμ≥log⁡\(1/δ\)\\mu\\geq\\log\(1/\\delta\), for0<δ<10<\\delta<1\. It is weak for smallμ\\muand equals zero whenμ=0\\mu=0\. This is a fixed\-cut statement, not a simultaneous connectivity or path\-survival guarantee\.

### E\.6Optional Composition Variants

Two theory\-driven variants extend the composition step\. Both are analyzed here as additional theoretical guarantees available within the framework, alongside rather than in place of the main experiments\.

#### Certificate\-core composition\.

Under the maximum\-score residual\-forest assumptions, setU0=∅U\_\{0\}=\\varnothing\. For edge\-budgetBBletq⁡\(B\)=max⁡\{q∈\{0,…,K\}:\|Uq\|≤B\}q\(B\)=\\max\\\{q\\in\\\{0,\\ldots,K\\\}:\|U\_\{q\}\|\\leq B\\\}and always retain the prefixUq⁡\(B\)U\_\{q\(B\)\}, filling the remainingB−\|Uq⁡\(B\)\|B\-\|U\_\{q\(B\)\}\|edges stochastically without replacement fromℰ∖Uq⁡\(B\)\\mathcal\{E\}\\setminus U\_\{q\(B\)\}\. SinceℰB\(t\)⊇Uq⁡\(B\)\\mathcal\{E\}\_\{B\}^\{\(t\)\}\\supseteq U\_\{q\(B\)\}andδA​\(S\)\\delta\_\{A\}\(S\)is monotone inAA, Fact[2](https://arxiv.org/html/2610.09059#Thmfact2)and Theorem[1](https://arxiv.org/html/2610.09059#Thmtheorem1)give every epoch graph the deterministic guarantees

\|δℰB\(t\)\(S\)\|≥min\{q\(B\),\|δ𝒢\(S\)\|\},\|δℰB\(t\)\(S\)∩ℰ≥τ\|≥min\{q\(B\),\|δ𝒢≥τ\(S\)\|\}\.\\boxed\{\|\\delta\_\{\\mathcal\{E\}\_\{B\}^\{\(t\)\}\}\(S\)\|\\geq\\min\\\{q\(B\),\|\\delta\_\{\\mathcal\{G\}\}\(S\)\|\\\},\\qquad\|\\delta\_\{\\mathcal\{E\}\_\{B\}^\{\(t\)\}\}\(S\)\\cap\\mathcal\{E\}\_\{\\geq\\tau\}\|\\geq\\min\\\{q\(B\),\|\\delta\_\{\\mathcal\{G\}\_\{\\geq\\tau\}\}\(S\)\|\\\}\.\}\(55\)
This trades cross\-epoch variability for a deterministic per\-epoch certificate\.

###### Proposition 13\(Average\-score trimming is expectation\-optimal\)\.

Fix available nonempty subgraphs indexed bykk, lets¯k=s⁡\(ℰk\)/nk\\bar\{s\}\_\{k\}=s\(\\mathcal\{E\}\_\{k\}\)/n\_\{k\}, and let0≤B≤∑knk0\\leq B\\leq\\sum\_\{k\}n\_\{k\}be an integer\. Among allocationsrk∈\{0,…,nk\}r\_\{k\}\\in\\\{0,\\ldots,n\_\{k\}\\\}with∑krk=B\\sum\_\{k\}r\_\{k\}=B, uniform within\-subgraph retention maximizes𝔼⁡\[∑ks⁡\(ℰ~k\)\]=∑krk​s¯k\\mathbb\{E\}\\bigl\[\\sum\_\{k\}s\(\\widetilde\{\\mathcal\{E\}\}\_\{k\}\)\\bigr\]=\\sum\_\{k\}r\_\{k\}\\bar\{s\}\_\{k\}by filling subgraphs in decreasing order ofs¯k\\bar\{s\}\_\{k\}, with at most one subgraph partially filled\. Other allocations can tie when subgraphs have equal average score\. The main method instead trims by cached total weightwkw\_\{k\}rather than this expectation\-optimal average\-score rule\. Thatwkw\_\{k\}\-based greedy fill is equally deterministic in its own retained counts given fixed tie\-breaking, though uniform sampling within the one partially filled subgraph can still vary which edges are kept\. This score\-optimality statement does not establish an accuracy\-optimal allocation\. The main method’s weighted ordering and total\-weight trimming are evaluated through the empirical ablations\.

###### Proof\.

Uniform retention gives𝔼⁡\[s⁡\(ℰ~k\)\]=rk​s¯k\\mathbb\{E\}\[s\(\\widetilde\{\\mathcal\{E\}\}\_\{k\}\)\]=r\_\{k\}\\bar\{s\}\_\{k\}, so∑krk​s¯k\\sum\_\{k\}r\_\{k\}\\bar\{s\}\_\{k\}is linear in\(rk\)k\(r\_\{k\}\)\_\{k\}subject to0≤rk≤nk0\\leq r\_\{k\}\\leq n\_\{k\}and∑krk=B\\sum\_\{k\}r\_\{k\}=B\. If an optimum hasra<nar\_\{a\}<n\_\{a\},rb\>0r\_\{b\}\>0, ands¯a\>s¯b\\bar\{s\}\_\{a\}\>\\bar\{s\}\_\{b\}, moving one unit frombbtoaachanges the objective bys¯a−s¯b\>0\\bar\{s\}\_\{a\}\-\\bar\{s\}\_\{b\}\>0, contradicting optimality\. Hence

an optimum fills subgraphs in decreasing​s¯k​order, at most one subgraph split\.∎\\boxed\{\\text\{an optimum fills subgraphs in decreasing \}\\bar\{s\}\_\{k\}\\text\{ order, at most one subgraph split\.\}\}\\qed\(56\)

The results establish exact\-budget reuse for any cached partition and deterministic cut and score\-qualified path certificates for maximum\-score forest prefixes\. They also characterize conditional edge retention and fixed\-cut survival under stochastic composition\. The last property does not transfer the full prefix certificates to every epoch graph\. The optional certificate\-core variant retains a prefix chosen according toBBand therefore inherits its deterministic cut guarantees\.

These combinatorial results describe available graph connections without assuming a particular GNN or loss\. The benchmark ablations provide complementary evidence for predictive utility\. Atρ=0\.3\\rho=0\.3, the reported means favorEDiS\-Lite over Frozen on 13 of 14 datasets, Direct on 11, and Shuffled groups on 12 \(Table\)\. This supports the practical contribution of decomposition and resampling in the tested settings, while leaving open how much of the gain is specifically attributable to the cut and path certificates rather than other changes in the induced sampling distribution\.

## Appendix FSelectors and Computational Cost

### F\.1Family of Residual Selectors

Each of the seven selectors below implements the same residual\-selector interfaceℱ\\mathcal\{F\}from a residual graphHHand its fixed edge scoresss, so any one of them can be dropped intoEDiSwithout changing anything else in the pipeline\. What differs is only how each one decides which edges to keep, and consequently its round costTi​\(n,mi\)T\_\{i\}\(n,m\_\{i\}\), explained selector by selector below and summarized in Table[5](https://arxiv.org/html/2610.09059#A6.T5)at the end of this appendix\.

#### Maximum/minimum covering forest\(maxst/minst,MaxCF/MinCFin Section[4](https://arxiv.org/html/2610.09059#S4)\)\.

The implementation namesmaxst/minstreflect that each round’s forest spans every component of the current residual graph\. We call it a*covering forest*instead because that spanning property holds only within one round, not for the budget\-limited graph actually composed for training \(Section[3\.4](https://arxiv.org/html/2610.09059#S3.SS4)\)\. This selector puts every remaining edge in order by score, either strongest first or weakest first, and adds edges one at a time down that list, skipping any edge that would close a loop back to nodes already connected\. This is Kruskal’s algorithm\([Kruskal, 1956](https://arxiv.org/html/2610.09059#bib.bib34);[Edmonds, 1971](https://arxiv.org/html/2610.09059#bib.bib35)\)run on our scores instead of raw edge weights, with ties kept in their original order\. Because it only adds loop\-free edges, it ends up touching every part of the residual graph\.maxstandminstdiffer only in which direction we sort\. Each round sorts the remaining edges and tracks which nodes are already connected, costing a little more than one plain scan\.

#### kk\-nearest neighbor\(knn\)\.

This selector lets every node claim itskkbest\-scoring remaining edges, or all of them if fewer thankkare left, and keeps the union of every node’s claims\. Asking for a fixed totalMMinstead of a fixedkktrims or tops up that union by score until it hitsMMexactly, which can take away an edge a node had already claimed, so no node is guaranteed to keep its own top choices\. This touches each remaining edge from both ends\.

#### Graph spanner\(spanner\)\.

This selector works on each disconnected piece of the residual graph on its own, building a smaller subgraph using edge lengths that shrink as the score grows, so the best\-scoring edges look shortest\. The result must keep every pair of nodes within a stretch factorα\\alphaof their true distance in these lengths\([Peleg and Schäffer, 1989](https://arxiv.org/html/2610.09059#bib.bib39)\), a bound on path length rather than hop count\. Construction is randomized, and its cost depends on the spanner routine used\.

#### Degree\-normalized\(degree\_norm\)\.

This selector draws a set numberMMof edges at random without repeats, weighting each edgeu​vuvbywu​v=1/dH​\(u\)\+1/dH​\(v\)w\_\{uv\}=1/d\_\{H\}\(u\)\+1/d\_\{H\}\(v\)so edges touching low\-degree nodes are more likely to be picked, recomputing degrees every round\. It ignores the score entirely and guarantees neither connectivity nor a minimum degree\. One pass over the edges is enough to compute the weights\.

#### Random\(random\)\.

This selector shuffles the remaining edges uniformly at random and keeps the firstMM\. Ignoring both score and structure, it serves as the score\-free baseline the others are compared against, and needs only one pass over the edges\.

#### Scheduled\(Hybrid\)\.

A schedule chains several selectors together, using a different one each round on whatever edges remain, and repeating the last one once the list runs out\. Any of the five selectors above can appear, in any order, and can repeat, so this is a general way to combine selectors rather than one fixed recipe\. The schedule used in our experiments runsmaxst, thenknn, thendegree\_normfor every later round, first extracting a connectivity\-preserving backbone, then giving each node its own best local edges, then spreading coverage to whichever nodes are still thin\. It stops under the same conditions as the other selectors\.

#### Selectors outside this family\.

Effective\-resistance sampling\([Spielman and Srivastava, 2008](https://arxiv.org/html/2610.09059#bib.bib22)\)needs spectral information recomputed as the residual changes\. Forest\-fire sampling\([Leskovec and Faloutsos, 2006](https://arxiv.org/html/2610.09059#bib.bib19)\), SCAN\([Xu et al\., 2007](https://arxiv.org/html/2610.09059#bib.bib21)\), and rank\-degree sampling\([Voudigari et al\., 2016](https://arxiv.org/html/2610.09059#bib.bib17)\)likewise need traversal, clustering, or ranking steps beyond a residual degree pass\. None of these are implemented here as candidate selectors insideEDiS’s own construction, though several are compared againstEDiSdirectly as full competing methods in Section[4](https://arxiv.org/html/2610.09059#S4)\.

### F\.2Cost of Construction and Epoch Composition

We now analyze whereEDiS’s computational cost is spent, writingn=\|𝒱\|n=\|\\mathcal\{V\}\|,m=\|ℰ\|m=\|\\mathcal\{E\}\|, andd0d\_\{0\}for the input feature dimension\. Every edge is scored once, before construction begins, at a cost ofTscore=O⁡\(m​d0\)T\_\{\\mathrm\{score\}\}=O\(md\_\{0\}\), and this cost cannot be skipped even by a score\-free selector, since the same scores also determine subgraph importance\.

Building the decomposition runs the selector once per round over whatever edges remain, so its total cost is just the sum of each round’s selector cost and residual bookkeeping\. For the repeated\-sortingmaxstconstruction, writingmim\_\{i\}for the residual edge count at roundii, this gives

Tconstruct=O⁡\(K​n\+∑i=1Kmi​log⁡\(mi\+1\)\)⊆O⁡\(K​n\+K​m​log⁡\(m\+1\)\)\.T\_\{\\mathrm\{construct\}\}=O\\\!\\left\(Kn\+\\sum\_\{i=1\}^\{K\}m\_\{i\}\\log\(m\_\{i\}\+1\)\\right\)\\subseteq O\\\!\\left\(Kn\+Km\\log\(m\+1\)\\right\)\.The dependence onKKcan be absorbed only when the round cap is treated as a fixed constant\. Fixed scores also permit implementations that reuse an initial ordering\. Storing the resulting subgraphs and the residual adds onlyO⁡\(m\+K\)O\(m\+K\)extra space, on top of the graph itself and its features\.

Composition reuses the partition and scores without repeating extraction\. An implementation can determine retained counts from cached group sizes before materializing edges\. With anO⁡\(K​log⁡\(K\+1\)\)O\(K\\log\(K\+1\)\)weighted ordering and trimming\-order sort, random\-access pools, and uniform subset sampling in time proportional to the returned subset size, this yieldsO⁡\(K​log⁡\(K\+1\)\+B\)O\(K\\log\(K\+1\)\+B\)composition time\. This is an implementation\-dependent bound\. Copying entire candidate pools or generating full\-pool permutations can introduce additional cost depending on their sizes, up tomm\. Expanding the chosen edges into their reciprocal directed pairs for message passing adds a furtherTreciprocal=O⁡\(B\)T\_\{\\mathrm\{reciprocal\}\}=O\(B\)per epoch\.

Summing over allTTtraining epochs, the total cost of a job is the one\-time scoring and construction cost plus the per\-epoch composition, reciprocal\-expansion, training, transfer, and validation costs added up across epochs,

Tjob=Tscore\+Tconstruct\+∑t=1T\(Tcompose\(t\)\+Treciprocal\(t\)\+Ttrain\(t\)\+Ttransfer\(t\)\+Tval\(t\)\)\.T\_\{\\mathrm\{job\}\}=T\_\{\\mathrm\{score\}\}\+T\_\{\\mathrm\{construct\}\}\+\\sum\_\{t=1\}^\{T\}\\Bigl\(T\_\{\\mathrm\{compose\}\}^\{\(t\)\}\+T\_\{\\mathrm\{reciprocal\}\}^\{\(t\)\}\+T\_\{\\mathrm\{train\}\}^\{\(t\)\}\+T\_\{\\mathrm\{transfer\}\}^\{\(t\)\}\+T\_\{\\mathrm\{val\}\}^\{\(t\)\}\\Bigr\)\.Full\-graph validation and test inference, where used, process the original graph𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\)instead of a composed one, so their cost depends on\(n,m\)\(n,m\)rather thanBB, and is charged separately from training\. The headline point is that scoring and construction are paid only once, while composition and reciprocal expansion recur every epoch\. Budget\-proportional edge materialization is possible under the implementation conditions above\. Measured runtime is reported separately in Appendix\.

SelectorRound costTi​\(n,mi\)T\_\{i\}\(n,m\_\{i\}\)Structural guaranteemaxst/minstO⁡\(n\+mi​log⁡\(mi\+1\)\)O\(n\+m\_\{i\}\\log\(m\_\{i\}\+1\)\)covering forest of every componentknnO⁡\(mi​log⁡\(mi\+1\)\)O\(m\_\{i\}\\log\(m\_\{i\}\+1\)\)top\-kkper node, unless trimmed to hitMMspannerdepends on the spanner routine useddistance stretch at mostα\\alphadegree\_normO⁡\(mi\)O\(m\_\{i\}\)nonerandomO⁡\(mi\)O\(m\_\{i\}\)noneHybridcost of whichever selector is active that roundinherits from the active selector
Table 5:Round cost and structural guarantee of each residual selector from Section[F\.1](https://arxiv.org/html/2610.09059#A6.SS1)\.

## Appendix GExperimental Details

### G\.1Dataset

The experiments use 19 node\-classification benchmarks, spanning six heterophilic small/medium graphs, eight homophilic small/medium graphs, and five large\-scale graphs \(Table[6](https://arxiv.org/html/2610.09059#A7.T6)\)\. Node and edge counts, and average degree, are computed after treating each graph as undirected and removing self\-loops\. Adjusted homophily measures how often connected nodes share a class after correcting for class proportions\([Platonov et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib37)\)\. Classes/Tasks reports the number of prediction classes for every dataset except ogbn\-proteins, a multi\-label dataset with 112 binary prediction tasks, and Features gives the input feature dimension\. Most datasets are evaluated with accuracy\. Minesweeper, Questions, and ogbn\-proteins use AUC instead, since their prediction tasks are binary\.

Graph sizeStructurePrediction taskDatasetNodesEdgesAvg\. degreeAdj\. homophilyClasses/TasksFeaturesMetricHeterophilic small/medium\([Platonov et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib37)\)Squirrel2\.22K47\.00K42\.280\.0152\.09KAccChameleon8908\.85K19\.900\.0352\.33KAccRoman\-Empire22\.66K32\.93K2\.91\-0\.0518300AccAmazon\-Ratings24\.49K93\.05K7\.600\.145300AccMinesweeper10\.00K39\.40K7\.880\.0127AUCQuestions48\.92K153\.54K6\.280\.022301AUCHomophilic small/mediumCora\([Yang et al\., 2016](https://arxiv.org/html/2610.09059#bib.bib7)\)2\.71K5\.28K3\.900\.7771\.43KAccCiteSeer\([Yang et al\., 2016](https://arxiv.org/html/2610.09059#bib.bib7)\)3\.33K4\.55K2\.740\.6763\.70KAccPubMed\([Yang et al\., 2016](https://arxiv.org/html/2610.09059#bib.bib7)\)19\.72K44\.32K4\.500\.693500AccAmazon\-Computer\([Shchur et al\., 2018](https://arxiv.org/html/2610.09059#bib.bib26)\)13\.75K245\.86K35\.760\.6810767AccAmazon\-Photo\([Shchur et al\., 2018](https://arxiv.org/html/2610.09059#bib.bib26)\)7\.65K119\.08K31\.130\.798745AccCoauthor\-CS\([Shchur et al\., 2018](https://arxiv.org/html/2610.09059#bib.bib26)\)18\.33K81\.89K8\.930\.78156\.81KAccCoauthor\-Physics\([Shchur et al\., 2018](https://arxiv.org/html/2610.09059#bib.bib26)\)34\.49K247\.96K14\.380\.8758\.42KAccWikiCS\([Mernyei and Cangea, 2020](https://arxiv.org/html/2610.09059#bib.bib36)\)11\.70K215\.60K36\.850\.5810300AccLarge\-scaleogbn\-arxiv\([Hu et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib8)\)169\.34K1\.17M13\.770\.4240128Accogbn\-proteins\([Hu et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib8)\)132\.53K39\.56M597\.000\.051128AUCogbn\-products\([Hu et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib8)\)2\.45M61\.86M50\.520\.4647100AccPokec\([Lim et al\., 2021](https://arxiv.org/html/2610.09059#bib.bib38)\)1\.63M22\.30M27\.320\.42265AccReddit\([Hamilton et al\., 2017](https://arxiv.org/html/2610.09059#bib.bib2)\)232\.97K57\.31M492\.000\.7441602Acc

Table 6:Dataset statistics for the 19 node\-classification benchmarks used in the current experiments\.
### G\.2Baseline Settings

We compareEDiSagainst baselines drawn from three families, grouped by the structural signal each relies on rather than by implementation detail\. Anchors bound the comparison without adapting to the graph, and comprise a feature\-only MLP \(No Graph\), a Spanning Tree, and Full Graph with the same tuned GNN configuration\([Luo et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib27)\)\. Semantic baselines learn which edges to keep jointly with the GNN parameters, and comprise Unified\-LTH\([Chen et al\., 2021](https://arxiv.org/html/2610.09059#bib.bib14)\), AdaGLT\([Zhang et al\., 2024](https://arxiv.org/html/2610.09059#bib.bib24)\), and MoG\([Zhang et al\., 2025](https://arxiv.org/html/2610.09059#bib.bib25)\)\. Topological baselines score edges directly from the graph, independent of the downstream task, and comprise Random, Local Degree\([Hamann et al\., 2016](https://arxiv.org/html/2610.09059#bib.bib18)\), Rank Degree\([Voudigari et al\., 2016](https://arxiv.org/html/2610.09059#bib.bib17)\), Forest Fire\([Leskovec and Faloutsos, 2006](https://arxiv.org/html/2610.09059#bib.bib19)\), SCAN\([Xu et al\., 2007](https://arxiv.org/html/2610.09059#bib.bib21)\), L\-Spar and G\-Spar\([Satuluri et al\., 2011](https://arxiv.org/html/2610.09059#bib.bib20)\), L\-Sim\([Chen et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib16)\), Spectral \(ER\)\([Spielman and Srivastava, 2008](https://arxiv.org/html/2610.09059#bib.bib22)\),tt\-Spanner\([Peleg and Schäffer, 1989](https://arxiv.org/html/2610.09059#bib.bib39)\), and DSpar\([Liu et al\., 2023](https://arxiv.org/html/2610.09059#bib.bib23)\)\.

Sampling\-based related methods\.Neighborhood\- and subgraph\-sampling methods such as GraphSAGE\([Hamilton et al\., 2017](https://arxiv.org/html/2610.09059#bib.bib2)\), GraphSAINT\([Zeng et al\., 2020](https://arxiv.org/html/2610.09059#bib.bib6)\), and Cluster\-GCN\([Chiang et al\., 2019](https://arxiv.org/html/2610.09059#bib.bib5)\)control a different resource, the minibatch or neighborhood size used for scalability, rather than a global edge\-retention budget\. They are therefore not part of the matched\-edge\-budget comparison, and GraphSAGE appears only as the alternate backbone in RQ7\.

### G\.3Propagation and Evaluation Settings

For full\-batch GCN training, we add each retained undirected edge in both directions\. We add one self\-loop per node\. The edge\-budgetBBcounts only the undirected non\-loop edges\. All layers use the same epoch graph, with normalized adjacency𝐀^\(t\)=\(𝐃~\(t\)\)−1/2\(𝐀\(t\)\+𝐈\)\(𝐃~\(t\)\)−1/2\\hat\{\\mathbf\{A\}\}^\{\(t\)\}=\(\\tilde\{\\mathbf\{D\}\}^\{\(t\)\}\)^\{\-1/2\}\(\\mathbf\{A\}^\{\(t\)\}\+\\mathbf\{I\}\)\(\\tilde\{\\mathbf\{D\}\}^\{\(t\)\}\)^\{\-1/2\}\. Here𝐃~\(t\)\\tilde\{\\mathbf\{D\}\}^\{\(t\)\}holds the degrees of𝐀\(t\)\+𝐈\\mathbf\{A\}^\{\(t\)\}\+\\mathbf\{I\}\. We recompute normalization for the current topology\. Edge scores guide selection\. They are not propagation weights\. The architecture and training objective stay the same\.

### G\.4Hyperparameter Settings

Every baseline and sparsifier method uses the same per\-dataset training setup for a given backbone\. This keeps accuracy differences tied to the sparsification method, not the training setup\. Per\-dataset settings follow the defaults of[Luo et al\. \(2024\)](https://arxiv.org/html/2610.09059#bib.bib27)for every dataset except Reddit, which that work does not include\. We use two backbones\. GCN is the default for every method\. GraphSAGE is used only by Full GraphSAGE andEDiS\-GraphSAGE\. In both tables below,LLis the number of GNN layers,HHis the hidden dimension, LR is the learning rate, and WD is the weight decay\.

#### KmaxK\_\{\\max\}\.

The round capKmaxK\_\{\\max\}on subgraph extraction is itself a hyperparameter, chosen per dataset rather than fixed globally, and applied the same way regardless of backbone\. Every small\- and medium\-scale dataset, homophilic or heterophilic, usesKmax=10K\_\{\\max\}=10\. The five large\-scale graphs instead useKmax=80K\_\{\\max\}=80for Pokec,Kmax=40K\_\{\\max\}=40for ogbn\-arxiv,Kmax=20K\_\{\\max\}=20for Reddit, andKmax=10K\_\{\\max\}=10for ogbn\-products and ogbn\-proteins\. These are the same values used throughout the main experiments and the extended ablations, where Section[4](https://arxiv.org/html/2610.09059#S4)\(RQ6\) and Appendixstudy how sensitive results are to this choice\.

#### MLP edge score\.

The learned score used in the edge\-score ablation \(Section[4](https://arxiv.org/html/2610.09059#S4)RQ5, Appendix\) trains a small MLP on the concatenated features of each edge’s two endpoints to predict an edge score\. Training uses only edges whose two endpoints both carry a training label, with target 1 if the endpoints share a label and 0 otherwise, and an equal number of same\-label and different\-label edges sampled per batch\. PubMed’s semi\-supervised split labels too few training nodes to assemble this balanced sample, so the MLP score is marked N/A for PubMed throughout\.

ProtocolArchitectureOptimizationEvaluationDatasetEpochsRunsLLHHNorm\./Res\.DropoutLRWDMetricHeterophilic small/mediumSquirrel500104256bn, res0\.701e\-25e\-4AccChameleon200105512–0\.205e\-31e\-3AccRoman\-Empire250039512bn, res0\.501e\-30AccAmazon\-Ratings250034512bn, res0\.501e\-30AccMinesweeper200031264bn, res0\.201e\-20AUCQuestions1500310512res0\.303e\-50AUCHomophilic small/mediumCora50053512–0\.701e\-35e\-4AccCiteSeer50052512–0\.501e\-31e\-2AccPubMed50052256–0\.705e\-35e\-4AccAmazon\-Computer100033512ln0\.501e\-35e\-5AccAmazon\-Photo100036256ln, res0\.501e\-35e\-5AccCoauthor\-CS150032512ln, res0\.301e\-35e\-4AccCoauthor\-Physics15003264ln, res0\.301e\-35e\-4AccWikiCS100033256ln0\.501e\-30AccLarge\-scaleogbn\-arxiv200025512bn, res0\.505e\-45e\-4Accogbn\-proteins1002380–0\.251e\-20AUCogbn\-products30025200ln0\.503e\-30AccPokec200027256bn, res0\.205e\-40AccReddit30025200ln0\.503e\-30Acc

Table 7:Per\-dataset training configuration for the GCN backbone\.ProtocolArchitectureOptimizationEvaluationDatasetEpochsRunsLLHHNorm\./Res\.DropoutLRWDMetricHeterophilic small/mediumSquirrel500103256bn, res0\.701e\-2–AccChameleon200104256bn, res0\.701e\-2–AccRoman\-Empire250039256bn0\.301e\-3–AccAmazon\-Ratings250039512bn, res0\.501e\-3–AccMinesweeper200031564bn, res0\.201e\-2–AUCQuestions150036512ln0\.201e\-3–AUCHomophilic small/mediumCora50053256–0\.701e\-3–AccCiteSeer50053512–0\.201e\-3–AccPubMed50054512–0\.705e\-3–AccAmazon\-Computer10003464ln0\.301e\-3–AccAmazon\-Photo10003664ln, res0\.201e\-3–AccCoauthor\-CS150032512ln, res0\.501e\-3–AccCoauthor\-Physics15003264bn, res0\.701e\-3–AccWikiCS100032256ln0\.701e\-3–AccLarge\-scaleogbn\-arxiv200024256bn, res0\.505e\-4–Accogbn\-proteins100026512bn, res0\.301e\-2–AUCogbn\-products100025256ln0\.503e\-3–AccPokec200027256bn, res0\.205e\-4–AccReddit30025200ln0\.503e\-3–Acc

Table 8:Per\-dataset training configuration for the GraphSAGE backbone\.

### G\.5Complete numerical results

Tables–report full results \(mean±\\pmstandard deviation\) on the homophilic, heterophilic, and large\-scale datasets\.