NeurIPS 2020

Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs

Meta Review

This is a surprising, novel, and principled framework for unsupervised ML-based combinatorial optimization. It translates the Erdos' Probabilistic Method for combinatorial optimization into a learning framework, producing impressive results. The paper should be improved following suggestions discussed in the rebuttal, but this should be straightforward. Overall, I'll quote R2: "Unlike many recent papers in this space which are rather incremental in combining GNN with reinforcement learning in various ways, this paper proposes a fresh, fundamentally new perspective."