# Challenges and Opportunities in Deep Reinforcement Learning with Graph
Neural Networks: A Comprehensive Review of Algorithms and Applications

Sai Munikoti, Student Member, IEEE, Deepesh Agarwal, Laya Das,
Mahantesh Halappanavar, Senior Member, IEEE, Balasubramaniam Natarajan, Senior
Member, IEEE S. Munikoti and M. Halappanavar are with Data Science and Machine
Intelligence group, 99354, PNNL, Richland, USA. (e-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>)D. Agarwal and B.
Natarajan are with Electrical and Computer Engineering, Kansas State
University, Manhattan, KS-66506, USA, (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>bala@ksu.edu)L. Das is with Reliability and Risk Engineering
Lab, ETH Zurich, 8092, Zurich, Switzerland. (e-mail<EMAIL_ADDRESS>)This work
has been submitted to the IEEE for possible publication. Copyright may be
transferred without notice, after which this version may no longer be
accessible.

###### Abstract

Deep reinforcement learning (DRL) has empowered a variety of artificial
intelligence fields, including pattern recognition, robotics, recommendation-
systems, and gaming. Similarly, graph neural networks (GNN) have also
demonstrated their superior performance in supervised learning for graph-
structured data. In recent times, the fusion of GNN with DRL for graph-
structured environments has attracted a lot of attention. This paper provides
a comprehensive review of these hybrid works. These works can be classified
into two categories: (1) algorithmic contributions, where DRL and GNN
complement each other with an objective of addressing each other’s
shortcomings in a theoretical setting; (2) application-specific contributions,
that leverage a combined GNN-DRL formulation to address problems specific to
different applications. This fusion effectively addresses various complex
problems in engineering and life sciences. Based on the review, we further
analyze the applicability and benefits of fusing these two domains, especially
in terms of increasing generalizability and reducing computational complexity.
Finally, the key challenges in integrating DRL and GNN, and potential future
research directions are highlighted, which will be of interest to the broader
machine learning community.

###### Index Terms:

Deep Reinforcement Learning, Graph Neural Network, Survey, Hybrid DRL-GNN,
Deep Learning.

##  I Introduction

In the recent past, deep learning has witnessed an explosive growth in terms
of development of novel architectures, algorithms and frameworks for
addressing a wide range of challenging real-life problems ranging from
computer vision to modeling to control. Among these developments, the use of
deep neural networks (DNN) for solving sequential decision making problems
within the reinforcement learning (RL) framework, resulting in deep
reinforcement learning (DRL) is considered one of the state-of-the-art
frameworks in artificial intelligence [1]. This approach finds applications in
combinatorial optimization [2], games [3], robotics [4], natural language
processing [5], and computer vision [6]. The tremendous success of DRL in
these applications can be credited to (1) the ability to tackle complex
problems in a computationally efficient, scalable and flexible manner, which
is otherwise numerically intractable [7]; (2) high computational efficiency
allowing fast generation of high fidelity solutions that are crucial in highly
dynamic environments with demand for real-time decisions [8]; (3) the ability
to understand environment dynamics and produce near-optimal actions based
solely on interactions with the environment, without the need for explicit
prior knowledge of the underlying system [9, 10].

While DRL’s effectiveness has most popularly been demonstrated in games, it is
rapidly being adopted in various other real-life applications. Several of
these applications involve environments exhibiting explicit structural
relationships that can be represented as graphs [11]. For example, a network
of cities in the Travelling Salesman Problem (TSP) or an incomplete knowledge
graph are inherently characterized by a graph-based arrangement of the
different entities. Methods developed for handling data in the Euclidean space
are not well-suited for such environments, that require special treatment in
terms of encoding the nodes or aggregating the information from different
agents. These aspects are systematically modelled with graph neural networks
(GNNs), detailed in Section II. Incorporation of such structural relationship
serves as an auxiliary input, and further improves the quality of solutions.

Recently, researchers have been exploring the idea of fusing powerful GNN
models with DRL to efficiently tackle such graph-structured applications.
Although there are several advantages of this hybrid approach, there are two
primary reasons associated with it. Firstly, DRL is rapidly being adopted in
various applications that involve environments and formulations exhibiting
structural relationships. GNNs are very effective in capturing such
relationships and thus improves the naive model performance. More importantly,
GNNs offer a computationally efficient and powerful framework for large-scale
complex DRL environments, which is not feasible with other modeling paradigms.
Secondly, there are several optimization-related tasks in GNN which can be
efficiently handled with DRL compared to any other paradigm. For instance,
tweaking graphs (by adding nodes and edges) in order to obtain robust models
against adversarial attacks. Therefore, a thorough review of these hybrid
works could be extremely beneficial in identifying challenges and determining
future research directions.
Related work: Several review works either related to DRL or GNN in general,
are continuously being published [2, 5, 6, 7, 9, 8, 10, 12, 13, 14, 15, 16,
17, 18, 19]. Most of these review articles include only a small paragraph or
section that briefly presents the combination of the two approaches. For
instance, [20] explains various type of GNN architectures and their specific
applications, but it discuss nothing about the DRL other than the fact that it
can be used to generate graphs of desirable properties. Similarly, in [21], RL
is described briefly in the context of path finding and relation extractor for
the knowledge graph in order to reason. DRL is primarily presented as a
process or algorithmic steps, and the review lacks a comprehensive
understanding of the applicability and significance of the particular DRL
formulation. In a nutshell, majority of these surveys are conducted via the
lens of a particular application domain. As a result, they are confined to
specific approaches that ignore holistic perspectives across domains. To the
best of our knowledge, comprehensive reviews dedicated to the study of the
combined potential of DRL and GNN do not exist in the current literature.
Contributions: This paper focuses on a systematic literature review of the
fusion of DRL and GNN, and makes the following contributions:

  * •

A rigorous review of articles spanning theoretical developments (Section
III-A) and multiple application domains (Section III-B) is conducted for
hybrid DRL and GNN paradigm, which is rapidly gaining momentum and proving to
be useful in several applications.

  * •

A categorization of theoretical and application-specific contributions of the
integrated DRL-GNN efforts is developed (Section III). To this end, various
attributes are identified for classifying and analyzing existing works
(Section IV).

  * •

The survey takes a holistic approach to reviewing the literature with special
focus on critical aspects of algorithms such as computational efficiency,
scalability, generalizability and applicability.

  * •

Both DRL and GNN are still in early stages of development, as is the study of
their fusion. Therefore, a thorough investigation of the associated challenges
is performed and future research directions are identified, which can advance
the state-of-the-art both in theoretical and practical aspects (Section V).

This review is limited to articles indexed in IEEE Xplore, Scopus and Google
Scholar. Initially, the keywords “deep reinforcement” and “graph neural
network” are used to select articles from databases. This search led to more
than $100$ papers from the year 2017 to 2022. The resulting list is filtered
to identify articles that include both DRL and GNN which finally led to $40$
papers. Most of the papers in this hybrid paradigm appear in a past few years,
which  indicates the relatively recent history and relevance of this trending
research topic. Among the $40$ articles, $22$ come from conferences
proceedings, $8$ from journals, and the remaining $10$ are preprint
manuscripts.

The paper is organized as follows. In (Section II), we offer a brief
methodological background of both DRL and GNN to equip readers to understand
the fundamentals prior to looking at the fusion of those techniques. (Section
III) presents a comprehensive review of existing literature, including
classification based on different novel attributes. In (Section IV), we
discuss our findings in terms of the applicability and unique offerings of an
approach involving GNNs and DRL. (Section V) highlights key limitations in the
existing literature as well as potential future directions for research.
(Section VI) concludes this study.

##  II Overview of DRL and GNN

