
First, regarding the first step, we propose to run in parallel \(p\)  local searches with algorithm A starting from different states, instead of a single one. It enables the generations of \(p\)  different search trajectories allowing one to build a training dataset with a high diversity of examples.

Secondly, regarding the step 2, we do not use any prior mapping \(F\)  from states to features. Following the current trend in deep learning, the embedding of the state can be directly learned in an end-to-end pipeline with a deep neural network, denoted as \(f_{\theta }: \mathcal {S} \rightarrow \mathbb {R}\) . We make this neural network invariant by permutation of the group of colors \(V_j\)  in the coloring \(S \in \mathcal {S}\)  which is a very important feature of all graph coloring problems, by adapting the deep set network architecture proposed in [1]} (see Section REF ).

Thirdly, in the step 3 of the original STAGE algorithm, a hillclimbing algorithm is used to optimize the current solution guided by the objective function \(\hat{f}_A\) . However, as we address a very complex problem and we use a complex non-convex and non-linear function (deep neural network), it is difficult to optimize it using a hillclimbing algorithm. We tried to use more complex algorithms such as tabu search to optimize it, but there is a deeper problem, which is the question of generalization. Indeed, if a state \(S\)  is too different from the states already seen before in the training dataset, and in particular if the color groups \(V_j\)  that composed it are too different from the color groups already seen before by the neural network, we expect that \(f_{\theta }(S)\)  can be very inaccurate for the estimation of \(\mathbb {E}[f_A(S)]\) . Therefore, we propose to replace this hillclimbing procedure by a crossover operation between different members of a population of candidate solutions. By recombining the different color groups already seen before by the learning algorithm we expect the approximation of \(\mathbb {E}[f_A(S)]\) , given by \(f_{\theta }(S)\) , to be more precise.

