# Feature Importance-aware Graph Attention Network and Dueling Double Deep
Q-Network Combined Approach for Critical Node Detection Problems

Xuwei Tan1, Yangming Zhou2,3, Zhanghua Fu4, Mengchu Zhou5

###### Abstract

Detecting critical nodes in sparse networks is important in a variety of
application domains. A Critical Node Problem (CNP) aims to find a set of
critical nodes from a network whose deletion maximally degrades the pairwise
connectivity of the residual network. Due to its general NP-hard nature,
state-of-the-art CNP solutions are based on heuristic approaches. Domain
knowledge and trial-and-error are usually required when designing such
approaches, thus consuming considerable effort and time. This work proposes a
feature importance-aware graph attention network for node representation and
combines it with dueling double deep Q-network to create an end-to-end
algorithm to solve CNP for the first time. It does not need any problem-
specific knowledge or labeled datasets as required by most of existing
methods. Once the model is trained, it can be generalized to cope with various
types of CNPs (with different sizes and topological structures) without re-
training. Extensive experiments on 28 real-world networks show that the
proposed method is highly comparable to state-of-the-art methods. It does not
require any problem-specific knowledge and, hence, can be applicable to many
applications including those impossible ones by using the existing approaches.
It can be combined with some local search methods to further improve its
solution quality. Extensive comparison results are given to show its
effectiveness in solving CNP.

## Introduction

Networks (also known as graphs) are a general and flexible representation for
describing complex systems of interacting entities, which have been widely-
used to represent real-world data. In recent years, Graph Neural Networks
(GNNs) have achieved great success in many challenging graph tasks (Khalil et
al. 2017; Li, Chen, and Koltun 2018; Fan et al. 2020; Bai et al. 2021). Among
such tasks, detecting a set of critical nodes in sparse networks (Arulselvan
et al. 2009; Zhou, Hao, and Glover 2019; Fan et al. 2020; Zhou et al. 2021) is
an important yet particularly hard task.

Critical node detection is useful in such practical applications, e.g.,
vulnerability assessment (Shen et al. 2012), drug discovery (Harrold,
Ramanathan, and Mager 2013), epidemic control (Doostmohammadian, Rabiee, and
Khan 2020), network security (Zhang et al. 2020), and social network analysis
(Fan et al. 2020), where valuable knowledge may be discovered by investigating
the identified critical nodes. According to specific scenarios, different
connectivity measures are designed to quantify network functionality
appropriately. In this study, we focus on a basic critical node detection
problem known as Critical Node Problem (CNP) (Zhou et al. 2021). It aims to
find a subset of nodes such that the removal of these vertices minimizes the
pairwise connectivity of the residual network.

Detecting critical nodes in sparse networks is a very challenging task
(Arulselvan et al. 2009; Baggio et al. 2021). On the one hand, critical nodes
are task-specific, i.e., the number and location of critical nodes may vary
from task to task. On the other hand, they need to be found at the global-
scale. To the best of our knowledge, there is no existing deep learning
methods that can identify task-dependent critical nodes at the global-scale in
an efficient manner.

Due to its NP-hard nature, state-of-the-art CNP solutions are based on
heuristic approaches (Pullan 2015; Aringhieri et al. 2016; Zhou, Hao, and
Glover 2019; Zhou et al. 2021). Domain knowledge and trial-and-error are
necessary to design them. They need to be revised or re-executed whenever a
problem change of the problem occurs. It thus becomes extremely expensive to
apply them to detect critical nodes in real-world networks that are constantly
changing.

Moreover, real-world networks from different fields vary significantly in
size. For example, social networks can be constructed with dozens of nodes to
billions of nodes. Although GNNs can operate on networks regardless of their
size, can they generalize to networks of sizes that were not seen during their
training phase? This question remains unanswered for CNP to the best of the
authors’ knowledge. It would be highly valuable to design a deep learning
method that can train on small networks and generalize to larger networks.

To answer the above-raised question, we propose a Feature importance-aware
Graph attention network and Dueling Double-deep-Q-network (FGDD) combined
approach to solve CNP. It works in two phases. At the first phase, we develop
a feature importance-aware Graph Attention neTwork (GAT) based on feature
aggregation and variance-constrained GAT module that learn the importance
vector of the nodes. At the second phase, we employ a dueling Double Deep
Q-Network (DDQN) as our agent to perform node selection. Our dueling DDQN
agent treats node representation from first phrase as a graph state and
determines the actions through dueling network. This work intends to make the
following contributions:

  * •

We formulate the process of identifying critical nodes in a network as a
sequential decision problem via a Markov Decision Process (MDP). To solve it,
we propose an end-to-end algorithm called FGDD that well combines feature
importance-aware GAT with dueling DDQN.

  * •

Our feature importance-aware GAT integrates two distinguishing components.
First, a feature aggregation method is developed to aggregate existing metrics
(i.e., node degree, degree centrality, eigenvector centrality, and PageRank)
into a matrix that well represents the network information. Second, an
invariance-constrained GAT is adopted to balance specificity and invariance.

  * •

We experimentally evaluate FGDD on 28 real-world networks. Empirical results
show our model not only outperforms two deep reinforcement learning-based
algorithms, but also competes well with three heuristic algorithms.

## Related Work

### Exact and Heuristic Methods

Detecting critical nodes in sparse network is proven to be an NP-complete
problem (Arulselvan et al. 2009). Considerable efforts have been made to solve
it, and a variety of methods have been proposed in the literature (Di Summa,
Grosso, and Locatelli 2011; Summa, Grosso, and Locatelli 2012; Pullan 2015;
Zhou et al. 2021). Most of existing studies focus on developing exact
algorithms and heuristic ones, called traditional algorithm in this paper.

Exact algorithms for CNP are able to guarantee the optimality of their
solutions. They are particularly useful for specifically structured graphs
such as trees (Di Summa, Grosso, and Locatelli 2011) and series-parallel
graphs (Shen and Smith 2012). For general graphs, CNP has been solved by the
branch and cut methods, including a general mixed integer linear programming
model (Arulselvan et al. 2009), and a vary large model relying on constraint
separation (Summa, Grosso, and Locatelli 2012). However, they are very time-
consuming when tackling large instances.

