Latent Geometry-Driven Network Automata for Complex Network Dismantling
Authors: Thomas Adler
Marco Grassia
Ziheng Liao
Giuseppe Mangioni
Carlo Vittorio Cannistraci
Venue: ICLR 2026 Poster (2026)
Keywords: network robustness
network dismantling
network geometry
network science
complex systems
network automata
graphs
network topology
Primary area: learning on graphs and other geometries & topologies
TL;DR: Latent Geometry-Driven Network Automata dismantles networks by estimating effective link distances on the latent manifold via local rules, outperforming all existing methods on 1,475 real-world networks and runs efficiently on large systems via GPU.

Abstract: Complex networks model the structure and function of critical technological, biological, and communication systems. Network dismantling, the targeted removal of nodes to fragment a network, is essential for analyzing and improving system robustness. Existing dismantling methods suffer from key limitations: they depend on global structural knowledge, exhibit slow running times on large networks, and overlook the network’s latent geometry, a key feature known to govern the dynamics of complex systems. Motivated by these findings, we introduce Latent Geometry-Driven Network Automata (LGD-NA), a novel framework that leverages local network automata rules to approximate effective link distances between interacting nodes. LGD-NA is able to identify critical nodes and capture latent manifold information of a network for effective and efficient dismantling. We show that this latent geometry-driven approach outperforms all existing dismantling algorithms, including spectral Laplacian-based methods and machine learning ones such as graph neural networks and . We also find that a simple common-neighbor-based network automata rule achieves near state-of-the-art performance, highlighting the effectiveness of minimal local information for dismantling. LGD-NA is extensively validated on the largest and most diverse collection of real-world networks to date (1,475 real-world networks across 32 complex systems domains) and scales efficiently to large networks via GPU acceleration. Finally, we leverage the explainability of our common-neighbor approach to engineer network robustness, substantially increasing the resilience of real-world networks. We validate LGD-NA's practical utility on domain-specific functional metrics, spanning neuronal firing rates in the Drosophila Connectome, transport efficiency in flight maps, outbreak sizes in contact networks, and communication pathways in terrorist cells. Our results confirm latent geometry as a fundamental principle for understanding the robustness of real-world systems, adding dismantling to the growing set of processes that network geometry can explain.

LATENT GEOMETRY-DRIVEN NETWORK AUTOMATA FOR COMPLEX NETWORK DISMANTLING
Thomas Adler" 1 MMMro Grassia "Ziheng Liao Giuseppe Mangioni"* Carlo V. Cannistraci'1.24
Center for Complex Network Intelligence (CCNI), Tsinghua Laboratory of Brain and Intelligence (THBI, Department of Psychological and Cognitive Sciences
*Deparmment of Computer Science and Technology, Tsinghua University *Department of Electric, Electronic and Computer Engineering, University Catania *Department of Biomedical Engineering, Tsinghua University
thomas 02 02990mmai1. com, marco grassiagunict. it, 1zhalpha@gmail. com, giuseppe iaaaniioniuunicte it, kalokagathos. a com
'These authors contributed equally to this work.
'Corresponding authors.
ABSTRACT
Complex networks model the structure and function of critical technological, bio- logical, and communication systems. Network dismantling, the targeted removal of nodes to fragment a network, is essential for analyzing and improving system robustness. Existing dismantling methods suffer from key limitations: they depend on global structural knowledge, exhibit slow running times on large networks, and overlook the network's latent geometry, a key feature known to govern the dynamics of complex systems. Motivated by these findings, we introduce Latent Geometry-Driven Network Automata (LGD-NA), a novel framework that lever- ages local network automata rules approximate effective link distances between interacting nodes. LGD-NA is able to identify critical nodes and capture latent manifold information of network for effective and efficient dismantling. We show that this latent geometry approach outperforms all existing dismantling algorithms, including spectral Laplacian-baas based methods and machine learning ones such as graph neural networks. We also find that simple Nommon-neighbor network automata rule achieves near state-of-the-an performance, highlighting the effectiveness of minimal local information for dismantling. LGD-NA is extensively validated on the largest and most diverse collection of real-world networks date (1,475 real-world networks across 32 complex systems domains) and scales efficiently to large networks via GPU acceleration. Finally, we leverage the ex- plainability of our common-nee -niihbor approach to engineer network robustness, substantially increasing the resilience of real- world networks. We validate LGD- NA's practical utility domain-specifie functional metries, spanning neuronal firing rates in the Drosophila Connectome, transport efficiency in flight maps, outbreak sizes in contact networks, and communication pathways in terrorist cells. Our results confirm latent geometry as a fundamental principle for understanding the robustness of real-world systems, adding dismantling the growing set of processes that network geometry can explain.
INTRODUCTION
Complex networks are the backbone our modern world, from the biological pathways within cell to global financial and transportation systems (Newman 2003). While the interconnected nature of these systems is often a source of efficiency and strength, it also introduces profound vulnerabilities. A localized failure can be absorbed, it trigger cascade of disruptions leading to systemic collapse. Understanding this fragility is crucial, as the consequences are far-reaching: targeted disruptions compromise cellular function in metabolic networks, dictate the spread of

---

virus through social fabric, cause catastrophic blackouts in power grids and failures in financial markets (Artime et al. 2024 Albert et al. 2000). The formal study of these vulnerabilities is known as network dismantling. It addresses fundamental question: What is the most efficient way to fragment a network by removing a minimal set of nodes or links, to disrupt its structural integrity and functional capacity? Answering this question is essential not only for predicting the impact of malicious attacks but, more importantly, for designing robust and resilient systems that can withstand them. The task of dismantling serves a dual purpose. It determines whether a system is robust and how to reinforce desirable networks, for example preventing system failure in flight network or security compromises in internet infrastructure. Conversely, it reveals how to disrupt undesirable systems, severing communications in terrorist cells or halting the spread of an epidemic. Efficient network dismantling is challenging because identifying the minimal set of nodes for optimal disruption is an NP-hard problem: no known algorithm can solve it efficiently for large networks (Artime et al.) 2024). forcing the field to rely on heuristic approximations. This difficulty arises not only from the prohibitively large solution space but also from the structural complexity of real-world networks, which exhibit heterogeneous, fat-tailed connectivity (Barabási & Albert 1999 [Broddo & Clauset 2019: Voitalov et al.) 2019 (Serafino et al.] 202T), modular and community structures (Newman
2012). hierarchies (Ravasz& & Barabási 2003 Clauset et al.) 2008), higher-order structures (Battiston
al. 2021 Lambiotte et 2019), and a latent geometry (Muscoloni et al.
2017
Wu al. 2015
Boguña et al.) 2021; Krioukov et al. 2010 Serrano et al. 2008
Node Betweenness Centrality (NBC) is a network centrality measure (Freeman 1977 that quantifies the importance of a node in terms of the fraction of the shortest paths that pass through it. NBC-based attacks, where nodes are removed in order of their betweenness centrality, considered one of, if
not the best, method for network dismantling (Engsig et al. 2024 [ervedio et al., 2025 Motter & Lai 2002, Holme et al.] 2002). However, like many other dismantling techniques, requires global knowledge of the entire network topology, and its high computational cost limits its scalability to large networks. These limitations are shared by many other state-of-the dismantling methods, which additionally rely black-box machine learning models, and are rarely validated across large, diverse sets of real-world networks (see Tables 16 5)..
Latent geometry has been recognized as key principle for understanding the structure and complexity of real-world networks. Recent works in network science suggest that the latent geometry of complex networks could explain critical network characteristics such mmall-worldness, degree heterogeneity.
clustering, and navigability, and drives critical processes like efficient information flow (Boguñá et al. 2021: 2009: Kleinberg] 2000 Wu et al. 2015, /Serraoo et al., 2008 Krioukov et al. 2010 Muscoloni & Cannistraci 2019 2018a). Work by Muscoloni et al. (2017) revealed that betweenness centrality is a global latent geometry estimator: it approximates node distances in an underlying geometric space. They also introduced Repulsion-Attractio network automata rule 2 (RA2), local latent geometry estimator that uses only first-neighbor connectivity. RA2 performed comparably to NBC in tasks such as network embedding and community detection, despite relying solely on local information. This raises the first question: can latent geometry, whether estimated globally or locally, guide effective network dismantling? If complex systems run on a latent manifold, estimating may offer a more efficient way to disrupt connectivity. The second question concerns efficiency. While both NBC and RA2 have O(Nm) complexity (N as the number of nodes and m the number of links), RA2 is significantly faster in practice because its local computations avoid NBC's large computational overhead. This motivates exploring whether local latent geometry estimators can match the dismantling performance of global methods like NBC while offering lower running time.
Motivated by these questions, introduce the Latent Seoomerry-Drivee Network Automata (LGD- NA) framework. Our first and primary contribution is the principle of (1) Latent Geometry-Driver (LGD) dismantling, where methods estimate effective node distances on a network's latent manifold to expose critical structural information. Specifically, our (2) LGD-NA framework uses local network automata rules to approximate these geometrie distances; a node's 's summed distance to its neighbors estimates how critical it is for dismantling. Within this framework, we discovered that (3) simple nommon-neighhor- based rule, which we term Common Neighbor Dissimilarity (CND), is highly effective, achieving performance close to the state-of-the-an method, NBC. We prove the effectiveness of our approach through (4) comprehensive experimental validation on an ATLAS of 1,475 real- world networks across 32 complex systems domains, the largest and most diverse collection to date, showing that LGD-NA consistently outperforms all other existing dismantling algorithms, including machine learning and spectral Laplacian- based methods. To enable dismantling at large scales,
2

---

A
network Unwwaighted Natwwork
Disimillattyy Natwork
Node strength
estimation
Acheo
Parma
Manudeer
Ji (666))
1-C
A40m
Inbatarn
Optional
H
Semserted Network
Reinsertion
Dismantteed
Audie
Clorpate rude-rove
Brauscsin
AC Mode joar the
PHEBUTE
Morore
E2 Nods that connacts
Magisha
Grvadest LCE Increase
Repeat until Shoedholdd IHR
Figure 1: Overview of the LGD Network Automata framework. A: Begin with an unweighted and undirected network. B: Estimate latent geometry by assigning weight Vij each edge between nodes and j using local latent geometry estimators. C: Construct a dissimilarity-wegghe based on these weights. D: Compute node strength as the sum of geometric weights to all neighbors in (i): = ())N() V/j E-F: Perform dynamic dismantling by iteratively computing node strengths, removing the node with the highest 8; and its edges, and checking whether the normalized size of the largest connected component (ICC) has dropped below threshold. G-H (optional): Reinsert dismantled nodes using selected reinsertion method.
we implement (5) GPU-acceleration for LGD-NA, yielding remarkable rumning time advantages over methods like NBC. Finally, using the explainability of our CND measure, we introduce new method for (6) engineering network robustness, substantially reducing the effectiveness of the best dismantling methods. We further validate the practical utility of our dismantling framework and robustness engineering method by demonstrating their impact domain-speciff functional metrics, including neuronal firing rates in the Drosophila Connectome, flight map efficiency, epidemic sizes, and communication reachability in terrorist cells.
RELATED WORK
Latent Geometry of Complex Networks. Many real-world networks are shaped by latent geo- metric manifolds of the complex systems that govern their topology and dynamics. These hidden geometries explain essential structural features such small-worldness,, degree heterogeneity, cluster- ing, and community structure (Boguña et al., 2022]] Wa et al. 2015 Serrano et al.) [2088] Muscoloni
Cannistraci] 2018a| Zuev al.] 2015 Muscoloni Cannistraci 2018b Muscoloni et al. [2017). The underlying metric space is not only descriptive but functional: it facilitates efficient routing and navigation with limited global knowledge (Kleinberg 2000, Boguñá et al.) 2009 Krioukov al.. 2010; Muscoloni & Cannistraci 2019). Such properties emerge consistently across diverse systems, including biological, social, technological, and socio-ccological networks (Boguñá et al. 2021 Wu et al. 2015). Latent geometries also enable predictive modeling of dynamical processes such as network growth (Papadopoulos et al. 2012 Muscoloni & Cannistraci 2018b a), and epidemic spreading (Brockmann & Helbing 2013
Latent Geometry Estimators. Latent geometry estimators assign edge weights to approximate pairwise distances linked nodes in the hidden geometric manifold. Among them, network automata rules based on the Repulsion-AAtractin proximity in the latent space (Muscoloni et al. 2017). ). RA is grounded in the theory of network navigability (Boguñá et al. 2200)), which posits that nodes with many non-overlapping neighbors tend to occupy distant regions in the latent space. Edges between such nodes receive higher dissimilarity scores due to strong repulsion, while those with many common neighbors scored lower due
(RA) criterion use only local topological information infer
3

---

Table 1: Number of real-world networks lested by dismantling algorithms (see Ta- ble 10
Table 2: Summary of real-world networks tested in this paper (see Table
Field
Sublields
Types
Networks
Algorithm
Year
Networks
Ref.
Biomolccular
PPL Genetic, Metabolic,
27
Callective
Influence
2016
2
Merune et al. 2016)
Molecular, Transcripiion
(CT)
Brain
Connectome
529
CorelII
2016
12
Zilebonväel et al.
Covert
Covert, Terrorist
89
2016)
Foodweb
Foodweb
Explosive tion (FI)
Immuniza-
Clusella
(0116)
Infrastructuee
7
Flight, Nautical, Power grid, Rail, Road, Subway,
314
Min Sum (MS)
2016
Braunsiein ct al. 2016)
Trade
Intemet
Internet
206
GND
2019
10
Ren et al 2019)
Misc
Citation, Copurchusing,
38
Game, Hiring. Lexical, call. Sottware,
Resilience Contrality
2020
Zhang et al 20200
Vote
57
al Grassin & Man-
Social
7 Coanthorstip. Collabo- ration, Contact, Email. Friendship. Social work, TTrust
201
2021)
CoreGDM
2023
15
gioni 2023
Domirank Centrality
2024
6
Engsig al. (20-4]
Total
32
1,475
Fitness Centrality
2025
5
Servedio et al.
2025)
L.DDNAA
2025
1,475
to attraction. RAI and RA2 are network automata rules for approximating linked nodes' pairwise distances on the latent manifold of a complex network. These rules are categorized as network automata because they adopt only local information to infer the score of link in the network without the need for pre-training of the rule. Note that RAI and RA2 are predictive network automata that differ from generative network automata, which are rules created to generate artificial networks (Barabási & Albert 1999 Papadopoulos et al. 2012 Muscoloni & Cannistraci 2018b). They were introduced to serve pre-weighting strategies for approximating angular distances associated with node similarities in hyperbolic network embeddings. RA2 performed slightly better than RAI, for this reason we will only consider RA2 in this study, RA2 defines dissimilarity between nodes i and] as:
RA2(i, 1 + e1 + ej :ej
1+ CN
where CN₃y is the number common neighbors nodes and j. and e; and ej are the external degrees of and j, representing the count of neighbors of i and that are not involved in the common neighbors interactions. global latent geometry estimator. By comparing it with RA2, they demonstrated that both global (betweenness centrality) and local (RA) estimators can effectively capture latent geometry, achieving strong results in network embedding and community detection. See Table 3 for comparison of estimators and Figure for illustrative examples. See also Appendix C where we validate the ability of these latent-geometyy estimators in identifying node importance and estimate link distances in networks with a known geometry.
the same work, Muscoloni et also showed that betweenness centrality is
Topological centrality measures. Degree, betweenness centrality, and their variants have all been used in the majority of dismantling studies (Artime et al. 2024), with betweenness centrality having been found be the most effective strategy when applying dynamic dismantling, meaning the scores are recomputed after every step. Degree centrality ranks nodes by their number of neighbors. and betweenness centrality (Freeman) 1977) counts how frequently node lies on shortest paths. Other centrality variants include eigenvector centrality (Bonacich) 1972), which gives higher scores to nodes connected to other influential nodes. PageRank (Page et al. 1999), based on a random walk model, favors nodes that receive many and high-quality links. Beyond these classical measures, several centrality indices have been developed specifically to capture aspects of network resilience. Fitness centrality (Servedio al. 2025), adapted from economic complexity theory, evaluates
4

---

node importance through the capabilities of neighbors while penalizing connections to weak nodes. DomiRank (Engsig et al. 2024) centrality models a competitive dynamic in which nodes gain or lose dominance, centrality (Zhang et al.) 2020), derived from a dynamical systems reduction, quantifies how a node's removal alters the system's resilience (see 3).
importance, based on the relative strength of their neighbors. Resilience
Statistical and Machine Learning Network Dismantling. We focus on network dismantling for targeted attacks, where the goal is to fragment a network as efficiently as possible by removing selected nodes. Message passing-based methods such Belief Propagation-guided Decimation (BPD) (Mugisha & Zhou 2016) and Min-Sum (MS) (Braunstein et al. 2016) use message-passing algorithms to decycle the network and then fragment the resulting forest with tree-breaker algorithm, while CoreHD Zdeeorová et al. 2016) achieves decycling by iteratively removing the highest-degree nodes from the 2-core of the network and also includes a tree-breaker algorithm. Decycling and dismantling are, in fact, closely related tasks, as a tree (or forest) can be dismantled almost opti- mally (Braunstein al. (016)) Generalized Network Dismantling (GND) (Ren et al.] (0199) targets nodes that maximize an approximated spectral partitioning. Collective Influence (CI) (Morone et al., 2016) targets nodes with maximal influence on their neighborhoods, and Explosive Immunization (EI) (Clusella et al.) 2016), uses explosive percolation dynamics. Machine staming-based methods include Graph Dismantling with Machine Learning (GDM) (Grassia et al.) 2021). which trains graph neural networks to predict optimal attack strategies in supervised manner. FINDER (Fan al. 2020b) uses reinforcement learning instead to autonomously learn dismantling strategies without needing labeled data. CoreGDM (Grassia & Mangioni (023) combines ideas from CoreHD and GDM as it attacks the 2-core of the network but uses machine learning models trained on optimal dismantling solutions to guide node removal (see Table 6)
LATENT GEOMETRY-DRIVE NETWORK AUTOMATA
We introduce the Latent Geometry-Drivee Network Automata (LGD-NA) framework. LGD-NA adopts parameter-free network automaton rule, such as RA2, to estimate latent geometric linked node pairwise distances and to assign edge weights based on these geometric distances. Then, computes for each node its network centrality as sum of the weights of adjacent edges. The higher this sum, the more a node dominates numerous and far-apart regions of the network, becoming a prioritized candidate for targeted attack in the network dismantling process. This prioritized node is then removed from the network, and the procedure is iteratively repeated until the network is dismantled (see Figure for full breakdown).
3.1 LATENT DEOMETRY-DRIVEE DISMANTLING
Our first contribution is Latent Geometry- -Divven (LGD) dismantling, where any function can be used to estimate edge weights that represent effective distances between nodes, capturing the network's s underlying latent geometry. These inferred weights are used to construct a dissimilarity-wiigheed network, encoding hidden geometric structure beneath the observable topology and allowing the dismantling process to prioritize nodes according to their geometric centrality in the latent manifold. Latent geometric structures have been shown not only explain key properties of complex networks, but also to support the understanding of dynamical processes such as navigation, routing, and epidemic spreading. Building on the idea that network geometry captures essential structural and dynamical properties of complex systems, LGD dismantling is guided by a geometric intuition about how nodes connect distant regions in the latent space. If two nodes are connected to many different nodes but have little overlap in their neighborhoods, they are likely to be far apart in the network's s latent space. An edge between them, therefore, connects distant regions of the network. A node that has many such edges is central to holding the network together, as it links otherwise separate areas. We propose that removing those geometrically central nodes is an effective way to fragment the network. Muscoloni et al. (2017) also offered evidence that betweenness centrality can be used as a latent geometry estimator, hence, NBC is a global topology centrality measure which can be used for latent geometry-driver dismantling.
5

---

3.2 LGD NETWORK AUTOMATA
Our second contribution is the introduction of a parameter-free network automaton framework for LGD dismantling. In this framework, node importance is estimated by aggregating edge geometric weights into node strengths, and the network is dismantled iteratively by removing the nodes with the highest strength and all their edges. The underlying intuition that nodes that connect to many externll, non-overlapee non-ovelaapinng regions are geometrically central and thus more structurally important, leading to higher strength values. Formally, we begin with an undirected, unweighted network without isolated components. A network automaton rule, such as RA2, that is able to adopt local topology to estimate latent geometry, is applied to assign a weight Viy to the edge between node and node representing the estimated geometric distance between the two nodes. We get dissimilarity- weighted network from these edge weights. The strength s; of node is then calculated by summing the geometric weights of all its edges, that is, the weights to all its neighbors in the set (i):
Σ JEN(0
Vij-
In this paper, we adopt three types of LGD network automata rules. The first rule RA2, which was proposed by Musccloni et al. (2017) for hyperbolic network embedding purposes. The second rule is proposed in this study as an ablation test of the RA2 rule. It is the denominator of the RA2, which we call common neighbors dissimilarity (CND), defined as:
1
Vij CND(1.)) 1+
where CN2, the number of common neighbors between nodes and j. Here, the lower the number of common neighbors two interacting nodes have, the more geometrically distant they are, and thus a higher edge weight is assigned between these two nodes. The rationale for proposing a network automaton rule based only on the common neighbors denominator term of RA2 is to account for the mere attraction between a node and its neighbors. Neglecting the repulsion part associated with the external links (the numerator of RA2) makes sense in a dismantling task because any time compute the common neighbors of seed node with one of its neighbors, we indirectly account for the exclusion of nodes that are not in the topological neighborhood of the seed node. For completeness, we also investigate a third rule as an ablation test of RA2 in which we consider only the external links term in the RA2 numerator, expecting that the mere RA2 numerator should also work, but not as well as the common neighbor-based denominator, Indeed, a previous study offers evidence that common neighbors are among the topological features most associated with community organization and mesoscale network geometry (Bianconi et al. 2014).
4 EXPERIMENTS
4.1 EVALUATION PROCEDURE
We evaluate all dismantling methods using widely accepted procedure in the field of network dismantling (Artime et al.] 2024). For each method, nodes are removed sequentially according to the order it defines. After each removal, Component (LCC), defined as the ratio /.CC(z)/|N) where N is the total number of nodes in the original network and LCC(xz) is the number of nodes in the largest component after x removals. This process continues until the LCC falls below predefined threshold. A commonly accepted threshold in dismantling studies is 10% of the original network size. To quantify dismantling effectiveness, we compute the Area Under the Curve (AUC) of the LCC trajectory throughout the removal process, which records the normalized LCC size at each step. A lower AUC indicates a more efficient dismantling, as it reflects an earlier and sharper disruption of network connectivity. The AUC is computed using Simpson's 's rule. See Figures 6 TO curve.
track the normalized size of the Largest Connected
and 19 for visual illustrations of the LCC
4.2 OPTIONAL REINSERTION STEP
After reaching the dismantling threshold, we optionally perform a reinsertion step to reduce the dismantling cost, defined as the number of removals. Nodes are sequentially reinserted back into

