Edge Rewiring Goes Neural: Boosting Network Resilience via Policy Gradient
Authors: Shanchao Yang
MA KAILI
Baoxiang Wang
Hongyuan Zha
Venue: ICLR 2022 Submitted (2022)
Keywords: network resilience
neural combinatorial optimization
graph neural networks
reinforcement learning

Abstract: Improving the resilience of a network protects the system from natural disasters and malicious attacks.
This is typically achieved by introducing new edges, which however may reach beyond the maximum number of connections a node could sustain.
Many studies then resort to the degree-preserving operation of rewiring, which swaps existing edges $AC, BD$ to new edges $AB, CD$.
A significant line of studies focuses on this technique for theoretical and practical results while leaving three limitations: network utility loss, local optimality, and transductivity. 
In this paper, we propose ResiNet, a reinforcement learning (RL)-based framework to discover Resilient Network topologies against various disasters and attacks. 
ResiNet is objective agnostic which allows the utility to be balanced by incorporating it into the objective function.
The local optimality, typically seen in greedy algorithms, is addressed by casting the cumulative resilience gain into a sequential decision process of step-wise rewiring.
The transductivity, which refers to the necessity to run a computationally intensive optimization for each input graph, is lifted by our variant of RL with auto-regressive permutation-invariant variable action space.
ResiNet is armed by our technical innovation, Filtration enhanced GNN (FireGNN), which distinguishes graphs with minor differences.
It is thus possible for ResiNet to capture local structure changes and adapt its decision among consecutive graphs, which is known to be infeasible for GNN.
Extensive experiments demonstrate that with a small number of rewiring operations, ResiNet achieves a near-optimal resilience gain on multiple graphs while balancing the utility, with a large margin compared to existing approaches.

Under review as a conference paper at ICLR 2022
EDGE REWIRING GOES NEURAL: BOOSTING NET- WORK RESILIENCE VIA POLICY GRADIENT
Anonymous authors Paper under double-blind review
ABSTRACT
Improving the resilience of a network protects the system from natural disasters and malicious attacks. This is typically achieved by introducing new edges, which however may reach beyond the maximum number of connections a node could sustain. Many studies then resort to the which swaps existing edges AC, BD to new edges AB, C.D. A significant line of studies focuses on this technique for theoretical and practical results while leav- ing three limitations: network utility loss, local optimality, and transductivity. In this paper, we propose ResiNet, a reinforcement learning (RL)-based framework discover Resilient Network topologies against various disasters and attacks. ResiNet objective agnostic which allows the utility to be balanced by incor- porating it into the objective function. The local optimality, typically seen in greedy algorithms. is addressed by casting the cumulative resilience gain into a se- quential decision process of step-wise rewiring. The transductivity, which refers to the necessity to run a computationally intensive optimization for each input graph, lifted by our variant of RL with auto-regressive variable action space. ResiNet is armed by our technical innovation, Filtration enhanced GNN (FireGNN), which distinguishes graphs with minor differences. It is thus possible for ResiNet to capture local structure changes and adapt its decision among consecutive graphs, which known to be infeasible for GNN. Extensive experiments demonstrate that with small number of rewiring opera- tions, ResiNet achieves near-optimal resilience gain on multiple graphs while balancing the utility, with large margin compared to existing approaches.
operation of rewiring.
commutation-invariane
INTRODUCTION
Modern infrastructure systems, such as computer routing and electric power networks, are vulnera- ble natural disasters and malicious attacks (Schneider et al., 2011]. Consider the scenario where the abnormality of one power supply station causes other power supply stations to overload, which cascades more power supply to fail, resulting in region-wide power outage. Figure T visualizes this scenario that the failures of a dozen nodes could jeopardize the connectivity and utility of the EU power network with 217 nodes. The ability for system to defend itself from such failures and attacks is characterized by the network resílience. A resilient network should continue to function and maintain acceptable level of utility when part of the network fails.
A network becomes more resilient if some connections could backup the others. It is seemingly straightforward achieve resilience by adding redundant edges. However, will not be practically feasible as the nodes are usually already running at their full capacity. For example, power supply facility can only support a certain number of connections and cannot afford additional loads. In such regime, degree-prece preserving operations, such as edge rewiring, are desired (Schneider et al., [011]] Rong Liu [2018] Yazıcioglu al., 20155 Zhou & Liu 2014). Let G = (V. E) be a graph. An edge rewiring operation alters the graph structure by removing AC' and BD and adding AB and CD, where AC, BD E and AB, CD, AD, BC & F Edge rewiring empirically effective to maximize network resilience and becomes the prevailing atomic operation in the literature. Despite this, methods for improving network resilience via edge rewiring share several limitations: utility loss, local optimality, and transduction.
AA few works have a different definition for the edge rewiring operation.

---

Under review as a conference paper at ICLR 2022
Narma tove ton of angest cornectd componen
Orgna Pet
ofremoved
Original EU network
(b) EU network after attacks
Remaining LCC size under attack
The EU power network under the adaptive degree-basen attack which removes the most critical node recursively with (a) original EU network with 217 nodes, (b) remaining EU network after a series of attacks on 40 nodes, and (c) the change of the normalized size of the largest con- nected component (LCCC). The node size proportional its degree and the node color given by DBSCAN (Ester et al. 1996).
Figure 1:
Network utility loss. Improving network resilience aims to protect the network utility from degrading under attack and make the network continue functioning. Optimizing network resilience without considering the network utility could jeopardize the functioning without the presence of an attack.
Local optimality. Combinatorially choosing the edges to rewire to optimize the resilience is proved to be NP-hard Aoyama 2008). Previous studies predominantly seek approx- imate optimality through greedy-like algorithms, which yields local optimality in practice.
Transductivity. Traditional resilience optimization methods search the resilience topology on a given graph. This search process has to be executed for every graph and does not transfer between graphs, even if the graphs are only up minor structure difference.
transductive since they
To tackle the challenges above, in this work, we present ResiNet, the first objective-agnostic learning-basee method for inductively discovering resilient network topologies. Frist, by formulat- ing the cumulative gain of the objective into RL, ResiNet is agnostic to arbitrary objective function, which makes resilience optimization practical real applications by incorporating the utility into the resilience. The nature of delayed gratification in RL also allows the agent to bypass local op- timums caused by step-wise optimal actions. Second, the fact that graphs have different sizes and arbitrary node permutations makes it challenging to solve transductivity when selecting edges with deep learning. this scenario, nodes can no longer be represented by their ID since com- putationally infeasible to train model handle all isomorphic graphs. Using mechanism (Vinyals et al.] 2015) to identify edges and an auto-regressive space (Trieedi et al. (2020) to formulate edge selection, agent trained by ResiNet works wide range of graphs with dif- ferent sizes and permutations.
cicention-based
Deep learning and graph neural networks (GNNs) have been successfully applied to many combi- natorial optimization problems on graphs (Khalil et al. 2017 Li et al.) 2018a Karalias & Loukas 2020). However, well on the task of improving network resilience via edge rewiring. We suspect that this is caused by a dilemma for the expressive power of GNN: If the representation power the GNN is too weak (e.g., the regular GNN), then it could not distinguish graphs with minor differences and will choose similar actions in consecutive steps of RI. This causes the process to alternate between two graphs, forming an infinite loop. If the representation power is too strong (e.g., SMP. IDGNN), it tends to give similar representations to connected vertices, known as the oversmoothing phenomenon (Vi- gnac et al. 2020; You et al. 2021). It is then difficult for the agent to distinguish vertices in connected component, causing large randomness in the output of the policy. This dilemma may lead to the bad performance of selecting edges using regular GNNs and RL. Therefore, successfully evolving dynamic graph at each step, the implementa-
we empirically observed, the combination of GNNs and RL cannot perform
select two edges from a tion of ResiNet is armed with Filtration enhanced GNN (FireGNN), our technical innovation, to
2

---

