Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
We present a learning-based approach to computing solutions for certain NPhard problems. Our approach combines deep learning techniques with useful algorithmic elements from classic heuristics. The central component is a graph convolutional network that is trained to estimate the likelihood, for each vertex in a graph, of whether this vertex is part of the optimal solution. The network is designed and trained to synthesize a diverse set of solutions, which enables rapid exploration of the solution space via tree search. The presented approach is evaluated on four canonical NP-hard problems and five datasets, which include benchmark satisfiability problems and real social network graphs with up to a hundred thousand nodes. Experimental results demonstrate that the presented approach substantially outperforms recent deep learning work, and performs on par with highly optimized state-of-the-art heuristic solvers for some NP-hard problems. Experiments indicate that our approach generalizes across datasets, and scales to graphs that are orders of magnitude larger than those used during training.
of solutions, which enables the network to explicitly disambiguate different modes in the solution space. This trained GCN is used to guide a parallelized tree search procedure that rapidly generates a large number of candidate solutions, one of which is chosen after subsequent refinement.
We apply the presented approach to four canonical NP-hard problems: Satisfiability (SAT), Maximal Independent Set (MIS), Minimum Vertex Cover (MVC), and Maximal Clique (MC). The approach is evaluated on two SAT benchmarks, an MC benchmark, real-world citation network graphs, and social network graphs with up to one hundred thousand nodes from the Stanford Large Network Dataset Collection. The experiments indicate that our approach substantially outperforms recent state-of-the-art (SOTA) deep learning work. For example, on the SATLIB benchmark, our approach solves all of the problems in the test set, while a recent method based on reinforcement learning does not solve any. The experiments also indicate that our approach performs on par with or better than highly-optimized contemporary solvers based on traditional heuristic methods. Furthermore, the experiments indicate that the presented approach generalizes across datasets and scales to graphs that are orders of magnitude larger than those used during training.
This paper proposes a method combining graph neural networks and guided tree search to tackle combinatorial optimization problems. The authors focus on the Maximum Independent Set (MIS), the Minimum Vertex Cover (MVC), Maximal Clique (MC) and Satisfiability which are all reduced to MIS. Given a MIS instance represented by a graph, the method consists in using the predictions of a graph convolutional neural (GCN) network, which is trained with binary cross-entropy to predict whether a vertex is in the maximum independent set, as input for a greedy search algorithm. The greedy search algorithm considers vertices in descending order of the GCN outputs, adding them to the independent set if doing so doesn't violate the independence assumption. Once this isn't possible, the process is repeated on the residual graph until termination. The method is further augmented with diversity, allowing the GCN to output different probability maps, and a tree search (partial solutions are added to a queue from which they will be randomly sampled to be further constructed). They train on a MIS graphs obtained from satisfiable SAT instances from the SATLIB benchmark for which solutions are available. They test the approach on instances coming from synthetic datasets and real-world graphs (such as citation networks or social networks). The authors compare their approach to the S2V-DQN baseline (from Learning Combinatorial Algorithms over Graph), the SOTA ILP solver Gurobi and the SMT solver Z3. Interestingly, the approach transfers well to different data distributions, larger instances and other problems. The proposed approach outperforms S2V-DQN and sometimes outperforms Z3 or Gurobi (which are hard baselines - assuming they're applied on the right problem).  The paper is clearly written and proposes a novel approach for tackling combinatorial optimization (a fundamental field in computer science) using machine learning. Some results are particularly interesting such as the fact that the approach transfers that well to other problems and larger instances or the fact that using the diversity loss provides such an improvement.  However, I have several issues with the current state of this draft (in no particular order). I am of course willing to change my low rating if these issues are addressed.  - Although the proposed method clearly improves over Classic+GR+LS and in spite of the ablation study in Table 4, I think that a random baseline (ie Random+GR+LS) is necessary to evaluate the usefulness of the neural netwrok in the approach. That random baseline should be given the same time budget and should be similar to the proposed approach except for the fact that it wouldn't query the network (ie use a random order).  - Supervised learning is presented as an advantage of the method on the premise that Reinforcement learning is a particularly challenging optimization problem and that supervised learning benefits from well-understood and reliable solvers. I believe that relying on labeled solutions is a weakness (albeit small) of the approach since it requires having solved (even approximately) NP-Hard problems. This is echoed in Neural Combinatorial Optimization with Reinforcement Learning (NCO), where the authors show that RL training clearly outperforms Supervised Learning training without requiring the need for costly solutions.  - The S2V-DQN baseline is quite weak in my opinion: *) I take exception that S2V-DQN outperforms prior deep learning approaches such as NCO: the results that they report when reimplementing NCO are worse than those initially reported in NCO paper, they used a moving average baseline instead of a critic, they don't use the fact that NCO can sample many solutions as one etc... *) As correctly pointed out by the authors, S2V-DQN only outputs one solution while their approach considers multiple solutions. In comparison, NCO and Attention solves your TSP, approximately (which uses a Transformer-Pointer Network instead of an RNN Pointer Network) can output many solutions (when sampling) making them better baselines to the proposed approach. *) Attention solves your TSP, approximately does outperform prior learning-based approaches (and actually shows that the NCO approach outperforms S2V-DQN) This contrasts to the overall tone of the paper that their method clearly surpasses recent work ("Our algorithm convincingly outperforms recent work" in the conclusion)  - The authors should also cite recent machine learning / combinatorial optimization work such as NeuroSAT, Attention solves your TSP,  Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks, etc.  =================================================  ) Random+GR+LS: The 12.7% performance of this baseline outlines how important it is to consider multiple solutions.  2) Relying on supervised data is a weakness: I misunderstood that the labels relied on solvers. I agree that this is not an issue if the labels are generated without a solver and the authors have shown strong generalization.  3)  The S2V-DQN baseline is quite weak. Out of the considered learning based approaches (ie NCO, ASTSP, the authors' method and S2V-DQN), S2V-DQN is the only method that considers a single solution.  NCO and ASTSP can easily consider multiple solutions (by sampling) but it looks like the authors use the greedy version ASTSP only (this is hard to tell from the rebuttal but given that ASTSP solves 0% while random search solves 12.7% this seems to be the case).  4) I also invite the authors to reconsider the following statements which are incorrect / misleading. (a) "Most recently, Dai et al. [10] used reinforcement learning to train a deep Q-network (DQN) to incrementally construct solutions to graph-based NP-hard problems, and showed that this approach outperforms prior learning-based techniques." - For tasks where the methods are comparable (and compared), Dai et al report worse results when reimplementing NCO than those initially reported in NCO paper. Careful reading indicates that they used a moving average baseline instead of a critic, they don't use the fact that NCO can sample many solutions as one, etc... This is also echoed in a figure from the independent ASTSP paper which present NCO and ASTSP as outperforming Dai et al.  (b) "First, we do not use reinforcement learning, which is known as a particularly challenging optimization problem. Rather, we show that very strong performance and generalization can be achieved with supervised learning, which benefits from well-understood and reliable solvers." - Previous work in combinatorial optimization has shown that RL is better suited than supervised learning (at least for pointer network models). - Reliance on solvers is a weakness in general.  (c) (rebuttal) "RL-based approaches consider problems up to 100 variables". This is not true (although the authors have indeed tackled larger problems that prior work). It also not clear why this statement is relevant to the comparison of RL vs supervised learning: I think it has more to do with the types of models being used rather than the training method.  In summary, I have a significant presentation issue with this paper.  I agree that % of solved instances is an important practical metric but it obviously greatly favors methods that consider multiple solutions. The paper does a poor job at outlining this fact and compares only to learning based methods that only consider a single solution (ie S2V-DQN). The fact that all other learning based are outperformed by the random search further demonstrates my point. Methods tend to be much closer when looking at the average independent set size metric. (The authors also didn't report this metric for ASTSP or Random+GR+LS in the rebuttal).  Relying on search (ie trying multiple solutions) to get good results is not a weakness of the paper in itself and I actually think it's a promising direction to combine both classic search methods with machine learning. However comparing to learning-based methods that only consider a single solution when considering to a metric that favors multiple solutions can be misleading . Especially that these methods can easily be augmented by search (ie sampling in NCO and ASTSP). The other incorrect statements about related work (mistakenly saying that the RL-based approaches consider up to 100 variables, etc.) also don't play in favor of the work.  If this wasn't for these issues, this would be a strong paper. I appreciate the thorough response of the authors and I have updated my score to 4.