论文名称：Reinforcement learning on graphs: A survey

作者：Nie Mingshuo, Chen Dongming, Wang Dongqi

时间：2022-4

出处：arxiv

代码：https://github.com/neunms/Reinforcement-Learning-on-Graph-A-Survey

摘要

图挖掘任务已经应用到许多领域中，比如社交网络，交通和电子商务等。这里有一些开创性的工作来，使用强化学习的技术来解决图数据挖掘任务。由于这些任务使用在不同领域中，这使得这些方法的比较存在一定的困难，在本文中，提供一个覆盖全局的视角来看RL和图挖掘方法，归纳这些图强化学习(GRL)为一个统一的公式。在本文中讨论了GRL方法的应用，简要描述，开源代码，基准数据集。并提出了在未来一些重要的方向和挑战。

介绍

RL的高速发展使得其被应用到多个跨学科领域中，近年来，学者们也开始考虑将RL域图挖掘进行结合，这激发了在使用有力的RL方法解决图挖掘任务中的决策问题上的兴趣。我们可以通过下图看到在2017~2022年发表的GRL文章数量：

image-20220904100932377

学者们使用RL的方法分析图数据主要有以下挑战：

  1. 计算机视觉和自然语言处理中常用的机器学习模型有效地捕获了欧几里得数据的隐藏模式（如图像和语音），但由于数据的复杂性，这些模型不能直接用于图形数据。
  2. RL方法很难准确地建立环境或状态空间，并为特定的图形挖掘任务设计动作空间或奖励函数。
  3. 图形挖掘任务的具体目标需要RL方法来为适应图形数据的特定目标设计有效的体系结构。
  4. 大规模图数据的出现给RL方法带来了限制。历史数据驱动的RL方法需要不断地从环境中学习来更新参数，而数据规模的增加则导致了RL方法的效率低下。
  5. 现实世界中的许多跨学科数据都可以建模为图结构，而跨学科数据分析结合领域知识将导致模型的扩展性和复杂性，这给RL方法的设计带来了很大的困难。

现有使用RL进行图数据挖掘的方法可以分成两类

  1. 通过利用图结构来解决RL问题
  2. 通过RL方法来解决图挖掘任务

将GRL定义为通过使用RL方法分析关键组件(图中的节点，连接和子图)实现对图的拓扑结构和属性信息的探索的解决方案和度量。GRL在许多领域取得成功的原因在于：

  1. 泛化性和适应性，RL任务直接把图挖掘任务当成MDP，而不需要考虑网络结构的有效性
  2. 数据驱动和有效性，现有图数据挖掘方法依赖大量的先验知识，而RL方法在没有先验知识的情况也能够快速学习。

本文的主要贡献：

  1. 对图数据的现代GRL方法进行了系统和全面的概述，并根据RL方法的研究领域和特点对这些方法进行了分类，重点是解决RL上的图数据挖掘问题。
  2. 提供了最近关于GRL的工作和实际应用的调查。通过进行调查，希望为图挖掘和RL社区提供一个有用的资源和全局视角。
  3. 讨论了在自动化RL、层次RL、多智能体RL、子图模式挖掘、可解释性和评估度量等方面的六个可能的未来方向。
  4. 在GRL上收集了大量的资源，包括最先进的模型、基准数据集和开放源代码。为GRL创建了一个开源存储库，其中包含了近年来大量关于GRL的论文。在这个开源存储库中，提供了论文和代码的链接（可选），让学者能够更快地概述研究内容和方法，并为GRL的研究提供更多的灵感。

基础知识

图神经网络：用于建模和计算图数据，其主要是用于聚合节点之间的关系信息，从而完成预测关系的任务。他在每一层的聚合计算可以用下面的式子表示：

公式1：Xi+1=σ(D−12A^D−12XiWi)公式1：X_{i+1} = \sigma(D^{-\frac 12}\hat{A}D^{-\frac 12}X_iW_i)

其中XiX_i是当前层的特征，第0层就直接使用原始节点的特征，WiW_i是要学习的参数矩阵，A^=A+I\hat{A}=A+I，D是对A^\hat{A}归一化后得到的对角度矩阵。其主要由三个步骤构成：初始化，邻居检测，信息聚合。

