acceptodds
Under review as a conference paper at ICLR 2027

EDIS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks

Abstract

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

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Graph Sparsification, Graph Sampling, Dynamic Graph Sampling, Edge-Disjoint Decomposition, Efficient GNN Training

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_FMpAOpenReview ↗
Rating
3(+1)
Confidence
2(−1)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

EDiS tackles a practical problem in sparse GNN training: a single fixed sparse graph can limit structural diversity, while rebuilding a new one every epoch can be expensive. The paper proposes to build a reusable, edge-disjoint library of subgraphs once, then compose an exact-budget training graph from that library each epoch by sampling, trimming, and filling edges. It gives a cut-preservation guarantee for the stored decomposition and a conditional edge-retention bound for the composed graphs. The evaluation spans 19 datasets and 17 baselines, with matched-budget experiments, ablations on decomposition and epoch-to-epoch variation, and comparisons across GNN backbones. Overall, the paper presents a clear and potentially useful way to reuse structural work while still exposing the model to changing sparse graphs.

Critical strengths
  1. The decomposition–composition split is a genuinely useful framing. What I like most is that EDiS treats the expensive structural library as a reusable object, rather than making sparsification a one-off preprocessing choice or rerunning a costly procedure every epoch. That makes the framework modular and gives it a plausible practical advantage when the same graph will be used for long training runs or multiple sparsity budgets.

  2. The paper makes a serious effort to connect theory to a broad empirical study. The two guarantees are scoped to different stages of the pipeline, which is a sensible way to reason about the method without claiming that every sampled graph has stronger properties than it actually does. The breadth of the evaluation, together with the ablations on frozen versus changing structures and the backbone comparisons, makes the paper more informative than a simple “our method gets higher accuracy” result.

Critical weaknesses
  1. The evidence does not fully isolate EDiS’s specific advantage, and one theorem–algorithm detail needs to be pinned down. The experiments are broad, but I do not see a clear, prominent comparison against per-epoch DropEdge or GraphSAINT under the same exact edge budget. That matters because the paper’s framing invites the question: is the gain coming from the cached edge-disjoint structure, or would generic epoch-wise resampling deliver much of it? Also, Theorem 2 seems to rely on uniform random trimming within a partially retained subgraph, while the method description is not fully explicit about the trimming rule. If the implementation uses a different rule, the theorem-to-algorithm connection needs more explanation. Finally, since efficiency is central to the paper’s motivation, the one-time construction cost and break-even point deserve a more prominent role; the reported Reddit example, where the Lite variant has not broken even at 300 epochs, makes that practical boundary important.

  2. Another big concern is whether the supplied code actually reproduces the paper’s stated method and headline experiments. The paper describes successive MaxCF decomposition as the default, while the inspected package’s default schedule appears to mix selectors (maxst → knn → degree_norm). The README documents a --config invocation, but the CLI parser does not appear to implement that option. There are also material setting differences: the paper gives dataset-specific decomposition depths that exceed the package’s default in some cases, and the OGBN-Proteins training preset differs from the paper’s reported hidden size, dropout, and number of runs. The ZIP also does not include the per-seed results needed to regenerate the main tables. I have not rerun training, so I am not claiming the reported numbers are wrong; the problem is that, from the supplied artifacts, I cannot confidently connect those numbers to the described pipeline. The included AGS budget-matching script also appears to round through a retention ratio, which can produce different integer edge counts—for example, 63 versus 64 edges on Karate. That weakens confidence in a comparison presented as budget-matched.

Questions for authors

I hope the authors can clarify these (which, I believe, should be addressed first):

  1. Which exact decomposition schedule and configuration produced the main tables: successive MaxCF at every step, or the mixed selector schedule in the supplied package? Could you point to the immutable code version, the resolved per-dataset configs, and the commands used to produce those results? In the same context, how should readers reconcile the paper’s Kmax settings and OGBN-Proteins hyperparameters with the supplied defaults?

  2. For a partially included subgraph, is trimming uniform at random, as Theorem 2 appears to require, or does the implementation use a score-based or other deterministic policy? If it is not uniform, how does the stated retention bound apply to the implemented procedure?