Compared to exact algorithms, heuristic algorithms lack theoretical guarantees
for the solution quality but are more favorable in practice since they can
usually find high-quality solutions in reasonable computational time for large
scale CNP. Existing ones can be divided into local search methods (Pullan
2015; Aringhieri et al. 2016) and population-based methods (Zhou, Hao, and
Glover 2019; Zhou et al. 2021). However, domain knowledge and trial-and-error
are necessary when designing them, thus requiring considerable efforts and
time.

### Learning-based Methods

Traditional algorithms suffer from specific limitations when applied to
practical challenging tasks. Recent advances in deep learning have shown
promising results of solving NP-hard combinatorial optimization problems
(Kurin et al. 2020; Fan et al. 2020; Barrett et al. 2020). They demonstrate
appealing advantages over traditional algorithms in terms of computational
complexity and scalability.

Inspired by the concept of Graph Convolutional Networks (GCNs) (Kipf and
Welling 2017; Chen et al. 2020; Bae and Jeon 2021), Yu et al. (2020)
innovatively converted the CNP as a regression problem, and proposed an
iterative method to rank nodes by using adjacency matrices of networks and
GCNs. Fan et al. (2020) proposed a generic and scalable Deep Reinforcement
Learning (DRL) framework named FINDER to find key players via GraphSAGE
(Hamilton, Ying, and Leskovec 2017) in complex networks. Kamarthi et al.
(2020) developed a Deep Q-Network (DQN)-based method called geometric-DQN to
use structural properties of the available social networks to learn effective
policies for the network discovery problem to maximize influence on
undiscovered social networks. Zhao et al. (2020) designed a deep learning
model called InfGCN to identify the most influential nodes in a complex
network based on GCNs. Note that most of existing studies focus on identifying
nodes in static networks. To predict critical nodes in temporal networks, Yu
et al. (2021) proposed a dynamic GCN by combining special GCN and a long
short-term memory network. The above mentioned studies have greatly advance
the field, but can they be further improved? This work aims to answer this
question.

## Proposed Method

In this section, we present our FGDD approach to CNP. We first present CNP and
its MDP formulation, and then describe the details of FGDD for solving it.

### Critical Node Problem

Given an undirected graph $G=(V,E)$ with $|V|=n$ nodes and $|E|=m$ edges,
Critical Node Detection Problems (CNDPs) aim to identify a subset of nodes
$S\subseteq V$ such that the removal of these nodes in $S$ maximally degrades
network connectivity of the residual graph denoted as $G[V\backslash S]$
according to some predefined connectivity metrics. A Critical Node Problem
(CNP) is a well-known CNDP (Arulselvan et al. 2009). It aims to find a set of
nodes $S=\\{v_{1},\ldots,v_{K}\\}$ whose removal from $G$ to be removed, which
minimizes the pairwise connectivity of $G[V\backslash S]$. Mathematically, its
objective function $f$ is as follows:

$f(G\setminus S)=\sum_{C_{i}\in G\setminus S}\frac{|C_{i}|(|C_{i}-1|)}{2}$ (1)

where $C_{i}$ is the $i$-th connected component in $G[V\backslash S]$, and
$|C_{i}|$ is the size of connected component $C_{i}$.

### Markov Decision Process Formulation of CNP

Following (Fan et al. 2020), we solve CNP sequentially and formalize it as a
MDP.

  * •

Environment ($G_{\emph{env}}$) is the network being analyzed.

  * •

State ($s_{t}$) is defined as the representation of a residual network at step
$t$. Each state $s_{t}$ presents the hidden information of the residual
network at step $t$ by concatenating feature vectors of all nodes generated by
a node representation algorithm. When the proportion of reduced nodes reaches
a certain value, it would be treated as the end state and finishes this
episode.

  * •

Action ($a_{t}$) is to remove a node $v$ from the current residual network
$G_{t}$.

  * •

Reward ($r(a_{t},t)$) is the decrease of the pairwise connectivity after
taking the action. The optimization objective is to minimize the pairwise
connectivity of the residual network. Thus, the decrease of total pairwise
connectivity between $s_{t}$ and $s_{t+1}$ is set as the step-reward after a
node $v$ be removed. Generally, the reward function could be written as
$r(a_{t},t)=f(s_{t})-f(s_{t+1})$, where $s_{t}$ and $s_{t+1}$ are the states
of residual networks before and after taking action $a_{t}$. However, we
observe that this reward function value is too small to well measure the
difference caused by the action $s_{t+1}$. We modify it and propose a new
reward function as follows.

$r(a_{t},t)=f(s_{0})-f(s_{t+1})$ (2)

where $s_{0}$ is the initial state, and $s_{t+1}$ is the state of residual
networks after taking action $a_{t}$. The intuition behind is that with the
removal of nodes from network, the remaining nodes have more potential to
become critical nodes. Therefore, later removed nodes will contribute more
reward to the agent.

During a Reinforcement Learning (RL) process, FGDD collects the trial-and-
error samples to update its parameters and becomes increasingly intelligent to
solve CNP.

### Our Model

To solve CNP, we propose FGDD that combines feature importance-aware GAT and
dueling DDQN. As shown in Figure 1, it is composed of two phases: encoding and
decoding phases. The former tries to present the state of a whole graph, while
the latter employs these representations to form a score function that
determines the action for a state. More specifically, node representation is
first obtained by a feature importance-aware GAT. A solution of CNP is then
iteratively constructed by a dueling DDQN agent who selects a node to be
removed from current network according to the representation information.

Figure 1: Overview of the FGDD framework.

#### Encoding Phase

