Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ahmed, S.: Applications of graph coloring in modern computer science. Int. J. Comput. Inf. Technol. 3(2), 1–7 (2012)
Aragon, C.R., Johnson, D., McGeoch, L., Schevon, C.: Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning. Oper. Res. 39(3), 378–406 (1991)
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
Barrett, T., Clements, W., Foerster, J., Lvovsky, A.: Exploratory combinatorial optimization with reinforcement learning. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 3243–3250 (2020)
Battaglia, P.W., et al.: Relational inductive biases, deep learning, and graph networks. arXiv:1806.01261 (2018)
Bengio, Y., Lodi, A., Prouvost, A.: Machine learning for combinatorial optimization: a methodological tour d’Horizon. Eur. J. Oper. Res. 290(2), 405–421 (2021)
Brandes, U., Gaertler, M., Wagner, D.: Experiments on graph clustering algorithms. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 568–579. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39658-1_52
Branke, J., Nguyen, S., Pickardt, C.W., Zhang, M.: Automated design of production scheduling heuristics: a review. IEEE Trans. Evol. Comput. 20(1), 110–124 (2015)
Brélaz, D.: New methods to color the vertices of a graph. Commun. ACM 22(4), 251–256 (1979)
Corso, G., Cavalleri, L., Beaini, D., Liò, P., Veličković, P.: Principal neighbourhood aggregation for graph nets. In: Advances in Neural Information Processing Systems, vol. 33, pp. 13260–13271 (2020)
Erdős, P., Rényi, A.: On random graphs I. Publicationes Math. 6(1), 290–297 (1959)
Formanowicz, P., Tanaś, K.: A survey of graph coloring - its types, methods and applications. Found. Comput. Decis. Sci. 37(3), 223–238 (2012)
Fricke, G., et al.: Combinatorial problems on chessboards: a brief survey. In: Quadrennial International Conference on the Theory and Applications of Graphs, vol. 1, pp. 507–528 (1995)
Galinier, P., Hao, J.K.: Hybrid evolutionary algorithms for graph coloring. J. Comb. Optim. 3(4), 379–397 (1999)
Garey, M.R., Johnson, D.S.: Computers and intractability, vol. 174. Freeman, San Francisco (1979)
Gianinazzi, L., Fries, M., Dryden, N., Ben-Nun, T., Besta, M., Hoefler, T.: Learning combinatorial node labeling algorithms. arXiv preprint arXiv:2106.03594 (2021)
Hertz, A., de Werra, D.: Using tabu search techniques for graph coloring. Computing 39(4), 345–351 (1987)
Huang, J., Patwary, M., Diamos, G.: Coloring big graphs with alphagozero. arXiv preprint arXiv:1902.10162 (2019)
Ireland, D., Montana, G.: Lense: Learning to navigate subgraph embeddings for large-scale combinatorial optimisation. In: International Conference on Machine Learning (2022)
Janczewski, R., Kubale, M., Manuszewski, K., Piwakowski, K.: The smallest hard-to-color graph for algorithm DSATUR. Discret. Math. 236(1–3), 151–165 (2001)
Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
Korte, B., Vygen, J.: Combinatorial Optimization. AC, vol. 21. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-662-56039-6
Leighton, F.T.: A graph coloring algorithm for large scheduling problems. J. Res. Natl. Bur. Stand. 84(6), 489–506 (1979)
Lemos, H., Prates, M., Avelar, P., Lamb, L.: Graph colouring meets deep learning: effective graph neural network models for combinatorial problems. In: International Conference on Tools with Artificial Intelligence, pp. 879–885. IEEE (2019)
Lewis, R.M.R.: Guide to Graph Colouring. TCS, Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81054-2
de Lima, A.M., Carmo, R.: Exact algorithms for the graph coloring problem. Revista de Informática Teórica e Aplicada 25(4), 57–73 (2018)
Lü, Z., Hao, J.K.: A memetic algorithm for graph coloring. Eur. J. Oper. Res. 203(1), 241–250 (2010)
Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM (JACM) 41(5), 960–981 (1994)
Mazyavkina, N., Sviridov, S., Ivanov, S., Burnaev, E.: Reinforcement learning for combinatorial optimization: a survey. Comput. Oper. Res. 134, 105400 (2021)
Mnih, V., et al.: Playing atari with deep reinforcement learning. arXiv:1312.5602 (2013)
Moalic, L., Gondran, A.: Variations on memetic algorithms for graph coloring problems. J. Heuristics 24(1), 1–24 (2018)
Sager, T.J., Lin, S.J.: A pruning procedure for exact graph coloring. ORSA J. Comput. 3(3), 226–230 (1991)
Scarselli, F., Gori, M., Tsoi, A.C., Hagenbuchner, M., Monfardini, G.: The graph neural network model. IEEE Trans. Neural Netw. 20(1), 61–80 (2008)
Silver, D., et al.: Mastering the game of go without human knowledge. Nature 550(7676), 354–359 (2017)
Smith, K.A.: Neural networks for combinatorial optimization: a review of more than a decade of research. INFORMS J. Comput. 11(1), 15–34 (1999)
Spinrad, J.P., Vijayan, G.: Worst case analysis of a graph coloring algorithm. Discret. Appl. Math. 12(1), 89–92 (1985)
Vaswani, A., et al.: Attention is all you need. In: Advances in Neural Information Processing Systems, vol. 30 (2017)
Watkins, C.J., Dayan, P.: Q-learning. Mach. Learn. 8(3), 279–292 (1992)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998)
Williams, R.J.: Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8(3), 229–256 (1992)
Zhou, Y., Hao, J.K., Duval, B.: Reinforcement learning based local search for grouping problems: a case study on graph coloring. Expert Syst. Appl. 64, 412–422 (2016)
Acknowledgements
G. Watkins acknowledges support from EPSRC under grant EP/L015374/1.
G. Montana acknowledges support from EPSRC under grant EP/V024868/1.
We thank L. Gianinazzi for sharing the code for the method presented in [16].
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Watkins, G., Montana, G., Branke, J. (2023). Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks. In: Sellmann, M., Tierney, K. (eds) Learning and Intelligent Optimization. LION 2023. Lecture Notes in Computer Science, vol 14286. Springer, Cham. https://doi.org/10.1007/978-3-031-44505-7_33
Download citation
DOI: https://doi.org/10.1007/978-3-031-44505-7_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-44504-0
Online ISBN: 978-3-031-44505-7
eBook Packages: Computer ScienceComputer Science (R0)