Also there are some points that could change my assessment (depends on authors' rebuttal):

  1. Were DropEdge or GraphSAINT evaluated with per-epoch resampling at the same integer edge budget as EDiS? If so, could you report those results and clarify the protocol; if not, what prevented a matched-budget comparison?

  2. Could you provide the per-seed outputs and the exact integer edge counts for the main results, along with preprocessing, per-epoch composition, training, and memory costs? In particular, what is the break-even point on representative small, medium, and large datasets?

5 comments

We thank the reviewer for the feedback.

W1 / Q2.1: Evidence and comparison

We isolate EDiS’s advantages through component ablations (Tables 17–23), standalone sparsifiers (Tables 9–11), and selector evaluations (Fig. 5).

We compare DropEdge and SAINT-RW/Edge under identical GNN settings, demonstrating benefits beyond generic epoch-wise resampling.

Table R1. Accuracy at ρ=0.3\rho=0.3.

DatasetDropEdgeSAINT-RWSAINT-EdgeEDiS-LiteEDiS-Full
WikiCS77.21±0.6177.07±0.3179.30±0.3380.21±0.6980.39±0.29
Roman-Empire68.75±0.4769.15±0.8667.77±0.1769.72±0.5274.90±0.43
ogbn-arxiv67.99±0.4764.66±0.3470.82±0.3971.03±0.2473.20±0.55
Reddit94.39±0.0594.40±0.1195.20±0.0295.61±0.0495.08±0.03

Theorem–algorithm: Theorem 1 (§3.4) concerns MaxCF extraction (§3.2), while Theorem 2 (§3.4) concerns uniform trimming during composition (§3.3, Appendix C.5). We will clarify these connections.

W1 / Q1.2: Trimming and Theorem 2

Our paper and implementation use uniform random trimming. Composition removes lower-priority subgraphs, uniformly trims at most one partial subgraph, or uniformly fills shortfalls from residual edges. This satisfies Theorem 2's assumptions.

W1 / Q2.2: Preprocessing, memory, and break-even

We report serial and parallel MaxCF decomposition times.

Table R2. Preprocessing scalability. Time (s), AMD EPYC 9334, median of 5 runs.

DatasetSerialp=2p=8p=16
Pokec67.233.223.121.3
ogbn-products198.393.454.635.9
Reddit393.9132.498.266.5

Table R3 reports break-even epochs including preprocessing and training costs. With scalable preprocessing (p=16), EDiS breaks even on Reddit within 90 epochs at ρ=0.3\rho=0.3, reducing peak GPU memory from 25.5 to 13.8 GB. Break-even can be high on smaller graphs like Cora. Component timings, memory, and exact edge counts are available in rebuttal evidence.

Table R3. Break-even at ρ=0.3\rho=0.3 (H100, 16 CPU, seconds).

ScaleDatasetBuildFull/epochEDiS/epochBreak-even
SmallCora (Full)0.010.00250.0025Never
MediumCoauthor-Physics (Lite)1.30.00850.00771,478
LargeReddit (Lite)450.8050.30590
Largeogbn-products (Lite)261.6120.84435

W2.1 / Q1.1: Reproducibility and experimental settings

  • We provide YAML configurations to reproduce results. For Cora:

    1. EDiS-Lite: python main.py run --config configs/paper/gcn/cora.yaml

    2. EDiS-Full: python main.py run --config configs/paper/gcn/cora_full.yaml

  • Experiments spanned multiple development stages with dataset- and variant-specific configurations, so results do not originate from one historical code revision. For verification, we provide representative per-seed logs, original-run records, resolved configurations, reproduction commands, exact edge-budget checks, and efficiency measurements in rebuttal evidence.

Reproducible examples for verification:

DatasetEDiS-LiteEDiS-Full
Cora76.96±1.2883.98±0.52
Squirrel41.83±1.4842.86±1.99
  • Successive MaxCF is the primary decomposition strategy in main experiments. Hybrid was evaluated separately (Table 17) but set as the script default.

  • Dataset/variant configurations override generic Kmax and training defaults (Table 7). For ogbn-proteins, runs used 512 hidden units, 0.3 dropout, batch normalization, residual connections, and three seeds, matching the released configuration. We will revise Table 7.

W2.2: AGS integer-budget verification

We did not use AGS's rounding utility. We enforce the budget directly, avoiding the Karate 63/64-edge mismatch. We compare AGS-GS-Disjoint with a tuned GCN at ρ=0.3\rho=0.3.

Table R5. Test accuracy; sparse/full inference.

DatasetAGS sparseEDiS-LiteAGS fullEDiS-Full
Cora74.20±1.1077.16±0.9880.78±1.5684.08±0.83
PubMed75.68±0.9177.28±0.5779.48±0.8180.20±0.46
Squirrel41.72±1.8442.63±2.0442.54±2.0743.26±2.43

Q2.2: Per-seed outputs/edge count

Rebuttal evidence provides available per-seed outputs and exact integer edge counts for the main results.

Thanks for the additional results and clarifications.

On the code side, I can't run the experiments at this point, and I don't have a saved copy of the package I originally inspected. The anonymous repository also seems to have been updated during rebuttal, so I can't reliably compare the two versions. I'll take the authors' explanation and fixes as given and won't pursue those code issues further.

The uniform-trimming clarification also answers that concern for me. There are still a few experimental points I'm unsure about, though.

What exactly is matched in R1?

The DropEdge and SAINT results are useful additions. My original question was specifically about the same exact integer edge budget per epoch. Could you confirm that this is what R1 uses? “Identical GNN settings” doesn't quite tell me how the sampling budget was handled. For SAINT, is each epoch using one graph with exactly the same number of edges as EDiS, or is it using minibatch sampling with multiple updates? Also, are the baseline scores measured with sparse-graph or full-graph inference? Since R1 includes both EDiS-Lite and EDiS-Full, I need that detail to understand which comparisons are actually like-for-like.

I'm still a bit confused by the new runtime numbers.

The Cora and Coauthor-Physics examples are helpful; they make the limits of the efficiency argument clearer. But I'm having trouble reconciling the Reddit numbers with the original paper:

RedditTable 16Rebuttal R3
Build time313.7 s45 s
Full-GCN (per epoch)about 2.38 s0.805 s
EDiS-Lite (per epoch)about 1.73 s0.305 s

I can see how R3 gives a 90-epoch break-even point. What I don't understand is why both per-epoch times changed so much as well. Both comparisons are labeled H100, and parallelizing decomposition alone wouldn't explain those changes. Did the model, implementation, graph representation, or timing scope change?

There is also a smaller mismatch within the rebuttal: R2 reports 66.5 s for Reddit decomposition with 16 workers, while R3 uses 45 s for the build. For Products, the corresponding numbers are 35.9 s and 26 s. Are these different setups, or are different parts of preprocessing being counted?

Finally, breaking even against Full-GCN answers part of my question. Since the argument also concerns avoiding repeated sampling work, a total-cost comparison against DropEdge or SAINT on a representative dataset would help establish that practical advantage.

One clarification on the Proteins settings.

I accept the correction to Table 7, but could you confirm that all methods in the main Proteins comparison used the same actual settings? The change from 80 to 512 hidden units, together with BN, residual connections, and a different number of seeds, is substantial enough that I want to be clear about this. Were those settings used consistently for EDiS and every baseline, with Table 7 simply reporting them incorrectly? If so, an explicit confirmation would address this concern.

We thank the reviewer for their thoughtful follow-up and the opportunity to clarify the experimental methodology and results. We address each concern below.

W1. Exact edge-budget matching and inference in R1

Yes. DropEdge, SAINT-RW, SAINT-Edge, and EDiS use the same integer edge budget B=min⁡(∣E∣,⌈ρ∣E∣⌉)B=\min(|E|,\lceil\rho|E|\rceil) per epoch, verified at runtime.

SAINT-RW starts random walks from randomly selected nodes and collects edges induced by visited nodes. If fewer than B edges are found, it continues sampling until at least B are available, then uniformly selects exactly B edges.

SAINT-Edge assigns each edge a weight of 1/(u)+1/(v) and samples exactly B distinct edges without replacement using these weights.

Both resample each epoch, matching EDiS's edge budget. All methods use the same GCN settings, normalization, seeds, and one full-batch update per epoch, rather than mini-batch training. All baselines use sparse-graph inference, making EDiS-Lite the direct comparison. EDiS-Full is included for reference.

Code verification:

W2. Runtime differences between Table 16 and R3

The model, graph, GCN settings, and decomposition bank are unchanged. The differences come from implementation and measurement conditions.

(a) Build time (313.7 to 45 s). Table 16 used serial Kruskal construction, while R3 used parallel extraction with 16 workers. The serial implementation takes 394–395 s on R2/R3 machines, compared with 66.5/44.8 s using 16 workers. This explains the preprocessing difference.

(b) EDiS-Lite (1.73 to 0.305 s/epoch). Table 16 used CPU graph composition, while R3 uses GPU composition. On the same R3 machine, CPU and GPU composition take 1.40 and 0.305 s/epoch, with nearly identical accuracy (95.61% and 95.63%). GPU residual sampling takes 0.013 s, while GCN training remains around 0.29–0.30 s. This confirms that graph composition accounts for most of the improvement.

(c) Full-GCN (2.38 to 0.805 s/epoch). The model and graph are unchanged. Table 16 was measured during shared-node experiments, while R3 used a dedicated H100 and excluded evaluation, which adds 0.375 s/epoch. A separate shared-node run took 5.75 s/epoch, confirming that GPU contention can substantially affect timing. We will clarify these conditions in the revision and update the values.

EDiS-Lite takes 73% of Full-GCN's epoch time in Table 16 and 38% in R3. These are comparisons within each measurement setting, not a direct speedup comparison between tables.

W3. Preprocessing difference between R2 and R3

Both measure the same steps with 16 workers and the same decomposition depth. R2 uses an AMD EPYC 9334 CPU node, while R3 uses the CPUs of an H100 node. This accounts for the different measurements.

  • Reddit: 66.5 s (R2) versus 45 s (R3).
  • ogbn-products: 35.9 s (R2) versus 26 s (R3).

The original R3 break-even points remain 90 epochs for Reddit and 35 for ogbn-products, using their respective R3 timings. We use the more conservative R2 build time in the additional total-cost comparison below.

W4. Total cost against DropEdge and SAINT

We measured total costs on Reddit at 0.3, using the same dedicated GPU and one method at a time. The totals cover 300 epochs, include sampling and training, and exclude evaluation. EDiS's total includes the conservative 66.5 s preprocessing cost (16 threads).

Methods/epochTotal (s)
EDiS-Lite0.305158
DropEdge0.30291
SAINT-Edge1.010303
SAINT-RW2.438731

Compared with the SAINT variants, EDiS recovers its preprocessing cost by epochs 95 (Edge) and 32 (RW). Against DropEdge, per-epoch costs are nearly identical. EDiS's advantage over DropEdge is accuracy (+1.22 percentage points), with some additional runtime cost. Against the evaluated SAINT variants, EDiS offers both higher accuracy and lower total cost on Reddit.

W5. Consistency of ogbn-proteins settings

Yes. All methods, including every sparsification baseline, Full-GCN, and both EDiS variants, used the same configuration of 3 GCN layers, 512 hidden units, 0.3 dropout, batch normalization, residual connections, and 3 seeds. Table 7 incorrectly reported these settings. Experiments used the configuration above, consistent with the shared per-dataset GNN settings in Table 1. We will correct Table 7.

Please let us know if you have any other concerns.

Reviewer_aGHJOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes EDiS, a graph sparsification framework that separates one-time structural decomposition from per-epoch graph composition. It caches edge-disjoint subgraphs and recombines them into training graphs containing exactly the requested number of edges. The default construction uses feature-based scores and successive maximum-score covering forests.

The analysis establishes score-threshold cut certificates for stored forest prefixes and separately characterizes conditional edge retention and fixed-cut survival after composition. Evaluation covers 19 node-classification benchmarks, with comparisons against sparsification baselines and ablations of epoch variation, structural grouping, selectors, scores, backbones, inference graphs, and computational cost.

Critical strengths
  1. A useful exact-budget framework with appropriately separated structural guarantees. EDiS supports multiple training budgets using one cached decomposition and accommodates different residual selectors. The distinction between deterministic certificates for stored prefixes and conditional guarantees for composed graphs is technically important: it makes clear which properties survive extraction and which require separate analysis after trimming and sampling.

  2. Substantial controlled evidence for structural grouping and epoch variation. The study includes 19 datasets and meaningful matched-budget controls. At 30% retention, EDiS has higher reported means than Frozen, Direct, and Shuffled groups on 13/14, 11/14, and 12/14 datasets, respectively. These comparisons provide useful evidence beyond aggregate baseline rankings. Additional inference and runtime analyses document practical tradeoffs and settings where construction costs are amortized.

Critical weaknesses
  1. The incremental contribution over the closest predecessor needs sharper positioning and validation. AGS-GS-Disjoint already constructs edge-disjoint subgraphs before training and samples and combines them across epochs (extended version, §9.2, Algorithms 7–8). Thus, the broad claim of being the first to separate extraction from composition is overstated. Appendix B acknowledges this predecessor and identifies meaningful additions in exact-budget composition and structural analysis. However, the empirical benefit over this closest existing combination remains unclear. Appendix J’s diversity-preprocessing bottleneck does not fully explain the omission of its single-channel variant, which does not require that step.

  2. Key experimental reports require reconciliation before the aggregate comparisons can be fully assessed. At 30% retention on Roman-Empire, AdaGLT scores 81.43 in Table 1 but 66.15 in Table 10, reversing its ordering against EDiS. Furthermore, using Table 1’s displayed means and excluding the four reference rows yields an EDiS average rank of approximately 2.53 and gap of 1.25, rather than Table 2’s 3.32 and 2.51. A different aggregation procedure could explain the latter discrepancy, but it must be specified. These issues reduce confidence in reporting consistency, although the recomputed statistics favor EDiS and its reported mean of 75.95 is reproducible.

Questions for authors
  1. Closest prior work: Which AGS-GNN variant was attempted in Appendix J? In particular, why does the reported diversity bottleneck preclude comparison with the single-channel AGS-GS-Disjoint algorithm, and what are the precise algorithmic additions over that variant?

  2. Numerical reporting: Which results are authoritative for the Table 1/Table 10 discrepancy? Are Table 2’s Rank and Gap computed from per-dataset means or separately within runs? Please reconcile the tables and provide the corresponding aggregation procedure.

3 comments

We thank the reviewer for the comments.

W1.1 The incremental contribution…

We will revise the novelty claim and position EDiS as an exact-budget sparsification framework. AGS-GS-Disjoint [1] can be viewed as an instance of the broader decomposition-and-composition paradigm when exact-budget enforcement is relaxed. Additions are in Q1.2.

W1.2 the empirical benefit over AGS-GS-Disjoint…

We compare EDIS with AGS-GS-Disjoint (similarity ranking, Algorithms 7-8) single channel variant with same edge budget. We evaluate AGS using both its original model and the tuned settings (Table 7), under sampled (S) and full-graph (F) inference at ρ=0.3\rho = 0.3.

Table R1:

DatasetAGS Orig.(S)AGS Orig.(F)AGS GCN(S)AGS GCN(F)EDiS-Lite(S)EDiS-Full(F)
Cora70.44±0.8676.36±1.1274.20±1.1080.78±1.5677.16±0.9884.08±0.83
PubMed70.82±1.8073.18±1.8975.68±0.9179.48±0.8177.28±0.5780.20±0.46
WikiCS78.34±0.8579.11±0.5980.10±0.7580.13±0.3680.25±0.7980.39±0.29
Squirrel38.53±1.8638.97±2.0841.72±1.8442.54±2.0742.63±2.0443.26±2.43

EDiS outperforms the AGS variants on all four datasets under both inference settings.

W1.3 Appendix J’s diversity-preprocessing…

Correct. Appendix J concerns dual-channel AGS-GNN, whose submodular diversity ranking did not complete on our hardware. We will add results for the single-channel variant in the revision.

Q1.1 Which AGS-GNN variant was attempted in Appendix J?

The variant tested is the dual-channel AGS-GNN (similarity + submodular diversity). The bottleneck is specific to that variant and does not preclude the single-channel comparison, which is shown in Table R1 (W1.2).

Q1.2 — Algorithmic additions

EDiS builds on AGS-GS-Disjoint's edge-disjoint decomposition and epoch-wise composition, with four key distinctions:

1. Exact-budget composition. EDiS guarantees exactly B=⌈ρ∣E∣⌉B=\lceil\rho|E|\rceil edges per epoch through subgraph selection, trimming, and residual filling. AGS-GS-Disjoint does not establish equivalent exact-budget control.

2. Structural guarantees. EDiS establishes score-threshold cut certificates for stored MaxCF prefixes (Theorem 1) and conditional edge-retention bounds for composed graphs (Theorem 2), neither established for AGS-GS-Disjoint.

3. Residual coverage and reuse. Both methods support residual-edge supplementation and cached decomposition. EDiS formalizes exact-budget composition across retention ratios without re-extraction.

4. Training and inference. EDiS evaluates full-batch training with sparse (Lite) or full-graph (Full) inference. AGS primarily uses GraphSAINT-style mini-batches but also permits full-batch processing.

Furthermore, EDiS provides dedicated empirical evaluation of these design choices, whereas AGS-GS-Disjoint was not separately evaluated in the original AGS paper.

W2 30% retention Roman-Empire, AdaGLT…

Table 10 used AdaGLT's default 2-layer GCN (512 hidden units, LR 0.01, WD 510-4; 66.15), while Table 1 used EDiS-aligned 9-layer GCN settings (LR 0.001, zero WD, batch normalization, residual connections; 81.43). We will align Table 10 accordingly.

Q2 Which results are authoritative …..

Table 1 is authoritative; Table 10 will be corrected. Rank and Gap are computed from the 19 dataset-level mean scores (accuracy or ROC-AUC where applicable) across the 15 ranked methods, excluding MLP, Spanning Tree, Full GCN, and EDiS-Full. Methods are ranked per dataset (best = 1, average ranks for ties); Gap is the difference from the best score in points. Score, Rank, and Gap are then averaged across datasets.

Revised Table 2.

Methodρ=0.3 ScoreRankGapρ=0.5 ScoreRankGap
Random73.718.503.4975.957.553.04
Local Deg.74.037.053.1776.607.182.39
Rank Deg.70.9510.246.2673.369.875.63
Forest Fire74.367.082.8477.104.421.89
SCAN72.778.794.4375.718.083.28
L-Spar72.3110.244.8974.6010.504.39
G-Spar72.4410.554.7674.4910.924.50
L-Sim75.264.741.9477.624.631.37
Spectral74.706.132.5076.396.162.60
t-Spanner73.917.663.3075.897.503.10
DSpar72.037.165.1774.407.164.60
Unified-LTH70.5511.876.6571.1912.767.81
AdaGLT70.379.896.8371.7611.377.23
MoG72.297.584.9174.028.584.97
EDiS-Lite75.952.531.2577.763.321.23

We confirm the reviewer's recalculation and will correct Table 2. EDiS-Lite retains the highest mean score (75.95/77.76), best average rank (2.53/3.32), and lowest average gap (1.25/1.23) at =0.3/0.5.

[1] https://arxiv.org/pdf/2405.15218

Thanks for adding the single-channel AGS results and correcting Table 2. The aggregation is clear now. I also agree that the novelty claim should focus on exact-budget composition and the structural analysis.

Since Table 1 is authoritative, could you check the corresponding appendix entries as well? For EDiS-Lite at 30% retention, Questions is 74.12 in Table 1 and 73.88 in Table 10. The Arxiv results are 71.41 and 70.96, and Pokec is 81.19 and 80.79, in Tables 1 and 11. If these are separate runs or configurations, a short explanation would help.

For AGS, you confirmed that the integer budget was enforced directly. What I would still like to know is how excess edges and shortfalls were handled, and whether this required changes to Algorithms 7–8. A pointer to the relevant code or a brief description would be enough. The matched-GCN comparison helps, though some of the gains are small.

I would also revise the wording of RQ5. Theorem 2 applies to any selector, but the bound depends on the actual decomposition and retained fractions. It therefore does not predict that classification performance will be independent of the selector. The ablations are useful evidence about this sensitivity; that distinction should be clear in the text.

These replies address much of what I raised in the original review. I’m keeping my weak-accept rating.

We thank the reviewer for the constructive follow-up. We address each remaining concern below.

Q1: Table 1 and Appendix Consistency

The differences arise from separate experimental runs conducted across different GPUs. At 30% retention, the discrepancies are Questions: 0.24 pp (74.12 vs. 73.88), ogbn-arxiv: 0.45 pp (71.41 vs. 70.96), and Pokec: 0.40 pp (81.19 vs. 80.79).

All differences are below 0.5 percentage points and originate from repeated runs. Table 1 contains our authoritative results. We will reconcile the experimental records, correct Tables 10–11, and ensure consistent reporting throughout the revision.

Q2: AGS-GS-Disjoint Exact-Budget Implementation

We appreciate the request for implementation details. Our comparison uses the single-channel AGS-GS-Disjoint variant with an explicit exact-budget extension, enforcing the same integer budget as EDiS: B = ⌈ρ|E|⌉.

Excess edges: Cached spanning forests are visited in importance-weighted random order. Complete forests are included while they fit within the budget. If the next forest exceeds the remaining budget, exactly the required number of edges is uniformly sampled without replacement from that forest.

Code: disjoint_sparsifier.py, _select_by_target_ratio(), lines 324–343.

Budget shortfalls: Edges remaining after spanning-forest extraction are preserved in a zero-weight residual subgraph. This pool is visited after positively weighted forests and supplies additional edges when needed to reach the requested budget.

Code: disjoint_sparsifier.py, lines 273–279 and disjoint_sparsifier.py, lines 310–343.

Modifications to Algorithms 7–8: We clarify that this is an exact-budget adaptation. The edge-disjoint spanning-tree decomposition is retained, with documented implementation adjustments. The main extension replaces Algorithm 8's fixed-subgraph-count selection with budget-controlled composition and boundary trimming.

These modifications are documented in baselines/ags_gnn/disjoint_port/README.md.

Q3: RQ5 and Theorem 2 Clarification

We thank you for this Recommendation; we will update it in the revision.

Closing Remarks

We sincerely appreciate your constructive feedback and thoughtful engagement throughout the review process. If you believe our additional experiments, implementation evidence, and clarifications have adequately addressed your remaining concerns, we would be grateful if you would consider revisiting your overall rating.

Thank you again for your time and valuable feedback. Please let us know if you have any further questions or concerns.

Reviewer_jL1MOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to reduce GNN training costs while exposing the model to different sparse graph structures. Reusing one sparsified graph limits structural diversity, whereas repeatedly extracting new structures can be expensive. EDiS addresses this trade-off by separating one-time decomposition from per-epoch composition.

The method scores edges and extracts a cached collection of edge-disjoint subgraphs, using maximum-score covering forests by default. At each epoch, it samples and combines these components, then trims or supplements the selected edges to meet an exact edge budget. The resulting graph retains all nodes and is used for standard GNN training. The paper provides structural guarantees for the stored decomposition and conditional retention analysis for the composed graphs.

Experiments cover 19 node-classification datasets, including homophilic, heterophilic, and large-scale graphs. Matched-budget comparisons include random and topology-based sparsifiers, spectral methods, and learned sparsification methods. Additional experiments examine alternative backbones, runtime, inference graphs, and controls isolating structural grouping and epoch-to-epoch variation. EDiS-Lite achieves the highest average predictive score among the ranked methods at 30% and 50% edge retention, although its margins over the strongest baseline are modest. Runtime results show benefits on some large graphs, while preprocessing costs are not always amortized within the evaluated training budget.

Critical strengths
  1. Clear motivation and practical problem. The paper clearly motivates the trade-off between reusing a fixed sparse graph and repeatedly generating new training graphs. Its focus on reducing construction costs while maintaining structural diversity is relevant to efficient GNN training.
  2. Broad empirical evaluation on comprehensive benchmarks. The experiments cover 19 benchmark datasets spanning homophilic and heterophilic graphs of varying scales. Comparisons include several categories of sparsification methods, providing a broad assessment of the proposed framework.
  3. Informative ablation studies. The Frozen, Direct, and Shuffled controls help distinguish the contributions of epoch-to-epoch variation and structural grouping. These experiments provide useful evidence beyond aggregate predictive performance.
Critical weaknesses
  1. Important details are deferred to the appendix. Several elements needed to assess the contribution—including distinctions from the closest prior methods, detailed efficiency results, and evaluation protocols—are primarily presented in the appendix. Bringing the essential information into the main text would make the novelty and practical benefits easier to assess.

  2. Limited comparison with related dynamic and sampling-based methods. Although the paper includes many sparsification baselines and useful controls, comparisons with sampling-based training methods such as LADIES and GraphSAINT are absent. Their different budget definitions justify separate evaluation protocols, but accuracy–time–memory comparisons would help establish EDiS’s practical advantages. More importantly, AGS-GS-Disjoint already caches edge-disjoint components and samples their combinations during training. Without a direct comparison, the empirical value of EDiS’s additional design choices remains unclear.

  3. Unexplained inconsistencies between result tables. Some results differ between the main text and appendix despite being reported at the same retention ratio. For example, on Cora at 30% retention, DSpar achieves 73.90±0.36 in Table 1 but 69.33±0.87 in Table 9. These differences may reflect different runs or configurations, but they should be explained and reconciled before assessing the aggregate rankings and relatively small average margins.

Questions for authors

My questions and concerns are listed in the weaknesses.

3 comments

We thank the reviewer for the feedback.

W1: Important details are deferred to the appendix

We will move key comparisons, efficiency results, and evaluation protocols to the main text, keeping details in the appendix.

W2 Part 1: Comparison with related dynamic and sampling-based methods

We compare EDiS with LADIES and GraphSAINT on accuracy, time, and memory. Both GraphSAINT samplers resample each epoch at the exact edge budget; LADIES uses layer-wise sampling without matched budgets. All share backbone and dataset settings (Table 7).

Accuracy: Table R1

DatasetGraphSAINT-RWGraphSAINT-edgeLADIESEDiS-LiteEDiS-Full
Amazon-Computer91.47±0.4793.17±0.2891.85±0.3993.21±0.2793.46±0.26
Roman-Empire69.15±0.8667.77±0.1772.87±0.4969.72±0.5274.90±0.43
ogbn-arxiv64.66±0.3570.83±0.3968.92±0.0871.03±0.2473.20±0.55
Reddit94.40±0.1195.20±0.0288.54±0.3595.61±0.0495.08±0.03
ogbn-products75.34±0.5180.30±0.2771.27±0.5980.78±0.5181.38±0.16

Time/Memory

EDiS requires one-time decomposition; GraphSAINT requires normalization preprocessing; LADIES requires none. We report preprocessing and training costs separately.

Table R2(a). Preprocessing scalability. Time (s), speedup over serial Kruskal (×); p = workers. AMD EPYC 9334, median of 5 runs.

DatasetSerialp=1p=2p=4p=8p=16
Reddit393.9231.1 (1.7×)132.4 (3.0×)103.1 (3.8×)98.2 (4.0×)66.5 (5.9×)
ogbn-products198.3155.2 (1.3×)93.4 (2.1×)61.9 (3.2×)54.6 (3.6×)35.9 (5.5×)

Preprocessing achieves up to 5.9× speedup; decomposition is reused across epochs and budgets.

Table R2(b). Training time/memory. Seconds/epoch / peak GPU GB; best per metric bolded. Median of 3 × 50 epochs on one GPU, excluding evaluation.

DatasetGraphSAINT-RWGraphSAINT-edgeLADIESEDiS-Lite
Amazon-Computer0.015/1.00.015/1.00.025/0.10.011/1.0
Roman-Empire0.030/1.60.029/1.60.082/0.20.029/1.6
ogbn-arxiv0.152/8.60.146/8.60.044/0.30.132/8.6
Reddit2.438/13.11.010/13.10.107/4.10.305/13.8
ogbn-products2.946/56.91.660/56.90.252/5.20.891/58.1

EDiS is 1.9–8.0× faster than GraphSAINT on the two largest graphs. LADIES uses less time and memory but generally has lower accuracy, except against EDiS-Lite on Roman-Empire. EDiS offers a favorable accuracy-efficiency tradeoff in several settings.

W2 Part 2: Comparison with AGS-GS-Disjoint

We compare AGS-GS-Disjoint [1] with its original model and an EDiS-tuned GCN, using sampled (S) and full-graph (F) inference at 30% retention.

Table R3. AGS-GS-Disjoint comparison.

DatasetAGS Orig.(S)AGS Orig.(F)AGS GCN(S)AGS GCN(F)EDiS-Lite(S)EDiS-Full(F)
Cora70.44±0.8676.36±1.1274.20±1.1080.78±1.5677.16±0.9884.08±0.83
PubMed70.82±1.8073.18±1.8975.68±0.9179.48±0.8177.28±0.5780.20±0.46
WikiCS78.34±0.8579.11±0.5980.10±0.7580.13±0.3680.25±0.7980.39±0.29
Squirrel38.53±1.8638.97±2.0841.72±1.8442.54±2.0742.63±2.0443.26±2.43

EDiS achieves higher mean accuracy than AGS on all four datasets. AGS-GS-Disjoint can be viewed as a special case of EDiS's decomposition-and-composition framework when exact-budget enforcement is relaxed. Key distinctions:

1. Exact budget: EDiS enforces the target edge count each epoch through selection, trimming, and residual filling; AGS offers no equivalent guarantee.

2. Structural guarantees: EDiS proves score-threshold cut certificates for stored MaxCF prefixes (Theorem 1) and conditional edge-retention bounds for composed graphs (Theorem 2); AGS lacks analogous analysis.

3. Residual coverage and reuse: Both cache components and add residual edges; EDiS formalizes exact-budget composition across retention ratios without re-extraction.

4. Training and inference: EDiS evaluates full-batch training with sparse (Lite) or full-graph (Full) inference. AGS mainly uses GraphSAINT-style mini-batches but permits full-batch processing.

EDiS evaluates these design choices; the original AGS paper did not separately evaluate AGS-GS-Disjoint.

W3: Unexplained inconsistencies

The appendix DSpar run used a 2-layer GCN (256 hidden units, dropout 0.5, LR 0.01, batch normalization). For fair comparison, the main-paper run used 3 layers (512 hidden units, dropout 0.7, LR 0.001, weight decay 5e-4, no batch normalization), achieving 73.90 ± 0.36. We will align the appendix settings. Conclusions remain unchanged: EDiS-Lite retains the highest mean benchmark score among ranked methods.

[1] https://arxiv.org/pdf/2405.15218

Thanks for authors' reply. My concern has already been solved. Raised the score.

We thank the reviewer for their reconsideration and for confirming that our responses have adequately addressed their concerns. We appreciate their careful evaluation and constructive feedback.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Gentle Follow-Up on Our Rebuttal

Dear Reviewers,

Thank you again for your thoughtful feedback. As the author–reviewer discussion period closes tomorrow, we wanted to kindly follow up on our rebuttal. We would greatly appreciate any further comments or remaining concerns, so we have an opportunity to address them before the discussion ends.

Thank you for your time and consideration!

Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.