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