Enhancing Network by Reinforcement Learning and Neural Confined Local Search

1 Introduction

Modern society has become increasingly dependent on the availability of networked systems, such as power grids, communication networks, traffic networks, and so on. Network robustness, which measures the ability of networks to maintain reliable operation in the presence of attacks [Ellens and Kooij, 2013], has attracted more and more attention because for many real-world networks, failures of a small number of nodes may cause the malfunction of the entire network [Albert et al., 2000; Holme et al., 2002; Wang and Rong, 2009]. The underlying reason is that robustness is not sufficiently considered when designing these networks. It has been found that the robustness of a network is determined by its structure [Albert et al., 2000]. Thus a natural question is: Can we improve the robustness of a given network as much as possible by slightly modifying its structure? We call this problem the Network Enhancement Problem (NEP).

∗Corresponding author.

This paper considers a specific set of NEP, as in [Darvariu et al., 2021], while our methods apply in more generalized settings. First, we specify the network robustness of a given network G against an attack algorithm A as R(G) = Eξ∼A(G) p(G, ξ)1 , where p(G, ξ) is the minimum fraction of nodes that must be removed from G in the order ξ to disconnect it. Note A is required in the definition because even the same network may show different levels of robustness under different attack algorithms. For instance, a scale-free network [Barab´asi and Albert, 1999; Faloutsos et al., 1999] is robust to random attack and vulnerable to targeted attack [Albert et al., 2000]. Second, we consider adding a certain number of links in a network to improve its robustness.

Existing methods can be divided into two categories: heuristic methods [Beygelzimer et al., 2005; S´anchez Mart´ınez, 2009; Wang and Van Mieghem, 2010; Wang et al., 2014; Li et al., 2018] and the Reinforcement Learning (RL) based method [Darvariu et al., 2021]. In the next section, we will review heuristic methods in detail. As we will see, developing a heuristic algorithm often requires extensive expert domain knowledge. In addition, the performance of a hand-engineered heuristic is often limited by the designer's intuition and experience. In contrast, the RL based method, named NEP-DQN [Darvariu et al., 2021], models the problem in the Markov Decision Process (MDP) framework and learns end-to-end solutions with DQN [Mnih et al., 2013]. With NEP-DQN, complex decision rules that are hard to specify by hand are automatically discovered through trial and error.

Although NEP-DQN performs better on InDistribution (ID) datasets than hand-engineered heuristics , it lacks the ability to generalize well for Out-OfDistribution (OOD) scenarios when enhancing networks against the degree-based targeted attack, i.e., removing nodes from a network in decreasing order of their degree. Towards a more effective decision model with stronger generalization ability, we incorporate domain knowledge to improve both the state and action representations, which are crucial in the decision-making process. In particular, we introduce measurements from the field of complex networks, such as various centrality measures [Barrat et al., 2004] to characterize the local neighborhood structure of a node. We also use decision criteria of hand-engineered heuristics, such as degree product, distance, and algebraic distance [Fiedler, 1973] to characterize the node pairs. To capture the global position of nodes in the network, we assign a two-dimensional coordinate to each node using the eigenvectors of the graph Laplacian such that adjacent nodes are mapped to neighboring points in the coordinate space. We solve NEP by adapting the Attention Model (AM) [Kool et al., 2018], i.e., adding a feature extraction module to AM. We call the adapted model NEP-AM. NEP-AM uses the network structure information indirectly through the introduced features. To directly utilize the network structure information, we add a structure-aware attention module [Shi et al., 2020] that only allows nodes to query local neighbors to NEP-AM. Thus the resulting model is a hierarchical attention model, i.e., the query range changes from local to global. We name it NEP-HAM.

1 A comprehensive discussion of various robustness measures can be referred to [Liu et al., 2017].

Let l be the edge budget. A solution can be represented as a node sequence of length 2l. The k-opt local search [Aarts et al., 2003] is generally used to improve a solution further. The solution is iteratively improved until a local optimum is achieved. In each iteration, we search the k-exchange neighborhood for a better candidate to replace the current solution. The k-exchange neighborhood contains feasible solutions that are obtained by exchanging k nodes of the current solution. The size of the k-exchange neighborhood is O((2l k )nk ), where n is the number of nodes of the network. In practice, k is usually set as a small value so that the algorithm can finish in a reasonable amount of time [Ma et al., 2019]. However, removing this constraint can lead to better solutions by exploring a larger neighborhood. To this end, we propose Neural Confined Local Search (NCLS). In particular, we define the restricted k-exchange neighborhood by restricting the selection of k nodes to be consecutive. The size of the restricted k-exchange neighborhood is O(2lnk ). However, examining all candidates in the restricted k-exchange neighborhood is also infeasible, especially when k is large. Hence, we use a learned policy πθ to generate a neural confined neighborhood that includes high-quality candidates decoded from πθ. The neural confined neighborhood is a subset of the restricted k-exchange neighborhood and of size O(2lη), where η is a hyperparameter that balances effectiveness and efficiency. NCLS effectively searches the restricted k-exchange neighborhood by only examining candidates in the neural confined neighborhood, which will be illustrated by experiments.

