Learning Combinatorial Optimization Algorithms over Graphs
The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case that the same optimization problem is solved again and again on a regular basis, maintaining the same problem structure but differing in the data. This provides an opportunity for learning heuristic algorithms that exploit the structure of such recurring problems. In this paper, we propose a unique combination of reinforcement learning and graph embedding to address this challenge. The learned greedy policy behaves like a meta-algorithm that incrementally constructs a solution, and the action is determined by the output of a graph embedding network capturing the current state of the solution. We show that our framework can be applied to a diverse range of optimization problems over graphs, and learns effective algorithms for the Minimum Vertex Cover, Maximum Cut and Traveling Salesman problems.
The authors propose a reinforcement learning strategy to learn new heuristic (specifically, greedy) strategies for solving graph-based combinatorial problems. An RL framework is combined with a graph embedding approach. The RL approach effectively learns a greedy policy for selecting constructing an approximate solution. The approach is innovative and the empirical results appear promising. An important advantage of the work is that the learned policy is not restricted to a fixed problem size, in contrast to earlier work.
One drawback of the paper is that I found the writing unnecessarily dense and unclear at various places. In particular, it would be good to include more details on the intuitive description of the approach. I believe the ideas can be stated clearly in words because the concept of learning a greedy policy is not that different from learning any policy as done in RL (Learning the “next move to make” in a game is quite analogous to learning what is the next node in the graph to select. So, the authors can focus more on what makes this work different from learning a game strategy.) The over reliance on formal notation does not help. 
I did not fully check the formal details but some points were unclear. For example, a state is defined as a sequence of action nodes on the graph. Each node in the tagged graph is represented by its p-dimensional embedding (a p-dimensional vector). A state is then defined as the sum of the vectors corresponding to the set of action nodes so far. Why is this choice of state definition the “right one”?
The empirical results are promising but some further insights would be helpful. For most combinatorial problems there is a known basic greedy strategy that already performs quite well. Does RL rediscover those strategies for the domains under consideration? (If the framework has the potential to discover new algorithmic strategy, it would be good to know that the approach can also re-discover known strategies.)