Learning to Boost Resilience of Complex Networks via Neural Edge Rewiring
Authors: Shanchao Yang
MA KAILI
Tianshu Yu
Baoxiang Wang
Hongyuan Zha
Venue: Submitted to ICLR 2023 (2023)
Keywords: complex networks
network resilience
network robustness
graph neural networks

Abstract: The resilience of complex networks, a critical structural characteristic in network science, measures the network's ability to withstand noise corruption and structural changes. Improving resilience typically resorts to minimal modifications of the network structure via degree-preserving edge rewiring-based methods. Despite their effectiveness, existing methods are learning-free, sharing the limitation of transduction: a learned edge rewiring strategy from one graph cannot be generalized to another. Such a limitation cannot be trivially addressed by existing graph neural networks (GNNs)-based approaches since there is no rich initial node features for GNNs to learn meaningful representations. However, neural edge rewiring relies on GNNs for obtaining meaningful representations from pure graph topologies to select edges. We found existing GNNs degenerate remarkably with only pure topologies on the resilience task, leading to the undesired infinite action backtracking. In this work, inspired by persistent homology, we specifically design a variant of GNN called FireGNN for learning inductive edge rewiring strategies. Based on meaningful representations from FireGNN, we develop the first end-to-end inductive method, ResiNet, to discover $\textbf{resi}$lient $\textbf{net}$work topologies while balancing network utility. ResiNet reformulates network resilience optimization as a Markov decision process equipped with edge rewiring action space and learns to select correct edges successively.  Extensive experiments demonstrate that ResiNet achieves a near-optimal resilience gain on various graphs while balancing the utility and outperforms existing approaches by a large margin.

Under review as a conference paper at ICLR 2023
LEARNING TO BOOST RESILIENCE OF COMPLEX NET- WORKS VIA NEURAL EDGE REWIRING
Anonymous authors Paper under double-blind review
ABSTRACT
The resilience of complex networks, a critical structural characteristic in network science, measures the network's ability to withstand noise corruption and structural changes. Improving resilience typically resorts to minimal modifications of the network structure via dlegree-preserving their effectiveness, existing methods are learning-free sharing the limitation of transduction: a learned edge rewiring strategy from one graph cannot be generalized to another. Such a limitation cannot be trivially addressed by existing graph neural networks (GNNs)-baad based approaches since there is no rich initial node features for GNNs to learn meaningful representations. However, neural edge rewiring relies on GNNs for obtaining meaningful representations from pure graph topologies to select edges. We found existing GNNs degenerate remarkably with only pure topologies on the resilience task, leading to the undesired infinite action backtracking. In this work, inspired by persistent homology, specifically design a variant of GNN called FireGNN for learning inductive edge rewiring strategies. Based meaningful representations from FireGNN, we develop the first end-to- end inductive method, ResiNet, to discover resilient network topologies while balancing network utility. ResiNet reformulates network resilience optimization a Markov decision process equipped with edge rewiring action space and learns to select correct edges successively. Extensive experiments demonstrate that ResiNet achieves a near-optimal resilience gain on various graphs while balancing the utility and outperforms existing approaches by a large margin.
edge rewiring-based methods. Despite
INTRODUCTION
Network systems, such as infrastructure systems and supply chains, are vulnerable to malicious attacks. To provide reliable services when facing natural disasters or targeted attacks, networked systems should continue to function and maintain acceptable level of utility when the network partially fails. Network resilience', in the context of network science, is a measurement characterizing the ability of a network system to defend itself from such failures and attacks (Schneider et al., 2011). Studying the resilience of complex networks has found wide applications in many fields, ranging from ecology (Sole& & Montoya, 2001), biology (Motter et al., 2008), economics (Haldane & May, 2011) 1) to engineering (Albert et al., 2004).
To improve network resilience, many learning-fret optimization methods have been proposed, typ- ically falling into the categories of heuristic-based (Schneider et al., 201 1; Chan & Akoglu, 2016; Yazıcioglu et al., 2015; Rong & Liu, 2018) and evolutionary computation (Zhou & Liu, 2014). These methods improve the resilience of complex networks by minimally modifying graph topologies based on a degree-preen prerreeieeeeviigggg atomic operation called edge rewiring (Schneider et al., 2011: 1: Chan & Akoglu, 2016; Rong & Liu, 2018). Concretely, for a given graph G = (V, E) and two existing edges AC' and BD, an edge rewiring operation alters the graph structure by removing AC and BD and adding AB and CD, where AC, BD E E and AB, CD, AD, BC & E. Edge rewiring has some nice properties against simply addition or deletion of edges: 1) preserves node degree, while addition may violate capacity constraints; 2) it achieves minimal utility degradation in terms of graph Laplacian measure- ment, while addition//eletion may lead to a large network utility degradation (Jaume et al., 2020; Ma et al., 2021). Despite their success, ferning-frree methods share the following limitations:
In this paper, network resilience and network resilience are used interchangeahly.

---

Under review as a conference paper at ICLR 2023
Agent
G
Gaze11
AC-BD
B
AB-CD
D
B
Figure 1: Action backtracking in successive edge rewirings since GNNs cannot provide distinguish- able edge representations on graphs without rich features. After selecting AC and BD from G++2x for rewiring step t 2k, the agent would select AB and CD at step + 2k returning back to G(42x and forming a cycled action backtracking between Gr42% and G242k+1-
Transduction. Existing methods for selecting edges for rewiring are transductive since they search the robust topology on particular graph instance. performed for every individual graph without generalization.
This search procedure is
Local optimality. It is NP-hard to combinatorially choose two edges to rewire to obtain the globally optimal resilience (Mosk-Aoyams, 2008). Previous studies predominantly adopt greedy-like algorithms, yielding local optimality in practice (Chan & Akoglu, 2016).
Utility Loss. Rewiring operation in network resilience optimization may lead considerable degradation of the network utility, which may jeopardize the network's functioning.
To knowledge, there is learning-bassee inductive network resilience optimization method. A key challenge is that many network science tasks, including resilience optimization, only have pure topologies without rich node features. GNNs-based learning paradigms have proved powerful in solving a large variety of graph tasks with rich features inductively (Li et al., 2018; Joshi et al., 2019; Fu al., 2020; Khalil al., 2017: Nazari al., 2018; Peng et al., 2020; Yu al., 2019). However, it still remains opaque how to adapt such approaches to graph tasks with only topological structures available, especially graph tasks requiring distinguishable node/edge representations to select correct nodes/edges for constructing a solution sequentially. For example, Boffa et al. (2022) showed that the performance of GNNs degenerates largely solving the traveling salesman problem (TSP) when node coordinate features missing. Similarly, empirically found that the popular framework of GNNs and reinforcement learning (RL) fails to optimize network resilience. The RL agent would be stuck into the undesired infinite action backtracking without the meaningful edge representations, as shown in Figure 1. Readers are referred to Appendix E for a more detailed analysis. Therefore, it is demanding to devise novel GNN that can be applicable for the network resilience optimization task without rich features.
In this work, we overcome the above limitation of GNNs in modeling graphs without rich features and develop the first inductive learning-based method for discovering resilient network topology using successive edge rewiring operations. Inspired by persistent homology and the approximation of the persistence diagram (Edelsbrunner & Harer, 2008; Aktas et al.. 2019; Hofer et al., 2020; Horn et al., 2022), we specially design a purely topology-orienter variant of GNN called Filtration enhanced GNN (FireGNN). FireGNN creates series of subgraphs (the filtration) by successively removing the node with the highest degree from the graph and then learns to aggregate node representations from each subgraph. FireGNN learns meaningful representations via the proposed filtration process.
The main contributions of this paper are summarized as follows:
1) We propose the first tearning-basee method, ResiNet, to boost network resilience without rich node features inductively in degree-preserving manner with moderate utility loss. ResiNet forms resilience optimization into a successive sequential decision process neural edge rewirings. Extensive experiments show that ResiNet achieves near-optimal resilience while balancing network utilities and outperforms existing approaches by a large margin.
2) FireGNN, technical innovation serving as the graph feature extractor, can learn meaning- ful representations from pure topological structures. FireGNN provides sufficient training signals to train RI agent learn successive edge rewiring operations inductively.
2

---