---

the network, time, until the LCC of the remaining network just meets exceeds the predetermined dismantling threshold. Reinsertion can significantly improve dismantling performance; recent work shows that simple heuristics with reinsertion can match outperform complex algorithms that include reinsertion by default (Fan et al. 2020a). As a result, we enforce two constraints to ensure the reinsertion step does override the original dismantling method: (1) reinsertion cannot reinsert all nodes to recompute a new dismantling order, and (2) reinsertion must use the reverse dismantling order as tiebreak. If method includes reinsertion by default, also evaluate its performance without reinsertion for a fair comparison (see Table
4.3 ATLAS DATASET
Our fourth contribution is the breadth and diversity of real-world networks tested in experiments, demonstrating the generality and robustness of LGD-NA across domains and scales. We build an ATLAS of 1,475 real-world networks across 32 complex systems domains, which is the largest and most diverse collection of real-world networks to date used for testing in network dismantling studies. We first test all methods across networks of up 5,000 nodes and 205,000 edges without reinsertion (n = 1,296), and 38,000 edges with reinsertion (n = 1,237). To assess the practical running time of the best performing methods,
evaluate NBC and RA2 even larger networks of up 23,000 nodes and 507,00 7,0000 edges (n = 1,475). Current state-of- offte-of-thh-art dismantling algorithms have been evaluated on no more than 57 real-world networks (see Table D with most algorithms tested on fewer than dozen. Our experiments cover 1,475 networks, representing substantial expansion. A key aspect of our ATLAS dataset the diversity of network types (see Table (2). We test across 32 different complex systems domains, ranging from protein-protein interaction (PPI) to power grids, international trade, terrorist activity, ecological food webs, internet systems, brain connectomes, and road maps. Since fields vary in both the number of networks and their characteristics, we evaluate dismantling methods using a mean field approach, ensuring that fields with more networks do not dominate the overall evaluation. Also, because dismantling performance varies in scale across fields, we compute mean field ranking to make results comparable across domains.
4.4 LGD-NA PERFORMANCE AND COMPARISON TO OTHER METHODS
We compare our LGD-NA framework against the best-performing dismantling algorithms in the literature. Main results are visualized in Figure 2 and full quantitative results, including side-by- side comparisons of absolute AUC and mean-field ranks for all methods and fields, are reported in through 35 the Appendix.
Tables 23
15
10
Mean Rell Ranking
xBC
CNO
RA2
GOM
Dagres
Domtoniiss
Rinats
Rasiffencc
Cle.AR
EiP
Eigenvedoo
NBC.
CND R3
GDM
CoreGoM
Ploness
Domirankeu
Cla
-12
M5
CoreHD
Figure 2: Mean field ranking for each dismantling method without reinsertion (n 1,296; upper panel) and with reinsertion (n 1,237; lower panel), for dynamic dismantling. In the lower panel, subset of the best best-performing methods from each category is paired with their respective best- performing reinsertion strategy. Methods based on latent geometry are shown red. NR denotes variants where the original reinsertion step disabled. Error bars indicate the standard error of the mean (SEM).
First, we find that all latent geometry network automata, NBC, RA2, and its variants, achieve top dismantling performance, both with and without reinsertion. These findings show that estimating the latent geometry of a network effectively reveals critical nodes for dismantling, confirming our first contribution. For each method, we evaluate three reinsertion strategies and report the best
7

---

result. We show in Figure 2 that using different reinsertion methods does not change the mean field ranking of the dismantling methods, and in Figures II and 12 that the improvement in performance varies across fields and reinsertion methods (see Figure ToP. We also adopt dynamic dismantling process for the network automata rules and all centrality measures, where we recompute the scores after each dismantling step, as it consistently outperforms the static variant (see Figure [3] for an example of the improvements for CND and Figure (T). Second, we find that local network automata rules RA2, CND, and RA2num. which adopt only the local network topology around node, are highly effective. In particular, RA2 and its variants consistently outperform all other non-latent geometry- driven dismantling algorithms, including those relying on global topological measures or machine learning. This confirms our second contribution. See Figure 6 for illustrative examples where the local network automata rules outperform NBC. In addition, Appendix validates the ability of our latent geometric distances. Third, we find that the simplest RA2 variant, based solely on inverse common neighbors, which we refer to as common neighbor dissimilarity (CND), achieves the best performance among all local network automata rules. This is our third contribution and demonstrates that even minimal local topology-baa based information useful for effective dismantling. NBC strictly dominates as the top-ranking method across all fields. However, among the second-best performers, the LGD-NA methods lead in the majority of domains: CND ranks second in Internet networks, RA2 in Biomolecular and Brain networks, and RA2 in Covert networks. The only fields where non-LGD-NA methods rank second are Foodweb (Fitness Centrality), Infrastructure (GDM), and Social networks (GND), LGD-NA consistently outperforms all other non-latent geometry-driver dismantling algorithms, including those relying on spectral Laplacian-based based methods and machine learning. The only measure that still outperforms LGD-NA is the NBC metric (also weeett-eometty-driveeee applied to dynamic dismantling. These results strongly demonstrate the practical reliability of our latent geometry-driver dismantling framework, LGD-NA.
C network automata rules in identifying node importance and estimating
effectively approximate latent geometry
4.5
GPU ACCELERATION OF LGD-NA FOR LARGE-SCALE DISMANTLING
50
RA2-4PU
RA2-CPU
8
25
NAC-CPU
BA2-GFU
23 kT
40
20
Time (hrs)
30
15
x3
20
10
10
24 mm
100k
200k
300k
400k
500k
0
100k
200k
300k
400k
500k
Network Size (E)
Figure 3: Runtime (in hours) is plotted against network size, measured by the number of edges, E, for dynamic dismantling. The annotated time indicates the runtime for the largest network. Evaluated on networks of up to 23,000 nodes and 507,000 edges (n = 1,475).
We implement GPU acceleration for all three LGD-NA variants by reformulating the required computations as matrix operations. On large networks, this enables a significant speedup in running time. When comparing RA2 and NBC, on the largest network, GPU-accelerated RA2 is 130 times faster than its CPU counterpart, highlighting the inefficiency of matrix multiplication on CPU. It is also over 63 times faster than NBC running on CPU, thanks our GPU-optimized implementation. Note that NBC on CPU remains faster than RA2 on CPU, again due to the limitations of CPU-based matrix operations. We report only the CPU running time for NBC, as its GPU implementation did not yield any speedup (see Table 15). While some studies report GPU implementations of NBC with improved performance (Fan et al.. 2017 Shi & Zhang 2011 Pande & Bader 2011 McLaughlin & Bader 20188] [Sariycce et al. [2013] Bernaschi et 20.6) these are often limited by hardware-specific optimizations, data-specific assumptions (e.g., small-wor
social, or biological networks), and the use of heuristics that are tailored to specific settings rather than offering general solutions. Moreover, publicly available code is rare, making these approaches difficult to reproduce or integrate. Overall, NBC is not naturally suited for GPU implementation, as it does not rely matrix multiplication, but is based on computing shortest path counts between all node pairs. Overall, while NBC achieves better dismantling performance, its high computational cost makes it impractical for large-scale use.
8

---

In contrast, thanks to our GPU-optimized implementation, our local latent geometry estimators based on network automata rules are the only viable option for efficient dismantling at scale. Here, we look at the details of our matrix operations for the LGD-NA measures. First, the common neighbors matrix is computed as
CNL = A (A²)
where A is the adjacency matrix and denotes element-wise multiplication. Here, A counts the number of paths of length two (i.e., common neighbors) between all node pairs. The Hadamard product with A ensures that values are only retained for existing edges. Next, we compute the number of external links node has relative each of its neighbors. Given the degree matrix D, the external degree matrix is:
E = A o (D - CN A)
Each entry (4,j) of EL2 represents the external degree of node with respect to node j: the number of neighhors of i that neither connected to nor directly connected to j itself. Non-edges are zeroed out. These matrices allow efficient construction of RA2 and its variants using only matrix operations. The time complexity is ((NS), with the common neighbor matrix being the dominant operation, for dense graphs, and O(Nm) for sparse graphs, NV being the number of nodes and m the number of links. On CPU, matrix multiplication is typically memory-bound and limited by sequential operations. GPUs, however, are optimized for matrix operations, leveraging thousands of parallel threads. This results in a substantial speedup when implementing the GPU version. Finally, we show in Appendix that in controlled settings with nPSO networks the GPU advantage becomes apparent when networks exceed 1,000 nodes or 100,000 edges.
4.6 LEVERAGING CND EXPLAINABILITY TO ENGINEER NETWORK ROBUSTNESS
key advantage of our LGD-NA framework its explainability, Indeed, we can directly explain why any of our
buased and latent- seeenttgemmttt---ie driven measures prioritize specific nodes for dismantling. CND, our most performant network automata rule for dismantling, makes this explainability even more straightforward and shows that the vulnerability of node is strongly related to the number of links its neighbors share with one another. The higher this number, the more common neighbors exist between the adjacent nodes of a vulnerable target node. This means that, to enhance the robustness of the network to the failure of a critical node, we should simply increase the number of links between its adjacent nodes. The strategy is as follows, First, identify the nodes with the highest dismantling scores according to a given measure. Here, we consider NBC, a global shortest-pard path count-based measure, and CND, a local topology common-neighbor based network automata measure, because they use different rationales to estimate critical nodes and are the two best-performing measures in this study. Second, for these critical nodes, add new links between their adjacent nodes that are not already connected to each other. Robustness is defined as the ability of a system to continue functioning when subjected to perturbations (Artime et al., 2024). In this initial context, we define attack tolerance, quantified by the LCC AUC, as robustness measure itself, representing the system's 's structural integrity under dismantling attacks. We validate our reinforcement strategy in Table 12 and Figure 15] We clearly show that adding links between the adjacent nodes of the most critical nodes significantly increases the AUC-and therefore the robustness-ad by 36% to 95% for 1% of added links, and by 59% to 259% for 10% of added links. Remarkably, by reinforeing only the top 1% of nodes, we increase network robustness regardless of the dismantling method whethere it our CND or NBC.
4.7 REAL- WORLD APPLICATIONS: FAULT TOLERANCE, SECURITY, AND COMMUNICATIONS To demonstrate the practical utility of LGD-NA, we evaluate its performance on four distinct real-world systems using comain-speciffe functional metries. First, we use the Drosophila Connec- tome (Shiu et al. 2024), where we utilize a Spiking Neural Network (SNN) model of the sugar-sensing circuit. The metric is the sensory neuron firing rate required to trigger the proboscis extension re- sponse. Second, the Terrorist Cell (Gutfraind & Genkin 2017). where we analyze the network responsible for the 2015 Paris and 2016 Brussels attacks. The metric is Commander Reach, defined as the percentage of operatives able to communicate with at least one of the three key commanders. Third, the Flight Map (Cardillo et al. 2013), where we measure Global Efficiency (Egtos). Fourth, a School Contact Network (Mastrandrea al. 2015). where we simulate epidemic using an SEIR model (Anderson & May] 1991). The metric is the Final Outbreak Size. Our results in Figure show that dismantling strategies effectively degrade the functional performance across all four systems. In
9

---

Droopphls Connectoree
Droscght la Connectoone
Pyanskr Flihht Mep
Fyoodd Righ Map
Sw:k/lnusek Temote
Souueess Seanrig Cel
Smeal Cornect
School Confact
CLAR QUe 10011
110
65% 30% Fraction Samooedd
395%
Redter Modea nemoved
50N
Nodee
12%
Figure 4: Dynamic dismantling process for four real-world networks with field-specific functional metries, for NBC, CND, and RA2. The final evaluation metric is the Area Under the Curve (AUC). Dashed line represents the dynamic dismantling process for reinforced networks. See Figure 13 for full results.
the Drosophila Connectome and Terrorist Cell, we observe particularly sharp drops in performance metrics after removing only a small fraction of nodes ( 5%).. We observe more gradual deterioration in the global efficiency of the Flight Map and the viral spread within the School Contact network. This functional collapse is particularly significant for the two adversarial scenarios (Terrorist Cell and School Contact Network): it confirms that LGD-NA is effective for security and communication disruption, efficiently suppressing epidemic outbreaks and isolating hostile leadership with minimal intervention. We subsequently applied our strategy for engineering network robustness to these four scenarios, demonstrating its effectiveness. As shown in Table [3] the reinforced networks are significantly harder to dismantle, achieving robustness gains of up to 363%. This increased resilience evident across both our original topological metric (LCC AUC) and the domain-specific functional metrics defined for each case. For the Drosophila Connectome, this analysis informs the resilient and redundant design of fault-tolerant neuromorphic circuits by mimicking its biological wiring (Suárez et al., 2021 Ham et al. 2021) I. In the Flight Map, it identifies specific hubs where reinforcement prevents systemic failure. Finally, for adversarial networks, our robustness analysis serves a diagnostic purpose when faced with incomplete data. Since social networks, and especially covert ones, often contain unobserved links (e.g., dormant ties or unreported contacts), calculating an empirical robustness ceiling allows us to estimate the margin of error required for successful security operations with partial observability.
CONCLUSION
We acknowledge the dual-use potential of this research, as understanding network vulnerabilities is critical for both designing targeted attacks and engineering robust defensive strategies. To mitigate this, we proactively demonstrate a constructive application for enhancing network robustness and believe the societal benefit of openly publishing these defensive tools outweighs the risk of misuse. In summary, we introduced Latent Geometry-Driven Network Automata (LGD-NA), a framework that achieves state-of-the-art network dismantling using only local topological information. By applying simple network automata rules to estimate a network's latent geometry, LGD-NA identi- fies critical nodes with sigmificant speed advantages over global methods like Node Betweenness Centrality (NBC). Across 1,475 real-world networks and 32 complex systems domains, it consis- tently outperforms all other dismantling algorithms, including those based on machine learning (e.g.. Graph Neural Networks) and spectral Laplacian-basee ones. Notably, our minimalistic Common Neighbor Dissimilarity (CND) measure matches NBC's efficacy while being orders of magnitude faster. Leveraging the explainability of CND, we introduce a novel strategy to engineer network robustness. Crucially, we demonstrate the practical utility of our framework across diverse domains, from informing the design of neuromorphic circuits and reinforcing transport hubs, to disrupting terrorist cells. This work establishes latent geometry as a powerful and efficient principle for both explaining vulnerabilities and engineering stronger networks.
10

---

ACKNOWLEDGEMENTS
This work was supported by The National Natural Science Foundation of China grant number W2531064 to CVC. The Zhou Yahui Chair Professorship award of Tsinghua University to CVC. The National High-Level Talent Program of the Ministry of Science and Technology of China grant number 202417 10001 to CVC. MG and GM acknowledge partial financial support from the University of Catania in the form of PIAno di inCEntiv per la Ricerca di Ateneo (PIACERI), The Authors thank Mo Yang for her administrative support.
REFERENCES
Josh Abramson, Jonas Adler, Jack Dunger, Richard Evans, Tim Green, Alexander Pritzel, Olaf Ronneberger. Lindsay Willmore, Andrew J. Ballard, Joshua Bambrick, Sebastian W. Boden- stein, David A. Evans, Chia-Chun Hung, Michael O'Neill, David Reiman, Kathryn Tunyasuvu- nakool, Zachary Wu, Akvilè Žemgulyté, Eirini Arvaniti, Charles Beattie, Ottavia Bertolli, Alex Bridgland, Alexey Cherepanov, Miles Congreve, Alexander I. Cowen-Rivers, Andrew Cowie, Michael Figurnov, Fabian B. Fuchs, Hannah Gladman, Rishub Jain, Yousuf A. Khan, Caro- line M. R. Low, Kuba Perlin, Anna Potapenko. Pascal Savy, Sukhdeep Singh, Adrian Stecula, Ashok Thillaisundrram, Catherine Tong, Sergei Yakneen, Ellen D. Zhong. Michal Zielinski, Augustin Žídek, Victor Bapst, Pushmeet Kohli, Max Jaderberg, Demis Hassabis, and John M. Jumper. Accurate structure prediction of biomolecular interactions with AlphaFold 3. Nature, 63008016):493-5000, June 2024. ISSN 1476-4687. doi: 10. 10.103/441556-024-0747777-4 URL 1038 1008/
Réka Albert, Hawoong Jeong, and Albert-László Barabási. Error and attack tolerance of complex networks. Nature, 406(6794) Jul 2000. ISSN 1476-4687. doi: 10. 10.103//3501911 URL
Antoine Allard, M. Ángeles Serrano, and Marián Boguñá. Geometric description of clustering in directed networks. Nature Physics, 20(1):10-1156. 2024. ISSN 1745-2481. doi: 10. 6411677002-00244--6
URLhtttss://doi
1038/ 023 02246-6
Roy M. Anderson and Robert M. May. Infectious diseases of humans: Dynamics and control. Oxford University Press, 1991.
Oriol Artime, Marco Grassia, Manlio De Domenico, James P. Gleeson, Hemán A. Makse, Giuseppe Mangioni, Matjaž Perc, and Filippo Radicchi. Robustness and resilience of complex networks. Nature Reviews Physics, 6(2), 2024. ISSN 2522-5820. doi: 10. 00.1000/4422540033-007777
David A. Bader, Shiva Kintali, Kamesh Madduri, and Milena Mihail. Approximating betweenness centrality. In Anthony Bonato and Fan R. K. Chung (eds.), Algorithms and Models for the Web-Graph, pp. 124-137, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. ISBN 978-3-540- 77004-6.
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks Science, 286 554 1999 doi: 10. 10.1126/science 286. 509. URL https:t:://///... www. science org/doi/abs//1 1wt./1111//ccccceemmmcc www.:ence.......... 5439.509 509
Federico Battiston, Enrico Amico, Alain Barrat, Ginestra Bianconi, Guilherme Ferraz de Arruda, Benedetta Franceschiello, Iacopo lacopini, Sonia Kéfi, Vito Latora, Yamir Moreno, Micah M. Mur- ray, Tiago P. Peixoto, Francesco Vaccarino, and Giovanni Petri. The physics of higher-order interac- tions in complex systems. Nature Physics, 17(10)) Oct 2021. ISSN 1745-2481, doi: 10. 1038/441557--021--1337-
Elisabetta Bergamini and Henning Meyerhenke. Fully-dynamic approximation of betweenness centrality. Nikhil Bansal and Irene Finocchi (eds.), Algorithms - ESA 2015, pp. 155-166, Berlin, Heidelberg, 2015. Springer Berlin Heidelherg. ISBN 978-3-662-48350-33
Massimo Bernaschi, Giancarlo Carbone, and Flavio Vella. Scalable betweenness centrality multi-gpu -puu systems. In Proceedings of the ACM International Conference on Computing Fron- fiers, CF 11. pp. 29-36, New York, NY, USA, 2016. Association for Computing Machinery.
11

---

ISBN 9781450341288. doi: 10.1145/2203115022901333 htt /tLLttss////....or//// 1903150.290311
Ginestra Bianconi, Richard K. Darst, Jacopo lacovacci, and Santo Fortunato. Triadic closure as a basic generating mechanism of communities in complex networks. Phys. Rev. E, 90:042806, Oct 2014. doi: 10. (etPPhysReeE.90044228.08 PhysRevE. 90. 042806
Marián Boguñá, Dmitri Krioukov, and K. C. Claffy. Navigability of complex networks. Nature Physics, 5(1), 2009. ISSN 1745-2481. doi: 10. 10.1008/nphss1133
Marián Boguñá, Ivan Bonamassa, Manlio De Domenico, Shlomo Havlin, Dmitri Krioukov, and M. Ángeles Serrano. Network geometry. Nature Reviews Physics, 3(2), 2021. ISSN 2522-5820.
doi: 10. 00.10088442254-0000022266
Phillip Bonacich, Factoring and weighting approaches to status scores and clique identification. The Journal of Mathemattical Sociology, 2(1):133-20, 1972. doi: 10. 10.10000002255XX11922.9999
URL
1972. 9989806)
Ulrik Brandes. A faster algorithm for betweenness centrality*. The Journal of Mathematical Sociology, 15(2)1663-17,, 2001. doi: 10.108000022200.2000.
URL https://doi
org/10 00000/002225000 2ww.::0....2222.2....2
Alfredo Braunstein, Luca Dall' Asta, Guilhem Semerjian, and Lenka Zdeborová. Network dis- mantling. Proceedings of the National Academy of Sciences, 113(44); 2016. doi: 10.1073/pnas. 1..1073/naa.11050881111 1605083113. URL httppp///www..naa..crrr////////.
1605083113
Dirk Brockmann and Dirk Helbing. The hidden geometry of complex, network-driven contagion
phenomena. Science, 342(6166) 2013. doi: 00.1126/scienee.125553 1245200. |
www. /tc.e//
1245500
Anna D. Broido and Aaron Clauset. Scale-free networks are rare. Nature Communications, 10
(1):1017, Mar 2019. ISSN 2041-1723.
doi: 10. 10.1088/44467--019-088
URL https
//doi. /00 1038/ 14100401441111111 947--499------
Carlo Vittorio Cannistraci, Gregorio Alanis-Lobato, and Timothy Ravasi. From link-prediction in brain connectomes and protein interactomes to the wwwcmoootttmprraaddooo in complex
networks. Scientific Reports, 3(1):1613, Apr 2013. ISSN 2045-2322. doi: 10. 1038/srep016113
URL UR..h::p::://ol.or///11...1 10000/p000000////0111111311
Alessio Cardillo, Jesús Gómez-Gardeñess, Massimiliano Zanin, Miguel Romance, David Papo, Francisco del Pozo, and Stefano Boccaletti. Emergence of network features from multiplexity. Scientific Reports, ((1):1344 2013. ISSN 2045-2322. doi: 10. 10.1038/sre001344, URL https
oedoi.org//10 10. 1038 http//rep134444
Aaron Clauset, Cristopher Moore, and M. E. J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 453(7191):98-101, May 2008. ISSN 1476-4687. doi: 10. 10.10088aaturcc06330 URL /ut.tttp:///do..ogg//1... http:///aaa.oo/......000a/aaaaaa http:////....000////uuuree3//3
Pau Clusella, Peter Grassberger, Francisco J. Pérez-Reche, and Antonio Politi. Immunization and targeted destruction of networks using explosive percolation. Phys. Rev. Lett., 117:208301, Nov 2016. doi: 10.1 Ro.1 1 17.208301. URL httpt:::////........ link. aps
TIC3/PhysRReveett.117...222
Mareus Engsig. Alejandro Tejedor, Yamir Moreno, Efi Foufoula- Gerooiio, and Chaouki Kasmi. Domirank centrality reveals structural fragility of complex networks via node dominance. Nature URI
Communications, 15( (:56) Jan 2024. ISSN 2041-1723. doi: 10.
https://doi org. 1038 /40.///44666--0 -277--0233--0 44257-0
Changjun Fan, Li Zeng, Yanghe Feng, Baoxin Xiu, Jincai Huang, and Zhong Liu. Revisiting the power of reinsertion for optimal targets of network attack. Journal of Cloud Computing. 9(1), 2020a. ISSN 2192-1 13X. doi: 10.1
12

---

Changjun Fan, Li Zeng, Yizhou Sun, and Yang- Yu Liu. Finding key players in complex networks through deep reinforcement learning. Nature Machine Intelligence, 2(6):317-324, Jun 2020b. ISSN 2522-5839. doi: 10. 020-0617-2--1777-
Rui Fan, Ke Xu, and Jichang Zhao. A gpu-based solution for fast calculation of the betweenness centrality in large weighted networks. PeerJ Computer Science, 3:e140, 2017. doi: 10.7717/
peerj-cs.140,
Linton C. Freeman. A set of measures of centrality based on betweenness, Sociometry, 40(1):35-41,
1977. ISSN 00380431, 23257938.
Marco Grassia and Giuseppe Mangioni. Coregdm: Geometric deep learning network decycling and dismantling. In Andreia Sofia Teixeira, Federico Botta, José Fernando Mendes, Ronaldo Menezes, and Giuseppe Mangioni (eds.), Complex Networks XIV, pp. 86-94, Cham, 2023. Springer Nature Switzerland. ISBN 978-3-031-28276-8
Marco Grassia, Manlio De Domenico, and Giuseppe Mangioni. Machine learning dismantling and early-warning signals of disintegration in complex systems. Nature Communications, 12(1), 2021. ISSN 2041-1723. doi: 10. 1410088/44444--0022255555--
Alexander Gutfraind and Michael Genkin. A graph database framework for covert network analysis: An application to the islamic state network in europe. Social Networks, 51:178- 188888888, 2017.
ISSN 0378-8733. doi: https://doi.or////
h0wp:00000000110..e.00000....... 10.004. URL https:///// //www////wwwwww
SCi rcienced1 rect. com www/sccicccoooocccooccc.ooo..... wwceiinnce/artii http://sscieeeeeaaaaccc////////s
6302428
Mostafa Haghir Chehreghani. An efficient algorithm for approximate betweenness centrality computation. In Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, CIKM '13 pp. 1489-1492, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450322638. doi: 10.1145/2505515555577222 URL
pettps:/ddoi.oom .rg. /ttgg//0.. 1...11155255515555 2507826
Donhee Ham, Hongkun Park, Sungwoo Hwang, and Kinam Kim. Neuromorphic electronics based on copying and pasting the brain. Nature Electronics, 4(9) 644, 2021. ISSN 11311 doi: 10. 1098/s41192-001-00664
1038//00..000/111 0ttp:////......01110//1001100010
Petter Holme, Beom Jun Kim, Chang No Yoon, and Scung Kee Han. Attack vulnerability of complex networks. Phys. Rev. E, 65:056109, May 2002. doi: 10.1 10.1100//hysReev.....0066 05..0........0619..... URL
https: aps org/
13/./////hyyeeeeee 65. 056109
Jon M. Kleinberg. Navigation in a small world. Nature, 406(6798). 2000. ISSN 1476-4687. doi: 10.1038/35022643.
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E, 82:036106, Sep 2010. doi: 10.1 PhysRevE.82.036100 URL https:://imme aps htt.a//.......or/ooo/////11111/1
.22
036106
Renaud Lambiotte, Martin Rosvall, and Ingo Scholtes. From networks to optimal higher-order models of complex systems. Nature Physics, 15(4):313-320, Apr 2019. ISSN 1745-2481, doi: 1031038/ 341567-019-0459-y.
0459
Jinlong Ma, Peng Wang, and Huijia Li. Directed network disassembly method based on non-
backtracking matrix. Applied Sciences, 12(23), 2022. ISSN 2076-3417 doi: 10.3390/
app122312047. URL httpt::////// //wp:://www. mdpi cwm htt.//2/66-3331//222210000 3417/12/23/12047
Rossana Mastrandrea, Julie Fournet, and Alain Barrat. Contact patterns in high school: A comparison between data collected using wearable sensors, contact diaries and friendship sur-
veys. PLOS ONE, 1069):1-26, 09 2015. doi: 10.1371/jorrnal.poe 10166.0136497. 36497. URL https
//doi. wtt.://///.....//oorruuro.u.oo.. www.eaawwppppp............... pww.ll00...ee.0...99..9
Adam McLaughlin and David A. Bader. Accelerating gpu betweenness centrality. Commun. ACM, 61(8):85 92, July 2018. ISSN 0001-0782, doi: 10. 10.1145/3230485. URL https: / http///d.o/// org/
10. 10.1135/3230485
13

---

Flaviano Morone, Byungjoon Min, Lin Bo, Romain Mari, and Hemánn A. Makse. Collective influence algorithm to find influencers via optimal percolation in massively large social media. Scientific Reports, 6(1), 2016. ISSN 2045-2322. doi: 10. 10.1008/ste330062.
Adilson E. Motter and Ying-Chenp Lai. Cascade-based attacks on complex networks. Phys. Rev. E. 66:065102, Dec 2002. doi: 10.1 11w.://yyse....6.66551// URL htttt::////ink http::///iinkkss...oooom org doi Goi/10.1103/Payye
66. 065102
Salomon Mugisha and Hai-Jun Zhou. Identifying optimal targets of network attack by belief propagation. Phys. Rev. E, 94:012305, Jul 2016. doi: 10.1 100//hyyeeev..94.02222..
URL
https: //link aps. org http/////////// http//ci/11111 hwt.1100//hysee..... 94 012305
Alessandro Muscoloni and Carlo Vittorio Cannistraci. Leveraging the nonuniform p8o network model as a benchmark for performance evaluation community detection and link prediction. New
Journal of Physics, 20(6),063022, jun 2018a. doi: 10. 10.1088/1367-2633kaar
URL URLhttps
www.doii..ggg00.. / 0011113676622---- 3/330/acc6F9
Alessandro Muscoloni and Carlo Vittorio Cannistraci. A nonuniform popularity-similarty op- timization (npso) model to efficiently generate realistic complex networks with communities. URL.
New Journal of Physics, 20(5):052002, may 2018b. doi:
Sttpps:/ee dx doi /10 1088 201/:///336-222/3aa5555555
Alessandro Muscoloni and Carlo Vittorio Cannistraci. Navigability evaluation of complex networks by greedy routing efficiency. Proceedings of the National Academy of Sciences, 116(5): 1469, 2019. doi: 10. (0.73//paa.1111880111 URL wttph:tt///////t //ww:///wwww./ pras. orgo /oi/ aabs//0 110
1073/pnas 1811 1817880116
Alessandro Muscoloni, Josephine Maria Thomas, Sara Ciucci, Ginestra Bianconi, and Carlo Vittorio Cannistraci. Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Nature Communications, 8(1), 2017. ISSN 2041-1723. doi: 10. 101100884444---00771188555555
M. E. Newman. Assortative mixing in networks. doi: 10.1 (e0s/ PhysRevLett. 89, 89..EE001992007101111
Phys. Rev. Lett., 89:208701, Oct 2002.
URL
aps htt.aa/...a...ogooo/o...........
M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45(2): 167-256, 2003. doi: 10.1177/50330 URL https:///oi..rr/200..
50036144503424B8
M. Newman. Detecting community structure in networks. The European Physical Journal B, 38(2):321-330 Mar 2004. ISSN 1434-6036. doi: 10. 10.11//0pp///2204400012444 URL https
M. E. Newman. Communities, modules and large-scale structure in networks. Nature Physics, (1):25-31, Jan 2012. ISSN 1745-2481. doi: 10.1008/nhhs2166.. URL htttttts///ooorgg 10. 10.1038/aphys2162
Yuxuan Ou, Fujing Xiong, Hairong Zhang, and Huijia Li. Network dismantling on signed network by evolutionary deep reinforcement learning. Sensors, 24(24), 2024. ISSN 1424-8220. doi:
10.3390/s242480266 URL http::tts://ie //www www.:.dpp..om ccm/1424 8220 /220/24/24/322222
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford Infol Lab, November 1999. URL
http://ilpubs. stan fordd. eda.r:d.du::09000 8C90/422/ Previous number SIDL-WP-1999-0122
Prasanna Pande and David A. Bader. Computing betweenness centrality for small world networks on a gpu. In Proceedings of the 15th Annual High Performance Embedded Computing Workshop (HPEC), September 2011.
Pietro Panzarasa, Tore Opsahl, and Kathleen M. Carley. Patterns and dynamics of users' behavior and interaction: Network analysis of an online community. Journal of the American Society for Information Science and Technology, 60(5):911 132, 2009. doi: miley. com/ /oi/abs/10.10000
21015. URL /attps://asistdl.. t www.eeloonnnnneeneeeeeeee http://aeestttlllooneeeeeaaaaaaa asi 21015
14

---

Fragkiskos Papadopoulos, Maksim Kitsak, M. Ángeles Serrano, Marián Boguñá, and Dmitri Krioukov. Popularity versus similarity in growing networks. Nature, 4 540, Sep 2012. ISSN 1476-4687. doi: 10. no.t/urr 1459. /ttpa///w.....//aa/////////////.
Ashwin Paranjape, Austin Benson, and Jure Leskovec. Motifs in temporal networks. In Pro- ceedings of the Tenth ACM International Conference on Web Search and Data Mining, WSDM $17, pp. 601-610 New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450346757. doi: 10.1145/301866 1.101 8731.
URL https: http:://doooogg////////// 1145/
301 8661. 30118711
Erzsébet Ravasz and Lászóó Barabási. Hierarchical organization in complex networks. Phys. Rev. E, 67:026112, Feb 2003, doi: 10. 1033PhhysseeE..770061122 URL httts:t//tinkkke aps 67. 026112
org/doi/10. 11tp///10.110///hheeeeeee
Xiao-Long Ren, Niels Gleinig, Dirk Helbing, and Nino Antulov-Fantulin. Generalized network dismantling. Proceedings of the National Academy of Sciences, 116(14))6544 6559, 2019, doi: 10.1073/pnas.
100p://aa....1188881111111 1006108116.. 1806108116
URL http:////ww...psss.c.c.//////aa/
Matteo Riondato and Evgenios M. Komarrooulls. Fast approximation of betweenness centrality through sampling. In Proceedings of the 7th ACM International Conference on Web Search and Data Mining, WSDM 11. 413-422, New York, NY, USA. 2014. Association for Computing doi: 00.1145255611555555222 URL https://doi... org/
Machinery. ISBN 9781 450323512.
T0.1145/2556195.. 2556224
Ahmet Erdem Sariyüce, Kamer Kaya, Erik Saule, and Ümit V. Çatalyürek. Betweenness centrality on gpus and heterogeneous architectures. In Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units, GPGPU-6, pp. 76-85, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320177.
doi: 10.1 10.1145/255552324558811
URL /ttttpsss//bo..o///110 1ttp:///...115522255522222 220.5855.224555533 2458531
C. M. Schneider, T. Mihaljev, and Herrmann. Inverse targeting an effective immunization may 2012. doi: 10. 10020/0955--50551844460022 URL
strategy. Europhysics Letters, 944)))440020 5075/ 5075/98/45000
http:://Aa..ol.ccr//0022222///22
Matteo Serafino, Giulio Cimini, Amos Maritan, Andrea Rinaldo, Samir Suweis, Jayanth R. Banavar, and Guido Caldarelli. True scale-free networks hidden by finite size effects. Proceedings of the National Academy of Sciences, 1180)):c0133825118 2021. doi: 10. http://paa...13251121. URL wttpppaas.....11111.
https://wwet pnas org
M. Ángeles Serrano, Dmitri Krioukov, and Marián Boguñá. Self-similarity of complex networks and hidden metric spaces. Phys. Rev. Lett. 100:078701, Feb 2008 doi: 10.1 10.1
100.078701. URL http:////.....coocc/////////a/ap
0 078701
Vito D Servedio, Alessandro Bellina, Emanuele Calô, and Giordano De Marzo. Fitness central- ity: a non-linear centrality measure for complex networks. Journal of Physics: Complexity, 6 (1):015002, jan 2025. doi: 10. 111100/2632-722X/aaa4444 URL URLhttps:: http:/xxxxdo...oo.. doi.org/10
1088/ 7088/26342 072X ada845
Zhiao Shi and Bing Zhang. Fast network centrality analysis using gpus. BMC Bioinformatics, 12(1): 149, May 2011. ISSN 1471-2105. doi: 10.1186/147112100--22-222 URL hellhhttps://oi..or 10. 0
2105-111111 149
Philip K. Shiu, Gabriella R. Sterne, Nico Spiller, Romain Franconville, Andrea Sandoval, Joie Zhou, Neha Simha, Chan Hyuk Kang, Seongbong Yu, Jinseop S. Kim, Sven Dorkenwald, Arie Matsliah, Philipp Schlegel, Szi-chieh Yu, Claire E. McKellar, Amy Sterling, Marta Costa, Katharina Eichler, Alexander Shakeel Bates, Nils Eckstein, Jan Funke, Gregory S. X. E. Jefferis, Mala Murthy, Salil S. Bidaye, Stefanie Hampel, Andrew M. Seeds, and Kristin Scott. drosophila computational brain model reveals sensorimotor processing. Nature, 634(8032) 2024, ISSN 1476-4687 doi: 10. 1038//441586000200776666666 URL https:: doi /ttppp::/dol..oz///0..00000 s4 641586-024-07766
15

---

Laura E. Suárez, Blake A. Richards, Guillaume Lajoie, and Bratislav Misic. Learning function from structure in neuromorphic networks. Nature Machine Intelligence, 3(9):771-786, 2021. ISSN 2522-5839. doi: 10. 00.1088/44225--021-000777 s s42256- 0272566021--0076---
Ivan Voitalov, Pim van der Hoor, Remco van der Hofstad, and Dmitri Krioukov. Scale-free networks well done. Phys. Rev. Res., 1:033034, Oct 2019. doi: 10.1 10ssPhhyeeeeeeesaaarc. 1.033034. URL https://link aps org/ htwp////o/100/// http://r...oo.......///////aaeo. 1033034
Min Wu, Jianhong Mou, Bitao Dai, Suoyi Tan, and Xin Lu. Dismantling directed networks: A multi-temporal information field approach. Chaos, Solitons & Fructals, 196: 19641, 2025.
ISSN 0960-0779. doi: oet.oaaccc..cccc//am/aaarr/////.
URL hetps:/ www
sciencedirect.co
Zhihao Wu, Giulia Menichetti, Christoph Rahmede, and Ginestra Bianconi. Emergent complex network geometry. Sciemtific Reports, 5(1):10073, May 2015. ISSN 2045-2322. doi: 10. 1031038/ srep10073.
Chenwei Xie, Chuang Liu, Cong Li, Xiu-Xiu Zhan, and Xiang Li. Esnd: An embedding based
framework for signed network dismantling. Expert Systems with Applications, 289:128346 2025. ISSN 0957-4174. doi:
http:t/ /www sciencedirect. htt.a///c.....oooooo......ooaa/a
Lenka Zdeborová, Pan Zhang, and Hai-Jun Zhou. Fast and simple decycling and dismantling of networks. Scientific Reports, 6(1), 2016. ISSN 2045-2322. doi: 10. 10.1038//re337954.
Yongtao Zhang. Cunqi Shao, Shibo He, and Jianxi Gao. Resilience centrality in complex networks. Phys. Rev. E, 101:022304, Feb 2020, doi: 11w.:///hyyee..111..222222
URL https:/7
link.
022304
Konstantin Zuev, Marián Boguñá, Ginestra Bianconi, and Dmitri Krioukov. Emergence of soft com- munities from geometric preferential attachment. Scientific Reports, 5(1):9421, Apr 2015. ISSN 2045-2322. doi: 10.1038/srep09421.
http:t::: /doi. org. 1038 rrpp0941
16

---

A LATENT GEOMETRY ESTIMATORS
Table 3: Comparison of latent geometry estimators and their variants, Pij the weight of the link between nodes i and j; e, and ej denote the number of external links of nodes and j. respectively; .) is the number of common neighbors shared by and j. Information Locality denotes the type of structural information required to assign a score to each node for dismantling. Time Complexity denotes the time complexity for dynamic dismantling using each estimator on sparse graphs, without reinsertion. N: number of nodes. m. number of links.
Estimator
Author
Year
Formula
Information Locality
Time Complexity
Repulsion Attriction?
Musenleai
2017
"
RA2
IFON
Local
((N(Nm))
2017
RA2
denominator-
Ours
2025
Jats 1+0Ng
CND
Local
((N(M)))
ablazion (CND)
RA2
numeratio-
Ours
2025
RA
+ + t..0)
Local
((N(Nm))
ablation
CN
ei
ej
em
en
m
n
CN
common neighbor
seed node
external node
common
candidate link
external link
neighbor
link
Figure 5: Illustration of how RA2 measures are computed on two toy networks. Seed nodes are shown in black; common neighbors (CN) shown in white with black border, and external nodes are white with grey border. The dashed line the edge that is being assigned a weight. External links denote the number of edges connecting node nodes outside its CN set, here in red. In black, the links to common neighbors. For the link Vij in the top network, e; = 5, = 3, and CNj For the link Pm in the bottom network, em en 1, and CN
Latent Geometry-Drin -Driven Network Automata rule. F how RA2-based network automata rules assign edge weights by estimating geometric distances using only local topological features. The two toy subnetworks demonstrate how the RA2 rule and its variants distinguish between geometrically distant and close node pairs. In the top subnetwork, nodes i and j have only one common neighbor and are each connected to many external nodes (e, = 5, Ej = 3), indicating weak integration in local community and stronger connectivity to distinct parts of the network. According
17

---

to the Repulsion- -ttrractnnt rule, this suggests larger latent distance due to high repulsion and low attraction. In contrast, in the bottom subnetwork, nodes m and n share four common neighbors and have only external link each (cm L, cn = 1). This pattern indicates stronger local community and a higher likelihood that the nodes are geometrically close in the latent space, with a lower dissimilarity score. These examples highlight how latent geometry-drivee RA2-based network automata rules estimate hidden distances: fewer common neighbors and more external links suggest geometrical separation, while many common neighbors and few external links imply proximity the latent manifold.
Why is RA2 latent geometry estimator? In geometric networks, nearby nodes form dense, closed neighborhoods: they share many common neighbors (high C),,)) and have few "external" links (small E). Distant node pairs show the opposite pattern. The Repulsion-AAtraccti (RA2) captures these patterns in their formulation: any RA variant that decreases with CN₂, and increases with external connectivity, e therefore monotonic with latent distance: small values indicate proximity; large values indicate separation. Crucially, this relies topological proximity, not a specific geometric space, so it applies across hyperbolic, Euclidean, or elliptic latent geometries. The only assumption apply this estimator of underlying geometry is that the topology displays:
rule
node heterogeneity (meaning that the node degree distribution displays standard deviation different from zero).
homophily (similar nodes link together), for instance geometric proximity in latent space causes nodes that are geometrically close have overlapping neighborhoods.
We can aggregate RA2 to score node criticality by summing its pairwise RA2 to neighbors. This turns local edge-level "distance" into node-level bridging load:
Few adjacent nodes (neighbors) with mostly short links yields a small RA2. This node is peripheral and non-critical; removal has little global effect.
Many neighbors with mostly short links still yields modest RA2 (short links contribute little). The node is locally redundant; removal is buffered by community structure.
Many neighbors with mix of short and long links yields large RA2 because long links carry high RA2. The node simultaneously anchors local community and bridges distant regions; removing it is likely to disconnect communities and degrade global connectivity.
Few neighbors with many long links (rare under geometric attachment) still yields large RA2; such nodes are likewise critical inter-community hubs.
As result, RA2 encodes latent separation from purely local topology. Summing RA2 over node's incident edges ranks nodes by how much long-range connectivity they support. Dismantling the highest-scoring nodes precisely targets those bridges whose removal most effectively fragments the network.
Time Complexity. We analyze the time complexity for the full dynamic dismantling process (excluding reinsertion) for the latent coometry-driveer network automata rules in Table where dynamic means recomputing the dismantling measure after each node removal. For RA2 and its variants, the dominant operation is the computation of the common neighbor (CN) matrix. This operation has a time complexity of O(N3) for dense graphs and O(Nm) for sparse graphs, where N is the number of nodes and is the number of links. Assuming N dismantling steps in the worst-case scenario, the overall time complexity becomes O D(N(N)) for sparse graphs. The assumption of N dismantling steps applies to all the time complexity analyses of dynamic dismantling methods.
B THEORETICAL DISTINCTIONS BETWEEN GRAPH METRICS AND LATENT MANIFOLDS
To avoid ambiguity regarding the use of manifold theory in complex systems, we clarify the distinction between topological deseriptors and latent geometric spaces. In this work, we define the latent manifold as the hidden, lower-dimensional structure that captures the essential configuration of the system.
18

