# Goal-directed graph construction using reinforcement learning

arXiv: https://arxiv.org/abs/2001.11279 · HTML: https://mlsanity.com/paper/2001.11279/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2020.

## Built on by (most cited first, 14 of 14)

- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [Reinforcement Learning for Generative AI: A Survey](https://mlsanity.com/paper/2308.14328/) (2023)
- [Planning Spatial Networks with Monte Carlo Tree Search](https://mlsanity.com/paper/2106.06768/) (2021)
- [Dynamic Network Reconfiguration for Entropy Maximization using Deep Reinforcement Learning](https://mlsanity.com/paper/2205.13578/) (2022)
- [Intrinsically motivated graph exploration using network theories of human curiosity](https://mlsanity.com/paper/2307.04962/) (2023)
- [Tree Search in DAG Space with Model-based Reinforcement Learning for Causal Discovery](https://mlsanity.com/paper/2310.13576/) (2023)
- [SCGG: A Deep Structure-Conditioned Graph Generative Model](https://mlsanity.com/paper/2209.09681/) (2022)
- [Discrete Compositional Generation via General Soft Operators and Robust Reinforcement Learning](https://mlsanity.com/paper/2506.17007/) (2025)
- [Modelling the Recommender Alignment Problem](https://mlsanity.com/paper/2208.12299/) (2022)
- [Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning](https://mlsanity.com/paper/2509.18930/) (2025)
- [Reinforcement Learning for Graph Generation under a Hard Assortativity Constraint](https://mlsanity.com/paper/2605.23285/) (2026)
- [Beyond Static Graph World Models: Learning Stochastic Latent Dynamics over Evolving Topologies](https://mlsanity.com/paper/2609.28670/) (2026)
- [Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning](https://mlsanity.com/paper/2610.06244/) (2026)

## Abstract (arXiv)

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.