In the experiment, we compare our models with heuristics and NEP-DQN on synthetic and real networks using two attack algorithms. We evaluate the ID and OOD generalization ability on synthetic networks, and the active search [Bello et al., 2016] on real networks. For NCLS, we set large values for k to test whether it can realize the effective search of large neighborhoods. Additionally, we visualize the validation results during the entire training process, where we study the impact of node coordinates. Our results show that: 1) NEPAM outperforms baselines in almost all cases. In particular, it has a much stronger OOD generalization ability than NEPDQN; 2) NEP-HAM performs better than or comparable to NEP-AM in most cases; 3) NCLS can improve the quality of solutions by effectively searching large neighborhoods; 4) Node coordinates are crucial for NEP-AM and provide additional information for NEP-HAM.

To summarize, our contributions are as follows.

1. Towards a more effective decision model with stronger generalization ability, we propose NEP-AM, where domain knowledge is incorporated to improve both the state and action representations. To directly utilize the network structure, we propose NEP-HAM by adding a structure-aware attention module to NEP-AM.
2. To further improve the solving of NEP, we propose NCLS, which exploits a learned policy to effectively search a large neighborhood. Specially, it realizes the effective search of the restricted k-exchange neighborhood of size O(2lnk ) by examining its subset of size O(2lη), i.e., the neural confined neighborhood.
3. We demonstrate the superiority of NEP-AM/HAM through extensive experiments, including the evaluation of the ID, OOD generalization ability, and active search. We verify NCLS's ability to search larger neighborhoods. In addition, we compare validation curves and assert the importance of providing node coordinates.

2 RelatedWork

Network robustness is a wide-ranging area of research that began around 20 years ago. NEP is one of the most important research topics in network robustness and has attracted increasing attention due to its applicability in realworld applications. There are many works addressing NEP by designing heuristic algorithms [Beygelzimer et al., 2005; S´anchez Mart´ınez, 2009; Wang and Van Mieghem, 2010; Wang et al., 2014; Li et al., 2018]. These methods insert an edge between the current best unconnected pair of nodes, where the quality of an unconnected pair of nodes is measured by some criterion, and repeat this process until the end. Let L be the graph Laplacian and λ2(L) be the second smallest eigenvalue of L. Criteria in [Beygelzimer et al., 2005; S´anchez Mart´ınez, 2009; Wang and Van Mieghem, 2010; Li et al., 2018] are designed to maximize λ2(L), which is called algebraic connectivity in the network jargon. The rationale lies in that the algebraic connectivity is a lower bound of node connectivity [Fiedler, 1973], reflecting the robustness of a network under the strongest attack algorithm, which involves identifying the minimum number of nodes that must be removed to disconnect the network. Since a network G's smallest degree provides an upper bound of its algebraic connectivity [Fiedler, 1973], the smallest degree has been used as a surrogate objective to maximize λ2(L). For instance, in each step, a link is added to unconnected nodes with lowest degrees [Beygelzimer et al., 2005] or between the minimum degree node and a random chosen node [S´anchez Mart´ınez, 2009]. To optimize λ2(L) directly, a useful property is that the improvement of λ2(L) by inserting (u, v) can be approximated by |eu - ev|2 , where e is the eigenvector of L corresponding to λ2(L) [Ghosh and Boyd, 2006]. To exploit this property, in each step, [Wang and Van Mieghem, 2010] adds a link between unconnected u, v with the maximal algebraic distance dA(u, v) = |eu - ev|. [Li et al., 2018] finds that in a special class of graphs, two nodes maximizing the algebraic distance are the ones with minimum local centrality and maximum distance. They thus propose a criterion based on their finding. Other than algebraic connectivity, the criterion in [Wang et al., 2014] is built based on effective resistance Ω(u, v) = (ˆL-1 )v,v + (ˆL-1 )u,u - 2(ˆL-1 )v,u, where ˆL-1 is the pseudo inverse of L [Ellens et al., 2011]. Intuitively, for a node pair with few alternative and longer paths, its effective resistance will be larger than that with a high number of alternative and short paths. Thus, the unconnected nodes with maximum effective resistance, i.e., argmaxu,v Ω(u, v), are selected in [Wang et al., 2014]. From the above introduction, we can see that the design of a heuristic algorithm is a complex task requiring extensive domain knowledge. In addition, the performance of a heuristic is often limited by the designer's intuition and experience.

