A deep learning dismantling approach for understanding the structural vulnerability of complex networks

Understanding the structural vulnerability of real-world complex networks is a crucial issue. This issue can be addressed by solving the so-called network dismantling problem, which aims to identify the smallest set of nodes for the fastest dismantling of a network. The network dismantling problem is a computationally challenging task due to its NP-hard nature. The powerful learning capabilities of machine learning methods provide a new perspective for solving this problem. Most existing deep learning methods are based on supervised learning, which rely on pre-labeled training data. These existing methods have achieved promising results in completely dismantling a network. However, they may not perform very well in identifying a very small number of nodes whose removal would significantly degrade—though far from fully dismantle—the network performance. This issue is particularly relevant to many real-world networks like transportation and infrastructure networks. This paper proposes a novel unsupervised learning model called GASC (Graph Attention network integrated with Shortcut Connections mechanism), to address this issue regarding the network dismantling problem. The GASC model employs the graph attention network to learn the underlying features of a network's topological structure and integrates the shortcut connections mechanism to overcome the vanishing gradients problem. Besides, we incorporate a network tailoring method to further improve the performance of our model. We performed comprehensive experiments on both synthetic networks and various real-world networks. The results validate that the proposed approach outperforms existing state-of-the-art methods and demonstrates significant robustness.