Deep Learning Chromatic and Clique Numbers of Graphs
This work addresses NP-complete combinatorial optimization problems in graph theory, offering a method that avoids complex feature engineering.
The paper tackled predicting the chromatic number and maximum clique size of graphs using deep learning models, achieving strong performance with convolutional neural networks trained on adjacency matrices.
Deep neural networks have been applied to a wide range of problems across different application domains with great success. Recently, research into combinatorial optimization problems in particular has generated much interest in the machine learning community. In this work, we develop deep learning models to predict the chromatic number and maximum clique size of graphs, both of which represent classical NP-complete combinatorial optimization problems encountered in graph theory. The neural networks are trained using the most basic representation of the graph, the adjacency matrix, as opposed to undergoing complex domain-specific feature engineering. The experimental results show that deep neural networks, and in particular convolutional neural networks, obtain strong performance on this problem.