Neural networks still can’t colour graphs

We were all petrified in our Laboratory. OpenAI claimed to have solve a Millenium Prize problem. An unfathomable amount of money, compute and data has enabled a sophistical neural network to propose a solution to some long-standing mathematics. And yet, in our own line of research, we found that basic optimization tasks still trouble state-of-the-art deep learning models.

Combinatorial optimization in particular, is the name given for a specific class of problems that are pretty much found everywhere in industry and science. For instance, although this doesn’t quite sell how it’s relevant to practice, finding the best possible colouring of a graph is one such problem. Essentially the question goes, if you were given a blue and red pen, how would you colour the nodes on a graph so that you minimize the number of nodes of the same colour being next to each other.

Graph neural networks (GNNs) are the natural way of applying neural networks to graph data. Many important optimization problems are naturally formulated as a graph. So this begs the question, can you use these GNNs to solve these graph-based optimization tasks?

It’s not a silly question by any means, and some famous people have attempted to do so. The problem is, that these tend to come with bold claims about these GNNs working, when in fact the verdict remains ambiguous under basic scrutiny. For example, some researchers have claimed to have developed genuinely competitive neural networks for optimization problems. Then others refute these claims, for example by showing that they barely even compete with basic greedy algorithms (essentially the bare minimum).

So we set out to do investigate two things. Firstly, to properly reassess these deep-learning methods and compare them against “unlearned” algorithms. And secondly, to see what happens if you instead offer a hybrid perspective, and initiate a GNN with heuristics from physics, and try to “learn” further improvements in a more sophisticated way.

MS-GNN is our proposed approach, and you can think of SA (linear) as a ground truth. The higher the line, the better the solution. The horizontal axis for indexes different optimization problems.

What we did find, is that you can use neural networks to refine a physics approach called the energetic cavity method (a fancy way of propagating information efficiently across graphs). This means that we get a fast way of doing optimization that is better than plain graph neural networks, the plain cavity method, and other methods that build from either of these. We even found that it is genuinely the most competitive (in the sense that it gives the best results for the least amount of compute) of all other deep-learning methods considered so far.

MS-GNN is our approach. Only ANYCSP (another deep-learning approach) gives sensible solution qualities, but is many times slower than our approach. Keep in mind that the -axis for runtime is logarithmic.

The irony is that after all of this, a really old method still proves to be the best. Simulated annealing, which was originally proposed in the early 1980s and can be implemented in a couple of lines of code, is still a better approach than any of these deep-learning ones.