Traditional algorithms (Arulselvan et al. 2009; Pullan 2015; Zhou et al. 2021)
usually operate on a testing network and optimize CNP directly. Unlike them,
deep learning methods (Fan et al. 2020; Yu et al. 2020) aim to extract the
features of critical nodes from a large number of networks, and use a well-
trained end-to-end model to predict on all testing networks. In some cases, or
fine-tuning to a specific task is needed. Therefore, how to represent the
contribution of each node to the whole network must be considered.

Compared with network embeddings that target the same task, Graph Neural
Networks (GNNs) (Wu et al. 2020; Li and Zhu 2021; Huang et al. 2021) are
suitable for various different tasks by maintaining a set of neural network
models. Inspired by the success of GNNs to process both inductive (Hamilton,
Ying, and Leskovec 2017; Li and Zhu 2021; Chen et al. 2020) and transductive
(Kipf and Welling 2017) problems, we employ an variance-constrained GAT
(Velickovic et al. 2018) cooperated with a mixture of node’s importance
metrics (obtained by feature aggregation) to develop a feature importance-
aware GAT as our encoding method.

Unlike spectral graph convolutions such as GCN, GAT utilizes an attention
operation on neighboring nodes combined with a self-attention mechanism to
obtain graph information. To make model robust, GAT also adopts multi-head
attention (Zhang, Xu, and Zhao 2020) to aggregate features as well as
transformer model (Vaswani et al. 2017).

The introduction of dropout mechanism in GAT brings much variance. Such
variance is not needed by the general RL (Anschel, Baram, and Shimkin 2017).
To solve CNP, we want our model to be trained on synthetic networks and test
on real-world networks which means we need to retain some variance to improve
the generalization ability. Therefore, we set first layer without any dropout
and set a lower probability for the dropout in another layer compared with
basic GAT. In the following, we explain why the input features are not
expected to drop randomly.

By treating synthetic networks as training data, we need to generate an
initial feature. To learn the importance of each node, our node feature is
initialized by a matrix $\mathcal{R}^{m\times n}$. We first leverage four
metrics (i.e., node degree, degree centrality, eigenvector centrality, and
PageRank) to describe the network as four numerical vectors. Then, a feature
aggregation method is developed to aggregate them into a matrix that well
represents the network information. Yet the aggregated features are limited,
that is why we preserve the whole input features by removing the first dropout
layer. This is why we must preserve the whole input features by removing
dropout in the first layer. Feeding the variance-constrained GAT with both
initial feature and adjacency matrix, after several rounds of recursion, our
encoder concatenates hidden representations from each attention head to obtain
a node representation matrix.

#### Decoding Phase

To select nodes from discrete space, we resort to a Deep Q-Network (DQN) (Mnih
et al. 2015) to estimate the best action with the maximum Q value. After
experimentally evaluating several variants of DQN, we adopt the dueling Double
Deep Q-Network (DDQN) (Wang et al. 2016) architecture as our decoding method.

Our decoder estimates the importance of each action through the output of node
representation. The Q-function is calculated as follows:

$Q(s,a;\theta)=V(s,a;\theta)+A(s,a;\theta)-\frac{1}{|A|}\sum_{a^{\prime}}{A(s,a^{\prime};\theta)}$
(3)

where $s$ is the embedding of node representation and $a$ is an action.
$V(s,a;\theta)$ is the value calculated for current state. $A(s,a;\theta)$
shows the importance of an action to the Q-function compared with other
actions. The action corresponding to the maximum Q-functrion value is then
performed and the corresponding node is removed.

We employ a target network, experience replay buffer and epsilon-greedy
approach to train FGDD as done in (Kamarthi et al. 2020). The combination of
these three mechanisms contribute to improve the learning efficiency and
balance exploration and exploitation of the FGDD framework (Gomes and
Kowalczyk 2009).

### Model Training and Deployment

We train an FGDD model on a randomly generated synthetic network per epoch.
Unlike a real-world network with a given $K$ nodes should be removed, the task
on a synthetic network does not have an exact $K$ value. Therefore, we set the
termination condition of training as removing a certain proportion of nodes.
At the beginning of training phase, the agent selects random nodes from a
residual network with a decaying probability $\epsilon$ to accumulate initial
experience. At each step, the network calculates an attention vector for each
node through aggregated feature $\emph{F}_{\emph{epi}}$ and adjacency matrix
$\mathcal{R}_{\emph{adj}}$. The agent treats representation of current
residual network as input and selects a node to be removed. Algorithm 1
realizes the main training steps of FGDD.

When employing DRL to solve CNP, action space is usually dynamic instead of
fixed ones. It changes along with the removal of nodes, which make it hard to
design the input of a network. To simplify the training process and make nodes
easy to be represented, the network in each step is viewed as a unique network
in our method, and the chosen node from the network would be removed directly.
Before storing the transition experience into a replay buffer, we receive
reward from environment and update the next state by our feature importance-
aware GAT.

Once our model is well trained, we evaluate it on real-world networks. Given a
real-world network with the number of removed nodes $K$, FGDD fixes the weight
of all layers and outputs all $K$ nodes as critical ones. At each step of
inference, it computes node embedding vectors and determines an action
according to the maximum Q-function value. To further accelerate inference, we
remove a batch of nodes in one step when a given network has a large number of
nodes.

Input: Train Graphs $\mathcal{G}=\\{G_{1},G_{2}...,G_{n}\\}$, number of
episodes $N$, number of removed nodes $K$

1 Initialize learn rate $\alpha$ and random factor $\epsilon$;

2 Initialize memory replay buffer $\mathcal{D}$;

3 Initialize current dueling deep Q network with $\theta$;

4 Initialize target dueling deep Q network with $\bar{\theta}=\theta$;

5 Initialize GAT model with random weight $w$;

6 Generate training set $\emph{G}_{\emph{train}}$;

7 for  _episode $=1$ to $N$_ do

8 Perform $\epsilon$ decay;

9
$\emph{G}_{\emph{env}}^{t=0}\leftarrow\emph{sample}(\emph{G}_{\emph{train}})$