---

Terrorist Ball Bombing
Covert Shipment
Collaboration Opsahi
Co-authorship Auger
CND
NSC
0.6
0.4
0.2
0.1
60 80 50
100
150
Fraction Nodes Removed
Figure 6: Dynamic dismantling process on example networks comparing local network automata rule RA2 and its variants versus NBC, when the former outperforms NBC in terms of AUC. The plot shows the normalized size of the largest connected component (LCC) as a function of the fraction of nodes removed, with a target LCC threshold of 10%. The final evaluation metric the Area Under the Curve (AUC) of the LCC trajectory.
To infer the latent manifold from high-dimensional data, a range of general dimensionality reduction and manifold learning techniques can be applied. These approaches seek to map the data points into a continuous, lower-dimensional space where geometric proximity reflects similarity the original space. They can be broadly categorized as methods preserving local structure (e.g., I-SNE, UMAP, and Minimum Curvilinear Embedding (MCE)), methods based on calculating intrinsic distances (e.g., Isomap (ISO) and its variants), spectral methods (e.g.. Laplacian eigenmaps and Diffusion Maps), and deep learning techniques (c.g., Autoencoders and VAEs) that learn the latent code necessary for data reconstruction. Finally, specialized manifold learning approaches in dynamical systems (e.g.. Koopman operator theory) can transform complex, nonlinear dynamics into simpler, linear representations within manifold.
When data is organized as a complex network, the latent manifold is typically inferred using network embedding techniques specifically designed to preserve the network's topology. These methods fall into three broad categories: spectral methods (e.g., spectral clustering) which use the alge- braic properties of the graph matrices; deep learning approaches (e.g., Deep Walk, Node2Vec. and Graph Autoencoders (GAF)) which learn representations using neural networks trained on struc- tural information like random walks, while Graph Neural Networks (GNNs) have emerged as the state-of-the-arr for learning task-specife embeddings using topology and node/edge features; and geometric approaches such as Hyperbolic network embeddings. These geometric methods (e.g.. Poincaré embeddings. Hypermap) utilize non-Euclidean geometries, such as negative curvature, to efficiently capture the hierarchical and scale-free properties of complex networks. Specific algorithms like LPCS generate node coordinates by analyzing and ordering the network's 's community structure.
We distinguish this latent manifold from graph metrics. For example, standard topological graph descriptors such worddswwrlddesss, community structure, and degree heterogeneity are not direct descriptors the manifold themselves. However, since the network sampled from a specific latent space, these observed properties are influenced by the manifold's geometry. Consequently, these topological metrics do characterize the topology of network that is embedded in a specific latent space: for instance, small-worldness suggests short geodesic distances, community structure can imply stratification or clustering, and degree heterogeneity may reflect features such as local curvature or singularities. Our approach uses the topology of the observable network to infer the geometric distance between nodes within the network's ss latent manifold, thereby allowing us to exploit the manifold's geometric properties for dismantling.
Note that we include a GNN-based dismantling algorithm. Graph Dismantling with Machine learning (GDM) GGassia et al.] 202I), in our experiments. GDM is a GNN that is trained on optimally dismantled networks, and is considered state-of-the-art dismantling algorithm (Artime et al. 2024 Grassia et al. 2021) that can implicitly capture features of the underlying latent geometry of the target network. The fact that our LGD-NA methods consistently outperform GDM in all situations suggests that our estimators might be yielding a more accurate estimation of the target network's latent geometry."
19

