DDIN: Reinforcement Learning with Asymmetric GNNs for Dismantling Directed Interdependent Networks (Student Abstract)

Abstract

Dismantling interdependent directed networks to obtain the largest mutually strongly connected component (MSCC) is an NP-hard problem. To address this, we propose a novel method, Disassembling Directed Interdependent Networks (DDIN), by synergizing Reinforcement Learning (RL) and Graph Neural Networks (GNN). We introduce asymmetric GNNs to capture the asymmetry of in/out-degree and multi-relational attention to model directed inter-layer dependencies, integrated with prioritized RL for efficient node selection in large action spaces. Our contributions include (i) a directed GraphSAGE encoder separating in/out aggregations for asymmetry, (ii) multi-relational attention fusing layer semantics, and (iii) sum-tree prioritized n-step Deep Q-Network (DQN) for efficient policy search. DDIN is evaluated on 5 directed multiplexes from biological, social, and economic domains, achieving 16-23% lower AUDC compared to known baseline heuristics.