10
$\emph{F}_{\emph{epi}}^{t=0}\leftarrow\emph{FeatureAggregation}(\emph{G}_{\emph{env}}^{t=0})$

11
$\emph{S}_{\emph{epi}}^{t=0}\leftarrow$GAT$(\emph{F}_{\emph{epi}}^{t=0},\mathcal{R}_{\emph{adj}}^{t=0}$)

12 while  _not done training_ do

13 Select a random node $v_{t}$ with probability $\epsilon$ else select node
$v_{t}\leftarrow\emph{argmax Q}(\emph{S}_{\emph{epi}}^{t},v;\theta)$;

14 Remove $v_{t}$ and observe new graph $\emph{G}_{\emph{env}}^{t+1}$;

15 Receive reward $r_{t}$;

16 Update
$\emph{F}_{\emph{epi}}^{t+1}\leftarrow\emph{FeatureAggregation}(\emph{G}_{\emph{env}}^{t+1})$;

17 Update state $\emph{S}_{\emph{epi}}^{t+1}\leftarrow$
GAT$(\emph{F}_{\emph{epi}}^{t+1},\mathcal{R}_{\emph{adj}}^{t+1})$;

18 Store
$\\{\emph{S}_{\emph{epi}}^{t},v_{t},r_{t},\emph{S}_{\emph{epi}}^{t+1}\\}$
transition into $\mathcal{D}$;

19 if  _number of removed nodes $=K$_ then

20 Terminate current episode;

21

22 end if

23

24 end while

25 if  _episode $\mod 20=0$_ then

26 Sample random batch $\delta$ from $\mathcal{D}$;

27 Update weight $\theta,w\leftarrow\emph{Adam}(\theta,w,\alpha,\delta)$;

28 if  _number of updates $\mod 300=0$_ then

29 $\bar{\theta}\leftarrow\theta$;

30

31 end if

32

33 end if

34

35 end for

Algorithm 1 Train Network

### Complexity Analysis

The time complexity of FGDD is composed of two parts. Our encoder consists of
a feature aggregation and variance-constrained GAT. The feature aggregation
method tires to aggregate four metrics into a matrix that well represents the
network information. The time complexities of both node degree and degree
centrality are $O(n)$, where $n$ is the number of nodes. The time complexities
of eigenvector centrality and PageRank are $O(n\log n)$ and $O(\xi*m)$
respectively, where $\xi$ is a small constant and $m$ means number of edges.
Therefore, the total time complexity of feature aggregation takes $O(n+n\log
n+m)$. The complexity of variance-constrained GAT is
$O(nll^{\prime}+ml^{\prime})$, where $l$ is the number of input features and
$l^{\prime}$ is the number of features computed by GAT attention head.
Therefore, the complexity of decoding phrase is $O(n+n\log
n+m+nll^{\prime}+ml^{\prime})$. We adopt the dueling DDQN as our decoder, its
complexity can be simplify written as $O(n+n\log n)$ for forward propagation
via fully connect layers and max-Q selection. Generally, the total complexity
of FGDD is $O(n+n\log n+m+nll^{\prime}+ml^{\prime})$.

## Experiments

### Dataset

Our FGDD model is first trained on a large number of small synthetic networks
of 50-150 nodes. To avoid overfitting, after some epoches, we update the
training data with 3,000 new synthetic networks. Note that these synthetic
networks are generated by three widely-used network models (Fan et al. 2020;
Yu et al. 2020; Zhou et al. 2021), i.e., Barabási-Albert, Watts-Strogatz model
and Erdős-Réyi models.

To verify its generalization ability of our FGDD model, we evaluate FGDD on 28
medium and large real-world networks from diverse domains, including 21
networks from widely-used CNP benchmarks (Zhou, Hao, and Glover 2019; Zhou et
al. 2021) and 7 networks from the Network Data Repository (Rossi and Ahmed
2015).

### Baseline Methods

We evaluate FGDD against two categories of baseline methods: traditional
construction heuristic methods and DRL-based methods. Construction methods aim
to remove nodes from network in a greedy or random way. As shown in (Fan et
al. 2020), CI and HDA greedily remove nodes with the highest collective
influence and the highest degree from network, respectively, while RAND
randomly removes nodes from network. DRL-methods construct an end-to-end model
to remove nodes, including FINDER (Fan et al. 2020) and GCN-DRL.

Recently, Graph Convolutional Networks (GCNs) have been successfully applied
to predict influential nodes in complex networks. For example, Yu et al.
(2020) ranked the nodes by their scores and selected nodes greedily via GCN.
Zhao et al. (2020) developed InfGCN consisting of a GCN and three fully
connected layers, which is similar to a combination of GCN and DQN, and used
it to select top influential nodes. Note that existing two GCN-based methods
are not publicly available. Therefore, we merge these two GCN-based methods
and develop a new baseline method, i.e., Graph Convolutional Network based
Deep Reinforcement Learning (GCN-DRL). GCN-DRL shares the same network
architecture with InfGCN. The main difference is that GCN-DRL treates the
three fully-connected layers as a Q-network, and updates the parameters by RL
as well as FINDER. In particular, GCN is used to process graph-structured
data, and three fully-connected layers are employed to select critical nodes.
For other baseline methods, we adopt the best model released by FINDER’s
authors to test without any change. We also use the same implementation of CI
and HDA (Fan et al. 2020).

We present the time complexities of FGDD and five baseline methods in Table 1.
From it, we observe that FGDD is highly competitive compared to FINDER and
GCN-DRL in terms of time complexity. Its time complexity is just slightly
higher than that of FINDER.

Table 1: Comparison of the time complexity Method | Complexity
---|---
FGDD | $O(n+n\log n+m+nll^{\prime}+ml^{\prime})$
FINDER | $O(n+n\log n+m)$
GCN-DRL | $O(n+n\log n+n^{3})$
CI | $O(n^{2}\log n)$
HDA | $O(n\log n)$
RAND | $O(1)$

### Hyperparameter Settings

