  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.
