An unsupervised-learning-based method for cost-constrained complex network dismantling

Finding and removing an optimal set of nodes at minimal cost to weaken or dismantle a network is a highly relevant problem in network science, which has attracted extensive attention in recent years. This problem is known as the cost-constrained Network Dismantling (ND) problem, an NP-hard discrete combinatorial optimization problem. To solve this problem, this paper proposes an Unsupervised-Learning-based Network Dismantling method (called ULND). Specifically, our method employs graph attention networks to generate higher-level features by learning and aggregating information from nodes and their neighbors. Then, our method introduces the skip connections technique to alleviate the vanishing gradients problem and enable effective feature reuse and multi-level information fusion. Notably, our method considers cascading effects and node weights to design the objective function of an unsupervised learning method for training our model, guiding it to effectively learn dismantling strategies. Our model is trained offline on small-scale synthetic networks, and the pre-trained model can effectively perform online inference on large-scale real-world networks. Besides, we introduce a cost-aware reverse greedy fine-tuning strategy to enhance the performance of our model. This paper conducts extensive experiments on synthetic and real-world networks, demonstrating the superior performance of the proposed method compared to state-of-the-art baselines. Our method can serve as a valuable tool to identify critical nodes in complex networks for proactive protection.