Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective

• URL: http://arxiv.org/abs/2404.06492v2
• Date: Tue, 20 Aug 2024 11:21:32 GMT
• Title: Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
• Authors: Victor-Alexandru Darvariu, Stephen Hailes, Mirco Musolesi,
• Abstract summary: We use the trial-and-error paradigm of Reinforcement Learning for discovering better decision-making strategies. This work focuses on non-canonical graph problems for which performant algorithms are typically not known.
• Score: 6.199818486385127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
  We propose an adaptive Graph Attention Sampling with the Edges Fusion framework to solve vehicle routing problems. Our proposed model outperforms the existing methods by 2.08%-6.23% and shows stronger generalization ability.
  arXiv  Detail & Related papers  (2024-05-21T03:33:07Z)
• A Novel Differentiable Loss Function for Unsupervised Graph Neural Networks in Graph Partitioning [5.22145960878624]
  The graph partitioning problem is recognized as an NP-hard prob-lem. We introduce a novel pipeline employing an unsupervised graph neural network to solve the graph partitioning problem. We rigor-ously evaluate our methodology against contemporary state-of-the-art tech-niques, focusing on metrics: cuts and balance, and our findings reveal that our is competitive with these leading methods.
  arXiv  Detail & Related papers  (2023-12-11T23:03:17Z)
• GIF: A General Graph Unlearning Strategy via Influence Function [63.52038638220563]
  Graph Influence Function (GIF) is a model-agnostic unlearning method that can efficiently and accurately estimate parameter changes in response to a $epsilon$-mass perturbation in deleted data. We conduct extensive experiments on four representative GNN models and three benchmark datasets to justify GIF's superiority in terms of unlearning efficacy, model utility, and unlearning efficiency.
  arXiv  Detail & Related papers  (2023-04-06T03:02:54Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  We propose a radically different approach in that no data is required for training the neural networks that produce the solution. In particular, we reduce the optimization problem to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest.
  arXiv  Detail & Related papers  (2022-03-15T19:21:31Z)
• Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement Learning [1.3534683694551497]
  In recent years, using deep learning techniques to find solutions for NP-hard graph problems has gained much interest. In this paper, we propose a novel architecture named Graph Temporal Attention with Reinforcement Learning (GTA-RL) to learn solutions for graph-based dynamic optimization problems.
  arXiv  Detail & Related papers  (2022-01-13T11:36:05Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Deep Reinforcement Learning of Graph Matching [63.469961545293756]
  Graph matching (GM) under node and pairwise constraints has been a building block in areas from optimization to computer vision. We present a reinforcement learning solver for GM i.e. RGM that seeks the node correspondence between pairwise graphs. Our method differs from the previous deep graph matching model in the sense that they are focused on the front-end feature extraction and affinity function learning.
  arXiv  Detail & Related papers  (2020-12-16T13:48:48Z)
• GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
  We propose an end-to-end framework that learns an implicit model of graph structure formation and discovers an underlying optimization mechanism. The learned objective can serve as an explanation for the observed graph properties, thereby lending itself to transfer across different graphs within a domain. GraphOpt poses link formation in graphs as a sequential decision-making process and solves it using maximum entropy inverse reinforcement learning algorithm.
  arXiv  Detail & Related papers  (2020-07-07T16:51:39Z)
• Differentiable Causal Discovery from Interventional Data [141.41931444927184]
  We propose a theoretically-grounded method based on neural networks that can leverage interventional data. We show that our approach compares favorably to the state of the art in a variety of settings.
  arXiv  Detail & Related papers  (2020-07-03T15:19:17Z)
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking [2.817395666721831]
  Existing approaches to solving optimization problems on graphs suffer from the need to engineer each problem algorithmically. We organize and compare the structures involved with learning to solve optimization problems, with a special eye on the telecommunications domain.
  arXiv  Detail & Related papers  (2020-05-22T09:45:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.