A Differentiable Approach to Combinatorial Optimization using Dataless\n Neural Networks

The success of machine learning solutions for reasoning about discrete\nstructures has brought attention to its adoption within combinatorial\noptimization algorithms. Such approaches generally rely on supervised learning\nby leveraging datasets of the combinatorial structures of interest drawn from\nsome distribution of problem instances. Reinforcement learning has also been\nemployed to find such structures. In this paper, we propose a radically\ndifferent approach in that no data is required for training the neural networks\nthat produce the solution. In particular, we reduce the combinatorial\noptimization problem to a neural network and employ a dataless training scheme\nto refine the parameters of the network such that those parameters yield the\nstructure of interest. We consider the combinatorial optimization problems of\nfinding maximum independent sets and maximum cliques in a graph. In principle,\nsince these problems belong to the NP-hard complexity class, our proposed\napproach can be used to solve any other NP-hard problem. Additionally, we\npropose a universal graph reduction procedure to handle large scale graphs. The\nreduction exploits community detection for graph partitioning and is applicable\nto any graph type and/or density. Experimental evaluation on both synthetic\ngraphs and real-world benchmarks demonstrates that our method performs on par\nwith or outperforms state-of-the-art heuristic, reinforcement learning, and\nmachine learning based methods without requiring any data.\n