Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks
Pages 491 - 505
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.
References
[1]
Ahmed S Applications of graph coloring in modern computer science Int. J. Comput. Inf. Technol. 2012 3 2 1-7
[2]
Aragon CR, Johnson D, McGeoch L, and Schevon C Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning Oper. Res. 1991 39 3 378-406
[3]
Barabási AL and Albert R Emergence of scaling in random networks Science 1999 286 5439 509-512
[4]
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)
[5]
Battaglia, P.W., et al.: Relational inductive biases, deep learning, and graph networks. arXiv:1806.01261 (2018)
[6]
Bengio Y, Lodi A, and Prouvost A Machine learning for combinatorial optimization: a methodological tour d’Horizon Eur. J. Oper. Res. 2021 290 2 405-421
[7]
Brandes U, Gaertler M, and Wagner D Di Battista G and Zwick U Experiments on graph clustering algorithms Algorithms - ESA 2003 2003 Heidelberg Springer 568-579
[8]
Branke J, Nguyen S, Pickardt CW, and Zhang M Automated design of production scheduling heuristics: a review IEEE Trans. Evol. Comput. 2015 20 1 110-124
[9]
Brélaz D New methods to color the vertices of a graph Commun. ACM 1979 22 4 251-256
[10]
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)
[11]
Erdős P and Rényi A On random graphs I Publicationes Math. 1959 6 1 290-297
[12]
Formanowicz P and Tanaś K A survey of graph coloring - its types, methods and applications Found. Comput. Decis. Sci. 2012 37 3 223-238
[13]
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)
[14]
Galinier P and Hao JK Hybrid evolutionary algorithms for graph coloring J. Comb. Optim. 1999 3 4 379-397
[15]
Garey, M.R., Johnson, D.S.: Computers and intractability, vol. 174. Freeman, San Francisco (1979)
[16]
Gianinazzi, L., Fries, M., Dryden, N., Ben-Nun, T., Besta, M., Hoefler, T.: Learning combinatorial node labeling algorithms. arXiv preprint arXiv:2106.03594 (2021)
[17]
Hertz A and de Werra D Using tabu search techniques for graph coloring Computing 1987 39 4 345-351
[18]
Huang, J., Patwary, M., Diamos, G.: Coloring big graphs with alphagozero. arXiv preprint arXiv:1902.10162 (2019)
[19]
Ireland, D., Montana, G.: Lense: Learning to navigate subgraph embeddings for large-scale combinatorial optimisation. In: International Conference on Machine Learning (2022)
[20]
Janczewski R, Kubale M, Manuszewski K, and Piwakowski K The smallest hard-to-color graph for algorithm DSATUR Discret. Math. 2001 236 1–3 151-165
[21]
Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
[22]
Korte B and Vygen J Combinatorial Optimization 2018 Heidelberg Springer
[23]
Leighton FT A graph coloring algorithm for large scheduling problems J. Res. Natl. Bur. Stand. 1979 84 6 489-506
[24]
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)
[25]
Lewis RMR Guide to Graph Colouring 2021 Cham Springer
[26]
de Lima AM and Carmo R Exact algorithms for the graph coloring problem Revista de Informática Teórica e Aplicada 2018 25 4 57-73
[27]
Lü Z and Hao JK A memetic algorithm for graph coloring Eur. J. Oper. Res. 2010 203 1 241-250
[28]
Lund C and Yannakakis M On the hardness of approximating minimization problems J. ACM (JACM) 1994 41 5 960-981
[29]
Mazyavkina N, Sviridov S, Ivanov S, and Burnaev E Reinforcement learning for combinatorial optimization: a survey Comput. Oper. Res. 2021 134 105400
[30]
Mnih, V., et al.: Playing atari with deep reinforcement learning. arXiv:1312.5602 (2013)
[31]
Moalic L and Gondran A Variations on memetic algorithms for graph coloring problems J. Heuristics 2018 24 1 1-24
[32]
Sager TJ and Lin SJ A pruning procedure for exact graph coloring ORSA J. Comput. 1991 3 3 226-230
[33]
Scarselli F, Gori M, Tsoi AC, Hagenbuchner M, and Monfardini G The graph neural network model IEEE Trans. Neural Netw. 2008 20 1 61-80
[34]
Silver D et al. Mastering the game of go without human knowledge Nature 2017 550 7676 354-359
[35]
Smith KA Neural networks for combinatorial optimization: a review of more than a decade of research INFORMS J. Comput. 1999 11 1 15-34
[36]
Spinrad JP and Vijayan G Worst case analysis of a graph coloring algorithm Discret. Appl. Math. 1985 12 1 89-92
[37]
Vaswani, A., et al.: Attention is all you need. In: Advances in Neural Information Processing Systems, vol. 30 (2017)
[38]
Watkins CJ and Dayan P Q-learning Mach. Learn. 1992 8 3 279-292
[39]
Watts DJ and Strogatz SH Collective dynamics of ‘small-world’ networks Nature 1998 393 6684 440-442
[40]
Williams RJ Simple statistical gradient-following algorithms for connectionist reinforcement learning Mach. Learn. 1992 8 3 229-256
[41]
Zhou Y, Hao JK, and Duval B Reinforcement learning based local search for grouping problems: a case study on graph coloring Expert Syst. Appl. 2016 64 412-422
Recommendations
Graph edge colouring: Tashkinov trees and Goldberg's conjecture
For the chromatic index @g^'(G) of a (multi)graph G, there are two trivial lower bounds, namely the maximum degree @D(G) and the density W(G)=max"H"@__ __"G","|"V"("H")"|">="2@__ __|E(H)|/@__ __|V(H)|/2@__ __@__ __. A famous conjecture due to Goldberg [...
Steinberg-like theorems for backbone colouring
AbstractA function f : V ( G ) → { 1 , … , k } is a (proper) k-colouring of G if ∣ f ( u ) − f ( v ) ∣ ≥ 1, for every edge u v ∈ E ( G ). The chromatic number χ ( G ) is the smallest integer k for which there exists a proper k-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Jun 2023
627 pages
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 25 October 2023
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Aug 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in