网络表征学习：将节点映射成低维的embedding，并通过embedding完成下游任务（链接预测，节点分类，图聚类）。基于网络表示学习的图挖掘方法避免了直接应用原始网络结构导致的信息缺失问题。其主要有三个条件：低维，具有信息性，连续性。

强化学习：RL可以描述成一个MDP(马尔科夫决策过程)，其是一个序列决策的数学模型，在这个模型中每一个动作会影响到短期收益，子序列状态，未来收益。MDP可以被定义为一个六元组{S,A,T,R,p(s0),γ}\{\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R},p(s_0),\gamma\}，其中S\mathcal{S}表示所有的状态集合(概括环境情况)，A\mathcal{A}表示动作集合，其可以根据状态进行适应，也是智能体所有动作的可能性。R:S×A×S→R\mathcal{R}:\mathcal{S}\times\mathcal{A}\times{S}\rightarrow \mathcal{R}表示奖励函数，表示环境在智能体做出决策之后得到的奖励。T:S×A→p(S)\mathcal{T}:\mathcal{S}\times\mathcal{A}\rightarrow p(S)由状态事物函数识别，p(s0)p(s_0)表示的是初始状态，γ∈[0,1]\gamma\in[0,1]表示折扣因子，可以看做智能体的一个超参数，可以帮助智能体更快得获取短期奖励。智能体和环境之间的交互可以使用下面的图表示：

image-20220904194917705

强化学习的目标是找出使得期望回馈Q(s,a)Q(s,a)最大化的策略函数π\pi，目标策略可以定义为如下公式

公式2：π∗=arg⁡max⁡πQ(s,a)=arg⁡max⁡πEπ,T[∑k=0Kγkrt+k∣st=s,at=a]公式2：\begin{aligned} \pi^* &=\arg \max _\pi Q(s, a) \\ &=\arg \max _\pi E_{\pi, \mathbb{T}}\left[\sum_{k=0}^K \gamma^k r_{t+k} \mid s_t=s, a_t=a\right] \end{aligned}

根据智能体对环境的可访问性可以分为Model-base和Model-free两类。model-base算法通常需要首先构建状态表示(由模型进行预测)，这使得model-base的方法通常会受到智能体无法有效建模真实环境的影响。所以GRL的大部分算法都是model-free的。

通常用于图数据挖掘的RL方法如下

  1. Q-learning：其是一个off-policy（与on-policy的区别在于前者的模型是自己去学，而后者，是根据其他模型的数据进行学习）和TD（时间差异）的方法，其目标策略是直接更新在Q-table中的值。在Q-learning中需要学习动作价值函数，Q-learning的目标是通过直接逼近最优动作价值函数q∗q^*，其可以用下面的公式进行表示：

    公式3：Q(st,at)←Q(st,at)+α[Rt+1+γmax⁡aQ(st+1,a)−Q(st,at)]公式3：Q\left(s_t, a_t\right) \leftarrow Q\left(s_t, a_t\right)+\alpha\left[R_{t+1}+\gamma \max _a Q\left(s_{t+1}, a\right)-Q\left(s_t, a_t\right)\right]

    等式表示在第t步中，状态sts_t使用基于Q-table值的行为策略探索环境，其执行动作aa，基于环境的回馈得到一个奖励RR，和一个新状态st+1s_{t+1}，然后执行上面的公式实现Q-table的更新。

  2. REINFORCE：其利用估计返回和完成的轨迹使用蒙特卡洛方法学习策略参数。这个方法创建了一个神经网络作为策略，使用状态作为输入，生成可操作的空间的概率分布作为输出。其目标是最大化期望奖励。这个折扣奖励被定义为智能体在未来得到的奖励总和。策略π\pi有参数θ\theta所以记为π(s;θ)=π(s)\pi(s;\theta)=\pi(s)，其是当前状态的动作概率分布，其更新公式为：

    公式4：Δωi,j=αi,j(r−bi,j)ϑϑωi,jln⁡gi公式4：\Delta \omega_{i, j}=\alpha_{i, j}\left(r-b_{i, j}\right) \frac{\vartheta}{\vartheta \omega_{i, j}} \ln g_i

    其中ai,ja_{i, j}是非负学习因子，rr表示折扣奖励，bi,jb_{i, j}是状态的表示函数，用于减少梯度估计的方差。bi,jb_{i, j}能够有效提高提高算法的收敛速度，gig_i是随机生成基于单元激活的动作的概率密度函数

  3. Actor-Critic：其采用参数化策略和价值函数为策略梯度的计算提供了更好A^(s,a)\hat{A}(s,a)估计。Actor-Critic学习策略和价值函数，结合基于价值函数和基于策略梯度算法的优点。Actor是策略模型，其可以得到每个动作的可能性，Critic表示评估价值函数，用于评价当前策略模型的价值。其结构可以使用下面的图表示：

    image-20220904204743844

  4. Deep Q-network：其通过函数近似和状态/动作空间缩减，将值函数近似和神经网络相结合。其结合深度学习的Q-learning和使用深度神经网络近似动作价值函数，并从智能体与环境的交互中获得轨迹{st,at,rt,st+1}\{s_t,a_t,r_t,s_{t+1}\}。这个方法的损失函数可以用下面的公式表示：

    公式5：L(θt)=E[(r+γmax⁡a+1Qθt−1(st+1,at+1)−Qθt(st,at))2]公式5：L\left(\theta_t\right)=\mathbb{E}\left[\left(r+\gamma \max _{a+1} Q_{\theta_{t-1}}\left(s_{t+1}, a_{t+1}\right)-Q_{\theta_t}\left(s_t, a_t\right)\right)^2\right]

    DQN通过重用过去的经验和定期更新独立的目标网络来保证训练过程的稳定性。