---

C GEOMETRIC VALIDATION OF LATENT GEOMETRY ESTIMATORS
To provide visual and empirical validation for our latent-geometry estimators, analyze the ability of our seeentgg estimators to identify node importance and estimate link distances using synthetically generated networks with known geometry. As previously mentioned, the RA measures were introduced to serve as pre-weighting strategies for approximating angular distances associated with node similarities in hyperbolic network embeddings (Muscoloni al. 2017).
To investigate this, we synthetically generate networks using the non-uniform Aipularit-SSmillati Optimization (nPSO) model (Muscoloni & Cannistraci 2018b). The nPSO model is built on the principle that radial coordinates represent hierarchy (popularity) while angular coordinates represent similarity. It produces networks that are both scale-free (characterized by power-law degree distribution, meaning a network has few highly connected hubs while the majority of nodes have few links) and clustered with distinct communities, closely mimicking the structure of many real- world complex systems. We utilize the nPSO network model specifically for this task because these networks are generated with known node coordinates and a known underlying hyperbolic geometry, making them highly suitable for validating geometry-relatee measures in network science.
We generate various nPSO networks keeping the number of nodes (N 500) and communities (C = 5) fixed. We test different network topologies by varying:
The power-law exponent 7 E (2 represents common bounds for real-world scale-free networks. With y = 3, fewer high-degree hubs exist, creating less hierarchy (seen through the radial coordinates) and reduced network hyperbolicity (meaning that they become more similar to Erdos-Renn Renyi random graph compared to when y 2). 2).
The number of nodes a new node will connect to when being added to the network, m E {10, 20, 50J. This value represents approximately half of the average node degree, making the network more or less connected. This results in networks with three different density levels p E f0.04, 0.08, 0.2].
The temperature T E f0.3, 0.6, 0.9} controls clustering, where lower temperatures pro- duce stronger clustering. Higher temperatures reduce clustering (seen through the angular coordinates) and increase the randomness of connectivity, thus reducing the generated net- work's 's hyperbolicity (nodes connect more by random rather than following the underlying hyperbolic geometry).
Figure 7 visualizes synthetic nPSO networks with nodes colored by CND score (red: high, blue: low) and sized by degree. The visualization clearly shows that high CND scores correspond to nodes with highcentrality, hubs located near the center of the hyperbolic disk. This relationship is most evident for 7 = 2, where the skewed degree distribution creates a clear distinction between central hubs and peripheral nodes. For 7 3, the trend persists but is less pronounced due fewer super-hubs, consistent with the network's s reduced hyperbolicity. These results provide strong visual evidence that CND effectively identifies structurally important nodes in the hyperbolic latent space.
To quantitatively support our claim, we evaluate how well the latent geometry estimators approximate the true hyperbolic distances. We use the hyperbolic distance correlation (HD-correlation) metric, the Pearson correlation between all pairwise geometrical shortest path distances in the networks' original hyperbolic space and the weighted shortest path distances using the latent- geometry estimators as edge weights (Muscoloni et al.) (017). The higher this correlation, the better the latent- geometry estimator is able to recover the geometrical distances between pairs nodes a network's 's underlying geometry.
Figure shows high HD-correlation for both CND and RA2 across all tested nPSO configurations, confirming that these measures used in our dismantling framework effective latent geometry estimators. This is further supported by the statistical significance reported in Table 20
The Pearson correlation is visualized in Figure 8 for different parameters, visualizing how well the distance approximation changes as the network becomes less hyperbolic. As expected, for y = 2, the correlation decreases for both estimators with increasing temperature (i.e., reduced clustering and hyperbolicity). For the less hyperbolic 7 = 3 networks, this decreasing trend persists for CND but not for RA2. This suggests that CND remains robust estimator of the latent geometry even when
20

---

p 0.04
p 0.08
p 0.2
T = 0.3
7
0.6
= 0.9
T 0.3
Y 3
T = 0.6
T 0.9
CND Weighting
31
16
Figure 7: nPSO model networks visualized in the hyperbolic space. Fixed parameters the number of nodes. N=500, and the number of communities, C=5. Nodes are colored according to their CND measure, where red represents higher CND scores and blue lower ones. Ranges of CND values reported in the color bar and are different for each density level. Node sizes are positively correlated with their degree.
21

---

