Timezone: »

Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
Zhuwen Li · Qifeng Chen · Vladlen Koltun

Thu Dec 06 07:45 AM -- 09:45 AM (PST) @ Room 210 #93

We present a learning-based approach to computing solutions for certain NP-hard 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.

Author Information

Zhuwen Li (Intel Labs)
Qifeng Chen (HKUST)
Vladlen Koltun (Intel Labs)

More from the Same Authors