数据集以及开源情况

节点分类相关:

image-20220905143253719

图分类相关：

image-20220905143439875

节点分类常见算法的表现：（指标ACC）

image-20220905143626755

知识图谱任务的常见算法表现：

image-20220905143746176

使用强化学习进行图挖掘

网络表征学习

网络表征学习是将图中的节点映射到一个低维的向量中，同时编码各种结构和语义信息。其目的是优化节点表征，以便于嵌入空间的几何关系保持原始图的结构。现有的方法主要存在三个挑战：

  1. 特征辨识度低：融合所有特征和关系得到的全局图表示使得图的特征难以区分。
  2. 对先验知识有要求：以相似性度量或motifs的形式保存结构特征总是基于启发式，并需要大量的先验知识。
  3. 可解释性低：使用逐步池化的方法丢失了大量详细的结构信息，导致下游任务缺乏足够的可解释性。

为了解决这三个挑战，SUGAR通过自适应地选择重要的子图来保存来自“Node-Subgraph-Graphs”层次的结构信息，这种分层学习方法提供了强大的表示、泛化和可解释性。其结构图如下：

image-20220905145111703

多跳的信息传递机制在多个模块中的信息传递效率较差，于是学者们提出了Batch sampling 和importance sampling，但这些sampling的方法造成了信息损失。下面有一些新颖的方式来替换消息传递机制：

  1. Policy-GNN定义meta-policy模块和GNN模块，用于学习节点属性和聚合迭代之间的关系和网络表征。meta-policy用于选择当前节点和邻居的跳数，并通过使用选择出的跳数聚合的信息训练GNN模块。利用DQN算法解决了确定大规模网络中节点聚集范围的挑战，并提出了参数共享和Buffer机制，来提高模型的训练效率。
  2. 研究了模块化RL方法，设计了一个没有形态信息的转化模型，有效地编码了图中的关系，从而解决了多跳信息传递机制的挑战
  3. 将A3C与GCN相结合的新型虚拟网络自动嵌入算法，利用GCN在学习智能体中自动提取不规则图拓扑结构中的空间特征。
  4. 通过加强图间和图内聚合来实现多视图图表征学习，并利用RL方法进行传播更新，以确定最优滤波阈值。
  5. ACE-HGNN利用多智能体RL方法来学习网络的最优曲率，以提高模型的质量和通用性。

