Abstract
Graphs are a natural representation for systems based on relations betweenconnected entities. Combinatorial optimization problems, which arise whenconsidering an objective function related to a process of interest on discretestructures, are often challenging due to the rapid growth of the solutionspace. The trial-and-error paradigm of Reinforcement Learning has recentlyemerged as a promising alternative to traditional methods, such as exactalgorithms and (meta)heuristics, for discovering better decision-makingstrategies in a variety of disciplines including chemistry, computer science,and statistics. Despite the fact that they arose in markedly different fields,these techniques share significant commonalities. Therefore, we set out tosynthesize this work in a unifying perspective that we term Graph ReinforcementLearning, interpreting it as a constructive decision-making method for graphproblems. After covering the relevant technical background, we review worksalong the dividing line of whether the goal is to optimize graph structuregiven a process of interest, or to optimize the outcome of the process itselfunder fixed graph structure. Finally, we discuss the common challenges facingthe field and open research questions. In contrast with other surveys, thepresent work focuses on non-canonical graph problems for which performantalgorithms are typically not known and Reinforcement Learning is able toprovide efficient and effective solutions.