Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks
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.
Code (1)
Tasks
Deep Reinforcement LearningGraph Neural NetworkQ-Learningreinforcement-learningReinforcement LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Unsupervised Graph-based Learning Method for Sub-band Allocation in 6G Subnetworks
In this paper, we present an unsupervised approach for frequency sub-band allocation in wireless networks using graph-based learning. We consider a dense deployment of subnetworks in the factory environment with a limite…
Graph Colouring Problem Based on Discrete Imperialist Competitive Algorithm
In graph theory, Graph Colouring Problem (GCP) is an assignment of colours to vertices of any given graph such that the colours on adjacent vertices are different. The GCP is known to be an optimization and NP-hard probl…
validLocal Vertex Colouring Graph Neural Networks
In recent years, there has been a significant amount of research focused on expanding the expressivity of Graph Neural Networks (GNNs) beyond the Weisfeiler-Lehman (1-WL) framework. While many of these studies have yield…
Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems
Deep learning has consistently defied state-of-the-art techniques in many fields over the last decade. However, we are just beginning to understand the capabilities of neural learning in symbolic domains. Deep learning a…
Deep LearningGraph Neural NetworkIncremental Inference on Higher-Order Probabilistic Graphical Models Applied to Constraint Satisfaction Problems
Probabilistic graphical models (PGMs) are tools for solving complex probabilistic relationships. However, suboptimal PGM structures are primarily used in practice. This dissertation presents three contributions to the PG…
Land Cover Classification