现有的基于GNN的表征学习方法及其变种依赖邻居信息聚合，这使得这个模型容易受到图中噪声的影响，于是有下面的方法来解决这个问题

  1. GDPNet采用两个阶段的signal neighbor selection和representation learning去除噪声邻居作为MDP，优化每个目标节点的邻居，从representation learning阶段中利用特定任务的奖励学习策略。允许模型仅在来自特定任务的奖励信号的弱监督下执行图去噪。
  2. GAM能够通过attention-guided walks将模型的学习注意力限制在小但有信息的部分。图注意力模型采用部分观察马尔科夫抉择过程(POMDP)方法进行训练，有选择地处理图中的信息部分。
  3. NetRL通过检测噪声链路和预测缺失链路进行网络增强，以提高网络分析和建模能力。

GNN模型的轻微改动将会显著地影响模型的性能，因此需要足够的邻域知识指导框架的设计原则。比如隐藏层的维度，聚合函数，目标分类器的参数。

  1. GraphNAS设计一个包含采样函数、聚合函数和门控函数的搜索空间，并使用RL搜索图神经结构。该算法首先使用一个递归网络来生成描述gnn体系结构的可变长度字符串。
  2. AGNN通过基于RL的控制，验证预定义搜索空间中的体系结构，将搜索空间分解为以下六类动作：隐藏层的维度、注意力函数、注意力头、聚合函数、组合函数和激活函数。
  3. GQNAS捕获网络层内的结构相关性，以解决使用DQN和GNN的神经结构搜索。

然而上面的方法没有考虑到聚合节点中的邻居异构性，忽视或简化了真实网络中节点和边的不同关系，导致异构信息损失。异构信息网络包含多种类型的节点和关系，节点之间保持着丰富而复杂的相互依赖关系，在实际网络和实际应用中得到了广泛的应用。

  1. 提出一种RL增强的异构GNN模型，为异构信息网络中的节点设计不同的元路径，用智能体代替手工设计的元路径，解决了对手工制作的元路径的依赖问题。除了改进元路径的设计解决方案外，还采用新的邻域聚合技术能够有效地提高异构网络表征学习的性能。
  2. 提出了一种基于多关系图的任务驱动GNN框架，该框架使用半监督方法学习多关系节点表示，该方法利用关系采样、消息传递、度量学习和RL来指导不同关系内部和不同关系之间的邻居选择。
  3. 用于社交网络建模任务的FinEvent允许通过将社交信息建模为异构图来传输跨语言的社交事件检测。

图数据的增强进一步提高了网络表示学习的性能，学者们认为学习机制的不变性对数据的增强至关重要。

  1. GraphAug能够使用自动增强模型，基于计算图的标签不变性，避免损害图的关键标签相关信息，从而在大多数情况下产生标签不变性。他们提出了一种基于RL的训练方法来最大化估计的标签不变概率。

  2. GPA研究了如何利用主动学习方法有效地标记gnn中的节点，从而降低了使用主动学习方法训练gnn的标注成本。其结构如下图所示：

    image-20220905161133917

更多基于GRL的网络表征学习方法如下表：

Method Action State Reward Transition RL Metrics
SUGAR 从k中添加或减去一个固定的值∆k∈[0,1] 中间的图由在每一轮训练中选择的子图组成 根据上一轮的分类精度，定义相应的奖励值 10个连续周期中k的变化不大于∆k Q-learning 平均精度、标准偏差、训练过程、测试性能和结果可视化。
RL-HGNN 元路径中涉及的所有节点 可用的关系类型的集合 与历史性能相比，特定任务的性能提高 - DQN Micro-F1，Macro-F1，以及元路径设计的耗时性。
Policy-GNN 当前节点的属性 当前节点的跳数 根据最后一个状态的特定任务的性能改进 - DQN 准确率
RioGNN 当关系r在第l层的深度d时的所有动作 每个epoch的平均节点距离 相似性是奖励函数中的决定性因素 只要相同的动作在当前精度下连续出现三次，RL将被终止 MDP 准确率
GraphNAS 为图形神经网络架构选择指定的参数 图的神经网络架构 根据特殊任务的准确性，定义相应的奖励值 以最大化生成的架构的预期精度 MDP Micro-F1和准确率
GPA 这些动作是根据策略网络给出的动作概率来定义的 节点的状态表示是根据主动学习中常用的几种启发式准则来定义的 收敛后的分类GNN在验证集上的性能得分 分类器的性能收敛性 MDP Micro-F1和准确率
GDPNet 选择邻居 有关当前节点及其邻居的信息的embedding 根据特殊任务的准确性，定义相应的奖励值 - MDP 准确率

