Multi-layer Network Disintegration via Deep Reinforcement Learning

Abstract

Multi-layer networks (MLN) effectively model interactions across layers, and the network disintegration (ND) problem yields significant importance in the analysis of MLN. Unfortunately, previous advances in ND for single-layer networks exhibits inefficiency and lack of scalability when extended to MLN, as MLN involve complex inter-layer dependencies and interactions that are absent in single-layer networks. To bridge this gap, we propose a pioneer framework named Multi-layer Network Disintegration via Deep Reinforcement Learning (MNDRL), by re-formulating the disintegration process into a preprocessing-encoding-decoding pipeline. To be specific, MNDRL consists of two Graph Neural Network (GNN) models to effectively capture intra-layer and inter-layer representations separately. Empowered with DRL, our MNDRL achieves near-optimal results in the ND task with the NP-hard complexity by autonomously learning efficient disintegration strategies. Extensive experiments demonstrate that our MNDRL outperforms the results of baseline disintegration methods by over 30% on real-world datasets and by over 10% on synthetic datasets with varying node counts.