Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art

Abstract

Graphs have been widely used to represent complex data in many applications. Efficient and effective analysis of graphs is important for graph-based applications. However, most graph analysis tasks are combinatorial optimization (CO) problems, which are NP-hard. Recent studies have focused a lot on the potential of using machine learning (ML) to solve graph-based CO problems. Most recent methods follow the two-stage framework. The first stage is graph representation learning, which embeds the graphs into low-dimension vectors. The second stage uses ML to solve the CO problems using the embeddings of the graphs learned in the first stage. The works for the first stage can be classified into two categories, graph embedding (GE) methods and end-to-end (E2E) learning methods. For GE methods, learning graph embedding has its own objective, which may not rely on the CO problems to be solved. The CO problems are solved by independent downstream tasks. For E2E learning methods, the learning of graph embeddings does not have its own objective and is an intermediate step of the learning procedure of solving the CO problems. The works for the second stage can also be classified into two categories, non-autoregressive methods and autoregressive methods. Non-autoregressive methods predict a solution for a CO problem in one shot. A non-autoregressive method predicts a matrix that denotes the probability of each node/edge being a part of a solution of the CO problem. The solution can be computed from the matrix. Autoregressive methods iteratively extend a partial solution step by step. At each step, an autoregressive method predicts a node/edge conditioned to current partial solution, which is used to its extension. In this survey, we provide a thorough overview of recent studies of the graph learning-based CO methods. The survey ends with several remarks on future research directions.

arXiv comment40 pages

References in corpus (24)

• Distributed Representations of Words and Phrases and their Compositionality
• Distributed Representations of Sentences and Documents
• Inductive Representation Learning on Large Graphs
• Deep Convolutional Networks on Graph-Structured Data
• Learning Combinatorial Optimization Algorithms over Graphs
• struc2vec: Learning Node Representations from Structural Identity
• MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding
• Variational Graph Auto-Encoders
• Junction Tree Variational Autoencoder for Molecular Graph Generation
• Graph Embedding on Biomedical Networks: Methods, Applications, and Evaluations
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• VERSE: Versatile Graph Embeddings from Similarity Measures
• Graph Matching Networks for Learning the Similarity of Graph Structured Objects
• Adaptive Sampling Towards Fast Graph Representation Learning
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Attention, Learn to Solve Routing Problems!
• subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs
• Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• Coloring Big Graphs with AlphaGoZero
• GAP: Generalizable Approximate Graph Partitioning Framework
• Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
• IsoNN: Isomorphic Neural Network for Graph Representation Learning and Classification