- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes ELDOR, a method for network dismantling under structural distribution shift. It separates each removal decision into an immediate fragmentation cost, computed exactly through articulation analysis, and a learned, budget-dependent future contribution. A discrete Doob transform combines these terms into a removal policy, trained using exact dynamic programming on tiny graphs and consistency objectives on larger synthetic graphs. Evaluation on 48 real networks shows improvements over the evaluated learned baselines, while greedy performance is comparable to strong training-free heuristics.
Critical strengths
-
Well-motivated separation of computation and learning. Computing the immediate effect exactly avoids asking a message-passing network to infer structural properties it cannot generally identify. The linear-time computation of all candidate afterstate costs makes this separation particularly appealing.
-
Coherent formulation with clearly stated guarantees. The Doob-control framework provides explicit targets for the learned future term. The paper establishes feasibility, permutation equivariance, and conditional bounds relating potential approximation error to trajectory divergence, while acknowledging the limits of these results.
-
Extensive empirical evaluation. The experiments cover 48 real networks, multiple synthetic settings, and strong training-free baselines. Component ablations, controlled structural tests, multiple training seeds, and equal-time comparisons provide useful evidence beyond aggregate accuracy.
Critical weaknesses
-
The methodological novelty needs sharper justification. The framework builds on established Doob transforms, soft afterstate values, and Bellman-consistency objectives. Section 2 also acknowledges that any positive removal kernel admits the proposed exact–learned decomposition. Consequently, it remains unclear how much of the gain comes specifically from the Doob formulation rather than exact structural inputs, bounded value parameterization, or the training curriculum.
-
The theory provides limited guidance for practical performance. Proposition 8 requires uniformly accurate potentials over all reachable states, a premise checked only on graphs with at most 20 nodes. Even there, the reported KL bound reaches 5.44, suggesting limited quantitative tightness. The large-graph consistency diagnostics do not establish this premise, and the trajectory-law guarantee does not directly cover greedy decoding or the batching and search procedures. A stronger connection between approximation error and the dismantling quality of the deployed decoder would be valuable.
-
Comparisons with published learned methods do not fully control training conditions. ELDOR uses seven synthetic training families, exact small-graph supervision, and a substantial training curriculum, whereas FINDER, GDM, and MIND are evaluated using published results without retraining. The Structural-AR control is helpful, but it does not establish whether the advantage over these methods persists under matched training data and computational budgets. Such comparisons would better isolate improvements in generalization attributable to the method.
Questions for authors
see Weaknesses
3 comments
Thanks
Thank you for the detailed response. I suggest using clearer tables and fixing the LaTeX rendering to make the rebuttal easier to follow. After considering the response and other reviewers’ comments, I still find the methodological novelty insufficiently justified. The additional experiments are helpful, but the conceptual contribution beyond established tools remains unclear. For now, I will retain my current score.
We thank the reviewer for the follow-up. We have clarified the tables and notation. The remaining novelty concern deserves a direct answer: assessing only whether individual tools are new overlooks the methodological problem ELDOR solves.
W1: The contribution is a defined learning problem, not a new name for an existing tool.
We do not claim to invent Doob transforms, articulation algorithms, soft values, kernel factorization, or a more expressive positive policy class.
The distinction is what is computed, learned, and targeted. For state , ELDOR obtains every candidate's immediate fragmentation cost exactly in a single graph analysis. The network then approximates the specific continuation target
where .
This is not simply an unconstrained learned ranking. The target aggregates reference-weighted, cost-tilted continuations over valid irreversible removal paths, depends on remaining budget, and is consistent with . Exact small-graph DP and larger-graph consistency training supervise this same quantity. Two actions identical under immediate fragmentation can therefore differ in value if one makes a later coordinated cut possible.
A generic scorer may represent the same policy, but need not have the same learning target. The methodological claim is this task-specific allocation of exact computation and target-defined learning. We respectfully disagree that reusing established mathematical ingredients, by itself, makes that formulation conceptually indistinct.
Table R1: Objective and component tests (48 real networks; normalized AUC, lower is better).
| Method | AUC |
|---|---|
| ELDOR greedy | 93.2 |
| Non-Doob future-value control | 97.4 |
| No exact labels | 98.1 |
| No consistency | 100.1 |
| No future guidance | 101.2 |
| No exact immediate cost | 102.4 |
| Structural-AR (same encoder) | 106.0 |
The non-Doob control changes only the future-learning objective; encoder, inputs, splits, exact-label access, optimization budget, checkpoint selection, and greedy decoding are matched. ELDOR improves by (95% CI half-width; Holm ). This is precisely the control needed to distinguish the implemented Doob-consistent target from merely using better structural inputs or more supervision. We do not claim superiority over every conceivable future-value objective.
Table R2: Unseen coordinated separators (Table 18; raw , lower is better).
| Method | Width 3 | Width 4 |
|---|---|---|
| ELDOR | 16.9 | 18.2 |
| Structural-AR | 21.9 | 23.7 |
| Exact-myopic | 24.1 | 26.2 |
Here immediate costs are flat while coordinated future removals matter. The result tests the proposed mechanism, rather than only aggregate benchmark performance.
W2: The theoretical claim is specific and its boundary is explicit.
Theorem 2 defines the ideal stochastic path law; Proposition 8 bounds the learned sequential law only with uniform potential accuracy on reachable states. We do not extend either guarantee to large-graph greedy or best-of-. A separate conditional result states that candidate-logit error at most (up to a common offset) gives at most exact-Doob logit regret; a learned winner's margin above ensures the exact-Doob greedy choice. On held-out exact-DP graphs, action agreement is 94.6% and the sufficient-margin condition holds in 78.4% of assessed states. These are small-graph observations, not a large-graph certificate.
W3: The training comparison is controlled, with its limitation disclosed.
Table R3: Retrained baselines (48 real networks; original MIND=100 normalization).
| Method | AUC |
|---|---|
| ELDOR | 93.2 |
| Retrained MIND | 99.3 |
| Retrained GDM | 103.4 |
| Retrained FINDER | 111.2 |
MIND, GDM, and FINDER retain their original architectures and objectives, with matched synthetic distributions, comparable optimization/selection budgets, five seeds, and no real-test tuning. Against retrained MIND, (Holm ). This does not erase supervision differences: ELDOR uses 2,100 exact-labeled small graphs, whose DP tables required 640 CPU-hours. Without exact labels, ELDOR scores 98.1; we make no significance claim against retrained MIND's 99.3.
We recognize that assessments of formulation-level novelty differ. Yet the contribution cannot be reduced to applying a Doob transform: it specifies a continuation-learning problem, exact immediate costs, complementary supervision, and matched evidence for the objective. We respectfully ask the reviewer to reassess this distinction.
We thank the reviewer for the thoughtful assessment. We address the novelty, theory and training-fairness concerns with matched tests and a greedy-decision analysis.
W1: What is distinctive about the Doob formulation? The Doob transform, soft values and kernel factorization are established tools. Our contribution is a task-defined control law for irreversible node deletion, P∗(π)∝Q0(π)e−βΦ(π), combining exact O(n+m) all-candidate immediate fragmentation costs with a learned, budget-dependent future potential. This defines the future-learning target rather than an arbitrary removal score. In Table 3, greedy ELDOR scores 93.2 on 48 real networks (normalized AUC, lower is better), compared with 106.0 for same-encoder Structural-AR, 101.2 without future guidance, 102.4 without exact costs, 98.1 without exact labels and 100.1 without consistency. The ELDOR–Structural-AR paired difference is −12.8±2.4 (Holm p<10−4; Table 22). On held-out width-3/4 separators, where one-node fragmentation costs cannot identify a coordinated cut, ELDOR achieves 16.9/18.2 versus Structural-AR 21.9/23.7 and myopic exact 24.1/26.2 (Table 18; raw R×100). These ablations support the decomposition, not the objective alone. We therefore tested a non-Doob future-value control that keeps the encoder, structural inputs, training and validation graphs, exact-label access, optimization budget, checkpoint selection and greedy decoder fixed; the future-learning objective is changed. It scores 97.4 against ELDOR's 93.2 on the same 48 networks (paired Δ=−4.2±1.4, 95% CI half-width; Holm p<0.001). This is the direct evidence for the value of our implemented Doob-consistent objective under matched conditions. We do not claim universal superiority.
W2: What does the theory tell us about greedy decisions? Theorem 2 characterizes the ideal stochastic path law. Proposition 8 concerns the learned sequential law and assumes uniform potential accuracy over every reachable state. At n=20, the measured path KL is 0.52 against the upper bound 5.44 (Table 17); the premise can be checked exactly only for n≤20. Real-network residual 0.040 and rollout correlation 0.91 are diagnostics, not certificates; Proposition 8 does not cover greedy, batching or best-of-K. To connect approximation to the deployed greedy choice, we provide a separate conditional result. If learned and exact-Doob candidate logits differ by at most ε after adjusting for a common additive offset, the chosen action has at most 2ε regret in exact-Doob logit value. A learned winner's margin greater than 2ε guarantees the same choice as exact-Doob greedy. If that condition holds at every visited state, the removal sequence and AUC coincide with exact-Doob greedy, not necessarily the globally optimal sequence. On held-out exact-DP graphs (n≤20), action agreement is 94.6%, the sufficient margin condition holds in 78.4% of assessed states, and mean absolute AUC difference is 0.42 (raw R×100). This is not a large-graph guarantee.
W3: Do the gains survive more comparable training conditions? We agree that the originally quoted MIND, GDM and FINDER results are not training-matched. We retrained their original architectures and learning objectives using matched synthetic training/validation distributions, comparable optimization and checkpoint-selection budgets, and five seeds, with no real-test tuning. ELDOR uses seven synthetic families, 9,600 unlabeled graphs and 2,100 exact-labeled small graphs (n≤20; Table 6). We retain the original per-network MIND=100 normalization, not the retrained MIND denominator. The retrained scores are 99.3 (MIND), 103.4 (GDM) and 111.2 (FINDER), versus ELDOR's 93.2; the paired ELDOR–retrained-MIND difference is −6.1±1.7 (95% CI half-width; Holm p<0.001 across 48 networks). The gain thus survives matched training distributions and compute. Importantly, it is not an identical-information comparison: ELDOR additionally uses exact small-graph labels. The no-exact-label ELDOR ablation scores 98.1 (Table 3), versus retrained MIND's 99.3, but we make no significance claim for that separate contrast. We will separately disclose supervision access and the 640 CPU-hours used to generate exact DP tables (Table 10).
Practical scope: Greedy ELDOR (93.2) ties training-free LGD-NA (93.9; Holm p=0.35). Best-of-16 (90.2) improves on per-graph equal-time restarted LGD-NA (92.2; paired −2.0±0.6, Holm p<10−4; Tables 16/22). Technological-network regressions and theory's scale limitations remain. We ask the reviewer to reconsider in light of the objective-matched control, retrained baselines and explicit greedy-decision analysis.