acceptodds
Under review as a conference paper at ICLR 2027

EXACT–LEARNED DOOB CONTROL FOR NETWORK DISMANTLING UNDER STRUCTURAL SHIFT

20 views

Abstract

Learned network dismantling methods can struggle to generalize to networks whose structures differ from those seen during training. To address this limitation, we separate the effect of removing a node into two components: an immediate effect that can be computed exactly and a budget-dependent future effect that must be estimated. We formulate network dismantling as an irreversible stochastic process over nested residual graphs and use a discrete Doob transform to steer a topology-based reference process toward early fragmentation. The immediate effect of each candidate node is computed using a linear-time articulation analysis, while a neural network estimates only the remaining long-term contribution. The model is trained using exact dynamic programming on small graphs together with a self-consistency objective on larger unlabeled graphs. Our proposed method, ELDOR, is trained only on small synthetic networks and generalizes zero-shot to 48 real-world networks and a standard synthetic benchmark. ELDOR outperforms the strongest learned baseline on 42 of the 48 real networks and reduces mean normalized AUC by 6.8%. Its overall performance is comparable to strong training-free methods, while providing significant improvements on several biological, information, and social networks. Using best-of-16 search further improves ELDOR's average performance across the benchmark.

Primary area:
transfer learning, meta learning, and lifelong learning
Keywords:
network dismantling, graph neural networks, combinatorial optimization, zero-shot generalization, Doob transform, stochastic control, graph algorithms, structural shift

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_QRJoOpenReview ↗
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
  1. 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.

  2. 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.

  3. 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
  1. 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.

  2. 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.

  3. 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

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−βΦ(π)P^*(\pi)\propto Q_0(\pi)e^{-\beta\Phi(\pi)}, combining exact O(n+m)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-12.8\pm2.4 (Holm p<10−4p<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×100R\times100). 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\Delta=-4.2\pm1.4, 95% CI half-width; Holm p<0.001p<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=20n=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≤20n\le20. Real-network residual 0.040 and rollout correlation 0.91 are diagnostics, not certificates; Proposition 8 does not cover greedy, batching or best-of-KK. 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 ε\varepsilon after adjusting for a common additive offset, the chosen action has at most 2ε2\varepsilon regret in exact-Doob logit value. A learned winner's margin greater than 2ε2\varepsilon 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≤20n\le20), 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×100R\times100). 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≤20n\le20; 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-6.1\pm1.7 (95% CI half-width; Holm p<0.001p<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.35p=0.35). Best-of-16 (90.2) improves on per-graph equal-time restarted LGD-NA (92.2; paired −2.0±0.6-2.0\pm0.6, Holm p<10−4p<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.

Reviewer_QRJoOpenReview ↗

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 (S,b)(S,b), ELDOR obtains every candidate's immediate fragmentation cost exactly in a single O(n+m)O(n+m) graph analysis. The network then approximates the specific continuation target

r∗(v;S,b)=log⁡hb−1(S∖{v}),r^*(v;S,b)=\log h_{b-1}(S\setminus\{v\}),

where hb(S)=∑v∈Sq0(v∣S)e−βc(S∖{v})hb−1(S∖{v})h_b(S)=\sum_{v\in S}q_0(v\mid S)e^{-\beta c(S\setminus\{v\})}h_{b-1}(S\setminus\{v\}).

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 P∗(π)∝Q0(π)e−βΦ(π)P^*(\pi)\propto Q_0(\pi)e^{-\beta\Phi(\pi)}. 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).

MethodAUC
ELDOR greedy93.2
Non-Doob future-value control97.4
No exact labels98.1
No consistency100.1
No future guidance101.2
No exact immediate cost102.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 Δ=−4.2±1.4\Delta=-4.2\pm1.4 (95% CI half-width; Holm p<0.001p<0.001). 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 R×100R\times100, lower is better).

MethodWidth 3Width 4
ELDOR16.918.2
Structural-AR21.923.7
Exact-myopic24.126.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-KK. A separate conditional result states that candidate-logit error at most ε\varepsilon (up to a common offset) gives at most 2ε2\varepsilon exact-Doob logit regret; a learned winner's margin above 2ε2\varepsilon 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).

MethodAUC
ELDOR93.2
Retrained MIND99.3
Retrained GDM103.4
Retrained FINDER111.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, Δ=−6.1±1.7\Delta=-6.1\pm1.7 (Holm p<0.001p<0.001). 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.

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

