acceptodds
Withdrawn from ICLR 2027

NETBREAKER: Benchmarking Network Dismantling across Objectives, Scales, and Topologies

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Network dismantling seeks to fragment a network with as few node removals as possible, which is widely applied in vulnerability analysis, epidemic containment, and infrastructure protection. Although learning-based methods have become increasingly prominent, their progress remains difficult to assess because existing studies differ in method coverage, datasets, evaluation criteria, and experimental protocols. Thus, we introduce NETBREAKER, a comprehensive benchmark designed for the learning era of network dismantling. NETBREAKER organizes 30 methods (18 non-learning and 12 learning-based) under a common taxonomy and evaluates them on 185 networks from eight unified domains, ranging from 14 to 1.69 million nodes. To enable fair comparison, heterogeneous method outputs are converted into node removal sequences and assessed under a unified execution protocol. The evaluation covers four complementary dimensions: target-based effectiveness, trajectory-based effectiveness, structural diagnostics, and applicability & computational efficiency. Extensive experiments show that current learning-based methods do not consistently outperform strong non-learning approaches, while exposing substantial differences in effectiveness, scalability, and efficiency across network conditions and evaluation perspectives. NETBREAKER provides a reproducible basis for measuring progress and developing reliable, scalable, and computationally efficient network dismantling methods.

Primary area:
datasets and benchmarks
Keywords:
complex network, network dismantling, datasets

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_kYUgOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The authors propose NetBreaker, a common benchmark for network (graph) dismantling algorithms. The benchmark integrates 30 methods, including classical, recent and learning-based approaches, and is designed to be extended in the future. The accompanying evaluations cover 185 network instances from various sources and domains, and cover multiple dimensions: number of node removals, dismantling trajectories, connectivity fragmentation diagnostics, completion coverage and computational resource usage. The paper’s novelty mostly lies in the integration of the algorithms into a common pipeline and their benchmarking, as the authors include recent contributions in the field. However, prior work, acknowledged by the authors in their references, already provides an open-source and extensible platform for this purpose (and to which at least two implementation sources point in Supplementary Tables 7 and 8) and covers most of the same evaluation dimensions. Thus, the paper appears to offer an empirical contribution rather than a new methodological framework. I detail my concerns about the evaluation protocol in the following sections.

Critical strengths

None. While the integration of many established and recent methods within a common benchmarking pipeline, together with their evaluation on a moderately large collection of network instances, is potentially useful to the community, I do not consider this a critical strength supporting acceptance, because this contribution overlaps with existing open-source infrastructure and previously established evaluation protocols.

Critical weaknesses

My major concerns relate to two critical weaknesses: the evaluation protocol and the dataset characterization and taxonomy.

Table 2 reports the “failure-aware aggregate comparison”, the “medians over successful dataset-level evaluations”, and the coverage (i.e., the fraction of successfully attacked instances per method). The ranks of the benchmarked methods are penalized when they fail, yet it is unclear whether two failing methods are assigned the same penalized rank. Moreover, no information is disclosed about the hardware used or about the reasons for unsuccessful runs. This is particularly concerning because, in lines 993-999, the authors acknowledge that “The evaluated methods rely on heterogeneous CPU and GPU implementations, and their recorded running times may include different combinations of inference, graph-specific adaptation, search, and post-processing.” Methods like Ensemble-GND(R) and LLM4CN have low coverage, which affects their final ranks. Furthermore, the medians of quantities such as \rho and the trajectory AUCs may be affected by selection bias since each method’s medians are computed only over its successful runs. In practice, OOMs and timeouts often occur on large networks where many algorithms tend to underperform, which could lead to biased conclusions. I also note that measuring wall-clock time and peak memory to compare the intrinsic computational efficiency of the algorithms is problematic, these measures are heavily affected by the implementation and by the environment. Yet I recognize that the heterogeneity and complexity of some algorithms make a rigorous comparison difficult.

The network instances are roughly described: they are primarily divided in three broad size categories (i.e., small, with less than 1k nodes, medium, below 50k nodes, and large, above 50k nodes) and some other simple statistics (range of number of nodes and edges, median average degree, and number per domain in each size group) are reported in the SI, but they are clearly not enough to characterize rigorously the instances and the benchmark dataset. Line 702 states that an “accompanying dataset registry” provides additional information about the dataset, but no such registry is available as supplementary information with the submission. The network instances are also organized according to a proposed domain taxonomy, which is only described in the SI. However, the taxonomy is insufficiently justified, and no examples of the inconsistencies attributed to previous classifications are reported. For example, crime and botnet networks are grouped under the same broad “Security, Crime, and Covert” domain without a clear justification for treating such heterogeneous systems as one category. If this domain taxonomy is intended as a contribution, the authors should make it more rigorous and explain why this categorization should be preferred to the classifications used in previous studies and/or inherited from established repositories such as KONECT, SNAP, Network Repository from which the paper draws several instances.

Questions for authors

None. My assessment is based on information already available in the manuscript and my concerns relate to the soundness of the evaluation protocol.

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

This paper studies the problem of network dismantling, where the goal is to fragment a network by removing as few nodes as possible. The authors then introduce NETBREAKER, a benchmark that evaluates 30 learning-based and non-learning methods across 185 networks. The NETBREAKER framework standardizes graph preprocessing, converts heterogeneous method outputs into node-removal sequences, and evaluates dismantling effectiveness, structural changes, computational cost, and completion coverage. The results suggest that existing learning-based methods do not consistently outperform strong non-learning approaches, with relative performance varying across evaluation metrics and network

