Goal-directed graph construction using reinforcement learning
arXiv:2001.11279 · doi:10.1098/rspa.2021.0168
Abstract
Graphs can be used to represent and reason about systems and a variety of metrics have been devised to quantify their global characteristics. However, little is currently known about how to construct a graph or improve an existing one given a target objective. In this work, we formulate the construction of a graph as a decision-making process in which a central agent creates topologies by trial and error and receives rewards proportional to the value of the target objective. By means of this conceptual framework, we propose an algorithm based on reinforcement learning and graph neural networks to learn graph construction and improvement strategies. Our core case study focuses on robustness to failures and attacks, a property relevant for the infrastructure and communication networks that power modern society. Experiments on synthetic and real-world graphs show that this approach can outperform existing methods while being cheaper to evaluate. It also allows generalization to out-of-sample graphs, as well as to larger out-of-distribution graphs in some cases. The approach is applicable to the optimization of other global structural properties of graphs.
References in corpus (32)
- Emergence of scaling in random networks
- The structure and function of complex networks
- Continuous control with deep reinforcement learning
- Error and attack tolerance of complex networks
- Efficient Behavior of Small-World Networks
- Assortative mixing in networks
- Neural Architecture Search with Reinforcement Learning
- Neural Message Passing for Quantum Chemistry
- Geometric deep learning: going beyond Euclidean data
- Resilience of the Internet to random breakdowns
- Attack vulnerability of complex networks
- Breakdown of the Internet under intentional attack
- Learning Combinatorial Optimization Algorithms over Graphs
- Mitigation of Malicious Attacks on Networks
- Junction Tree Variational Autoencoder for Molecular Graph Generation
- Communicability in complex networks
- GNNExplainer: Generating Explanations for Graph Neural Networks
- Discriminative Embeddings of Latent Variable Models for Structured Data
- GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
- A Survey of Multi-Objective Sequential Decision-Making
- Learning Deep Generative Models of Graphs
- Operational resilience: concepts, design and analysis
- Robustness of the European power grids under intentional attack
- Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation
- Robust network community detection using balanced propagation
- Optimization of Network Robustness to Waves of Targeted and Random Attack
- Efficient Graph Generation with Graph Recurrent Attention Networks
- Adversarial Attack on Graph Structured Data
- Two-Peak and Three-Peak Optimal Complex Networks
- Programmatically Interpretable Reinforcement Learning
- Provably Powerful Graph Networks
- GraphOpt: Learning Optimization Models of Graph Formation