This section begins with the definition of a graph, a mathematical model best
suited to describe networked systems, and provides the foundations of two
powerful learning paradigms namely DRL and GNN. We introduce  RL and then
present its extension with deep neural networks, i.e., DRL. Then, we briefly
explain the fundamentals of GNN algorithms.  Fig. 1 depicts these two learning
paradigms through an infinite shape loop. The left loop shows Deep
Reinforcement Learning (DRL) paradigm, and the right loop exhibit the
framework of Graph Neural Network (GNN). Through Fig. 1, we first illustrate
the contrasting view of these two frameworks in general by leveraging three
attributes, namely “Goals”, “key steps” and “Algorithms”. “Goals” primarily
represents the objectives or tasks that are typically accomplished with the
framework. “Key-steps” describe the process involve in obtaining the
algorithm. “Algorithm” highlights the widely known architectures developed
under the framework. We also marked the intersection area of two loops, where
the two paradigms come together in a fundamentally holistic way to solve
complex problem in an elegant way. This section will equip the readers with
the required background knowledge to follow the hybrid works on DRL and GNN
(discussed in (Section III).

A graph $G$ is a mathematical model for representing a networked system. It is
typically denoted via a tuple $G=(\mathcal{V},\mathcal{E})$ of a set of
$n_{V}$ nodes $\mathcal{V}$ and $n_{E}$ links $\mathcal{E}$. The nodes
represent entities of the underlying networked system (e.g. users in an online
social network) and links denotes their relationship (e.g. friendship). Each
node $u_{i}$, $i\in[1,n_{V}]$ of the graph may consist of features, typically
represented through a vector $h_{i}$. Similarly, the link $e_{ij}$, between
$u_{i}$ and $u_{j}$ could also be associated with a set of features
represented as $h_{ij}$ which can, for example, signify the strength of the
link. The interconnections in the graph can also be represented with an
adjacency matrix $A\in\mathbb{R}^{n_{V}\times n_{V}}$ such that $A(i,j)=1$ if
there exists a link between $u_{i}$ and $u_{j}$, and $0$ otherwise.

###  II-A Deep Reinforcement Learning

Reinforcement learning (RL) is considered the third important branch of
machine learning with supervised and unsupervised learning serving as the
other two [22]. RL is a sequential decision process where agents are trained
to take optimal actions for different scenarios of an environment. The action
transitions the environment to a new state and meanwhile the agent gets some
reward that quantifies how good or bad the action was. To formulate the
sequential decision process, RL employs a well known mathematical concept of
Markov decision process (MDP) [22]. Typically, an MDP is defined by
($X,A,p,R$) where $X$ is a finite state space, $A$ is the action space for
each state $x\in X$, $p$ is the state transition probability from state
$x^{t}$ at time $t$ to state $x^{t+1}$ at time $t+1$, and $r$ is the immediate
reward value obtained after an action $a\in A$ is performed. The agent’s
primary goal is to interact with its environment (take state as input) at each
time step to find the optimal policy $\pi^{*}$ (return action for the current
state) in order to reach the goal while maximizing the cumulative rewards
(expected return) over the entire time period. Agent takes the state $X$ as
input and returns an action $a$ to be taken. At a particular time step $t$,
the expected return $R^{t}$ is the sum of rewards from the current time step
onward till the last time step $T$. When taking an action, an agent must
choose between taking the best action based on previous experiences (exploit)
and gathering new experiences (exploration) in order to make better decisions
in the future. A common approach to account for the trade-off is the greedy
strategy, where the agent takes a random action with a probability $\epsilon$.

In addition, there are real-life situations where agents lack sufficient
knowledge about the environment for holistic learning. Therefore, partially
observed MDPs (POMDP) is designed for these conditions [22]. A POMDP is an MDP
where the agent only possess a partial view of the state and therefore policy
functions maps history of observations (belief states) to actions. It’s
typical expression is similar to that of MDP ($X,a,\Omega,T,p,O,r,b_{o}$) with
some extra elements. The new elements include $\Omega$ that denotes
observation, $T$ signifies time, $O$ represents observation probabilities, and
$b_{o}$ is the initial probability distribution of states. Every time the
agent takes the action, it receives an observation $o\in\Omega$ which depends
on the new state of the environment, the just taken action and probability
$O(o|X^{{}^{\prime}},a)$.

Traditional RL records the state, action and reward values for different
actions taken at the time of training in a tabular format. However, this
tabular approach is not scalable to larger number of state-action pairs, or to
a continuous state-action space [23]. This challenge can be addressed by
employing a DNN to approximate the state-action values, leading to the
paradigm of DRL. The DNN in a DRL framework estimates the state values and
avoids a tedious record-keeping, thus providing an elegant solution to the
scalability challenge. The added advantage of using DNN in DRL is that it
allows the agent to generalize the value of states it has never seen before,
or has partial information about, by leveraging the values of similar states.
As a result, DRL algorithms are far more generalizable and practical for use
across a wide range of applications involving vast state spaces.

There are several ways to classify existing DRL algorithms such as: model-free
vs model-based, value vs policy based, and offline vs online learning. In the
following, we will provide the fundamental concepts of these algorithms across
different categories.

####  II-A1 Value based DRL

Value-based methods aim to learn the value of the state or state-action pair
and then select actions accordingly. The state-action value function
$Q_{\pi}(x,a)$, expressed in Eq. (1), is the expected return starting from
state $x$, taking action $a$, and thereafter following a policy $\pi$. Deep Q
learning (DQN) is one of the widely use algorithm in this category [24].
Q-learning enables the agent to choose an action $a\in A$ with the highest
Q-value available from state $x\in X$ based on a DNN model which maps discrete
state-action space with Q values. The parameters of DQN network is updated
every time step following the Bellman optimality equation as shown in Eq. (1),
where $R$ is the reward obtained and $\alpha$ is the learning rate which takes
values between $0$ and $1$. DQN is an “off-policy” algorithm, where a target
policy is used to take action at the current state $X$ and a different
behavior policy is used to select action at the next state.

$\begin{split}Q_{\pi}(x,a)=E_{\pi}(R^{t}|x^{t},a^{t})=E_{\pi}(\sum_{k=0}^{\infty}\gamma^{k}r^{t+k}|x^{t},a^{t})\\\
=(1-\alpha)Q(x,a)+\alpha\left[R+\gamma
max_{a^{{}^{\prime}}inA}Q(x^{t+1},a^{t+1})\right]\end{split}$ (1)

A key feature of DQN training is the replay buffer, which stores trajectory
information $(x^{t},a^{t},r^{t},x^{t+1})$ during each step of the training. In
DQN, DNN is trained using a minibatch of a randomly selected sample
(experiences) from replay buffer which offers various advantages in terms of
sample efficiency, low variance and large learning scope. For each sample, the
input (state) is passed through the current DNN to generate an output
$\hat{Q}(x,a;\theta)$. The target $Q$ value corresponds to Bellman optimality
equation in (1), and is used to minimize the following loss function [22]:

$L(\theta)=E[R+\gamma max_{a^{{}^{\prime}}\in
A}Q(x^{t+1},a^{{}^{\prime}})-Q(x,a;\theta)]$ (2)

DQN has many variations to improve its current design, including double DQN
and dueling DQN. The max operator in the DQN update equation selects and
evaluates an action using the same Q network. As a result, DQN significantly
overestimates the value function. Double DQN addresses this problem by
employing two distinct networks, one for action selection and the other for
action evaluation [25]. Similarly, dueling Q network approximates the Q
function by decoupling the value function and the advantage function [26].

####  II-A2 Policy based DRL

These methods learn the policy directly unlike value based methods that learn
the values first and then determine the optimal policy. Typically, a
parametrized policy $\pi_{\theta}$ is chosen with parameters constantly
updated by minimizing the expected return using a gradient based approach also
known as policy gradient theorem [27]. They are particularly suitable for very
large action space (continuous problems) and learning stochastic policies. The
policy can be written as:

$\pi(a|x,\theta)=Pr(a|x,\theta),$ (3)

which denotes the probability of taking action $a$ being at state $x$, and
policy is parameterized by $\theta$. Now, we need an objective function to
assess the performance of this policy. The objective function can be defined
as:

$J(\theta)=v_{\pi_{\theta}}(S_{0}),$ (4)

where $v_{\pi_{\theta}}(S_{0})$ is the true value function for the policy
$\pi(a|x,\theta)$, and $S_{0}$ is the start state. In short the maximizing
$J(\theta)$ means maximizing $v_{\pi_{\theta}}(S_{0})$ which is equivalent to
$\nabla J(\theta)=\nabla v_{\pi_{\theta}}(S_{0})$. According to policy
gradient theorem,

$J(\theta)\propto\sum_{x}\mu(x)\sum_{a}q_{\pi}(x,a)\nabla\pi(a|x,\theta),$ (5)

where $\mu(x)$ is the distribution under $\pi$, $q(x,a)$ is the action value
function, and $\nabla v_{\pi_{\theta}}(X_{0})$ is the gradient of $\pi$ given
$x$ and $\theta$. So the theorem says that $J(\theta)$ is proportional to the
sum of the q function times the gradient of the policies for all feasible
actions at the states that we might be at. But to compute this gradient, we
need to find $\nabla\pi(a|x,\theta)$. It turns out the gradient can be
expressed as:

$\nabla_{\theta}\pi_{\theta}(x,a)=\pi(x,a)\nabla_{\theta}Log\pi_{\theta}(x,a),$
(6)

where $\nabla_{\theta}Log\pi_{\theta}(x,a)$ is scoring function. Since this is
a gradient method, the update of the parameters (that we are trying to
optimize) will be conducted in following way:

$\Delta\theta=\alpha\nabla_{\theta}J(\theta).$ (7)

There are various ways to define the policy such as softmax, Gaussian, etc.
[22] Next, we discuss three widely used policy based methods: ($i$) REINFORCE:
where parameter updates at a given time step involves only the action taken
from the current state – the update relies on estimated return by Monte-Carlo
method using episode samples. Since it relies on expected return from the
current time step, it works only for the episodic tasks [7]; ($ii$) Trust
region policy optimization (TRPO) [28]:  add KL divergence constraints for
enabling the trust-region for the optimisation process. It makes sure that the
new updates policy is not far away from the old policy or we can say that the
new policy is within the trust region of the old policy. This constraint is in
the policy space rather than in the parameter space. The KL constraint adds
additional overhead in the form of hard constraints to the optimisation
process. Hence, there is a simpler approach to this problem in terms of
($iii$) Proximal policy optimization (PPO) [29]: that relies on clipped
surrogate objective function to reduce the deviation between new policy and
old policy. Basically, it defines the probability ratio between the new policy
and old policy, and led this ratio to stay within a small interval around $1$.
The clip function truncates the policy ratio between the range $1-\epsilon$
and $1+\epsilon$ , where $\epsilon$ is a hyperparameter. The objective
function of PPO takes the minimum value between the original value and the
clipped value.  It is relatively simpler in implementation and empirically
performs on par with TRPO [7]. Furthermore, these algorithms (REINFORCE, TRPO,
etc.) leverage value estimates for parameter updation. There is an another
line of work which assume the presence of model information and uses
techniques from dynamic programming and approximate dynamic programming to
develop model aided reinforcement learning techniques such as actor only
policy or direct controller [30].

####  II-A3 Actor-critic DRL

Both value based and policy based algorithms have some limitations. While
value based algorithms are not efficient for high dimensional action space,
policy based algorithms have high variance in gradient estimates. To overcome
these shortcomings, an actor-critic method has been proposed that combines the
two approaches [31]. Fundamentally, the agent is trained with two estimators.
First, is an actor function that controls the agent’s behavior by learning the
optimal policy, i.e., provides the best action $a^{t}$ for any input state
$X^{t}$. Second is a critic function that evaluates the action by computing
the value function.

Some of the popular variants of algorithms under this category are discussed
next. Advantage actor-critic (A2C) consists of two DNNs – one for actor and
one for critic [32]. The term “Advantage” corresponds to the temporal
difference (TD) error or in other words its a prediction error. This error is
the difference of the TD target (predicted value of all future rewards from
the current state $x$) and the value of the current state evaluated from the
critic network. Besides A2C, asynchronous advantage actor-critic (A3C)
executes different agents in parallel on multiple instances of the environment
instead of experience replay as in A2C [32]. Although A3C is memory efficient,
its updates are not optimal as different agents work with different version of
model parameters. Deep deterministic policy gradient (DDPG) is an extension
over deterministic policy gradient (DPG), which is designed for continuous
action space [33]. DPG defines policy to be the function
$\mu_{\theta}:X\rightarrow A$. Here, instead of getting the integral over
actions as in stochastic policy, we only need to sum over the state space as
action is deterministic. DDPG employs a parameterized actor function with a
parameterized critic function that approximates the value function using
samples. In this way, DDPG can tackle large variance in policy gradients of
actor-only methods.

Figure 1: Fusion of Deep reinforcement learning with Graph neural network

###  II-B Graph Neural Network

Learning with graph-structured data, such as knowledge graphs, biological, and
social networks have recently attracted a lot of research attention. There are
numerous benefits of representing data as graphs, such as systematic modeling
of relationships, simplified representation of complex problems, etc. It is
however challenging to interpret and evaluate such graph-structured data by
employing conventional DNN-based learning methods. The fundamental
mathematical procedures like convolutions are difficult to implement on graphs
owing to their uneven structure, irregular size of unordered nodes and dynamic
neighborhood composition. Graph Neural Networks (GNN) address these
shortcomings by extending DNN techniques to graph-structured data [34]. GNN
architectures can jointly model both structural information as well as node
attributes. They provide significant performance improvement for graph-related
downstream tasks like node classification, link prediction, community
detection and graph classification [35]. Typically, GNN models consist of a
message passing scheme that propagates the feature information of the nodes to
its neighbors until a stable equilibrium is reached.  This process can
mathematically be expressed as:

$h_{u}^{(l)}=f(h_{v}^{l-1}),v\in N(u)\cup u$ (8)

where, $h$ is the node representing (embedding) vector and $N(.)$ denotes the
neighborhood.  Several GNN algorithms have been proposed to improve this
message passing technique. We discuss some of the key approaches below.

####  II-B1 GCN

Graph convolutional network [36] is the first effort that incorporate
convolution operations (similar to CNN) on GNN. The core idea behind any GNN
is to generate unique Euclidean representation of nodes/links in the graph.
Conventionally, spectral methods generate node representation vectors using
eigen decomposition, but are computationally inefficient and are not
generalizable. GCN overcomes these challenges with its powerful approximation,
where the update equation of the node representation vector $h_{u}$ at a
particular layer $l$ is given by:

$\begin{split}h_{u}^{(l)}&=g\Bigg{[}\theta^{(l)}h_{u}^{(l-1)}A^{*}\Bigg{]}=\Bigg{[}\theta^{(l)}h_{u}^{(l-1)}D^{-\frac{1}{2}}AD^{\frac{1}{2}}\Bigg{]},\end{split}$
(9)

where, $A$ is Adjacency matrix, $D$ is degree matrix,  $\theta$ is the
learnable parameter and $g$ is the activation function.
$A^{*}=D^{-\frac{1}{2}}AD^{\frac{1}{2}}$ is normalized in this way to scale
the node features and ensures numerical stability at the same time. It is
important to note that GCN relies on the entire graph (i.e., full adjacency
matrix) for learning node representation which is inefficient as the number of
neighbors of a node can vary from one to thousands or even more and cannot be
generalized to graphs of different sizes.

####  II-B2 GraphSAGE

It is an inductive node embedding approach that exploits node attributes to
learn an embedding function [37]. It supports simultaneous learning of
topological structure as well as distribution of node features within a
confined neighborhood. The fundamental premise is to train a neural network
that can recognize structural properties of node neighborhood, thereby
indicating its local role in the graph along with global position. Initially,
the algorithm samples node features in the local neighborhood of each node in
the graph-structured data. This is followed by learning appropriate functional
mappings to aggregate the information received by each node as it propagates
through the GNN layers. This inductive learning approach is scalable across
graphs of different sizes as well as subgraphs within a given graph. The
operation performed at $l$th node embedding layer is given by:

$\begin{split}h_{u}^{(l)}&=f^{(l)}\left(h_{u}^{(l-1)},h_{N(u)}^{(l-1)}\right)=g\Bigg{[}\theta_{C}^{(l)}h_{u}^{(l-1)}+\theta_{A}^{(l)}\tilde{A}\Big{(}h_{N(u)}^{(l-1)}\Big{)}\Bigg{]}\end{split}$

where $\tilde{A}$ represents the aggregation operation; $g[\cdot]$ specifies
the activation function; $h_{u}^{(l)}$ denotes the node embedding of node $u$
at $l$th layer; $N(u)$ describes the neighborhood of node $u$; $\theta_{C}$
and $\theta_{A}$ are the parameters of the combination and aggregation
operation of GNN, respectively.

####  II-B3 GAT

Graph attention network (GAT) assumes that contributions of neighboring nodes
to the target node are neither predetermined like GCN nor identical like
GraphSage. GAT adopts attention mechanisms to learn the relative weights
between two connected nodes [38]. The graph convolutional operation according
to single head GAT is defined as follows:

$\begin{split}h_{u}^{(l)}&=g\Bigg{[}\sum_{v\in N(u)\cup
u}\alpha_{uv}\theta^{(l)}h_{u}^{(l-1)}\Bigg{]}\\\
a_{uv}^{l}&=\text{softmax}\Bigg{(}g\Bigg{[}a^{T}\Bigg{(}\theta^{(l)}h_{u}^{(l-1)}||\theta^{l}h_{u}^{(l-1)}\Bigg{)}\Bigg{]}\Bigg{)},\end{split}$
(10)

where the attention weight $\alpha_{uv}$ quantifies the connection strength
between node $u$ and its neighbor $v$. The attention weight is learned across
all node-pairs using softmax function that ensures weights sum up to one over
all neighbors of the node $u$. For the case of Multihead attention, the update
equation for the node embedding is expressed as:

$\begin{split}h_{u}^{(l)}&=\mathbin{\|}_{k=1}^{k}\Bigg{[}g\Big{(}\sum_{v\in
N(u)\cup
u}\alpha_{uv}^{k}\theta^{(l),k}h_{u}^{(l-1)}\Big{)}\Bigg{]}\end{split}$ (11)

where $\mathbin{\|}$ represents concatenation, $\alpha_{uv}^{k}$ are
normalized attention coefficients computed by the k-th attention mechanism,
and $\theta^{(l),k}$ is the corresponding linear transformation’s weight
matrix. This mechanism selectively aggregates the neighborhood contributions
and suppresses minor structural details.

##  III Categorization of DRL+GNN Methods

DRL and GNN have emerged as extremely powerful tools in modern deep learning.
While DRL exploits the expressive power of DNNs to solve sequential decision
making problems with RL, GNNs are novel architectures that are particularly
suited to handle graph-structured data. We identify two broad categories of
research articles that jointly make use of GNN and DRL, as shown in Fig. 2.
The first category of articles makes algorithmic contributions, where DRL and
GNN complement each other with an objective of addressing each other’s
shortcomings in a theoretical setting. On the other hand, the second category
of articles makes application-specific contributions, that leverage a combined
GNN-DRL formulation to address problems specific to different applications.
The first category involves novel fundamental formulations which enhance the
performance of the algorithms in a generic way, irrespective of the
application/use-cases. Whereas, papers in second category combined DRL and GNN
to achieve a certain objective. Therefore, these works entail application-
specific formulations that are suitable for particular use-cases. The summary
of surveyed DRL and GNN fused works is depicted in Table I and individual
components of surveyed papers are outlined in Table II. “Dynamic”, “Scalable”,
“Generalizability” and “Multiagent” are four important attributes that are
selected to characterize the existing works in Table I. Dynamic and Scalable
are evaluated for GNN, where Dynamic determines whether the framework is
applicable for time varying system (configuration, parameter), and Scalable
indicates the ease (memory and computational) of building models for large-
scale inputs and systems. On the other hand, Generalizability and Multi-agent
are defined for DRL algorithms. Generalizability shows the applicability of
trained model across similar RL environments. Multi-agent determines whether
the DRL algorithm involves single agent or multiple agents to accomplish the
desired task.

###  III-A Algorithmic Developments

In this section, we discuss the articles that focus on developing novel
formulations or algorithms to improve DRL or GNN. In these articles, either
GNN is used to improve the formulation and performance of DRL, or DRL is used
to improve the applicability of GNN.

####  III-A1 DRL enhancing GNN

The articles that make use of DRL for improving GNN are used for diverse
purposes including neural architecture search (NAS), improving the
explainability of GNN predictions and designing adversarial examples for GNN.

Neural Architecture Search (NAS): refers to the process of automatically
searching for an optimal architecture of a neural network (eg. number of
layers, number of nodes in layer, etc.) to solve a particular task. A DRL-
based controller that makes use of exploration guided with conservative
exploitation is used in [39] to perform an efficient search of different GNN
architectures. The search space is made up of hidden dimension, attention
head, attention, aggregation, combination, and activation functions. The
authors introduce homogeneity of models as a method to perform a guided
parameter sharing between offspring and ancestor architectures. Along with
computational gain, the unique characteristics of DRL based search engine is
in terms of generalizability, i.e., same model can be used to quickly
determine the optimal parameters for various use-cases. The superiority of the
proposed method is demonstrated with better performance on benchmark datasets
and baselines [40].

Explaining GNN predictions: Generating explanations for DNN predictions is an
important task in improving the transparency of ML models. Shan et al. [41]
use DRL to improve existing methods of explaining GNN predictions. The problem
of generating explanations for GNN predictions involves identifying the sub-
graph that is most influential in generating a prediction. The authors devise
a DRL-based iterative graph generator that starts with a seed node (the most
important node for a prediction) and adds edges to generate the explanatory
sub-graphs. The reward of the DRL model is obtained as the mutual information
between the original predicted label and the label made by the generated
graph. The distribution of predictions is based solely on the explanatory sub-
graph to learn a sub-graph generation policy with policy gradient. The authors
show that the proposed method achieves better explainability in terms of
qualitative and quantitative similarity between the generated sub-graphs and
the ground truth explanations. The unique exploitation vs exploration search
mechanism of DRL inherently allow the model to find relevant subgraphs without
getting stuck in local regions, which is usually the case with conventional
approaches.

Figure 2: A taxonomy of hybrid DRL and GNN works

Generating adversarial attacks for GNN: Recent studies [42, 43, 44] have shown
that GNNs are vulnerable to adversarial attacks that perturb or poison the
data used for training them. DRL has been used to learn strategies to make
adversarial attacks on GNNs, which in turn can be used to devise defense
strategies to such attacks. RLS2V [45] is one of the first frameworks that
uses DRL to perform an attack aimed at evading detection during
classification. Specifically, it employs a Q-learning and structure-to-vector
based attack methodology that learns to modify the graph structure (adding or
dropping existing edges) with only the prediction feedback (reduction in
accuracy) of the target classifier.  While [46] consider a novel node
injection poisoning attack (NIPA) on graph data considering nodes as well as
links. Specifically, it injects fake nodes (e.g., fake accounts in a social
networks) into the graph, and uses carefully crafted labels for the fake nodes
together with links between them and other (fake as well as genuine) nodes in
the graph to poison the graph data. NIPA frames the sequential addition of
adversarial connections and the design of adversarial labels for the injected
fake nodes as an MDP and solves it with deep Q-learning. To effectively cope
with the large search space, NIPA adopts hierarchical Q-learning and GCN based
encoding of the states into their low-dimensional latent representations to
handle the non-linearity of the mapping between states and actions.
Furthermore, the underlying Q network in these approaches, learns the
sensitivity (relationship) between the changes in the input graph and final
performance, rather than exact mapping. This enables them to predict
performance for various possible configurations of attacks for different
families of graph, which is not feasible with conventional graph optimization
approaches.

####  III-A2 GNN enhancing DRL

This subsection discusses the papers related to the algorithmic improvement of
DRL. Specifically, we focus on efforts wherein GNN has been used for
relational DRL problems (RDRL) for effective modeling of the relationship
among (1) different agents in a multi-agent deep reinforcement learning
(MADRL) framework, and (2) different tasks in multi-task deep reinforcement
learning (MTDRL) framework.

Modeling relationship among agents in MADRL: In MADRL, a group of agents
cooperate or compete with each other to achieve a common goal. This framework
has recently been used for a number of challenging tasks, including traffic
light control, autonomous driving, and network packet delivery [47, 48, 49].
In such scenarios, the communication among agents offers additional
information about the environment and state of other agents. Several methods
have been proposed to learn this communication. The first body of work in
capturing these relationships is related to attention-based approaches [50,
51, 52, 53]. ATOC [54], DGN [55], and COMA-GAT [51] provide communication
through the attention mechanism. Along these lines, G2ANet [56] employs hard
attention to filter out irrelevant data and soft attention to focus on
relevant information. DCG [57] employs coordination graphs, which uses message
passing mechanism to coordinate the behaviors of agents. For each agent, these
attention-based algorithms learn the significance distribution of other
agents. The authors in GraphComm [58], explore both static and dynamic
relations simultaneously among agents. Specifically, it leverages the
relational graph module to incorporate static relationships via relational
graph provided by prior system knowledge and uses proximity relational graph
for dynamic relationships. Agents’ Q values are learned in a CTDE manner via
MLP and GRU network along with RGCN and GAT to exchange messages among agents
for static and dynamic relations, respectively.

Similarly, in [59], Zhang et al. propose a Structural Relational Inference
Actor-Critic (SRI-AC) framework for CTDE that can automatically infer the
pairwise interaction between agents and learn a state representation. The
model is used to predict which agents need to interact in advance, and then
supply the most relevant agent observation information to the critic network.
In particular, each agent has a critic, which leverages information from the
combined action as well as appropriate observational data during training.
Then a variational autoencoder (VAE) is used to infer the pairwise
interaction, and state representation from observed data, followed by a critic
network that employs GAT to integrate the knowledge from neighboring agents.
In a similar vein, [60] presents a novel state categorization method for CTDE
DRL. Basically, it separates the state into agents’ own observations, allies’
partial information, and opponents’ information specific to the Starcraft
game, and then leverages GAT to learn the correlation and relationship among
the agents.

Modeling relationship among tasks in MTDRL: This framework provides an elegant
way to exploit commonalities between multiple tasks in order to learn policies
with improved returns, generalization, data efficiency, and robustness. One of
the inherent assumptions in a majority of MTDRL works is compatible state-
action spaces, i.e., same dimensions of states and actions across multiple
tasks. However, this is violated in many practical applications like
combinatorial optimization and robotics [61]. This issue has been addressed by
using GNNs that are capable of processing graphs of arbitrary size, thereby
supporting MTDRL in incompatible state-action environments [61]. Since GNNs
provide the flexibility to incorporate structural information, it enables the
integration of additional domain knowledge, where states are characterized as
labeled graphs. The use of GNN in MTDRL has been demonstrated in continuous
control environments that exploit physical morphology of the RL agents for
constructing input graphs [62, 63]. Here, limb features are encoded in the
form of node labels and edges represent the physical connections between the
corresponding limbs. In this way, the structure of the agents is explicitly
modeled in the form of graphs. NerveNet [62] serves as the policy network
which first propagates information over agent structure, followed by
predicting actions for different parts of the agent. The authors in [63]
formulate a single global policy that can be represented as a collection of
modular neural networks called Shared Modular Policies (SMP), each of which is
designated to handle tasks related to its corresponding actuator.

Relational symbolic input for RDRL: The fundamental premise of RDRL is to
integrate DRL with relational learning or Inductive Logic Programming [64],
wherein states, actions and policies are represented by a first-
order/relational language [65]. The tasks in this space are characterized by
variable state and action spaces. In these problems, it is difficult to find
fixed-length representation that is required by a majority of the existing DRL
methodologies. This issue can be handled using GNN by formulating relational
problems in terms of graph-structured data. The mechanics of a relational
domain are typically represented by Relational Dynamic Influence Diagram
Language (RDDL) [66]. Garg et al. [67] propose SymNet for automated extraction
of objects, interactions, and action templates from RDDL. Specifically, an
RDDL problem instance is transformed into an instance graph, for which the
embeddings of states and important object tuples are generated using GNN.
Further, these are decoded into scores corresponding to individual ground
actions. Node embeddings are generated using GNN and action templates are
applied over object tuples to create a probability distribution. This is
followed by updating the model using policy gradient method. However, SymNet
is computationally expensive and is applicable only when RDDL domain
definition is available since pre-defined transition dynamics are required to
construct the graphs. Symbolic Relational DRL (SR-SRL) [68] addresses these
limitations by considering an enriched symbolic input comprising of objects
and relations along with their features in the form of a graph. This does not
require information about transition dynamics and generalizes over any number
of object tuples.

The unique aspect of GNN in terms of representing nodes/links in high
dimensional embedding space makes them an powerful candidate for quantifying
relationship among the large space of agents and tasks as described in
previous three sub-sections. As a result, they are very successful in
assimilating the relational information compared to any other relational
learning methodologies.

In a nutshell, the review of papers in the part A (i.e., algorithmic
developments) indicates that the first set of methods primarily addresses
challenges associated with GNN models. Specifically, these challenges (such as
explainability of GNN predictions and computational complexity of training and
inference process) typically involve large optimization problems, which can be
effectively handled with DRL. The unique “learning from interaction” approach
makes DRL a suitable candidate for this kind of sequential identification
problem. Furthermore, it exhibit all the desirable advantages of a learning
paradigm, i.e., low computational effort, large scalability and high
generalizability compared to the conventional Graph optimization
methodologies. On the other hand, the second class of works focuses on
improving the encoding aspects of DRL algorithms. Specifically, the complexity
of the decision problems is continuously increasing where DRL is adapting to
multi-agent and multi-task configurations. This demands a powerful encoding
mechanism to represent the underlying systems and scenarios, which can be
efficiently accomplished with GNN. The unique message passing mechanism
combined with attention-based learning process, makes them an efficient
encoder for complex data generated from distributed multi-agent and multi-task
systems.

###  III-B Applications

The second broad category of articles exploit the versatility of DRL along
with the flexible encoding capability of GNNs to address interesting
challenges in different application domains. These domains span a wide
spectrum, including combinatorial optimization, transportation, control,
knowledge graphs and life sciences, which we briefly review next.

####  III-B1 Combinatorial optimization (CO)

Many CO problems are computationally expensive and require approximations and
heuristics to solve in polynomial time. There has been an increasing interest
in solving CO problems using DRL since they naturally fit into the problem. In
this regard, CO problems are often framed as an MDP where the optimal
actions/solutions can be learnt with DRL. Further, the underlying environment
is represented as graph that is processed using GNN.  The problem can be
mathematically written as: Given a graph $G=(V,E)$, where $V=A\cup B$ and a
budget $b$, find a set $S^{*}\subseteq A$ of $b$ nodes such that $f(S^{*})$ is
maximized. $f(S^{*})$ is the cost function specific to the objective. In DRL,
this problem is typically formulated as a MDP, where state represent the
current solution set $S$ and action refers to the process of selecting a node
from $V$ and appending to the solution set. The process is repeated until the
cardinality $|S|$ reaches $b$. Reward quantifies the benefit of taking an
action, and it is proportional to $f(S)$.  The articles addressing these
challenges can further be divided into following sub-categories:

Solving CO problems in Operations Research: Manchanda et al. [69] use GNN to
capture the structural information of CO problems and thus address the poor
generalizability and scalability of existing DRL-based approaches. They
learned a construction heuristic for a budget-constrained maximum vertex cover
(MVC) problem by combining supervised learning and DRL. GCN is first utilized
to find appropriate candidate nodes by learning the scoring function computed
using the probabilistic greedy approach. Then, the candidate nodes are used in
an algorithm similar to [70] to sequentially construct a solution. Since the
degree of nodes in large graphs can be rather high, importance sampling based
on computed score is used to select the neighboring nodes while determining
embeddings, thereby reducing the computational complexity. Extensive
experiments on random/real-world graphs reveal that the proposed method
marginally outperforms S2V-DQN and scales to much larger graph instances up to
a hundred thousand nodes. Additionally, it is significantly more efficient in
terms of the computation efficiency due to a relatively smaller number of
learned parameters.

Another interesting application of DRL and GNN can be seen in solving
diffusion processes in graphs, such as influence maximization, and epidemic
test prioritization, among others. The goal is to identify a set of nodes on a
temporally evolving graph such that the global objective of curbing spread or
maximizing information spread is achieved [71, 72]. Various graph-theoretic
algorithms have been developed to address this class of problems. However,
they are inefficient when scaling to larger graphs. Further, the added
difficulty is that the states are partially observed, for instance, we might
not know the ground truth infection status for every node in the graph at any
point in time. To address these challenges, [73] poses the problem of
controlling a diffusive process on a temporally evolving graph as a partially-
observed Markov decision process (POMDP). The problem of selecting a subset of
nodes for dynamical intervention is formulated as a ranking problem, and an
actor-critic proximal policy optimization is employed to solve it.
Specifically, the architecture contains two separate GCN modules; one updates
the node representation according to the dynamic process and the other is in
charge of long-range information propagation. The results on various real-
world networks, including COVID-19 contact tracing data, show the superior
performance of this approach.

Solving design problems: Several design problems, especially electronic
circuit design are CO problems, which can benefit from a DRL-GNN formulation.
For instance, automatic transistor sizing is a challenging problem in circuit
design due to the large design space, complex performance tradeoffs, and fast
technological advancements. The authors in [74], present the GCN-RL Circuit
Designer, which uses DRL to transfer knowledge between different technology
nodes and topologies. GCN is employed to learn the circuit topology
representation. The GCN-RL agent retrieves features of the topology graph with
transistors as nodes and wires as links. Actor critic approach with continuous
space DRL algorithm DDPG is used. The generalizability of DRL enables training
on one technology node and then applying the trained agent to search the same
circuit under different technology nodes. GCN extracts circuit features which
enables transfer of knowledge between different topologies that share similar
design principles, for example, between a two-stage and three-stage trans-
impedance amplifier.

A similar problem is Logic synthesis for combinational circuits, in which the
lowest equivalent representation for Boolean logic functions is sought. A
widely used logic synthesis paradigm represents Boolean logic with
standardized logic networks, such as and-inverter graphs (AIG), which
iteratively conducts logic minimization operations on the graph. To this end,
[75] poses this problem as an MDP and DRL is incorporated with GCN to explore
the solution search space. Specifically, this work leverages Monte Carlo
policy gradient based RL algorithm, REINFORCE. Since circuits and AIG logic
can be naturally modeled as graphs, they leverage GCN to extract the current
state’s features.

System robustness: Recently, authors in [76] demonstrate a novel application
of DRL with GNN, where the authors used DRL to search for optimal graph
topology for a given graph objective. Essentially, the construction of a graph
is framed as a sequential decision process of adding a fixed number of links
to the current graph one at a time such that the robustness score of the final
graph is the maximum among all feasible combinations of the given graph and
edges. Particularly, the state represents the current graph, while the action
corresponds to a new node that needs to be added. They are encoded using the
S2V variant of GNN [77], and DQN constitutes the underlying DRL engine.
Although this approach is more computationally efficient than conventional
approaches (such as greedy, Fiedler vector, etc.), it requires an iterative
algorithm at each step of the episode to compute the global score of the
current graph (robustness in this case), which demands some computational
effort. This can be avoided by using learning-based models to compute
intermediate rewards, i.e., global graph scores [78, 79].

####  III-B2 Transportation

Transportation problems that are handled with DRL and GNN can be broadly
classified into two classes, namely routing and speed prediction.

Vehicle routing: Routing problem is usually formulated by considering a graph
$G(V,E)$, in which $V=C\cup\\{0,n+1\\}$ is the set of nodes associated to
customers in $C$ and to the depot nodes $0$ and $n+1$. Nodes $0$ and $n+1$
represent the same depot and impose that all routes must start on $0$ and
return to $n+1$. Set $E$ contains the links $(u,v)$ for each pair of nodes
$u,j\in N$. The cost of crossing an link $(u,v)\in E$ is denoted by $c_{uv}$ .
Each node has a demand $q_{i}$. The objective of the problem is to determine a
set of minimal cost route for each of the $k$ vehicle satisfying all the
requirements. In DRL, this problem is typically formulated by initializing an
solution set $S$ with the fixed starting and ending node representing depot.
Action would be to select the city node and fill the intermediate values in
the solution set $S$. Reward will be proportional to both the cost of the
links ($c_{uv}$) and demand of the selected node $a$. The process is repeated
until the aggregated demand of all the selected city crosses the net limit.
This problem can also be posed in a multiagent setting where each agent (here
each vehicle) allots its routes by exchanging the information among them. One
of the early efforts to solve the vehicle routing problems (VRP) with GNN with
DRL is the Traveling Salesperson Problem (TSP), where the objective is to find
the shortest possible route that visits each node in the graph exactly once
and returns to the source node [80]. Here, the state is denoted by a graph
embedding vector that describes the tour of the nodes until time step $t$,
whereas action is defined as selecting a node from the non-visited pool and
the reward is the negative tour length. A GNN with attention mechanism is used
as an encoder followed by a pointer network decoder. The described
encoder–decoder network’s parameters are updated using the REINFORCE algorithm
with a critic baseline. The methodology proposed by [81] adopts a GNN
representation to offer a general framework for model-free RL that adapts to
different problem classes by altering the reward. This framework uses the
edge-to-vertex line graph to model problems and then formulates them in a
single-player game framework. The MDPs for TSP and VRP are the same as in
[82]. Rather than employing a full-featured Neural MCTS, [81] represents a
policy as a graph isomorphism network (GIN) encoder with an attention-based
decoder, which is learned throughout the tree-search operation. Further, [83]
proposes to learn the improvement heuristics (methods that start from an
arbitrary policy and improve iteratively) for VRP in a hierarchical manner.
The authors devised an intrinsic MDP that includes not only the present
solution’s features but also the running history. REINFORCE method is used to
train the policy, which is parameterized by a GAT.

Another important problem of cooperative combinatorial optimization in TSP is
related to optimization of the multiple TSPs (MTSP). [84] developed an
architecture consisting of a shared GNN and distributed policy networks to
learn a common policy representation to produce near-optimal solutions for the
MTSP. Specifically, Hu et al. use a two-stage approach, where REINFORCE is
used to learn an allocation of agents to vertices, and a regular optimization
method is used to solve the single-agent TSP associated with each agent.

Speed/flow control: The second class of transportation problems deals with the
prediction of speed/flow in the road network commonly referred as traffic
signal control (TSC)  [85]. In recent years, TSC has been modeled as an MDP
and researchers have adopted DRL to control the traffic signals [86, 87, 88,
89, 90]. The authors in [88] propose Inductive Heterogeneous Graph Multi-agent
Actor-critic (IHG-MA) algorithm consisting of three steps: ($i$) sampling of
heterogeneous nodes via fast random walk with restart approach, ($ii$)
encoding heterogeneous features of nodes in each group using Bi-GRUs, and
($iii$) aggregating embeddings of groups using graph attention mechanism.
Finally, the proposed MA framework employs the actor-critic approach on the
obtained node embeddings to compute the $Q$-value and policy for each SDRL
agent, and optimizes the whole algorithm to learn the transferable traffic
signal policies across different networks and traffic conditions. Shang et al.
[91] proposed to use a DQN agent to effectively combine the predictions of GCN
and GAT, thus improving the overall space-time modeling capabilities and
forecasting performance. The DQN provides weights to combine the GCN and GAT
predictions, where the weights are adaptive to different network topology,
weather conditions, and other relevant attributes of the traffic data. Apart
from the road network, traffic is also monitored in communication domain such
as optical network. In [92], the authors have proposed to use message passing
GNN architecture to solve routing optimization in optical networks. The key
contribution of this work lies in its generalizability as it is able to
achieve outstanding performance over several real-world networks that are
never seen during training.

####  III-B3 Manufacturing and control

DRL has also been explored in modern manufacturing systems because of the
increasing complexity and interdependency across processes and system-levels
[93, 94, 95]. Recently, Huang et al. [96] proposed an integrated process
system model based on GNN. Here, the manufacturing system is represented as a
graph, where machines are treated as nodes and material flow between machines
as links. GCN is used to encode machine nodes and obtain a node’s latent
representation that reflects both the local condition of the machine (i.e.,
parameters of neighboring machines) and the global status of the entire
system. Each machine is modeled as a distributed agent, and MARL is trained to
learn an independent adaptive control policy conditioned on the node’s latent
feature vector. The latent characteristics of the node, machine process
parameters, and total yield with defects serve as the state, action, and
reward of the underlying MDP, respectively. Specifically, C-COMA [51] has been
deployed by employing the Advantage Actor Critic (A2C) framework in a
distributed setting and is easily compatible with GNN.

In manufacturing, job shop scheduling problem (JSSP) is also an important
problem that aims to determine the optimal sequential assignments of machines
to multiple jobs consisting of series of operations while preserving the
problem constraints. Park et al. [97] propose a framework to construct the
scheduling policy for JSSPs using GNN and DRL. They formulate the scheduling
of a JSSP as a semidefinite programming problem (SDP) in a computationally
efficient way by representing the state of a JSSP as a disjunctive graph [98],
where nodes represent operations, conjunctive edges represent
precedence/succeeding constraints between two nodes, and disjunctive edges
represent machine-sharing constraints between two operations. Then, they
employ a GNN to learn node embeddings that summarize the spatial structure of
the JSSP and derive a scheduling policy that maps the embedded node features
to scheduling action. Proximal policy optimization (PPO) algorithm, a variant
of policy-based RL, is used to train GNN-based state representation module and
the parameterized decision-making policy jointly [29].

Another key application of DRL is in the control of connected autonomous
vehicles [99, 100, 101, 102]. However, DRL-based controllers in most existing
literature address only a single or fixed number of agents with both fixed-
size observation and action spaces. This is because of the highly
combinatorial and volatile nature of CAV networks with dynamically changing
number of agents (vehicles) and the fast-growing joint action space associated
with multi-agent driving tasks, which pose difficultly in achieving
cooperative control. Recently, Chen et al. [103] presented a DRL based
algorithm that combines GCN with DQN to achieve efficient information fusion
from multiple resources. A centralized multi-agent controller is then built
upon the fused information to make collaborative lane changing decisions for a
dynamic number of CAVs within the CAV network.

Efficient allocation of communication resources in wireless networks that are
commonly used in modern control systems to exchange data across a vast number
of plants, sensors, and actuators is also addressed with DRL [104, 105]. These
DRL techniques, however do not scale well with the network size. To overcome
this issue, Lima et al. [106] employ a GNN to parameterize the resource
allocation function. In particular, Gama et al. [107] use random edge GNNs
since the underlying communication graph is randomly distributed, and then
coupled it with REINFORCE since the action space is continuous.

Another interesting application can be found in multi agent formation control.
Although a number of algorithms can achieve formation control effectively,
they ignore the structure feature of the graph formed by agents [108, 109,
50]. Wang et al. [110] proposed a model named MAFCOA building on the framework
of GAT. In particular, the model can be divided into two parts including
formation control and obstacles avoidance. The first part uses GAT and focuses
on cooperation among agents, while the second part focuses on obstacle
avoidance with multi-LSTM models. The Multi-LSTM allows the agents to take
obstacles into consideration in the order of distance and avoid arbitrary
number of obstacles [111]. Moreover, in order to scale to more agents, the
parameters are shared to train all the agents in a decentralized framework.
Actor and critic approach is used with MADDPG to learn the optimal control
policy for multiple agents.

####  III-B4 Knowledge graph completion

Knowledge Graphs (KG) are increasingly being used to represent heterogeneous
graph-structured data in a wide variety of applications including
recommendation systems [112], social networks [113], question-answering
systems [114], smart manufacturing [115], information extraction [116],
semantic parsing [117] and named entity disambiguation [118]. One of the key
problems in real-world knowledge bases is that they are notoriously
incomplete, i.e., a lot of relationships are missing. KG Completion (KGC) is a
knowledge base completion process that aims to fill-in the incomplete real-
world knowledge bases by inferring missing entries with the help of existing
ones. The entities and corresponding relations are represented by means of
triplets consisting of head nodes ($h$), relations ($r$), and tail nodes
($t$). The problem of KGC entails prediction of missing tails for given pairs
of head nodes and relations. Traditional RL-based methods do not consider
generation of new subgraphs within existing knowledge graphs, e.g., new or
missing target entities. Moreover, the domain-specific rules are not
incorporated, which could be utilized to learn state transition processes when
KGC is posed as a Markov process. Finally, the issue of reward sparsity leads
to large variance of sampling methods and low learning efficiency. In order to
overcome these limitations, [119] proposed a Generative Adversarial Network
(GAN)-based DRL framework (GRL). The authors divide the problem into two
scenarios: when the target entity can be located within limited time steps,
and when the target entity cannot be found from the original KG while there
are still time steps to go, in which case a new sub-graph is formed. KGC being
defined as an MDP, explores the rules that can be introduced in both the state
transition process and rewards to better guide the walking path under the
optimization of GAN. LSTM is employed as a generator of GAN, which not only
records previous trajectories (of states, actions, etc.) but also generates
new sub-graphs and trains policy networks with GAN. Furthermore, to better
generate new sub-graphs, a GCN is used to embed the KG into low-dimensional
vectors and parameterize the message passing process at each layer. In
addition, GRL also applies domain-specific rules and utilizes DDPG to optimize
rewards and adversarial loss.

####  III-B5 Life sciences

Along with engineering applications, recent advancements in ML have also
demonstrated the potential to revolutionize various life sciences applications
such as drug discovery [120, 121, 122] and brain network analysis [123]. To
this end, [120] proposes a new method for designing antiviral candidates
coupling DRL to a deep generative model. Specifically, the authors use the
actor critic approach, in which a scaffold-based generative model is leveraged
as the actor model to build valid 3D compounds. For the critic model, parallel
GNNs are used as a binding probability predictor to determine whether the
generated molecule actively binds with a target protein [121]. The results
demonstrated that the model could produce molecules with higher druglikeness,
synthetic accessibility, water solubility, and hyrdophilicity than current
baselines. Do et al. [122] proposed a Graph Transformation Policy Network
(GTPN) that combines the strengths of DRL and GNN to learn reactions directly
from data with minimal chemical knowledge. Their model has three key
components: a GNN, a node pair prediction network, and a policy network. The
GNN is responsible for obtaining the atom’s representation, the node pair
prediction network is responsible for computing the most possible reaction
atom pairs, and the policy network is responsible for determining the optimal
sequence of bond changes that transforms the reactants into products.
Additionally, the model’s step-by-step creation of product molecules allows it
to exhibit intermediate molecules, greatly improving its interpretability.

TABLE I: Summary of surveyed DRL and GNN fused works. AD:Algorithms-DRL enhancing GNN, AG:Algorithms-GNN enhancing DRL, PC:Applications in Combinatorial optimization, PT:Applications in Transportation, PR:Applications in Control, PK:Applications in Knowledge graph, PL:Applications in Life science Reference |  Category |  Dynamic |  Scalable |  Generalizable across envs |  Multiagent |  Source code |  Publication venue-year
---|---|---|---|---|---|---|---
Algorithms
AGNN [39] |  AD |  |  |  |  |  |  arxiv 2019
GraphNAS [40] |  AD |  |  |  |  |  |  IJCAI 2020
RG-Explainer [41] |  AD |  |  |  |  |  |  NeurIPS 2021
RL-S2V [45] |  AD |  |  |  |  |  |  ICML 2018
Sun et al. [46] |  AD |  |  |  |  |  |  WWW 2020
G2ANet [56] |  AG |  |  |  |  |  |  AAAI 2020
DCG [57] |  AG |  |  |  |  |  |  ICML 2020
GraphComm [58] |  AG |  |  |  |  |  |  ICASSP 2021
SRI-AC [59] |  AG |  |  |  |  |  |  Elsevier 2021
CSGA [60] |  AG |  |  |  |  |  |  IEEE SMC-2021
NerveNet [62] |  AG |  |  |  |  |  |  ICLR-2018
SMP [63] |  AG |  |  |  |  |  |  ICML-2020
SymNet [67] |  AG |  |  |  |  |  |  ICML-2020
SR-DRL [68] |  AG |  |  |  |  |  |  arxiv 2021
Applications
GCOMB [69] |  PC |  |  |  |  |  |  NeurIPS-2020
Khalil et al. [70] |  PC |  |  |  |  |  |  NeurIPS-2017
GraMeR [72] |  PC |  |  |  |  |  |  arxiv 2022
RLGN [73] |  PC |  |  |  |  |  |  ICML-2021
GCN-RL [74] |  PC |  |  |  |  |  |  DAC-2020
Rnet-DQN [76] |  PC |  |  |  |  |  |  PRSA-2021
Drori et al. [81] |  PT |  |  |  |  |  |  ICMLA-2020
L2I[83] |  PT |  |  |  |  |  |  ICLR-2020
Hu et al. [84] |  PT |  |  |  |  |  |  Elsevier-2020
IG-RL [87] |  PT |  |  |  |  |  |  IEEE-2021
Shang et al. [91] |  PT |  |  |  |  |  |  Elsevier-2022
Lima et al. [105] |  PR |  |  |  |  |  |  IFAC-2020
Wang et al. [110] |  PR |  |  |  |  |  |  IFAC-2020
GNN-MARL [96] |  PR |  |  |  |  |  |  CIRP-2021
Park et al. [97] |  PR |  |  |  |  |  |  T&F-2021
GCQ [103] |  PR |  |  |  |  |  |  Wiley-2021
GRL [119] |  PK |  |  |  |  |  |  Elsevier-2020
3D-MolGNNRL [120] |  PL |  |  |  |  |  |  ICLR-2022
GTPN [122] |  PL |  |  |  |  |  |  KDD-2019
TABLE II: DRL and GNN components of the surveyed papers

Ref. |  Categ. |  State |  Action |  Reward |  DRL |  GNN |  Remarks
---|---|---|---|---|---|---|---
Algorithms
AGNN [40] |  AD |  Activation function in GNN layers |  Changes in activations, aggregation, hidden units, # heads |  Validation accuracy |  PPO |  GCN, GAT, LGCN |  LSTM encodes graph architecture & DRL for optimizing accuracy
RG-Explainer [41] |  AD |  Node feature and current subgraph |  validation performance + controller entropy |  Prediction loss |  GraphSAGE |  GAT |  Identify most influential subgraph to interpret node prediction
[46] |  AD |  Intermediate poisoned graph |  Add adversarial edge & change labels of injected nodes |  Node classification accuracy |  DQN |  GCN |  novel non-target specific node injection poisoning attack on graphs
CSGA [60] |  AG |  characteristics of agents; partial information of other agents and enemies |  cooperative actions of individual agents |  joint-action value function |  DRQN |  GAT |  Novel MADRL algorithm to control multiple agents in RTS games.
SMP [63] |  AG |  positions, velocity, rotations |  position with lower and upper bound |  actuator response |  DDPG |  Message passing |  shared modular policy that is generalize to variants ( several planar agents with different skeletal structures) not seen during training
SR-DRL[68] |  AG |  objects and their features, relations, global context |  object labels, set of parameters, preconditions |  goal specifications |  A2C |  GAT |  Generic framework for solving relational domains
Applications
GCOMB[69] |  PC |  candidate nodes in solution set |  Adding a node to solution set |  marginal gain of action function |  DQN |  GCN |  Scalable constrained learning of combinatorial algorithms
[70] |  PC |  nodes in solution set |  Adding a node to solution set |  marginal gain in cost function |  DQN |  structure2vec |  First learning framework for graph combinatorial
GraMeR[72] |  PC |  nodes in solution set |  select the node from candidate set |  marginal gain in cost function |  Double DQN |  GraphSage |  GNN predictor to reduce the search space of the DRL agent
RNet-DQN [76] |  PC |  Graph and edge stub(node) |  Adding a node to solution set |  gain in graph robustness score |  DQN |  structure2vec |  Learning graph construction using DRL and GNN
[80] |  PT |  Partial set of visited cities |  next city to visit |  Tour length |  REINFORCE |  GAT |  Learning clever heuristics
IG-RL [87] |  PT |  Current Connectivity and demand |  Switch to next phase or continue with current |  number of vehicles stopped on a lane |  Double
Duelling DQN |  GCN |  Inductive learning applicable to various road networks & traffic distribution
[91] |  PT |  GNN parameters |  Modify GNN parameters |  Target function error |  DQN |  GCN & GAT |  Ensemble model weighing GCN and GAT predictions
[110] |  PR |  Agents local observations |  Unit movement in X & Y directions |  Distance from target point |  REINFORCE |  REGNN |  Leverages graph attention & LSTM for cooperative agent behavior
GNN-MARL [96] |  PR |  node (machine) latent features |  machine control settings |  difference between step wise yield & defect |  C-COMA |  GCN |  Distributed adaptive control for multistage systems
[97] |  PR |  Snapshot of job shop at specific transition |  Loading/skipping scheduling |  negative of number of waiting jobs |  PPO |  GCN |  Generic framework for Job shop scheduling incorporating spatial and temporal structure
[102] |  PK |  Combination of entity and relation space |  Selecting neighboring relational path to another entity |  Closeness of new state to target entity |  DDPG |  GCN |  Leverages GAN and LSTM to capture graph dynamics for knowledge graph completion
GRL [119] |  PK |  Combination of entity and relation space |  Selecting neighboring relational path to another entity |  Closeness of new state to target entity |  A2C |  GCN |  knowledge graph completion with domain specific rules
3D-MolGNNRL [120] |  PL |  Intermediate molecule |  Add new atom to partial molecule |  binding probability and affinity |  A2C |  GAT |  include 3D structure of both protein target and generated compounds for drug design.
GTPN [122] |  PL |  Intermediate compound |  add new bond between an atom pair |  +/- 1 whether generated product matches groundtruth |  A2C |  GAT |  Uses GNN to represent reactant/reagent molecules, and DRL to find an optimal sequence of bond changes for product transformation

##  IV Discussion and lessons learned

Supported by an extensive review, we observe that the use of GNNs in a DRL
framework is becoming increasingly popular from an algorithmic development
perspective and applications of machine learning to complex problems. In this
section, we present our perspectives in terms of applicability and advantages
of fusing these learning frameworks.

###  IV-A Advantages of fusing DRL and GNN

As discussed before, GNN and DRL are fused in two different fronts, i.e.,
algorithmic enhancement where methodologies are enhancing each other and
application where algorithms are supporting each other. This fusion has
several advantages that can be summarized as follows:
(1) On moving from single agent to multi-agent or from single task to multi-
task scenarios in DRL, the complexity of problem drastically increases.
Therefore, various new approaches are continuously being proposed to improve
the model performance. However, there is always a scope to incorporate
auxiliary information for further improvement. Since MADRL/MTDRL involves
multiple agents, incorporating the relational information among these agents
in the core model with a GNN architecture can improve its performance.  Since
GNNs are inherently designed to capture topological/attributed relationships,
they are powerful models that allow capturing the multi-agent and multi-task
relationships relative to other models;
(2) GNN, like other DNN models require further improvements in terms of
automatic setting generation, improving model explainability and enhancing
robustness against adversarial attacks. These tasks can easily be handled via
DRL due to inherent sequential nature.  DRL is well-suited compared to
traditional optimization based approaches for these tasks since it offers a
computationally lightweight framework to tackle large problem spaces in a
scalable and generic way;
(3) The performance of DRL in applications involving graph-structured
environment such as knowledge graphs and transportation networks depend on
encoder to a large extent. Therefore, GNNs are used to represent trajectory
information in such environments and also act as a function approximator.
GNNs are very effective in representing/encoding graphs compared to other
techniques such as graph signal processing or spectral graph theoretic
approaches. Further, they are flexible and generic enough to work for
different graph families and sizes.

###  IV-B Problem-specific applicability of DRL and GNN methods

A fusion of GNN and DRL has found itself a set of niche problems that span
diverse applications, while sharing common features. These common features
are: (1) Sequential decision making setting of the problem, wherein learning
occurs via interactions with the environment in a closed loop manner; (2) The
learning agent exploits its acquired knowledge at any time, while also
striking a balance between exploring multiple options for a potentially better
solution; (3) The learning is aimed at achieving long term goals and avoid
making myopic decisions; (4) The underlying system is most efficiently
represented as a graph, thereby making GNNs the natural choice for
representing such systems. A widely studied example of such a problem is the
traveling salesperson problem, where the process of finding the optimal route
is a sequential process of identifying nodes that lead to minimum total
distance travelled. Furthermore, the underlying problem possesses a graph
structure with nodes being destinations and links representing connection
between them.

The majority of applications in literature involve static systems, so that a
single GNN module can serve as both a function approximator and an encoder for
the environment. However, depending on the nature of the problem, an
appropriate GNN algorithm must be chosen for the best performance.
Environments involving large graphs should rely on GraphSAGE [37] rather than
GCN [36], as GraphSAGE is a sub-graph-based inductive learning approach that
is scalable to larger networks. Similarly, applications where the position of
a node with respect to the entire graph is vital, position-aware GNNs (PGNN)
[124] are preferred. PGNN explicitly make use of anchor nodes along with
neighboring sub-graph to improve the effectiveness of node embeddings.
Furthermore, the expressive power of most GNNs is upper-bounded by the
1-Weisfeiler-Lehman (1-WL) graph isomorphism test, i.e., they cannot
differentiate between different d-regular graphs. Therefore, it is recommended
to explore identity-aware GNN [125] for complex graph-structured environments,
which inductively considers nodes’ identities during message passing.

Along with static graphs, there are certain applications that involve dynamic
graph-structured environments. For instance, in a connected autonomous vehicle
network, the number of vehicles dynamically changes. Under this scenario, an
appropriate strategy would be to use LSTMs fused with GNNs for capturing graph
evolution as well as DRL trajectories. At any instant, the spatial information
of the environment can be gathered via GNN and fed to an LSTM cell state for
learning long-range spatio-temporal dependency. Furthermore, separate GNNs can
be used to encode topological changes and long-range dependencies
individually. Dynamic graphs can also be handled via novel graph neural odes
formulation (GDE), where input-output relationship is determined by a
continuum of GNN layers, blending discrete topological structures and
differential equations [126, 127]. The structure–dependent vector field
learned by GDEs offers a data–driven approach to the modeling of dynamical
networked systems, particularly when the governing equations are highly
nonlinear and therefore challenging to approach with analytical methods [128].
Autoregressive GDE can adapt the prediction horizon by adjusting the
integration interval of the ODE, allowing the model to track the evolution of
the underlying system from irregular observations [126] In addition to the
type of environment, the problem of interest can have a single learning agent
or multiple agents. In a multi-agent application without any interaction
between agents, traditional MADRL algorithms are most suited. However, in
certain scenarios, the agents might interact with each other in search of a
better solution. These interactions can further be predefined or might appear
as an agent interacts with the environment. GNN models can be used to capture
such relationships and provide auxiliary information to the agent in order to
further improve model performance. This also applies to multi-task situations
where different tasks are correlated or structurally related.

GNNs encompasses various tuning parameters in their architecture. Thus, neural
architecture search in them are very effective. DRL algorithms such as DQN are
an appropriate choice for searching since the search methodology is generic
and applicable across different architectures. In fact, any applications
involving search operations in GNN such as adversarial attack can be tackled
very effectively with DRL. The use of multimodal data has led to heterogeneous
graph-structured data in various applications, including knowledge graphs and
recommender systems. Conventional GNNs are not designed to handle
heterogeneity. Therefore, it is recommended to employ customized GNNs like
relational GCN [129], heterogeneous GAT [130] and HetSANN [131] for encoding.
Fundamentally, all these works demand separate aggregation and combination
functions (model parameters) for each node/link type, i.e., node attributes or
link relationships, so that a powerful node representation can be learned.

##  V Challenges and Future Research opportunities

The articles surveyed in this work reveal the wide applicability and
importance of fusing GNN and DRL (summarized in (Section IV). This section
identifies the challenges that lie ahead for widespread adoption, and suggests
future directions to unlock the full potential of a combined GNN-DRL
framework.These challenges and opportunities are shown in Figure 3. We
identify two broad classes of challenges - those associated with fundamental
theoretical limitations of the existing approaches such as generalizability,
explainability, expressivity (interpretability), and the ones concerned with
the transfer of techniques to real life applications, e.g. standard benchmark
design, sensitivty analyses, uncertainty and reliabilty quantification, etc.

Figure 3: Challenges and Future Research Opportunities in hybrid DRL-GNN
paradigm.

###  V-A Improving generalizability with state-of-the-art models and learning
frameworks

Deep neural networks are notoriously challenging in terms of generalizing to
different problems. This problem predominantly stems from the large size, and
hence model capacity of modern deep neural networks. A combined GNN-DRL
approach can fall into the pitfall of poor generalzability by not being able
to generalize to slightly different environment settings. For instance,
changing the layout of environment (e.g. dynamic link connections in social
network while solving combinatorial problem such as influence maximization)
for a model that learns to navigate through the environment can result in the
model being stuck in a segment of the network, or to take large amount of time
to navigate the network. This can be caused either due to the GNN, or the DRL
not being able to generalize to the environment.

One possible approach to address this challenge is to use graph meta
reinforcement learning framework where agents can quickly adapt to new tasks
or environment with fewer samples [72]. Specifically, this can be achieved by
providing context variables that vary with applications/environments. For
example, in case of CO, variations could be the problems that are smaller
instances of the same problem, problem instances with different distributions,
or even the ones from the other types of CO problems. Although certain
generalization efforts can be seen recently, there is more to be done.

Another way to enhance generalizability of DRL algorithms is by exposing
agents to several graph environments that can be created with training graphs
via graph augmentation techniques. One potential idea would be in leveraging
GAN for graph augmentation by generating synthetic examples via perturbing
input graphs in terms of adding/removing nodes and links or modifying
node/link attributes [132, 133]. This enables DRL agent to adapt by learning
invariant features across varied and noisy environments. We believe that
although this task is challenging, it is extremely important and a promising
direction for research in hybird DRL-GNN works. Moreover, recently,
researchers brought the idea of Decision Transformers (similar to large pre-
trained language models such as BERT, GPT, etc.) to DRL algorithms [134]. This
involves pre-training on large set of environments and then fine-tuning on the
specific application. It will be interesting to explore these pre-training and
fine-tuning tasks for graph-structured environments.

###  V-B Increasing transparency by incorporating XAI and representation
learning

A substantial amount of explainable Artificial Intelligence (XAI) literature
is emerging on feature relevance techniques to explain the predictions of a
deep neural network (DNN) or explaining models that consume image source data.
However, it is unclear as to how XAI techniques can aid in understanding
models beyond classification tasks, such as DRL. An improved interpretability
and explainability of DRL (XRL) models could help shed light on the underlying
mechanisms in situations where it is essential to justify and explain the
agent’s behavior, which is still contemplated as a black box. The recent
efforts on XRL are problem specific and cannot be generalized to real-world RL
tasks [135]. Explaining predictions of GNN and explaining reasoning behind the
DRL actions are important and active area of research.

The concepts based on representation learning, like hierarchical RL, self-
attention and Hindsight Experience Replay have been highlighted as a few
encouraging approaches to improve explainability in DRL models [135], and can
be considered as future lines of research. Furthermore, DRL is also employed
for explaining node/link predictions in GNN by identifying the most
influential sub-graph [41]. The use of GNN to improve the prediction of DRL
can also be investigated as a part of future research in this space.

###  V-C Incorporating network constraints with novel formulations

Optimization problems for real-life applications are mostly bounded by a
variety of constraints in terms of finance, time, resources, etc. Most of the
existing DRL work deal with constraints through penalties in rewards, which is
appropriate if the constraints are soft, i.e., they can be violated at some
cost. However, hard constraints must be strictly met and imposing a penalty
cannot eliminate them, and thus is not a perfect approach. An alternative way
to deal with hard constraints is by masking the constraints while designing
the training environment, to keep the exploration space away from constraint
violation, as considered in autonomous driving [136, 137]. These constraints
become further complex when the underlying environment is graph-structured,
such as a transportation network.  A few attempts have been made in this
direction with remarkable performance such as reward shaping via hierarchical
framework [138] and deferred markov decision process [139]. However, there is
still a lot of scope to improve. Therefore, further research is needed to
explore the rich literature of constrained dynamical systems and other
strategies for dealing with hard constraints.

###  V-D Learning with dynamic/heterogeneous environment

A majority of the existing GNN models perform prediction and inferencing over
homogeneous graphs. However, a large number of real-world applications, like
critical infrastructure networks, recommendation systems, and social networks,
involve learning on heterogeneous graphs. Heterogeneous graph-structured data
can represent numerous types of entities (nodes) and relations (edges) within
a common framework. It is difficult to handle such diverse graphs using
existing GNN models. Consequently, developing new models and algorithms that
are capable of learning with heterogeneous graphs would be highly beneficial
in real-world systems like cybersecurity [140], [141], text analysis [142],
[143] and recommendation engines [144], [145]. Integrating the use of DRL
techniques to achieve this goal can be considered as one of the possible
future directions of research. Furthermore, the existing GNN methodologies
assume graph-structured data to be static, i.e., the possibility of addition
and/or removal of nodes/edges is disregarded. However, many practical
applications like social networks encompass dynamic spatial relations that
continuously evolve over time. Although spatial-temporal GNNs (STGNNs) possess
the ability to partially handle dynamic graphs [146], further work is required
to integrate a thorough understanding about executing downstream tasks like
node classification, link prediction, community detection, and graph
classification in dynamic graphs.

###  V-E Enabling a seamless transition to real-world networks

Most of the prevailing GNN-DRL methods are developed based on synthetic graph-
structured datasets and simulated platforms. However, real-life scenarios can
be  far more intricate compared to simulated platforms. Thus, the resulting
models need rigorous validation before being deployed confidently in real life
applications. This validation is specifically more crucial for applications
like connected autonomous vehicle, manufacturing process, etc., where safety
is of utmost importance. There are some attempts to transfer the trained DRL
agent from a simulator to an actual test bed [147] in general DRL, but there
is a significant gap for graph-structured environments in general. Therefore,
seamless transition from a simulated setting to real-world scenarios in a
cautious, protected and productive approach is an important future research
direction.  In this regard, more collaborative efforts from the industry and
academia through partnership projects is required to understand the
limitations of models in real-life applications and devise methods to improve
the model’s performance. It is important to design standardised problem
settings and benchmark datasets that can be used to evaluate and compare
different methodologies for specific applications, enabling the faster
development of the state of the art solutions.

###  V-F Assessing transferrability with uncertainty and reliability
quantification

From the perspective of practitioners, it is critical that any solution be
robust to slight variations in its inputs. Specifically in the case of hybrid
DRL-GNN approaches, it is important that the solutions be robust to changes in
the  graph and environment. A sensitivity analysis of the model’s performance
to data and environmental parameters can provide important insights into the
stability of a model, and help identify  suitable modifications in terms of
environment design, model specification, training process, and data fidelity
among others to improve the real-life applicability of the model. In addition,
quantifying the uncertainty of the model will allow an end-user to calibrate
and evaluate the confidence in the model’s predictions. This can be achieved
with Bayesian approaches such as Bayes by backpropagation, assumed density
filtering, Monte-Carlo dropout, or by ensemble methods [148] . While several
of these studies have been performed for DNNs, a lot of progress is still
required in DRL-GNN approaches to assess the applicability to real-life
scenarios. Finally, generative models such as GANs can be used to generate
different scenarios and potentially improve the model’s performance.

###  V-G Computational Requirements

Schwartz et al., observe that from AlexNet to AlphaZero, the computational
requirements have grown more than $300,000\times$ in six years [149]. For
example, a single game of AlphaGo required 1,920 CPUs and 280 GPUs with an
estimated cost of $\$35,000,000$ [149]. Given the large parameter space, as
well as the lack of formal complexity analysis in existing literature, it
remains challenging to accurately assess the computational requirements of
combined DRL and GNN models. We posit it that the complexity of the combined
models will be additive in nature, rather than multiplicative, and therefore,
will be bounded by the larger of the two complexities of GNN or DRL models for
a given problem setting. Recently, the concept of Foundation model has become
popular for NLP, where single large pretrained model can be efficiently fine
tuned for several downstream tasks [150]. We believe that a single Foundation
model can also be developed for DRL-GNN paradigm with high few/zero-shot
learning capability that can reduce the computational burden imposed by
training several problem-specific decision models.

##  VI Summary and Conclusions

This paper presents a systematic survey of literature focusing on works fusing
DRL and GNN approaches. Although several reviews related to DRL have been
published in recent years, most of these studies are limited to a particular
application domain. This study, for the first time, presents a methodical
review spanning diverse range of application domains. We have reviewed papers
from the perspectives of both fundamental algorithmic enhancements as well as
application-specific developments. From an algorithmic perspective, either a
GNN is exploited to strengthen the formulation and improve performance of DRL,
or DRL is employed to expand the applicability of GNN. Recent works blending
the usage of both DRL and GNN across multiple applications (broadly classified
into combinatorial optimization, transportation, manufacturing and control,
knowledge graphs and life sciences) have been thoroughly investigated and
discussed. We also highlight the key advantages of fusing DRL and GNN
methodologies and outline the applicability of each of those components.
Furthermore, we identify the challenges involved in effective integration of
DRL and GNN, and propose some potential future research directions in this
area.

## References

  * [1] “Mit technology review,” https://www.technologyreview.com/10-breakthrough-technologies/, 2017.
  * [2] N. Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev, “Reinforcement learning for combinatorial optimization: A survey,” _Computers & Operations Research_, vol. 134, p. 105400, 2021.
  * [3] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller, “Playing atari with deep reinforcement learning,” _arXiv preprint arXiv:1312.5602_ , 2013.
  * [4] C. Finn, S. Levine, and P. Abbeel, “Guided cost learning: Deep inverse optimal control via policy optimization,” in _International conference on machine learning_. PMLR, 2016, pp. 49–58.
  * [5] J. Luketina, N. Nardelli, G. Farquhar, J. Foerster, J. Andreas, E. Grefenstette, S. Whiteson, and T. Rocktäschel, “A survey of reinforcement learning informed by natural language,” _arXiv preprint arXiv:1906.03926_ , 2019.
  * [6] A. Bernstein and E. Burnaev, “Reinforcement learning in computer vision,” in _Tenth International Conference on Machine Vision (ICMV 2017)_ , vol. 10696\. SPIE, 2018, pp. 458–464.
  * [7] N. P. Farazi, B. Zou, T. Ahamed, and L. Barua, “Deep reinforcement learning in transportation research: A review,” _Transportation research interdisciplinary perspectives_ , vol. 11, p. 100425, 2021.
  * [8] S. K. Zhou, H. N. Le, K. Luu, H. V. Nguyen, and N. Ayache, “Deep reinforcement learning in medical imaging: A literature review,” _Medical image analysis_ , vol. 73, p. 102193, 2021.
  * [9] M. S. Frikha, S. M. Gammar, A. Lahmadi, and L. Andrey, “Reinforcement and deep reinforcement learning for wireless internet of things: A survey,” _Computer Communications_ , vol. 178, pp. 98–113, 2021.
  * [10] R. N. Boute, J. Gijsbrechts, W. van Jaarsveld, and N. Vanvuchelen, “Deep reinforcement learning for inventory control: A roadmap,” _European Journal of Operational Research_ , 2021.
  * [11] T. Li, G. Peng, Q. Zhu, and T. Başar, “The confluence of networks, games, and learning a game-theoretic framework for multiagent decision making over networks,” _IEEE Control Systems Magazine_ , vol. 42, no. 4, pp. 35–67, 2022.
  * [12] A. Perera and P. Kamalaruban, “Applications of reinforcement learning in energy systems,” _Renewable and Sustainable Energy Reviews_ , vol. 137, p. 110618, 2021.
  * [13] F. Obite, A. D. Usman, and E. Okafor, “An overview of deep reinforcement learning for spectrum sensing in cognitive radio networks,” _Digital Signal Processing_ , vol. 113, p. 103014, 2021.
  * [14] M. Glavic, “(deep) reinforcement learning for electric power system control and related problems: A short review and perspectives,” _Annual Reviews in Control_ , vol. 48, pp. 22–35, 2019.
  * [15] M. Botvinick, J. X. Wang, W. Dabney, K. J. Miller, and Z. Kurth-Nelson, “Deep reinforcement learning and its neuroscientific implications,” _Neuron_ , vol. 107, no. 4, pp. 603–616, 2020.
  * [16] A. Alomari, N. Idris, A. Q. M. Sabri, and I. Alsmadi, “Deep reinforcement and transfer learning for abstractive text summarization: A review,” _Computer Speech & Language_, vol. 71, p. 101276, 2022.
  * [17] J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun, “Graph neural networks: A review of methods and applications,” _AI Open_ , vol. 1, pp. 57–81, 2020.
  * [18] Y. Zhou, H. Zheng, X. Huang, S. Hao, D. Li, and J. Zhao, “Graph neural networks: Taxonomy, advances, and trends,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 13, no. 1, pp. 1–54, 2022.
  * [19] Q. Wang, Z. Mao, B. Wang, and L. Guo, “Knowledge graph embedding: A survey of approaches and applications,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 29, no. 12, pp. 2724–2743, 2017.
  * [20] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” _IEEE transactions on neural networks and learning systems_ , vol. 32, no. 1, pp. 4–24, 2020.
  * [21] S. Ji, S. Pan, E. Cambria, P. Marttinen, and S. Y. Philip, “A survey on knowledge graphs: Representation, acquisition, and applications,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 33, no. 2, pp. 494–514, 2021.
  * [22] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [23] Y. Li, “Deep reinforcement learning: An overview,” _arXiv preprint arXiv:1701.07274_ , 2017.
  * [24] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski _et al._ , “Human-level control through deep reinforcement learning,” _nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [25] H. Van Hasselt, A. Guez, and D. Silver, “Deep reinforcement learning with double q-learning,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 30, no. 1, 2016.
  * [26] Z. Wang, T. Schaul, M. Hessel, H. Hasselt, M. Lanctot, and N. Freitas, “Dueling network architectures for deep reinforcement learning,” in _International conference on machine learning_. PMLR, 2016, pp. 1995–2003.
  * [27] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour, “Policy gradient methods for reinforcement learning with function approximation,” _Advances in neural information processing systems_ , vol. 12, 1999.
  * [28] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz, “Trust region policy optimization,” in _International conference on machine learning_. PMLR, 2015, pp. 1889–1897.
  * [29] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [30] C.-V. Pal and F. Leon, “Brief survey of model-based reinforcement learning techniques,” in _2020 24th International Conference on System Theory, Control and Computing (ICSTCC)_. IEEE, 2020, pp. 92–97.
  * [31] I. Grondman, L. Busoniu, G. A. Lopes, and R. Babuska, “A survey of actor-critic reinforcement learning: Standard and natural policy gradients,” _IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)_ , vol. 42, no. 6, pp. 1291–1307, 2012.
  * [32] V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu, “Asynchronous methods for deep reinforcement learning,” in _International conference on machine learning_. PMLR, 2016, pp. 1928–1937.
  * [33] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra, “Continuous control with deep reinforcement learning,” _arXiv preprint arXiv:1509.02971_ , 2015.
  * [34] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” _IEEE transactions on neural networks_ , vol. 20, no. 1, pp. 61–80, 2008.
  * [35] K. Madhawa and T. Murata, “Active learning for node classification: an evaluation,” _Entropy_ , vol. 22, no. 10, p. 1164, 2020.
  * [36] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [37] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [38] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” _arXiv preprint arXiv:1710.10903_ , 2017.
  * [39] K. Zhou, Q. Song, X. Huang, and X. Hu, “Auto-gnn: Neural architecture search of graph neural networks,” _arXiv preprint arXiv:1909.03184_ , 2019.
  * [40] Y. Gao, H. Yang, P. Zhang, C. Zhou, and Y. Hu, “Graph neural architecture search.” in _IJCAI_ , vol. 20, 2020, pp. 1403–1409.
  * [41] C. Shan, Y. Shen, Y. Zhang, X. Li, and D. Li, “Reinforcement learning enhanced explainer for graph neural networks,” _Advances in Neural Information Processing Systems_ , vol. 34, 2021.
  * [42] D. Zügner, A. Akbarnejad, and S. Günnemann, “Adversarial attacks on neural networks for graph data,” in _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2018, pp. 2847–2856.
  * [43] X. Tang, Y. Li, Y. Sun, H. Yao, P. Mitra, and S. Wang, “Transferring robustness for graph neural network against poisoning attacks,” in _Proceedings of the 13th International Conference on Web Search and Data Mining_ , 2020, pp. 600–608.
  * [44] H. Wu, C. Wang, Y. Tyshetskiy, A. Docherty, K. Lu, and L. Zhu, “Adversarial examples on graph data: Deep insights into attack and defense,” _arXiv preprint arXiv:1903.01610_ , 2019.
  * [45] H. Dai, H. Li, T. Tian, X. Huang, L. Wang, J. Zhu, and L. Song, “Adversarial attack on graph structured data,” in _International conference on machine learning_. PMLR, 2018, pp. 1115–1124.
  * [46] Y. Sun, S. Wang, X. Tang, T.-Y. Hsieh, and V. Honavar, “Non-target-specific node injection attacks on graph neural networks: A hierarchical reinforcement learning approach,” in _Proc. WWW_ , vol. 3, 2020.
  * [47] J. Jin and X. Ma, “Hierarchical multi-agent control of traffic lights based on collective learning,” _Engineering applications of artificial intelligence_ , vol. 68, pp. 236–248, 2018.
  * [48] H. Mao, Z. Gong, Z. Zhang, Z. Xiao, and Y. Ni, “Learning multi-agent communication under limited-bandwidth restriction for internet packet routing,” _arXiv preprint arXiv:1903.05561_ , 2019.
  * [49] H. Mao, Z. Zhang, Z. Xiao, and Z. Gong, “Modelling the dynamic joint policy of teammates with attention multi-agent ddpg,” _arXiv preprint arXiv:1811.07029_ , 2018.
  * [50] S. Iqbal and F. Sha, “Actor-attention-critic for multi-agent reinforcement learning,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 2961–2970.
  * [51] J. Su, S. Adams, and P. A. Beling, “Counterfactual multi-agent reinforcement learning with graph convolution communication,” _arXiv preprint arXiv:2004.00470_ , 2020.
  * [52] Y. Wang, D. Shi, C. Xue, H. Jiang, G. Wang, and P. Gong, “Ahac: Actor hierarchical attention critic for multi-agent reinforcement learning,” in _2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC)_. IEEE, 2020, pp. 3013–3020.
  * [53] H. Mao, Z. Zhang, Z. Xiao, Z. Gong, and Y. Ni, “Learning multi-agent communication with double attentional deep reinforcement learning,” _Autonomous Agents and Multi-Agent Systems_ , vol. 34, no. 1, pp. 1–34, 2020\.
  * [54] J. Jiang and Z. Lu, “Learning attentional communication for multi-agent cooperation,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [55] J. Jiang, C. Dun, T. Huang, and Z. Lu, “Graph convolutional reinforcement learning,” _arXiv preprint arXiv:1810.09202_ , 2018.
  * [56] Y. Liu, W. Wang, Y. Hu, J. Hao, X. Chen, and Y. Gao, “Multi-agent game abstraction via graph attention neural network,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 05, 2020, pp. 7211–7218.
  * [57] W. Böhmer, V. Kurin, and S. Whiteson, “Deep coordination graphs,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 980–991.
  * [58] S. Shen, Y. Fu, H. Su, H. Pan, P. Qiao, Y. Dou, and C. Wang, “Graphcomm: A graph neural network based method for multi-agent reinforcement learning,” in _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2021, pp. 3510–3514.
  * [59] X. Zhang, Y. Liu, X. Xu, Q. Huang, H. Mao, and A. Carie, “Structural relational inference actor-critic for multi-agent reinforcement learning,” _Neurocomputing_ , vol. 459, pp. 383–394, 2021.
  * [60] W. J. Yun, S. Yi, and J. Kim, “Multi-agent deep reinforcement learning using attentive graph neural architectures for real-time strategy games,” in _2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC)_. IEEE, 2021, pp. 2967–2972.
  * [61] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner _et al._ , “Relational inductive biases, deep learning, and graph networks,” _arXiv preprint arXiv:1806.01261_ , 2018.
  * [62] T. Wang, R. Liao, J. Ba, and S. Fidler, “Nervenet: Learning structured policy with graph neural networks,” in _International conference on learning representations_ , 2018.
  * [63] W. Huang, I. Mordatch, and D. Pathak, “One policy to control them all: Shared modular policies for agent-agnostic control,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 4455–4464.
  * [64] S. Muggleton and L. De Raedt, “Inductive logic programming: Theory and methods,” _The Journal of Logic Programming_ , vol. 19, pp. 629–679, 1994\.
  * [65] V. Zambaldi, D. Raposo, A. Santoro, V. Bapst, Y. Li, I. Babuschkin, K. Tuyls, D. Reichert, T. Lillicrap, E. Lockhart _et al._ , “Relational deep reinforcement learning,” _arXiv preprint arXiv:1806.01830_ , 2018.
  * [66] S. Sanner _et al._ , “Relational dynamic influence diagram language (rddl): Language description,” _Unpublished ms. Australian National University_ , vol. 32, p. 27, 2010.
  * [67] S. Garg, A. Bajpai _et al._ , “Symbolic network: generalized neural policies for relational mdps,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 3397–3407.
  * [68] J. Janisch, T. Pevnỳ, and V. Lisỳ, “Symbolic relational deep reinforcement learning based on graph neural networks,” _arXiv preprint arXiv:2009.12462_ , 2020.
  * [69] S. Manchanda, A. Mittal, A. Dhawan, S. Medya, S. Ranu, and A. Singh, “Gcomb: Learning budget-constrained combinatorial algorithms over billion-sized graphs,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 20 000–20 011, 2020.
  * [70] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song, “Learning combinatorial optimization algorithms over graphs,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [71] H. Chen, W. Qiu, H.-C. Ou, B. An, and M. Tambe, “Contingency-aware influence maximization: A reinforcement learning approach,” in _Uncertainty in Artificial Intelligence_. PMLR, 2021, pp. 1535–1545.
  * [72] S. Munikoti, B. Natarajan, and M. Halappanavar, “Gramer: Graph meta reinforcement learning for multi-objective influence maximization,” _arXiv preprint arXiv:2205.14834_ , 2022.
  * [73] E. Meirom, H. Maron, S. Mannor, and G. Chechik, “Controlling graph dynamics with reinforcement learning and graph neural networks,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 7565–7577.
  * [74] H. Wang, K. Wang, J. Yang, L. Shen, N. Sun, H.-S. Lee, and S. Han, “Gcn-rl circuit designer: Transferable transistor sizing with graph neural networks and reinforcement learning,” in _2020 57th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 2020, pp. 1–6.
  * [75] K. Zhu, M. Liu, H. Chen, Z. Zhao, and D. Z. Pan, “Exploring logic optimizations with reinforcement learning and graph convolutional network,” in _2020 ACM/IEEE 2nd Workshop on Machine Learning for CAD (MLCAD)_. IEEE, 2020, pp. 145–150.
  * [76] V.-A. Darvariu, S. Hailes, and M. Musolesi, “Goal-directed graph construction using reinforcement learning,” _Proceedings of the Royal Society A_ , vol. 477, no. 2254, p. 20210168, 2021.
  * [77] H. Dai, B. Dai, and L. Song, “Discriminative embeddings of latent variable models for structured data,” in _International conference on machine learning_. PMLR, 2016, pp. 2702–2711.
  * [78] S. Munikoti, L. Das, and B. Natarajan, “Scalable graph neural network-based framework for identifying critical nodes and links in complex networks,” _Neurocomputing_ , vol. 468, pp. 211–221, 2022.
  * [79] ——, “Bayesian graph neural network for fast identification of critical nodes in uncertain complex networks,” in _2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC)_. IEEE, 2021, pp. 3245–3251.
  * [80] M. Deudon, P. Cournut, A. Lacoste, Y. Adulyasak, and L.-M. Rousseau, “Learning heuristics for the tsp by policy gradient,” in _International conference on the integration of constraint programming, artificial intelligence, and operations research_. Springer, 2018, pp. 170–181.
  * [81] I. Drori, A. Kharkar, W. R. Sickinger, B. Kates, Q. Ma, S. Ge, E. Dolev, B. Dietrich, D. P. Williamson, and M. Udell, “Learning to solve combinatorial optimization problems on real-world graphs in linear time,” in _2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA)_. IEEE, 2020, pp. 19–24.
  * [82] I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio, “Neural combinatorial optimization with reinforcement learning,” _arXiv preprint arXiv:1611.09940_ , 2016.
  * [83] H. Lu, X. Zhang, and S. Yang, “A learning-based iterative method for solving vehicle routing problems,” in _International conference on learning representations_ , 2019.
  * [84] Y. Hu, Y. Yao, and W. S. Lee, “A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs,” _Knowledge-Based Systems_ , vol. 204, p. 106244, 2020.
  * [85] D. Srinivasan, M. C. Choy, and R. L. Cheu, “Neural networks for real-time traffic signal control,” _IEEE Transactions on intelligent transportation systems_ , vol. 7, no. 3, pp. 261–272, 2006.
  * [86] S. Yang, B. Yang, H.-S. Wong, and Z. Kang, “Cooperative traffic signal control using multi-step return and off-policy asynchronous advantage actor-critic graph algorithm,” _Knowledge-Based Systems_ , vol. 183, p. 104855, 2019.
  * [87] F.-X. Devailly, D. Larocque, and L. Charlin, “Ig-rl: Inductive graph reinforcement learning for massive-scale traffic signal control,” _IEEE Transactions on Intelligent Transportation Systems_ , 2021.
  * [88] S. Yang, B. Yang, Z. Kang, and L. Deng, “Ihg-ma: Inductive heterogeneous graph multi-agent reinforcement learning for multi-intersection traffic signal control,” _Neural networks_ , vol. 139, pp. 265–277, 2021.
  * [89] J. Yoon, K. Ahn, J. Park, and H. Yeo, “Transferable traffic signal control: Reinforcement learning with graph centric state representation,” _Transportation Research Part C: Emerging Technologies_ , vol. 130, p. 103321, 2021.
  * [90] M. Noaeen, A. Naik, L. Goodman, J. Crebo, T. Abrar, Z. S. H. Abad, A. L. Bazzan, and B. Far, “Reinforcement learning in urban network traffic signal control: A systematic literature review,” _Expert Systems with Applications_ , p. 116830, 2022.
  * [91] P. Shang, X. Liu, C. Yu, G. Yan, Q. Xiang, and X. Mi, “A new ensemble deep graph reinforcement learning network for spatio-temporal traffic volume forecasting in a freeway network,” _Digital Signal Processing_ , vol. 123, p. 103419, 2022.
  * [92] P. Almasan, J. Suárez-Varela, K. Rusek, P. Barlet-Ros, and A. Cabellos-Aparicio, “Deep reinforcement learning meets graph neural networks: Exploring a routing optimization use case,” _Computer Communications_ , 2022.
  * [93] Q. Xiao, C. Li, Y. Tang, and L. Li, “Meta-reinforcement learning of machining parameters for energy-efficient process control of flexible turning operations,” _IEEE Transactions on Automation Science and Engineering_ , vol. 18, no. 1, pp. 5–18, 2019.
  * [94] J. Dornheim, N. Link, and P. Gumbsch, “Model-free adaptive optimal control of episodic fixed-horizon manufacturing processes using reinforcement learning,” _International Journal of Control, Automation and Systems_ , vol. 18, no. 6, pp. 1593–1604, 2020.
  * [95] J. Huang, Q. Chang, and J. Arinez, “Deep reinforcement learning based preventive maintenance policy for serial production lines,” _Expert Systems with Applications_ , vol. 160, p. 113701, 2020.
  * [96] J. Huang, J. Zhang, Q. Chang, and R. X. Gao, “Integrated process-system modelling and control through graph neural network and reinforcement learning,” _CIRP Annals_ , vol. 70, no. 1, pp. 377–380, 2021.
  * [97] J. Park, J. Chun, S. H. Kim, Y. Kim, and J. Park, “Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning,” _International Journal of Production Research_ , vol. 59, no. 11, pp. 3360–3377, 2021.
  * [98] T. Yamada, “Studies on metaheuristics for jobshop and flowshop scheduling problems,” 2003.
  * [99] S. Chen, Y. Leng, and S. Labi, “A deep learning algorithm for simulating autonomous driving considering prior knowledge and temporal information,” _Computer-Aided Civil and Infrastructure Engineering_ , vol. 35, no. 4, pp. 305–321, 2020.
  * [100] D. M. Saxena, S. Bae, A. Nakhaei, K. Fujimura, and M. Likhachev, “Driving in dense traffic with model-free reinforcement learning,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 5385–5392.
  * [101] R. Du, S. Chen, Y. Li, J. Dong, P. Y. J. Ha, and S. Labi, “A cooperative control framework for cav lane change in a mixed traffic environment,” _arXiv preprint arXiv:2010.05439_ , 2020.
  * [102] Y. Wang, S. Hou, and X. Wang, “Reinforcement learning-based bird-view automated vehicle control to avoid crossing traffic,” _Computer-Aided Civil and Infrastructure Engineering_ , vol. 36, no. 7, pp. 890–901, 2021.
  * [103] S. Chen, J. Dong, P. Ha, Y. Li, and S. Labi, “Graph neural network and reinforcement learning for multi-agent cooperative control of connected autonomous vehicles,” _Computer-Aided Civil and Infrastructure Engineering_ , vol. 36, no. 7, pp. 838–857, 2021.
  * [104] D. Baumann, J.-J. Zhu, G. Martius, and S. Trimpe, “Deep reinforcement learning for event-triggered control,” in _2018 IEEE Conference on Decision and Control (CDC)_. IEEE, 2018, pp. 943–950.
  * [105] V. Lima, M. Eisen, K. Gatsis, and A. Ribeiro, “Resource allocation in wireless control systems via deep policy gradient,” in _2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_. IEEE, 2020, pp. 1–5.
  * [106] ——, “Resource allocation in large-scale wireless control systems with graph neural networks,” _IFAC-PapersOnLine_ , vol. 53, no. 2, pp. 2634–2641, 2020.
  * [107] F. Gama, A. G. Marques, G. Leus, and A. Ribeiro, “Convolutional neural network architectures for signals supported on graphs,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 4, pp. 1034–1049, 2019.
  * [108] R. Lowe, Y. I. Wu, A. Tamar, J. Harb, O. Pieter Abbeel, and I. Mordatch, “Multi-agent actor-critic for mixed cooperative-competitive environments,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [109] J. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson, “Counterfactual multi-agent policy gradients,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 32, no. 1, 2018.
  * [110] H. Wang, T. Qiu, Z. Liu, Z. Pu, and J. Yi, “Multi-agent formation control with obstacles avoidance under restricted communication through graph reinforcement learning,” _IFAC-PapersOnLine_ , vol. 53, no. 2, pp. 8150–8156, 2020.
  * [111] M. Everett, Y. F. Chen, and J. P. How, “Motion planning among dynamic, decision-making agents with deep reinforcement learning,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2018, pp. 3052–3059.
  * [112] X. Wang, D. Wang, C. Xu, X. He, Y. Cao, and T.-S. Chua, “Explainable reasoning over knowledge graphs for recommendation,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 33, no. 01, 2019, pp. 5329–5336.
  * [113] Q. He, J. Yang, and B. Shi, “Constructing knowledge graph for social networks in a deep and holistic way,” in _Companion Proceedings of the Web Conference 2020_ , 2020, pp. 307–308.
  * [114] Y. Zhang, H. Dai, Z. Kozareva, A. J. Smola, and L. Song, “Variational reasoning for question answering with knowledge graph,” in _Thirty-second AAAI conference on artificial intelligence_ , 2018.
  * [115] P. Zheng, L. Xia, C. Li, X. Li, and B. Liu, “Towards self-x cognitive manufacturing network: An industrial knowledge graph-based multi-agent reinforcement learning approach,” _Journal of Manufacturing Systems_ , vol. 61, pp. 16–26, 2021.
  * [116] H. Fei, Y. Ren, Y. Zhang, D. Ji, and X. Liang, “Enriching contextualized language model from knowledge graph for biomedical information extraction,” _Briefings in bioinformatics_ , vol. 22, no. 3, p. bbaa110, 2021.
  * [117] L. Nizzoli, M. Avvenuti, M. Tesconi, and S. Cresci, “Geo-semantic-parsing: Ai-powered geoparsing by traversing semantic knowledge graphs,” _Decision Support Systems_ , vol. 136, p. 113346, 2020.
  * [118] I. O. Mulang’, K. Singh, C. Prabhu, A. Nadgeri, J. Hoffart, and J. Lehmann, “Evaluating the impact of knowledge graph context on entity disambiguation models,” in _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, 2020, pp. 2157–2160.
  * [119] Q. Wang, Y. Ji, Y. Hao, and J. Cao, “Grl: Knowledge graph completion with gan-based reinforcement learning,” _Knowledge-Based Systems_ , vol. 209, p. 106421, 2020.
  * [120] A. D. McNaughton, C. Knutson, M. Bontha, J. A. Pope, and N. Kumar, “De novo design of protein target specific scaffold-based inhibitors via reinforcement learning,” in _ICLR2022 Machine Learning for Drug Discovery_ , 2022.
  * [121] C. Knutson, M. Bontha, J. A. Bilbrey, and N. Kumar, “Decoding the protein-ligand interactions using parallel graph neural networks,” _arXiv preprint arXiv:2111.15144_ , 2021.
  * [122] K. Do, T. Tran, and S. Venkatesh, “Graph transformation policy network for chemical reaction prediction,” in _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2019, pp. 750–760.
  * [123] X. Zhao, J. Wu, H. Peng, A. Beheshti, J. Monaghan, D. McAlpine, H. Hernandez-Perez, M. Dras, Q. Dai, Y. Li _et al._ , “Deep reinforcement learning guided graph neural networks for brain network analysis,” _arXiv preprint arXiv:2203.10093_ , 2022.
  * [124] J. You, R. Ying, and J. Leskovec, “Position-aware graph neural networks,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 7134–7143.
  * [125] J. You, J. Gomes-Selman, R. Ying, and J. Leskovec, “Identity-aware graph neural networks,” _arXiv preprint arXiv:2101.10320_ , 2021.
  * [126] M. Poli, S. Massaroli, J. Park, A. Yamashita, H. Asama, and J. Park, “Graph neural ordinary differential equations,” _arXiv preprint arXiv:1911.07532_ , 2019.
  * [127] J. Zhuang, N. Dvornek, X. Li, and J. S. Duncan, “Ordinary differential equations on graph networks,” 2019.
  * [128] L. Furieri, C. L. Galimberti, M. Zakwan, and G. Ferrari-Trecate, “Distributed neural network control with dependability guarantees: a compositional port-hamiltonian approach,” in _Learning for Dynamics and Control Conference_. PMLR, 2022, pp. 571–583.
  * [129] M. Schlichtkrull, T. N. Kipf, P. Bloem, R. v. d. Berg, I. Titov, and M. Welling, “Modeling relational data with graph convolutional networks,” in _European semantic web conference_. Springer, 2018, pp. 593–607.
  * [130] X. Wang, H. Ji, C. Shi, B. Wang, Y. Ye, P. Cui, and P. S. Yu, “Heterogeneous graph attention network,” in _The world wide web conference_ , 2019, pp. 2022–2032.
  * [131] H. Hong, H. Guo, Y. Lin, X. Yang, Z. Li, and J. Ye, “An attention-based graph neural network for heterogeneous structural learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 04, 2020, pp. 4132–4139.
  * [132] C. Fan, Y. Sun, Z. Li, Y.-Y. Liu, M. Chen, and Z. Liu, “Dismantle large networks through deep reinforcement learning,” in _ICLR representation learning on graphs and manifolds workshop_ , 2019.
  * [133] C. Fan, L. Zeng, Y. Feng, G. Cheng, J. Huang, and Z. Liu, “A novel learning-based approach for efficient dismantling of networks,” _International Journal of Machine Learning and Cybernetics_ , vol. 11, no. 9, pp. 2101–2111, 2020.
  * [134] Q. Zheng, A. Zhang, and A. Grover, “Online decision transformer,” _arXiv preprint arXiv:2202.05607_ , 2022.
  * [135] A. Heuillet, F. Couthouis, and N. Díaz-Rodríguez, “Explainability in deep reinforcement learning,” _Knowledge-Based Systems_ , vol. 214, p. 106685, 2021.
  * [136] M. Nazari, A. Oroojlooy, L. Snyder, and M. Takác, “Reinforcement learning for solving the vehicle routing problem,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [137] Y. Liu, A. Halev, and X. Liu, “Policy learning with constraints in model-free reinforcement learning: A survey,” in _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence_ , 2021.
  * [138] Q. Cappart, T. Moisan, L.-M. Rousseau, I. Prémont-Schwarz, and A. A. Cire, “Combining reinforcement learning and constraint programming for combinatorial optimization,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 5, 2021, pp. 3677–3687.
  * [139] S. Ahn, Y. Seo, and J. Shin, “Learning what to defer for maximum independent sets,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 134–144.
  * [140] B. Hu, Z. Zhang, C. Shi, J. Zhou, X. Li, and Y. Qi, “Cash-out user detection based on attributed heterogeneous information network with a hierarchical attention mechanism,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, no. 01, 2019, pp. 946–953.
  * [141] S. Hou, Y. Ye, Y. Song, and M. Abdulhayoglu, “Hindroid: An intelligent android malware detection system based on structured heterogeneous information network,” in _Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining_ , 2017, pp. 1507–1515.
  * [142] H. Linmei, T. Yang, C. Shi, H. Ji, and X. Li, “Heterogeneous graph attention networks for semi-supervised short text classification,” in _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , 2019, pp. 4821–4830.
  * [143] L. Hu, S. Xu, C. Li, C. Yang, C. Shi, N. Duan, X. Xie, and M. Zhou, “Graph neural news recommendation with unsupervised preference disentanglement,” in _Proceedings of the 58th annual meeting of the association for computational linguistics_ , 2020, pp. 4255–4264.
  * [144] C. Shi, B. Hu, W. X. Zhao, and S. Y. Philip, “Heterogeneous information network embedding for recommendation,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 31, no. 2, pp. 357–370, 2018.
  * [145] B. Hu, C. Shi, W. X. Zhao, and P. S. Yu, “Leveraging meta-path based context for top-n recommendation with a neural co-attention model,” in _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2018, pp. 1531–1540.
  * [146] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” _IEEE transactions on neural networks and learning systems_ , vol. 32, no. 1, pp. 4–24, 2020.
  * [147] B. Chalaki, L. E. Beaver, B. Remer, K. Jang, E. Vinitsky, A. M. Bayen, and A. A. Malikopoulos, “Zero-shot autonomous vehicle policy transfer: From simulation to real-world via adversarial learning,” in _2020 IEEE 16th International Conference on Control & Automation (ICCA)_. IEEE, 2020, pp. 35–40.
  * [148] S. Munikoti, D. Agarwal, L. Das, and B. Natarajan, “A general framework for quantifying aleatoric and epistemic uncertainty in graph neural networks,” _arXiv preprint arXiv:2205.09968_ , 2022.
  * [149] R. Schwartz, J. Dodge, N. A. Smith, and O. Etzioni, “Green ai,” _Commun. ACM_ , vol. 63, no. 12, p. 54–63, nov 2020. [Online]. Available: https://doi.org/10.1145/3381831
  * [150] R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, S. von Arx, M. S. Bernstein, J. Bohg, A. Bosselut, E. Brunskill _et al._ , “On the opportunities and risks of foundation models,” _arXiv preprint arXiv:2108.07258_ , 2021.