综述| 当图神经网络遇上强化学习

图神经网络和强化学习都是机器学习中研究的主流模型，如何结合GNN和RL，是一个有趣的问题。最近来自美国堪萨斯州立大学发布了《基于图神经网络的强化学习》综述，阐述相关算法与应用。

深度强化学习(DRL)已经增强了各种人工智能领域的能力，包括模式识别、机器人、推荐系统和游戏。类似地，图神经网络(GNN)也证明了它们在对图结构数据进行监督学习方面的卓越性能。近年来，GNN与DRL在图形结构环境中的融合引起了广泛关注。本文对这些混合工作进行了全面的综述。这些工作可以分为两类: (1)算法增强，其中DRL和GNN相辅相成，发挥更好的效用;(2)特定于应用的增强，其中DRL和GNN相互支持。这种融合有效地解决了工程和生命科学中的各种复杂问题。在此基础上，我们进一步分析了融合这两个域的适用性和好处，特别是在提高通用性和降低计算复杂度方面。最后，强调了整合DRL和GNN的关键挑战，以及潜在的未来研究方向，这将是更广泛的机器学习社区的兴趣。

近年来，深度学习的体系结构、算法和框架得到了爆炸式的发展，用于解决计算机视觉、建模和控制等一系列具有挑战性的现实问题。在这些发展中，使用深度神经网络(DNN)在强化学习(RL)框架内解决顺序决策问题，导致深度强化学习(DRL)被认为是人工智能[1](§II)中最先进的框架之一。该方法应用于组合优化[2]、游戏[3]、机器人[4]、自然语言处理[5]和计算机视觉[6]。DRL在这些应用中的巨大成功可以归功于(1)以一种计算高效、可伸缩和灵活的方式处理复杂问题的能力，这在其他情况下是数值棘手的[7];(2)计算效率高，能够快速生成高保真度解决方案，这在需要实时决策[8]的高动态环境中至关重要;(3)理解环境动力学的能力，并仅基于与环境的交互产生接近最优的行动，而不需要明确的基础系统[9]，[10]的先验知识。

虽然DRL的有效性在游戏中得到了最广泛的证明，但它正在迅速地应用于其他各种现实应用中。其中一些应用程序涉及到显示可以用图形表示的显式结构关系的环境。例如，旅行商问题(TSP)中的城市网络或不完整的知识图谱本质上具有基于图的不同实体排列的特征。在欧几里得空间中处理数据的方法并不适合这种环境，需要在编码节点或聚合来自不同代理的信息方面进行特殊处理。这些方面用图神经网络(GNN)系统建模，详见§II。这种结构关系的融入是一种辅助输入，进一步提高了解决方案的质量。最近，研究人员一直在探索将强大的GNN模型与DRL融合的优势，以有效地解决这类图结构应用。这些混合工作的彻底调研可能是极其有益的，在识别挑战和确定未来的研究方向。此外，一些与DRL相关的综述作品也在[2]、[5]-[15]不断发表。然而，这些综述存在两个主要缺陷: (1)这些调研的大多数是通过特定应用领域的视角进行的。因此，他们被局限于特定的方法，忽视了跨领域的整体视角;(2)据我们所知，目前的文献中还没有关于DRL和GNN联合研究的全面综述。

深度强化学习与图神经网络的融合

本文对DRL和GNN融合的相关文献进行了系统综述，主要贡献如下:

• 对涉及DRL和GNN的横跨理论发展(§III-A)和多个应用领域(§III-B)的文献进行了严格的综述。

• 对综合DRL-GNN的理论和应用贡献进行了分类(§III)。为此，对现有作品进行分类和分析的各种属性被确定(§IV)。

• 该调研采取了一个整体的方法来回顾文献，特别关注算法的关键方面，如计算效率，可扩展性，通用性和适用性。

• DRL和GNN仍处于发展的早期阶段，两者融合的研究也处于早期阶段。因此，对相关挑战进行了彻底的调研究，并确定了未来的研究方向(§V)。

DRL和GNN已经成为现代深度学习中极其强大的工具。DRL利用DNN的表达能力来解决RL的顺序决策问题，而GNN是一种新颖的体系结构，特别适合处理图结构数据。我们确定了两大类联合使用GNN和DRL的研究文章，如图2所示。第一类文章利用GNN(或DRL)对DRL(或GNN)的应用进行算法和方法上的改进。另一方面，第二类文章同时使用DRL和GNN来解决不同应用领域的实际问题。表一描述了调研DRL和GNN融合工程的概况，表二概述了调研论文的个别组成部分。

A.算法发展

在本节中，我们将讨论着重于开发改进DRL或GNN的新公式或算法的文章。在这些文章中，要么使用GNN来改进DRL的配方和性能，要么使用DRL来提高GNN的适用性。

1) DRL增强GNN:

利用DRL改进GNN的工作被用于不同的目的，包括神经体系结构搜索(NAS)，提高GNN预测的可解释性和为GNN设计对抗样本。