This paper introduces updated Network dismantling procedure, named ELDOR. It claims to improve upon previous work by computing each node removal's immediate fragmentation effect (how much removing a node shrinks the network largest component now) exactly using graph algorithm (a linear-time articulation analysis), and learns only its longer-term, budget-dependent value using GNN (how that removal changes what can be achieved with the remaining budget).

Particularly, its next-node score combines the reference policy term (prior with a soft preference for high-degree nodes) , the exact immediate term and the learned future term. A discrete Doob transform turns these terms into a valid probability distribution over the remaining nodes. With the exact future potential, the resulting trajectories are reweighted toward sequences that fragment the graph early, while retaining valid, non-repeating node removals by construction.

ELDOR network for learned future term is permutation-invariant and it takes residual-graph structural features, not node identities or graph-size identifiers. The network is also conditioned on the criticality density which reduces network evaluations when the residual graph is far from a critical split. Similar to pertaining and SFT in diffusion modelling, the ELDOR network is also trained with data from two regimes - exact supervision on small graph for which all the reachable states are precomputed using dynamic programming and coarse supervision (only self-consistency checks) on large unlabelled synthetic graphs.

After training on seven synthetic graph families, ELDOR was evaluated zero-shot on 48 real networks and synthetic benchmarks. Here, it was shown to outperform MIND on 42 networks and reduces dismantling AUC by 6.8%.

Critical strengths

ELDOR’s strongest contribution is not a new dismantling objective, but a well-motivated hybrid formulation that makes the sequential decision problem more structured, testable, and apparently more transferable than prior learned dismantlers.

  • Principled exact–learned decomposition Prior learned methods such as FINDER, MIND, NIRM, GDM, and other RL-style approaches learn a removal score or policy end-to-end. ELDOR instead computes the one-step post-removal giant-component cost for every candidate exactly, then learns only the budget-dependent future value. This directly addresses a documented limitation of message-passing GNNs: they do not generally detect biconnectivity or articulation structure.
  • A coherent control formulation rather than an ad hoc score The Doob construction gives a precise target distribution over removal trajectories: a topology-based reference process tilted toward paths that fragment early. This is a sharper theoretical account than typical policy-gradient or ranking formulations.
  • Unusually credible transfer protocol One model is trained on seven synthetic families and evaluated zero-shot on 48 real networks, including graphs far larger than training set and an unseen configuration-model family.

However, the novelty claim should be stated narrowly. The individual ingredients are established: articulation-point algorithms, soft value functions, Doob transforms, linearly solvable control, trajectory-balance objectives, and learned combinatorial policies all predate this work. What appears to be novel is formulation-level -- an irreversible node-removal process controlled by a Doob transform, exact all-candidate afterstate costs, and a learned budget-conditioned future potential trained from small exact instances plus unlabeled consistency training.

Moreover, compared with learned dismantlers, ELDOR is clearly stronger in zero-shot transfer. However, when compared with the best training-free published methods, it is a quality-sensitive hybrid rather than a universal replacement: it wins most clearly on biological, information, and social networks and with multi-sample search, while separator-focused heuristics remain preferable for technological networks and time-critical use.

Critical weaknesses

In authors own words,

  • The scope is narrower than several newer dismantling variants (RL and training-free methods) - It assumes fully observed, static, undirected, unweighted, single-layer graphs with uniform removal cost. It does not yet address directed, weighted, temporal, multilayer, interdependent, hypergraph, defended, or partially observed networks. Thus, ELDOR is strongest as a method for the classical single-layer dismantling benchmark, not yet as a general framework for all network-intervention problem

Moreover, the paper is very poorly written. It is absolutely not written for a generic researcher. And I think even people from this domain may find it difficult to follow through at certain sections. I came across many places, where the text doesn't look continuous. Like the story or flow breaks abruptly. For instances,

  • At line 114, it suddenly reads "We use no Simpson weighting". Nowhere before this, the "Simpson weighting" definition is introduced.
  • At line 124, it abruptly starts talking about kernels which have no relevance to the previous sentence which was explaining how prior models estimate the next node to be removed.
Questions for authors
2 comments

