Science China Information Sciences Компьютерные науки (общие)
Discovering a compact meta-RL rule for critical node identification in complex networks
Аннотация
Identifying critical nodes whose removal fragments a complex network underpins applications across infrastructure resilience, epidemic blocking, and biological network analysis. Existing reinforcement learning (RL)-based graph learning methods train graph neural network (GNN) agents with hand-designed reinforcement-learning rules, so that every new task formulation, whether single-layer network dismantling, multilayer network dismantling, maximum independent set, minimum vertex cover, or maximum clique, requires re-engineering a reward or an architecture from scratch. We instead ask whether the RL update rule itself can be discovered once on the graph domain and re-used across this entire class of problems, by adapting a meta-RL paradigm in which a meta-network emits loss-shaping targets that train agents in place of a hand-designed RL loss. To our knowledge, this is the first systematic graph-domain instantiation of meta-learned RL update rules, realized through a graph-aligned meta-network. The proposed meta-network is compact and is meta-trained on five graph-combinatorial tasks on a single GPU in about 13 h, treating critical-node detection as a single underlying capability rather than as five disjoint tasks. GNN agents trained by this rule outperform all baselines on the established 53-network single-layer network dismantling benchmark; transfer zero-shot to 33 real-world multilayer networks, approaching the specialized state-of-the-art (SOTA) on interdependent networks and surpassing all baselines on multiplex networks; and approach the exact optimum on maximum independent set (MIS), minimum vertex cover (MVC), and maximum clique (MC) without per-task tuning. Because each task-specialized baseline leads only on its home protocol and degrades on the others, agents trained by our rule are the only ones that remain non-dominated across the single-layer, interdependent, and multiplex protocols simultaneously. Controlled comparisons under an identical training protocol attribute these gains to the discovered, graph-domain-specific update signal, rather than to model capacity or any classical RL update. For graph-combinatorial problems with short episodes and structure-driven action spaces, compact and domain-aligned meta-RL rules dominate large, domain-agnostic ones.