Edge Dismantling with Geometric Reinforcement Learning

The robustness of networks plays a crucial role in various applications. Network dismantling, the process of strategically removing nodes or edges to maximize damage, is a known NP-hard problem. While heuristics for node removal exist, edge network dismantling, especially in real-world scenarios like power grids or transportation networks, remains underexplored. This paper introduces eGDM-RL, a novel framework for edge dismantling based on Geometric Deep Learning and Reinforcement Learning. Unlike previous approaches, this method demonstrates superior performance in terms of the Area Under the dismantling Curve (AUC) with low computational complexity. The proposed model, utilizing a Graph Attention Network (GAT) and a Deep Q-value Network (DQN), outperforms traditional methods such as those based on edge betweenness. Experimental results on real-world networks validate the effectiveness of the proposed eGDM-RL framework, offering insights into critical edge removal for practical applications.