Graph Reinforcement Learning for Combinatorial Optimization: A Survey
  and Unifying Perspective
Victor-Alexandru Darvariu Stephen Hailes Mirco Musolesi
Graphs are a natural representation for systems based on relations between
connected entities. Combinatorial optimization problems, which arise when
considering an objective function related to a process of interest on discrete
structures, are often challenging due to the rapid growth of the solution
space. The trial-and-error paradigm of Reinforcement Learning has recently
emerged as a promising alternative to traditional methods, such as exact
algorithms and (meta)heuristics, for discovering better decision-making
strategies 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 to
synthesize this work in a unifying perspective that we term Graph Reinforcement
Learning, interpreting it as a constructive decision-making method for graph
problems. After covering the relevant technical background, we review works
along the dividing line of whether the goal is to optimize graph structure
given a process of interest, or to optimize the outcome of the process itself
under fixed graph structure. Finally, we discuss the common challenges facing
the field and open research questions. In contrast with other surveys, the
present work focuses on non-canonical graph problems for which performant
algorithms are typically not known and Reinforcement Learning is able to
provide efficient and effective solutions.