hyperbolic structure is less pronounced, whereas RA2's performance is more dependent strongly hyperbolic conditions, consistent with our dismantling experiments.
We also conducted experiments considering only existing links, correlating their estimated weights with the true geometrical shortest path distances in the hyperbolic space (Figures [2] and and 22). The results confirm that both CND and RA2 are effective latent geometry estimators, the link weights strongly correlate with the true distances.
This visual and quantitative evidence demonstrates LGD-NA measures' ability to accurately estimate the geometric distance between nodes. Consequently, the node aggregation step in our LGD-NA framework successfully identify nodes that connect distant regions in the latent space.
Table 4: Pearson correlation between all the pairwise geometrical shortest path distances of the network nodes in the original nPSO model and in the reconstructed hyperbolic space (HD- correlation) (Muscoloni et al. 2017). Mean values over 10 seeds are reported, with a color gradient where green corresponds to values approaching and red to values approaching -1. The power-law exponent 7 represents the scale-freeness found in real-world networks. networks. is the density of the networks. The temperature T controls the level of clustering (lower temperatures yield stronger clustering). Fixed parameters are the number of nodes, N = 500, and the number of communities,
C' Standard Error of the Mean (SEM) and Fisher p- p-value are found Table 20
N=500,
p=0.04
p=0.08
p=0.2
T=0.3
0.722
0.792
0.846
CND
T=0.6
0.693
0.768
0.801
T=0.9
0.633
0.765
0.777
y=2
T=0.3
0.521
0.532
0.521
RA2
T=0.6
0.524
0.484
0.308
T=0.9
0.498
0.460
0.303
T=0.3
0.584
0.624
0.645
CND
T=0.6
0.510
0.579
0.590
T=0.9
0.452
0.552
0.597
y=3
T=0.3
0.685
0.714
0.783
RA2
T=0.6
0.722
0.780
0.805
T=0.9
0.688
0.795
0.755
-1
D TOPOLOGICAL CENTRALITY MEASURES
Table 5: Comparison of topological centrality measures and the associated time complexity for dy- namic dismantling using each centrality measure. Information Locality denotes the type of structural information required to assign a score to each node. Time Complexity denotes the time complexity for dynamic dismantling using each centrality measure sparse graphs, without reinsertion. N: number of nodes. m. number links.
Type
Complexity
Locality
Degrne
Depreo-hased
Local
OCN Iog N)
Eigenvecoor
Boncich
Walkss
Glubal
OUNTN m])
Nede
Retweemeess
Frammun
1977
Shortost poth-bued
Global
O(N(Nm))
(NBC)
Pagekunk
1999
Kandoms
m))
Resilience
Zhang al (033)
2050
Resilienco-hssed
Global
O(N(N 4 ml
Domnmak
Enssis
2014
Giobai
O(N(N
Fimess
2015
Finnes--ussol
O(N(N m))
Time Complexity. We analyze the time complexity of dynamic dismantling (excluding reinsertion) for the topological centrality measures used in our experiments, summarized in Table As before, the analysis assumes N dismantling steps in the worst-case scenario. For degree, the score update after each removal is local and can be done in (log N) time using a binary heap. For NBC, we use Brandes' algorithm (Brandes) 2001), which computes berweenness centrality in O(Nm) time per
22

---

0.8
Y
0.04
0.8
2, p 0.08
Y 2, p
0.8
Pearson Correlation
CND
0.6
0.6
RA2
0.6
0.4
0.4
0.4
0.3
0.6
0.9
0.3
0.6
0.9
0.3
0.9
Y 3, = 0.04
= 3, = 0.08
Y = 3, p 0.2
0.8
0.8
Pearson Correlation
0.6
0.6
0.6
0.4
0.3
0.6
0.4
0.3
0.6 Temperature
0.9 0.4
0.3
0.9
Temperature
Temperature
Figure 8: Pearson correlation between all the pairwise geometrical shortest path distances of the network nodes the original nPSO model and in the reconstructed hyperbolic space (HD- correlation) (Muscoloni et al., 2017). Mean values over 10 seeds reported, with the shaded area the Standard Error of the Mean (SEM). The power-law exponent y represents the scale-freeness found in real-world networks, networks. p the density of the networks. The temperature T controls the level of clustering (lower temperatures yield stronger clustering). Fixed parameters are the number of nodes, N 500, and the number of communities, C == 5.
23

---

step for unweighted networks. Eigenvector, PageRank, Resilience, Domirank, and Fitness all rely matrix-vector multiplications, which has a time complexity of O(m). ). We also add the term N, which represents the overhead of looping over nodes update normalize the resulting vector each iteration. This leads to a total per-step cost of O(N + m)) We also omit the constant k for Figenvector, PageRank, and Fitness centrality, which represents the number of iterations these methods perform. In practice, reaching full convergence to a single optimal solution is often computationally infeasible; this is why a fixed number of iterations is typically defined.
E STATISTICAL AND MACHINE LEARNING NETWORK DISMANTLING.
Table Comparison of dismantling algorithms (Artiee et al. 2024). Information Locality denotes the type of structural information required to assign whether scores are recomputed after each removal. Reinsertion specifies whether the algorithm includes a reinsertion step after dismantling. Time Complexity denotes the time complexity of the method on sparse graphs, without reinsertion. N: number of nodes. m: number of links. h: number of attention heads. T: maximal diameter of the trees in the forest for BPD and MS. c is small constant used in spectral partitioning operations. Included states whether the method was run in our experiments; if not, a brief reason provided.
each node. Dynamicity indicates
Algorithm
Author
Yeur
Information Locality Locil
Dynamicity
Reinsertion
Time Complexity
Included
Collectivee
Infla-
Inflaence maxi- mization
Momone
2016
Dysamic
Yes
C(N log N)
Yes
enca
cral 2016
Message passing based docycling
Magiisa
Dysamic
Optional
(mm))
propagation
& Zhog
Code
guided decima- (BPD)
2016
miss-
Min-Sum (MS)
Message passing-baved based decycling
Rrunstein
Dynamic
((m77
2016
(NN(lo N
+
7))
Generalized Nes. work Dismanting (GNDD
Spectaal puti- tioning
Rei et al
2019
Giobal
Dynamic
Optional
O log N)
Yes
2019
CorefTD
Degree-bused decycling
Ziehurwa
2016
Global
Dynamic
O(N)
Yes
<t 1 2010
Explosive
Explosive per- colutioo
Global
Dynamic
O(N N)
Yes
nization (FI)
2016
FINDER
Machine leam- ing
3n et
2020
Global
Dynamic
Opiional
D[V[
No
out-
dated
Graph Disman- Machine
Maching leum- ing
Greeda
2021
Global
Statie
Opiionll
Oth(N m))
Yes
CoroGUM
Machine leam-
Crrasnia
&
2025
Global
Static
Yes
O m))
Yes
Mangioni
20:4
Table i is adapted and extended from Table 1 of Artime et al. (Artime et al., 2024), a recent and comprehensive review which has become a key reference the field of network dismantling, The majority of these algorithms were included in our experiments, with the exception of BPD and FINDER due to unavailable or outdated code, respectively.
F REINSERTION METHODS
Reinsertion was originally introduced the context of immunization reverse process: starting from a fully dismantled network, nodes are reinserted one by one, each time selecting the node whose addition causes the smallest increase in the largest connected component (LCC) (Schneider al.) 2012). This reversed sequence then defines an effective dismantling order. In subsequent studies, reinsertion has been used as a post-processing step to improve dismantling outcomes (Artime et al. 2024): the network is first dismantled by given method, and nodes reinserted until the LCC reaches the dismantling threshold. This reduces the dismantling cost while preserving the original attack target.
In this work, dismantling cost is defined as the number of nodes removed from the network. The reinsertion step aims directly minimize this cost by reintroducing nodes that were initially removed but found to unnecessary for achieving the dismantling objective. It's important to note that while reinsertion reduces the number of physical removals, it does introduce higher computational
24

---

LGD estimators
Mean Field Ranking
NBC
CND-RL
GDM R1
CoreGIMM -R1
Fitness R1
Demirank,, A1
Chi A1
MS
CoreHiD R1
MBC R2
CND-R2
GDM R2
DoreGOM RR
Fitness R2
Domtranks, R2
Chu R2
Mis R2
CoreHi R2
8
NBC CND-R3
GDM R3
CoreGOM R3
Fitness- R3
Domiranka R3
Clu A3
M5 CoreHDD R3
Figure 9: Mcan field ranking for subset of the best-performing methods from each category with each reinsertion method (RI, R2, R3) (n = 1,237). Methods based on latent geometry are shown in red. All LGD and topological centrality measures dynamic dismantling. Error bars indicate the standard error the mean (SEM). Method acronyms are defined in Tables and 6
Foodweb
Fruit Fly Connectome
Retweets Twitter
CND R1
0.8
CND R3
0.6
0.4
0.2
0.1
LCC
10%
20%
30%
20%
40%
60%
1% Roadmap Minnesota
2%
UK Railmap
Contact Infections
1
0.8
0.6
0.4
0.2
0.1
2%
4%
10%
20%
30%
10%
20%
Fraction of Nodes Removed
Figure 10: Dynamic dismantling process on example networks comparing CND with and without reinsertion. The plot shows the normalized size of the largest connected component (LCC) function of the fraction of nodes removed, with target LCC threshold of 10%. The final evaluation metric is the Area Under the Curve (AUC) of the LCC trajectory.
25

---

cost as it's post-processing step performed after the initial dismantling. However, the primary objective is to minimize this physical intervention, as in many real-world scenarios, the logistical and financial implications of physically removing network components (c.g.. infrastructure) far outweigh the computational resources expended during the optimization phase. This is why we compare all methods with and without the reinsertion step.
Several reinsertion criteria have been proposed: Braunstein et al. (2016) select the node that ends up in the smallest resulting component after reinsertion; Morone al. (2016) choose the node that reconnects the fewest components; Mugisha & Zhou (2016) select the node that causes the smallest LCC increase. See Table for a full comparison.
Reinsertion can greatly enhance dismantling performance. However, recent work shows that this step can overpower the dismantling algorithm itself, allowing weak methods appear effective when paired with reinsertion (Fan et al. 2020a). To address this, we enforce two constraints to ensure fair comparisons and prevent reinsertion from dominating the dismantling process:
1. Reinsertion must stop the LCC exceeds the dismantling threshold. Recomputing new dismantling order by reinserting all nodes is not allowed.
2. Ties the reinsertion criterion must be broken by reversing the dismantling order: nodes removed later prioritized.
These rules ensure that reinsertion complements rather than overrides the dismantling process, preserving the integrity of the original method.
In our experiments, we implement three reinsertion methods, adapted from prior work, here we explain which part of their method we change for our experiments. Those changes are marked with an asterisk (*) in Table
R1 (Braunstein et al. 2016): We replace their original tiebreak (smallest node index) with reverse dismantling order.
R2 (Morone et al. reinserted to compute new dismantling sequence.
2016): We apply the LCC stopping condition. Originally, all nodes
R3 (Mugisha & Zhou 2016): We apply reverse dismantling order as the tiebreak, as no rule is defined in their paper, and their code is unavailable.
R3 is the most similar to the reverse immunization method proposed by /Schneider et al. (2012). where nodes are added back one by one based on minimal LCC growth. their original method, ties are broken by selecting the node with the fewest connections to already reinserted nodes; if multiple candidates remain, one is chosen at random.
We note that reinsertion typically reduces the number of removals but does not always lead to lower AUC. Since the trajectory of the LCC changes with reinsertion, the dismantling process may reach the threshold faster. improving AUC. However, this is not guaranteed, as we see in the first two subplots of Figure 10 for the Foodweb and Fruit Fly Connectome networks. The methods with reinsertion arrive at the dismantling threshold in fewer number of removals, but the change in the LCC curve results in a worse final AUC.
We also see that the reduction in AUC is not proportional to the reduction in the number of removals, as seen in Figures and 12 for CND. Indeed, reinsertion, by definition, reinserts nodes that were ultimately unnecessary for the dismantling process to reach its target.
A significant limitation in previous literature is the lack of differentiation between algorithms that inherently include reinsertion and those that do not, leading inconsistent comparisons. To ensure strictly fair evaluation, we standardized two critical control variables across all experiments: the tie-breaking mechanism for the order of reinsertion and the stopping criteria. Furthermore, rather than arbitrarily assigning reinsertion strategy. we evaluated every method under the three reinsertion methods. We report the best performance for each method, ensuring that the results reflect the maximum potential of the dismantling strategy rather than an inconsistent application of reinsertion.
Ranking Stability. Across all tested reinsertion methods, the mean-fiee feendfieed ranking remains the same: NBC consistently outranks CND, which in turn outranks GDM. This order holds true both when
26

---

comparing specific fixed reinsertion methods and when selecting the best-performing method for each dismantling method. However, we observe a nuanced interaction between the dismantling algorithms and their best reinsertion strategy: the optimal reinsertion method varies (R2 is optimal for NBC, R3 for CND, and RI for GDM). For all other algorithms, though, R1 is the most effective reinsertion strategy."
Time Complexity. We report the total time complexity of each reinsertion method over the full reinsertion process in Table assuming all dismantled nodes are considered for reinsertion for every step and that all nodes are reinserted. Candidates for reinsertion are denoted as r. As a result, we multiply the per-step cost of updating for each method by the total number of reinsertion candidates. kmax is the maximum number of components node can connect to, equal the maximum degree in the original graph, and C' is the maximum size of any connected component during the reinsertion phase. For RI, the candidate node that ends up in the smallest resulting component selected. Reinserting node may merge up to kmax components, each of size at most C², requiring update of at most kmax C" nodes. These updates are tracked a binary heap of size r, where at maximum kmax C" nodes have be updated, giving cost of log( Amax C") per update. The per-step cost therefore OKkaax C" log(kmax C²). R2 selects the node that connects the fewest existing components. Unlike R1, it requires inspecting not only the components merged by the candidate node, but also the neighbors of the affected neighbors. This increases the complexity by a factor of kmax. resulting in per-step time complexity of O CC" log(kamxx C²). R3 evaluates each candidate by explicitly computing the resulting LCC size after reinsertion. Each evaluation requires a graph traversal recompute connected components, which takes O(N m) time on sparse graphs. This has to be done for each reinsertion candidate, at every step, so Or22(N
(N + m),
Table 7: Comparison of reinsertion methods. Criteria defines the criterion for selecting which node to reinsert. Tiebreak specifies how ties are resolved. LCC Condition indicates whether all dismantled nodes reinserted if reinsertion stops once the predefined LCC threshold is reached. Time Complexity denotes the time complexity of each reinsertion method on sparse graphs, for the whole reinsertion process. N: number of nodes. number of links. set of reinsertion candidates. kimax: maximum degree in the original graph G. C": maximum size of any connected component during the reinsertion phase. Used In lists the methods that use each method, in bold, the dismantling method that originally proposed that reinsertion method. An asterisk (*) marks components of the reinsertion method that were modified in our study, as detailed in Appendix
Name
Author
Year
Criteria
Tiebraak
LCC Con- dition
Time Complesity
Used In
RI
Braunstein
2016
Node that up amallestt component
disman-
Ofrikaax logs (ouax C I))
tling
ComGDD CorelID.
GDM,
GND
2016
Node con- nects to the fewest clostess
Reverse disman- ting order
Yes"
O(k C² log(A C())
etal.
2016
R3
Mugiséu
2016
Node that smallest crease in LCC size
Reverse disman- ting order*
Yes
O(r2(N + m))
BPD
2016
G DYNAMIC & STATIC DISMANTLING
In static dismantling, node scores are computed once at the beginning and are then removed in descending order of importance until the dismantling threshold is reached. In contrast, dynamic dismantling recomputes the scores after each removal. As shown in Figure [3] with CND given as an example, dynamic dismantling consistently outperforms static dismantling across all fields. Dynamic variants achieve lower AUC and fewer removals in every case, confirming the advantage of score recomputation.
27

---

0.4
-2.0%
CND-R1
CND-R2
CND-R3
0.3
CND
Mean AUC
0.2
-6.0%
0.1
Biomolecular
Brain
Covert
Foodweb
Infrastructure
Internet
Misc
Social
150
-19.8%
125
Mean Removals
100
-44.9%
-17.4%
75
-19.7%
-0.4%
50
25
-18.0%
Biomelecular
Brain
Covert
Foodweb
Infrastructure
Internet
MIsC
Social
Figure 11: Mean AUC and number of removals by field for CND without reinsertion and with each reinsertion method (R1, R2, R3) (n 1,237 for methods). Error bars represent the standard enror of the mean (SEM). Red text indicates the percentage improvement achieved by using the best-performing reinsertion method for each field. Quantitative results for AUC and removals improvement from each reinsertion methods reported in Table
28

---

0.4
RA2-R1
RA2-R2
0.3
RA2-R3
RA2
Mean AUC
3.4%
-3.1%
0.2
0.1
0
Biomotecular
Brain
Covert
Foodweb
Infrastructure
Internet
MISC
Social
-11.9%
125
Mean Removals
100
-003%%
-14.1%
75
-16.0%
-6.7%
50
25
-12.3%
22..8%
Biomolecular
Brain
Covert
Foodweb
Infrastructure
Internet
MIsC
Social
Figure 12: Mean AUC and number of removals by field for RA2 without reinsertion and with each reinsertion method (RI, R2, R3) (n = 1,237 for methods). Error bars represent the standard enror of the mean (SEM). Red text indicates the percentage improvement achieved by using the best-performing reinsertion method for each field. Quantitative results for the AUC and removals improvement from each reinsertion methods reported in Table g
29

---

Table 8: Percentage improvement for the mean AUC and mean number of removals for each reinsertion method over the baseline for CND and RA2 (n 1,237). In bold the method that improves the baseline the most, by field.
CND
RA2
AUC
AUC
R1
R2
R3
R1
R2
R3
Biological
11.2%
9.9%
Biological
8.0%
8.3%
8.5%
Connectome
1.9%
2.0%
2.0%
Connectome
-0.3%
0.0%
-0.1%
Covert
3.4%
3.5%
3.8%
Foodweb
2.2%
2.0%
2.0%
Foodweb
2.3%
2.0%
2.1%
Infrastructun
5.6%
5.0%
5.7%
Infrastructun
4.1%
3.4%
4.0%
Internet
6.1%
Internet
5.0%
4.3%
4.9%
Misc
4.4%
4.0%
4.2%
Misc
3.2%
3.1%
3.4%
Social
3.2%
3.1%
3.2%
Social
3.1%
3.1%
3.1%
CND
Removals
Removals
R1
R2
R3
R1
R2
R3
Blological
24.9%
21.9%
Blological
20.3%
19.1%
20.1%
Connectome
8.4%
8.2%
8.3%
Connectome
4.4%
4.4%
4.5%
18.0%
Covert
12.3%
12.1%
12.3%
Foodweb
8.0%
7.9%
8.0%
Foodweb
6.7%
6.2%
6.4%
Infrastructun
28.7%
26.2%
28.7%
Infrastructun
21.9%
19.4%
21.8%
Internet
17.5%
15.8%
16.7%
Internet
14.1%
12.6%
13.5%
Misc 19.8%
18.3%
19.3%
Misc
11.9%
10.5%
11.6%
Social
19.7%
17.5%
19.1%
Social
16.0%
15.3%
15.7%
Table 9: Full summary statistics of the ATLAS networks used in this study, averaged by field: number
of subfields and networks, average number nodes (N). number of edges (E), density {p), mean
degree ((d),, characteristic path length (L), assortativity (r) (Newman 2002 transitivity (T), mean
local clustering coefficient ((Loc. CC)) maximum k-core (kmax)) average k-core ((k)). LCP-corr
LLCP..mi (Cannistraci et al. 2013), and modularity (Q) (Newman 2004
Field
Riomolacatar
Amin
Cowert
Foodweb
Infrestuctone
Internet
Mise
Social
Total
Subfields
7
Netwooks
(N)
2.007
5,708
2,880
3.267
(E)
11,855
1,535
1,087
1,332
19,601
19.921
53,977
(p)
0.01
0.34
0.17
0.16
0.07
0.01
0.07
0.11
((d))
28.3
15.2
4.9
7.5
26.9
(r)
-0.03
-0.15
-0.88
-0.52
-0.33
-0.07
(T)
0.06
0.55
0.29
0.19
0.06
0.11
0.22
0.29
((Lo..CC)
0.13
0.63
0.16
0.22
0.31
0.34
0.36
(Ranns)
(())
17.5
8.3
15,4
(LCPcore)
0.66
0.97
0.76
0.67
0.15
0.94
0.85
0.77
(Q)
0.26
30

---

Table 10: Number and size of real-world networks tested by dismantling algorithms. N denotes the number nodes, E the number of edges.
Algorithm
Year
Networks
Nmax
Emax
Collective Influence (CI) Morone
2016
2016
2
14M
51M
CoreHD (Zdeborová et al.
2016)
2016
12
1.7M
11M
Explosive Immunization (EI) (Clusella
2016)
2016
5
50K
344K
Min-Sum (MS) (Braunstein et al.
2016
2016
2
1.IM
2.9M
Generalized Network Dismantling (GND)
Ren et al.
2019
2019
10
5K
17K
Resilience Centrality Zhang et al.
2020
2020
4
1K
14K
Graph Dismanting Machine (GDM)
Grassia et al.
2021
2021
57
1.4M
2.8M
CoreGDM (Grassia Mangioni
2023
2023
79K
468K
Domirank Centrality Engsig
2024
2024
58M
Fitness Centrality (Servedio et al.
2025
2025
5
297
4K
LGD-NA
2025
1,475
23K
507K
0.4
-7.4%
CND-D
CND-S
0.3
Mean AUC
-8.2%
20.6%
-11.5%
0.2
-10.4%
0.1
-12.5%
+7.4%
Biomolecular
Brain
Covert
Foodweb
Infrastructure
Internet
Misc
Social
-12.0%
500
-19.3%
Mean Removals
400
300
200
100
-33.5%
-7.4%
27.8%
-22.9%
0
Biomolecular
Brain
Covert
Foodweb
Infrastructure
Internet
Misc
Social
Figure 13: Mean AUC and number of removals for dynamic and static CND (n 1,296. Error bars represent the standard error of the mean (SEM). Red text indicates the percentage improvement achieved by using dynamic over static variants.
31

---

Table 11: Percentage improvement for the mean AUC and mean number of removals for dynamic CND over static CND (n 1,296), by field.
AUC
Removals
Biomolecular
12.53%
18.42%
Brain
7.37%
7.43%
Covert
10.35%
11.30%
Foodweb
20.57%
27.81%
Infrastructure
7.36%
22.95%
Internet
14.20%
33.47%
Misc
11.47%
19.27%
Social
8.22%
11.99%
Molecular Yeast Phosphorylation
Roadmap Anaheim
Email DNC Corecipient
Bird Connectome Synaptic
CND-D
CND-5
0.8
0.6
0.4
0.2
0.1
0
2%
4%
15%
30%
0
10% 20%
20%
40%
60%
Fraction of Nodes Removed
Figure 14: Dismantling process on example networks comparing dynamic and static CND. The plot shows the normalized size of the largest connected component (LCC) as a function of the fraction of nodes removed, with a target LCC threshold of 10%. Performance evaluated using the Area Under the Curve (AUC) of the LCC trajectory.
32

---

H ENGINEERING NETWORK ROBUSTNESS
Here, we would like to comment on the feasibility of our suggested network modifications practical scenarios. In the case of PPI networks, recent advances in structural modeling of molecules using AlphaFold (AF3) (Abramson et al. 2024) have reduced the longstanding limitations in testing and engineering arbitrary proteins. Coupling our dismantling predictions with AF3 could impact drug repositioning and drug design. For example, in the case of antibiotic- of how to dismantle the bacterial PPI network could be used to identify which proteins to target with repositioned, modified, or newly designed antibiotics. Meanwhile, to minimize side effects of newly designed drugs that target critical proteins in bacterial PPI networks, our reinforcement strategy based on common-neighhor generation could be applied to predict which protective bindings to promote in the human PPI network, thereby reducing the destructive impact of drug on a critical human protein whose impairment could cause side effects, Finally, the application of the proposed common- common-neighbor reinforcement strategy to increase the robustness of flight and shipping networks straightforward, as it can indicate which critical nodes should be reinforced by adding links between their adjacent nodes.
bacteria, knowledge
We validate our reinforcement strategy explained in Section 4.6 on three types of real-world networks considered critical: human PPI network (biological), flight map network (transportation with social and geographic constraints), and shipping trade network (transportation with economic and geographic constraints). We select the top 1% of highest-scoring nodes according to the chosen measure (NBC CND) and randomly add either 1% or 10% of the potential links between their respective adjacent nodes, thereby modifying the network topology according to the explainable rule discovered via CND.
Table 12: Area Under the dismantling Curve (AUC) for NBC and CND on the original network and "reinforced" networks, by adding 1% and 10% of the links between common neighbors of the top 1% of nodes. In parentheses the increase in the AUC compared to the original network, representing the reduction the dismantling effectiveness.
0% Links
1% Links
Links
NBC-
0,051
buseline
NBC-
0.093 (+88%)
(+11919))))))
reinforced
CND-
0.055
baseline
CND-
0.098 ((+7))))
0.198 (1-25996))
reinforced
Hight Map
0% Links
1% Links
Links
US
NBC.
0.042
haseline
NBC-
0.067 (46775)
(4
relnforced
CNT-
0,055
haseline
CND.
0.099 (5-9580)
0.172 ((-24196)
reinforced
Trade
0% Links
1% Links
10% Links
Shipping
NBC-
0.138
baseline
0.236 (+77%)
(-749))
reinforced
CND-
0,220
baseline
((+361)))
(1+59%))
reinforced
Our results in Figure 4 and Table 13 also confirm that engineering robustness translates into func- tional gains across the four real networks studied. Regarding Fault Tolerance, in the Drosophila Connectome and Flight Map. the analysis informs the design of fault-tolerant neuromorphic circuits and identifies critical hubs where reinforcement prevents systemic transport failure. For Security and Communications, in the adversarial systems (Terrorist Cell and School Contact Network), we can calculate the theoretical robustness ceiling, by accounting for unobserved links (e.g., dormant ties in
33

---

PPI Human
Flight Map US
World Trade Shipping
1
RBC CND
0.5
0.1
LCC
0
5%
10%
15%
5%
10%
15%
20%
40%
1% Nodes 1% Links
1
0.5
0.1
0
0
10% 20%
30%
10%
20%
30%
20% 40%
60%
1% Nodes 10% Links
Figure 15: Dismantling curve on the original (solid) and reinforced networks (dashed). The plot shows the normalized size of the largest connected component (LCC) as function of the fraction of nodes removed, with a target LCC threshold of 10%. Performance evaluated using the Area Under the Curve (AUC) of the LCC trajectory.
covert networks) and quantify the margin of error required to successfully disrupt communications or secure the network against epidemics despite incomplete data.
I FUNCTIONAL METRICS AND REAL- WORLD APPLICATION DETAILS
We now provide the specific experimental setup for the real-world functional experiments described in Section Unlike topological metrics (e.g., LCC size), these experiments measure the functional performance of the systems under dismantling.
Drosophila Connectome: We utilize the central brain connectome Drosophila melanogaster (FlyWire), comprising 125,000 neurons and 50 million synaptic connections. To assess func- tional performance, we employ a Leaky Integrate- and-Fire (LIF) spiking computational model, as established by Shiu al. (2024). We focus the sugar-sensing gustatory circuit (which results in smaller subnetwork of 377 nodes and 13.671 edges), critical pathway for feeding initiation. We simulate the activation of sugar-sensing Gustatory Receptor Neurons (GRNs), with a stimulation frequency of 100 Hz. We use the default parameters provided by Shhu et al. (2024), with the trial duration adjusted 100 ms for the sake of time. The performance metric is the Motor Neuron Firing Rate, MN9. A dismantling attack is considered successful if the removal of specific interneurons prevents the propagation the signal from the sensory GRNs the motor neurons, causing the firing rate to drop.
Paris/Brussels Terrorist Cell We analyze the network of the terrorist cell responsible for the November 2015 Paris attacks and the 2016 Brussels bombings (Gutfraind & Genkin 2017), with 77 nodes and 271 edges. In adversarial networks, the ability of the leadership to communicate with the rest of the operational network, and vice versa, crucial. As result, define Commander Reach as the percentage of network operatives (nodes) that retain a valid communication path to at least one of the three identified cell commanders.
34

