《图强化学习在组合优化中的应用》综述

图是一种自然表示方式，适用于基于连接实体之间关系的系统。当考虑与感兴趣的过程相关的目标函数时，会出现组合优化问题，这些问题通常具有挑战性，因为解决方案空间的迅速增长。强化学习的试错范式最近已经成为一种有前景的替代传统方法，如精确算法和（元）启发式算法，用于在化学、计算机科学和统计学等多种学科中发现更好的决策策略。尽管这些技术源自截然不同的领域，但它们具有显著的共性。因此，我们着手将这些工作综合在我们称之为图强化学习的统一视角中，将其解释为图问题的一种构造性决策方法。在介绍相关的技术背景后，我们回顾了这些研究工作，并沿着是否旨在优化给定过程的图结构，或在固定图结构下优化过程本身的结果这一分界线进行了评述。最后，我们讨论了该领域面临的共同挑战和开放性研究问题。与其他综述不同，本工作关注于非典型图问题，对于这些问题，通常没有已知的高效算法，而强化学习能够提供高效且有效的解决方案。

图是一个数学概念，用于形式化由关系（边）连接的实体（节点）的系统。超越原始拓扑结构，图中的节点和边常常与属性相关联：例如，一个边可以与距离度量的值相关联（Barthélemy, 2011）。通过这样的特性增强，图成为了一种强大的形式主义，能够表示各种系统。这种灵活性使得它们被广泛应用于计算机科学、生物学和社会科学等多样的领域（Newman, 2018）。这种类型的数学建模可以用来分析性地检查网络的结构和行为，构建预测模型和算法，并将它们应用于实际问题。除了描述在图上发生的过程外，一个自然的问题是如何介入网络以优化给定过程的结果。这类在离散结构上的组合优化问题通常具有挑战性，因为解决方案空间的迅速增长。一个著名的例子是旅行商问题（TSP），它要求在一个完全连通的图中找到一个哈密顿回路，使得路径长度总和最小化。

近年来，机器学习（ML）开始作为解决组合优化问题的有价值工具而兴起，研究人员预计其影响将是革命性的（Bengio et al., 2021; Cappart et al., 2021）。特别是，强化学习（RL）的范式已显示出通过试错发现能够胜过传统精确方法和（元）启发式方法的算法的潜力。一个常见的模式是将感兴趣的问题表达为一个马尔可夫决策过程（MDP），在其中，一个代理逐步构建解决方案，并根据其优化目标函数的能力获得奖励。从MDP公式开始，可以透明地应用各种RL算法，这使得这种方法在可以解决的问题类型上非常灵活。与此同时，开始出现了使用RL解决图组合优化问题的工作，涵盖了从化学（You et al., 2018a），计算机科学（Valadarsky et al., 2017），经济学（Darvariu et al., 2021b）到统计学（Zhu et al., 2020）等多种科学领域。

本综述的目标是提出一个统一框架，我们称之为图强化学习（Graph RL），用于处理图上的决策问题。我们将综合可以在这个新兴范式的背景下解释的各种方法。我们将讨论几个组合优化问题，重点是那些通常不知道有效、高性能算法的非典型问题。事实上，最近的综述关注的是应用RL解决典型问题的作品，我们使用“典型问题”这一术语来指代可能已经被研究了几十年的问题。例如，仅关于解决上述TSP的研究就可以追溯到近70年前Dantzig等人的论文（1954），并且存在非常有效的算法可以最优地（Applegate et al., 2009）或近似地（Lin & Kernighan, 1973; Helsgaun, 2000）解决多达数千万节点的实例。其他值得注意的典型问题包括最大独立集（Ahn et al., 2020）、最大割（Khalil et al., 2017; Ahn et al., 2020）以及诸如车辆路径问题（VRP）（Kool et al., 2019; Kim & Park, 2021）等路由问题。除了少数例外，尽管在这些基准问题上的工作对于推动基于ML方法的极限很重要，但目前它们还不能直接与成熟的、高度优化的启发式和精确求解器竞争。因此，本文与其他综述（Mazyavkina et al., 2021; Wang & Tang, 2021）和观点（Bengio et al., 2021; Cappart et al., 2021）相辅相成，无论是在提出统一范式还是关注非典型问题方面。