对抗性攻击

GNN通过节点的属性和边的连接情况进行训练，而攻击器就可以对这些用于训练的图数据进行修改达到攻击GNN模型的目的，降低GNN模型的性能。

  1. RL-S2V学习如何通过使用下游任务的反馈添加或删除图的链接来修改图结构。

image-20220906092329050

  1. Q-learning算法作为一个用于网络结构顺序修改的RL模块的实现解决方案。算法使用structure2vec的方式训练图结构得到每个节点的表示，然后用图神经网络对每个节点进行参数化，得到Q值，通过Q-learning得到需要修改的候选链路，实现黑盒攻击。

然而这种需要频繁修改网络结构的攻击方式需要高度的复杂性来避免攻击被抵抗。

  1. 提出了NIPA方法来破坏图，在不改变图中现有节点之间的链接结构的情况下，增加GNN的节点误分类率。NIPA方法将假节点注入图中，而不是操作现有节点之间的链接。该算法将注入的假节点的对抗连接和对抗标签表示为MDP，并设计了一个适当的奖励函数来指导RL智能体降低GNN的节点分类性能。

对抗攻击GRL的方法具体内容如下表：

Method Action State Reward Transition RL Metrics
NIPA 在注入节点与干净节点之间添加注入节点内的对抗边，设计注入节点的对抗标签 注入节点的中间poisoned图和标签信息 基于分类器成功率的指导奖励 智能体会添加预算边数 DQN 准确性、poisoned关键统计量、注入节点的平均度和原始图的稀疏性。
RL-S2V 添加或删除图形中的边 修改后的图形 目标分类器的预测置信度 智能体将修改指定数量的链接 Q-learning 准确性
CARE-GNN 正负于一个固定的小值 邻居节点的选择范围 两个连续时期之间的平均距离差 RL在最近的十个时期收敛，并在GNN收敛前的最优阈值 BMAB ROC-AUC和召回率
ReWatt 操作空间包含所有有效的 rewiring操作 环境的状态空间由在所有可能的rewiring操作后生成的所有中间图组成 奖励函数是基于分类器的性能而开发的 当操作数达到预算K或攻击者成功地更改了轻微修改的图的标签时，攻击过程将停止 MDP 攻击性能

Relational Reasoning

发现和理解因果关系(causal relation)机制，可以定义为寻找最小的有向无环图(DAG)使得定义的score function最小。RL方法可以很好地探索这种因果关系，但是但搜索DGA空间和发现隐含条件通常具有很高的复杂度。随机策略的RL方法中的智能体能够根据学习策略的不确定信息自动定义搜索策略，并可以通过奖励快速更新。

  1. 利用RL从图空间中找到底层的DAG，而不需要平滑的score function。该算法采用actor-critic作为搜索算法，输出在训练过程中生成的所有图中获得最佳回报的图。然而，该方法出现了计算score较差的问题，而由有向图组成的动作空间通常难以完全探索。
  2. CORL将RL方法合并到基于排序的范例中。该方法将排序搜索问题描述为一个多步骤的MDP，并利用Econder-Decoder构实现了排序生成过程，最后基于针对每个排序设计的奖励机制，用RL对所提出的模型进行了优化。然后使用变量选择来处理生成的排序，得到最终的因果图。
  3. 结合了迁移学习和RL来进行协同学习，以利用先验的因果知识来解决因果推理任务。

面向任务的口语对话系统(SDS)是一个可以持续地与人进行交互以完成一个预定义的任务的系统。

  1. 设计一种替代但互补的方法来创新神经网络的结构，结合DQN算法，使其更适应对话策略。学者们提出了一些自然的问题生成模型，为问答任务提供更多的训练数据，以进一步提高任务的性能。
  2. 针对自然问题的生成，提出了一种基于RL的Graph2Seq模型，该算法采用自临界序列训练(SCST)算法来直接优化评价度量。通过交互式对话显式获取用户推荐项和属性的偏好是会话推荐系统的目标。
  3. 利用图形结构，将推荐和对话组件作为一个整体集成起来。该算法利用一个动态加权图来建模对话过程中用户、项目和属性之间不断变化的相互关系，并考虑一个基于图的MDP环境来同时处理这些关系。

