EXACT–LEARNED DOOB CONTROL FOR NETWORK DISMANTLING UNDER STRUCTURAL SHIFT

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.