Sure, here’s the text in markdown format:
Introduction
Deep Learning (DL) models have achieved outstanding performances in tasks such as image recognition and natural language processing. Deep Reinforcement Learning has also been successful in classic Atari games and in the Chinese board game Go. However, the direct application of DL to symbolic domains is still in its lead-off stages. The combination of connectionist and symbolic approaches may address the bottlenecks faced by these methods when they are used alone. Applying DL models to combinatorial problems arises as one of the main approaches towards achieving integrated machine learning (ML) and reasoning.
Combinatorial problems are naturally represented by graph structures. One way of incorporating the relational structure of a combinatorial problem into a neural model is to ensure permutation invariance by letting adjacent elements of the problem communicate with themselves through neural modules subject to parameter sharing. The family of models that makes use of this message-passing algorithm includes message-passing neural networks, recurrent relational networks, graph networks, and the pioneer model: graph neural network (GNN). In this work, we introduce a model to tackle the decision version of the graph colouring problem (GCP), with no need of prior reductions, and formalise our solution using a GNN framework.
Graph Colouring Problem
The Graph Colouring Problem (GCP) is an important combinatorial problem with applications on flow management, job scheduling, register allocation, and others. Our model mainly relies on GNN’s power of coping with several types of edges as we approached the GCP problem by using two different types of vertices. By designing a GNN model to solve GCP, we hope to foster the adoption and further research on GNN-like models which in turn integrate deep learning and combinatorial optimisation.
Model Performance
We report the model’s performance on different datasets along with baseline heuristics comparisons. Recently, a GNN solution was developed to the NP Complete boolean satisfiability problem (SAT) which achieved around 85% of accuracy on SAT instances containing 40 variables. In this work, we introduce a model to tackle the decision version of the graph colouring problem (GCP) with no need of prior reductions. Our model achieved a high accuracy rate of over 90% on GCP instances with up to 100 vertices.
Analysis and Future Research
From an AI perspective, our work provides useful insights on how neural modules reason over symbolic problems, and also on how their hidden states or embeddings can be interpreted. Further research can investigate the use of GNN models for other combinatorial problems and explore the interpretability of the hidden states or embeddings.