随着人工智能的发展，知识图已经成为许多下游现实应用的数据基础设施，并已达到多样化
对话系统和知识推理的应用

  1. 提出了一种基于策略的智能体，通过RL方法依次扩展其推理路径。
  2. MINERVA利用RL方法对多跳知识图上回答问题的端到端模型进行实际任务训练。然而，这些专注于固定的多跳或单跳推理的方法消耗了大量的计算资源，而手工收集的数据的不完全性影响了推理的性能。
  3. 建立具有动态奖励的端到端动态知识图推理框架，该方法将动作embedding和搜索历史作为策略网络集成到前馈神经网络中进行动态路径推理。
  4. 提出了一个基于时间路径的RL模型来解决时间知识图的推理任务，并设计了一个基于时间的奖励函数来指导模型的学习。
  5. AttnPath是一个基于路径的框架，解决了知识图推理中缺乏记忆模块和过度依赖算法预训练的问题，该算法结合了长短期记忆(LSTM)和图注意网络(GAT)，设计了一种能够迫使智能体移动的RL机制。
  6. RLPath在关系路径搜索中同时考虑了关系选择和实体选择。

为了解决知识不完全图的问题，学者们通常采用多跳推理来推断缺失的知识。

  1. 提出了一种分层RL方法来模拟人类思维模式，其中整个推理过程分解为两步RL策略。采用策略梯度方法和REINFORCE，选择两种策略来编码历史信息和学习一个结构化的行动空间。
  2. 基于RL的知识图的层次推理的DeepPath需要手动规则来处理，以获得更充分的层次关系。
  3. PAAR采用基于双曲知识图嵌入和RL的多跳推理模型进行层次推理

推荐系统通过向用户提供更好的项目或信息，对各种在线应用程序至关重要，如电子商务网站和社交媒体平台。交互式推荐系统因其灵活的推荐策略和最佳的长期用户体验而受到广泛关注，学者们已将DQN和DDPG等DRL模型引入IRS，用于动态环境下的决策和长期规划。

  1. KGQR能够将图学习和顺序决策问题整合到交互推荐系统中，利用先验知识从用户反馈中选择候选对象和学习用户偏好，并通过聚合知识图中实体之间的语义相关性来提高RL的性能。

    image-20220906100123521

GRL在现实世界的应用

解释性

在探索GNN时，学者们经常将它们视为黑盒子，而这一假设缺乏人类容易理解的解释，这阻碍了它们在涉及药物、隐私和安全的关键应用中的应用。许多研究这种GNN黑盒模型的可解释性的学者通常专注于解释图数据中节点、边或节点特征级的可解释性，而忽略了GNN模型和频繁子图。在子图级的解释使其能够更直观和有效地描述GNN。将现有的GNN可解释方法分为实例级方法和模型级方法，以促进对GNN的理解。

在基于子图的GNN可解释性的研究中

  1. SubgraphX提出采用蒙特卡洛树搜索方法来探索关键子图，从而从子图级解释GNN的预测问题，结构如下图：

image-20220906100925679

  1. RioGNN学习不同关系之间的重要性的差异获得区别的节点embedding，这种措施的向量表示节点可以提高节点embedding的质量同时提高模型的可解释性和实现多关系GNN从个人的角度不同关系的重要性。

  2. 设计子图和节点级特性，以支持理解攻击策略和检测器漏洞。

  3. 通过优化多目标分数来获得扰动策略，以实现对图数据的局部解释。

此外，学者们认为，从模型层面解释GNN可以增强人类对某些应用领域的信任。XGNN通过将图生成构造为RL来解释GNN，生成的图结构能够验证、理解和改进训练过的GNN模型。

城市服务

随着现代城市的快速发展，城市人口的快速增长造成了交通拥堵、交通效率低下等诸多问题。交通网络和通信网用复杂的网络方法对产生的问题进行分析，引起了众多学者的关注。将道路网和通信网络建模为图数据，由于其结构化属性，保留了更丰富的信息，并协助相关政府机构或电信服务提供商更好地优化交通道路或通信链路，从而缓解交通拥堵问题，为市民提供更好的通信服务。