Under review as a conference paper at ICLR 2022
solve the above dilemma of the expressive power of GNN. FireGNN creates series of subgraphs (the filtration) by successively removing nodes from the graph, and aggregates the node represen- tations from the subgraphs. It makes the GNN powerful when representing graphs while avoiding oversmoothing as the node information are adequately acquired from a multi-step filtration. This technical innovation is inspired by persistent homology and the approximation of the persistence diagram (Edelsbrunner & Harer 2008 Aktas et al. 2019; Hofer et al. 2020).
The main contributions of this paper are summarized as follows:
1) We propose ResiNet, a data-driven framework to boost network resilience in a degree- preserving way with moderate loss of the network utility by forming resilience optimization into a objective-agnostic sequential decision process of edge rewiring. Extensive experi- ments show that with small number of rewiring operations, ResiNet achieves a near- optimal resilience gain on multiple graphs while balancing network utilities. Existing ap- proaches are outperformed by a large margin.
2) FireGNN, our technical innovation, balances the expressive power and the oversmoothing issue through the graph filtration augmentation. FireGNN could distinguish very similar graphs and distinguish connected vertices at the same time, which is essential to make the combination of GNNs and RL work on the network resilience optimization.
3) ResiNet is the first to improve network resilience in an inductive way, with the special- ized rego-segee permutation invariint size-variable policy network. Once an agent is trained, it works on wide range of graphs. The policy network is general enough to be extended to other problems in constrained graph generation.
2 RELATED WORKS
Network attacks and defenses The problem of attacking network is characterized by the target resilience measurement and the manipulation type. Depending on the application, network resilience is defined as a corresponding measure to quantify the network functionality, such as graph connec- tivity (Grsssi et al. 2021, Fan et al.) 2020). For particular networks (e.g., scale-free networks), attacks appear in destroying critical nodes and critical connections (Grassia et al.) 2021 Fan et al.)
2020 ZZhao et al. 2021, Zhang et al., 2017; Medya et al. 2020). Heuristic and learning-basee based at-
tack methods (Holme et al. 2002: Lyer al. 2013 Grassia et al. [02 Fan al. 2020) have been proposed to target the critical subset of the network. To defend against potential attacks, various defense strategies have been proposed protect the network functionality from crashing and pre- serve some of its topologies. The commonly used defense manipulations include adding additional edges (Li et al. 2019: Carchiolo et al. (2019), protecting vulnerable edges (Wang et al. 2014) and rewiring two edges (Schneider et al.] 2011 Chan & Akoglu 20166) Buesser et al. 2011)). Among these manipulations, edge rewiring fits well to real-world applications as induces less functionality changes (e.g. degree preserving) to the original network and does not impose additional loads to the
vertices (Schneider et al. 2011 Rong & Liu 2018
Yazıcioglu et al. 2015 Zhou & Liu 2014).
GNNs for combinatorial optimization problems The idea of applying GNNs to solve combina- torial optimization problems on graphs is becoming a promising yet challenging topic. Abundant algorithms have been developed and can be classified into three categories. Supervised learning approach combines GNNs with heuristics search procedures or solvers to solve classical combi- natorial problems, such as graph matching (Bai al. (2018), graph coloring (Lemos et al.) 2019)
TSP (Li et al.) [00 8b) Joshi et al. 2019) and SAT (Wang et al. 2019). These methods require la- beled instances and thus are difficult generalize to scage-scale instances directly. Unsupervised learning approach (Karalias & Loukas 2020) trains GNNs to parametrize probability distribu- tion over sets. The probabilistic proof achieves the existence of feasible solutions. After that, the derandomized method is applied to decode the desired solutions. However, meeting complex con- straints have not been supported yet. Reinforcement learning approach formulates a problem as a Markov decision process with proper reward function to guide the search towards an optimal solution. Some classical CO problems have achieved remarkable results like TSP (Fu et al. 2020
Khalil et al. 2017). Vehicle Routing Problem (Nazari al. 2018 Peng al. 2020 Yu al. 2019)
SAT (Yolcu & Poczos 2019) and max-cut (Khalil et al. 2017). 7). In this paper, we adopt the R based approach but with specialized policy network.
3

---

Under review as a conference paper at ICLR 2022
Positioning of this work In this paper, only the edge rewiring operation to defend against degree-based and centrality- attacks while preserving the network utility.
Extended related works The related works on Network resilience and utility, mulri-views graph augmentation for GNNs, and deep graph generation models are deferred to Appendix A
3 PROPOSED APPROACH: RESINET
ReniNet
FICGINN
State C,
Node embedding
First edge embedding
Esgh aargaaa fiS.. d)
FIRGNN
ResiNet
Env step: Rewire AC AB and CD
State G.s and reward R
Eaeaargaax SXS,, d)
edge embedding
Figure Overview of the policy architecture of ResiNet select rewiring edges.
In this section, we first present the problem formulation of maximizing network resilience while preserving utility performance. We then discuss the graph resilience-awarc environment design and give the graph policy network which guides the process of edge rewiring. The problem of boosting network resilience is formulated as a reinforcement learning task by iteratively rewiring the edges.
3.1 PROBLEM DEFINITION
An undirected graph is defined as G (V,F), F), where V = (1,2,... N) is the set of N nodes, E is the set of M edges, A E (0,
the adjacency matrix, and F7 I2 Nxd the d-dimensional node feature matrix The degree of node is defined as d; ΣØ= Aij, and node with degree 0 called an isolated node.
Let GG denote the set of graphs with the same node degrees as G. Given the network resilience function RGG) and the utility function (G),, the objective of boosting the resilience of G' is to find target graph G* GG, which maximizes the network resilience while preserving the network utility. Formally, the problem of maximizing network resilience is formulated as
G arg max a R(G') + (1- (L)))(())))
eGa
where a E R is the scalar weight that balances the resilience and the utility.
Two examples of resilience functions, including the graph connectivity- -based measurement (Schnei- der et al. 2011) and the poactrum-based measurement (e.g., adjacency matrix spectrum and Lapla- cian matrix spectrum), and two examples of utility functions, including global efficiency and local efficiency, are given in Appendix B Our formulation could generalize to other definitions of re- silience and utility.
3.2 ROBUST GRAPH GENERATION VIA EDGE REWIRING AS MARKOV DECISION PROCESS
To satisfy the constraint of preserving the node degree, the resilience optimization of a given graph is based on edge rewiring. We formulate this process into the MDP framework. The Markov property
Without loss of generality, unweighted graphs considered. Our framework can be extended to weighted graphs with the weight as additional edge feature.
4

---

Under review as a conference paper at ICLR 2022
denotes the fact that the graph obtained at time step t-t relies only the graph time step t and the rewire operation. As is illustrated in Figure the environment performs the resilience optimization in autto-reressive step-wise way through sequence of edge rewiring actions guided by ResiNet. Given an input graph, the agent first decides whether to terminate or not. If chooses not to terminate, it selects edge from the graph remove, receives the very edge it just selected the regression signal, and then selects another edge to remove. Four nodes of these two removed edges re-combined, forming two new edges to added the graph. The optimization process repeats until the agent decides to terminate. The details of the design of the state, the action, the transition dynamics, and the reward are presented follows.
State
The fully observable state of the environment is formulated as S, Gr. where G3 is the current input graph at time step The node feature initialization strategy is given in Appendix CC.
Action ResiNet is equipped with node germutation-invariant, variable-dimmesionaa action space. Given graph G, the action a₁ is to select two edges and the rewiring order. The agent first chooses the state, e1, and the direction
edge e1 = AC and a direction A C. Then conditioning the agents chooses an edge 62 = BD such that AB, CD, AD, BC & E and direction B - D. The heads of the two edges reconnect
edge AB and does the tail CD. As A - C, B + D and C + A, D + B refer to the same rewiring operation, the choice of the direction of ei is randomized (this randomized bit still an input of choosing E2), is shown in Figure This effectively reduces the size of the action space by half. In this way, The action space is the set of all feasible pairs of (e1, 62) E E², which has variable size no larger than 2 ( 1).
(a) Example graph
(b) First edge selection
(c) Sccond edge selection
(d) Graph after the edge rewiring
Figure 3: Illustration the edge rewiring and the rewiring order. (a) The undirected example graph the state: (b) Edges with random directions are candidates when selecting the first edge; (c) All 2M directed edges can be candidates when selecting the second edge, subject to that it forms a rewiring with the first edge; (d) The resultant graph after the rewiring, with the removal of AC, BD and the introduction of AB, CD.
Transition dynamies By the formulation of the action space, the agent does not terminate step t, the selected action must form an edge rewiring. This edge rewiring is executed by the environment and the graph transits to the new graph.
Note that in some other works, infeasible operations are also included in the action space (to make the action space constant through the process) (You et al. 2018 Trivedi al.) a 2020). In these works, if the operation is infeasible, it is not executed and the state is not changed. This reduces the sample efficiency, causes biased gradient estimation (Huang & Ontañón 2020), and makes the process to be prone stuck at the state (which requires manually disabling the specific action in the next step). ResiNet takes the advantage of the action space composed of only feasible operations.
Reward ResiNet desires optimize the resilience while preserving the utility, forming com- plicated and possibly unknown objective function. Despite this, by Wakuta| (1995), an MDP that maximizes complicated objective is up MDP that maximizes the linear combination of silience and utility for some coefficient factor. This fact motivates us to design the reward as the step-wise gain of such linear combination
R₂ = a (R(G++)) (1 - a) ((G++))))) - (a R(G))()))))))))) + (1) u(G)))
where R(G) and U(G)) are the resilience and the utility functions, respectively. The cumulative reward D Rs up to time T is then the total gain of such linear combination.

---

