Post #508

Constructions in combinatorics via neural networks I have been fascinated about potential of using machine learning for combinatorial problems and have written multiple posts (here and here) and a survey about this. And as such it was exciting to see a work that applies RL framework to disprove several combinatorial conjectures. The algorithm is very simple: generate many graphs with MLP, select the top-X of them, use cross-entropy to update MLP. So it does not use recent advances in RL, neither in GML to care about invariance of the input. So there is a room for improvement. Also it generates graphs of pre-determined size, so if a counterexample has a big order it would be difficult to know in advance. But it would be very interesting to apply this framework to more complicated conjectures such as reconstruction conjecture.