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.
翻译:图表可以用来表达和解释各种系统和各种计量方法,以量化其全球特性,然而,目前对于如何构建图表或改进现有图表给定目标的目标鲜为人知。在这项工作中,我们将图表的构造设计成一个决策过程,中央代理物通过试验和错误产生地形,并获得与目标值相称的回报。我们通过这个概念框架,提出了一种基于强化学习和图形神经网络的算法,以学习图形构建和改进战略。我们的核心案例研究侧重于对失败和攻击的稳健性,这是一个与现代社会的基础设施和通信网络相关的属性。对合成和现实世界图形的实验表明,这种方法在比较便宜的情况下,可以优于现有方法。它还允许一般化的标本图,以及在某些情况下更大的批发外图。这个方法适用于优化图表的其他全球结构特性。