- 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
-
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.
-
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
-
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.
-
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):
-
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?
-
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):
-
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?
-
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
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:
| Table 16 | Rebuttal R3 | |
|---|---|---|
| Build time | 313.7 s | 45 s |
| Full-GCN (per epoch) | about 2.38 s | 0.805 s |
| EDiS-Lite (per epoch) | about 1.73 s | 0.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 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:
- https://anonymous.4open.science/r/EDSparse-9FB0/baselines/pytorch_graphsaint.py, lines 138–140 define B, lines 164–165 verify the exact count each epoch, and lines 118–122 implement SAINT-RW sampling and trimming.
- https://anonymous.4open.science/r/EDSparse-9FB0/baselines/graphsaint_edge.py, lines 26 and 33 implement exact-budget weighted edge sampling and connect it to the shared training protocol.
- https://anonymous.4open.science/r/EDSparse-9FB0/edsparse/core/sampling.py, lines 104–107 define the matching EDiS edge budget.
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).
| Method | s/epoch | Total (s) |
|---|---|---|
| EDiS-Lite | 0.305 | 158 |
| DropEdge | 0.302 | 91 |
| SAINT-Edge | 1.010 | 303 |
| SAINT-RW | 2.438 | 731 |
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.
We thank the reviewer for the feedback.
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.
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.
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.
We report serial and parallel MaxCF decomposition times.
Table R2. Preprocessing scalability. Time (s), AMD EPYC 9334, median of 5 runs.
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, 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 (H100, 16 CPU, seconds).
We provide YAML configurations to reproduce results. For Cora:
1. EDiS-Lite:
python main.py run --config configs/paper/gcn/cora.yaml2. EDiS-Full:
python main.py run --config configs/paper/gcn/cora_full.yamlExperiments 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:
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.
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.
Table R5. Test accuracy; sparse/full inference.
Rebuttal evidence provides available per-seed outputs and exact integer edge counts for the main results.