We thank the reviewer for the careful reading and for pinpointing where the presentation becomes difficult to follow. We agree that readers should understand the exact–learned distinction before encountering Doob control. Below we address the scope and offer replacement passages for both examples.

W1: Clarifying the scope. ELDOR studies classical network dismantling on fully observed, static, undirected, unweighted, single-layer graphs with uniform removal costs. Our zero-shot evaluation covers 48 real networks across four domains (128–1,402,673 nodes) and held-out synthetic shifts. We will state these assumptions in the abstract, Section 2, and conclusion. Directed, weighted, temporal, multilayer, interdependent, hypergraph, defended, or partially observed variants can require different objectives, transitions, or immediate-cost calculations. We do not claim to solve them. Our contribution is a specific control formulation for the established classical problem, combining exact structural evaluation with learned guidance for subsequent removals.

W2: Restoring the conceptual flow. The current exposition moves too abruptly from the dismantling metric to kernels. We will reorganize Sections 1–3 around two questions: what happens when we remove a node now, and how does that choice affect the remaining removal budget? Before the formal construction, we will add: "Removing a node has an immediate effect and a future effect. The first is the size of the largest connected component after its removal, which can be calculated exactly for every candidate in one O(n+m)O(n+m) graph analysis. The second depends on which removals remain useful and how much budget is left. ELDOR computes the first quantity and learns the second. The Doob formulation then provides a principled way to favor valid removal sequences that fragment the graph earlier." This bridge will lead into the policy notation. Figure 2 will follow the same order: exact candidate costs, learned future potential, normalized policy, and decoding. We will distinguish the ideal path law, its learned approximation, and greedy, batched, and multi-sample decoding.

Line 114: Explain the metric before Simpson's rule. We propose replacing the abrupt sentence with: "Equation (1) measures dismantling quality by summing the normalized largest-component size at each step before collapse, weighting every step equally. Lower values mean earlier fragmentation. We explain differences from earlier numerical-integration conventions in Section 5.1." There we will define Simpson's rule before comparing it with Eq. (1). Appendix K.1 already recomputes Eq. (1) for eight of nine quoted baselines with available removal orders. Differences are at most 0.4 normalized points per graph and 0.2 in domain means, with unchanged average ranks. The ninth method will remain explicitly marked as quoted because its removal order is unavailable. Line 124: Define the kernel before factorization. We propose: "At a state with surviving vertices SS and bb removals remaining, a sequential dismantler chooses a node v∈Sv\in S. We denote its selection probability by q(v∣S,b)q(v\mid S,b) and call this normalized decision rule a removal policy, or kernel. End-to-end approaches learn the complete selection score. ELDOR computes each candidate's immediate fragmentation cost exactly and learns its budget-dependent future contribution." Only then will we show that any strictly positive kernel admits the algebraic factorization. The identity itself is not new. ELDOR's contribution is the cost-tilted Doob path target that gives the future potential a specific learning objective.

Why this distinction matters empirically. On 48 real networks (normalized AUC, lower is better), greedy ELDOR scores 93.2, compared with 106.0 for same-encoder Structural-AR, 101.2 without future guidance, and 102.4 without exact immediate costs (Table 3). On unseen width-3/4 separators, where one-step effects are flat, ELDOR achieves 16.9/18.2 versus Structural-AR's 21.9/23.7 (Table 18; raw R×100R\times100, not normalized AUC). It also outperforms MIND on 42 of 48 real networks. We retain important qualifications: greedy ELDOR ties LGD-NA and RD overall, while best-of-16 achieves 90.2 versus 92.2 for equal-time restarted LGD-NA (paired Δ=−2.0±0.6\Delta=-2.0\pm0.6, Holm p<10−4p<10^{-4}; Table 22). Technological-network failures and runtime costs remain explicit. The reviewer is right that readers should see the reasoning before the formal machinery. These changes correct both identified transitions and make our scope and contribution easier to assess. We respectfully request reconsideration.

Dear Reviewer, Thank you very much for your time and valuable feedback. We have carefully addressed your comments and provided a point-by-point response. We would greatly appreciate your further feedback and would be happy to provide any additional clarification if needed. Thank you again for your consideration and support.

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