In recent years, machine learning techniques are increasingly being used to solve combinatorial optimization problems, such as Travelling Salesman Problem [Vinyals et al., 2015; Bello et al., 2016; Deudon et al., 2018; Kool et al., 2018], KnapSack [Bello et al., 2016], Vehicle Routing Problem [Nazari et al., 2018; Kool et al., 2018], Maximum Cut [Khalil et al., 2017], and so on. These methods can be divided into two categories: supervised learning based and RL based. However, supervised learning does not apply to NEP since the optimal labels are unavailable. [Darvariu et al., 2021] proposes an RL based method NEP-DQN, which uses a neural network Qθ(s, v) to estimate the optimal action-value function. In particular, a graph neural network [Dai et al., 2016] is employed to extract the representations of state and action, where the raw feature of a node is a binary variable indicating whether the node is an edge stub. These representations are used to calculate the actionvalue function. θ is trained based on a variant of DQN [Mnih et al., 2013]. After training, the node chosen under state s is given by π(s) = argmaxv Qθ(s, v). However, the domain knowledge is completely ignored in NEP-DQN, which causes its poor OOD generalization ability. In contrast, our proposed methods exploit domain knowledge to improve the representations of state and action, which are essential for the decision process. Previous work [Hu et al., 2019] has also considered the confine of the neighborhood of 1-opt local search. However, their method can not be directly generalized to larger k. Some studies, including [Wu et al., 2021; Ma et al., 2021], focus on using RL to learn improvement heuristics directly, rather than using pre-trained models to guide classical improvement heuristics as in our work.

3 Methodology

In this section, we first describe the decision process and then present our proposed NEP-AM and NEP-HAM. Finally, we introduce the NCLS.

3.1 The Decision Process and Policy Learning

Let G be the network to enhance, V = {1, 2 · · · , n} be the node set consisting of n nodes. Given the edge budget l, there are 2l steps in the decision procedure. At each step, the agent observes a state, decides which node to choose, and then acts to change the state. Specifically, for 0 ≤ t ≤ l - 1, the state s2t is a tuple (G2t, ∅), where G2t = G ⊕ {(v2i, v2i+1)}t-1 i=0 is obtained by adding edges {(v2i, v2i+1)}t-1 i=0 into G, v0, v1, · · · , v2t-1 are nodes chosen in previous steps, ∅ means there is no edge stub. After observing s2t, the agent chooses an edge stub v2t and enters a new state s2t+1 = (G2t+1, {v2t}), where G2t+1 = G2t. Then the agent chooses v2t+1 and insert (v2t, v2t+1) into G2t+1 so that G2t+2 = G2t+1 ⊕{(v2t, v2t+1)}. The agent repeats this process to the final step and receives a reward as the robustness improvement of G2l against G.

Let πθ be a parameterized policy, where θ refers to the parameters of a model. We learn πθ by maximizing the expected reward:

where τ = (s0, v0, · · · , s2l-1, v2l-1) is a trajectory. R(τ) is the robustness improvement of the final network G2l against G. We use the REINFORCE [Williams, 1992] to estimate the gradient and introduce a baseline b(s) to reduce the variance:

where τ is sampled from πθ and '∼' means the right-hand side is an unbiased estimator of the gradient.

3.2 NEP-AM

NEP-AM consists of three parts: a feature extraction module that extracts node features, an encoder that generates node and state representations from the extracted features, and a decoder that makes decisions based on the node and state representations. We discuss these three parts in detail below.

Feature Extraction Module

High-quality state and action representations help improve the policy's performance. We introduce the following two kinds of features 2 . The first type, aiming to characterize the local structure near a node, includes centrality measures (the degree centrality and the average neighbor degree) and the clustering coefficient. Centrality measures, with a strong ability to distinguish nodes, have been widely used to identify critical nodes in complex networks [Liu et al., 2016]. The clustering coefficient complements centrality measures by characterizing the presence of loops in the local neighborhood [Costa et al., 2007]. The goal of the second type is to describe the relative relationship between the edge stub and the other nodes. Inspired by heuristics [Wang and Van Mieghem, 2010; Li et al., 2018], we compute the distance, product of degree, and algebraic distance between the considered node pairs. And we adopt the Jaccard coefficient [L¨u and Zhou, 2011] to characterize the similarity between the considered node pairs. All statistics are normalized between 0 and 1. In addition, to capture the global position of nodes in the network, we project them into a two-dimensional coordinate space by using the eigenvectors associated with the two smallest nonzero eigenvalues of the graph Laplacian, which has the property that adjacent nodes have smaller Euclidean distances in the coordinate space. We will illustrate the indispensable role of node coordinates through experiments.

2 We provide a detailed introduction to the feature selection in the appendix.

Encoder

The encoder generates low-dimensional representations for states and actions. The critical step involves computing node representations from the raw features. For node 1 ≤ i ≤ n, we put all extracted features into a vector xi, perform a linear transformation to map xi to the initial representation hi, and process hi by multiple transformer layers [Vaswani et al., 2017]. Let o be the number of transformer layers. For 1 ≤ j ≤ o, the computation steps in the j-th layer are listed in (3).

where hj-1 i is the representation of i-th node produced by the j -1-th layer and h0i = hi. MHA refers to the multi-head attention mechanism [Vaswani et al., 2017]. In each head, hj-1 i is mapped into a query, {hj-1 1 , · · · , hj-1 n } are mapped into keys and values, and comparabilities between the query and keys are computed to combine the values into an embedding for node i. Embeddings of node i on all heads are linearly projected to the single representation ˆhji . BN1 and BN2 are batch normalization modules [Ioffe and Szegedy, 2015] with learnable affine parameters. FF is the point-wise feedforward network.