Under review as a conference paper at ICLR 2023
2 RELATED WORK
GNNs for graph-related tasks with rich features. GNNs are powerful tools to learn from relational data with rich features, providing meaningful representations for downstream tasks, Several successful applications using GNNs as backbones include node classification (Kipf & Welling, 2017; Hamilton et al., 2017; Velickovic et al., 2018), link prediction (Li et al., 2020a; Kipf & Welling, 2017: Hamilton et al., 2017), graph property estimation (Xu et al., 2019; Kipf & Welling, 2017: Li et al., 2020a; Bodnar et al., 2021). and combinatorial problems on graphs (c.g.. TSP (Li et al., 2018: Joshi et al., 2019; Fu et al., 2020; Khalil et al., 2017; Hudson et al., 2022), vehicle routing problem (Nazari et al., 2018; Peng et al., 2020; Yu et al., 2019), graph matching (Yu et al., 2021) and adversarial attack on GNNs (Ma al., 2021; Dai et al., 2018)). However, till now, it remains unclear how to adapt GNNs to graph tasks without rich feature (Zhu et al., 2021) like the resilience optimization task that we focus on. Current topology-based GNNs like TOGL (Horn al., 2022) still rely distinct node features for calculating the filtration, while our proposed FireGNN addresses this by creating a temporal-relatee filtration and learning aggregate them (Sec. 4.2).
Graph rewiring Graph rewiring is typically used in the GNN community build novel classes of GNNs by preprocessing a given graph to overcome the problems of the over-squashing issue of training GNNs. For example, Kliepera et al. (2019) developed graph diffusion convolution (GDC) to improve GNN's performance on downstream tasks by replacing message passing with graph diffusion convolution Topping et al. (2022) proposed an edge-based combinatorial curvature to help alleviate the over-squashing phenomenon in GNNs. To our knowledge, there is currently no inductive learning-based graph rewiring method, and graph rewiring methods rely on rich features to train GNNs better on downstream tasks. The edge rewiring operation used in our paper is special graph rewiring operator that preserves node degree.
Extended related work. The related work on network resilience, network utility, graph structure learning, multi-views graph augmentation for GNNs and deep graph generation is deferred to Appendix A.
3 PROBLEM DEFINITION
An undirected graph is defined as G EV, where = (1,2..... .N) is the set of N nodes, E is the set of M edges, A E (0, 1) NxN the adjacency matrix. and N is the d-dimensional node feature m The degree of a node is defined as d; = Σi= Aij. and a node with degree 0 is called an isolated node. Let Gg denote the set of graphs with the same node degrees as G.
Given the network resilience metric R(G) (Schneider et al., 2011 I) and the utility metric ((()) (Latora & Marchiori, 2003; Boccaletti et al., 2006), the objective of boosting the resilience G is to find a target graph G* Go. which maximizes the network resilience while balancing the network utility. Formally, the problem of maximizing the resilience of complex networks is formulated as
G arg max a RR(G') + +1 a.) -((G).
G' EGG
To satisfy the constraint of preserving degree, edge rewiring is the default atomic operation for obtaining new graphs G' from G. Combinatorially, total of T successive steps of edge rewiring has the complexity of 2 The definitions of resilience and utility metrics are deferred to Sec. 5.1.
4 PROPOSED APPROACH: RESINET
In this section, we formulate the task of boosting network resilience as reinforcement learning task by learning to select two edges and rewire them successively. We first present the graph resilience- aware environment design and describe our innovation FireGNN in detail. Finally, present the graph policy network that guides the edge selection and rewiring process.
For graph with pure topology structure, node feature matrix not available.
3

---

Under review as a conference paper at ICLR 2023
ReaNet
FiReGNN
State
Node embedding
First edge emboddiig
Fig argmax fis .4)
PicGNN
ResiNet
Env step: Rewire AC and BD to AB and CD)
State Gist and reward R
Ego argunx f2(SL,o)
Second edge embedding
Figure 2: Overview of the architecture of ResiNet to select edges for edge rewiring.
(a) Example graph
(b) First edge selection
(c) Second edge selec-
(d) Graph after the edge
tion
rewiring
Figure 3: The edge rewiring operation with the removal of AC, BD and the addition of AB, CD.
4.1 BOOSTING NETWORK RESILIENCE VIA EDGE REWIRING AS MARKOV DECISION PROCESS
We formulate the network resilience optimization problem via successive edge rewiring operations into the Markov decision process (MDP) framework. The Markov property denotes that the graph obtained at time step t + relics only on the graph at time step t and the rewiring operation, reducing the complexity from original O O(E2T) O Then further reduce the complexity to O(TE) by designing an autoregressive edge selection module shown as follows.
As shown in Figure 2. the environment performs the resilience optimization in regressvee step-wise way through a sequence of edge rewiring actions. Given an input graph, the agent first decides whether to terminate not. If not, selects edge from the graph remove, receives the very edge just selected as the auto-regression signal, and then selects another edge to remove. Four nodes of these two removed edges are re-combined, forming two new edges be added the graph. The optimization process repeats until the agent decides to terminate. The detailed design of the state, the action, the transition dynamics, and the reward are presented follows.
State. The fully observable state is formulated as S, G., where G2 is the current input graph at step t. The detailed node feature initialization strategy is given in Appendix C.3.
ResiNet equipped with node permutation permutation-invariant,, Given graph G,, the action is to select two edges and the rewiring order. As is shown in Figure 3, the agent first chooses an edge 61 = AC and direction 61, and the direction the agents chooses an edge eq BD such that AB, CD, AD, BC & E and direction B + D. The heads the two edges reconnect as a new edge AB, and so does the tail CD. Although G, is undirected, avoids the redundancy in representing action space since + C. B + D and C A. D + B refer to the same rewiring operation. Therefore. original action space by half and still leads to a complete action space. In this way. the action space is the set of all feasible pairs of (e1, e2) F.2 with variable size no larger than 2 2 F. 1).
Action.
action space.
C. Then conditioning on the state,
propose to consider the artificial edge directions, which effectively
proposed action space reduces the size of the
4

---

