Network Attack and Defense: Deep Learning in the Presence of Limited Information

Networked systems are vulnerable to attacks that fragment them via removal of a handful of key nodes. Though optimal identification of these weak points is NP-hard, deep reinforcement learning can learn near-optimal solutions. This raises the question: does there exist defense strategies to mitigate such an attack? We address network defense by casting attack/defense as a two-player game where an attacker fragments the network with minimum node removals, while a defender obfuscates structure by strategically concealing links before the attacker makes its decisions. While increased concealment challenges the attacker, outperforming heuristic strategies like random concealment, the effect is sublinear—only when nearly all structure is hidden does the attacker perform no better than random. This reveals that network vulnerabilities remain inferable with substantial missing information, limiting defensive effectiveness against sophisticated adversaries. More broadly, this framework enables solving NP-hard problems (vertex cover, feedback vertex set, maximum cut) under partial observability—a ubiquitous challenge in real systems such as food webs with undiscovered species and gene regulatory networks with unknown interactions. This provides a methodology for robust decision-making on incompletely characterized networks, offering new perspectives on both network defense and optimization under uncertainty.