Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks

George Watkins, Giovanni Montana, Juergen Branke
4/8/2023
cs.LG

No official code found. Best implementation: gpdwatkins/graph_colouring_with_RL (4 stars, last commit 2023-10-16).

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.

View on arXivView PDF

Code Implementations(1)

gpdwatkins/graph_colouring_with_RLCommunity100%

Supplementary material for Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks paper

42PythonFeb 7, 20233 years ago

Similar Papers

Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs

84% match2024

Reinforcement Learning for Graph Coloring: Understanding the Power and Limits of Non-Label Invariant Representations

83% match2024

Graph Neural Networks as Ordering Heuristics for Parallel Graph Coloring

83% match2024

Neural Algorithmic Reasoning for Approximate k-Coloring with Recursive Warm Starts

81% match1 repo12026

Contrastive Neural Algorithmic Reasoning for Graph Coloring

80% match2026

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

79% match2024

Cite this paper

@article{watkins2023generating,
  title  = {Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks},
  author = {George Watkins and Giovanni Montana and Juergen Branke},
  year   = {2023},
  eprint = {2304.04051},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2304.04051v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2304.04051.svg)](https://codeofpaper.com/paper/2304.04051)

Discussion