Source-linked AI summary
Machine learning dismantling and early-warning signals of disintegration in complex systems
Marco Grassia, Manlio De Domenico, Giuseppe Mangioni
TL;DR
Network dismantling is NP-hard, and no general theory is available to guide the task. The paper introduces GDM, trained on small systems that can be dismantled optimally, and reports that it disintegrates real systems more efficiently and faster than state-of-the-art approaches, with O(N + E) complexity.
Problem
Network dismantling is NP-hard, and a general theory is missing while applications rely on approximated theories or heuristics.
Source: Introduction · p. 2Method
GDM is a machine-learning framework trained to identify critical points in relatively small systems that can be dismantled optimally.
Source: Introduction · p. 3Results
GDM disintegrates real systems more efficiently and faster than state-of-the-art approaches, with complexity O(N + E).
Source: Discussion · p. 10Takeaways & Limitations
The framework offers an approach for disintegrating real systems more efficiently than state-of-the-art methods.
Source: Discussion · p. 10The ultimate theoretical framework for network dismantling is still missing.
Source: Discussion · p. 9
Abstract
from arXiv · showhide
From physics to engineering, biology and social science, natural and artificial systems are characterized by interconnected topologies whose features - e.g., heterogeneous connectivity, mesoscale organization, hierarchy - affect their robustness to external perturbations, such as targeted attacks to their units. Identifying the minimal set of units to attack to disintegrate a complex network, i.e. network dismantling, is a computationally challenging (NP-hard) problem which is usually attacked with heuristics. Here, we show that a machine trained to dismantle relatively small systems is able to identify higher-order topological patterns, allowing to disintegrate large-scale social, infrastructural and technological networks more efficiently than human-based heuristics. Remarkably, the machine assesses the probability that next attacks will disintegrate the system, providing a quantitative method to quantify systemic risk and detect early-warning signals of system's collapse. This demonstrates that machine-assisted analysis can be effectively used for policy and decision making to better quantify the fragility of complex systems and their response to shocks.
Introduction
Network structure affects system functioning, but the topological factors behind vulnerability remain unclear. The paper introduces GDM, a machine-learning framework trained on small, optimally dismantled systems that generalizes to unseen nodes and much larger networks.
Introduction
- Network dismantling seeks small target sets that quickly fragment a system, but is NP-hard; no general theory exists and applications rely on approximations or heuristics.The minimum set of units to target is the dismantling objective.Source: Introduction · p. 2
- The paper presents GDM as a computationally efficient, scalable machine-learning framework for dismantling networks and examining their latent topological features.The framework is based on machine learning and is introduced to address the dismantling challenge.Source: Introduction · p. 3
- Graph convolutional-style layers combine each node’s features with those of its neighborhood through learned functions to produce high-level node features.The paper uses these layers to operate on graph-structured data.Source: Introduction · p. 3
- Training on critical points from relatively small, optimally dismantled systems, GDM generalizes to previously unseen nodes and much larger networks.The authors present this as an inductive capability of the trained machine.Source: Introduction · p. 3
Results
The framework outperforms established dismantling methods on average and estimates when future attacks threaten collapse, with performance on real networks indicating that it exploits topological correlations. In real-world infrastructure networks, Ω provides an earlier warning of collapse than LCC size, while its derivative tracks the importance of attacked nodes over time.
Model architecture
- The model uses stacked Graph Attention Network layers and a regressor to assign each node a probability of belonging to a near-optimal dismantling set, then removes nodes in descending probability order.It is trained on small synthetic networks that can be dismantled optimally and applied to larger networks.Source: Model architecture · pp. 3, 5
Dismantling real-world systems
- GDM outperforms the compared methods on average; Generalized Network Dismantling’s cumulative AUC is ∼12% higher, while GDM beats Min-Sum despite being static as other methods recompute importance during attacks.Lower AUC indicates more efficient dismantling; the comparison is notable because GDM makes predictions at the beginning of the attack.Source: Dismantling real-world systems · p. 6
- Without reinsertion, GDM performs comparably to GND with reinsertion and outperforms the other algorithms, identifying more critical network nodes.The reinsertion phase greedily restores nodes whose removal is unnecessary to reach the target.Source: Dismantling real-world systems · p. 6
- GDM can enhance existing heuristics based on node descriptors by using the same measure as its only node feature.Source: Dismantling real-world systems · p. 7
- Dismantling performance drops on configuration models that preserve observed connectivity distributions but destroy topological correlations, indicating that GDM learns and exploits those correlations.Source: Dismantling real-world systems · p. 7
Early-warning signals of systemic collapse
- The Early Warning score sums predicted attack probabilities for removed nodes to estimate the impact of future attacks and flag potential system disruption.The score is defined on a 0-to-1 scale.Source: Early-warning signals of systemic… · pp. 7–8
- In the toy example, after 16 bridge-node removals, the LCC still includes more than 80% of nodes; the Ω value gets closer to 1 very fast to capture imminent disruption.Source: Early-warning signals of systemic… · pp. 8–9
- Ω does not grow during slow degradation, distinguishing it from the faster growth associated with successful attacks on critical nodes.The passage states that Ω captures this difference but does not provide further detail about slow degradation.Source: Early-warning signals of systemic… · p. 9
- On real-world infrastructure networks, the method predicts system collapse under various attack strategies.The passages refer to Fig. 5 for details but provide no specific prediction results.Source: Early-warning signals of systemic… · p. 9
- Ω grows faster when critical nodes are successfully attacked and reaches warning levels before disruption, unlike LCC size, which declines slowly without a clear alarm until heavy damage and collapse.First Response Time is defined as the time between collapse and an early-warning signal at Ω = 0.5.Source: Early-warning signals of systemic… · p. 9
- The first derivative Ω′ tracks the importance of attacked nodes and measures attack intensity over time.Source: Early-warning signals of systemic… · p. 9
Discussion
The discussion presents learned dismantling as a faster, more efficient alternative to state-of-the-art approaches, alongside a damage descriptor intended to warn of collapse under subsequent attacks. It also emphasizes computational scalability, data-driven retuning, and applicability beyond dismantling, while noting that an ultimate theoretical framework is still missing.
Discussion
- An ultimate theoretical framework for network dismantling is still missing.Source: Discussion · p. 9
- The framework learns directly from data and can be improved by retuning model parameters and training again, unlike approaches requiring heuristic or algorithm redesign.Source: Discussion · pp. 9–10
- O(N+E) complexity drops to O(N) for sparse networks, supporting million-node applications with excellent computing-time and accuracy performance.Source: Discussion · p. 10
- The framework is described as adaptable to other NP-hard problems on networks, opening further research directions in complexity science.Source: Discussion · p. 10
- The framework disintegrates real systems more efficiently and faster than state-of-the-art approaches.Source: Discussion · p. 10
- The damage descriptor is more predictive than largest-connected-component size and estimates potential collapse from subsequent damages.Source: Discussion · p. 10
- The damage measure is presented as an early-warning signal for policy responses to systemic emergencies in water, power, communication, and public-transport networks.Source: Discussion · p. 10
Supplementary Materials
The supplementary materials provide model, training, and computational details, extend dismantling and early-warning evaluations across toy and real-world networks, and probe the method’s behavior and scope through comparisons, rewiring tests, and additional datasets.
Deep Learning Model
- The model aggregates an L-hop neighborhood with Graph Attention Network layers and feeds the resulting features to a regressor that estimates each node’s structural importance.Self-attention weights nodes differently, and the aggregation covers the whole neighborhood rather than only its frontier.Source: Deep Learning Model · p. 20
- In supervised training, models use small synthetic networks with 25 nodes each, generated using Barabási–Albert and Erdős–Rényi methods and optimally dismantled by brute force; labels depend on the number of optimal sets containing each node.The target LCC size was approximately 18% in the tests.Source: Deep Learning Model · pp. 20–21
- To limit attack and learning costs, the authors select degree, neighborhood Pearson χ2, k-coreness, and local clustering coefficient as node features.They note that feature choices can be adapted to the target networks or domain.Source: Deep Learning Model · pp. 21–22
Computational complexity
- Under the stated sparse-network assumption, the approach has O(N) computational complexity, determined by the GAT layers and the most expensive feature, k-coreness.The GAT layers scale as O(N + E), and k-coreness also scales as O(N + E).Source: Computational complexity · p. 23
Other Results
- On a toy network of three ego-networks joined by a bridge, GDM removes only the ego-network cores rather than following the bridge-first heuristic.The heuristic strategy would remove the bridge and then the centers of the separated ego-networks, requiring four removals.Source: Other Results · p. 24
- In toy networks, the model matches the three-removal LCC result in one example and detaches a tailed clique’s tail first, outperforming degree- and betweenness-based heuristics.The tail-first strategy differs from degree-based removal, which would select the clique nodes first.Source: Other Results · p. 24, Figure 2 · p. 25
- The GDM-enhanced degree- and betweenness-based heuristics effectively outperform their vanilla versions, with the reported comparison highlighting enhancements to both degree- and betweenness-based heuristics.Source: Other Results · p. 25
- The approach outperforms node-removal baselines that remove nodes in descending degree (71) or betweenness order, with a significant margin even against methods with higher computational complexity.Source: Other Results · p. 26
- Across 12 large networks with up to 1.8M nodes and 2.8M edges, the main-paper results were confirmed, though with smaller margins; the proposed approach remains static while others recompute importance.This entails many removals (e.g., 70K on hyves network) and drastic topology changes.Source: Other Results · p. 26
- The supplementary dismantling curves compare model choices optimized for area under the curve or removal count, including reinsertion results against state-of-the-art algorithms.The two objectives can select overlapping models for some networks.Source: Other Results · p. 27
- On European power-grid and American-road systems, Ω detects damage and reaches warning levels before collapse, including when multiple large components detach.These tests include random failures and degree- or Min-Sum-based attacks on the power grid, and network-dismantling attacks on roads.Source: Other Results · p. 27
Dataset
- The test networks used in the experiments model biological, infrastructure, and social systems, and their sizes span from a few hundred nodes to larger network sizes.All experiments ran on a shared machine with two Intel Xeon E5-2620 CPUs, 128 GB RAM, and a two-core Nvidia Tesla K80 with 12 GB VRAM each.Source: Dataset · p. 27, Test environment · p. 28