The paper formulates network dismantling as an irreversible stochastic removal process and applies a discrete Doob transform to reweight a topology-based reference kernel toward early fragmentation. Each candidate's immediate effect is computed exactly via a linear-time articulation/separability analysis; a GNN estimates only the budget-conditioned future term. Training combines exact dynamic programming on small graphs (n ≤ 20) with a self-consistency objective on larger unlabeled synthetic graphs (n up to 1,000). The method (ELDOR) is evaluated zero-shot on 48 real networks (up to 1.4M nodes) and a synthetic protocol against 15 baselines. Sequential greedy ELDOR reaches 93.2 mean normalized AUC (MIND = 100), statistically indistinguishable from training-free LGD-NA (93.9) and reverse dismantling (93.7); best-of-16 search reaches 90.2. It is significantly better than LGD-NA on biological/information/social networks but clearly worse on technological ones.

Critical strengths

A principled and clean problem formulation: separating the exactly computable immediate effect from the learned future term, with the Doob transform derived carefully and its assumptions stated honestly; ablations isolate each component's contribution, and reporting includes the losing domains and compute costs.

Honest, unusually thorough evaluation hygiene: policy quality, batched approximation, search, and equal-wall-clock comparisons are reported separately; uncertainty across 5 trained models; checkpoints selected only on synthetic validation cells.

Critical weaknesses

The like-for-like result is parity, not superiority. As a single greedy policy ELDOR (93.2) is statistically indistinguishable from LGD-NA (93.9) and RD (93.7). The significant headline margins come from best-of-16 search (90.2), which shrinks from −3.7 to −2.0 against LGD-NA restarted for equal wall-clock time, and vanishes entirely at the batched-greedy budget (93.6 vs 93.7). Appendix C.1 itself concedes restarted LGD-NA "closes most of the greedy margin at equal time", and best-of-16 costs ~30× one heuristic run. The improvement is thus substantially a compute effect over methods that need no training.

The theoretical guarantee does not reach the evaluation regime. The KL bound (Prop. 8) is verifiable only where the DP is exact — up to n = 20 (ε̂max ≤ 0.34 nats) — while test networks reach 1.4M nodes and training graphs 1,000; at test scale only "consistency diagnostics" (residual ≤ 0.052, ρs ≥ 0.86) are reported, which the authors acknowledge do not establish the premise. Combined with a clear regression on technological networks (83.8 vs EI 67.4, RD 76.0, LGD-NA 80.5) — the infrastructure setting that motivates dismantling — the practical case for the added machinery is weak.

Questions for authors

Is there a setting where ELDOR's advantage survives an equal-compute comparison with restarted LGD-NA? What justifies the 30× inference cost in policy mode?

Can the consistency diagnostics be tightened into an a-posteriori per-graph certificate valid at n >> 20? Without this, what practically distinguishes the Doob-based estimator from a well-tuned learned heuristic?

What explains the technological-network regression (83.8 vs 80.5/76.0/67.4), and is it addressable within the current feature class given the 1-WL limitations discussed in Appendix M.1?