交通流量预测的重点是根据特定道路区域内或区域间的交通流量统计信息和相关政府机构或组织提供的交通数据，建立一些预测模型来估计特定道路的交通流量。

  1. 利用GCPN对现有的交通流图进行建模，利用LSTM提取时间特征，解决了大多数交通流数据的不完全性和非时间性问题
  2. 动态交通网络的IG-RL主要研究交通信号控制问题，利用GCN学习实体作为节点embedding，并采用Q-learning算法对模型进行训练。这种方法能够以适当的方式表示和利用交通需求和路网结构，而不管实体的数量和它们在路网中的位置如何。

电子收费(ETC)系统在缓解城市交通拥堵问题方面具有重要作用。

  1. 采用GCN表示动态电子收费(Dynamic Electronic Toll Collection, DETC)问题中的价值函数和策略函数，并采用协同多智能体RL算法解决动态电子收费问题。

此外，优化按需拼车服务、互联自动驾驶车辆的变道决策、自适应交通信号控制也可以提高城市交通流的运营效率。

学者们提出了一种多智能协作的图卷积模型，以获得有效的协作策略，以改进分组交换网络的路由。

  1. DRL+GNN架构能够在任意网络拓扑上进行学习和推广，并在基于SDN的光传输网络场景中进行了评估。
  2. 一种基于DRL的信道分配方案。该算法采用图卷积层来提取具有拓扑信息的信道向量的特征，并学习DDQN，用于信道分配策略的制定。

流行病控制

在疫情遏制、产品营销和假新闻检测等领域，学者们采用了有限数量的干预措施来部分控制图上观察到的动态过程。

  1. 提出了一种整合宏观和微观信息的全尺度扩散预测模型来求解信息扩散预测。
  2. 提出了一种RL方法，通过有限数量的干预措施来控制图上部分观察到的动态过程，并成功地应用于遏制流行病的传播。
  3. RAI算法利用社交物联网(SIoT)中移动设备之间的社会关系，通过早期识别COVID-19疑似病例，将有限的保护资源分配给有影响力的个人，从而帮助控制病毒的传播

关键节点查找和网络拆除等算法可以应用于疫情控制问题。到目前为止，将GRL方法用于网络动力学的研究还很少，现有的方法仅集中在流行病控制等问题上。

组合最优化

组合优化是一个跨学科的问题，它涵盖了优化、运筹学、离散数学和计算机科学，涵盖了丰富的经典算法和许多关键的现实世界的应用。大多数真实的组合优化问题可以用图表示。组合优化的GRL方法允许自动学习基于原始输入数据和指导过程返回可行和高质量输出的策略。

  1. OpenGraphGym提出了用求解求解组合图优化问题。

  2. S2V-DQN学习通过Q-learning逐步构建解决方案的策略。其中，智能体通过添加节点，基于图结构逐步构造有效的解，该贪婪算法是一种流行的逼近算法和组合优化的启发式模式

    image-20220906102419129

  3. AS-Net可以通过模拟规划问题的关系结构，采用权值共享方案，允许将网络应用于给定规划领域中的任何问题。

许多图数据挖掘的动态版本是解决交通、社会和电信网络的一个关键研究对象，在这些网络中，现实世界中的网络结构会随着时间的推移而演变。

  1. GTA-RL是一种用于动态组合优化问题的基于图的启发式学习算法，该算法通过提出一种能够嵌入实例的时间特征编码器和一种能够聚焦于嵌入特征以找到给定组合问题实例的解码器来解决NP难问题的动态性。
  2. DeepOpt采用DRL方法解决了虚拟网络函数(VNF)中多种资源类型的放置策略问题。
  3. 基于静态和动态子图构造时空图中的最短路径查询方法，并采用近端策略优化(PPO)算法训练代理优化状态到动作策略，以解决现实任务中的路径规划问题

医学