During the 2t-th step of the decision process, the action representation of selecting node i is the representation of node i, i.e., hoi , computed from G2t by the procedure described above. The state s2t is represented as hs = [hG, he], where the graph embedding hG is obtained via the sum or mean of all node embeddings, he is the default vector when there is no edge stub. The representation for s2t+1 is computed similarly, the only difference is that he is replaced by the node representation of the edge stub.

Decoder

The decoder makes decisions based on the state representation hs and node representations {hoi }ni=1 . In the first step, the decoder computes a glimpse as below.

where MHA is almost the same as described above, except that the compatibility of a node is masked as -∞ if the node is infeasible. At step 2t, nodes with degree equal to n-1 are infeasible; at step 2t+1, nodes that are connected to the edge stub are infeasible.

In the second step, the glimpse g is mapped into query q, the node embedding hoi is mapped into key ki. The compatibility ui is computed as below:

where d is the dimension of the query, C is a hyperparameter to balance exploration and exploitation [Bello et al., 2016]. Finally, the compatibilities are transformed by a Softmax operator into probabilities.

3.3 NEP-HAM

In the encoder of NEP-AM, initial node embeddings hi, which are indirectly computed from the network structure through extracted features, are used as the input of multiple transformer layers. One way to improve the performance is to make the input directly depend on the network structure. To this end, we add a structure-aware multi-head attention module [Shi et al., 2020] before the multiple transformer layers, where node i queries its first order neighbors and combines their values in the added module. The resulting NEP-HAM model is a hierarchical attention model, i.e., the query range changes from local to global. Compared to NEP-AM, NEPHAM enables the direct utilization of the network structure.

3.4 Neural Confined Local Search

Given an initial solution, k-opt local search is a commonly used technique to improve the solution. As stated in the introduction, k is restricted to a small value to maintain a reasonable running time. To remove this restriction, we propose NCLS to realize the effective search of a restricted kexchange neighborhood of size O(2lnk ) by only examining candidates in the neural confined neighborhood of size O(2lη), where η is a hyperparameter to balance effectiveness and efficiency. We can take a large k for the number of candidates to check is independent of k.

Now we introduce the details of NCLS. Let wp = {p, (p + 1)%2l, · · · , (p + k - 1)%2l} be the index set of exchangeable nodes, where p is the starting index. Let F be the set of all feasible solutions, v = {v1, v2, · · · , v2l} be a feasible solution. We define the restricted k-exchange neighborhood as N (v) = ∪2l p=1Np(v), where Np(v) is defined as below.

It is clear that the size of N(v) is O(2lnk ) and an exhaustive enumeration over N(v) is unfeasible for large k. To confine N(v), we first apply the partial solution v′ = {vi : ∀1 ≤ i ≤ 2l, i /∈ wp} to G and obtain a state s′ . Then we generate η groups of nodes {(vi1 , · · · , vik )}ηi=1 by a learned policy πθ from s′ . We can either sample these groups from πθ or perform a beam search. All solutions that can be obtained by replacing exchangeable nodes with a node group form the neural confined neighborhood. Thus, the neural confined neighborhood is of size O(2lη). The rationale behind NCLS is that we can decode high-quality groups from a learned policy.

4 Experiments

The main goal of this section is to provide answers to the following research questions. RQ1: Does NEP-AM outperform previous baselines? RQ2: How does the performance of NEP-HAM compare with NEP-AM? RQ3: Can NCLS effectively search the restricted k-exchange neighborhood? RQ4: How important are node coordinates to the performance of NEP-AM/HAM?

4.1 Datasets

We use synthetic networks generated from graph models and real-world networks. The first model is Barab´asi-Albert (BA) model [Barab´asi and Albert, 1999]. An instance is generated according to the growth and preferential attachment mechanisms, where newly added nodes preferentially attach to M existing nodes with probabilities proportional to the degrees of those nodes. The second model is Erd˝os-R´enyi (ER) model [Erdos et al., 1960]. An instance is generated by uniformly sampling from the set consisting of all networks with n nodes and m edges. To evaluate RL pretraining, which is introduced below, we generate networks of 3 different sizes: 20, 100, and 500. We set M = 2 for BA and m = p × (n2 ) for ER, where p is set as 0.2 for 20, 100, and 0.015 for 500.

We take 10 real-world networks: the road networks in Kazakhstan, Poland, Romania, Finland, and Turkey, and the power grids in the Switzerland, Czech Republic, United Kingdom, Hungary, and Sweden 3 . For convenience, we abbreviate these country names by country codes in the following paper, i.e., KZ, PL, RO, FI, TR, CH, CZ, GB, HU, and SE.

4.2 ComparingMethods and Parameter Setup

