A Systematization of the Wagner Framework: Graph Theory Conjectures and Reinforcement Learning

In 2021, Adam Zsolt Wagner proposed an approach to disprove conjectures in graph theory using Reinforcement Learning (RL). Wagner frames a conjecture as f(G) < 0 for every graph G, for a certain invariant f; one can then play a single-player graph-building game, where at each turn the player decides whether to add an edge or not. The game ends when all edges have been considered, resulting in a certain graph \(G_T\), and \(f(G_T)\) is the final score of the game; RL is then used to maximize this score. This brilliant idea is as simple as innovative, and it lends itself to systematic generalization. Several different single-player graph-building games can be employed, along with various RL algorithms. Moreover, RL maximizes the cumulative reward, allowing for step-by-step rewards instead of a single final score, provided the final cumulative reward represents the quantity of interest \(f(G_T)\). In this paper, we discuss these and various other choices that can be significant in Wagner’s framework. As a contribution to this systematization, we present four distinct single-player graph-building games. Each game employs both a step-by-step reward system and a single final score. We also propose a principled approach to select the most suitable neural network architecture for any given conjecture and introduce a new dataset of graphs labeled with their Laplacian spectra. The games have been implemented as environments in the Gymnasium framework, and along with the dataset and a simple interface to play with the environments, are available at https://github.com/CuriosAI/graph_conjectures.