GRLND: A Graph Reinforcement Learning Framework for Network Dismantling

Network Dismantling (ND) seeks to identify the smallest subset of nodes whose removal fragments a network into disconnected components. Traditional methods rely on fixed centrality heuristics or supervised models trained on synthetic data, often failing to generalize across diverse topologies. We introduce GRLND, a Graph Reinforcement Learning framework that enables fully unsupervised, structure-aware dismantling through end-to-end optimization. GRLND formulates ND as a single-step Markov Decision Process (MDP), where the action is a binary mask indicating the nodes to be removed-allowing the agent to generate a complete dismantling strategy in a single forward pass while accounting for the joint effect of multiple node removals. The framework combines a Graph Convolutional Network (GCN) for topological encoding with a stochastic policy trained via the REINFORCE algorithm. Additionally, we design a task-specific reward that balances connectivity disruption and removal sparsity, guiding the policy toward compact yet high-impact dismantling solutions. Experiments on both synthetic and real-world networks show that GRLND consistently outperforms classical heuristics and recent learning-based methods, achieving strong generalization without requiring labels or pretraining.

• Publication year

  2025

• Venue

  International Conference on Information and Knowledge Management

• Publication date

  2025-11-10

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/3746252.3761371
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Novelty-aware Graph Traversal and Expansion for Hierarchical Reinforcement Learning

  2024cited by this paper
• Assessing road network resilience in disaster areas from a complex network perspective: A real-life case study from China

  2023cited by this paper
• Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback

  2022cited by this paper
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks

  2022cited by this paper
• Neural extraction of multiscale essential structure for network dismantling

  2022cited by this paper
• Minimizing the spread of misinformation in online social networks: A survey

  2021cited by this paper
• Machine learning dismantling and early-warning signals of disintegration in complex systems

  2021influential reference
• Survey on reinforcement learning for language processing

  2021cited by this paper
• The physics of higher-order interactions in complex systems

  2021cited by this paper
• Deep Reinforcement Learning for General Game Playing

  2020cited by this paper
• Finding key players in complex networks through deep reinforcement learning

  2020influential reference
• A Comprehensive Survey on Graph Neural Networks

  2019cited by this paper
• Reinforcement Learning Based Routing in Networks: Review and Classification of Approaches

  2019cited by this paper
• Generalized network dismantling

  2018cited by this paper
• Graph Neural Networks: A Review of Methods and Applications

  2018cited by this paper
• Deep Reinforcement Learning: A Brief Survey

  2017cited by this paper
• Learning Combinatorial Optimization Algorithms over Graphs

  2017cited by this paper
• Graph Attention Networks

  2017cited by this paper
• Mastering the game of Go with deep neural networks and tree search

  2016cited by this paper
• Network dismantling

  2016cited by this paper
• Semi-Supervised Classification with Graph Convolutional Networks

  2016cited by this paper
• Identifying optimal targets of network attack by belief propagation

  2016cited by this paper
• Network science

  2016cited by this paper
• Influence maximization in complex networks through optimal percolation

  2015cited by this paper
• The Network Data Repository with Interactive Graph Analytics and Visualization

  2015cited by this paper
• Epidemic processes in complex networks

  2014cited by this paper
• Attack Robustness and Centrality of Complex Networks

  2013cited by this paper
• The Power Grid as a Complex Network: a Survey

  2011cited by this paper
• Collaboration in computer science: A network science approach

  2010cited by this paper
• Benchmark graphs for testing community detection algorithms.

  2008cited by this paper
• Networks

  2007cited by this paper
• A human phenome-interactome network of protein complexes implicated in genetic disorders

  2007cited by this paper
• Complex networks: Structure and dynamics

  2006cited by this paper
• A model of Internet topology using k-shell decomposition

  2006cited by this paper
• Identifying useful subgoals in reinforcement learning by local graph partitioning

  2005cited by this paper
• Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning

  2004cited by this paper
• Attack vulnerability of complex networks.

  2002cited by this paper
• Community structure in social and biological networks

  2001cited by this paper
• Exploring complex networks

  2001cited by this paper
• A faster algorithm for betweenness centrality

  2001cited by this paper
• The modularity of biological regulatory networks.

  1999cited by this paper
• Emergence of Scaling in Random Networks

  1999cited by this paper
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• Centrality in social networks conceptual clarification

  1978cited by this paper
• Factoring and weighting approaches to status scores and clique identification

  1972cited by this paper

• No citing papers are available for this paper.