Machine learning dismantling and early-warning signals of disintegration in complex systems

Many empirical systems can be represented as complex networks with heterogeneous connectivity, mesoscale and higher-order structure, hierarchy, efficiency in information exchange, and multiplexity. Such structural features shape collective dynamics (e.g., synchronization, spreading, cascades, misinformation and hate propagation, emergence of conventions) and influence robustness to shocks. Although hubs increase vulnerability to targeted perturbations, a comprehensive understanding of which topological factors and their interplay drive systemic fragility is lacking. Network dismantling—finding a minimal set of nodes whose removal fragments the largest connected component (LCC)—is NP-hard. Random percolation theory explains macroscopic transitions under random failures, but a general theory for optimal dismantling is missing; practice relies on heuristics or approximate methods. This study asks whether a machine learning model trained on small, optimally dismantled synthetic networks can learn higher-order topological patterns to produce efficient dismantling strategies on large, real networks, and whether such a model can provide early-warning signals of imminent systemic collapse.

Prior work has introduced influential heuristics and optimization-based approaches for dismantling and related percolation problems: Collective Influence, Min-Sum, CoreHD, Explosive Immunization, and Generalized Network Dismantling. Percolation theory has illuminated robustness in single and interdependent networks under random failures. Recent machine learning trends include (i) learning from synthetic data and generalizing to real-world instances, and (ii) learning heuristics for hard combinatorial problems on graphs using graph neural networks. Attention mechanisms (e.g., Graph Attention Networks) have advanced learning on non-Euclidean structures. However, a principled, general theory of optimal dismantling is still absent, motivating data-driven, scalable methods that can infer nontrivial topological patterns and long-term effects of attacks.

The authors propose GDM (Graph Dismantling with Machine learning), a geometric deep learning framework to predict dismantling strategies. Architecture: stacked graph convolutional-style layers based on Graph Attention Networks (GAT), with residual linear layers of matching dimensions, Exponential Linear Unit activations, dropout 0.3, and multi-head attention. These layers aggregate each node’s features with those of its neighbors via learned attention, enabling K-hop feature propagation without neighbor sampling. A multilayer perceptron regressor with sigmoid output maps the final node embeddings to p_i ∈ [0,1], the predicted probability that node i belongs to a (sub-)optimal dismantling set. Dismantling procedure: compute node features (local degree, degree χ² over neighborhood, local clustering coefficient, and global k-core index), infer p_i for all nodes once (static prediction), rank nodes by p_i, and iteratively remove them if they belong to the current LCC until a dismantling target is reached. Performance metric: area under the LCC vs. removals curve (AUC), integrated with Simpson’s rule; lower AUC indicates faster disintegration. Comparators: state-of-the-art methods (GND, EI, CoreHD, MS, CI). A greedy reinsertion phase can optionally reinsert nodes removed from small components that were not necessary to achieve the target. Training data: small synthetic networks (25 nodes) generated by Barabási–Albert, Erdős–Rényi, and Static Power-law models (igraph and NetworkX). Each network is optimally dismantled via brute-force to identify all minimum-size node sets that reduce the LCC to ~18% of N. Node labels equal the fraction of optimal sets containing the node (e.g., 1, 0.5, or 0), encoding node criticality across optimal solutions. Supervised training is performed for 50 epochs with learning rate 1e-5; a grid search explores 1–4 GAT layers (5–50 channels, 1–30 heads) and 1–4 MLP layers (20–100 neurons). Understanding the model: GNNExplainer extracts explanation subgraphs to reveal patterns learned (e.g., bridges between large clusters). Articulation Point (AP) analysis tracks the number of APs and APs within the removal set R across removals, revealing that the model creates and targets effective APs connecting large components. Feature attribution analyses show the relative importance of features varies by network and by removal stage. Early-warning signal: define Ω to estimate imminent systemic collapse. Simulate GDM dismantling to identify the critical removal set S that causes percolation; compute Ω_s = Σ_{u∈S} p_u and normalize by Ω_m (the model-dependent tolerance/maximum): Ω = min(Ω_s/Ω_m, 1). Ω rises quickly when critical nodes are attacked, anticipating abrupt collapse better than LCC. Complexity: dismantling with GDM is O(N+E), dropping to O(N) for sparse networks, enabling application to million-node systems. Code and data availability: open-source GDM code on GitHub and Zenodo; synthetic data on Zenodo.