GRL技术通常应用于临床决策支持(CDS)应用、药物组合预测(MCP)、化学反应产物预测和脑网络分析任务。

  1. 提出了一种基于MCP的图卷积RL模型来解决医学相关性和顺序问题。该方法将MCP问题表示为一种无序的MDP，并设计了一种DQN机制来学习药物之间的相关性和不良性相互作用。
  2. Graph Transformation Policy Network(GTPN)解决了化学反应产物预测的问题。它们利用图神经网络将由输入反应物和试剂分子组成的实体系统表示为具有多个连接成分的标记图，并将从反应物分子生成产物分子的过程表示为一系列图转换过程。GTPN利用A2C来寻找将反应物转化为产物的键变化的最佳序列。
  3. BN-GNN是一个脑网络表示框架，它能够通过DDQN确定特征聚合的最优数量，并将丰富的医学知识图和DRL方法相结合，可以支持患者描述疾病特征，并提供疾病诊断的准确性。

在制药行业中，新生药物的设计和发现辅助工具具有重要的研究价值，许多学者对RL方法的化学分子生成和优化进行了研究。这些方法利用RL预先设计药物的分子结构，可以显著节省化学实验室的工作时间、金钱和劳动力成本，为新药的设计和发现提供了有效的帮助。

开放研究方向

虽然目前学者们已经探索和提出了几种GRL方法，但该领域仍处于起步阶段，具有很大的探索空间和研究价值，并提出了该领域学者可能感兴趣的未来研究方向。

Automated RL：GRL方法中的环境建模、RL算法的选择和模型的超参数设计通常需要详细的专家探索。状态空间和动作空间的不同定义、批的大小和批更新的频率，以及时间步长的数量，会导致不同的实验性能。Automated RL提供了一个解决方案，可以在开始学习之前自动对RL进程的设置做出适当的决策，使非专家的方式能够执行，并改进RL的应用范围。将这种自动学习方法应用于图挖掘将显著提高GRL方法的效率，并为图挖掘算法和RL方法的最优组合提供更有效的生成解决方案。

Hierarchical RL：算法设计中的Hierarchical RL方法允许顶级策略关注于更高层次的目标，而子策略则负责细粒度的控制。学者们提出了实施基于手工制定和自动政策制定的顶层政策，以便在子政策之间进行选择。GRL的层次策略允许模型设计顶级和子级结构，以增强模型的可解释性和鲁棒性，并且使用分层数据处理策略或分层算法设计策略都可以使算法更容易理解。

Multi-agent RL：单个代理在与环境交互的过程中，通常会忽略其他代理的利益。个体主体通常将环境中的其他主体视为环境的一部分，在学习过程中无法适应不稳定的环境。Multi-agent RL考虑了多智能体之间的通信，允许它们有效地协作学习。现有的Multi-agent RL方法提出了双向通道、顺序传输和全到全通道等策略来实现代理之间的交互。

Subgraph Patterns Mining：在网络局部结构分析的过程中，许多学者探索并发现了许多新的图数据挖掘方法，这些方法利用了具有不同策略的图的局部结构。此外，他们还采用了批量抽样和重要性抽样的方法来获得网络表示学习的局部结构。图的局部结构选择为GRL提供了自然的优势。图局部结构的顺序构建可以表示为MDPs，并以下游分类和预测任务的性能为指导。这些自适应邻域选择方法可以提高GNN的性能，并在异构信息网络中分析消息传递中不同关系的重要性。

Explainability：研究图神经网络的可解释性的学者数量有限，这对于提高图神经网络模型的性能和有助于理解图神经网络模型的内在意义和潜在机制具有重要意义。

Evaluation metrics：定义RL中的奖赏功能是至关重要的。合理的奖励函数可以使RL算法更快更好地收敛，获得预期目标。然而，现有的GRL方法通常使用设计奖励函数为下游分类器或预测器的性能。这些方法允许根据下游任务的性能来评估GRL方法，但是GRL方法的执行包括多个步骤，并且使用下游任务来评估每个动作的结果会导致大量的资源消耗。虽然许多学者提出了新的方法来减少开销或设计更有效的奖励函数指导RL的训练过程，资源消耗的问题仍然存在，我们相信设计奖励功能依赖于行动或提供一个统一的GRL评估框架可以有效地提高算法的性能。这是一个需要解决的问题。