As in [Darvariu et al., 2021], we set up two attack algorithms: the first is the degree-based targeted attack, as we mentioned before; the second is the random attack, known as random failures in the network jargon, where nodes are removed in random order. We compare with 5 baselines, including 4 heuristics and NEP-DQN. Heuristics, involving Greedy, LDP [Wang et al., 2014], FV [Wang and Van Mieghem, 2010], and ERes [Wang et al., 2014] have been introduced in the related work section. Their criteria are formally listed below.

3 All real-world networks are available at this URL. All source code is available at this github repository.

where deg(u) is the degree of u, dA(u, v) is the algebraic distance between u, v, Ω(u, v) is the effective resistance between them. For each method, we evaluate the Robustness Improvement (RI):RI(G) = R( ¯G) - R(G) (8)

where ¯G is the network enhanced by the method.

For NEP-AM and NEP-HAM, we set the initial embedding dimension dhi = 32, the number of transformer layers o = 3. In MHA, the number of heads is set as H = 8, the key and value dimensions are set to dk = dv = dhi /H. The number of hidden neurons in FF is set as 512. The C in (5) is set to 10. Models are trained using Adam optimizer; the batch size is fixed at 128, and the learning rate is fixed at 1e - 4. Other hyperparameters, such as max norm of the gradients (1.0 or ∞), set pooling function (sum or mean) to compute the graph embedding hG, baseline function b(s) in (2) (the exponential or greedy rollout baseline [Kool et al., 2018]), are adjusted to optimize the performance of our models. The experiments are conducted on a server (56-core Intel Xeon Gold 6348 CPU 2.60GHz, 1T RAM, 8 NVIDIA A100 GPUs) under the Python 3.9.12 and PyTorch 1.12.1 environments.

4.3 Evaluation of RL Pretraining (RQ1 &RQ2)

Our goal in RL pretraining is to test the ability of a pre-trained model to generalize to both ID and OOD test sets. To this end, we conduct experiments on synthetic networks. We generate a training set, a validation set, an ID test set, and two OOD test sets for each network model. The training set consists of 214 networks, while both the validation set and the test set consist of 27 networks. The network size in the training, validation, and ID test sets is 20, while the network size in the first/second OOD test set is 100/500. For each network, the edge budget is set as a percentage τ of the maximal possible number of edges, i.e., the number of edges to insert is l = (n2 )τ. We set the values of τ as 1%, 2.5%, and 5% for networks with 20 or 100 nodes, and decrease these values for networks with 500 nodes to 0.05%, 0.1%, and 0.2% to mitigate the expensive computation cost. We train a model for each attack method, network model, and edge budget combination. The training steps are set as 400k, 300k, and 200k for τ = 1%, 2.5%, 5%, respectively. We then choose the pretrained model with the best validation performance for each combination and report the best performance achieved by the pre-trained models for each OOD test set.

Table 1 displays the average RIs against both targeted and random attacks. The results for targeted (random) attack are outside (inside) the parentheses. Dashes are used to indicate unavailable solutions due to the unbearable computational time. We use names like "BA-100" ("OOD-100") to represent the BA (OOD) test set consisting of networks with 100 nodes.

Targeted attack. We make the following observations regarding the targeted attack from Table 1. 1) In the ID test set, NEP-DQN performs better or comparable to all heuristics. NEP-AM improves the results of NEP-DQN for nearly all cases, and the maximum relative increase of average RI (17.99%) is reached at BA-20, τ=5%. 2) In the OOD test sets, NEP-DQN is beaten by FV and ERes in most cases and performs significantly worse than LDP in all cases. In particular, its performance degrades severely at BA-500, where no robustness improvements are obtained. In comparison, NEP-AM works better than the best-performing heuristic (LDP) in almost all cases. For instance, NEP-AM outperforms LDP by 33.33% for BA-500 at τ=0.1% and by 57.07% ∼ 84.44% (51.53% ∼ 61.22%) for ER-100 (ER500). The only case where LDP achieves a non-marginal improvement (18.31%) over NEP-AM is BA-500 at τ=0.2%. In addition, NEP-AM can generate meaningful solutions even for BA-500 at τ=0.05%, where all baselines fail to yield improvements. 3) For ID and OOD-100, NEP-HAM performs better than NEP-AM in almost all cases, especially for the ER model. For instance, compared with NEP-AM, average RIs brought by NEP-HAM have a relative increase of 8.53% and 8.22% for ER-20 at τ = 1%, 5%, and of 19.28% for ER100 at τ = 1%. One possible reason is that, compared to BA networks, the features are more evenly distributed across nodes in ER networks, making the network structure information more important. And in NEP-HAM, the network structure directly affects node representations by determining the local query range. However, this direct dependence on network structure harms the generalization ability of NEP-HAM when applied to larger networks. This is evidenced by the worse performance of NEP-HAM compared to NEP-AM on ER-500. Despite this, NEP-HAM still outperforms LDP on OOD-500 except at BA-500, τ=0.2%.