Under review as a conference paper at ICLR 2023
Transition dynamics. The formulation of the action space implies that if the agent does not terminate at step t, the selected action must form an edge rewiring. This edge rewiring executed by the environment, and the graph transits to the new graph
Note that in some other work, infeasible operations are also included the action space (to make the action space constant through the process) (You al., 2018; Trivedi et al., 2020). This reduces the sample efficiency and causes biased gradient estimations (Huang & Ontañón, 2020). ResiNet takes advantage of the state-dependent variable action space composed of only feasible operations.
Reward. ResiNet aims to optimize resilience while balancing the utility, forming a complicated and possibly unknown objective function. Despite this, by (Wakuta, 1995), an MDP that maximizes a complicated objective is up to MDP that maximizes the linear combination of resilience 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) R(G.)) + (1 (U(G++1 - U(G.))
where R(G) and (() are the resilience and the utility functions, respectively. The cumulative reward Et Re to time T is then the total gain of such linear combination.
4.2 FIREGNN
Motivated by graph filtration in persistent homology (Edelsbrunner & Harer, 2008), we design the filtrated graph enhanced GNN termed FireGNN to model graphs without rich features, or even with only topol- ogy. As shown Figure for given input graph G, FireGNN transforms G from the static version to temporal version consisting of sequence of subgraphs, by repeatedly removing the node with the highest degree". Observing sequence of nested subgraphs of G grants FirGNN the ca- pability to observe how evolves towards being empty. Then FireGNN aligns and aggregates the node, edge, and graph embedding from each subgraph, leading to meaningful representations in node, edge, and graph levels. Formally, the filtration in FireGNN is constructed
((k-1) -(())
Uks
Uk argmax DEGREE(1.) E(Kk)
(V, 0) G(D) C CG C... C(N)
where ((k) denotes the remaining graph after removing N k nodes with highest node degrees, Uy denotes the node with highest degree in current subgraph ((A), DEGREE(.) measures the node degree, ((N) is the original graph, and ( contains no edge. The sequence of the nested subgraphs of G is termed the filtrated graph G.
Node embedding. Regular GNN only operates on the original graph G to obtain the node embedding for each node ey h((e)) ((GN)= G)2, where p(-) denotes a standard GNN model. In FireGNN, by using the top K + subgraphs in graph filtration, the final node embedding f(v,)) of o is obtained by
Figure 4: Filtration pro- cess in FireGNN.
h(w;)) = AGG (H(N-K) (UNN..)).......AA AIN-1) (o;)
where A.GN(.) denotes a node-level aggregation function, (k) (w:) is the node embedding of in the k-th subgraph G(k), and K E [N]. practice, (k)) (v:) is discarded when calculating h(v;) if isolated or not included in ((k)
'Removing the node with highest degree leads an efficient minimal number of resultant subgraphs, comparing the uniformly random removal of nodes.
5

---

Under review as a conference paper at ICLR 2023
Edge embedding. The directed edge embedding h h²)) (e1g) of the edge from node to node j in each subgraph is obtained by combining the embeddings of the two end vertices in ((R) as
1h (eig) = = (AGGN-E (c:), (0)))))))))))))))))))))))))))(
where AGGN-E() denotes 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 consistence between the dimensions of edge embedding and graph embedding.
The final embedding of the directed edge Eij of the filtrated graph G is given by
h(ery) = AGGE (ex)) ,, (LN-11)00 (ey)) h (ea))
where AGG denotes an edge-level aggregation function.
Graph embedding. With the node embedding (e(0) (u;) of each subgraph ( available, the graph embedding (A) (G) of each subgraph G(R) calculated by a readout functions (e.g., mean, sum) on all non-isolated nodes in G(&) as
(k) (G) = READOUT (v:)) Ve, G(R) and d.t) 2 0.
The final graph embedding of the filtrated graph G given by
h(G)= AGG "|),),,,"",""",,,,,,,,,
where AGGa(.) denotes graph-level aggregation function.
4.3 EDGE REWIRING POLICY NETWORK
Having presented the details of the graph resilience environment and FireGNN, in this section, describe the policy network architecture of ResiNet in detail, which learns to select two existing edges for rewiring at each step. At time step I, the policy network uses FireGNN as the graph extractor to obtain the directed edge embedding M(e;)) [R][EE xd and the graph embedding h(G) E IR from the filtrated graph G, and outputs an action a representing two selected rewired edges, leading to the new state Ge+1 and the reward R.
To be inductive, we adapt special autoregressive node permutation invariant cianenniio-vvrriabee action space to model the selection of two edges from graphs with arbitrary sizes and permutations. The detailed mechanism of obtaining the action 0, based edge embedding and graph embedding is presented as follows, further reducing the complexity from OTT)") to OTTE).
Auto-regressive latent edge selection. An edge rewiring action a, time step involves the (0) and the selection of two edges (a, and a(²2) and the rewiring order. The action space of (0) is binary, however, the selection of two edges imposes huge action space in O(E which is too expensive to sample from even for a small graph. Instead
prediction of the termination probability di
of selecting two edges simultaneously, we decompose the joint action a, into a, = (a, ag at (2)).
(0) (1)
where aj and at are two existing edges which do not share any common node (recall that az and (2) directed edges for undirected graph). Thus the probability of a, formulated
P(a (st) = P(a: (0) (P.) (s
(0)
(((
(2) [st, Oz ())
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 not as
P(a; (0) (t) = no (h(G)),
where mo(+) is implemented by two layer MLP. Then a (0)
Bermouli( (0) (s))) (0. 1).

---

Under review as a conference paper at ICLR 2023
(0) given by the agent decides continue rewire, edges Selecting edges. If the signal dt
are then selected an auto-regressive way. The signal of continuing to rewire ot is input to the selection of two edges as one-hot encoding vector Le- The second policy network Ti iT(-) takes the graph embedding and l, as input and outputs a latent vector 1 E Rd The pointer network ( (Vinyals al., 2015) is used to measure the proximity between 1 and each edge embedding h(eyy) in G to obtain the first edge selection probability distribution. Then, to select the second edge, the graph embedding (G) and the first selected edge embedding h(((")) and le are concatenated and fed into the third policy network (-). (-)-) obtains the latent vector /2 for selecting the second edge using respective pointer network. The overall process can be formulated as
P(a,") (8c, (0) ((, Vei E E 1/ = M(e 2,))), P(a,
4 = ([K)),
(3) (8,, di ,4 " = (2 M(j))) Vas E E,
(1)
where (+) is two-layer MLP model, [;-]] denotes the concatenation operator, h(e(") is the embedding of the first selected edge at step i, and fi(.) is pointer network.
5 EXPERIMENTS
In this section, we demonstrate the advantages of ResiNet over existing non-learning- -basd and learning- based methods in achieving superior network resilience, inductively generalizing unseen graphs, and accommodating multiple resilience and utility metrics. Moreover, we show that FireGNN can learn meaningful representations from graph data without rich features, while current GNNs fail. Our implementation is already open sourced.
5.1 EXPERIMENTAL SETTINGS
Synthetic datasets, real EU power network (Zhou & Bialek, 2005) and Internet peer-to- peer networks (Leskovec et al., 2007; Ripeanu et al., 2002) are used to demonstrate the performance of ResiNet transductive and inductive settings. The details of data generation and the statistics of the datasets are presented in Appendix C.I. Following the conventional experimental settings in network science, the maximal node size is set to be around 1000 (Schneider et al., 2011) 1), taking into account: the high complexity of selecting two edges each step is O )FF2); 2) evaluating the resilience metric is time-consuming for large graphs.
Datasets.
Baselines. We compare ResiNet with existing graph resilience optimization algorithms, including learning-free and Sarming-based algorithms. Learning free methods (upper half of Table 1) include the hill climbing (HC) (Schneider et al., 20, the greedy algorithm (Chan Akoglu, 2016), the simulated annealing (SA) (Buesser et al., 201 10, and the evolutionary algorithm (EA) (Zhou & Liu, 2014). Since to our knowledge there is no previous learning-band based baseline, we specifically devise five counterparts based on our method by replacing FireGNN with existing well-known powerful GNNs (DE-GNN (Li et al., 2020b), k-GNN (Morris et al., 2019), DIGL (Klicpera et al., 2019), ADGN (Sun & Wu, 2020) and SDRF (Topping et al., 2022)) (lower half of Table 1). The classical GIN model is used as the backbone (Xu et al., 2019). The ResiNet's training setup detailed in Appendix C.2.
Metrics. Following the conventional setting in network science, resilience metrics used in our experiments include graph connectivity-based (Schneider et al., 2011) and spectrum-based measure- ments (adjacency matrix spectrum and Laplacian matrix spectrum). Utility metrics consist of global efficiency and local efficiency (Latora & Marchiori, 2003; Boccaletti al., 2006). The detailed definitions are deferred to Appendix B.
5.2 COMPARISONS TO THE BASELINES
In this section, we compare ResiNet to baselines in optimizing the combination of resilience and utility with weight coefficient {0, 0.5). Following conventional setting. the graph connectivity- based metric used as resilience metric (Schneider et al., 2011) 1) and the global efficiency is used as utility metric (Latora & Marchiori, 2003; Boccaletti et al., 2006).
7

---

Under review as a conference paper at ICLR 2023
Table I: Resilience optimization algorithm under the fixed maximal rewiring number budget of 20. Entries are in the format of (Y),, where 1) X: weighted sum of the graph connectivity based resilience and the network efficiency improvement (in percentage); 2) Y: required rewiring number.
Method
BA-15
BA-50
BA-100
BA-500
BA-1000
EU
P2P-Gnutellu05
PJP-Gnuella09
0
26.8 (10)
30.0
24.1 (20)
(20)
66.6 (20)
19.8 (20)
6.2 (20)
8.4 (20)
HC
0.5
18.6 (11.3)
22.1 (20)
14.9 (20)
5.9 (20)
16.4 (20)
16.3 (20)
5.2 (20)
(20)
21.6 (17.3)
(20
(20)
3.8 (20)
42,9 (20)
14.9 (20)
3.9 (20)
3.7 (20)
SA
0.5
16.8 (19.0)
(244
(2.)
4.0 (20)
15.4 (20)
14.0 (20)
6.3 (20)
4.8 (20)
23.5
(13)
64.3 (20)
X
0.5 (3)
Greedy
0.5
(15)
(13)
42,7 (20)
X
X
0.3 (3)
X
X
8.5 (20)
(20)
4.0 (20)
8.5 (20)
174.1 (20)
8.2 (20)
2.7 (20)
(20)
EA
0.5
6.4 (20)
4.7 (20)
288 (20)
5.6 (20)
18.7 (20)
9.3 (20)
3.7 (20)
0.1 (20)
DE-GNN.
13.7 (2)
U(I)
(
(20)
41.7 (20)
9:0120)
(20)
RL
0.5
10.9 (2)
(
((I)
2.7 (20)
20.1 (14)
2.1 (20)
0(1)
(20)
R-GNN-
13.7
D(I)
O())
(
8.8 (20)
4.5 (20)
-022 (20)
(1)
RL
0.5
(2)
O(I)
O(I)
O (20)
24499 (20)
4.8 (20)
-0.1 (20)
0 (1)
DIGL-RL
(2)
D(I)
0(1))
X
X
5.9 (20)
0.5
(2)
O(1)
O(1)
X
X
7.2 (20)
AGDN-
(4)
D
0(1)
X
X
0 (20)
RL
(2)
0(1)
X
0.9 (20)
SDRE.
(2)
(1))
(
X
X
4.7 (20)
x
RL
0.5
(2)
(
(20)
X
5.3 (20)
55
ResiNet
35.3
61.5 (20)
70.0 (20)
(0.2
172.8 (20)
54.2 (20)
14.0 (20)
18.6 (20)
(ours)
0.5
26.9 (20)
53,9 (20)
53.1 (20)
15.7 (20)
43.7 (20)
51.8 (20)
12.4 (20)
15,1 (20)
Table I records the metric gain and the required number of rewiring operations of different methods under the same rewiring budget. ResiNet outperforms all baselines consistently on all datasets. Note that this performance may be achieved by ResiNet under much fewer numher of rewiring operations, such as on BA-15 with a = O. In contrast, despite approximately searching for all possible new edges, the greedy algorithm is trapped in local optimum (as maximizes the one-step resilience gain) and is too expensive to optimize the resilience of network with more than 300 nodes. For SA, the initial temperature and the temperature decay rate need be carefully tuned for each network. EA performs suboptimally with a limited rewiring budget due to the numerous rewiring operations required in the internal process (e.g., the crossover operator). Learning-ban
methods using existing GNNs coupled with distance encoding cannot learn effectively compared to our proposed ResiNet, supporting our claim about the effectiveness of FireGNN on graphs without rich features.
5.3 ABLATION STUDY OF RESINET
In this section, we investigate the impact of coefficient a of the objective on ResiNet and the effect of the filtration order K on FireGNN.
To investigate the impact of the a in the reward function on ResiNet, we run grid search by varying a from 0 to and summarize the resilience gain, utility gain, and the sum them in Table 2. Table shows that when only optimize the resilience with O, the utility will degrade. Similarly, the resilience would also decrease if we only optimize the utility with a = 1. This suggests a general tradeoff between resilience and utility and is consistent with their definitions. However, despite this tradeoff, we can achieve resilience gain and utility gain simultaneously on BA-15 and BA-50 since the original graph usually does not have the maximum resilience or utility. This incentivizes almost every network conducts such optimization to some extent when feasible.
In FireGNN, the filtration order K of FireGNN determines the total number of subgraphs involved in calculating the final node embedding, edge embedding, and graph embedding. FireGNN degenerates to existing GNNs when the filtration order K is O. Table 1 validates the effectiveness and necessity of FireGNN. Without FireGNN (other GNNs as the backbone), it is generally challenging for ResiNet to find a positive gain on graphs without rich features since ResiNet cannot learn to select the correct edges with the incorrect edge embeddings. The maximum K of each dataset is recorded in Appendix Table 7, which shows that the maximum K equals the around half size of the graph since we gradually remove the node with the largest degree, leading to fast graph filtration process. For our experiments, we use the maximum of K for graphs of sizes less than 50 and set K =3 (1) for graphs of sizes larger than 50 (200). To validate that ResiNet is not sensitive K, we run grid search several datasets to optimize the resilience by setting K = 0, 1,2, 3. As shown in Appendix Table 5, the resilience is improved significantly with K > 0 and ResiNet performs well with K or K 2.
8

---

Under review as a conference paper at ICLR 2023
(a) Induction resilience
(b) Induction on utility
(c) Induction on both metrics
Figure The inductive ability of ResiNet on test dataset (BA-10-30) when optimizing (a) network resilience, (b) network utility, and (c) their combination.
Table 2: The effect of the coefficient a on ResiNet. The result is shown as percentages.
Dataset
Gain
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
I
Resilience
35.3
35.3
35.3
33.3
17.6
17.6
27.5
17.6
17.6
17.6
-2.0
BA-15
Utility
-5.9
-3.9
-3.8
-2.7
1.1
0
1.1
1.1
1.1
5.4
Reward
35.3
34.2
32.9
29.7
11.4
9.2
6.0
5.4
Resilience
56.7
51.1
42.3
48.6
53.9
51.4
50.6
48.1
39.3
-9.1
BA-50
Utility
-3.6
-2.1
-4.0
-4.2
-2.1
0.5
5,5
Reward
56.7
49.5
39.9
43.1
44.9
22.0
5.5
Resilience
75.4
74.6
74.8
76.
72.8
72.8
75.1
75.4
74.9
71.6
-11.8
BA-100
Utility
-4.0
-4.6
-3.9
-5.1
-4.2
-4.2
-3.8
-3.7
-3.5
-2.5
4.8
Reward
75.4
71.9
69.0
66.4
59.4
54.3
49.7
41.8
31.1
16.7
4.8
6 GENERALIZATION
To demonstrate the induction of ResiNet, first train ResiNet two different datasets (BA- 10-30 and BA-20-200) with the data setting listed Appendix Table 3, and then evaluate its performance on individual test dataset. The test dataset is observed during the training process and fine-tuning is not allowed. We report the averaged resilience gain for the graphs of the same size for each dataset. The performance of ResiNet BA-10-30 is shown in Figure and the results of other datasets are deferred to Figure 9 in Appendix D. Figure 5 shows nearly linear improvement of resilience with the increase of graph size, which is also consistent with the results in the transductive setting that larger graphs usually have larger room to improve their resilience, Moreover, we conduct experiments to demonstrate ResiNet's generalization on optimizing different utility and resilience metrics, and details are deferred to Appendix D.
7 CONCLUSION
We have proposed a learning-basee inductive method, ResiNet, for the discovery of resilient network topologies with minimal changes to the graph structure. ResiNet is the first inductive method that formulates the task of boosting network resilience as MDP of successive edge rewiring operations. Our technical innovation, FireGNN, is motivated by persistent homology as the graph feature extractor for handling graphs with only topologies available. FireGNN alleviates the insufficiency of current GNNs (including GNNs more powerful than 1-WL test) on modeling graphs without rich features. By decomposing graphs into temporal subgraphs and learning to combine the individual representations from each subgraph, FireGNN can learn meaningful representations sufficient gradients for training an RL agent to select correct edges while current GNNs fail due to the infinite action backtracking. Our method is practically feasible as it balances the utility of the networks when boosting resilience. FireGNN is potentially general enough to be applied to solve various graph problems without rich features.
the resilience task to provide

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mehmet E Aktas, Esra Akbas, and Ahmed EI Fatmaoui. Persistence homology of networks: methods and applications. Applied Nenwork Science, 4(1):1-28, 2019.
Réka Albert and Albert-Lászlo Barabási. Statistical mechanies of complex networks. Reviews of Modern Physics, 74(1):47, 2002.
Réka Albert, István Albert, and Gary L Nakarado. Structural vulnerability the north american power grid. Physical review E, 69(2):251033, 2004,
Marcin Andrychowicz, Anton Raichuk, Piotr Stañezyk, Manu Orsini, Sertan Girgin, Raphaël Marinier, Leonard Hussenot, Matthieu Geist, Olivier Pietquin, Marcin 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.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference Learning Representations, 2016.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based
generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 34, 2021.
Stefano Boccaletti, Vito Latora, Yamir Moreno, Martin Chavez, and D-U Hwang. Complex networks: Structure and dynamies. Physics Reports, 424(4-5):155-308, 2006.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and Ichman go cellular: CW networks. In Advances in Neural Information Processing Systems, 2021.
Mattco Boffa, Zied Ben-Houidi, Jonatan Krolikowski, and Dario Rossi. Neural combinatorial optimization beyond the TSP: existing architectures under-represent graph structure. In Proceedings the AAAI Conference on Artificial Intelligence, 2022.
Béla Bollobás and Oliver Riordan. Robustness and vulnerability of scale-free random graphs Internet Mathematics, 1(1):1-3 15111-3,222 2004.
Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What's wrong with deep learning in tree scarch for combinatorial optimization. In International Conference Learning Representations, 2022.
Pierre Buesser, Fabio Daolio, and Marco Tomassini. Optimizing the robustness of scale-free networks with simulated annealing. International Conference on Adaptive and Natural Computing Algorithms, pp- 167-176. Springer, 2011.
Tianle Cai, Shengjie Luo, Keyulu Xu, He, Tie- Yan Liu, and Liwei Wang. GraphNorm: A principled approach to accelerating graph neural network training. In Proceedings of the International Conference on Machine Learning, 1021.
Vincenza Carchiolo, Marco Grassia, Alessandro Longheu, Michele Malgeri, and Giuseppe Mangioni. Network robustness improvement via long-range links. Computational Social Networks, 6(1):1-16, 2019.
Hau Chan and Leman Akoglu. Optimizing network robustness hy edge rewiring: a general framework. Data Mining and Knowledge Discovery, 3055):1355-142: 2016.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International Conference on Machine Learning, 2018
Herbert Edelsbrunner and John Harer. Persistent homology-A survey, Contemporury Mathematics, 2008.
1iauhemmtiis,45::55-222552 453:257-282,
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.
Zua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large TSP instances. In Proceedings the AAAI Conference on Artificial Intelligence, 2020.
Marco Grassia, Manlio De Domenico, and Giuseppe Mangioni. Machine learning dismantling and carly- signals of disintegration in complex systems. Nature Communications, 12( 1200), 2021.
10

---

Under review as a conference paper at ICLR 2023
Xiaojie Guo, Lingfei Wu, and Liang Zhao, Deep graph translation. CoRR, abs/1805.09980 2018. URL http://arxiv. wws/180s...0 09980.
Andrew G Haldane Robert May. Systemic risk in banking ecosystems. Nature, 469(7330)3351-555 2011.
Will Hamilton, Zhitao Ying, and Jure Leskovee, Inductive representation lcarning on large graphs. In Advances in Neural Information Processing Systems, 2017.
Kaveh Hassani and Amir Hosein Khasahmadi, Contrastive multi-view representation learning on graphs. In Proceedings of the International Conference on Machine Learning, 2020.
Christoph Hofer, Florian Graf, Bastian Rieck, Mare Niethammer, and Roland Kwitt. Graph filtration learning. In International Conference on Machine Leurning, 2020.
Petter Holme, Beom Jun Kim, Chang No Yoon, and Seung Kee Han. Attack vulnerability of complex networks. Physical Review 65(5):056109 2002.
Max Horn, Edward De Brouwer, Michael Moor, Yves Morcau, Bastian Rieck, and Karsten Borgwardt. Topolog- ical graph neural networks. 2022.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zätnik, Percy Liang, Vijay S. Pande, and Jure Leskovee.
Strategies for pre-training graph neural networks. In International Conference on Learning Representations, 2020.
Shengyi Huang and Santiago Ontañón. A closer look at invalid action masking in policy gradient algorithms. CoRR, abs/2006. 141771, 2020. URL httpthttt:///att http://wwiw....aaaa.aaaaaaaa wrgg/bs//200eeccoo 14171.
Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for traveling salesperson problem. International Conference on Learning Representations, 2022.
Swami Iyer, Timothy Killingback, Bala Sundaram, and Zhen Wang. Attack robustness and centrality of complex networks. PloS One, 8(4):c59613, 2013.
Daniel A Jaume, Adrián Pastine, and Victor Nicolas Schvöllner. 2-switch: transition and stability on graphs and forests. arXiv preprint arXiv:2004.1 164, 2020.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020.
Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. CoRR, abs/1906.01227, 2019. URL http://arxiv. org abs/ 1906. 01227.
Chaitanya K Joshi, Quentin Cappart, Louis-Martin
Martin Rousscau, and Thomas Laurent. Leamning the travelling salesperson problem requires rethinking generalization. Constraints, pp. 1-29, 2022.
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, 2017.
P. Diederik Kingma and Lei Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Günter Klambauer, Thomas Unterthiner, Andreas Mayr. and Sepp Hochreiter. Self-normalizing neural networks. In Advances in Neural Information Processing Systems, 2017.
Johannes Klicpera, Stefan Weillenberger, and Stephan Günnemann. Diffusion improves graph learning. In Advances in Neural Information Processing Systems, 2019.
Wouter Kool, Herke Van Hoof, and Max Welling, Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018
Vito Latora and Massimo Marchiori. Efficient hehavior of small-world networks. Physical Review Letters, 87 (197:198701, 2001.
11

---

Under review as a conference paper at ICLR 2023
Vito Latora and Massino Marchiori. Economic small-world behavior in weighted networks. The European Physical Journal B- B-Condensed Matter and Complex Systems, 32(2):249 263, 2003.
Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD International conference on Knowledge Discovery and Data Mining, 2006.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters.
ACM transactions Knowledge Discovery from Data (TKDD), 1(1):2-es, es, 2007.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. DeeperGCN: All you need to train deeper GCNs. arXiv preprint arXtv:2006.077: 07739, 2020a.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In Advances in Neural Information Processing Systems, 2020b.
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 convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, 2018.
Yao Ma. Suhang Wang, Tyler Derr, Lingfei Wu, and Jiliang Tang. Graph adversarial attack via rewiring. In KDD, pp. 1161-1169, ACM, 2021.
Sourav Medya, Tianyi Ma, Arlei Silva, and Ambuj Singh. game theoretic approach for k-core minimization. In Proceedings of the International Conference on Autonomous Agents and MultiAgent Systems, 2020.
Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
Damon Mosk-Aoyama, Maximum algebraic connectivity augmentation is NP-hard. Operations Research Letters, 36(6):677-679 2008.
Adilson E Motter, Natali Gulbahce, Eivind Almaas, and Lászóó Barabási. Predicting synthetic rescues metabolic networks. Molecular systems biology, 4(1):168, 2008.
MohammadReza Nazari, Afshin Oroojlooy, Lawrenee V. Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Syxtems, 2018.
Bo Peng. Jiahai Wang. and Zizhen Zhang. A deep reinforcement learning algorithm using dynamic attention model vehicle routing problems. CoRR, abs/2002.003822, 2020. URL pestts://arxee org/ / 2002.00 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 KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2020.
Matei Ripeanu, Ian Foster, and Adriana Jamnitchi. Mapping the gnutella network: Properties of large-scale peer-to-peer systems and implications for system design. arXiv preprint cx/0209028, 2002.
Lei Rong and Jing Liu. A heuristic algorithm for enhancing the robustness of scale-free free networks based on edge classification. Physica A: Statistical Mechanics and its Applications, 503:503-511 2018.
Christian M Schneider, André Moreira, José S Andrade, Shlomo Havlin, and Hans Herraann Mitigation of malicious attacks on networks. Proceedings of the National Academy of Sciences, 108(10):3838336)) -84118 2011.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, 0bs//707.003377 2017. URL http: / arxiv org/ abbp://77.003444
Ricard V Sole and Ma Montoya. Complexity and fragility in ccological networks. Proceedings of the Royal Society of London. Seriey B: Biological Sciences, 268(1480):2039-044 2001.
Chuxiong Sun and Guoshi Wu. Adaptive graph diffusion networks with hop-wise attention. arXiv preprint 1rXiv:2012.1502.. 2020.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
12

---

Under review as a conference paper at ICLR 2023
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. Advances in Neural Information Processing Systems, 2017.
Petar Velickovie, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. International Conference on Learning Representations. 2019.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, 2015.
Kazuyoshi Wakuta. Vector-valued markov decision processes and the systems of linear inequalities. Stochastic Processes and Their Applications. 56(1):159-669, 1995.
Xiangrong Wang, Evangelos Pournaras, Robert E Kooij, and Piet Van Mieghem. Improving robustness 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, 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:/ /tpp:://////eewwwew/e net/ forum? Serrmiid-ryCssikee
A Yasin Yazıcroglu, Magnus Egerstedt, and Jeff's S Shamma. Formation of robust multi-agent networks through self-organizing random regular graphs. IEEE Transactions on Network Science and Engineering, 2(4): 139-151. 2015.
Deheng Ye, Zhao Liu, Mingfei Sun, Bei Shi, Peilin Zhao, Hao Wu, Hongsheng Yu, Shaojic Yang. Xipeng Wu, Qingwei Guo, et al. Mastering complex control in moba games with deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
Jiaxuan You. Bowen Liu, Zhitao Ying. Vijay S. Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. Advances in Neural Information Processing Systems, 2018.
Yuning You. Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang. and Yang Shen. Graph contrastive learning with augmentations. Advances Neural Information Processing Systems. 2020.
James Jian Qiao Yu, Wen Yu, and Jiatao Gu. Online vehicle routing with neural combinatorial optimization and deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 20(10))3806 3817, 2019. doi: 10. 11110/0TTT2009999999 2909109.
URL https: //tl: org/10. wwt.:/111111....
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Deep latent graph matching. In International Conference on Machine Learning, 2021.
Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. Finding critical users for social network engagement: The collapsed k-core problem. In Proceedings of the AAAI Conference on Artificial Intelligence, 2017.
Kangfei Zhao, Zhiwei Zhang, Yu Rong, Jeffrey Xu Yu, and Junzhou Huang. Finding critical users in social communities via graph convolutions. IEEE Transactions Knowledge and Data Engineering, pp. 1-1, 1021. doi: 10. 10.11099TKDE22221..0058
Mingxing Zhou and Jing Liu. A memetic algorithm for enhancing the robustness of scale-free networks against malicious attacks. Physica Staristical Mechanics and its Applications, 410:131-143, 2014.
Qiong Zhou and Janusz W Bialek. Approximate model of european interconnected system as benchmark system study effects of cross-border trades. IEFE Transactions on Power Systems, 20(2):782-788 2005.
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Yuanqi Du, Jicyu Zhang, Qiang Liu, Carl Yang, and Shu Wu. A survey on graph structure learning: Progress and opportunitics. IJCAI, 2021.
13

---

Under review as a conference paper at ICLR 2023
APPENDIX
A EXTENDED RELATED WORK
Network resilience. Modern network systems are threatened by various malicious attacks, such as the destruction of critical nodes, critical connections and critical subset of the network via heuristies/leaming-asss -bsse attack (Fan al., 2020: Zhao et al., 2021; Zhang et al., 2017; Holme et al., 2002; Iyer et al., 2013; Grassia et al., 2021; Fan et al., 2020; Medya et al., 2020). Network resilience was proposed and proved as a suitable measurement for describing the robustness and stability of a network system under such attacks (Schneider et al., 201 I). Around optimizing network resilience, various defense strategies have been proposed to protect the network functionality from crashing and preserve network's topologies to some extent. Commonly used manipulations of defense 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, 2016; Buesser et al., 2011). Among these manipulations, edge rewiring fits well to real-world applications as it induces fewer functionality changes the original network and does not impose additional loads to the vertices (degree-preservingg preserving) (Schneider et al., 2011; Rong & Liu, 2018; Yazıcioğlu et al., 2015). By now, there has been no learning-basc -baedd inductive edge rewiring strategy for the resilience task.
Network utility. Network utility refers to the system's quality to provide a specific service, for example, transmitting electricity in power networks and transmitting packages in routing networks. A popular metrie for network utility is the network efficiency (Latora & Marchiori. 2003; Boccaletti et al., 2006). In many previous work, despite that network resilience could be improved, the utility may dramatically drop at the same time (Li et al., 2019; Carchiolo et al., 2019; Wang et al., 2014; Schneider et al., 201 I; Chan & Akoglu, 2016; Buesser et al., 201 1). This contradicts the idea behind improving network resilience and will be infeasible in world applications. Our goal is to enhance network resilience with moderate loss of network utility via edge rewiring.
Graph structure learning. Unlike the graph generation task which focuses on the quality of the generated graph, graph structure learning (GSL.) aims to jointly learn an optimized graph structure and corresponding graph representations only for better performance on downstream tasks. Although conceptually related, GSL differs from graph generation since GSL mostly cares for the downstream task while graph generation focuses on the generated graphs (Jin et al., 2020; Zhu et al., 2021), Currently, GSL relies on the existence of rich features to construct graph, while there are generally no rich features in graph generation. Moreover, GSL cannot control the graph's 's node degree during graph optimization. We refer the interested readers to survey of GSL (Zhu al., 2021) since our work is a constrained graph generation task unrelated to GSL.
Multi-views graph augmentation for GNNs. way to improve the expressive power of GNNs or combine domain knowledge, which is adapted based on the task's prior (Hu et al., 2020). For example, GCC generates multiple subgraphs from the same ego network (Qiu et al., 2020). DGI maximizes the mutual information between global and local information (Velickovic et al., 2019). GCA adaptively incorporates various priors for topological and semantic aspects of the graph (You et al., 2020). (Hassani & Khasahmadi, 2020) contrasts representations from first-order neighbors and a graph diffusion. DeGNN Jin et al. (2020) was proposed as automatic graph decomposition algorithm improve the performance of deeper GNNs. These techniques rely on the existence of rich graph feature and the resultant GNNs cannot work well on graphs without rich features. In the resilience task, only the graph topological structure is available. Motivated by the calculation process of persistent homology (Edelsbrunner & Harer, 2008), we apply the filtration process to enhance the expressive power of GNNs for handling graphs without rich features.
Multi-views graph augmentation is one efficient
Deep graph generation. Deep graph generation models learn the distribution of given graphs and generate more novel graphs. Some work use the encoder-decoder framework by learning latent representation of the input graph through the encoder and then generating the target graph through the decoder. For example, GCPN (You et al., 2018) incorporates chemistry domain rules molecular graph generation. GT-GAN (Guo et al., 2018) proposes a GAN-base model on malware cy network synthesis. GraphOpt (Trivedi al., 2020) learns an implicit model to discover underlying
14

---

Under review as a conference paper at ICLR 2023
Oigeal Roi Not
Nomal and LCC
(a) Original EU network
(b) network after attacks
(c) Remaining LCC size under attack
Figure 6: The EU power network under the adaptive degree-based attack with (a) original EU network with 217 nodes, (b) remaining EU network after a series of attacks on nodes, and (c) normalized size of the largest connected component (LCC).
optimization mechanism of the graph generation using inverse reinforcement learning. Net learns stochastic policy for generating molecules with the probability proportional to given reward based on flow networks and local fow-matching conditions Bengio al. (2021). Boosting network resilience in pregeeeires way can be viewed as a constrained graph generation task. However, constrained version graph generation is still under development and none of existing methods can generate desired graphs with the exact node degree preserving constraint, which is required by the resilience task.
B DEFINITIONS OF DIFFERENT OBJECTIVE FUNCTIONS
In this section, we present resilience definitions and utility definitions used in our experiments.
B.1 RESILIENCE DEFINITIONS
Three kinds of resilience metrics are considered:
The graph connectivity- measurement is defined (Schneider al., 2011)
R(G) = N Σ sq)),
where s(q) is the fraction nodes in the largest connected remaining graph after removing q nodes from graph G according to certain attack strategy. The range of possible values of R is [1/N, 1/2]. where these two extreme values correspond to a star network and a fully connected network, respectively. Figure shows that the failures of dozen of nodes could jeopardize the connectivity and utility of the EU power network.
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.
B.2 UTILITY DEFINITIONS
In this paper, the global and local communication efficiency are used as two measurements of the network utility, which are 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 as inversely proportional to the average over pairwise distances (Latora Marchiori, 2001) as
E(G) N(N 1)
Σ
d(i.j)
iøJEV
15

---

Under review as a conference paper at ICLR 2023
where N denotes the total nodes in network and d(i.j) is the length of the shortest path between node i and another node j.
We calculate the global and local efficiency given the average efficiency.
The global efficiency of network G is defined as (Latora & Marchiori, 2001; 2003)
giobaal (G) B(G)
((Gidaat)
where Gideal is the "ideal" fully-connected graph on N nodes and the range of Eglobat is [0, 1].
The local efficiency of a network G measures a local average of pairwise communication efficiencies and is defined (Latora & Marchiori, 2001)
Etoeat (G)
B(G.),
N
iEV
where G3 is the local subgraph including only of node i's one-hop neighbors, but not the node itself. The range of Etocal (G) is [0, 1].
C IMPLEMENTATION DETAILS OF RESINET
This section provides the implementation details of ResiNet, including dataset, network structure training strategies, and node feature construction.
C.I DATASET
We first present the data generation strategies. Table 3 summarizes the statistics of each dataset. Synthetic datasets are generated using the Barabasi-Alber (BA) model (known as scale-free graphs) (Albert & Barabási, 2002), with the graph size varying from [N|=10 to |N|=1000. During the data generation process, each node is connected to two existing nodes for graphs with no more than 500 nodes, and each node is connected are chosen since they are vulnerable to malicious attacks and are commonly used to test network resilience optimization algorithms (Bollobás Riordan, 2004). We test the performance of ResiNet on both transductive and inductive settings.
existing node for graphs with near 1000 nodes. BA graphs
Transductive setting.
The algorithm is trained and tested on the same network.
Randomly generated synthetic BA networks, denoted by BA-m, are adopted networks of various sizes, where
to test the performance of ResiNet (15, 50, 100, 500, 1000} is the graph size.
The Gnutella peer-to-peer network file sharing network from August 2002 (Leskovec al., 2007; Ripeanu et al., 2002) and the real EU power network (Zhou Bialek, 2005) are used to validate the performance of ResiNet on real networks. The random walk sampling strategy is used to derive a representative sample subgraph with hundreds of nodes from the Gnutella peer-to-peer network (Leskovec & Faloutsos, 2006).
Inductive setting. Two groups of synthetic BA networks denoted by BA-m-n are randomly 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 networks as the training data to train ResiNet and then evaluate ResiNet's performance directly the test dataset without any additional optimization.
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 a 5-layer defined GIN (Xu al., 2019) as the backbone. The hidden dimensions for node embedding and graph embedding in
16

---

Under review as a conference paper at ICLR 2023
Table 3: 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 graphs. The edge rewiring has a fixed execution order. For the inductive setting, report the maximum number of edges. The action space size of the edge rewiring is measured by 2 E
Dataset
Node
Edge
Action Space Size
Train/Tes
Setting
BA-15
15
54
5832
Transductive
BA-50
50
192
73728
Transductive
BA-100
100
392
307328
Transductive
BA-500
500
996
1984032
Transductive
BA-1000
1000
999
1996002
X
Transductive
EU
217
640
819200
Transductive
p2p-Gnutella05
400
814
1325192
X
Transductive
92p-Gnutella09
300
740
1095200
Transductive
BA-10-30 (x)
10-30
112
25088
1000/500
Inductive
BA-20-200 (*)
20-200
792
1254528
4500/360
Inductive
each hidden layer are set to 64 and the SeLU activation function (Klambauer et al., 2017) is used after each message passing propagate. Graph normalization strategy is adopted to stabilize the training of GNN (Cai et al., 2021). The jumping knowledge network (Xu et al., 2018) is used to aggregate node features from different layers of the GNN.
The overall policy is trained by using the highly tuned implementation of proximal policy optimization (PPO) algorithm (Schulman et al., 2017). Several critical strategies for stabilizing and accelerating the training of ResiNet are used, including advantage normalization (Andrychowicz et al., 2021), the dual-clip PPO (the dual clip parameter 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 a linearly decayed learning rate of 0.0007 for the value network. The aggregation function of FireGNN is defined as an attention mechanism-buut based linear weighted combination.
10) (Ye et al., 2020), and the usage of different
Hardware: We run all experiments for ResiNet on the platform with two GEFORCE RTX 3090 GPU and one AMD 3990X CPU.
C.3 NODE FEATURE CONSTRUCTION
The widely-used node degree feature cannot significantly benefit the network resilience optimization of single graph due to the pegree-preserving rewiring. Therefore, we construct node features for each input graph to aid the transductive learning and inductive learning, including
The distance encoding strategy (Li et al., 2020b). Node degree feature is a part it.
The 8-dimensional position embedding originating from the Transformer (Vaswani et al., 2017) as the measurement of the vulnerability of each node under attack. If the attack order is available, we can directly encode it into the position embedding. If the attack order is unknown, node degree, node betweenness, and other node priority metrics can be used for approximating the node importance practice. our experiments, we used the adaptive node degree for the position embedding.
C.4 BASELINE SETUP
All baselines share the same action space with ResiNet and use 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 their paper. The early-stopping strategy used for baselines, which means that the search process terminates if no
17

---

Under review as a conference paper at ICLR 2023
Table 4: Performance gain (in percentage) of ResiNet optimizing varying objectives on the BA-15 network. All objectives are optimized with the same syper-parameters, which means that we did not tune hyper-parameters for objectives except for RD-
Objective
Gain (%)
Objective
Gain(%)
RDD
35.3
RB8
14,6
SRp
15.3
SR
15.3
AC
48.2
AC
43.2
R2 + Egtobui
14.2
Rg + Egtobat
13.1
SRD Eglobal
14.6
15.0
AC + Egtobal
34.0
ACB Eggltaal
31.3
Ry Elocal
24.4
RB + Eiocul
39.4
SRD Elocal
17.3
SRB + Eiocal
21.2
AC Frocal
9.4
ACB Frocal
15.1
improvement is obtained successive 1000 objective function calling trials. All algorithms are repeated for random seeds using default hyper-parameters.
D EXTENDED EXPERIMENTAL RESULTS
In this section, present additional experimental results show that ResiNet generalizes unseen graphs, different utility and resilience metrics.
D.1 LEARNING BALANCE DIFFERENT UTILITY AND RESILIENCE METRICS
Figure 7 shows that ResiNet can accommodate various of to balance the resilience and utility during the optimization process. As shown Figure 8, conduct extensive exper- iments on the BA-15 network to demonstrate that ResiNet can learn to optimize graphs with different resilience and utility metrics and to defend against other types of attacks besides the node degree-bases attack, such as the node betweenness-basee attack.
0.28
0.29
924
Table 4 records the improvements in percentage ResiNet for varying objectives on the BA-15 dataset. As visualized in Figure 8, ResiNet not limited to defend against the node degree-based attack (Figure 8 (b)-()) and also learns to defend against the betweenness- based attack (Figure 8 (k)-(s)). Total three resilience metrics are used, with denoting the graph connectivity-basee resilience metric, SR. being the spectral radius and SR representing the algebraic connectivity. Total two utility metrics are adopted, including the global efficiency Egiobal and the local efficiency Evocat- Not surprisingly, the optimized network with an improvement of about 3.6% for defending the betweenness- based attack also has a higher resilience (around 7.8%) against the node-degree attack. This may be explained as the similarity between node degree and betweenness for small network.
822
Figure 7: Pareto points obtained by
ResiNet of balancing various combi- nations of resilience and utility.
D.2 INDUCTIVITY ON LARGER DATASETS
To demonstrate that ResiNet can leam from networks to accommodate different utility and resilience metries, we conduct experiments based on BA-15 using multiple resilience and utility metrics. The Pareto points shown in Figure 7 denote the optimum under different objectives on BA-15, implying that ResiNet can obtain the approximate Pareto frontier. Surprisingly, the initial gain of resilience (from around 0.21 to around 0.24) is obtained without loss of the utility, which incentivizes almost every network to conduct such optimization to some extent when feasible. More results are included in Appendix D.I and the optimized network structures visualized in Figure 8 and Figure 11.
18

---

Under review as a conference paper at ICLR 2023
(a) Original
(b) Rp
(c) SR
(d) ACD
(e) RD Egiobol
(1) p + Egiobal
(g) AC + Egtobal
(h) Rp + E
(i) SRD + Etocal
ii AC Eiorat
(k) Ra
(I) SRB
(m) AC
(n) Ra Eglobal
(o) SR Eggobel
(p) ACB + Eggobal
(q) Ra + Frocat
(r) SR
(6) ACB + Frocol
Figure 8: The resilience maximization on the BA-15 datasct with 15 nodes and 27 edges with (a) original network, (b)-() results of defending the node begree-based attack with diffferent combinations of resilience and utility, and (k)-(s) results of defending against the node betweenness- based attack with varying combinations of resilience and utility. For three resilience metrics, R denotes the graph connectivity- resilience metric; SR is the spectral radius; SR represents the algebraic connectivity. For two utility metrics, Egtabal denotes the global efficiency, and Evocat is the local efficiency.
Even with limited computational resources, armed with the autoregressive action space and the power of FireGNN, ResiNet can be trained fully end-to-end on graphs with thousands of nodes using RL. We demonstrate the inductivity of ResiNet on graphs of different sizes by training ResiNet on the BA-20-200 dataset, which consists of graphs with the size ranging from to 200, and then report its performance on directly guiding the edges selections on unseen test graphs. The filtration order K is set to I for the computational limitation. As shown in Figure 9, we can see that ResiNet has the best performance for N [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 to 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.1 THE EFFECT OF FILTRATION ORDER K ON FIREGNN
In this section, report the ratio of the remaining edges in subgraphs versus different filtration order K in Table 6 and visualize in Figure 10. The maximum filtration order K of FireGNN of each dataset is summarized in Table 7. Table 7 demonstrates that the maximum filtration order K is nearly
19

---

Under review as a conference paper at ICLR 2023
0.00
25
-62
1:90
Graph N
(a) Inductivity on resilience
(b) Inductivity on resilience and utility
Figure 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.
Table 5: The effect of the filtration order K ResiNet in improving network resilience (percentage).
K
BA-15
BA-50
BA-100
EU
11.8 + 2.7
0 0
0 0
6.1 4.2
17.6
4
74.9 0.8
54.5 + 0,4
17.6
76.3 0.1
57.4 + 1.6
17.6
55.7=2.3
73.1 + 0.9
54.9 + 0.9
Table 6: The ratio of remaining edges in subgraphs versus the filtration order K.
K
BA-15
BA-50
BA-100
BA-500
BA-1000
P2P- G--GGlluell99
0.6667
0.7708
0.8571
0.9538
0.9479
0,9625
0.9779
0.9608
0.4815
0.6667
0.7602
0.9096
0.9139
0,9313
0.957
0.927
0,3333
0.5938
0.6837
0.8665
0.8809
0,9031
0.9361
0,8973
0.2222
0.5208
0.6224
0.8313
0,8559
0.8781
0.9152
0,8703
0,1481
0.4583
0.5663
0.8002
0,8348
0.8562
0,8956
0,8446
0.0370
0.4062
0.5255
0.7741
0.8158
0.8344
0.8771
0.8189
0
0.3646
0.4847
0.754
0.7998
0.8125
0.8587
0.7959
0
0.3229
0.4439
0.7359
0.7848
0.7906
0.8403
0.773
0.2917
0,4031
0.7199
0.7698
0.7719
0.8231
0.75
Table 7: Maximum filtration order of each dataset.
Dataset
BA-15
BA-50
BA-100
BA-500
BA-1000
EU
P2P-Gmutella05
P2P-Gnmellla09
(node)
Maximum of K
7
23
42
226
306
103
216
160
around the half size of the graph since we gradually remove the node with the largest degree filtration process.
D.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. Compared to the original EU network, Figure 11 (b) is the network structure obtained by only optimizing the graph connectivity-basee resilience. We can observe a more crowded region 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 11 (c).
20

---

Under review as a conference paper at ICLR 2023
(a) Original EU network
(b)
(c) Eglobal
Figure II: Visualizations of the original EU network and optimized networks using ResiNet with different objectives: means the connectivity-bast based resilience measurement and Eglobal is the global efficiency.
Table 8: Resilience optimization algorithm under the fixed maximal rewiring number budget of 200. Entries are in the format of X X(Y), where 1) X: weighted sum of the graph connectivity-bant -base resilience and the network efficiency improvement (in percentage); 2) Y: required rewiring number. Results are averaged over 3 runs and best performance bold.
Method
a
BA-15
BA-50
BA-100
BA-500
BA-1000
P2P-Cnutella05
P2P-Gmutellad99
26.8 (10.0)
52.1 (47.0)
76.9 (97.3)
45.8 (200)
302.5 (200)
71.9 (152.7)
37.5 (193.3)
40.2
HC
0.5
(11.3)
43.1 (62.7)
56.9 (121)
30.0 (200)
66.3 (200)
63.2 (200)
27.7 (200)
34.7 (196.3)
(59.0)
(200)
73.5(160.3)
37.2
0.5
17.8 (21)
41.1 (79.7)
57.7 (127.7)
31.4 (200)
64.9 (200)
62.8 (200)
37.1 (200)
35.2 (200)
Greedy
0.5
5.3 (15)
34.7 (13)
42.7 (20)
0.3 (3)
EA
35.3
(K)
(X)
9.9 (200)
(200)
(200)
0.5
27.1
38.3 (K)
46.6 (K)
6.8 (200)
18.7 (200)
58.4 (K)
3.2 (200)
(200)
DEN
13.7(2)
0(1)
0(1)
(,6
41.7
(20
(2()0)
U(I)
10.9
(1)
(20)
20.1
ENNNN.
(2.7(2)
0(1)
0(1)
o(l)
(20)
(20)
(20
0(I)
6.3
(
-24.9 (20)
(20)
(20)
0
ResiNet
(6)
(205
70,0 (20)
10.2 (20)
172.8 (20)
54,2
14,0 (20)
18.6
(20)
(20)
53.1 (20)
(20)
43.7 (20)
(208
12.4 (20)
(20)
D.4 PERFORMANCE COMPARISONS UNDER A LARGE REWIRING BUDGET
In this section, present the resilience improve-
ment and the required number of edge rewiring of each algorithm under a large rewiring budget of 20. The running speed is also presented to compare the running time efficiency of each algorithm.
Ratio of remaining edges subgraph
BA-15
BA-100
BA-500
BA-1000
As shown Table 8, traditional methods improve the network resilience significantly compared ResiNet under large rewiring budget of 200. However, tra- ditional methods are still undesired in such a case since solution with large rewiring budget is not applicable in practice due to the vast cost of adding many new edges into real system. For example, the
P2P05
P2Р03
350
400
Number of
actual number rewiring budget for EA is hard to calculate since it is population-base based algorithm, it is omitted Table 8. All baselines adopt the early- stopping strategy that they will terminate if there is no positive resilience gain in a successive 1000 steps.
Figure 10: Ratio of the remaining edges in subgraphs versus different filtration order
Table 9 indicates that the time it takes for the benchmark algorithm to solve the problem usually increases as the test data set size increases. In contrast, our proposed ResiNet suitable for testing on large dataset once trained.
21

---

Under review as a conference paper at ICLR 2023
Table 9: Running speed (in second) of the resilience optimization algorithm under the fixed maximal rewiring number budget. Entries are in the format of X (Y), where 1) X: speed under the budget of 20; 2) Y: speed under the budget of 200 means that the result is not available at a reasonable time.
Results are averaged over 3 runs and best performance is in bold.
Method
BA-15
BA-50
BA-100
BA-500
BA-1000
EU
P2P-Gnutella05
P2P-Gnutella09
(1.0)
1.1 (6.4)
1.3 (22.2)
21.9 (354.))
80.3 (1288. 3)
3.1 (94.2)
15.3 (358. II
(89.8)
HC
0.5
1.5 (11.5)
1.1 (12.8)
2.9.04
40.9 (589.5)
148.7 (2603.7)
5.3 (193.7)
24.7 (462.8)
(19
SA
0
0.3 (0.5)
0.3 (6.6)
0.6 (226)
45.7 (313.)
(10818)
(912)
10.8 (286.4)
(89
0.7 (1.7)
(13.2)
1.7 (47.5)
33,9 (568.9) 9)
99.8 (2166.3)
(19,)
(454.5)
6.3 (1885)
Groedy
0
0.2 (6.0)
$4.1
766.3 (X)
X
X
3061.7 (K)
X
X
0.7 (0.7)
64.1 (65.4)
1478.9 (X)
6192.6 (K)
0
0.01 (X)
0.1 (X)
(X)
2.5 (X)
10.3 (3)
0.2 (x0
1.6 (X)
0.4 (X)
EA
0.01
(X)
(X)
15.0
(2)
(.0
0.8
DE-GNN-
0.1
(X)
(x1
14.9
70.3
3x6
(X)
0.5
RL
0.5
0.1 (X)
0.1 (X)
0.2 (X9
13.7 (X)
60,9 (K)
4.5 (20
(X)
6.7
E-GNN-
0.02 (X)
0.03 (K)
0.07 (X)
(X3
$6.5 (X)
2x6
(x2
0.5 (X)
(K)
0.08
17.3 (0)
76.1
ResiNet
0
0.5 (X)
(K)
22200)
66.8 (X)
4.5
14.7 (X)
(x3(X)
0.5
(X)
244
18.0
5.2
10.3 (1)
Table 10: Characteristics of different graph related tasks.
Appenech
Task
Actinn
RL. compunal
Rivard
Frobica Cumpleaity
Ettraptatc
Esceuke
Traning & Interess
Acton Mankin
MVC
mode lovd
(A33 eade splnec
52N
500
SOV Khall es dl (201))
Maa-Cal
ande lord
cak aoulo selsec
clange iu weigl
SIV
300
Lood Hadoo
regiet
GNS
RNS RL. (Bollod al. 2016)
TSP
mode level
<dl eodo 5o loer
change coll
RNN
100
UNNNAL Doott st.l, 2022;
1330
leve
cad zode o0 icer
change sest coet
GRS
50
T3P
mode leve
sdd mods loar
chongs
0.01
Alteniicn
Locd seacch (Bother st.. 20130
MBS
lend
uald mndi
chasss use
GNN
Brollww
groph Iiwi
rdg Waiting
(lorgy moll fere and vtilly 05.07)
ForrrW
7000
E DEEP ANALYSIS OF WHY REGULAR GNNS FAIL IN THE RESILIENCE TASK
is well-known that GNNs generally work well for graphs with rich features. Unluckily, the graph network in the resilience task has no node/edge/graph) feature, with only the topological structure available. No rich feature means that the output of the GNNs is not distinguishable, and then is difficult for the RL agent to distinguish different vertices/edges, causing large randomness in the output of the policy. This may cause the rewiring process to alternate between two graphs, forming an infinite loop. And we suspect that this infinite loop failure may explain the poor empirical performance of optimizing network resilience by selecting edges using existing GNNs and reinforcement learning (RL). The infinite loop failure is presented as follows.
Consider the graph G, with N nodes and containing two edges AB and CD. The agent selects AB and CD for rewiring, leading to G++1 with news edges AC and BD. A frequent empirical failure of regular GNNs for the robustness task is the infimite action backtracking phenomenon. The agent would select AC and BD step & + 1, returning back G. and forming cycled loop between G. and G.+1. Formally, the infinite loop is formulated as
((A, B), D)) = arginax SIM ((ChE, (2), (hT (.))), hc.)
((A, C), (B, arginax SIM ((th44)) (1444)111444: (he M(41)) ho..))
K.I.
where SIM is similarity metric, bf and ha, are embeddings of node i and graph G2 at step 4, and (A,B) is one edge.
Table 10 compares and summarizes different graph related tasks' characteristics. We can see that the resilience task is more challenging from many aspects. No prior rule like action masking or negative penalty can be used to avoid selecting visited nodes as in TSP. For the resilience task, all previously visited edges are also possibly valid to be selected again, resulting in insufficient training signals.
The desired GNN model should not depend on rules like action masking to distinguish edge and graph representations for graphs with little node features. Our proposed FireGNN fulfills these requirements to obtain proper training signals. FireGNN has distinct expressive power and learns create more
22

---

Under review as a conference paper at ICLR 2023
meaningful and distinguishable features for each edge. FireGNN is not simple aggregation of higher-order information a static graph. It was inspired by homology filtration and the multi-view graph augmentation. Persistence homology motivates by observing how the graph evolves towards being empty, leading to more distinct and meaningful features for each node/edge, thus avoiding the infinite loop. Extensive experimental results in Table validate the necessity and effectiveness of FireGNN. Existing GNNs perform worse while FireGNN performs well.
to aggregate more distinct node features
23


Reviews:
[{"review_id": "ksAskKF1pqf", "reviewer": "Reviewer_sxfB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "", "summary_of_the_paper": "Current GNN models rely on strong features for good performance. However, they struggle in the absence of features and when only the topology is present. This is true particularly in the case of making network resilient to all forms of attack. The paper proposes to make network resilient even in the absence of availability of features. In addition, contrast to earlier approaches, this paper proposes a learning-based method. The key idea is to create a series of subgraph by removing the node with the highest degree and the learn to aggregate node embeddings from such subgraphs.", "summary_of_the_review": "The paper proposes an approach to make network resilient even when the features are unavailable. The method seems to bear some resemblance to [A] but the goals were quite different. Regardless, the ideas are quite novel. The gains shown in the experiment section are pretty impressive. I am incline to accept the paper.\n***\n# References:\n[A] GraphOpt: learning optimization models of graph formation, Rakshit Trivedi, Jiachen Yang, Hongyuan Zha, ICML 2020\n\n", "strength_and_weaknesses": "# Strengths:\n1. The paper is well-written.\n2. The experiment results show significant gain\n***\n# Weaknesses:\n1. The algorithm can be hard to follow. It would be good to add a pseudocode in the Appendix.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kV0KtO8y4dm", "reviewer": "Reviewer_aMne", "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": "", "summary_of_the_paper": "This work aims to study the problem of improving the resilience of a network while trading off between network utility. The authors point out that though edge rewiring can be a promising direction for network resilience improving, existing learning-free methods are not enough due to their limitations of transduction, local optimality, and utility loss issue; and existing learning-based GNN models are also not enough as they may fail the network resilience optimization. Therefore, the authors provide the solution ResiNet (which includes the newly developed FireGNN model for feature-less graphs), and evaluate it on rich benchmark datasets.", "summary_of_the_review": "Though the novelty of this work is fine to me and the experimental results are impressive, I think the writing is very unclear, and the experimental results are not well-explained, therefore, I think it is not ready to get published.", "strength_and_weaknesses": "Strength:\n\n1. The problem of considering resilience tasks with utility balancing is very interesting, and doing it under an inductive setting makes this work novel.\n2. The experimental results are very impressive.\n\nWeakness (and questions):\n1. The writing is unclear and very hard to follow.\n1) I think the authors abuse the appendix a little bit. I think usually people put the supplementary stuff (like experiments on extra datasets, related background information, details for the baseline models, etc) in the appendix, but would always keep the main paper self-contained. However, in this paper, the authors put some important details that would affect the reading in the appendix, i.e.the main paper itself is not self-contained and can not be fully understood without the appendix. \n2) Sometimes the audience may need to check the many different sections to understand a single definition. For example, to understand what is a resilience metric in section 3, the audience needs to first go to section 5.1, then go to Appendix B.1, and then, the definition is still not very clear, because the authors use the term \"certain attack strategy\" without giving concrete examples or explaining the requirements of the attack strategy.\n3) A small question for figure 1, why will AB and CD be selected at the t+2k+1 step?\n\n2. The experimental results are not well-interpreted. \n1) For table 1, in datasets BA-50 and BA-100, why do almost all the learning-based methods get 0(1)?\n2) why is ResiNet capable of obtaining such a good performance boost on the EU dataset (>100% performance improvement on the second best)? what is so special about this dataset?  \n3) why are so many \"x\" in table 1?\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Y0NhiLRcaE9", "reviewer": "Reviewer_CVfp", "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": "", "summary_of_the_paper": "The resilience of complex networks is a critical structural characteristic in network science, measures the network’s ability to withstand noise corruption and structural changes. The authors propose a framework, ResiNet, combining a variant of GNN called FireGNN to model the structural features of networks and reinforcement learning, to enhance the resilience of network with moderate loss of network utility via neural edge rewiring, which selects two directional edges step by step and rearranges them among four involved nodes, connecting two original head nodes and two original tail nodes. Extensive experiments demonstrate the validity of ResiNet in many kinds of networks and generalization on optimizing different utility and resilience metrics.", "summary_of_the_review": "The authors propose a framework, ResiNet, combining a variant of GNN called FireGNN to model the structural features of networks and reinforcement learning, to enhance the resilience of network with moderate loss of network utility via neural edge rewiring. The experimental results and analysis are also comprehensive. However, due to the weaknesses and concerns above, I think further experiment and revision are needed, so I recommend to reject.", "strength_and_weaknesses": "Strength:\n1. The authors propose the first (claimed by themselves) inductive learning-based approach, ResiNet, to boost the resilience of complex networks, and the design of FireGNN learns meaningful representations via the proposed filtration process.\n2. The experimental results are detailed and plentiful, which provide many perspectives to understand and prove the effectiveness of model.\n3. The authors provide in-depth analysis for their approach and the resilience task itself, further illustrating the reason and the validity of their proposed designs.\n\nWeakness:\n1. There are small writing mistakes in the manuscript, for example, the footnote in the 1st page containing repeating “network resilience”, which makes me confused. In Section 4.2 (5th page) there are wrong spelling “FirGNN”.\n\n2. In Table 1, the authors show that many learning-free methods can also achieve competitive performance, however their computational cost are relatively low. The authors also need to show the computational cost, such as the number of parameters or the training time for their reinforcement learning approach to\tdemonstrate if it is worth trading the cost using the performance.\n\n3. The generalization of reinforcement learning method is important. However, “the generalization on optimizing different utility and resilience metrics” does not seem to be surprising for a learning-based model. What I am concerned about is the performance of the model which trains on synthetic networks but tests on real-world networks, further indicating its generalization and real-world applications. After all, different sizes of\tBA networks\talso\tshare similar characteristics and experiments on them are not convincing.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-r20EWMJab", "reviewer": "Reviewer_6mo7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "summary_of_the_paper": "The paper studies the problem of learning to improve network resilience and unity with reinforcement learning on graphs, which is a important combinatorial optimization problem giving its application in power system and other robust networks. The author designs a reinforcement learning framework with modeling the decision of edge rewiring sequentially with MDP. Policy network is modeled with improved graph neural network as many GNNs failed to model edge selection. The author demonstrate the effectiveness of designed RL based policy over simulation datasets and real-world datasets, on transductive setting and inductive setting. ", "summary_of_the_review": "The author studies the resilience optimization problem with edge rewiring through reinforcement learning and graph neural network. The problem itself is interesting and the pipeline designed is reasonable. My concerns are mainly about experimental settings and evaluation baselines. ", "strength_and_weaknesses": "**Strength**:\n1. Improving network resilience is an important real-world problem. And the method is the first learning based method for finding policies to optimize resilience.\n2. The writing is easy to follow, with many visualization to help understanding the pipeline.\n3. Experimental setup is solid for the new problem, with many traditional baselines, which should be considered as a contribution.\n\n**Weakness**:\n1. The author claimed the designing of FireGNN is effective for modeling the edge selection. The node deleting idea is already explored in [Cotta et al. 21] and [Bevilacqua et al. 21] for improving GNN expressivity. Also deleting by node degree is inherently give a specific ordering of the graph, and it's really strange to see that all other GNNs failed to do edge selection but only the proposed method can do. Even more strange, the biggest improvement is combing from K from 0 to 1, which is hard to understand. Notice that K increasing from 0 to 1 just uses one additional graph for each step, which is similar to using 2-tuple representation. So my intuition is that you need 2-tuple based GNN for edge selection like 2-WL or 2-FWL, and I recommend the author to test with PPGN [Maron et al. 19]. \n2. Similar to above comments, the GNN baselines picked are kind of out-of-date, and I suggest the author to consider include many recent more expressive GNNs. \n3. Perhaps the biggest question is the setup of transductive setting and inductive setting. From my understanding, what we really care about should be the inductive setting. However the author only report partial result with the designed method only, and there is no comparison with non-learning based baselines. Hence I suspect whether the proposed method can really work under inductive setting, or whether comparable with non-learning baselines. \n4. For transductive setting, it seems a bit unfair to compare learning based method and traditional non-learning based method, as the the learning based method needs extremely higher time to train/learn. So the result in Table 1 seems questionable. To give a fair comparison, the author should also report the computational time for all methods. Also I would like to ask whether transductive setting is meaningful in real-world, and I wish the author can give some example about when transductive setting can be used.\n5. Again, the current inductive setting only uses simulation dataset, I wish to see its performance on real-world problem, giving that the problem itself is valuable because of its real-world application.\n\n\n\n\n\n**Reference**:\n[Cotta et al. 21] Reconstruction for Powerful Graph Representations    \n[Bevilacqua et al. 21] Equivariant subgraph aggregation networks    \n[Maron et al. 19] Provably Powerful Graph Networks\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject