Network dismantling asks which few nodes of a network to remove so that it falls apart: the largest connected piece shrinks, or the dense core collapses. It is used to plan epidemic interventions, disrupt criminal networks, and find weak points in power grids. Learned dismantlers, which are graph neural networks (models that score each node by repeatedly passing messages between neighbours), now beat classical rankings on graphs with up to a million nodes. All of them were designed by hand and benchmarked with abstract runtimes. The literature that optimizes neural networks for real devices, hardware-aware neural architecture search, has never touched dismantling. The obvious bridge would take a hardware-aware search method for graph neural networks and point it at a dismantling model. We argue this misses where the cost actually sits. A dismantler is a sequential policy. It scores nodes, removes some, and scores again on a smaller graph. Its wall-clock cost and energy depend as much on how often it rescores, how many message-passing rounds it runs per score, and how cost grows with graph size as on which layers it uses.
We propose to search over complete removal policies, with the network's operators and its removal schedule chosen jointly, under hard latency or energy budgets on real devices. A cost model that depends on the size of the input graph makes this possible. The outcome is a measured Pareto front: the best dismantling quality reachable at each time or energy budget, across hardware from a Raspberry Pi to a server GPU. The front also answers whether learned dismantlers are ever worth their cost compared with cheap local rules.
Core Claim
The quality–cost trade-off of a learned dismantler is controlled mainly by three things: its rescoring schedule, its message-passing depth, and the way its per-step cost scales with the number of nodes and edges. The choice of layer type matters much less. A search that treats these as first-class choices, and enforces device budgets as hard constraints rather than penalties, should find policies that dominate both hand-designed neural dismantlers and the fastest heuristics at intermediate budgets. If cheap heuristics turn out to dominate at every budget, the same study will show that cleanly, and that is also worth knowing.
To make the cost side concrete, consider a policy $a$ run on a graph $G$. Let $t$ index rescoring rounds, let $|V_t|$ and $|E_t|$ be the nodes and edges remaining at round $t$, and let $\alpha_o, \beta_o, \gamma_o$ be device-specific coefficients for operator $o$. The modelled cost is
$$T(a,G)=\sum_{t\in \mathcal{S}(a)}\sum_{o\in a}\left(\alpha_o |V_t|+\beta_o |E_t|+\gamma_o\right),$$
where $\mathcal{S}(a)$ is the set of rescoring rounds the policy's schedule triggers. The linear form is an assumption we will test. It reflects the fact that sparse aggregation is memory-bound in edge count and the dense combine step is compute-bound in node count. Quality is measured by the area $R(a,G)$ under the curve of largest-component size against fraction of nodes removed; lower is better. The search solves
$$\min_a \; \mathbb{E}_{G}\,R(a,G)\quad \text{subject to}\quad T(a,G)\le B(|V|) \text{ for all evaluation graphs},$$
where $B(|V|)$ is a time or energy budget that may grow with graph size.
Research Program
What motivates this, and what is missing. Four learned dismantlers set the quality bar.
- MIND trains an attention-based network with actor-critic reinforcement learning, starting from featureless inputs, and scales to 1.4 million nodes. It keeps a "message iteration profile" of node states across rounds, so its depth is an explicit, costly choice.
- SmartCore pairs a GraphSAGE encoder that has a virtual global node with a Double DQN decoder. It targets accumulated 2-core size.
- NIRM trains a graph attention network on exhaustively solved 20–30-node graphs.
All three fix their architecture by hand and report no device measurements. SmartCore's timings are in "units of time."
At the other end of the cost spectrum, LGD-NA replaces learning with local geometric rules, such as common-neighbour dissimilarity, written as matrix products. On GPU it matches betweenness centrality and runs much faster. Its rules are fixed, and it does not study constrained devices.
The hardness results explain why learned and greedy methods are the only practical route. Dismantling is a collective problem whose scores shift after every removal (Network dismantling). Core-based variants (Network Robustness via Global k-cores) admit no constant-factor approximation. That shifting is exactly what makes rescoring frequency a real quality–cost knob rather than an implementation detail.
What supplies the method. - HGNAS splits graph neural network layers into sample, aggregate and combine operators, and learns a latency and memory predictor. That predictor needed about 30,000 on-device profiles per device and was built for fixed-size inputs. Dismantling inputs range across orders of magnitude, so we replace it with the size-parametric model above. - ConNAS handles constraints as hard boundaries, reporting 100% constraint satisfaction on CNN search spaces. We adopt that philosophy. - DUCCIO uses margin losses that activate only on violation, which we use when several budgets apply at once. - NATS-Bench found regularized evolution to be a robust search baseline.
Because dismantling quality is non-differentiable and policies are sequential, we use constraint-filtered regularized evolution, not differentiable search. A candidate that violates the cost model is repaired toward feasibility before evaluation, in the spirit of ConNAS's direction-to-feasibility step.
The search space. Each candidate is assembled from four groups of choices.
- Operators: HGNAS-style sample, aggregate and combine operators, plus parameter-free LGD-NA and degree operators. Including these lets the search choose a heuristic or a hybrid.
- Depth and pooling: message-passing depth from 1 to 8, with or without MIND-style iteration profiles, and with or without a virtual global node.
- Removal schedule: the fraction of nodes removed per rescoring round, from a single node up to 5% of remaining nodes, and optionally a fraction that grows as the graph shrinks.
- Numeric precision: float32, float16 or int8.
Making candidate evaluation affordable. Training every candidate with reinforcement learning would be prohibitive. Instead, candidates are trained by imitation for a fixed short budget. The supervision combines exact optima on tiny graphs, following NIRM, with removal rankings from a teacher on mid-size synthetic graphs. The teacher is MIND or iterated betweenness, whichever is stronger on validation. We then check that imitation-trained rankings agree with briefly reinforcement-tuned rankings on a held-out sample of candidates. If the Kendall correlation falls below 0.7, we fall back to short reinforcement fine-tuning for the top decile.
Building the cost model. For each device we profile each operator on about 10 graph sizes. We then test whether summing these per-operator costs predicts end-to-end policy cost within 15% on held-out graphs. HW-NAS-Bench showed that FLOPs-to-latency rank correlation can drop to 0.18 on an Edge TPU, so we report the correlation for both FLOPs and our model. Where additivity breaks down, we add a small learned correction.
Baselines
Naive reference. The do-nothing reference is adaptive high-degree removal: remove the highest-degree node, recompute degrees, repeat. On every device it is nearly free. Any learned policy that cannot beat it at equal measured time has no reason to exist, so it anchors the low-budget end of every front. Static degree and iterated betweenness are run in the same harness to bracket the quality range.
Strongest learned method. This is MIND, run from the authors' released configuration. We sweep its message-iteration count and also run it with batched removal, so it is not penalised for a schedule it was never tuned for. No reported result was found on Lacuna for MIND's numerical gains, so we measure it ourselves. NIRM and SmartCore run in the same harness. We check our reproduction against published figures: NIRM reports an average of 24.76% of nodes removed to fully dismantle its 15 real networks, and SmartCore reports an accumulated 2-core size of 0.0660 on Digg.
Strongest fast method. This is LGD-NA's common-neighbour-dissimilarity rule. It reports matching node betweenness while being 63× faster on GPU, and a 130× GPU-over-CPU speedup on the ATLAS benchmark. We port it to every target device.
Fair comparison. All methods receive the same evaluation graphs and the same per-device measurement harness. Every learned baseline gets the same training-graph distribution and the same GPU-hours of tuning as the search's total budget. Beating a baseline means one of two things on held-out ATLAS domains, with confidence intervals over graphs: lower area under the largest-component curve at equal measured latency or energy, or equal quality at lower cost by at least 2×.
Ablations. - Schedule ablation: the search runs with the removal schedule frozen to one node per round. This isolates whether the schedule is the key ingredient. - Cost-model ablation: the search runs with HGNAS's fixed-size predictor in place of the size-parametric model. - Learned-operator ablation: the search runs with learned operators removed, leaving only heuristics and schedules.
Why not just…?
Why not just use LGD-NA or adaptive degree removal and skip learning? This is the most serious threat. LGD-NA already matches betweenness at a fraction of its cost. Our design does not argue around it: these rules sit inside the search space, so if they dominate, the search will return them. Comparing the full search against the heuristics-only ablation settles the question directly. A front where learned operators add nothing at any budget would be reported as the main finding.
Why not just run HGNAS on a dismantling objective? HGNAS's predictor assumes inputs of roughly fixed size and costs about 30,000 profiles per device. It also has no notion of rescoring rounds, so it cannot see that halving rescoring frequency can save more time than any operator swap. The cost-model ablation and the schedule ablation each measure what this omission costs.
Why not just tune MIND's iteration count and batch size by grid search? This is plausible, and it may capture much of the gain. That is why MIND is swept along exactly these knobs with an equal tuning budget. The proposal earns its place only if searched policies beat this tuned MIND front. We expect the advantage to come at small-device budgets, where dropping attention for cheaper aggregation matters most.
Why not just quantize and prune an existing dismantler? Hardware-aware compression, as in Balaskas et al., reduces cost per forward pass but leaves the number of passes untouched. We include int8 and pruned MIND as a baseline. Precision is also a search dimension, so the comparison is direct.
Proposed Experiments
Data. Search uses synthetic training graphs of the kind used by MIND and SmartCore. Validation uses a fixed subset of ATLAS domains. Testing covers three sets:
- the remaining ATLAS networks, grouped by domain;
- the SNAP graphs HI-II-14, Digg, Enron and Epinions, scored with accumulated 2-core size;
- the UCTE grid with 1,254 buses, where results are compared against spectral greedy line removal from the power-grid bounds work.
Devices. Raspberry Pi 4, Jetson TX2, a desktop CPU and a server GPU. These match the edge platforms used in HW-NAS-Bench and HGNAS. Energy is measured wherever power rails are accessible.
Decisive checks. 1. Does the size-parametric cost model rank policies by measured latency much better than FLOPs do? 2. Do searched policies dominate the tuned-MIND and LGD-NA fronts on held-out domains, on the edge devices specifically? 3. Does the policy that is optimal on Jetson differ from the one optimal on the Pi, and does swapping them cost measurable quality at a fixed budget? HW-NAS-Bench found about a 50% device-specific latency gap for CNNs; we test whether a comparable gap exists here. 4. Does freezing the schedule remove most of the gain?
If the answer to the last check is yes, the contribution is a principled account of removal scheduling under compute budgets rather than an architecture result. That would still be a clear, publishable claim.
References
- Learning Network Dismantling Without Handcrafted Inputs
- Deep Reinforcement Learning for Network Dismantling: A K-Core Based Approach
- Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
- Latent Geometry-Driven Network Automata for Complex Network Dismantling
- Network dismantling
- Network Robustness via Global k-cores
- HGNAS: Hardware-Aware Graph Neural Architecture Search for Edge Devices
- Constraint-guided Hardware-aware NAS through Gradient Modification
- Enhancing Neural Architecture Search With Multiple Hardware Constraints for Deep Learning Model Deployment on Tiny IoT Devices
- NATS-Bench: Benchmarking NAS Algorithms for Architecture Topology and Size
- HW-NAS-Bench: Hardware-Aware Neural Architecture Search Benchmark
- Hardware-Aware DNN Compression via Diverse Pruning and Mixed-Precision Quantization
- Topological vulnerability of power grids to disasters: Bounds, adversarial attacks and reinforcement