We run all experiments with Intel E5-2690 CPU and two NVIDIA Tesla P100 GPUs.
For encoders, we utilize eight attention heads for the multi-head GAT model
with two layers. The hidden dimension and output one are set to 60 and 96,
respectively. As aforementioned, we remove the first dropout layer and keep
the second one. The dropout rate is set to 0.3. For decoders, we adopt dueling
DDQN. Both value and advantage networks are implemented as two fully-connected
layers with embedding dimension being 256.

We use the Adam optimizer (Kingma and Ba 2015) to train dueling DDQN and
feature importance-aware GAT with the learning rates 0.001 and 0.005,
respectively. The loss function is mean square error. The eval network is
trained per 20 epochs and the update frequency of a target network is 300. The
models are implemented in PyTorch and Networkx.

### Results

To evaluate FGDD against baseline methods, we conduct three groups of
experiments on real-world networks. First, we report their results on 28 real-
world networks. Second, we improve their results by a simple local search.
Finally, we demonstrate their performance curves under different $K$ values.

#### Results without local search:

Table 2 summarizes the results between our FGDD and five baseline methods on
28 real-world networks, where the best results of each instance are in bold.
In addition, we give the number of instances on which FGDD obtains a better
(Wins), equal (Ties), and worse (Loses) results than the corresponding
baseline algorithms. At its bottom, we also give the p-values of the Wilcoxon
signed ranks test recommend in (Demsar 2006).

Table 2: Results of FGDD and baseline methods on real-world networks.

Instance | #Nodes | #Edges | $K$ | FGDD | FINDER | GCN-DRL | CI | HDA | RAND
---|---|---|---|---|---|---|---|---|---
Bovine | 121 | 190 | 3 | 268 | 268 | 268 | 268 | 268 | 6903
Circuit | 252 | 399 | 25 | 24090 | 11681 | 9874 | 11414 | 11681 | 24626
Ecoli | 328 | 456 | 15 | 1668 | 1579 | 1911 | 2137 | 1668 | 44502
USAir97 | 332 | 2126 | 33 | 15764 | 16041 | 23037 | 15944 | 15944 | 41876
HumanDisease | 516 | 1188 | 52 | 9473 | 1351 | 3094 | 13849 | 1651 | 72280
TreniRoma | 255 | 272 | 26 | 1836 | 2770 | 2501 | 5655 | 1731 | 3775
EU_flights | 1191 | 31610 | 119 | 439460 | 462259 | 537168 | 491543 | 492535 | 545089
openflights | 1858 | 13900 | 186 | 175447 | 182258 | 223573 | 251088 | 193900 | 847617
yeast1 | 2018 | 2705 | 202 | 114829 | 1826 | 1937 | 34468 | 1778 | 925890
Hamilton1000 | 1000 | 1998 | 100 | 393828 | 400067 | 403651 | 402753 | 402753 | 404190
Hamilton2000 | 2000 | 3996 | 200 | 1581531 | 1606530 | 1617301 | 1617301 | 1613706 | 1616942
Hamilton3000a | 3000 | 5999 | 300 | 3555111 | 3614020 | 3643650 | 3630165 | 3638254 | 3640412
Hamilton3000b | 3000 | 5997 | 300 | 3563115 | 3600590 | 3643650 | 3632860 | 3630167 | 3643650
Hamilton3000c | 3000 | 5996 | 300 | 3536470 | 3616710 | 3635557 | 3632861 | 3624779 | 3638793
Hamilton3000d | 3000 | 5993 | 300 | 3549780 | 3627470 | 3638253 | 3622086 | 3622087 | 3642031
Hamilton3000e | 3000 | 5996 | 300 | 3563115 | 3627470 | 3643650 | 3635556 | 3627472 | 3640415
Hamilton4000 | 4000 | 7997 | 400 | 6253422 | 6442260 | 6467406 | 6453028 | 6438666 | 6471004
Hamilton5000 | 5000 | 9999 | 500 | 9876790 | 10068800 | 10113753 | 10100265 | 10100265 | 10106561
powergrid | 4941 | 6594 | 494 | 2922557 | 118780 | 193854 | 1036812 | 76046 | 8320922
OClinks | 1899 | 13838 | 190 | 743619 | 762026 | 831424 | 825000 | 785662 | 1379317
facebook | 4039 | 88234 | 404 | 5400494 | 3771740 | 6190140 | 4688231 | 5339614 | 6586685
email-enron-only | 143 | 623 | 14 | 7750 | 7875 | 8128 | 7876 | 8128 | 8078
email-univ | 1133 | 5451 | 113 | 408161 | 434780 | 448882 | 493522 | 436649 | 504316
soc-wiki-Vote | 889 | 2914 | 89 | 206429 | 203247 | 234976 | 228182 | 208374 | 298125
socfb-Caltech36 | 769 | 16656 | 77 | 209634 | 220786 | 223452 | 222117 | 222117 | 232637
socfb-Reed98 | 962 | 18812 | 96 | 344865 | 365940 | 367653 | 366796 | 366796 | 372299
socfb-Haverford76 | 1446 | 59589 | 145 | 814726 | 840456 | 841753 | 841753 | 841753 | 843571
socfb-Bowdoin47 | 2252 | 84387 | 225 | 1943407 | 2025080 | 2037172 | 2035154 | 2029106 | 2044447
Wins$\mid$Ties$\mid$Loses | $-$ | $-$ | $-$ | $-$ | 20$\mid$1$\mid$7 | 23$\mid$1$\mid$4 | 23$\mid$1$\mid$4 | 20$\mid$2$\mid$6 | 28$\mid$0$\mid$0
p-value | $-$ | $-$ | $-$ | $-$ | 3.25e-2 | 2.30e-3 | 8.80e-3 | 1.33e-2 | 3.79e-6

We observe in Table 2 that our FGDD model shows excellent performance. In
particular, it finds best results on 20 out of 28 networks. Our FGDD wins each
baseline algorithm on at least 20 of 28 networks. At a significance level
0.05, it significantly outperforms two DRL-based algorithms (i.e., FINDER and
GCN-DRL) and three heuristic algorithms (i.e., CI, HDA and RAND).