---

Table 13: Setwork-specific evaluation metric and the original LCC AUC performance metric for four real-world networks, for NBC, CND, and RA2. N denotes the number of nodes, E the number of edges. Reinforced are the those reinforced by adding 10% of the links between common neighbors of the top 5% of nodes according to each method, as detailed in Appendix H In red the improvement robustness compared to the baseline network, assuming that a higher value indicates worse dismantling performance, meaning the network is more robust. Specific functional metrics are detailed in Appendix !
In bold the best method for each metric and network.
Drosophila Connectome
LGC
Sugar Firing Rate (Freq. 1000 100 Hz) AUC
N+377, Ex13,671
Baseline
Reinforcec
Baseline
Reinforoed
NBC
0.410
0,465
+14%
0.030
0.139
+363%
GND
0.454
0,461
+1%
0,093
0.180
+5396
RA2
0,48C
Paris/ uussells Terrorist
LCC AUC
Commander's Reach AUC
Cell
N-72, F-273
Raselina
Reinforce:
Raseline
Reinfored
0.284
0.182
CND
0.125
0.274
-12016
0.149
0.182
+22%
RyanAir Flight Map
LCC
Globel Efficiency AUC
1=128, E-601
Baseline
Reinforces
Baseline
Reinforced
0,040
+379%
CND
0.145
0.556
-196%
0.099
0.121
+207%
Contact
LCCAUC
Final Outbreaak Size AUC
N= N=-277_--,818 8-5,818
Baseline
Rainforcee
Baseline
Reinforoed
0,351
CND
0.420
0.452
+896
0,208
0.339
+17%
Ryanair Flight Map: This network represents the flight routes of Ryanair in Europe (Cardillo et al. 2013), with 128 nodes and 601 edges. Nodes represent airports, and edges represent direct flight connections. We measure the functional integrity of the transport system using Global Efficiency (Eytot), rather than the Average Shortest Path Length (APL), because: APL is mathematically undefined (or diverges to infinity) when network fragments into disconnected components, which inevitably occurs during dismantling. Global Efficiency avoids this divergence by averaging the inverse geodesic distances.
Eglob
N(N 1)
i dis
Where N the number of airports and dy is the shortest path length between airport i and j. If no path exists, क; = O. This metric correctly quantifies the remaining communication capacity of fragmented network.
School Contact Network: We utilize a contact network collected from a French high school (Mas- trandrea al. 2015), with 327 nodes and 5,818 edges, where nodes represent students and edges represent close-proximity physical contacts capable of disease transmission. We simulate the spread tealle--xxxooe--nneettii
(SEIR) compart- mental model (Anderson & May 199T). Unlike basic SIR models. SEIR includes an "Exposed" state account for the latency period typical of real-world pathogens. The simulation begins with 5% of nodes infected; over 200 discrete time steps, individuals progress from Susceptible (S) to Exposed (E) (based on contact with infected neighbors and rate / 0.01), then to Infected (I) (based on latency rate a 0.01), and finally to Recovered R (based on recovery rate 7 0.01). These uniform parameters were selected to establish a generic baseline, ensuring that observed variations in outbreak size are attributable to network topology rather than pathogen-specific characteristics. We average the results of 50 independent simulations. The functional integrity of the network measured by the Final Outbreak Size, defined as the total percentage of the population that was infected and subsequently recovered. The size is normalized with the size of the largest connected component, from which the epidemic starts from.
of infectious disease using a classic
35

---

