  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.