#### Results with local search:

FGDD can be combined with other existing heuristic search methods to further
improve its performance, which is confirmed by using a recently proposed
Component-Based Neighborhood Search (CBNS) (Zhou, Hao, and Glover 2019). CBNS
is a simple and fast local search, which relies on a focused and reduced
neighborhood by integrating a large component-based node exchange strategy and
a node weighting scheme. In our experiment, the final result of each algorithm
is further improved by CBNS with the stopping condition that the given number
of iterations without improvement is reached, i.e., $\emph{MaxIters}=1000$. We
summarize their improved results in Table 3.

Table 3: Results of FGDD and baseline methods improved by local search on
real-world networks.

Instance | #Nodes | #Edges | $K$ | FGDD | FINDER | GCN-DRL | CI | HDA | RAND
---|---|---|---|---|---|---|---|---|---
Bovine | 121 | 190 | 3 | 268 | 268 | 268 | 268 | 268 | 268
Circuit | 252 | 399 | 25 | 2280 | 2366 | 2635 | 2371 | 2604 | 2527
Ecoli | 328 | 456 | 15 | 806 | 806 | 806 | 806 | 806 | 815
USAir97 | 332 | 2126 | 33 | 5444 | 5484 | 5444 | 5452 | 5444 | 5452
HumanDisease | 516 | 1188 | 52 | 1116 | 1117 | 1119 | 1120 | 1116 | 1121
TreniRoma | 255 | 272 | 26 | 936 | 938 | 947 | 941 | 938 | 947
EU_flights | 1191 | 31610 | 119 | 368879 | 366316 | 367342 | 367173 | 369246 | 365626
openflights | 1858 | 13900 | 186 | 37648 | 38648 | 40260 | 38519 | 39800 | 210305
yeast1 | 2018 | 2705 | 202 | 2015 | 1428 | 1442 | 1683 | 1433 | 33735
Hamilton1000 | 1000 | 1998 | 100 | 377168 | 386240 | 392236 | 3877662 | 391017 | 391907
Hamilton2000 | 2000 | 3996 | 200 | 1554969 | 1578688 | 1576558 | 1589733 | 1572660 | 1591167
Hamilton3000a | 3000 | 5999 | 300 | 3494053 | 3571677 | 3601665 | 3579163 | 3595230 | 3596841
Hamilton3000b | 3000 | 5997 | 300 | 3513109 | 3548200 | 3602736 | 3591477 | 3583437 | 3590938
Hamilton3000c | 3000 | 5996 | 300 | 3490360 | 3561526 | 3577035 | 3579691 | 3576485 | 3591477
Hamilton3000d | 3000 | 5993 | 300 | 3500424 | 3563691 | 3593078 | 3565803 | 3576481 | 3600592
Hamilton3000e | 3000 | 5996 | 300 | 3499888 | 3578618 | 3580767 | 3582904 | 3570615 | 3604888
Hamilton4000 | 4000 | 7997 | 400 | 6253423 | 6412857 | 6412857 | 6378537 | 6368528 | 6401412
Hamilton5000 | 5000 | 9999 | 500 | 9781919 | 9969463 | 10054483 | 10000772 | 10024904 | 10051796
powergrid | 4941 | 6594 | 494 | 74766 | 23562 | 326841 | 37859 | 22050 | 2157729
OClinks | 1899 | 13838 | 190 | 642929 | 643155 | 700939 | 663533 | 654357 | 897544
facebook | 4039 | 88234 | 404 | 4755478 | 3515847 | 5571466 | 3644206 | 5076011 | 5786544
email-enron-only | 143 | 623 | 14 | 5156 | 5156 | 5156 | 5156 | 5156 | 5265
email-univ | 1133 | 5451 | 113 | 371631 | 366138 | 373404 | 375782 | 372315 | 379768
soc-wiki-Vote | 889 | 2914 | 89 | 151780 | 154205.2 | 167470 | 169933 | 157321 | 168593
socfb-Caltech36 | 769 | 16656 | 77 | 189436 | 190064 | 191533 | 192029 | 191660 | 195266
socfb-Reed98 | 962 | 18812 | 96 | 328782 | 339244 | 337434 | 338419 | 338913 | 339904
socfb-Haverford76 | 1446 | 59589 | 145 | 804548 | 824457 | 821894 | 821378 | 825230 | 824974
socfb-Bowdoin47 | 2252 | 84387 | 225 | 1924921 | 1989023 | 1990615 | 2000208 | 1994606 | 2007415
Wins$\mid$Ties$\mid$Loses | $-$ | $-$ | $-$ | $-$ | 20$\mid$3$\mid$5 | 22$\mid$4$\mid$2 | 22$\mid$3$\mid$3 | 21$\mid$5$\mid$2 | 26$\mid$1$\mid$1
p-value | $-$ | $-$ | $-$ | $-$ | 1.19e-2 | 5.61e-5 | 2.70e-3 | 2.62e-4 | 1.23e-5

From Table 3, we observe that FGDD outperforms baseline methods on most of
real-world networks. In particular, it achieves the best results on 22 out of
28 networks. Compared with two DRL-based methods, it finds better results on
at least 21 networks, and equal results on at least 3 networks. Compared to
heuristic search methods, FGDD also shows excellent performance, finding
better results on at least 22 networks, worse result on at most one instance,
and equal results on remaining instances. At a significant level 0.05, FGDD is
significantly better than all five baseline methods. These observations show
that existing heuristic algorithms can also benefit from FGDD.

#### Results under different $K$ values:

Note that results reported in Tables 2-3 are obtained under a fixed $K$ value.
That is, the allowable number of removed nodes is determined in advance. To
further evaluate its effectiveness, we compare the performance curves of FGDD
and five baseline methods under a series of $K$ values on four representative
real-world networks: flight network (i.e., EU_flights), hamiltonian cycles
network (i.e., Hamilton2000), social network (i.e., OClinks) and communication
network (i.e., email-univ). These real-world networks are obtained from
different fields, with node count ranging from 1000 to 2000.