Random attack. We make the following observations regarding the random attack from Table 1. 1) The observations for the ID test set are similar to those for the targeted attack. However, the relative improvements of NEP-AM compared to NEP-DQN against the random attack (1.35% ∼ 3.08%) are less evident than those (0.78% ∼ 17.99%) against the targeted attack. The reason, as pointed out by [Darvariu et al., 2021], is that improving network robustness against the random attack is a simpler task than against the targeted attack such that: a) even heuristics are enough to generate competitive solutions and b) a learned policy can only obtain a limited performance improvement. 2) In OOD-100, NEP-DQN provides better or at least comparable performance than the best baseline (ERes), which differs significantly from the situation observed under the targeted attack. An explanation is that generalization to OOD-100 for the challenging task (improving against the targeted attack) requires a more effective decision model than for the easy task (improving against the random attack). NEP-AM outperforms NEP-DQN by 4.01%∼ 15.73% on OOD-100. In OOD-500, NEP-AM outperforms over NEP-DQN in all cases (0.37% ∼ 58.33%) except at ER-500, τ = 0.05% and ER-500, τ = 0.1%, where the differences are small (less than 2.3%). However, competitive heuristics (LDP and ERes) perform best for OOD-500. That is because the severely changed network structures degrade the performance of NEP-AM such that the competitive heuristics beat it. 3) In the ID test set, NEP-HAM outperforms NEP-AM in all cases (0.75% ∼ 5.25%) except at ER20, τ = 1%, where the average RI of NEP-HAM is 1.89% lower than that of NEP-AM. For OOD-100, NEP-HAM performs on par with NEP-AM. For instance, they have the same result values on ER-100. For OOD-500, the average RIs of NEP-HAM are 0.37% ∼ 26.32% lower than that of NEP-AM in all cases, except for BA-500, τ = 0.2%, where NEP-HAM outperforms NEP-AM by 21.52%.

Conclusions. 1) In the ID test set, NEP-AM outperforms all baselines for both attack methods, and NEP-HAM further surpasses NEP-AM. 2) When it comes to OOD test sets, NEP-AM shows better generalization ability than NEP-DQN, especially for the targeted attack where NEP-AM outperforms the best-performing heuristic in almost all cases. NEPHAM performs better than or comparable to NEP-AM in OOD-100. Although directly utilizing network structure information contributes to the performance gain of NEP-HAM, it hinders its generalization to more severely changed network structures, i.e., OOD-500. 3) NEP-AM/HAM also suffers from performance degradation on OOD test sets. One potential solution is to include a competitive heuristic, e.g., LDP, as a sub-policy of the decision model such that the heuristic can be utilized when a significant distribution shift is detected. We will explore this solution in future work.

4.4 Evaluation of Active Search (RQ1 &RQ2)

In active search [Bello et al., 2016], we focus on testing a model's ability to solve a single instance, which involves continuously optimizing the model's parameters while keeping track of the best solution. We test our models on real networks, with a fixed τ value as 2.5%. The edge budget is computed using the same method in RL Pretraining. All models (including NEP-DQN) are trained for 50k steps 4 . We try NEP-AM/HAM with or without the entropy regularization [Haarnoja et al., 2018] and report the best results. For entropy regularization, we set the target entropy to -n, initialize the dual variable α to 10, and fix the learning rate for α to 1e - 4. We present the results in Table 2, where the results regarding targeted (random) attack are outside (inside) the parentheses. For NEP-DQN performs significantly better than heuristics on real networks, we mainly compare our models with NEP-DQN in the discussion below.

Targeted attack. We analyze the results regarding the targeted attack in Table 2 as below. 1) In 7 (8) out of 10 real networks, NEP-AM (NEP-HAM) outperforms NEP-DQN significantly with a relative increase of RIs ranging from 5.40% (9.90%) to 112.37% (125.27%). On SE, NEP-AM performs slightly worse than NEP-DQN with -0.32% lower RI, while NEP-HAM outperforms NEP-DQN by 9.90%. On HU, all models have the same RI. On FI, the RI of NEPAM (NEP-HAM) is 9.16% lower than NEP-DQN. This indicates the entropy regularization does not effectively prevent the premature convergence of our models. In future work, we will explore incorporating intrinsic rewards [Burda et al.,

4 We discuss the results under different training steps in the appendix.

2018] to improve our models' exploration ability to address this issue. 2) NEP-HAM performs better than or equal to NEP-AM in 8 out of 10 real networks. Specifically, it outperforms NEP-AM by 6.08%, 10.04%, and 10.26% on CZ, GB, and SE, respectively. However, on RO and TR, the RIs of NEP-HAM are 14.45% and 11.57% lower than NEP-AM.

Random attack. We analyze the results regarding the random attack in Table 2 as below. 1) NEP-AM outperforms NEP-DQN in 8 out of 10 real networks. Specifically, NEPAM shows significant improvements on FI, KZ, and HU with relative increases of RIs at 24.34%, 26.60%, and 21.62%, respectively. However, on CZ and GB networks, NEP-AM performs slightly worse than NEP-DQN with about 5% lower RIs. NEP-HAM narrows the performance gap to NEP-DQN on these two networks to about 3%. 2) In 5 out of 10 real networks, NEP-HAM has a slight advantage over NEP-AM with relative increases of RIs ranging from 1.56% to 4.02%. However, NEP-AM performs slightly better than NEP-HAM by 1.73% and 4.65% on FI and HU networks, respectively. They have similar performance in the remaining three networks, with about or less than 1% performance differences.

