The Library
Generating a graph colouring heuristic with deep Q-learning and graph neural networks
Tools
Watkins, George, Montana, Giovanni and Branke, Jürgen (2023) Generating a graph colouring heuristic with deep Q-learning and graph neural networks. In: The 17th Learning and Intelligent Optimization Conference, Nice, France, 4-8 Jun 2023. Published in: Learning and Intelligent Optimization. LION 2023, 14286 ISBN 9783031445040. doi:10.1007/978-3-031-44505-7_33
PDF
WRAP-generating-graph-colouring-heuristic-deep-Q-learning-graph-neural-networks-2023.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only until 25 October 2024. Contact author directly, specifying your specific needs. - Requires a PDF viewer. Download (889Kb) |
Official URL: https://doi.org/10.1007/978-3-031-44505-7_33
Abstract
The graph colouring problem consists of assigning labels, or colours, to the vertices of a graph such that no two adjacent vertices share the same colour. In this work we investigate whether deep reinforcement learning can be used to discover a competitive construction heuristic for graph colouring. Our proposed approach, ReLCol, uses deep Q-learning together with a graph neural network for feature extraction, and employs a novel way of parameterising the graph that results in improved performance. Using standard benchmark graphs with varied topologies, we empirically evaluate the benefits and limitations of the heuristic learned by ReLCol relative to existing construction algorithms, and demonstrate that reinforcement learning is a promising direction for further research on the graph colouring problem.
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > Q Science (General) Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
Divisions: | Faculty of Social Sciences > Warwick Business School Faculty of Science, Engineering and Medicine > Engineering > WMG (Formerly the Warwick Manufacturing Group) |
|||||||||
Library of Congress Subject Headings (LCSH): | Graph coloring, Deep learning (Machine learning), Reinforcement learning, Neural networks (Computer science) | |||||||||
Series Name: | Lecture Notes in Computer Science | |||||||||
Journal or Publication Title: | Learning and Intelligent Optimization. LION 2023 | |||||||||
Publisher: | Springer | |||||||||
ISBN: | 9783031445040 | |||||||||
Official Date: | 25 October 2023 | |||||||||
Dates: |
|
|||||||||
Volume: | 14286 | |||||||||
DOI: | 10.1007/978-3-031-44505-7_33 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Re-use Statement: | “This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/978-3-031-44505-7_33. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms”. Under no circumstances may an Accepted Manuscript be shared or distributed under a Creative Commons or other form of open access licence. | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
Date of first compliant deposit: | 21 April 2023 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | The 17th Learning and Intelligent Optimization Conference | |||||||||
Type of Event: | Conference | |||||||||
Location of Event: | Nice, France | |||||||||
Date(s) of Event: | 4-8 Jun 2023 | |||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |