Learning Combinatorial Optimization Algorithms over Graphs

By Elias Boutros Khalil, Hanjun Dai, Yuyu Zhang, Bistra N. Dilkina, Le Song. Neural Information Processing Systems, 2017

1,745 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Reinforcement Learning, Graph Learning

View Paper: https://arxiv.org/abs/1704.01665

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Reinforcement Learning

In Graph Learning

Citations in the corpus

Structured Convolutional Kernel Networks for Airline Crew Scheduling (2021, background): “, 2020), (2) to solve the optimization problem end-to-end (Khalil et al., 2017), or (3) to guide an optimization process (variable selection in branch-and-bound Gasse et al.”
Structured agents for physical construction (2019, methodology): “We implement a DQN agent with a structured graph input and graph output (roughly similar to Dai et al. (2017)), but where the Q-function is deﬁned on the edges of the graph.”
Relational inductive biases, deep learning, and graph networks (2018, methodology): “…and structure, have also been explored with graph neural networks, such as combinatorial optimization (Bello et al., 2016; Nowak et al., 2017; Dai et al., 2017), boolean satisﬁability (Selsam et al., 2018), program representation and veriﬁcation (Allamanis et al., 2018; Li et al., 2016),…”
Relational Deep Reinforcement Learning (2018, background): “This approach builds off previous work suggesting that relational computations needn’t necessarily be biased by entities’ spatial proximity [20, 10, 21, 11, 13], and may also profit from iterative structured reasoning [22, 23, 24, 25].”
Attention-based Graph Neural Network for Semi-supervised Learning (2018, methodology): “There are several extensions to this model as discussed in the previous section, but this standard graph neural network has proved powerful in several problems over graphs, e.g. [9, 6, 14].”
Learning a SAT Solver from Single-Bit Supervision (2018, background): “…neural network architectures can learn good heuristics for NP -hard combinatorial optimization problems (Vinyals et al., 2015; Bello et al., 2016; Dai et al., 2017); however, ﬁnding low-cost solutions to optimization problems requires less precise reasoning than ﬁnding satisfying assignments.”
Recent Advances in Neural Program Synthesis (2018, background): “In "Learning Combinatorial Optimization Over Graphs" [23] the researchers demonstrate high quality results when the neural programming model is constrained to produce greedy algorithms.”
Learning to Perform Local Rewriting for Combinatorial Optimization (2018, methodology): “, with a Seq2Seq model) from the problem specification [50, 6, 33, 28].”
Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization (2018, background): “There is a growing body of research at the interface of machine learning and discrete optimization (Vinyals, Fortunato, and Jaitly 2015; Bertsimas and Dunn 2017; Khalil et al. 2017b; Khalil et al. 2017a).”
Can graph neural networks count substructures? (2020, background): “In the past few years, graph neural networks (GNNs) have achieved empirical success on processing data from various fields such as social networks, quantum chemistry, particle physics, knowledge graphs and combinatorial optimization (Scarselli et al., 2008; Bruna et al., 2013; Duvenaud et al., 2015;”
Deep Learning for Intelligent Transportation Systems: A Survey of Emerging Trends (2020, neutral): “[51], and Kool et al.”
AliGraph: A Comprehensive Graph Neural Network Platform (2019, background): “Typical examples include social networks [21, 30], physical systems [1, 43], biological networks [14], knowledge graphs [19] and etc [28].”
Adversarial Attack on Graph Structured Data (2018, methodology): “Recently, there are some exciting works using reinforcement learning to learn to solve the general sequential decision problems (Bello et al., 2016) or graph combinatorial problems (Dai et al., 2017).”
Graph Neural Networks in Recommender Systems: A Survey (2020, background): “Recently, systems based on variants of GNN have demonstrated ground-breaking performance on many tasks related to graph data, such as physical systems [2, 45], protein structure [11], knowledge graph [15] and other areas [3, 4, 26].”
An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem (2019, methodology): “…as the Vehicle Routing Problem [Nazari et al., 2018, Kool et al., 2019] and the multiple TSP [Kaempfer and Wolf, 2018], as well as other combinatorial problems such as the Minimum Vertex Cover Problem and the Maximum Cut Problem [Dai et al., 2017, Venkatakrishnan et al., 2018, Mittal et al., 2019].”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, background): “) can be expressed in terms of graphs and recently, there has been interest [60, 85, 102] in leveraging graph embeddings to approximate solutions of NP-hard problems.”
Text Level Graph Neural Network for Text Classification (2019, background): “, 2017) and many other research areas (Khalil et al., 2017) are with data in the form of trees or graphs.”