Figure 2: Performance curves of FGDD and baseline methods under different $K$
values.

As shown in Figure 2, FGDD consistently outperforms five baseline methods on
all four networks. These observation confirms the superiority of FGDD over
both DRL-based methods and heuristic methods.

### Ablation Study

To investigate the effectiveness of different components proposed in our FGDD
model, we perform three ablation studies on 7 representative real-world
networks. In our ablation studies, we compare our FGDD model with its three
variants, as shown in Figure 3.

Figure 3: Ablation study on 7 real-world networks. We compare our FGDD method
with its three variants by removing feature aggregation (w/o FA) method,
variance-constrained GAT (w/o VG) module and dueling DDQN (w/o DD) module,
respectively.

We first evaluate the importance of Feature Aggregation (FA) method used in
feature importance-aware GAT. We remove FA, and then initialize the node
feature by only node degree (w/o FA) as well as FINDER (Fan et al. 2020). From
Figure 3, we can observe that FGDD is better than the model without FA. This
suggests that feature aggregation is quite important to model performance.

We next study the benefit of Variance-constrained GAT (VG for short) module
that alters dropout layer mentioned in encoding phase. We replace it with the
original GAT (w/o VG) to explore how variance influences efficiency of FGDD
Comparative results in Figure 3 show that FGDD (with VG) outperforms the model
with original GAT (w/o VG), thus confirming the effectiveness of our variance-
constrained GAT.

Finally, we compare FGDD model with a variant based on basic DDQN (w/o DD)
instead of Dueling DDQN (DD for short). Dueling DDQN can learn which states
are valuable. As shown in Figure 3, the performance of model with basic DDQN
is worse than FGDD (with DD), indicating the significant performance boost
introduced by dueling DDQN.

## Conclusion

This work presents FGDD as a new DRL-based algorithm for a critical node
problem that generalizes well to unseen networks size and structures. FGDD
combines feature importance-aware GAT with dueling DDQN. Empirical results on
28 real-world networks show our method achieves superior performance on real-
world networks. It significantly outperforms both DRL-based methods and
heuristic methods. FGDD can start a search from any valid state, opening the
door to its combination it with other search heuristics, which we have
demonstrated by using a recently proposed component-based neighborhood search.
In addition, our model performs well on social networks and has great
potential to extend to solve other problems in complex networks, e.g., an
influence maximization problem. A limitation of our approach is that it does
not use any supervised information. We plan to employ some supervised
information (e.g., optimal solutions) to guide the model training so that our
model is able to outperform state-of-the-art heuristic algorithms.