Under review as a conference paper at ICLR 2022
3.3 EDGE REWIRING POLICY
Having presented the details of the resilient graph generation environment, in this section, we de- scribes the architecture of ResiNet in details. ResiNet is policy network trained maximize the cumulative reward of the agent in the graph resilience-aware environment. At time step 4, the pol- icy network takes the current graph Gt as input and outputs an action ae which represents the two rewired edges, leading to the new state G++1 and the reward R4.
3.3.1 FIREGNN VIA GRAPH FILTRATION ARGUMENTATION
Motivated by the graph filtration in persistent homology [Edelsbrunner & Harer 2008), we propose to enhance the expressivity of GNN via the graph filtration process by augmenting input graph G. To avoid the computational cost of calculating the persistence diagram at each step, the similarity between the filtration process and resultant subgraphs after each attack motivates to construct sequence of nested subgraphs of G as an approximate filtration, such that
(V, = ( C G( C ..... G G,
where (kk) denotes the remaining graph after removing N - k nodes particular task-dependent order, G(N) the original graph, and (( is empty graph with edge.
The sequence of nested subgraphs G is termed the filtrated graph G. Regular GNN only operates on the original graph G to obtain the node embedding for each node i;
h((s)) ((G = G),,
where (b-) denotes standard GNN model.
Node embedding In FireGNN, by using the top K + subgraphs in a graph filtration, the final node embedding h(v:) of o; obtained by
h(v;) = Agen (1(N-K)(z;)) (c))..... 1(N (v.) (w.) (e:))
where (-) denotes node-level aggregation function, ((()())) is the node embedding of in the k-th subgraph G(A), and K E [N]. In practice, (xx) is discarded when calculating h(v)) if is isolated or not included in ((k)
Edge embedding The directed edge embedding h (esz) of the edge from node to node j in each subgraph is obtained by combining the embeddings of the two end vertices (k) as
h (erg) m, (AgEN-, (n (x (u.), (1))))
where AggN=e() denotes an aggregation function for obtaining edge embedding from two end vertices (typically chosen from min, max, sum, difference, and multiplication) my(() is multilayer perceptron (MLP) model that ensures the consistent dimension of edge embedding and graph embedding.
The final embedding of the directed edge eş of the filtrated graph G is given by
Me(e)) Agg (N (eig), (N K K+1) (eg),..... (NN (en)), (e6))
where Aggg(.) (-) denotes edge-level aggregation function.
Graph embedding With the node embedding (*s)))) of each subgraph available, the graph em- bedding (G)) of each subgraph is calculated by readout functions (c.g., mean, sum) all non-isolated nodes in (K) as
(G) READOUT (e:)) Ve, E ((k) and d( 2 0.
The final graph embedding of the filtrated graph G is given by
(G) = -Aggc (N(N-K) NNN- ((N (G) (N-11) (G), (G))

---

Under review as a conference paper at ICLR 2022
where (-) denotes graph-level aggregation function.
By observing a sequence of nested subgraphs of G. a filtration process transforms an input graph from the static graph to sequences of subgraphs, which grants GNNs the capability to observe how G evolves and improve the expressivity in node, edge, and graph levels. We term the Filtrated graph enhanced GNN as FireGNN.
3.3.2 POLICY NETWORK
After obtaining the directed edge embedding h(ess) R2 and the graph embedding IGG) Id from the proposed FireGNN, armed with specially designed autoregressive node permutation-invarian dimension-variable action space, we can select the edge rewiring operation for graphs with arbitrary sizes and node-permutations. The detailed architecture of ResiNet and the mechanism of obtaining the action at are presented as follows.
Auto-regressvve latent action selection An edge rewiring action a at time step t involves the prediction of the termination probability (0) and the selection of two edges (a, and a; a,²)) and the rewiring order. The action space of ( binary, however, the selection of two edges imposes huge action space in O(E²), which is too expensive sample from even for small graph. Instead of selecting two edges simultaneously, we decompose the joint action a, into 0₂ (a, ag az (2)
where at (1) and at are two existing edges which do not share any common node (recall that at and ag (2) are directed edges for an undirected graph). Thus the probability of a, is formulated as
P(a, (x) P(a (s)))P((( ((((a))) (8,, af (Pa |se, dg (1) ())
Predicting the termination probability The first policy network To(-) takes the graph embedding as input and outputs the probability distribution of the first action that decides to terminate or not as
P(a;
(0 To (h(G)),
where (-)+) ) implemented by a two layer MLP. Then a Ber(P (0) (s)) (s))s) (0.
Selecting two edges If the signal a (0) given by the agent decides to continue rewire, two edges are then selected an auto-regressive way. The signal continuing to rewire (0)) input to the selection of two edges
one-hot encoding vector le- The second policy network 7-(-) takes the graph embedding and le as input and outputs a latent vector 4 E Rd The pointer network (Vinyals) et al. 2015) is used to measure the proximity between l and each edge embedding h(e;;) in G to obtain the first edge selection probability distribution. Then, to select the second edge, the graph embedding h(G) and the first selected edge embedding h(((") and le concatenated and fed into the third policy network (.).). π²(-) obtains the latent vector l2 for selecting the second edge using respective pointer network. The process can be formulated as
4 Ti (Ih(G), 4c)
P(a St, a ()) (1 h(es)))), Veiz E E
la T2 (l), (e))))
P(a 15 0) fz(12, h(es)))), Veij E E,
where TT(+) is implemented by two layer MIP model. [. denotes the concatenation operator, h_a> the embedding of the first selected edge at time step t, and fi(-) is a pointer network.
4 EXPERIMENTS
In this section, demonstrate the advantage of ResiNet in optimizing network resilience, general- izing to unseen graphs, and accommodating multiple resilience and utility metrics. The experimental results show that the optimization of ResiNet is achieved with fewer edge rewiring operations.

---

Under review as a conference paper at ICLR 2022
4.1 EXPERIMENTAL SETTINGS
Synthetic datasets and the real EU power network (Zhou & Bialek 2005 are used to demonstrate the performance of ResiNet in both transductive and inductive settings. The details of data generation and the statistics of the datasets are presented in Appendix C.I
Datasets
Baselines We compare ResiNet with existing graph resilience optimization algorithms, including the hill climbing (HC) (Schneider et al., 2011), the greedy algorithm (Chan & Akoglu 2016), the simulated annealing (SA) (Buesser et al. 2011). and the evolutionary algorithm (EA) (Zhou & Liu 2014). It should be noted that all traditional baselines are transductive. Since there is neural- version baseline, we provide one by replacing FireGNN with a regular GNN. The ResiNet's training setup is detailed in Appendix C.2 All algorithms are repeated for three random seeds using default hyper-paramelers to obtain the averaged performance.
4.2 COMPARISONS TO THE BASELINES
In this set of experiments, we first compare ResiNet to the baselines in optimizing the combination of resilience and utility with weight coefficient a {0, 0.53. The graph connectivity- metric is used as the resilience metric and the global efficiency is used as the utility metric. The test is conducted on transductive settings and 3 inductive settings.
Table D records the metric gain and the required number of rewiring of different methods under the same maximal rewiring budget. ResiNet outperforms all baselines consistently on all datasets. Note that this performance may be achieved under much fewer number of rewiring operations, such as the BA-15 with a 0. In contrast, even approximately searching for all possible new edges, the greedy algorithm is still trapped into a local optimum by maximizing the one-step resilience gain. For SA, the initial temperature and the temperature decay rate need to be carefully tuned for each network. EA performs worse with limited rewiring budget due to the numerous rewiring operations required in the internal process (e.g., the crossover operator). It should be noted that the poor performance of combination of regular GNNs and RL (GNN+RL), compared to ResiNet, validates the challenges of improving network resilience via edge rewiring and indicates the effectiveness of ResiNet with FireGNN.
In general, the metric gain is more significant for larger graphs, which implies that it is reasonable and cost-effective to improve the resilience of large networks. All baselines are compared under the same rewiring budget of 20 since each edge rewiring introduces economic costs for real systems. It should be noted that solutions under large rewiring budget like 200 will not be applicable in prac- tice due to the tremendous rewiring cost. We record the performance and speed of each algorithm for a maximal rewiring budget of 200 in Appendix Table 4
4.3 GENERALIZATION
In this section, conduct extensive experiments to show that ResiNet generalizes different utility and resilience metrics, various attack strategies, and unseen graphs We do not compare ResiNet with other algorithms on the inductive setting because existing algorithms are transductive.
To explore the complicated objective of resilience and utility, the BA-15 network is taken as an example to be optimized by ResiNet to obtain the approximate Pareto frontier. The Pareto points are shown in Figure 8 to denote the optimum under different objectives. Surprisingly, the initial gain of resilience (from around 0.21 to around 0.24) without loss of the utility, which incentivizes almost every network to conduct such optimization at least to some extent when feasible.
To demonstrate that ResiNet can learn from the networks for accommodating different utility and resilience metrics, conduct experiments based on the BA-15 and EU datasets by using multiple different resilience metrics and different utility metrics (details are in Appendix B). The results are included in Appendix D.2 The network structures are visualized in Figure 7 and Figure 10
To demonstrate the inductivity of ResiNet, we first train ResiNet on two different datasets, and the individual test dataset. These
data setting is recorded in Table We evaluate its performance datasets are unknown to ResiNet and have not been observed during the training process. Fine- tuning is not allowed. We report the averaged resilience gain for the graphs with the same number
8

---

Under review as a conference paper at ICLR 2022
Resilience optimization algorithm under the fixed maximal rewiring number budget of 20. We report the weighted combination of the graph connectivity based resilience and the network efficiency improvement (in percentage) with the weighted coefficient a E {0, 0.53. Results are averaged over 3 runs. We report the rewiring number inside the bracket.
Table 1:
Method
BA-15
BA-50
BA-100
EU
0
26.8 (10)
30.0 (20)
24.1 (20)
19.8 (20)
HC
0.5
18.6 (11.3)
22.1 (20)
14.9 (20)
16.3 (20)
0
21.6 (17.3)
(20)
12.5 (20)
14.9 (20)
SA
0.5
16.8 (19.0)
(20)
1204
(20)
0
23.5 (6)
(13)
64.3 (20)
0.5 (3)
Greedy
0.5
5.3
313)
42.7 (20)
0.3 (3)
0
(20)
(20)
(20)
8.2 (20)
EA
0.5
6,4 (20)
(20)
2.8 (20)
9.3 (20)
13.7
0
(
920)
GNN+RL
0.5
10.9 (2)
0
(
2.1 (20)
0
35.3 (6)
61.5 (20)
70.0 (20)
54.2 (20)
ResiNet
0.5
26.9 (20)
53.9 (20)
53.1 (20)
51.8 (20)
(a) Inductivity on resilience
(b) Inductivity on utility
(c) Inductivity on both metrics
Figure 4: The inductive ability ResiNet on the test dataset (BA-10-30) when optimizing (a) net- work resilience, (b) network utility, and (c) their combination.
of nodes for each dataset. The result of BA-10-30 is shown in Figure and the results of the other datasets deferred to Appendix D.2] Figure 4 shows nearly linear improvement of resilience with the increasing of graph size, which also consistent with the results in the transductive setting that larger graphs usually have larger to improve.
CONCLUSION AND FUTURE WORKS
In this work, propose a general, leaming-hasee framework, ResiNet, for the inductive discovery of resilient network topologies. The framework practically feasible as it also preserves the utility of the networks. ResiNet is the first formulate the problem of boosting network resilience as an MDP, with specialized auto-regressive permutation-invarian variable action space. This variant of MDP allows the agent handle graphs of different sizes and isomorphisms. Once an agent is trained, it inductively works on wide range of graphs and is ready to be deployed to real systems. Our technical innovation, FireGNN, is powerful technique for node and graph representations, which is a suitable replacement other GNNs, especially in RL. It balances the expressive power and the oversmoothing issue of GNNs and could distinguish graphs and connected nodes the same time. Both ResiNet and FireGNN general enough to be applied to variety of problems in graph theory, network theory, combinatorial optimization, machine learning, and their applications.
An interesting direction of future work is to obtain better approximation algorithm for the persis- tence diagram. The current implementation includes an average operation across the entire filtration, which is computationally expensive when the graph is large and forces truncate the filtration in our implementations. An efficient and accurate approximation algorithm will grant FireGNN better feasibility in real applications.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Mehmet E. Aktas, Esra Akbas, and Ahmed El Fatmaoui. Persistence homology of networks: methods and applications. Applied Network Science, 4(1):1-28, 2019.
Réka Albert and Albert-LászIó Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47, 2002.
Marcin Andrychowiez, Anton Raichuk, Piotr Stańczyk, Manu Orsini, Sertan Girgin, Raphaël Marinier, Leonard Hussenot, Matthieu Geist, Olivier Pietquin, Marein Michalski, Sylvain Gelly, and Olivier Bachem. What matters for on-policy deep actor-critic methods? A large-scale study. In International Conference on Learning Representations, 2021.
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Graph edit distance computation via graph neural networks. CoRR, 0ass/1808.06688 2018. URL http://arxiv
oxg/ab3/1808. 05689
Stefano Boccaletti, Vito Latora, Yamir Moreno, Martin Chavez, and D-U Hwang. Complex net- works: Structure and dynamics. Physics Reports, 424(4-5):175-300 2006.
Béla Bollobás and Oliver Riordan. Robustness and vulnerability of scale-free random graphs. In- ternet Mathematics, 1(1):1-35, 2004.
Pierre Buesser, Fabio Daolio, and Marco Tomassini. Optimizing the robustness of scale-free net- works with simulated annealing. In International Conference on Adaptive and Natural Computing Algorithms, pp. 167-176. Springer, 2011.
Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie- Yan Liu, and Liwei Wang. GraphNorm: A principled approcch to accelerating graph neural network training. CoRR, abs/2200.03224, 2020. URL httph:: org. abs/ 2009. 03294
Vincenza Carchiolo, Marco Grassia, Alessandro Longheu, Michele Malgeri, and Giuseppe Man- gioni. Network robustness improvement via long-range links. Computational Social Networks, 6 (1):1-16, 2019.
Hau Chan and Leman Akoglu. Optimizing network robustness by edge rewiring: a general frame- work. Data Mining and Knowledge Discovery, 3065):1395-14255 2016.
Herbert Edelsbrunner and John Harer. Persistent homology-A survey. Contemporary Mathematics, 453:257-282, 2008
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, volume 96, pp. 226-231, 1996.
Changjun Fan, Li Zeng, Yizhou Sun, and Yang- Yu Liu. Finding key players in complex networks through deep reinforcement learning. Nature Machine Intelligence, pp. 1-8, 2020.
Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large TSP instances. CoRR, abs/2012.10658, 2020.
10658
Marco Grassia, Manlio De Domenico, and Giuseppe Mangioni. Machine learning dismantling and early-warming signals of disintegration in complex systems. arXiv preprint arXiv:2101.02453, 2021.
Xiaojie Guo and Liang Zhao. A systematic survey on deep generative models for graph generation. CoRR, abs/2007.06686, 2020.
Xiaojie Guo, Lingfei Wu, and Liang Zhao. Deep graph translation. CoRR, abs/1805 1tt/1/805009990 2018.
URL http:http///xii// org/ abs/ / 1805. 09980)
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning graphs. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 162664126. PMLR, 13-18 Jul 2020.
10

---

Under review as a conference paper at ICLR 2022
Christoph Hofer, Florian Graf, Bastian Rieck, Mare Niethammer, and Roland Kwitt. Graph filtration learning. In International Conference on Machine Learning, pp. 4314-4323, PMLR, 2020.
Petter Holme, Beom Jun Kim, Chang No Yoon, and Seung Kee Han. Attack vulnerability of complex networks. Physical Review E, 65(5):056099 2002.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitmik. Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenRe- view.net, 2020. URL
dww.:neeeeoodddeeeneee.... HJIWAJSFDH
Shengyi Huang and Santiago Ontañón. A closer look at invalid action masking in policy gradient algorithms. CoRR, abs/2006. 14171, 2020. URI. //ax:::////xvv// htt.:/tss///a...oooo//bb//////// 2006 1 4 71
Swami Iyer, Timothy Killingback, Bala Sundaram, and Zhen Wang. Attack robustness and centrality of complex networks. PloS One 8(4):e59 2013.
Chaitanya K. Joshi, Thomas I Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. CoRR, abs/1906.01222 2019. URL http://
arxiv. www.v/org/aaae abs/ 1906. 01227
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Process- ing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS http::ttts//pp/aceeaeae
2020, December 6-12, 2020, virtual, 2020. paper 2ttp:/22///// hhsh/ 19185a 90
neurips. cc/ html
Elias B. Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems 30; Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6348 6358, 2017. URL /tttps::/prroceeedd.ng.. mew.eddddinnnnnnne.u...ee..... newrips..... cc/ naper/2017:0 1000///ah////// http//ashh//999996 A989619668888. aaaaa9933ddd0 Saa -ab- .ttll
P. Diederik Kingma and Lei Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self- normalizing neural networks. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Ad- vances in Neural Information Processing Systems 30: Annual Conference on Neural In- formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA. USA, pp. 971-980, 2017. URL
neur ips. 2tcp//aper/2011/haaaee Abst html
5d44ee6f2c3 117
Vito Latora and Massimo Marchiori. Efficient behavior of small-world networks. Physical Review Letters, 37(19):19870) 2001.
Vito Latora and Massimo Marchiori. Economic small-world behavior in weighted networks. The European Physical Journal B-Condensed Matter and Complex Systems, 32(2):249-263, 2003.
Henrique Lemos, Marcelo O. R. Prates, Pedro H. C. Avelar, and Luis C. Lamb. Graph colouring meets deep learning: Effective graph neural network models for combinatorial problems. In 31st IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2019, Portland, OR, USA, November 4-6, 2019, pp. 879-885, IEEE, 2019, doi: 10.1109//CTA12201000002. URL https::/doi. org. 1.00.1100 11011119///0 AL09/ICCAA, 2019.000223
Guohao Li, Chenxin Xiong, Ali K. Thabet, and Bernard Ghanem. DeeperGCN: All you need to train deeper gens. CoRR, abs/2006.07739, 2020a. www.:httsss//arxii.oor/////////p
07739
Pan Li, Yanbang Wang. Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33, 2020b.
11

---

Under review as a conference paper at ICLR 2022
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- semi-super learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018a.
Wenguo Li, Yong Li, Yi Tan, Yijia Cao, Chun Chen, Ye Cai, Kwang Y Lee, and Michael Pecht. Maximizing network resilience against malicious attacks. Scientific Reports, 9(1):1-9, 2019.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph con- volutional networks and guided tree search. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp- 537-546, 2018b. URL httpp::/pproceeenngggn neuree Bd3bba74255 / /tteee//cccc5c55225522328333 Absttarrattt.aataatc.a...... html
cc/paper/2018/haste
Abstract
Sourav Medya, Tianyi Ma, Arlei Silva, and Ambuj Singh. A game theoretic approach for k-core minimization. In Proceedings of the 19th International Conference Autonomous Agents and MulliAgent Systems, AAMAS '20, pp. 1922-1924. International Foundation for Autonomous Agents and Multiagent Systems, 2020. ISBN 978 97844503751
Damon Mosk-Aoyama. Maximum algebraic connectivity augmentation is NP-hard. Operations Research Letters, 36(6):677-679, 2008.
MohammadReza Nazari. Afshin Oroojlooy. Lawrence V. Snyder, and Martin Takác. Reinforce- ment learning for solving the vehicle routing problem. Samy Bengio, Hanna M. Wal- lach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Ad- vances in Neural Information Processing Systems 31: Annual Conference on Neural Informa- fion Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 9861-9871 2018 URL
wtw.eeeeedding....iieeeeee wttperisss.cccpepeeeeeee http://a....aaocoopp/////////aa. httpppprr/218//haa.. .html
Bo Peng. Jiahai Wang, and Zizhen Zhang. A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems. CoRR, abs/2002.03282, 2020. URL https:
03282
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. GCC: graph contrastive coding for graph neural network pre-training. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash (eds.), KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pp. 1150-1160. ACM, 2020. doi: 141145//394496344036666 URL https:://ddd org 10. 1e..1114/339940 3403168
Lei Rong and Jing Liu. A heuristic algorithm for enhancing the robustness of scale-free networks based on edge classification. Physica A: Statistical Mechanics and its Applications, 503:503-515, 2018.
Christian M Schneider, André A Moreira, José S Andrade, Shlomo Havlin, and Hans J Herrmann. Mitigation of malicious attacks on networks. Proceedings of the National Academy of Sciences, 108(10):338-3841 2011.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1 777700637, 2017. URL htttp://axxiv. org/ abs/
Rakshit Trivedi, Jiachen Yang, and Hongyuan Zha. GraphOpt: Learning optimization models of graph formation. In International Conference on Machine Learning, pp. 9603-9613. PMLR, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, pp. 5998-6008, 2017.
12

---

Under review as a conference paper at ICLR 2022
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liö, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OpenReview.net, 2019. URL https: //openreview www//forruaa id z AckQ
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-pasinng. arXiv preprini arXiv:2006. 15107, 2020.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL httpppppp:ppppppppitgttgooeeeeee
weweediiinnnnee.eeeeeeeeeee neurips cc/ www.aaapppppppp.
Kazuyoshi Wakuta. Vector-valued markov decision processes and the systems of linear inequalities.
Stochastic Processes and Their Applications, 56(1):159-169, 1995.
Po-Wei Wang, Priya I.. Donti, Bryan Wilder, and J. Zico Kolter. SATNet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Ma- mml..
chine Learning Research, pp. 6545-6554, PMLR, 2019. URL Stess/v93 Delsss/v7/wwag1330 html
Xiangrong Wang, Evangelos Pournaras, Robert E Kooij, and Piet Van Mieghem. Improving robust- ness of complex networks via the effective graph resistance. The European Physical Journal B, 87(9):1-12, 2014.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462. PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https:
//openzeview..o.
A Yasin Yazicroğlu, Magnus Egenstedt, and Jeff's S Shamma. Formation of robust multi-agent net- works through self-organizing random regular graphs. IEEE Transactions on Network Science and Engineering. 2(4): 2015.
Deheng Ye, Zhao Liu, Mingfei Sun, Bei Shi, Peilin Zhao, Hao Wu, Hongsheng Yu, Shaojie Yang. Xipeng Wu, Qingwei Guo, et al. Mastering complex control in moba games with deep reinforce- ment learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 6672-6679, 2020.
Emre Yoleu and Barnabás Póczos. Learning local search heuristics for boolean sat- isfiability. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Infor- mation Processing Systems 32: Annual Conference on Neural Information Process- ing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 7990 8001, 2019. URL ptttp:://proceedings. http:///wwppooaa..ooocooccaaaaaa cc/ppappr/r//11///ass/ 4e6dff 3dbe2 Abst html
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay S. Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. Samy Bengio, Hanna M. Wal- lach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Ad- vances in Neural Information Processing Systems 31: Annual Conference on Neural Informa- tion Processing Systems 2018. NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 6412 6422, 2018 URL d60678e88 (at.ee222bbacaaa 9obba9 66677887h0c2003333keee1111----23
Jiaxuan You, Jonathan Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12):10737-10745 May 2021.
13

---

Under review as a conference paper at ICLR 2022
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan-Tiees Lin (eds.), Advances in Neural Information Process- ing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL http:///ooeeeddegeeee / wwwrinuuppp...m cc/ .html
James Jian Qiao Yu, Wen Yu, and Jiatao Gu. Online vehicle routing with neural combinatorial optimization and deep reinforcement learning. IEEE Trunsactions on Intelligent Transportation Systems, 20(10):3806 38177 2019. doi: 10.1109/TTTS org/10. 11/11011109/IIIS0 2011
URL https: //doi.
Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. Finding critical users for social network engagement: The collapsed k-core problem. In Satinder P. Singh and Shaul Markovitch (eds.). Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA. pp. 245-251, AAAI Press, 2017. URL http:h//aaaa org/ocs, index wwtpppppp/pppppppppppppp.pppppwp AAAI/AAII///// http://AAA11/pppa/reraee 14349
Kangfei Zhao, Zhiwei Zhang, Yu Rong. Jeffrey Xu Yu, and Junzhou Huang, Finding critical users in social communities via graph convolutions. IEEE Transactions on Knowledge and Data Engi- neering, pp. 1-1, 2021. doi: 10. 109//K0EE.2211.3387777
Mingxing Zhou and Jing Liu. A memetic algorithm for enhancing the robustness of scale-free networks against malicious attacks. Physica A: Statistical Mechanics and its Applications, 410: 131-143, 2014.
Qiong Zhou and Janusz W Bialek, Approximate model of european interconnected system as a benchmark system to study effects of cross-border trades. IEEE Transactions on Power Systems, 20(2):782-788, 2005.
A EXTENDED RELATED WORK
Network resilience and utility
Network utility refers to the system's 's quality to provide a certain service, for example transmitting electricity in power networks and transmitting packages in routing networks. A popular metric for network utility is the network efficiency (Latora & Marchiori] 2003 Boccaletti et al.] (0066). Network resilience measures the ability of preventing the utility loss under failures and attacks. Our goal is to improve both network resilience and utility by network structure manipulations.
In many previous works, despite that the resilience could be improved, the utility may dramatically drop at the same time (Li et al.] 2019; Carchiolo et al., 2019 Waan et al.) [2014] [Shhniddrr et al. 2011 Chan Akoglu 2016] Buesser et al. 2011)p This is contradicting with the idea behind improving network resilience and will be infeasible in real-world applications.
Multi-views graph augmentation for GNNs
Multi-views graph augmentation is one efficient way to improve expressive power or combine do- main knowledge, which adapted based on the task's prior (Hu et al., 2020). For example, GCC QQuu et al. (020)) generates multiple subgraphs from the same ego network. DGI (Velickovic et al.) 2019) maximizes the mutual information between global and local information. GCA (You et al., 2020) adaptively incorporates various priors for topological and semantic aspects of the graph. (Has-) sani & Khasahmadi] 2020) contrasts representations from first-order neighbors and a graph diffu- sion. In our problem, two desired properties different edge representations and the capability to predict accurate network resilience gain. Motivated by the calculation process of persistent homol- ogy (Edelsbrunner & Harer 2008), apply the filtration process to enhance the expressive power of GNNs.
Deep graph generation models
Deep graph generation models learn the distribution of given graphs and generate more novel graphs, which could be classified as unconditional generation methods and conditional generation methods
14

---

Under review as a conference paper at ICLR 2022
Figure 5: Illustration of the graph connectivity--asee measurement calculation with a scale-free example graph under node degree-basee based malicious attack. Each snapshot demonstrates the attack on the red node, which removes the red node and its adjacent (dashed) edges, leading to a next remnant graph. The attacker recalculates the node degree and repeatedly seeks for the remaining node with a maximum degree as the next target. In the end, the entire graph becomes disconnected when each node cannot reach other nodes.
Guo & Zhao 2020). Specifically, edge transformation conditioned on another graph (a.k.a. graph translation) is more relevant to our work since the edge rewiring process can be regarded as opera- tions on the previous graph via edge addition and deletion. Some works utilize the encoder-decoder framework by learning latent representation of the input graph through the encoder and then gen- erating the target graph through the decoder. For example, GCPN (You et al., 2018) incorporates chemistry domain rules on molecular graph generation. GT-GAN (Guo et al. (2088) proposes a GAN-based model malware cyher-network synthesis. GraphOpt (Trivedi
al. 2020) learns
an implicit model to discover an underlying optimization mechanism of the graph generation us- ing inverse reinforcement learning. Although exploiting similar encoder-decoder framework, our approach differs from existing works by the rigid constraint of the studied task: node degree preser- vation, which imposes additional requirements for the expressive power of GNNs.
B DEFINITIONS OF DIFFERENT OBJECTIVE FUNCTIONS
In this section, we present resilience definitions and utility definitions used in experiments.
B. RESILIENCE DEFINITIONS
Three kinds of resilience metrics are considered:
The graph cannectvvity-base measurement (Shhneider et al. 2011 is defined as
1 N
R(G)
$()).
where s(q) is the fraction nodes in the largest connected remaining graph after removing g nodes from graph G according to certain attack strategy, shown in Figure The range of possible values of R is [1/N, 1/2], where these two extreme values correspond to a star network and fully connected network, respectively.
The spectral radius (SR) denotes the largest eigenvalue A of an adjacency matrix.
The algebraic connectivity (AC) represents the second smallest eigenvalue of the Laplacian matrix of G.
15

---

Under review as a conference paper at ICLR 2022
B.2 UTILITY DEFINITIONS
In this paper, the global and local communication efficiency are used as UWO measurements of the network utility, which widely applied across diverse applications of network science, such as transportation and communication networks (Latora Marchiori, 2003 Boccaletti et al. 2006).
The average efficiency of network G is defined inversely proportional the average over pair- wise distances (Latora & Marchiori 2001 as
F(G) N(N-1 1N
Σ
d(1,))
ijjEV
where N denotes the total nodes in network and d(i,,) denotes the length of the shortest path between node i and another node j.
Given the average efficiency, we can calculate the global efficiency and local efficiency.
The global efficiency of a network G is defined as (Latora & Marchiori, 2001 2003
E(G)
Egglobal (G)
((Gideat)
where Gideal is the "ideal" fully-connected graph on nodes, and the range of Egtobat (G) is [0, 1].
The local efficiency of a network G measures a local average of pairwise communication efficiencies and is defined (Latora & Marchiori] 2001)
Froeat
N Σ F(G.),
where G2 is the local subgraph including only node i's one-hop neighbors, but not the node itself. The range of Froeat (G') is [0, 1].
C IMPLEMENTATION DETAILS OF RESINET
In this section, we provide the implementation details of ResiNet, including dataset, network struc- ture training strategies and node feature construction. Moreover, discussed the role of FireGNN in ResiNet and analyze current limitations of ResiNet and future work.
C.I DATASET
We first present the data generation strategies. Synthetic datasets are generated using the Barabasi- Albert (BA) model (known as scale-free graphs) (Albert & Barabási 2002), with the graph size varying from |
-|00000. During the data generation process, each node is connected to
two existing nodes. BA graphs are chosen since they are vulnerable to malicious attacks and are commonly used to test network resilience optimization BeaeritnmsBBolloba & Riordan 2004). We test the performance of ResiNet on both transductive and inductive settings.
Transductive setting The algorithm is trained and tested on the same network.
Randomly generated synthetic BA networks, denoted by BA-m, are adopted to test the performance of ResiNet on networks of various sizes, where m E (15, 50, 100) is the graph size.
The real EU power network (Zhou & Bialek 2005 is used to validate the performance of ResiNet on real networks.
Inductive setting Two groups of synthetic BA networks denoted by BA-m-n are ran- domly generated to test ResiNet's inductivity, where m is the minimal graph size, and n indicates the maximal graph size. We first randomly generate the fixed number of BA net- works as the training data to train ResiNet and then evaluate ResiNet's performance directly the test dataset without any additional optimization. We only consider ResiNet for the inductive setting since other methods are all transductive.
Table 2 summarizes the statistics of each dataset.
16

---

Under review as a conference paper at ICLR 2022
Table 2: Statistics of graphs used for resilience maximization. Both transductive and inductive settings (+) are included. Consistent with our implementation. we report the number of edges by transforming undirected graphs to directed graph so that the edge rewiring has the fixed execution order. For the inductive setting, we report the maximum number of edges. The action space size of the edge rewiring is measured by E/
Dataset
Node
Edge
Action Space Size
Train/Test
Setting
BA-15
15
54
5832
Null
Transductive
BA-50
50
192
73728
Null
Transductive
BA-100
100
392
307328
Null
Transductive
EU
217
640
819200
Null
Transductive
BA-10-30 (+)
10-30
112
25088
1000/500
Inductive
BA-20-200 (+)
20-200
792
1254528
4500/360
Inductive
C.2
RESINET SETUP
In this section, we provide detailed parameter setting and training strategies for ResiNet.
Our proposed FireGNN is used as the graph encoder in ResiNet, including 5-layer defined GIN (Xu et 2019 as the backbone. The hidden dimensions for node embedding and graph embedding in each hidden layer are set to 64 and the SeLU activation function (Klambauer al. 2017 is used after each message passing propagate (Li al. 2020a). Graph normalization strategy is adopted to stabilize the training of GNN (Ca et al. (020). The jumping knowledge network (Xu et al. 2018) is used to aggregate node features from different layers the GNN.
The overall policy is trained by using the highly tuned implementation of proximal policy optimiza- tion (PPO) algorithm (Schulman et al.] 2017). Several critical strategies for stabilizing and accel- erating the training of ResiNet are used, including advantage normalization (Andrychowiez al., 2021]. the dual-clip PPO (the dual clip parameter is set to 10) (Ye et al.) (020). and the usage of different optimizers for policy network and value network. Additionally, since the step-wise reward range is small (around 0.01), we scale the reward by factor of 10 to aim the training of ResiNet. The policy head model and value function model use two separated FireGNN encoder networks with the same architecture. ResiNet is trained using two separate Adam optimizers (Kingma & Ba 2015) with batch size 256 and linearly decayed learning rate of 0.0007 for the policy network and lin- early decayed learning rate of 0.0007 for the value network. The aggregation function of FireGNN is defined as an attention mechanism- based linear weighted combination.
C.3 NODE FEATURE CONSTRUCTION
The widely-used node degree feature cannot significantly benefit the network resilience optimization of a single graph due to the degree-preserving rewiring. Therefore, we construct node features for each input graph to aid the transductive learning and inductive learning, including
The 8-dimensional position embedding originating from the Transformer (Vaswani al. (017)) is adopted as the measurement of the vulnerability of each node under attack. If the attack order available, we can encode into the position embedding. the attack order is unknown, node degree, node betweenness, and other node priority metrics can be used for approximating the node importance practice.
The distance encoding strategy (Li al. 20206).
One-hot encoding denoting whether the attack causes the node removal just because all adjacent nodes are removed.
C.4 BASELINE SETUP
All baselines share the same action space with ResiNet, and they uses the same action masking strategy to block invalid actions as ResiNet does. The maximal objective evaluation is consistent for all algorithms. Other settings of baselines are consistent with the default values in their paper.
17

---

Under review as a conference paper at ICLR 2022
35%
25%
gain
15%
10%
0%
200000 Total limesteps
520300
Figure 6: Experiments on the BA-15 dataset to study the effect of the filtration order on FireGNN in maximizing resilience. Results are averaged over runs.
The carly-stopping strategy is used for baselines. which means the search process terminates if no improvement is obtained in successive 1000 objective function calling trials.
D ABLATION STUDY AND EXTENDED EXPERIMENTAL RESULTS
In this section, we provide the ablation study about the importance of FireGNN and present addi- tional experimental results.
D.I FIREGNN
In FireGNN, the total number of subgraphs involved in calculating the final node embedding, edge embedding, and graph embedding, are determined by the filtration order K = means only the original graph is used and K N - means there are total N subgraphs used. We run a grid search to explore the effect of the filtration order on ResiNet's performance. As shown in Figure ResiNet only achieves minor gain of around 5% without FireGNN. The performance improved significantly with K greater than zero, and ResiNet obtained the optimal resilience gain of about 35 % BA-15 when K 5. We only report the performance when K since the BA-15 loses all connections when more than eight critical nodes are removed.
[0, N - 1]. where
Besides the BA-15 dataset, also conducted the ablation experiments of FireGNN large datasets, including the BA-50, BA-100, and EU power network. We found that without FireGNN, ResiNet hardly learns find positive gain, often chooses to stop the first step, which may further validate the effectiveness of FireGNN.
is worth pointing out that the task-dependent order of node removal will affect the filtration. For example, the scale-free networks lost all connections under the degree-based attack on half nodes on average, while it maintains most topologies under some other attacks. For the network resilience task, we are inspired by the definition of the graph connectivity baaed resilience metric, with the adaptive node degree centrality determine the node removal order. Nodes with larger degrees are first removed, and the ties are broken by arbitrary.
provide possible reasons why FireGNN is critical for network resilience task as
Each rewire only changes the graph by four edges, so the graph embedding and the node embedding may not change significantly at two steps provide essential information for the RL agent to make new accurate decisions. For example, we empirically found that the RL agent stick into action loop, which means that after the rewiring of A-C and B-D to obtain A-B and C-D at step t, the agent may choose to rewire the new forming edges back step & forming infinite loop.
18

---

Under review as a conference paper at ICLR 2022
Table Performance gain (in percentage) of ResiNet in optimizing varying objectives on the BA- network. All objectives are optimized with the same syper-parametent which means that we did not tune hyper-parameters for objectives except for RD-
Objective
Gain (%)
Objective
Gain(%)
RDD
35.3
RB
14.6
SRD DC
15.3
SR
15.3
48.2
AC
43.2
RD Eglobal
14.2
RB Eglobal
13.1
SRD Egiobal
14.6
S
15.0
AC + Eeglobal
34.0
ACB Eiglobol
31.3
RD + Ftocal
24.4
Rn + Fitecal
39.4
SRD Esocal
17.3
SRB + Elocal
21.2
AC + Elocal
9.4
ACB + Biocul
15.1
The dominating nodes may potentially be regarded outliers which can shade other nodes' unique features, which is problematic for the agent's 's learning to distinguish different nodes. By removing the dominating nodes, the residual nodes each subgraph have the freedom to express their salient features.
It might also be potentially valuable for other edge embedding-based tasks, such as graph generation, recommendation, and link prediction.
D.2 MORE EXPERIMENTAL RESULTS
This section provides additional experimental results, including the optimization with different silience and utility metrics and validating ResiNet's inductivity on larger datasets. Finally, we ana- lyze the current limitations of ResiNet.
D.2.1 LEARNING TO BALANCE MORE UTILITY AND RESILIENCE METRICS
As shown in Figure that ResiNet can learn to optimize graphs with different resilience and utility metrics and defend against other types of attacks besides the node degree-based attack, such the node betweenness- based attack.
conduct extensive experiments the BA-15 network to demonstrate
Table records the improvements in percentage of ResiNet for varying objectives the BA-15 dataset. As visualized in Figure ResiNet is not limited to defend against the node degree-based attack (Figure 7 (b)-(i) and also learns defend against the betweenness-based attack (Figure 7 (s)- Total three resilience metrics are used, with R denoting the graph connectivity bbase resilience metric, SR being the spectral radius and SR representing the algebraic connectivity. Total two utility metrics are adopted, including the global efficiency Eggobat and the local efficiency Ftoeat- Not surprisingly, the optimized network with an improvement of about 3.6% for defending the betweenness-be based attack also has higher resilience (around 7.8%) against the node-degree attack. This may be explained as the similarity between node degree and betweenness for a small network.
To balance utility and resilience simultaneously, the distribution of Pareto points obtained by ResiNet on the BA-15 dataset in Figure 8 jimplies that the maximization of the resilience and utility may not be satisfied simultaneously. The simultancous improvements in resilience and utility could occur if the poorly designed original network has weak resilience and utility.
D.2.2 INDUCTIVITY ON LARGER DATASETS
Even with limited computational resources, armed with the autoregressive action space and the power FireGNN, ResiNet can be trained fully end-to-end on graphs with hundreds of nodes using RL. We demonstrate the inductive ability of ResiNet graphs of different sizes by training ResiNet on the BA-20-204 dataset, which consists of graphs with the size ranging from 20 to 200, and then report its performance directly guiding the edges selections unseen test graphs. The filtration
19

---

Under review as a conference paper at ICLR 2022
(a) Original
(b) Rp
(c) SRD
(d) ACD
(e) RD Eglobal
(I) SR + Egtobal
(g) D Egtobal
(h) Rp Eisent
(i) S + Etocol
ii AC Eiocal
(k) Ra
(I) SR
(m) AC
(n) Ra Egtobal
SR S
(p) ACB + Egglbal
(q) Ra + Frocal
(1) SRa+ Frocat
(s) ACB + Frocat
Figure 7: The resilience maximization on the BA-15 dataset with 15 nodes and 27 edges with (a) original network, (b)-() results of defending the node degree-based attack with different combina- tions of resilience and utility, and (k)-(s) results of defending against the node betweenness-baa attack with varying combinations of resilience and utility. For three resilience metrics, R denotes the graph connectivity-basee resilience metric; SR is the spectral radius; SR represents the alge- braic connectivity. For two utility metrics, Eglohat denotes the global efficiency, and Etocat is the local efficiency.
order K is set for the computational limitation. As shown in Figure 9 can that ResiNet has the best performance for N E [70, 100). The degrading performance with the graph size may be explained by the fact that larger graphs require a larger filtration order for ResiNet work well. A more stable performance improvement of ResiNet is observed with the increment of graph size when trained to optimize network resilience and utility simultaneously, and ResiNet possibly finds a strategy to balance these two metrics.
D.2.3 INSPECTION OF OPTIMIZED NETWORKS
Moreover, to provide deeper inspection into the optimized network structure, we take the EU power network as an example to visualize its network structure and the optimized networks given by ResiNet with different objectives. Comparing to the original EU network, Figure 10 (b) is the network structure obtained by only optimizing the graph connectivity- observe more crowded region on the left, consistent with the "onion-like" structure concluded in previous studies. If we consider the combination gain of both resilience and utility, we observe a more compact clustering "crescent moon"-like structure shown in Figure (c).
resilience. We can
20

---

Under review as a conference paper at ICLR 2022
0.30
alpha
0.2
0.4
0.28
0.8
Resilence
1.0
0.28
0.22
Utitty (global efficiency)
Figure 8: Pareto points obtained by ResiNet of balancing various combinations of resilience and utility on the BA-15 dataset. The resilience metric is the graph connectivity- resilience, and the utility metric is the global efficiency. Results are averaged over three runs.
-0 15
D:02
un gatt
8.15
0.30
B-4
03
02
0.
Weighted
-22
25
80
100
125
150
176
250
100
Graph size RV
Crephaizo
(a) Inductivity on resilience
(b) Inductivity resilience and utility
Figure 9: The inductive ability of ResiNet on the test dataset (BA-20-200) when optimizing (a) network resilience and (b) the combination of resilience and utility.
(a) Original network
(b)
(0) Eglobat
Figure 10: Visualizations of the original EU network and optimized networks using ResiNet with different objectives: R means the connectivity-baat resilience measurement and Eglobal is the global efficiency.
21

---

Under review as a conference paper at ICLR 2022
Table Resilience optimization algorithm under the fixed maximal rewiring number budget of 200. We report the weighted combination of the graph coneeciviity-base resilience and the network efficiency improvement (in percentage) with the weighted coefficient a E {0,0.5) Results are averaged over 3 runs. We report the rewiring number inside the bracket.
Method
Q
BA-15
BA-50
BA-100
EU
0
26.8 (10.0)
52.1 (47.0)
76.9 (97.3)
71.9 (152.7)
HC
0.5
18.6 (11.3)
43.1 (62.7)
56.9 (121)
63.2 (200)
0
26.8 (20)
49.7 (59.0)
84.5 (119.7)
73.5(160.3)
SA
0.5
17.8 (21)
41.1 (79.7)
57.7 (127.7)
62.8 (200)
23.5 (6.0)
(13.0)
Greedy
0.5
5.3 (15.0)
34.7 (13.0)
0
(1)
50.2
61.9 ())
66.2 ()
EA
0.5
27.1 (g)
38.3
46.6 ())
58.4 ())
0
(2)
0
(
9.0 9.0)
GNN+RL
0.5
(0)9
(1)
(
(20)
0
(6)
61.5 (20)
(200
54.2 (20)
ResiNet
0.5
26.9 (20)
53.9 (20)
53.1 (20)
51.8 (20)
Table 5: Running speed (in second) of the resilience optimization algorithm under the fixed maximal rewiring number budget 20 and 200 (in bracket). Results are averaged over 3 runs.
Method
BA-15
BA-50
BA-100
EU
1.0 (1.0)
1.1 (6.4)
1.3 (22.2)
3.1 (94.2)
HC
0.5
1.5 (11.5)
1.1 (12.8)
2.0
5.3 (193.7)
0
1.1 (1.1)
0.3 (6.6)
0.2.66
(91.2)
SA
0.5
0.7 (1.7)
0.7 (13.2)
(47.5)
(1935))
0
(6.0)
(34.5)
766.3
3061.7
Greedy
0.5
0.7 (0.7)
64.1 (65.4)
(V
6192.6
0.01
0.1
(.59
0.2
EA
0.5
0.01 ())
0.1
0.8
0.4
0.05
0.1
0.13
3.6()
GNN+RL
0.5
0.05
0.1
0.19
4.5
0.47())
18
2.23
4.5()
ResiNet
0.5
0.48 ())
1.89
2.4
5.2
D.2.4 PERFORMANCE COMPARISONS UNDER A LARGE REWIRING BUDGET
In this section, we present the resilience improvement and the required number of edge rewiring of each algorithm under large rewiring budget of 20. The running speed is also presented compare the running time efficiency of each algorithm.
As shown in Table traditional methods improve the network resilience significantly compared to ResiNet under large rewiring budget of 200. However, traditional methods are still undesired in such a case since a solution with large rewiring budget not applicable in practice due the vast cost of adding many new edges into real system. For example, the actual number of rewiring budget for EA is hard to calculate since it is population-bass algorithm, so it is omitted Table All baselines adopt the early-stopping strategy that they will terminate if there is positive resilience gain in a successive 1000 steps.
Table indicates that the time it takes for the benchmark algorithm to solve the problem usually increases as the test data set size increases. contrast, once trained, our proposed ResiNet is suitable for testing large datasets since the model size is fixed.
22

---

Under review as a conference paper at ICLR 2022
D.2.5 LIMITATIONS
It should be noted that the weighted combination of resilience and utility setting can be slightly un- fair for ResiNet due to the additional RL training burden. Despite our highly tuned implementation of ResiNet, training RL known challenging, with two reward functions with different ranges posing another challenge. Moreover, due to limited computational resources, we only train ResiNet with all non-empty subgraphs FireGNN on the BA-15 network as transductive and BA-10-30 network
inductive setting. For networks with more than 50 nodes, we only use the top-2 subgraphs in the filtration, as we observed to balance the computational effort and the satisfying performance. This may explain the performance of ResiNet is slightly weaker than several baselines on larger networks.
Another point is that for ResiNet, the maximum episode length is set to 20 steps on all graphs, which means all solutions given by ResiNet require no longer than 20 edge rewiring operations. For example, the optimal solution obtained by ResiNet defending against node degree-based attacks on BA-15 only requires a minimum of six steps to arrive at the target graph. A larger filtration order, longer episode length, powerful RI. learning algorithm should be expected boost the performance of ResiNet further.
Despite the success of ResiNet armed with our proposal FireGNN in both the transductive and inductive settings, we empirically observe that the trained agent only works well on the unseen datasets with similar setting as training. How improve further the inductivity of ResiNet is left as another future work.
23


Reviews:
[{"review_id": "q16ikwyuB_N", "reviewer": "Reviewer_Qtac", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positives:\n\n+ The problem is relevant. In particular, the idea of neural approaches to increase network resilience is interesting. \n+ The paper is easy to follow.\n\nNegatives:\n\n-  Method: The paper overclaims a bit. Among the three major points in the introduction (utility, local optimality, and transductivity); the last two are already addressed by previous methods that use reinforcement learning with graph neural networks (GNNs). Please refer to the survey [1] and especially [2]. It is also a little surprising to see the paper is not positioned in the context of those existing works that are very similar [1] in terms of frameworks. Given those, It is difficult to assess the additional technical novelty of the proposed method. The paper could be improved by focusing on specific challenges (such as scalability) that the rewiring problem has while working with this framework. The proposed method's efficiency is also unclear as there is no analysis of efficiency. \n\n[1] Mazyavkina, Nina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. \"Reinforcement learning for combinatorial optimization: A survey.\" Computers & Operations Research (2021): 105400.\n[2] Dai, Hanjun, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. \"Learning combinatorial optimization algorithms over graphs.\" NeurIPS, 2017.\n\n\n- Experiments: The experiments can be significantly improved.\n\na) The experiments have small datasets. Besides they are mostly synthetic. From Table 1, it is also difficult to say that the proposed method, ResiNet is a superior method.\n\nb) There is no comparison with non-neural approaches in terms of efficiency. One of the major reasons for going to the neural version is to be able to test on big data while training on small ones. The neural approaches might be able to outperform the non-neural methods at least in terms of efficiency.\n\n c) There are no comparisons with other neural baselines that address graph combinatorial problems via neural approaches especially the ones which use reinforcement learning.\n\nd) Why are the number of rewired edges not being compared among different methods? The paper claims that the proposed method uses a low number of edges to rewire to achieve high network resilience.\n\n\n\n - Motivation:\nThe motivation going into the neural version is not clear. Why will someone use a neural algorithm compared to the non-neural ones? The context where the algorithm needs to be used repetitively might motivate this in a better way (please refer to Khalil et al., NeurIPS, 2017). Could you provide other types of use cases?", "summary_of_the_paper": "The paper proposes a neural approach that increases network resilience by edge wiring. The approach uses a combination of graph neural network (GNN) and policy gradient method to do so. The experiments use a few small networks and several non-neural baselines. ", "summary_of_the_review": "The novelty of the proposed method is unclear and the experiments need major improvement.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nV3dF3PcxDc", "reviewer": "Reviewer_vtoA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The proposed reinforcement learning based framework is suitable for the rewiring task. Meanwhile, the framework can generalize to unseen graphs since the edge rewiring policy can be directly applied to other graphs.\n\nWeaknesses:\n\n1. My main concern is the empirical performance of the proposed framework. Specifically, the proposed framework performs much worse than baseline approaches on large graphs (BA-100 dataset, EU dataset) as shown in Table 1. Also, the improvements on BA-15 dataset and BA-50 dataset are not significant. \n\nQuestions and suggestions:\n\n1. I suggest the authors put the ablation study on the FireGNN and the new framework. For example, what is the performance of ResiNet using a standard GNN architecture (not using FireGNN)? What is the performance of replacing standard GNN with FireGNN in the previous method (not using the RL-based framework ResiNet)? These may help better understand the role of the architecture and the RL-based framework.\n\n2. As mentioned in Section 4.2 (Page 8), 'Note that this comparable performance is under a much fewer number of rewiring operations.' Could the authors provide the number of rewiring operations of each method in Table 1? \n\n3. As mentioned in Section 3.3.1 (Page 6), 'where $G^{(k)}$ denotes the remaining graph after removing $N-k$ nodes in a particular task-dependent order'. Could the authors clarify how the task-dependent order is determined? \n\nTypo:\n\n1. $d_i = \\sum_{i=1}^{N}A_{ij}$ in Section 3.1 (Page 4).", "summary_of_the_paper": "This paper studies how to improve network resilience by proposing a reinforcement learning-based framework named **ResiNet** and a new GNN architecture called **FireGNN**. The proposed framework is able to directly generalize to unseen graphs. The new GNN architecture applies the graph filtration process, which enhances the expressivity of GNN. The authors conduct experiments on synthetic and real datasets to compare the proposed framework with previous baseline methods.", "summary_of_the_review": "This paper proposes a new RL-based framework together with a new GNN architecture for improving network resilience. The new frameworks can generalize to unseen graphs. However, the empirical performance of the framework is not convincing on the tasks considered in this paper. \n\n\n=============================after response=============================\n\nThe updated results in the revision resolve some of my main concerns. I decide to raise my recommendation score from 5 to 6.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "j_UoNs756a", "reviewer": "Reviewer_AvkM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\na new approach based on neural networks. \n\nWeaknesses\n\nThe main motivation is to improve the robustness of infrastructure networks such as power networks.  While rewiring an edge sounds straightforward on a graph, it is tremendously difficult in a physical network, e.g. adding a new road or a new power line. Furthermore, the functionality of a physical network is beyond nodes and links. For example, for a power network, power flow is determined by power flow equations. So considering the graph structure alone, without the dynamics of the systems, is not sufficient. ", "summary_of_the_paper": "The paper proposes a neural network based algorithm for edge rewiring. ", "summary_of_the_review": "The problem is not very motivated. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an RL technique for dealing with the problem of network (graph) rewiring for robustness against attacks. Graph rewiring has been studied in a variety of fields, including graph theory (graph abstraction), graph ML (adversarial robustness, performance of GNNs), and combinatorial optimization. Reviewers had concerns with novelty, the correctness of some of the statements, and empirical evalution (in particular, baselines and scalability). While the rebuttal addressed some of the concerns, the overall feel about the paper is lukewarm and the AC believes the paper is below the bar.
Decision: Reject