论文标题
组合优化的图形学习：最新的调查
Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
论文作者
论文摘要
图表已被广泛用于表示许多应用程序中的复杂数据。对图的有效分析对于基于图的应用很重要。但是，大多数图形分析任务是组合优化（CO）问题，它们是NP-HARD。最近的研究非常集中于使用机器学习（ML）解决基于图的CO问题的潜力。最近的方法遵循两阶段的框架。第一阶段是图表学习，将图形嵌入到低维向量中。第二阶段使用ML使用在第一阶段学到的图表的嵌入来解决CO问题。第一阶段的作品可以分为两个类别：图嵌入方法（GE）方法和端到端（E2E）学习方法。对于GE方法，学习图嵌入具有自己的目标，这可能不依赖要解决的CO问题。 CO问题通过独立的下游任务解决。对于E2E学习方法，图形嵌入的学习没有其自己的目标，并且是解决CO问题的学习过程的中间步骤。第二阶段的作品还可以分为两类，非自动回旋方法和自回归方法。非自动回归方法一次预测CO问题的解决方案。一种非入学方法预测了一个矩阵，该矩阵表示每个节点/边缘的概率是CO问题解决方案的一部分。该解决方案可以从矩阵中计算。自回旋方法迭代地逐步扩展部分解决方案。在每个步骤中，一种自回旋方法都预测了一个节点/边缘，该节点/边缘适用于当前部分解决方案，该解决方案用于其扩展。在这项调查中，我们对基于图学习的CO方法的最新研究提供了详尽的概述。调查以未来研究方向的几篇评论结束。
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.