Critical strengths
  1. An unified framework that evaluates learning-based and non-learning network dismantling methods using common graph preprocessing and evaluation criteria is useful for assessing progress in the field of network dismantling.
  2. The paper is relatively well-written and easy to follow, with a clear organization around four research questions.
  3. Some findings are useful, namely that low median runtime does not necessarily indicate good scalability when a method fails to complete many large networks and that method rankings depend on the evaluation metric. These observations highlight the importance of reporting runtime alongside completion coverage and assessing both target-based and trajectory-based performance.
Critical weaknesses
  1. My first concern is about the limited novelty and depth of the analysis. The contribution mainly consists of collecting existing networks, integrating existing methods, and evaluating them through a shared framework. For example, RQ1 concludes from Table 2 that learning-based methods do not consistently outperform strong non-learning approaches. However, similar observations already exist: Artime et al. (2024) show that the best-performing method varies across networks and domains, while LGD-NA (Adler et al., 2026) demonstrates strong performance of non-learning approaches against learning-based baselines. This makes it unclear what additional insight the broader evaluation provides. A more valuable insight would be determining where and why learning-based methods underperform.

  2. My second concern is about the limited analysis of network topology. Despite having “topologies” in the title, the paper mainly compares methods across application domains and network sizes ( Figure 3 and Table 10). While Section 3.1 reports properties such as average degree, clustering, and assortativity, the paper does not examine how these properties relate to method performance.

  3. Despite being a key result for a benchmark paper, Table 2 provides no uncertainty estimates. For stochastic methods, such as Ensemble-GND, the manuscript does not specify whether results are averaged across seeds. Furthermore, the manuscript does not specify the timeout and memory limits or the pre-declared skip criteria. Since these choices might affect coverage and failure-aware rankings in Table 2, it is difficult to assess whether the observed differences reflect algorithmic limitations or choices in the experimental protocol.

Questions for authors

See Weaknesses

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

NETBREAKER assembles a benchmark for network dismantling on simple, undirected, unweighted graphs. It evaluates 30 methods and variants - 18 non-learning and 12 learning-based or AI-guided - on 185 processed graphs, using a shared removal-sequence interface. Evaluation covers the removal fraction needed to reduce the largest connected component to a prescribed threshold, connectivity trajectories, structural diagnostics, completion coverage, and observed computational cost. The reported results identify BPD, CoreHD, and Min-Sum as strong target-based baselines and Explosive Immunization as the strongest LCC-AUC baseline, while learning-based methods exhibit varying quality-coverage trade-offs. The contribution is primarily benchmark integration and comparative empirical evidence, rather than a new dismantling algorithm.

Critical strengths
  1. A useful breadth of method integration with explicit applicability reporting. Thirty methods and variants are assessed on 185 graphs, and non-completion is retained in the comparison rather than silently discarding difficult instances (Sections 3-4, Table 2). This is consequential for evaluating whether a method is practically usable beyond the networks on which it succeeds. The manuscript also explicitly labels CNT and AGNN as proxy critical-node methods rather than treating them as direct dismantling optimizers.

  2. A valuable separation of complementary evaluation questions. The paper distinguishes the number of interventions needed to achieve a target from accumulated connectivity and structural transition diagnostics. Table 11 and Figure 5 demonstrate substantial rank changes across these views. This can improve evaluation practice, and the authors appropriately state that transition magnitudes are not independent measures of overall superiority and that their runtime observations are not hardware-independent complexity claims.

Critical weaknesses
  1. The manuscript does not provide a sufficiently auditable execution specification for its central benchmark claims. Completion coverage and failure-aware ranks drive the conclusions, yet the paper does not enumerate numerical runtime/memory/scale limits, method-specific skip rules, exact checkpoint/configuration identities, run repetitions, or the treatment of ties and different failure categories. Section 3.2 points to Appendix B for configurations, but that appendix mainly provides descriptions and implementation links. Moreover, Table 8 and Appendix B explicitly state unresolved provenance/completeness for LLM4CN and incomplete data/checkpoint dependencies for AGNN, without explaining how the evaluated versions were validated against the intended methods. I do not require all architectures to be retrained under an identical budget: the stated deployable-pipeline comparison is legitimate. I do require a verifiable record of exactly which pipelines and resource constraints produced these results.

  2. The comparative conclusions need robustness analyses that separate solution quality, non-completion, and cost selection effects. Table 2 reports metric medians over successful networks, while superscripts reflect ranks over all networks; Figure 4 similarly pairs failure-aware ranks over 185 graphs with runtime/memory medians over each method's successful subset. Reporting coverage is helpful, but these summaries still describe different instance populations. Consequently, the apparent quality-cost frontier and the extent to which learning methods lag can depend on which graphs were skipped or failed and how failures are ranked. The manuscript does not show paired common-support comparisons, sensitivity to failure-ranking/skip policies, or uncertainty for stochastic runs/aggregate ranks. This does not invalidate the observed leaderboard, but it limits the evidence for general comparative guidance.

Questions for authors

See the Weaknesses part; if they are resolved, I will consider increasing my score.

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

Related papers

Discussion (0)

Sign in to comment.