Table 1 mixes quoted numbers (Simpson's rule metric) with re-run ones under Eq. (1); the reconciliation is ≤ 0.4 points, but why not recompute all under the same metric for the ranking?

2 comments

We thank the reviewer for the careful reading and constructive questions.

W1/Q1: Is the gain mainly due to extra compute? The advantage survives matched compute in search; single-run greedy still ties strong heuristics. On 48 real networks (normalized AUC$\downarrow$), greedy ELDOR scores 93.2, versus LGD-NA 93.9 (paired Δ=−0.6±0.9\Delta=-0.6\pm0.9, Holm p=0.35p=0.35) and RD 93.7 (Δ=−0.5±0.9\Delta=-0.5\pm0.9, p=0.41p=0.41). Batched greedy similarly ties time-matched LGD-NA (93.6 versus 93.7). At equal per-network wall-clock time, best-of-16 ELDOR achieves 90.2 versus 92.2 for restarted LGD-NA (Δ=−2.0±0.6\Delta=-2.0\pm0.6, 95% CI half-width; Holm p<10−4p<10^{-4}; Tables 16/22). Restarts narrow, but do not eliminate, the gain. At n=1000n=1000, LGD-NA takes 0.49 s, ELDOR batched greedy 0.93 s, sequential greedy 7.41 s, and original best-of-16 14.70 s end-to-end (Table 20). The 30-fold overhead is unsuitable for time-critical use. We therefore tested K=16K=16, batch 64, selected on synthetic validation. Against LGD-NA restarts matched to its per-network end-to-end time, it obtains 90.7 versus 92.6 over the 48 real networks (paired Δ=−1.9±0.7\Delta=-1.9\pm0.7, Holm p<0.001p<0.001), with 2.25$\times$ lower ELDOR runtime than the original K=16K=16 configuration. This supports offline, quality-sensitive analysis, not faster-than-heuristic inference.

W2/Q2 : What does Doob contribute beyond a learned heuristic? We do not claim novelty for the Doob transform or positive-kernel factorization. ELDOR instead defines a cost-tilted target over irreversible removal paths, computes every candidate's immediate fragmentation cost exactly in O(n+m)O(n+m) per residual state, and learns a budget-conditioned future potential (Eqs. 5–9). Thus the future term has a defined target, not an arbitrary score. The submitted greedy ablations (Table 3) support this design: ELDOR 93.2, same-encoder Structural-AR 106.0, no future term 101.2, no exact immediate cost 102.4, no exact labels 98.1, and no consistency 100.1. On unseen width-3/4 separators, where one-step effects are flat, ELDOR scores 16.9/18.2 versus Structural-AR 21.9/23.7 and myopic exact greedy 24.1/26.2 (Table 18; raw R×100R\times100). More directly, we trained a non-Doob future-value control with the same encoder, structural inputs, splits, exact-label access, optimization budget, validation, and sequential greedy decoder; only the future-learning objective differs. It scores 97.4 versus ELDOR's 93.2 on the same 48 networks (paired Δ=−4.2±1.4\Delta=-4.2\pm1.4, 95% CI half-width; Holm p<0.001p<0.001). This isolates the benefit of the implemented Doob-consistent objective under matched conditions, without claiming universal Doob superiority.

W2/Q2 : Can the theory certify large-graph decisions? No unconditional certificate follows from our diagnostics. Theorem 2 describes the ideal Doob path law; Proposition 8 bounds the learned sequential law only if potential error is uniformly bounded over all reachable states. Exact DP verifies that premise only for n≤20n\le20 (at n=20n=20, measured KL 0.52 versus bound 5.44; Table 17). The real-network residual of 0.040 is a diagnostic, not a large-graph certificate; the proposition does not cover greedy, batching, or best-of-KK. If candidate logits have error at most ε\varepsilon after aligning a common offset, the selected action incurs at most 2ε2\varepsilon regret in exact-Doob logit value. A learned winning margin above 2ε2\varepsilon guarantees agreement with exact-Doob greedy. On held-out exact-DP graphs, action agreement is 94.6%, the sufficient margin holds in 78.4% of assessed states, and mean absolute AUC gap is 0.42 (raw R×100R\times100). These results neither certify large graphs nor establish globally optimal dismantling.

Q3 : Why the regression on technological networks? We acknowledge it: greedy ELDOR scores 83.8, compared with LGD-NA 80.5, RD 76.0, and EI 67.4. On the other 39 networks, ELDOR improves over LGD-NA (paired Δ=−1.6±0.4\Delta=-1.6\pm0.4, Holm p<10−4p<10^{-4}; Table 22). Our nine-network audit flags coordinated multi-node cuts in 6/9 and candidates indistinguishable under current inputs in 4/9 (categories overlap). A single-node afterstate cannot reveal an intact joint cut, and 1-WL-equivalent inputs cannot be resolved by the present encoder. The audit is not a complete causal explanation; richer features are needed.

Q4 : Why not use a consistent AUC metric? We agree. Appendix K.1 recalculates Eq. (1) from released removal orders for eight of nine quoted methods: changes are at most 0.4 normalized points per graph and 0.2 in domain means, with unchanged average ranks. We will use these values in Table 1 and clearly flag the ninth method. Without its removal order, the original aggregate Simpson score cannot be converted reliably to Eq. (1). We respectfully ask the reviewer to reconsider the assessment in light of the equal-time search results and objective-matched control, while retaining the limitations in runtime, theory, and domain transfer.

Dear Reviewer, We sincerely appreciate your time and valuable feedback on our manuscript. We have provided a detailed point-by-point response to your comments and would be grateful for any further feedback you may have. We fully appreciate your busy schedule and kindly invite you to let us know if any additional explanations or supporting materials are required. Thank you again for your time, consideration, and continued support.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.