Complex systems, spanning diverse fields like physics, biology, and social sciences, are characterized by interconnected topologies with heterogeneous connectivity, mesoscale organization, and hierarchy. These topological features significantly influence the system's robustness to external perturbations, including targeted attacks. Network dismantling, the process of identifying the minimal set of units to attack for system disintegration, is a computationally challenging (NP-hard) problem. Existing approaches often rely on heuristics, lacking a general theoretical framework. This research aims to address these limitations by developing a machine-learning-based approach that can efficiently dismantle large-scale networks and provide early-warning signals of systemic collapse. The ability to accurately predict and mitigate these risks has significant implications for policy and decision-making across various domains.

The paper reviews existing literature on complex networks, highlighting their structural features and how these affect their vulnerability to attacks. It discusses the challenges posed by the NP-hard nature of network dismantling and the limitations of existing heuristic methods like Generalized Network Dismantling (GND), Explosive Immunization (EI), CoreHD, Min-Sum (MS), and Collective Influence (CI). These methods often rely on node descriptors (degree, clustering coefficient, k-core value) which can be computationally expensive for large networks and might miss subtle higher-order topological patterns. The authors note the recent trend in machine learning of learning on synthetic data and generalizing to real-world instances, and applying machine learning to solve hard combinatorial problems on graphs.

The proposed GDM framework utilizes a geometric deep learning model. This model consists of graph convolutional-style layers (specifically, Graph Attention Networks or GATs) and a regressor (multilayer perceptron). GAT layers aggregate node features from their neighborhood using a learned function, capturing higher-order topological patterns. The model is trained on small synthetic networks (25 nodes) generated using Barabási-Albert, Erdős-Rényi, and static power-law models. The training process involves optimally dismantling these small networks using brute force and assigning labels to nodes based on their presence in optimal dismantling sets. The trained model then generalizes to larger, unseen networks. Node features used include local (node degree and its χ² value over the neighborhood), second-order (local clustering coefficient), and global (k-core value) features. During dismantling, nodes are ranked and removed based on the model's predicted probability of belonging to the optimal dismantling set. The performance is evaluated using the Area Under the Curve (AUC) of the Largest Connected Component (LCC) size changes during the attack, with lower AUC indicating more efficient dismantling. For comparison, GDM is tested against existing state-of-the-art methods, including a node reinsertion phase to further enhance dismantling efficiency.

GDM demonstrates superior performance in dismantling various real-world networks compared to existing methods. It consistently achieves lower AUC values, indicating faster and more efficient disintegration, even surpassing dynamic methods that recompute node importance during the dismantling process. The advantage is maintained even on large networks with millions of nodes. While the Min-Sum algorithm performs slightly better on synthetic networks, GDM shows significant advantages on real-world scenarios. Analysis of the model's learned patterns reveals that it targets nodes bridging multiple clusters, effectively creating new connected components and accelerating disintegration. The model's ability to identify these crucial bridge nodes, even if not directly causing substantial damage, highlights its capability in predicting long-term network disruption strategies. The study introduces an early-warning signal (Ω) which is a more accurate predictor of impending system collapse than LCC size. Ω measures the cumulative probability of nodes causing percolation, offering a quantitative assessment of systemic risk. The analysis shows Ω's effectiveness in predicting the system's collapse in infrastructure networks (European and North American power grids, and London public transport), providing early warning signals well before the LCC size dramatically decreases.

The findings demonstrate the effectiveness of machine learning in addressing the computationally challenging problem of network dismantling. GDM provides a more efficient and accurate approach compared to existing heuristics, particularly for large-scale networks. The use of geometric deep learning allows the model to learn complex topological patterns essential for system disintegration. The introduction of the early-warning signal (Ω) offers a powerful tool for risk assessment and proactive intervention in critical infrastructure. The results have significant implications for various sectors requiring robust system analysis, such as infrastructure management, cybersecurity, and public health. The model's ability to learn from data makes it adaptable and potentially applicable to other NP-hard problems in network science.

This paper introduces GDM, a machine learning framework for efficient network dismantling and early-warning signal generation. GDM outperforms state-of-the-art methods and provides a quantitative measure (Ω) for assessing systemic risk. Future research could focus on exploring different node features, model architectures, and applications to other types of complex systems. Investigating the robustness of GDM under diverse attack strategies and noise levels is also warranted. The framework's adaptability holds promise for diverse applications in complexity science.

While GDM demonstrates superior performance, its reliance on training data from specific network generation models might limit its generalizability to entirely novel network topologies. Further research is needed to assess its robustness in handling noisy data or incomplete network information. The interpretation of the model's learned patterns requires careful consideration, as it reveals correlations and dependencies that might not be fully understood from a theoretical standpoint.