Goal-directed graph construction using reinforcement learning

Abstraction: RL agent with GNNs constructs graphs optimizing target structural properties

Key points:

• Formulates graph construction and improvement as a sequential decision-making (MDP) problem where a central agent adds edges and receives rewards proportional to a target objective
• Proposes algorithm combining reinforcement learning and graph neural networks to learn reusable construction and improvement policies
• Core case study targets network robustness to failures and attacks, a critical property for infrastructure and communication networks
• Outperforms existing heuristic methods on synthetic and real-world graphs with lower evaluation cost
• Generalizes to out-of-sample graphs and, in some cases, to larger out-of-distribution graphs
• Framework is general: applicable to any differentiable global structural graph property; submitted Jan 2020, final version Oct 2021

Connections: Reinforcement Learning · Graph Neural Networks · Graph Optimization

Source: https://arxiv.org/abs/2001.11279