Conclusions. 1) Our models show significant progress in solving NEP for real networks against both attack methods. However, we should improve their exploration ability to further improve their performance, especially for the targeted attack. 2) NEP-HAM performs better than or similar to NEPAM in most real networks.

4.5 Evaluation of the NCLS (RQ 3)

We aim to check whether NCLS can realize the effective search of the restricted k-exchange neighborhood with large k values. Due to the extremely long computation time of k-opt local search with large k values, we compare NCLS with 1opt local search. We evaluate them on the ID test sets of synthetic networks at τ = 5% and real networks at τ = 2.5%. The NEP-AM/HAM model trained in previous experiments is used to generate initial solutions for NCLS and 1-opt local search. In particular, we sample 8 initial solutions for each synthetic network and attack method and 32 (128) initial solutions for each real network for the targeted (random) attack. To generate a neural confined neighborhood, we perform a beam search with width 2 to find the η = min{2k , 100} groups of nodes with the highest probability under a trained model to replace the exchangeable nodes. We set k to 5, 7. We update the current solution with the best solution in the neighborhood and iteratively improve the solution until obtaining a local optimal solution. We process all initial solutions in parallel, and choose the best-improved solution as the final solution. We present the results in Table 3 and also list the results of NEP-AM and NEP-HAM in the table for easier comparison. We use names like "NCLS-AM" to represent NCLS with both initial solutions and neural confined neighborhoods generated by a trained NEP-AM model and "LSAM" to represent the 1-opt local search with initial solutions generated by a trained NEP-AM model. When comparing NCLS-AM (NCLS-HAM) with NEP-AM (NEP-HAM), we report the best results among NCLS-AM (NCLS-HAM) with k = 5, 7. We observe that for NCLS-AM (NCLS-HAM), these best results are consistently achieved with k = 7 in most cases.

Targeted attack. We make the following observations regarding the targeted attack in Table 3 as below. 1) When dealing with synthetic networks (BA and ER), NCLSAM/HAM performs better than LS-AM/HAM. Specifically, with k = 5, NCLS-AM/HAM outperforms LS-AM/HAM by 14%/12.98% on BA networks and by 1.34%/2.57% on ER networks. With k = 7, the advantages of NCLSAM/HAM expand further to 16.73%/18.46% on BA networks and 1.95%/2.57% on ER networks. 2) For real networks, with k = 5, NCLS-AM outperforms LS-AM in two networks (RO and TR) by 41.89% and 3.77%, respectively. It performs equally well as LS-AM in six networks and worse in two networks (KZ and GB) with a 7.69% and 4.10% difference. With k = 7, NCLS-AM outperforms LS-AM in four networks (RO, TR, GB, and SE) by 41.89%, 3.77%, 4.27% and 9.01%, and performs equally well as LS-AM in all other networks. It is worth noting that LS-AM, NCLSAM with k = 5, and NCLS-AM with k = 7 tend to have the same results in most networks. However, this does not imply our methods cannot search a larger neighborhood effectively. The reason for these results is that the initial solutions sampled from NEP-AM are good enough such that even LS-AM can find high-quality local optima. We find that when we generate initial solutions randomly, 1-opt local search is much worse than NCLS. For instance, in KZ, NCLS-AM with k = 5 outperforms 1-opt local search by 50%. The results on other real networks are similar, thus omitted here. We can conduct similar analyses to compare LS-HAM and NCLS-HAM with k = 5, 7. NCLS-HAM with k = 5 outperforms LS-HAM in four networks (RO, TR, CZ, and GB) by 25.23%, 17.35%, 6.08%, and 4.28%. It performs equally to LS-HAM in five real networks, but performs worse than LS-HAM in one network (KZ) by 7.69%. Meanwhile, NCLS-HAM with k = 7 outperforms LS-HAM in five real networks with relative increases of RIs ranging from 4.28% to 33.56%, and performs equally to LS-HAM in all remaining real networks. 3) NCLS-AM (NCLS-HAM) shows significant improvements over NEP-AM (NEP-HAM) on synthetic networks, with an increase of 88.27% (84.09%) on BA networks and 67.74% (55%) on ER networks. For real networks, NCLS-AM (NCLS-HAM) improves the results of NEP-AM (NEP-HAM) on 7 out of 10 real networks with relative increases of RIs ranging from 3.77% to 25% (5.49% to 33.56%).