本文的其余部分如下组织。在第2节中，我们提供了关于图上的组合优化问题及其使用RL方法的相关技术背景。随后，在第3节中，我们回顾了考虑优化图结构的工作（即，从头开始创建图或修改现有图）以使目标函数最大化。然后，在第4节中，我们综述了在固定图结构下优化过程的论文。第5节讨论了在应用这些技术时面临的常见挑战，这些也可以视为未来工作中需要解决的重要研究问题，此外还总结了一些关键的应用领域。我们在第6节以图强化学习作为解决图上组合优化问题的统一范式的讨论来结束本文。

图结构优化在机器学习（ML）处理典型图组合优化问题的工作中，一个共有的特点是它们通常不涉及对图的拓扑结构进行改变。具体来说，需要在假设网络结构保持固定的情况下找到解决方案。学习构建图或修改其结构以优化给定目标函数的问题在ML文献中相对较少关注。在这一部分，我们回顾了处理修改图拓扑结构以优化感兴趣的量的问题的工作，并使用强化学习（RL）来发现实施这一过程的策略。这是通过与环境的互动来执行的。

在高层次上，这类问题可以被表述为寻找满足argmaxG∈G F(G)的图G，其中G是要搜索的可能图的集合，F如前所述，是目标函数。我们在图2中示意了这一过程。精确的框架取决于问题，并可能涉及从一个空图开始还是从一个现有的图开始选择，以及对图的有效性如空间限制、非循环性或平面性施加约束。如图3所示，动作空间的设计也可以变化。代理可能被允许进行边的添加、移除和重连，或者这些操作的某种组合。 鉴于范围的自然限制，我们只考虑那些（1）使用图表示问题；（2）通过RL训练策略进行结构优化的工作。让我们简要讨论一下相关但不在讨论范围内的一系列工作。ML文献中的几项工作考虑了生成与提供的数据集具有类似属性的图。这通常使用深度生成模型执行，并可被视为经典图生成模型的基于ML的替代方法，例如Barabási & Albert（1999）的模型。这些工作主要使用最终图（即“成品”）的示例数据集，并不使用中间的，从某种意义上说，对应于生成过程本身的步骤。它们还需要大量相关的示例集合，这些可能并不总是可用的，具体取决于领域。

在这一领域，使用自回归模型（如LSTM或GRU）的工作类似于MDP公式；例如添加边的决策可以被视为序列中的一个标记，由模型学习。这一领域的一些值得注意的工作包括Li等人（2018）提出的技术，GraphRNN（You等人，2018b），以及图重复注意网络（Liao等人，2019）。其他类型的生成模型，如变分自编码器和生成对抗网络，也被用于生成分子（Kusner等人，2017; Guimaraes等人，2018; De Cao & Kipf, 2018; Jin等人，2018）。

本节的其余部分深入回顾了相关论文，按问题家族分组。我们涵盖了旨在学习如何攻击GNN、设计网络结构、发现因果图和构建分子图的工作。考虑的论文根据其采用的技术和特点在表1中进行了总结。 在这项综述中，我们讨论了图强化学习这一新兴领域，这是一种通过试错学习来解决图上计算挑战性优化问题的方法。我们特别关注那些尚未知晓高效算法的问题，以及传统的启发式和元启发式算法通常无法提供满意性能的问题。我们将这些工作分为两类。第一类是图结构优化，包括需要找到最优图结构的问题，这在对抗性攻击图神经网络、网络设计、因果发现和分子优化等领域有显著应用。第二类是图过程优化，将图结构视为固定不变，代理在离散的可能控制行动空间中进行搜索，以优化过程的结果。这包括网络路由、游戏、传播过程和图搜索等问题。最后，我们讨论了该领域面临的主要挑战，其解决可能具有非常重大的影响。