神经体系结构搜索(NAS): 指自动搜索神经网络的最优体系结构的过程。层数，层中的节点数等)来解决一个特定的任务。[24]采用一种基于DRL的控制器，采用探索引导和保守利用的方法，对不同的GNN架构进行高效搜索。搜索空间由隐藏维度、注意力头、注意力、聚合、组合和激活函数组成。作者将模型同质化作为一种方法，在子代和祖先体系结构之间执行引导参数共享。与现有的架构搜索方法[25]相比，该方法在基准数据集上具有更好的性能。

解释GNN预测: 为DNN预测生成解释是提高ML模型透明度的一项重要任务。Shan等人[26]使用DRL来改进现有的解释GNN预测的方法。为GNN预测生成解释的问题涉及识别对生成预测影响最大的子图。作者设计了一个基于DRL的迭代图生成器，它从种子节点(预测的最重要节点)开始，并添加边来生成解释子图。DRL模型仅基于解释性子图，利用预测的相互信息和预测的分布来学习具有策略梯度的子图生成策略。作者表明，该方法在生成的子图和基础真理解释之间的定性和定量相似性方面获得了更好的可解释性。

2) GNN增强DRL:

本小节讨论与DRL算法改进相关的论文。具体而言，我们着重研究了GNN在关系型DRL问题(RDRL)中的应用，以有效地建模(1)多智能体深度强化学习(MADRL)框架中的不同智能体之间的关系，以及(2)多任务深度强化学习(MTDRL)框架中的不同任务之间的关系。

在MADRL中，agent之间的关系建模: 在MADRL中，一群agent为了实现一个共同的目标而相互合作或竞争。该框架最近被用于许多具有挑战性的任务，包括交通灯控制、自动驾驶和网络数据包传输[32]-[34]。在这种情况下，代理之间的通信提供关于其他代理的环境和状态的附加信息。人们提出了几种学习这种交流的方法。捕捉这些关系的第一个工作主体与基于注意力的方法[35]-[38]有关。ATOC[39]、DGN[40]和COMA-GAT[36]通过注意力机制提供通信。

在MTDRL中对任务之间的关系进行建模:该框架提供了一种优雅的方法来利用多个任务之间的共性，以便学习具有更高回报、泛化、数据效率和健壮性的策略。在大多数MTDRL工作中，一个固有的假设是相容的状态-动作空间，即跨多个任务的相同维度的状态和动作。然而，这在许多实际应用中被违背，如组合优化和机器人。这个问题已经通过使用能够处理任意大小的图的GNN得到了解决，从而在不兼容的状态-动作环境[46]中支持MTDRL。由于GNN提供了合并结构信息的灵活性，它允许集成额外的领域知识，其中状态被标记为图。GNN在MTDRL中的使用已经在连续控制环境中得到证实，利用RL代理的物理形态来构建输入图[47]，[48]。

RDRL的关系符号输入:RDRL的基本前提是将DRL与关系学习或归纳逻辑编程[49]集成，其中状态、动作和策略用一阶/关系语言[50]表示。该空间中的任务具有变化的状态空间和动作空间的特点。在这些问题中，很难找到大多数现有DRL方法所需要的固定长度的表示。这个问题可以使用GNN来处理，方法是根据图形结构数据制定关系问题。关系域的机制通常由关系动态影响图语言(RDDL)[51]表示。

B .应用

第二大类论文利用DRL的多功能性和GNN的灵活编码能力来解决不同应用领域的有趣挑战。这些领域涵盖了广泛的范围，包括组合优化、运输、控制、知识图谱和生命科学，我们将在接下来简要回顾。

1) 组合优化(CO):

许多CO问题的计算是昂贵的，需要近似和启发式来解决多项式时间。人们对使用机器学习技术解决CO问题越来越感兴趣。在这方面，CO问题通常被定义为MDP，其中最优行动/解决方案可以通过DRL学习到。此外，底层环境表示为使用GNN处理的图。

2) 交通: 用DRL和GNN处理的运输问题大致可以分为路由和速度预测两类。

3) 制造与控制:由于过程和系统级之间日益增加的复杂性和相互依赖性，DRL也在现代制造系统中得到了探索[73]-[75]。

4) 知识图谱补全 :在推荐系统[93]、社交网络[94]、问答系统[95]、智能制造[96]、信息抽取[97]、语义解析[98]和命名实体消歧[99]等各种应用中，知识图谱(Knowledge Graphs, KG)被越来越多地用于表示异构的图结构数据。现实世界知识库的一个关键问题是，它们是不完整，也就是说，很多关系都缺失了。知识图谱(KGC)补全。是一个知识库完成过程，旨在通过推断缺失的条目与现有的帮助下，填补不完整的现实世界的知识库。

5)生命科学: 除了工程应用之外，ML最近的进展也展示了它在各种生命科学应用方面的革命性潜力，如药物发现[101]-[103]和脑网络分析[104]。为此，[101]提出了一种设计将DRL耦合到深度生成模型的抗病毒候选药物的新方法。