# Deep Learning Chromatic and Clique Numbers of Graphs

arXiv: https://arxiv.org/abs/2108.01810 · HTML: https://mlsanity.com/paper/2108.01810/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 14 references that are in the map.
- First posted on arXiv 4 Aug 2021.

## Builds on (most cited first, 3 of 3)

- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)
- [Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems](https://mlsanity.com/paper/1903.04598/) (2019)
- [Coloring Big Graphs with AlphaGoZero](https://mlsanity.com/paper/1902.10162/) (2019)

## Abstract (arXiv)

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.