## References

  * Anschel, Baram, and Shimkin (2017) Anschel, O.; Baram, N.; and Shimkin, N. 2017.  Averaged-DQN: Variance reduction and stabilization for deep reinforcement learning.  In _ICML_ , 176–185.
  * Aringhieri et al. (2016) Aringhieri, R.; Grosso, A.; Hosteins, P.; and Scatamacchia, R. 2016.  Local search metaheuristics for the critical node problem.  _Networks_ , 67(3): 209–221.
  * Arulselvan et al. (2009) Arulselvan, A.; Commander, C. W.; Elefteriadou, L.; and Pardalos, P. M. 2009.  Detecting critical nodes in sparse graphs.  _Computers & Operations Research_, 36(7): 2193–2200.
  * Bae and Jeon (2021) Bae, I.; and Jeon, H. 2021.  Disentangled multi-relational graph convolutional network for pedestrian trajectory prediction.  In _AAAI_ , 911–919.
  * Baggio et al. (2021) Baggio, A.; Carvalho, M.; Lodi, A.; and Tramontani, A. 2021.  Multilevel Approaches for the Critical Node Problem.  _Operations Research_ , 69(2): 486–508.
  * Bai et al. (2021) Bai, Y.; Xu, D.; Sun, Y.; and Wang, W. 2021.  GLSearch: Maximum common subgraph detection via learning to search.  In _ICML_ , 588–598.
  * Barrett et al. (2020) Barrett, T. D.; Clements, W. R.; Foerster, J. N.; and Lvovsky, A. I. 2020.  Exploratory combinatorial optimization with reinforcement learning.  In _AAAI_ , 3243–3250.
  * Chen et al. (2020) Chen, M.; Wei, Z.; Huang, Z.; Ding, B.; and Li, Y. 2020.  Simple and deep graph convolutional networks.  In _ICML_ , 1725–1735.
  * Demsar (2006) Demsar, J. 2006.  Statistical comparisons of classifiers over multiple data sets.  _Journal of Machine Learning Research_ , 7: 1–30.
  * Di Summa, Grosso, and Locatelli (2011) Di Summa, M.; Grosso, A.; and Locatelli, M. 2011.  Complexity of the critical node problem over trees.  _Computers & Operations Research_, 38(12): 1766–1774.
  * Doostmohammadian, Rabiee, and Khan (2020) Doostmohammadian, M.; Rabiee, H. R.; and Khan, U. A. 2020.  Centrality-based epidemic control in complex social networks.  _Social Network Analysis and Mining_ , 10: 1–11.
  * Fan et al. (2020) Fan, C.; Zeng, L.; Sun, Y.; and Liu, Y.-Y. 2020.  Finding key players in complex networks through deep reinforcement learning.  _Nature Machine Intelligence_ , 2(6): 317–324.
  * Gomes and Kowalczyk (2009) Gomes, E. R.; and Kowalczyk, R. 2009.  Dynamic analysis of multiagent q-learning with epsilon-greedy exploration.  In _ICML_ , 369–376.
  * Hamilton, Ying, and Leskovec (2017) Hamilton, W. L.; Ying, Z.; and Leskovec, J. 2017.  Inductive representation learning on large graphs.  In _NIPS_ , 1024–1034.
  * Harrold, Ramanathan, and Mager (2013) Harrold, J.; Ramanathan, M.; and Mager, D. 2013.  Network-based approaches in drug discovery and early development.  _Clinical Pharmacology & Therapeutics_, 94(6): 651–658.
  * Huang et al. (2021) Huang, C.; Xu, H.; Xu, Y.; Dai, P.; Xia, L.; Lu, M.; Bo, L.; Xing, H.; Lai, X.; and Ye, Y. 2021.  Knowledge-aware coupled graph neural network for social recommendation.  In _AAAI_ , 4115–4122.
  * Kamarthi et al. (2020) Kamarthi, H.; Vijayan, P.; Wilder, B.; Ravindran, B.; and Tambe, M. 2020.  Influence maximization in unknown social networks: Learning policies for effective graph sampling.  In _AAMAS_ , 575–583.
  * Khalil et al. (2017) Khalil, E. B.; Dai, H.; Zhang, Y.; Dilkina, B.; and Song, L. 2017.  Learning combinatorial optimization algorithms over graphs.  In _NIPS_ , 6348–6358.
  * Kingma and Ba (2015) Kingma, D. P.; and Ba, J. 2015.  Adam: A method for stochastic optimization.  In _ICLR_.
  * Kipf and Welling (2017) Kipf, T. N.; and Welling, M. 2017.  Semi-supervised classification with graph convolutional networks.  In _ICLR_.
  * Kurin et al. (2020) Kurin, V.; Godil, S.; Whiteson, S.; and Catanzaro, B. 2020.  Can Q-learning with graph networks learn a generalizable branching heuristic for a SAT solver?  In _NeurIPS_.
  * Li and Zhu (2021) Li, M.; and Zhu, Z. 2021.  Spatial-temporal fusion graph neural networks for traffic flow forecasting.  In _AAAI_ , 4189–4196.
  * Li, Chen, and Koltun (2018) Li, Z.; Chen, Q.; and Koltun, V. 2018.  Combinatorial optimization with graph convolutional networks and guided tree search.  In _NeurIPS_ , 537–546.
  * Mnih et al. (2015) Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M. G.; Graves, A.; Riedmiller, M.; Fidjeland, A. K.; Ostrovski, G.; et al. 2015\.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540): 529–533.
  * Pullan (2015) Pullan, W. 2015.  Heuristic identification of critical nodes in sparse real-world graphs.  _Journal of Heuristics_ , 21(5): 577–598.
  * Rossi and Ahmed (2015) Rossi, R. A.; and Ahmed, N. K. 2015.  The network data repository with interactive graph analytics and visualization.  In _AAAI_ , 4292–4293.
  * Shen and Smith (2012) Shen, S.; and Smith, J. C. 2012.  Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs.  _Networks_ , 60(2): 103–119.
  * Shen et al. (2012) Shen, Y.; Nguyen, N. P.; Xuan, Y.; and Thai, M. T. 2012.  On the discovery of critical links and nodes for assessing network vulnerability.  _IEEE/ACM Transactions on Networking_ , 21(3): 963–973.
  * Summa, Grosso, and Locatelli (2012) Summa, M. D.; Grosso, A.; and Locatelli, M. 2012.  Branch and cut algorithms for detecting critical nodes in undirected graphs.  _Computational Optimization and Applications_ , 53(3): 649–680.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017.  Attention is all you need.  In _NIPS_ , 5998–6008.
  * Velickovic et al. (2018) Velickovic, P.; Cucurull, G.; Casanova, A.; Romero, A.; Liò, P.; and Bengio, Y. 2018.  Graph attention networks.  In _ICLR_.
  * Wang et al. (2016) Wang, Z.; Schaul, T.; Hessel, M.; Hasselt, H.; Lanctot, M.; and Freitas, N. 2016\.  Dueling network architectures for deep reinforcement learning.  In _ICML_ , 1995–2003.
  * Wu et al. (2020) Wu, Z.; Pan, S.; Chen, F.; Long, G.; Zhang, C.; and Philip, S. Y. 2020.  A comprehensive survey on graph neural networks.  _IEEE Transactions on Neural Networks and Learning Systems_ , 32(1): 4–24.
  * Yu et al. (2020) Yu, E.; Wang, Y.; Fu, Y.; Chen, D.; and Xie, M. 2020.  Identifying critical nodes in complex networks via graph convolutional networks.  _Knowledge-Based Systems_ , 198: 105893.
  * Yu et al. (2021) Yu, E.-Y.; Fu, Y.; Zhou, J.-L.; Sun, H.-L.; and Chen, D.-B. 2021.  Predicting critical nodes in temporal networks by dynamic graph convolutional networks.  _arXiv preprint arXiv:2106.10419_.
  * Zhang et al. (2020) Zhang, W.; Liu, K.-y.; Sheng, W.; Du, S.; and Jia, D. 2020.  Critical node identification in active distribution network using resilience and risk theory.  _IET Generation, Transmission & Distribution_, 14(14): 2771–2778.
  * Zhang, Xu, and Zhao (2020) Zhang, Y.; Xu, B.; and Zhao, T. 2020.  Convolutional multi-head self-attention on memory for aspect sentiment classification.  _IEEE/CAA Journal of Automatica Sinica_ , 7(4): 1038–1044.
  * Zhao et al. (2020) Zhao, G.; Jia, P.; Zhou, A.; and Zhang, B. 2020.  InfGCN: Identifying influential nodes in complex networks with graph convolutional networks.  _Neurocomputing_ , 414: 18–26.
  * Zhou et al. (2021) Zhou, Y.; Hao, J.; Fu, Z.; Wang, Z.; and Lai, X. 2021.  Variable population memetic search: A case study on the critical node problem.  _IEEE Transactions on Evolutionary Computation_ , 25(1): 187–200.
  * Zhou, Hao, and Glover (2019) Zhou, Y.; Hao, J.; and Glover, F. W. 2019.  Memetic search for identifying critical nodes in sparse graphs.  _IEEE Transactions on Cybernetics_ , 49(10): 3699–3712.