Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set

The recent work by Schuetz et al. ‘Combinatorial optimization with physics-inspired graph neural networks’ introduces a physics-inspired unsupervised graph neural network (GNN) to solve combinatorial optimization problems on sparse graphs. To test the performances of these GNNs, the authors show numerical results for two fundamental problems: the maximum cut and the maximum independent set (MIS), concluding “that the graph neural network optimizer performs on par or outperforms existing solvers, with the ability to scale beyond the state of the art to problems with millions of variables”. Here we show that a simple greedy algorithm, running in almost linear time, can find solutions for the MIS problem of much better quality than the GNN in a much shorter time. In general, many claims of superiority of neural networks in solving combinatorial problems are at risk of being not solid enough, as we lack standard benchmarks based on really hard problems. We propose one of such hard benchmarks, and we hope to see future neural network optimizers tested on these problems before any claim of superiority is made.