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

Summary and Contributions: This paper considers the problem of learning to do combinatorial optimization on graphs. In particular, it focuses on a set of constrained minimization problems: given an objective function and a constraint, find a set of nodes minimizing the objective function subject to the constraint. This is a broad family that includes many NP-hard problems. The goal is to train a neural network such that, when given a new instance of one of these problems, it can efficiently compute a solution satisfying the constraints whose cost is "close" to the optimal cost. This work proposes a novel framework for unsupervised combinatorial optimization on graphs, which is inspired by Erdos's probabilistic proof technique and makes it more likely that the outputs produce a valid solution when compared to previous approaches.