Engineering Network Robustness Protocol: To validate method for "engineering robustness", we also reinforce these networks as defined in Section 4.7 choosing the top 5% of nodes and adding 10% of links, and rerun the dismantling process under the exact same conditions.
Table 13 shows the quantitative results for our original dismantling metric, LCC AUC, alongside the functional metries defined above. Notably, both metrics yield highly similar rankings of the top methods, further validating our choice of LCC AUC as a robust evaluation standard."
J GPU ACCELERATION
2, 0.04
y 2, p 0.08
2, p 0.2
10000
NBC-CPU
1200
5000
8000
1000
Time (sec)
4000
6000
3000
600
4000
400
2000
200
0
10a
10a
10a
10a
10
10
102
10f
10a
10
10a
10a
10a
10a
10a
Y 3, p
0.04
P
0.08
3, p
3500
10000
3000
6000
8000
2500
Time (sec)
6000
4000
1500
1000
2000
500
10"
10a
10a
10" 10a
102 10
10"
10"
10"
102
10a
10"
10 10"
Network (E)
Network (E)
(E)
Figure 16: Running time (in seconds) comparison between CND on GPU and NBC on CPU on synthetic nPSO networks, as a function of network size in terms of edges. Experiments were conducted with network sizes ranging from 10 to 2,499,500 edges with densities (p) of 4%, 8%, and 20%, using fixed temperature for N E {10, 50, 100), = 5 for N (500, 0000, C 10 for N 5, 000). See Figure 37 for quantitative results.
0.3 and community counts scaled by network size (C
Table 14: Average runtime (in seconds) and standard error of the mean (SEM) by field and method for dynamic dismantling. Evaluated on networks of up to 23,000 nodes and 507 700 edges (n 1,475). In bold the fastest method per field. (N) denotes average number of nodes and (E) number of edges.
Biomolecular
11,885
1,698.9
3.E
74.2
3.599.8
29,4
Brain 97
1,535
7.7
4.
0.2
7.
2.+0.11
7.3
0.+00.2
Foodweb
117
1,087
24.2
2,4
0.20011
25.4=10.8
1,800,2
1,332
34.9:116
Internet
5,708
19,601
6,148.2 a 863.2
34.2+3
138.6 15.3
9,801.8 1176.6
3.
2,880
19.921
3.641.8 1771.9
54.9
439.3
5,085.1 1990.8
Social
3,267
53,977
6.322.5=1287.6
149.4=20.1
4,840.6 1008.5
12.474.4*2148
161
Since the difference in running time between the three LGD-NA methods is not relevant, neither for CPU nor GPU, we report the running time of the original RA2 the main text (Figure and the CND in the Appendix (Figure 18). When comparing CND and NBC, on the largest network,
36

---

2,
0.04
y= 2, = 0.08
y 2, = 0.2
6000
10000
NBC-CPU
MND-GPU
5000
Time (sec)
800
4000
6000
600
400
2000
2000
200
1000
10a
10a
10
10a
10a
104
10
3,
0.04
3,
0.08
3,
0.2
3500
3000
6000
8000
Time (sec)
2500
6000
2000
4000
1000
2000
500
10a
10 10
102
10a
10a
10a Network Size (E)
10c
Network Size (E)
Network Size (E)
Figure 17: Running time (in seconds) comparison between CND on GPU and NBC on CPU on synthetic nPSO networks, conducted with network sizes ranging from 10 to 5,000 nodes with densities (p) of 4%, 8%, and 20%, using fixed temperature T 0.3 and community counts scaled by network size (C' 2 for N E {10, 50, 100), C 5 for N {500, 1, 000}, C 10 for N 5, 000). See Figure 37 for quantitative results.
function of network size in terms of nodes. Experiments were
CND-CPU
25
NBC-CPU CND-GPU
CND-GR
35
16
30
20
Time (hrs)
25
15
20
18.8
15
10
5
36
20
0.4 Arz
000000
0.4 hrs
0
100k
200k
300k
400k
500k
0
100k
200k
300k
400k
500k
Network Size (E)
Figure 18: Runtime (in hours) is plotted against network size, measured by the number of edges, E, for dynamic dismantling. The annotated time indicates the runtime for the largest network. Evaluated on networks of up 23,000 nodes and 507 507,000 edges (n 1,475). See Figure [4 for quantitative results.
37

---

Table 15:
Runtime (in seconds) for NBC run on CPU (graph-tool) and GPU (cuGraph) on subset of networks. N denotes the number of nodes and E the number of edges.
N
E
NBC-GPU
NBC-CPU
Foodweb Blackrock
86
375
4.7
0.04
Phonecall 2012
193
1,030
20.7
0.08
Rat Transcription 2010
524
1,081
37.9
0.10
Roadmap Winnipeg
1,040
1,595
848.3
0.41
GPU-accelerated CND is over 46 times faster than its CPU counterpart and also over 63 times faster than NBC rumning CPU.
To empirically validate these runtime advantages in a controlled setting, we conducted additional experiments using the nPSO model (Muscoloni & Cannistraci 2018b) with network sizes ranging from 10 to 5,000 nodes, and 10 to 2,499,500 edges, with densities of 4%, 8%, and 20%. We keep the temperature (lower temperature yields higher clustering) fixed (T 0.3) and adjust the number of communities to suit the size of the network (C = 2 for N E {10. 50, 100), C 5 for N E {500, 1, 000), C 10 for N E {5, 000)). Our results demonstrate that GPU-accelerated LGD-NA methods begin to show running time advantages over NBC-CPU when networks exceed approximately 1,000 nodes (see Figure 17] or 100,000 edges (see Figure [6p. This threshold aligns with our observations in real-world networks (see Figures B and 3 and Table [4). where GPU methods achieve superior running times for larger-scale networks such as biomolecular, internet, and social networks, while offering no runtime benefit for smaller networks where CPU implementations remain efficient.
Section 4.3 details how we implement the RA-based measures for GPU, using matrix multiplication. We end up with the following formula for RA2:
1 + EL ET + EE2 o E
RA2
1 1 CN12
and for CND:
CND CN1
In our experiments, the CPU-based RA2 and CND implementation uses Python's 's NumPy (imple- mented in C) while the GPU implementation uses Python 's CuPy (implemented in C++CCUDA).
As mentioned earlier, report only the CPU rumning time for NBC, as its GPU implementation did not yield any speedup. While some studies report GPU implementations of NBC with improved performance (Fan et al. 2017 Shi & Zhang, 2011 Pande & Bader 2011 Mc Mclauugliin & Bader 2018; [Sariyüce et al. 2013) Bernaschi et al. 2016 these are often limited by hardware-specific optimizations, data-specific assumptions (e.g.. small-world social, or biological networks), and using heuristics that are tailored to specific settings rather than offering general solutions. Moreover, publicly available code is rare, making these approaches difficult to reproduce or integrate. Overall, NBC is not naturally suited for GPU implementation, as it does not rely on matrix multiplication, but is based on computing shortest path counts between all node pairs. In our experiments, the CPU- based NBC implementation from Python's 's graph tool (implemented in C++), based on Brandes' algorithm (Brandes 2001) with time complexity ((N)) for unweighted graphs, outperformed the GPU version from Python's 's cuGraph (implemented for C++CCUDA).
is important to note that our LGD-NA implementation inherently utilizes a hybrid workflow: the sequential dismantling logic is managed by the CPU, while the expensive latent geometry estimations (relying on matrix multiplication) are offloaded to the GPU. This architecture is highly effective for LGD-NA but is not applicable to NBC. For NBC, the computational burden is the calculation of pairss shortest paths, a task that does not lend itself well to GPU computations, meaning hybrid pipeline yields significant performance gain, and thus solely runs CPU.
38

---

K NBC APPROXIMATORS
Table 16: Average runtime (in seconds), AUC, and number of removals with their associated standard error of the mean (SEM) by field and method for dynamic dismantling, Evaluated where Nman 2, 235, NNma 9, 885, Emin 10, 075, Emaz 506, 437, (n 157). In bold the best method per field, by runtime, AUC, and number of removals. (N) denotes average number of nodes and (F) number of edges.
Field
(E)
Method
Running time (sec)
AUC
Removals
CND
86 + 17
0.087 0.016
830 = 134
NBC
453 171
0.082
708 124
Biomolecular 5,528
26,804
NBC-20
437 = 183
0.011
705 = 124
NBC-log
365
0.08
733 130
CND
203 * 113
0.099
1,324 = 575
NBC
76
0.021
13
Infrastructure
5,803
15,068
NBC-20
105 a 43
0.022
249 16
NBC-log
141
0.022
2
CND
2
0
263
NBC
0.016
1
Internet
6,623
31,292
NBC-20
4
0.016 0.001
171#6
NBC-log
1
0.006
172
CND
121 *
0.134 = 0.03
1,114 #29
NBC
1,220 402
0.108
876 215
Misc
5,444
53,289
NBC-20
655 + 338
0.106
889 = 217
NBC-log
491
228
CND
405
0.325 * 0.019
2,805 * 218
NBC
14,961 2,782
2,527 206
Social
5,778
156,918
NBC-20
1,368 = 147
0.274 * 0.016
2,543 = 207
NBC-log
1,363 118
0.279 0.017
2,745 230
While the high computational cost of Node Betweenness Centrality (NBC) has motivated the devel- opment of numerous approximators (????), comparing against them is challenging due to the scarcity of standardized, publicly available code and the complexity of their sampling algorithms, which are often performant only for specific domains or incompatible with disconnected graph structures.
To address this, we implemented two standard randomized pivoting strategies for approximation. NBC-20 estimates betweenness centrality using a random sample of 20% the nodes. NBC-log uses random sample of 10 1og,(N) (N) nodes. NBC-20 prioritizes accuracy by always scanning fixed slice of the network (20%), whereas NBC-log prioritizes speed by scanning a much smaller, logarithmically scaled subset that grows very slowly the network gets larger. We evaluated these baselines against the exact NBC and our CND method on a subset of 157 networks selected for their size, where exact NBC calculation begins to become computationally expensive.
TTble/16|reports the dismantling performance (AUC) and total runtime, averaged by field. First, we see that the NBC approximators perform comparably to the exact NBC, even occasionally outperforming it. However, this performance increase of NBC approximators should not be overstated due to the smaller sample size of this experiment. Second, while NBC approximators than exact NBC, CND remains faster than both approximation methods in almost all domains. A notable exception occurs in the Infrastructure field. Here, the usually slowest method NBC is actually the fastest in terms of total runtime because it takes a significantly lower number of removals to dismantle the network. Consequently, even though CND faster per step, the NBC-based methods result in lower total runtime simply because the dismantling threshold reached much carlier.
significantly faster
Finally, it is critical to distinguish the theoretical foundations of these approaches. Existing NBC approximators focus accelerating the estimation of global metric. In contrast, LGD-NA leverages purely local topological information to directly estimate pairwise distances the latent metric space. This distinction allows LGD-NA to bypass the need for global knowledge more complex sampling strategies. Although approximation techniques improve NBC's speed, their reliance on sampling global paths is inherently less efficient than strictly local approach, validate in Table [6]
39

---

Furthermore, sampling global information remains vuinerable to missing data and adversarial noise. The strength of N.DNA, therefore, lies its ability to achieve high dismantling performance by directly utilizing local geometric insights, rather than attempting to approximate computationally intensive global metric.
L APPLICATION TO DIRECTED NETWORKS
While network dismantling has primarily targeted undirected networks Artime et al. (022)) many critical real-world systems, such as neural circuits, social media platforms, and financial transaction systems, are inherently directed. Although our LGD-NA framework is designed for undirected network, we explore its upplicability to directed graphs. Research on directed network dismantling is relatively underexplored. Directed Node Entanglement (DNE) (?) generalizes the network density matrix to specifically capture and disrupt directed information flow within a system. utilizes the non-backtracking matrix identify and remove the minimum set of nodes connecting distinct edge modules. Dismantling on Signed Networks based on Evolutionary Deep Reinforcement Learning (DSEDR) (?) an evolutionary deep reinforcement learning approach designed to dismantle signed networks by optimizing novel objective function. Embedding baatingg-ssddd Signed Network Dismantling (ESND) (?) combines giant component detection, network embedding, and node clustering identify critical nodes.
We evaluate our LGD-NA framework on directed graphs using two approaches: applying the original method (treating the graph as undirected) and directed variant where node scores are computed aggregating only outgoing links. For comparison, we implement Directed Node Entanglement (DNE) as a baseline specific to directed networks. We exclude other methods-such as the set-based approach of ? and the complex, multi-step frameworks DSEDR and ESND to maintain a focused comparison computationally efficient, node-ranking strategies.
Table 17: LCC AUC for the three LGD-NA estimators treating a directed network as undirected, their directed variant, and DNE, specific directed network dismantling method. In bold the best performing method per network. N denotes the number nodes and E the number edges.
College Messages
Drosophila Connectome N=377, E=13,671
Email EU N=986, E=24,929
N=1,899, E=20,296
CND
0.1426
0,4470
0.2710
CND-Directed
0.1537
0.4512
0.3064
RA2
0.1427
0,4529
0.2824
RA2-Directed
0.1466
0,4507
0,2955
RA2
0.1431
0,4625
0.2873
nA2 num-Dirrected
0.1485
0,4653
0.2984
DNE
0.4069
0.4923
0.4311
We focus on three directed networks from different fields. College Messages (Social) (?) represents private messages on social network at UC Irvine (1,899 nodes, 20,296 edges). Drosophila Connec- tome (Brain) (Shiu et al.) 2024), focuses the sugar-sensing gustatory circuit (377 nodes, 13,671 edges). Email EU (Social)(?) are anonymized internal emails from a European research institution (986 nodes, 24,929 edges).
Table 17 shows two key results. First, for our LGD-NA framework, treating directed networks undirected yields superior dismantling performance when applied this undirected way, LGD-NA outperforms the directed-speciffc DNE baseline, demonstrating its effectiveness directed networks.
directed variant. Second, even
Finally, our framework predicated on the association between network topology and a latent geometry. For directed networks, this relationship less established, with only preliminary studies (?).
40

---

Therefore, designing asymmetric network measures that account for directional flow remains open challenge, yet a promising direction for future research.
M EXPERIMENTAL SETUP
Baseline Topological Centrality Measures. We selected centrality measures cover diverse categories: shortest path-based (NBC), degree-based (degree), walk-based (eigenvector), random walk-based (PageRank), resilience-bate based (Resilience), and fitness-based (Domirank and Fitness centrality). We also tested closeness and load centrality. but both performed worse than NBC and rely on the same shortest- pattesst--athhhhe principle; thus, we retained NBC. Similarly, Katz centrality underperformed compared to eigenvector centrality and is also based on spectral properties of the adjacency matrix. For DomiRank, we tested three values for the numerator the a parameter formula: 0.1, 0.5, and 0.9. While the original study sometimes performs grid search to find the optimal per network, this is not feasible for our large-scale evaluation. Instead, we selected representative range and found that num 0.5 yielded the best performance, and report that value. The parameter controls the balance between local degree-base based dominance and global network-structun based competition. As O. the scores approximate degree centrality. As increases, nodes evaluated in increasingly competitive environments, where centrality depends more on non-local structural dominance than individual connectivity. For Fitness centrality, capped the number of iterations k = 100. Without this cap, the method took prohibitively long time to converge, especially on large networks.
Baseline Dismantling Methods. We selected the best-performing and most widely adopted dis- mantling algorithms from the literature (Artime al. 2024). As mentioned earlier, we did not include BPD and FINDER in our experiments due to unavailable and outdated code, respectively. For Collective Influence (CI), we tested values = 1, 2, 3, where & defines the radius ball centered at node i, and (i, E) is the frontier at distance (i.e., nodes exactly l hops away). We found that performed best across our benchmarks and report this setting, while
3 performed the
worst. For Explosive Immunization (EI), evaluated both scores o(1) and ( The o(!) score targets high-connectivity nodes to rapidly fragment the network early on. The g(2) score aims to prevent large cluster merges near the percolation threshold by avoiding the connection of separate components. We found that g!)) consistently outperformed d(2), and thus we use in our final experiments. For eigenvector centrality, we capped the number of power iterations to avoid long or unbounded runtimes, since convergence can be very slow in large networks. For PageRank, we used convergence tolerance of 10-6 as the algorithm runs until the change in scores falls below this threshold.
100
LGD-NA Measures. Our analysis of pure win rates (draws are excluded) in Table 18 reveals distinct domain-specins strengths. CND achieves the highest win rate in Biomolecular, Foodweb, Infrastructure, Internet, and Social networks. In contrast, RA2 is the preferred method for Brain and Covert networks. Notably, RA2 does not emerge as the top-performing method in any of the tested domains.
Table 18: Pure win rate (draws excluded), for LGD-NA measures, without reinsertion (n 1,296). In bold the method with the highest win rate per field.
CND
RA2
RA2num
Biomolecular
52%
30%
17%
Brain
28%
68%
4%
Covert
16%
42%
41%
Foodweb
67%
16%
16%
Infrastructure
65%
16%
19%
Internet
52%
46%
2%
Misc
41%
45%
14%
Social
51%
29%
20%
41

---

Robustness to Threshold Variations. As shown in Table 19 the mean field rankings of the methods are broadly consistent across removal thresholds of 10%, 25%, and 50%. While permutations occur, the dominance of NBC and CND is consistent across different thresholds, confirming that our conclusions are not artifacts of the 10% threshold.
Table 19: Mean field ranking with standard error of the mean (SEM), for different threshold levels (n 1,296). In bold the best method per threshold.
Threshold
10%
25%
50%
NBC
0
*
CND
3.625 + 0.56
3.5 + 0.5
3.25 0.25
RA2
4 0.93
3.875 # 0.79
5.125 + 0.77
RA2num
4.875 = 0.72
5.5 0.76
8.375 0.73
GDM
0.5
5.25 0.56
4.875 0.58
CoreGDM-NR
6.125 = 0.52
6.25 0.62
7.25 0.86
GND
8.875 * 2.07 2.07
7.75 * 2.09
5.875 * 1.83
Degree
8.875 0.64
0.83
9.75 0.8
Domirank do.s
8.875 = 0.64
8.625=02
= =
9.125 * 1.08
8.375 * 1.05
6.5
Fitness
9.5 * 1.34
8.625 * 1.03
7.375 * 1.02
Resilience
11.125 * 0.4
11.625 * 0.42
12.375 * 0.42 0.42
Cl11
13 0.63
12.625 # 0.42
13.125 = 0.44
El 01
13.625 + 1.29
15.25 # 0.45
15.5 = 0.38
Eigenvector
14.25 = 0.31
14.375 = 0.32
14.5 0.46
MS
15.125 = 0.61
15.375 # 0.56
14.625 # 1.27
CoreHD-NR
16 0.5
16 0.38
14.75 1.44
Note on Reinsertion. We did not apply reinsertion techniques on all networks included in the initial dismantling experiments. In some cases, certain methods performed poorly that applying reinsertion became prohibitively slow. To ensure consistency, we excluded these networks from the reinsertion analysis for all methods. Specifically, any method required more than 800 node removals to reach the dismantling threshold. Based on this criterion, 59 networks were excluded.
imposed cutoff: networks excluded if
LCC AUC as the evaluation metric. We employ LCC AUC as our primary evaluation metric because it provides unified standard for comparing methods across 32 distinct complex system domains. As the established standard in the vast majority of dismantling studies (Artime et al., 2024), allows for direct comparisons between diverse networks from disparate fields and different dismantling algorithms. While dynamical metrics offer specific insights, simulating 'live' system dynamies for every network is computationally unfeasible and conceptually inconsistent given the broad scope of domains. Crucially, our functional analysis in Section 4.7 demonstrates that rankings based on LCC AUC align closely with domain-specific functional metrics, validating LCC fragmentation as a reliable proxy for functional disruption. Note that lower number of removals does not always imply a lower AUC. Our AUC metric rewards methods that fragment the network early, even if they require more steps to reach the dismantling threshold. As shown in Figure 19 show cases where a method that reaches the threshold with more removals can still achieve lower AUC, due earlier damage the network structure.
42

---

Co-authorship NetSci
Flightmap US
Phonecall
1
RA2
RAZ
RmZ..
RA2
CND
CND
0.8
LCC
0.6
0.4
0.2
0.1
3%
6%
20%
40%
60%
4% 8%
12%
Fraction of Nodes Removed
Figure 19: Dynamic dismantling process on example networks comparing CND, RA2 and RA2 showing lower removal number does not necessarily mean a lower Area Under the Curve (AUC) of the LCC trajectory. The plot shows the normalized size of the largest connected component (LCCC) as function of the fraction of nodes removed, with target LCC threshold of 10%.
N TECHNICAL IMPLEMENTATION AND REPRODUCIBILITY
Code. All our methods are implemented in our codebase, available in the supplementary material. We implement RA2, RA2num- CND, NBC, well degree and eigenvector centrality. We also adapt and integrate the original implementations of Domirank centrality and Fitness centrality) Since no code was available for Resilience centrality, we implemented it ourselves based on the original description in the paper. Instructions for running these methods and reproducing the experiments are included in the supplementary material. We also provide a representative network from the ATLAS dataset for testing purposes. For GDM, CoreGDM, GND, CI, EI, MS, and CoreHD, we use the publicly available code from Artime et (2024)'s ss review.
Computational Resources. All experiments were conducted on machine equipped with an AMD Ryzen Threadripper PRO 3995WX CPU (64 cores), 251 GiB of RAM, and single NVIDIA RTX A4000 GPU with 16 GiB of memory. All code was implemented in Python, with dependencies and library versions specified in the supplementary material to ensure full reproducibility.
Quantitative Results. All results are in Tables 23 in the Appendix.
25
30
and 35
O DISCUSSION, LIMITATIONS, AND FUTURE WORK
Missing or Manipulated Data. The robustness of our LGD-NA methods to missing or manipulated information, such missing neighbor data adversarial modifications neighborhood structure, is crucial question for practical applications of any network analysis method, especially those relying on local information. Our LGD-NA methods, by design, are inherently more robust global missing manipulated information compared to methods that require complete global view of the network (e.g., exact NBC). Since our methods rely solely on local neighborhood information, random missing data across the network would primarily affect only the scores of directly impacted nodes, rather than propagating errors throughout the entire graph. Similarly, adversarial modifications would need to target specific local neighborhoods to significantly alter node's dismantling score, making large-scale, coordinated attacks more challenging than for global metrics. However, we acknowledge that direct adversarial manipulation of node's immediate neighborhood could indeed impact its calculated score.
While many real-world systems, such citation networks, neural synaptic connections, transportation and trade networks, contain directed interactions, our LGD-NA measures focus unweighted topologies for two key reasons. First, in practical dismantling contexts, weight data is often dynamic, temporal, or unavailable, whereas topology is more robust. Second, current state-of-the-ee dismantling algorithms focus unweighted graphs (Artime al. 2024), making fair
Weighted Networks.
43

---

comparisons impossible. Consequently, we consider the extension of latent- geonett approaches to weighted graphs as a promising avenue for future work.
Limitations. A limitation of this study is the mismatch between theoretical and observed runtimes, which can vary across methods. These differences stem from factors such as the programming language used, hardware acceleration, and implementation-Iewe optimizations. However, all experi- ments were run on the same CPU and GPU to ensure fair comparison, and we made a strong effort to optimize all methods both terms of runtime and dismantling performance. For example, we tested different parameters for Domirank, CI, and EI, and evaluated multiple variants of shortest path-based and spectral partitioning- based centrality measures. Furthermore, we were unable to test on extremely large networks due to hardware constraints and the high computational cost of running a broad set of dismantling methods. However, we are confident that our results would generalize to larger networks, given the diversity of the 1,475 networks tested, spanning wide range of domains and sizes from very small to large. Another limitation relates to the parameter tuning required by some baseline methods, especially machine learning-based approaches and Domirank. Due the scale of our experimental setup-both in the number and size of networks-we were unable to perform extensive tuning. Although targeted tuning could enhance performance for specific methods on individual networks, it would compromise consistency across the wide range of complex systems domains considered. contrast, LGDDNA requires no parameter tuning and consistently achieves strong, generalizable performance across all tested networks.
Future Work. Future research could further explore latent geometry, particularly how to effectively combine local and global information in dismantling strategies. Improving the scalability of matrix- based computations, especially for very large and sparse networks, is another important direction. There is also need for cost-efficient dynamic dismantling strategies that reduce the overhead of recomputing scores after every node removal without significantly sacrificing performance. In addition, edge dismantling remains a relatively underexplored area compared to node-based disman- tling, and it would be valuable to investigate whether latent ceometry-drivee principles can also guide the efficient removal of links in complex networks. Targeting edges can be just as important as targeting nodes, and in many weal-world systems, such as transportation networks (railroads, roads, subways, or shipping trade routes), edge removal may represent the more realistic and sensible threat scenario, making it highly relevant for dismantling strategies. Finally, our work can also be of interest. to Explainable AI (XAI) for models like GNNs and Reservoir Computers (RC). By identifying critical (dismantling) unimportant (percolation) nodes in network, we conduct "perturbation experiments" to assess their impact on an ML model's 's performance. This process reveals which parts of the graph are most crucial for the model's predictions computations, effectively opening the model's s "black box" and providing crucial insights into its internal decision-making, robustness, and vulnerabilities.
P ETHICS STATEMENT
The research on network dismantling presented in this paper has potential for dual use. The techniques developed to identify and exploit network vulnerabilities could theoretically be used to design targeted attacks on critical systems. such as communication. transportation, or power grid networks. However, it can also be used for defensive strategies. A thorough understanding of network vulnerabilities is a prerequisite for designing robust systems. To directly address the dual-use concern, we demonstrate the constructive potential of our work by presenting a novel technique for proactively engineering network robustness using our latent geometry-basee methods (see Section 4.6). This application moves beyond vulnerability analysis to provide an explainable framework for modifying a network to enhance its resilience. Finally, by openly publishing our theoretical foundations, source code, and comprehensive evaluations, aim to ensure that the benefits of this research, namely the ability to secure critical networks, are accessible to all. We believe the societal benefit of advancing defensive capabilities significantly outweighs the risk of potential misuse.
44

---

Q REPRODUCIBILITY STATEMENT
To ensure full reprodueibility, we have made our source code publicly available, including detailed instructions on how replicate all experiments. The codebase includes an implementation of our LGD-NA framework (illustrated in Figure D the exact formulas used (detailed in Appendix (A). and an example network for demonstration. The code is compatible with both CPU and GPU environments and also provides the necessary tools to engineer network robustness as described in this work. The baseline methods were implemented using the code from the review by /Artime et al.
(2024). The exact topological measures of all networks used in our study are provided in Appendix 2 Further details regarding the experimental setup, including hardware specifications, are described in Appendix M and N
R CLAIM OF THE LLM USAGE
We used LLM-based tools to improve the language and flow; the principles, core logic, and innovations are entirely the authors'.
SUPPLEMENTARY MATERIAL
Table 20: Pearson correlation between between all the pairwise hyperbolic distances of the network nodes in the original nPSO model and in the reconstructed hyperbolic space (HD-correlatie (Mus coloni et al. 2017). Mean values over seeds and Standard Error of the Mean (SEM) are reported, and the Fisher p-value in parentheses. The power-law exponent represents the scale-freeness found real-world networks. networks. p is the density of the networks. Fixed parameters are the number of nodes, N 500, and the number of communities, C = 5. The temperature T controls the level of clustering (lower temperatures yield stronger clustering).
N=500, C=5
p=0.04
p=0.08
p=0.2
T=0.3
= (0.000)
0.792 0.002 (0.000)
0.846 0.001 (0.000)
CND
T=0.6
A.893+00004 (0.000)
0.768 = 0.002 (0.000)
0.801 + 0.001 (0.000)
T=0.9
0,633 * 0.008 (0.000)
0.765 0.003 (0.000)
8.777 (0.000)
y=2
T=0.3
0.521 (0.000)
0.532 = 0.007 (0.000)
0.521 + 0.010 (0.000)
RA2
T=0.6
0.524 0.007 (0.000)
0.484 0.010
0.308 0.008 (0.000)
T=0.9
0.498 0.003 (0.000 (0000))
0.460 0.004 (0.000)
0.303 + 0.008 (0.000)
T=0.3
0.584 = 0.004 (0.000)
0.624 0.003 (0.000)
0. 0.645 + 0.001 (0.000)
CND
T=0.6
0.510 (0.000)
0.579 0.002 (0.02
0.590 0.002 (0.000)
T=0.9
0.452 0.004 004 (0.000)
0.552 0.003 (0.000)
0.597 + 0.003 (0.000)
y=3
T=0.3
0.685 + 0.009 (0.000)
0.714 (0.000
0.783 + 0.008 (0.000)
RA2
T=0.6
0.722 0.003 (0.000)
0.780 0.003 (0.000)
0.805 0.006 (0.000)
T=0.9
0.688 + 0.002 (0.000)
0.795 (0.0000
0.755 + 0..10
45

---

Table 21: Pearson correlation between estimated link weights from CND and RA2 versus true geometric distances in nPSO networks. Mean values over 10 seeds reported, with color gradient where green corresponds to values approaching and red to values approaching -1. The power-law exponent ty represents the scale-freeness found in real-world networks. networks, is the density of the networks. The temperature T controls the level of clustering (lower temperatures yield stronger clustering). Fixed parameters the number of nodes, N 500, and the number of communities,
C = 5. Standard Error of the Mean (SEM) and Fisher p-value are found in Table 22
N=500,C=5
p=0.04
p=0.08
p=0.2
T=0.3
0.534
0.641
0.664
CND
T=0.6
0.602
0.675
0.719
T=0.9
0.649
0.690
0.746
y=2
T=0.3
-0.044
0.062
0.319
T=0.6
0.066
0.239
0.562
T=0.9
0.140
0.361
0.682
T=0.3
0.329
0.370
0.394
CND
T=0.6
0.543
0.512
0.473
T=0.9
0.607
0.553
0.510
y=3
T=0.3
0.301
0.388
0.530
RA2
T=0.6
0.441
0.542
0.625
T=0.9
0.473
0.588
0.669
Table 22: Pearson correlation between estimated link weights from CND and RA2 versus true geometric distances nPSO networks. Mean values over 10 seeds is reported and Standard Error of the Mean (SEM) are reported, and the Fisher p-value in parentheses. The power-law exponent represents the scale-freeness found real-world networks. networks. p is the density of the networks. Fixed parameters are the number of nodes, N 500, and the number of communities, C 5. The temperature controls the level of clustering (lower temperatures yield stronger clustering).
N=500,C=5
p=0.04
p=0.08
p=0.2
T=0.3
0.534 0.000
0.641 0.004 (0.000)
0,864 0.001 (0.0)
T=0.6
0.003 =
0.003 (0.000)
0.675 * 0.005 (0.000)
0.001
T=0.9
0.02 (0.000)
0.690 0.004 (0.000)
0.746
y=2
T=0.3
0.004 (0.000)
0.062 0.003 (0.000)
0.319 (0.0)
RA2
T=0.6
0.066 (0.000)
+ (0.000)
0.562 (0.00
T=0.9
0.140 (0.0000
0.361 0.004 (0.000)
0.682
T=0.3
0.329 = (.00
0.370 = 0.003 (0.000)
0.394 x 0,006
CND
T=0.6
0.543 (0.000
0.512 0.002 (0.000)
0,473 0.004
T=0.9
0,603 (0.000)
0.553 = 0.001 (0.000)
0.510 0,003
3=3
T=0.3
0.301
7.388 003 (0.000)
0.530 0.003
RA2
T=0.6
0.441 = 0.003 00003))
0. 3.542 + 0.003 (0.000)
0.625 + 0.003
T-0.9
0.473
0.588 0.002 (0.000)
0.669 0.00
END-
CND-
DINEOR-AE
Serelecarr
13754-8331
03722 0016
13101-3310
0202 00092
0.3772-0.22
93951-0.32
6270319521
03706-0022
Bean
84377-9332
0083
9.3393-3332
1000
64323-3
0.206+0001
0342++000 00033
02707-0012
92276-001
025724043
02390+135
92004-001
92296-0.00
02377+0.005
82330-1.37
05507 0007
0274248577
13401-3335
00515-40000
00050 +0000
8388-0000
0042940103
0285243355
03915-0.00
Soiki
0240842330 216
0.000 40074
1220941815
0530PAD155
8265642224
0.209-00144
110
552
Bal
64128 955
93711 40081
9451
0415-C313
$444-000 1.00
5367 C0EET
06: 500
53793 -0493
03879-8.31
EX117 MEE3
15772-082
1008
1565
15184
51144 00089
61393-625
68K0 8.00
68807 1004
20089 0233
6462 183
306 3063
00681 30
1944 C003)
06596 130
8079 04493
06477-133 133
6337 63771-3044
Soodd
035228 2:14
6.023-6005
02588-200 2014
22443 0054
03330 -314
12345-0034
03853-8317
-003 0333
02455
02340-131 9314
1240)-2034
Table 23: Mean and standard error of the mean (SEM) for the AUC per field, by dismantling method (n 1,296). In bold the best method per field.
46

---

Table 24: Mean and standard enror of the mean (SEM) for the number of removals per field, by dismantling method 1,296). In bold the best method per field.
Digse
037437
71,02
13A+20
184-18
$4.2423
35.613
IC.417
18.+1.7
805.1.7
833437
15:147
71.2-144
204143
153422
17.1434
163-18
198464
148+51
352422
353423
T53423
32.143
1831667
383150
Scarnt
800133
069:33
1358-73
86:58
1862183
908-34
168344
06-133
878122
1003141
162163
MBc
2073-1584
2225
3382-3233
MAGA
2113 21.3-0.
SW3:51
20311 713
303-3
26 26-11713
274+15
05.--33
630-18
614116
53
935-12
403-46
647-34
463-5
430-12
452-53
SL3-13
40-42
415+45
444-52
446-3
433146
653-5
7K2-27
-25--11
29-3-10
1165-30
183-4
245723
2313-1
962:33
125-13
15284223
12 108
501.1094
142241003 1767
28584811
01734783
Table Ranking per field for selected dismantling method (n = 1,296). In bold the best method per field.
100000
2020
CO
Table 26: Mean and standard error of the mean (SEM) for the AUC per field, by dismantling method, for reinsertion method R1, (n 1,237). In bold the best method per field.
AUC
C1:41
CMD R1
CsrcooM
CerenD Rt
Domironk #
Finees
0DM-R5
NS-
NBC
Blomotecular
0.025
0.0662
9.227
0.2000
0.207
0.2811- 0.009
Isbrasructare
0.8521 2.002
0.9453+0.003
0.087
0.0500 0.503
0.001
Internet
3
0.0567 0.00
3.098
0.0062
0.069 003
0.0599
0.0673 0.003
0.8652 6.313
Misc
0.1943
0..00
0.1069 0.025
0,1805 0.025
0./055
0.2023 029
0.1929 00025
0.1855 0.009
0.1590 0,025
0.3732 8.025
Sociat
022337 -1.15
137375
012061
8.015
0.2028-0.013
0.300/
3.8323 11 015
0,0022
01005
0,2238 0.035
0.3683 8:334
Table 27: Mean and standard error of the mean (SEM) for the number of removals per field, by dismantling method, for reinsertion method RI, (n 1,237).In bold the best method per field.
Rereenals
Cliodt
CHD-81
CacSOM R1
CarcH0-1
Domirask
CDMR1
MS-Rt
NBC-81
alsmslecutar
70.1-11.5
72.1422.
71.54
68.
7254
72.5-12.9
71.9.12.1
71.241.8
66.4
Bruin
55.3+09
16.1+19
543+01
543+009
$4.3-09
S4A-0.
50.2+0.
52.+0.5
13:11
12.51.5
12.7.15
12.3.10
12.8:15
12.3:16
12.61.4
13.91122
12:12
Footwet
41.2440
388:4.
55.3481
15.5499
83-3-84
Table 28: Ranking per field for selected dismantling method, for reinsertion method R1, (n = 1,237). In bold the best method per field.
Parkiing
NBC-1
CND41
60M4R1
DtredDM-Rt
Fitress-i
Dantrark dts--1
Cha-81
HS-81
CarcHD-81
Bloreotecutor
0
5
Brain
Infrustucturee
1
Internet
2
Misc
Secial
47

---

Table 29: Mean and standard error of the mean (SEM) for the AUC per field, by dismantling method, for reinsertion method R2, (n 1,237). In bold the best method per field.
AUC
Cluy R2
CND-B2
ConoCOM-R
Cord 12-22
Doreraate Bu.
Fibras-ff2
G014-2
PS--22
NOC-42
Blersotccllar
0.002 0.0G4
0.0672 0.22
0.0613 0.523
0.000 0.22
0.0538 0.234
0.054 0.025
0.0822 0.222
0:0725 +.022
0.5485
Brain
-0.000
0.5005 0.500
0.5001 0.362
0.008: 0.000
0:4045
0.6043 0.022
0.3066 0.232
0.4897 9.002
0.3650
0.1272
Intrect
0,057-0..00
0.0000
0.0687 0.22
0.0006
0.0659 0.822
0.8588+
0.0887
0.003
Mic
0.187
0.823
0.1346
0.1856-0.815
0:1508- 9.036
0.2830
0.1711:0.025
Social
0.2168 0.015
0.1677.0.554
3.207 0.005
222 0.666
0.2118 0.035
0,2107 0.835
0,2066 9.035
6
8,3862 9.054
Table 30: Mean and standard error of the mean (SEM) for the number of removals per field, by dismantling method, for reinsertion method R2, (n = 1,237). In bold the best method per field.
Ch:433
Brai
85.1+0.9
15.733
35.1+00
25.1+03
Cowert
13
1277:15
128:115
12.8:3.
12:
12.0:1.
112::12
Foodwebb
22.1..7
4.2-47
42.144
4L2+4.
41.1-47
41.244
42:1448
41+48
35.5-46
Irhuntouctare
15.0-211
135-18
36+2
165+12
36.5+21
16.5
16.2.1
34.-222
22.3-16
Interstt
767722
786:33
78:21
77.85
61.5334
12:1335
789::3
77.5x3
76.1224
Miso
10.9+22.
99.3-225
1223+342
104.2+24.3
162.5+241
108-24.6
223.2
206-24.3
12.8
Social
04:85
12.--M
BLC+8.7
83.
15.7+87
83.91877
05.1189
06.118.7
$7.6773
Table 31: Ranking per field for selected dismantling method, for reinsertion method R2, (n = 1,237). In bold the best method per field.
Boniing
NBC-F2
CND-F2
0DM-82
DoreGDM
Finess RD
Domirank OR-2
MS-R2
CarHHD-R
Blerotecutor
Cowert
Fandweb
1
3
5
Intrastucture
1
4
2
3
Interset
5
Misc
Table 32: Mean and standard error of the mean (SEM) for the AUC per field, by dismantling method, for reinsertion method R3, (n 1,237). In bold the best method per field.
AUC
CHO 90
Ca0c00M 8g
CarcHD Rg
Domtmek mna-3
Ritres R3
0DM-R3
NSS-8
MBC
Moomolecstar
8.0965
0.0611+0.02 023
0.000
0.224
0.8619
1.002--D.E2
0,0404
Foodweb
0.27540.02
0.2227
0.21540..3
0.2689
12212000.00
1.8911-0.88
Inhrestructrr
0.0582 0.004
8.3645
0.847+0.00
0.0532 3.033
0.065 8.000
0.6658-0.800
0.0500 0.000
Internet
0,0902 000
8 0.0999.10
04591 0.0
0.0884-3.00
0.00
6.0680 0.803
0.009 0.000
0.0677 0.808
0
0.1948 028
9.1869 + 0.025
0.1892 0.02
0.2030 4.025
8.1005 8.025
6.1548+0.025
0.1507 9.025
0,200.025
0,1711 0.625
Social
0.33--0.055
9. 9.1875 10.0
0.303300.155
0.2015
0.2000-0.0115
D.2260 2.015
8,2953 0.515
0.1857
Table 33: Mean and standard error of the mean (SEM) for the number of removals per field, by dismantling method, for reinsertion method R3, (n 1,237). In bold the best method per field.
Renivaas
Cli-Ra
ChD-R8
CHHe0M Rg
CarcHD 95
Domiisnk 6-3
Finees R5
00M
HS
HBC
Blorslecudor
20.6
72.8
72.6
70.24
70.44
76.2
70.44
71.94
66.34186
Foodwcd
Infrssracter
12.4
13.522
16:+2
54x2
12.7+2
24.2.3
12.3-16
Internet
7L6:2.
77.112
77.21
76
8033:3
11:1
76.33
7541277
76.124
Misc
30.+
25.7+23
120.1+23.0
20..
2
104.3-245
203.922.8
20.54232
525+216
Socie:
19.7+33
813182
13:11
83.188
36+1.5
543106
25:3.
633184
37.5+76
48

---

Table 34: Ranking per field for selected dismantling method, for reinsertion method R3, (n 1,237). In bold the best method per field.
hanking
NBC-R
CNO-P3
CDM5R3
CarcCoM-13
Fitsessfi
Demirunt ox-
Cl.-/33
MB-40
CareHD-is
Covnrt
Foodwes
3
Intrrsucbbre
4
7
Internet
7+0.00
Table 35: Ranking per field for selected dismantling method with their best-performing reinsertion method (n 1,237). In bold the best method per field.
Ranking
Bommleecatr
2
Blain
Mic
Sacial
Maar SGV
210
5.77
0.37
6.0.M
4.375 0.60
7:0.0
8,25 0.26
8.275 C-36
Table 36: Average AUC by field for top two performing methods: NBC and CND, under different reinsertion methods (n 1,237) and without reinsertion (n. 1,296). In bold the best method per field and reinsertion method.
Baseline
R1
R2
R3
NBC
CND-R1
NBC-R1
CND-R2
NBC-R2
CND-R3
NBC-R3
Biomolecular
0.072
0.058
0.056
0.049
0.057
0.048
0.057
0.048
Brain
0.388
0.362
0.381
0.368
0.380
0.366
0.380
0.386
0.110
0.116
0.105
0.115
Foodweb
0.215
0.195
0.210
0.197
0.211
0.196
0.211
0.196
Infrastructure
0.048
0,040
0.045
0.041
0.045
0,041
0.045
0,041
Internet
0.058
0.057
0.053
0.057
0.053
0.057
Misc
0.204
0.171
0.186
0.173
0.187
0.171
0.187
0.171
Social
0.232
0.204
0.198
0.188
0.198
0.185
0.198
0.186
49

---

Table 37: Running time (in seconds) comparison between CND on GPU and NBC on CPU on synthetic nPSO networks. Experiments were conducted with network sizes ranging from 5,000 nodes and densities (p) of 4%, 8%, and 20%, using fixed temperature T 0.3 and community counts scaled by network size (C = for N E {10, 50, 100), C for E {500, 1, 0000, C' 10 for N 5, 000). In bold the fastest method per network. N denotes number of nodes and E' number of edges.
N
CND-GPU
NBC-CPU
10
0.22
0.020
0.011
2
10
20
0.44
0.008
0.003
2
10
30
0.67
0.007
0.004
2
50
49
0.04
0.19
0.13
50
98
0.08
0.37
0.20
50
245
0.20
0.80
0.16
100
0.08
1.23
0.23
100
0.20
3.10
0.52
500
4,990
0.04
8.78
3.26
2
500
9,980
0.08
11.62
4.75
2
500
24,950
0.20
15.76
12.83
1,000
19,980
0.04
23.93
9.53
1,000
39,960
0.08
33.47
10.30
1,000
99,900
37.50
5,000
499,900
390.67
1,304.82
5,000
989,800
0.08
674.40
5,860.19
5,000
2,499,500
0.20
1,448.55
9,632.88
3
10
10
0.22
0.003
0.002
3
10
20
0.44
0.004
0.002
10
30
0.67
0.005
0.002
50
0.04
0.23
0.07
50
0.67
0.16
100
198
0.04
1.12
0.11
3
100
396
0.08
1.81
0.22
3
100
990
0.20
2.77
0.40
3
500
4,990
0.04
12.97
4.64
3
500
9,980
0.08
17.18
6.69
500
24,950
0.20
21.37
9.38
1,000
34.24
25.47
35.08
1,000
99,900
44.92
5,000
499,900
0.04
632.02
3,593.83
3
10
5,000
989,800
0.08
946.71
7,367.02
10
5,000
2,499,500
0.20
2,090.94
10,122.08
50


Reviews:
[{"review_id": "PzGMx7xRHV", "reviewer": "Reviewer_vDje", "summary": "The submission makes a contribution in the area of network dismantling, which largely has to do with understanding vulnerabilities of large and complex networks.  The paper proposes a new framework that provides insight into the geometry of the latent manifold and applies it to a wide range of networks with excellent performance.", "questions": "Although I do not work in the area of network dismantling, a classical approach that is inherently geometric and is also known to be powerful for robust network design is spectral graph theory, leveraging the spectra of graph Laplacians.  Is there any existing work on the use of Laplacians for this task?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is quite well written.  The experimental study also appears to be extensive with accompanying code that will be freely distributed.\n\nThe experimental study is extensive and compares to a lot of other methods.", "weaknesses": "Limitations were not discussed in the main body and relegated to the appendix.  In the revision, it is important to include at least a brief discussion of the challenges and limitations of the contribution in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vK7XVZLcXf", "reviewer": "Reviewer_jELD", "summary": "The paper proposes Latent Geometry-Driven Network Automata (LGD-NA) for network dismantling. The general idea behind is to estimate effective link distances using local “network automata” rules and rank nodes by the sum of their incident dissimilarities, where highest-scoring nodes are removed with dynamic recomputation. This paper evaluates the proposed methods across a very large “ATLAS” of 1,475 real-world networks covering 32 domains, using AUC of the LCC curve (10% threshold) as the metric. Additionally, it also studies optional reinsertion strategies, where a GPU implementation is reported to yield substantial speedups and latent-geometry estimators (including betweenness as a global estimator) can explain why these strategies work. Finally, this paper leverages CND’s explainability to “engineer robustness” by adding edges among neighbors of critical nodes.", "questions": "1. Could you clarify whether CND or RA2 actually outperform NBC in accuracy across the dataset or whether their advantage is primarily speed, and include a consolidated table with AUC gaps with and without reinsertion.\n\n2. What explains the lack of GPU gains for NBC and would approximate betweenness or hybrid CPU GPU pipelines change the outcome.\n\n3. How sensitive are the conclusions to thresholds other than ten percent and to alternative fragmentation metrics, especially when stratified by domain or graph statistics.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The method offers an intuitive latent geometry framing with dynamic recomputation, which remains simple, general, and effective in practice.\n\n2. The evaluation spans 1,475 networks across 32 domains and follows a clear LCC AUC metric and protocol.\n\n3. Matrix formulations together with a GPU implementation yield speedups that make the approach scalable.\n\n4. The paper translates insights into an easy robustness intervention by closing triangles among neighbors of critical nodes.", "weaknesses": "1. There are no theoretical guarantees that connect the proposed geometry estimators to near optimal dismantling orders, leaving the case largely empirical.\n\n2. Runtime comparisons underrepresent strong GPU or approximate betweenness baselines, weakening claims about practical efficiency.\n\n3. Mean field ranking and a single ten percent threshold may hide domain specific behavior, and guidance on when CND versus RA2 is preferable is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LS8QRltzVB", "reviewer": "Reviewer_a3SW", "summary": "Latent Geometry-Driven Network Automata Framework\nThe LGD-NA framework introduces a novel approach to network dismantling by leveraging local network automata rules to estimate effective link distances. ​\n\nLGD-NA utilizes local automata rules to approximate node distances, enhancing dismantling efficiency. ​\nIt identifies critical nodes and captures latent manifold information for effective network dismantling. ​\nThe framework outperforms existing algorithms, including machine learning methods, across 1,475 real-world networks. ​\nA common-neighbor-based rule achieves near state-of-the-art performance, demonstrating the effectiveness of minimal local information. ​\nGPU acceleration enables efficient scaling to large networks, significantly reducing running times. \n\nThe paper empirically validates the approach.", "questions": "Your notion of NETWORK ROBUSTNESS is theoretical only. Please define it precisely. How does NETWORK ROBUSTNESS apply to the 3 applications pointed out above, in a precise sense: fault tolerance, communications,  security? I am looking for validation of the strong claim: \"a novel strategy to engineer network robustness\".", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Contributions:\n 1.  Latent Geometry-Driven (LGD) dismantling, where methods estimate effective node distances on a network’s latent manifold to expose critical structural information. \n\n2.  LGD-NA framework uses local network automata rules to approximate these geometric distances; a node’s summed distance to its neighbors estimates how critical it is for dismantling. \n\n3.  simple common neighbors-based rule, which we term Common Neighbor Dissimilarity (CND), is highly effective, achieving performance close to the state-of-the-art method, NBC. \n\n4.  comprehensive experimental validation on an ATLAS of 1,475 real-world networks across 32 complex systems domains, the largest and most diverse collection to date, showing that LGD-NA consistently outperforms all other existing dismantling algorithms, including machine learning methods.", "weaknesses": "I have issues with the objectives of a framework for LGD dismantling: what is the purpose of knowing about dismantling?\n\n--fault tolerance: will a system fail?\n\n--communications: will communications be disrupted?\n\n--security: can a system's security be compromised?\n\nThe metrics used are totally abstract, and I would like to see a real-world application that shows the significance of your results. At present, it is an extension of small-world theory with no clear application.\n\n\n\n\nThe paper makes overly general claims about manifolds and the applications of this approach that must be scaled back, e.g, \"network geometry captures essential structural and dynamical properties of complex systems\". There is also the strong claim: \"a novel strategy to engineer network robustness\". The latter claim is unsubstantiated. Robustness is undefined; you are engineering graph-theoretical properties, not a precise notion of robustness.\n\nOriginally, small-world graph research showed that systems possess shared graph metrics. Now, you are using dismantling methods, but for what purpose? You need to show how dismantling impacts system performance. All you do is apply small-world theory with an application driven framework, and you MUST look at the application.\n\nYou need to be more precise about your use of manifolds and manifold theory. In complex systems, a latent manifold is a hidden, often lower-dimensional structure that captures the essential dynamics or configurations of the system. These manifolds are not directly observable but can be inferred from data using techniques like:\n\n--Nonlinear dimensionality reduction (e.g., t-SNE, UMAP, Isomap)\n\n--Autoencoders and variational autoencoders (VAEs)\n\n--Diffusion maps or spectral embeddings\n\n--Manifold learning in dynamical systems (e.g., Koopman operator theory)\n\nGraph metrics like small-worldness, degree heterogeneity, clustering coefficient, and community structure are NOT manifolds themselves, but they characterize the topology of networks that may be embedded in or arise from latent manifolds.\n\n--Community structure can hint at stratification or clustering on a manifold.\n--Small-worldness suggests short geodesic distances on a latent space.\n--Degree heterogeneity may reflect curvature or singularities in the manifold.\n\n Manifolds in complex systems can be:\n\n--Non-Euclidean: Curved, with nontrivial Riemannian metrics.\n\n--Stratified: Composed of multiple manifolds of different dimensions glued together (e.g., hybrid systems with discrete modes).\n--Singular: Containing points where the manifold structure breaks down (e.g., bifurcations, phase transitions).\n\nMulti-scale: Different dynamics dominate at different scales, requiring nested or hierarchical manifolds.\n\nSo while these metrics are topological descriptors, they can be indirect indicators of underlying manifold geometry.\n\nFor example, a system that can operate in multiple modes may have different structural properties important per mode. This corresponds to a system (in your sense) having different small-world metrics representing different modes. Typically, people use persistent homology to show structural consistency across dynamics---what you compute is different from this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pg98H9Hp3X", "reviewer": "Reviewer_MAH5", "summary": "The paper proposes Latent Geometry-Driven Network Automata (LGD-NA) for network dismantling—sequentially removing nodes to fragment a graph. The key idea is to estimate latent geometric distances on the graph using local, training-free automata rules, convert these to edge dissimilarities, sum per-node to obtain a geometric strength score, and perform dynamic dismantling (recompute scores after each removal). The study evaluates on an ATLAS of 1,475 real-world networks across 32 domains, by AUC of the LCC curve until 10% LCC, and reports top mean-field ranks for the latent-geometry family vs. centrality, message-passing and ML baselines. It also provides a GPU implementation and a robustness-engineering experiment.", "questions": "1. NBC vs LGD-NA performance kind of unclear. Please provide a table with absolute AUC and mean-field rank side-by-side for NBC, RA2, CND under identical dynamic/reinsertion settings, and list fields where one strictly dominates.\n2. Please show results for at least one directed (e.g., trade) and one weighted (e.g., power grid loads) domain, in order to make the paper more convincing.\n3. I am kind of interested in the sensitivity analysis of the proposed method. For 3–4 strong methods, please plot AUC with no reinsertion vs 3 reinsertion policies and report ΔAUC. So that we can confirm rankings are stable or not.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Latent-geometry-driven dismantling, realized via local automata rules (RA2; CND ablation) that use only first-hop structure, is a clean and useful angle.\n2. The paper is clearly written. Pipeline, metrics (AUC to 10% LCC), and reinsertion constraints are explicit.\n3. The proposed work is evaluated on large-scale set, including 1,475 networks across 32 domains.", "weaknesses": "1. Paper alternates between “LGD-NA outperforms all” and “NBC achieves better dismantling but is slower.”\n2. Results are for undirected, unweighted graphs; many domains are directed or weighted (transport flows, trade). Please consider adding experiments (or a clearly stated limitation) for those cases. \n3. Missing tuning/compute budgets and accelerated-NBC baselines.\n4. Reinsertion and robustness-engineering analyses need stronger controls.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)