Random attack. We make the following observations regarding the random attack in Table 3 as below. 1) For synthetic networks (BA and ER), with k = 5, NCLSAM (NCLS-HAM) produces better results than LS-AM (LSHAM). Specifically, NCLS-AM (NCLS-HAM) outperforms LS-AM (LS-HAM) by 9.06% (6.77%) on BA networks and by 2.48% (4.01%) on ER networks. When the value of k is increased to 7, these advantages are further increased to 13.44% (11.38%) on BA networks and 5.28% (4.01%) on ER networks. 2) For real networks, with k = 5, NCLSAM (NCLS-HAM) outperforms LS-AM (LS-HAM) on eight real networks with relative increases of RIs ranging from 1.39% to 7.28% (0.77% to 9.06%). In the remaining two networks, NCLS-AM (NCLS-HAM) performs equally to LSAM (LS-HAM) on one network and worse than LS-AM (LS-HAM) on another by 0.38% (1.12%). With k = 7, NCLS-AM (NCLS-HAM) outperforms LS-AM (LS-HAM) on all (nine) real networks with relative increases in RIs ranging from 1.44% to 9.22% (1.37% to 6.04%). 3) For synthetic networks, NCLS-AM (NCLS-HAM) improves the results of NEP-AM (NEP-HAM) by 61.33% (59.47%) on BA networks and by 33.46% (31.64%) on ER networks. For real networks, NCLS-AM (NCLS-HAM) improves the results of NEP-AM (NEP-HAM) on 8 out of 10 real networks with relative increases in RIs ranging from 0.76% to 6.23% (0.69% to 11.58%).

Conclusions. 1) NCLS can realize the effective search of the restricted k-exchange neighborhood by only examining a few candidates generated by a trained model. 2) NCLSAM (NCLS-HAM) as a post-processing tool can significantly improve the results of NEP-AM (NEP-HAM) on both attack methods.

4.6 Comparison of Validation Curves (RQ 4)

In the previous subsection, we compare pre-trained models on synthetic networks. In this subsection, we evaluate the performance of NEP-AM and NEP-HAM throughout the entire training process by measuring the average RI on the validation set. We also investigate the necessity of recomputing node coordinates as the network structure changes. Although methods [Demmel, 1997] have been proposed to approximate the eigenvectors of graph Laplacian efficiently, there is still computational overhead. A natural idea is to fix the node coordinates during the decision process. Thus, we consider these models with fixed node coordinates. We display the results of the targeted attack in Fig. 1, which shows the average RI against the training step. The results of the random attack are similar, thus omitted here. From the figure, we can see that: 1) In all cases, NEP-HAM (orange lines) has an obvious advantage over NEP-AM (blue lines) on all training steps. 2) With fixed node coordinates, the performance of NEP-AM degrades severely. Thus, updated node coordinates provide essential information for NEP-AM to capture the changing of the network structure. 3) With fixed node coordinates, the performance of NEP-HAM also degrades somewhat, but not so much as NEP-AM. That is because NEP-HAM exploits the network structure more directly than NEP-AM. Thus, recomputing node coordinates is indispensable for NEP-AM and provides some extra information for NEP-HAM.

5 Discussions

Scalability. Our models face two scalability issues 5 . Firstly, the changing network structure in the decision process requires recomputing node coordinates, which is timeconsuming. To address this, we suggest computing exact node coordinates only in the first decision step and adjusting them dynamically in subsequent steps using matrix perturbation theory [Chan et al., 2014]. Secondly, the computation of the multi-head attention mechanism is quadratic with graph size. We propose replacing it with the ProbSparse selfattention [Zhou et al., 2021], which calculates the inner product O(n log n) times and does not compromise performance. Generalization to different network patterns. In this work, we only focus on how well our models generalize to different network sizes within the same network model. We run a pilot experiment and find that when we train our models on BA networks and test them on ER networks, their performance is slightly worse than NEP-DQN trained on ER networks. We are working on a solution to address this challenge. We build an encoder qϕ(z|G) to map the network G to a distribution over the latent vector z, where the distribution distance between two similar structures is small, and learn a policy πθ(v|s, z) conditioned on z. For decision, we select node v with probability p(v) = ∫ qϕ(z|G)πθ(v|s, z)dz.

5 We provide a running time comparison in the appendix.

Defending against anunknown attackmethod. Our work aims to improve network robustness against two common attack methods. However, it is often difficult to anticipate the attack method beforehand. To address this, we suggest maximizing the robustness against the strongest attack strategy A∗ mentioned in the related work section. Let G∗ be the optimal solution under A∗ . For arbitrary strategy A, we have RA∗ (G∗ ) ≤ RA(G∗ ) ≤ RA( ¯G), where ¯G is the optimal solution under A. However, the gap between RA∗ (G∗ ) and RA( ¯G) may be large. Our methods can be applied to seek G∗ by modifying the reward function.

Conclusions. We develop NEP-AM and NEP-HAM for solving NEP. In NEP-AM, we incorporate domain knowledge to get high-quality state and action representations. In NEPHAM, we add a structure-aware attention module to NEPAM to directly utilize the network structure information. To further improve the results of NEP-AM/HAM, we introduce NCLS to realize the effective search of a large neighborhood. We demonstrate our models' superiority and NCLS's effectiveness through extensive experiments.

Acknowledgements

This work is supported by the National Key R&D Program of China (No.2021ZD0113000).