- On real-world networks of societal and strategic relevance, GDM achieves lower cumulative AUC than state-of-the-art methods, indicating faster disintegration. For example, compared to GND, cumulative AUC is ~12% higher for GND (i.e., GDM lower is better), and GDM significantly outperforms MS, CoreHD, EI, and CI despite being static (no recomputation during attacks). - With a greedy reinsertion phase, GDM still matches or surpasses dynamic techniques; even without reinsertion, GDM performs comparably to GND + reinsertion and outperforms others. - On 12 large networks (up to ~1.8M nodes and ~2.8M edges), GDM retains its advantage, with average gains of ~5.6% and ~7.6% in cumulative AUC against GND with and without reinsertion, respectively. - On synthetic networks (ER, CM power-law, SBM), Min-Sum performs best, achieving AUC ~6% (vs. GDM) and ~3% (vs. GDM+R) lower. The authors attribute GDM’s relative underperformance here to training distribution effects and the static nature of predictions; notably, GND performs worst on these synthetic graphs. - Model explanations indicate GDM prioritizes bridge nodes spanning multiple clusters and follows a long-term strategy that both targets and creates effective Articulation Points between large components, accelerating fragmentation. - Feature importance is context-dependent; e.g., degree dominates early removals in the Brazilian corruption network, while clustering coefficient can be most influential in early stages for other graphs, with importance rebalancing later. - Dismantling performance drops on configuration-model surrogates (which destroy correlations while preserving degree), evidencing that GDM learns and exploits higher-order topological correlations. - Early-warning descriptor Ω anticipates collapse earlier than LCC. In toy and infrastructure cases (European and North-American power grids, London transport), Ω reaches warning levels (e.g., Ω = 0.5) well before LCC shows abrupt change; Ω′ reflects attack intensity. - Computational efficiency is high: O(N+E), suitable for million-scale networks.

The study demonstrates that a machine learning model trained on small, optimally dismantled synthetic networks can learn higher-order topological patterns that generalize to large, real systems. GDM’s static predictions—computed once—still outperform dynamic, recomputing heuristics across diverse real networks, indicating that learned representations capture long-term dismantling strategies, particularly identifying and inducing critical bridges and Articulation Points between large clusters. The framework’s early-warning signal Ω provides actionable foresight, detecting imminent systemic collapse before it manifests in standard robustness metrics like LCC, thus enabling timely interventions in critical infrastructures. Beyond performance, interpretability analyses (GNNExplainer, AP dynamics, feature attributions) elucidate how geometric deep learning integrates local and mesoscopic features across K-hop neighborhoods to identify vulnerability patterns. The approach highlights the strength of data-driven, parameter-retunable models over hand-crafted heuristics and suggests that learned strategies can inform new algorithmic insights for network resilience and risk assessment.

The authors introduce GDM, a geometric deep learning framework that dismantles complex networks more efficiently than leading heuristics and approximate methods on real-world systems, while scaling to million-node graphs with near-linear complexity. Trained on small synthetic instances via optimal dismantling labels, GDM generalizes to large, unseen networks, learns to target and create critical bridges and Articulation Points, and delivers an early-warning metric Ω that anticipates abrupt collapses better than LCC. The framework is general, data-driven, and easily improved by retraining or enriching features, with code and data openly available. Future directions include tailoring training distributions and node features to specific domains, integrating dynamic recomputation if needed, extending to multiplex/interdependent networks, and applying the methodology to other NP-hard network problems, potentially combining with recent ML approaches for predicting extreme events.

- Training-label design and performance depend on the training distribution (small BA/ER/power-law graphs with a fixed dismantling target ~18%); domain-specific retraining may be needed for optimal results. - The approach is static during attack execution; no recomputation may be suboptimal in certain synthetic graph families where dynamic updates (e.g., Min-Sum) perform better. - Node features were chosen for computational efficiency; richer features could improve performance but at higher cost. - Decreased performance on configuration-model surrogates indicates reliance on topological correlations present in real networks; in settings lacking such correlations, gains may diminish. - Early-warning Ω primarily reflects the accumulation of predicted criticalities; slow, diffuse attacks on peripheral nodes may produce limited Ω growth, though such attacks are less abrupt. - The paper does not provide an ablation of architecture components across all datasets nor exhaustive sensitivity to hyperparameters; superscript affiliations may be incomplete in the excerpted text.