Learning to Boost Resilience of Complex Networks via Neural Edge Rewiring
Authors: Shanchao Yang
MA KAILI
Baoxiang Wang
Tianshu Yu
Hongyuan Zha
Venue: Accepted by TMLR ()

Abstract: The resilience of complex networks refers to their ability to maintain functionality in the face of structural attacks. This ability can be improved by performing minimal modifications to the network structure via degree-preserving edge rewiring-based methods. Existing learning-free edge rewiring methods, although effective, are limited in their ability to generalize to different graphs. Such a limitation cannot be trivially addressed by existing graph neural networks (GNNs)-based learning approaches since there is no rich initial node features for GNNs to learn meaningful representations. In this work, inspired by persistent homology, we specifically design a variant of GNN called FireGNN to learn meaningful node representations solely from graph structures. We then develop an end-to-end inductive method called ResiNet, which aims to discover resilient network topologies while balancing network utility. ResiNet reformulates the optimization of network resilience as a Markov decision process equipped with edge rewiring action space. It learns to sequentially select the appropriate edges to rewire for maximizing resilience. Extensive experiments demonstrate that ResiNet outperforms existing approaches and achieves near-optimal resilience gains on various graphs while balancing network utility.

Published in Transactions on Machine Learning Research (08/2023)
Learning to Boost Resilience of Complex Networks via Neu- ral Edge Rewiring
Shanchao Yang
shanchooyang@link.cuk.kk www..
School of Data Science The Chinese University of Hong Kong, Shenzken
Kaili Ma
klma Cesc.. cuhkk edu.hk
Deportment Computer Science and Engineering
The Chinese University of Hong Kong
Baoxiang Wang
brionnguong@cuhh.eu..co
School of Data Science The Chinese University of Hong Kong, Shenzhen
Tianshu Yu
yudianshu@cuhk.edu.
School of Dato Science The Chinese University of Hong Kong, Shenzken
Hongyuan Zha
zhahy edu..r
School of Data Science
The Chinese University of Hong Kong, Shenzhen
Shenzhen Institute of Artificial Intelligence and Robotics for Society
Reviewed on OpenReview: https: // openreview. net/ forum? id= moZv0a5cae
Abstract
The resilience of complex networks refers to their ability to maintain functionality the face of structural attacks. This ability can be improved by performing minimal modifications to the network structure via degree-preserving edge twiring-based methods. Existing learning- free edge rewiring methods, although effective, are limited in their ability to generalize to different graphs. Such limitation cannot be trivially addressed by existing graph neural networks (GNNs)-based learning approaches since there is no rich initial node fcatures for GNNs to learn meaningful representations. In this work, inspired by persistent. homology, we specifically design a variant of GNN called FireGNN to learn meaningful node repre- sentations solely from graph structures. We then develop an end-to-end inductive method called ResiNet, which aims to discover resilient network topologies while balancing network Markov decision
utility. ResiNet reformulates the optimization of network resilience process equipped with edge rewiring action space. It learns to sequentially select the ap- propriate edges to rewire for maximizing resilience. Extensive experiments demonstrate that ResiNet outperforms existing approaches and achieves near-optimal resilience gains on various graphs while balancing network utility.
1 Introduction
Network systems,, such as infrastructure systems and supply chains, are susceptible to malicious allacks, which necessitates addressing their vulnerability through the concept of network resilience. Network resilience serves as a metric to assess the ability of network system to withstand failures and defend itsclf against attacks (Schneider et al. 2011). Figure D visualizes this scenario that the failures of dozen of nodes could jeopardize the connectivity and utility of the FU power network. Maintaining network resilience is crucial in

---

Published in Transactions on Machine Learning Research (08/2023)
18
Origital ResiNet
Normalized
Number remaved nodes
(a) Original EU network
(b) EU network after attacks
(c) Remaining LCC size under attack
Figure 1: The EU power network under the adaptive degree-based attack which removes the most critical node recursively with (a) original EU network with 217 nodes, (b) remaining EU network after series of atlacks 40 nodes, and (c) the change of the normalized size of the largest connected component (LCC). The node size is proportional its degree and the node color given by DBSCAN (Ester et al. 1996..
ensuring that networked systems continue to function and provide an acceptable level of utility, even when confronted with natural disasters or targeted attacks. Consequently, the study of the resilience of complex networks has found widespread applications in various fields, including ecology (Sole & Montoya, 2001)
biology (Motter al. 2008). economics (Haldane & May 2011), and engineering (Albert al.
2004
To enhance network resilience, numerous learning-frees optimization methods have been proposed, typically
falling into heuristic-basse (Schneider et al.] 2011 Chan & Akoglu 2016 Yazıcoohu et al. 2015 Rong &
Liu 2018) and evolutionary computation (Zhou & Liu 2014) categories. These methods aim to improve
the resilience of complex networks by making minimal modifications to graph topologics using a degree-
preserving alomic operation known as edge rewiring (Schneider et al., 2011 Chan Akoglu 2016 Rong
Liu. 2018 Specifically, for given graph G = EV 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 and AB, CD, AD,BC & E. Edge rewiring possesses several advantageous properties when compared to simple addition deletion of edges although edge addition generally outperforms edge rewiring (Beygelzimer jet al. (005). First, edge rewiring preserves node degrees, ensuring capacity constraints are not violated and incurring less network costs [Friitas et al., 2022). Second, edge rewiring minimizes utility degradation in terms of graph Laplacian measurement and thus preserves important graph properties, which may not be the case with edge addition or deletion (Jaume al. 2020 Ma al. 2021).
Despite their success, learning-free methods share the following limitations:
Transduction. Existing methods for selecting edges for rewiring are transductive, meaning that they search for robust topologies specific each individual graph instance. This search procedure is performed independently for each graph and does not generalize across graphs, even if the graphs only differ slightly in structure.
Local optimality. Combinatorially choosing two edges to rewire order achieve globally optimal resilience an NP-hard problem (Mosk-Aoyama 2008). Previous studies rely primarily on greedy algorithms, resulting in local optimality in practice [Chan & Akoglu 2016).
Utility Loss. Rewiring operation in network resilience optimization may result in significant degra- dation of the network utility, potentially compromising the network's overall functionality.
To the best of our knowledge, there is currently no learning based inductive method for optimizing network resilience via edge rewiring. One of the key challenges lies the fact that many network science tasks, including resilience optinization, often involve pure network topologies without rich node features. Learning paradigms based Graph Neural Net (GNNs) have demonstrated their effectiveness in solving wide
2

---

Published in Transactions on Machine Learning Research (08/2023)
Agent
G+22
G
A
A
AC-BD
B
AB-CD
D
B
Figure 2: Action backtracking in successive edge rewirings. The graph Ge+za is shown, where AC and BD represent existing edges. To preserve the node degree, at step t + 2k, one edge rewiring removes AC and BD from Ge+za and introduces AB and CD, resulting in the new graph G4424+1. However, in cases where GNNs fail to provide distinguishable edge representations at step + 2h + 1, leading to a cycle of action backtracking between G++2k and G++28+1-
graphs lacking rich features, the agent may select AB and CD for rewiring
range of graph-related tasks when rich features are available in an inductive manner (Li et al. 2018 Joshi ct al. 2019 Khalil et al.) 2017 Nazari et al. 2018 Peng et al. 2020). However, it remains challenging to adapt these approaches to lasks that rely solely on topological structures, particularly those that require distinguishable node/edge representations for sequentially constructing a solution. For instance, Boffa et al. (2022) demonstrated a significant performance degradation of GNNs when solving the Traveling Salesman Problem (TSP) without incorporating node coordinate features. Similarly, we have empirically observed that the popular combination of GNNs and reinforcement learning (RL) fails to optimize network resilience via edge rewiring, even though similar framework has been successfully employed to improve the resilience via edge additions (Darvariu et al. 2021 2023). Unlike edge addition, which can alter the node degree, edge rewiring preserves the node degree, leading to a graph task with fewer rich features. Therefore, the RL agent gets trapped in an undesired infinite action backtracking loop without mcaningful edge representations, as illustrated Figure 2 A more detailed analysis can be found Appendix D
Therefore, devising novel graph neural network (GNN) that can effectively handle network resilience optimization tasks without relying rich features is challenging endeavor. In this study, we address the aforementioned limitation of GNNs in modeling graphs without rich features. We propose the first inductive learning- based method for discovering resilient networks through successive edge rewiring operations. To accomplish this, we introduce a specialized variant of GNN called Filtration enhanced GNN (FireGNN).
FireGNN draws inspiration from persistent homology and persistence diagrams (Edelsbrunner & Harer 2008
Aktas al. 2019 Hofer et al., 22000: Horn et al.] (022). Persistent homology is a mathematical framework that measures the lifetime of specific topological properties within simplicial complex as simplices are added removed. The sequence of subcomplexes const during this process, known as filtration, provides valuable information about the network's resilience quality (Horak et al. 2009). Motivated by this, FireGNN generates filtration by iteratively removing the node with the highost degree from the original graph, resulting in a series of subgraphs. By employing this filtration process, FireGNN learns to aggregate node representations from each subgraph, enabling the acquisition of meaningful representations. This innovative approach enhances the representative power of FireGNN and addresses the challenge of modeling graphs without rich fcatures. Due the ability of FireGNN to Iearn these meaningful representations, ResiNet successfully avoids becoming trapped in undesired infinite action backtracking loops, common failure case observed in other GNNs.
The main contributions of this paper can be summarized as follows:
1) We propose ResiNet, the first learning-basee method designed to enhance network resilience via edge rewiring without relying on rich node features. ResiNet employs an inductive approach to preserve degrees while minimizing utility loss during the resilience optimization process. formulates resilience optimization as a soquential docision-making process for neural edge rewirings. Extensive experiments demonstrate that ResiNet achieves near-optimal resilience while effectively balancing network utilities, outperforming existing approaches by a significant margin.
3

---

Published in Transactions on Machine Learning Research (08/2023)
2) FireGNN, our technical innovation serving as the graph feature extractor, can learn meaningful representations from pure topological structures. FireGNN provides sufficient training signals to train an RL agent to learn successive edge rewiring operations inductively.
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.
2017p, link prediction (Li et al.
2020a;
Kipf & Welling 2017), graph property estimation (Xu et al. 2019 Kipf
& Welling 2017;
Li et al.)
2020a
Bodnar et al., 2021) and combinatorial problems on graphs (e.g., TSP (Li
let al.
2018
Joshi et al.
2019
Khalil et al.) 2017] Hudson et al., 2022), vehicle routing problem (Nazari
ott al.
2018
Peng et al.
2020),
graph matching Yu et al. (022)) and adversarial attack on GNNs (Ma et al.
2021
Dai et al. 20188)
However, till now, it remains unclear how to adapt GNNs to graph tasks without
rich
2021) like the resilience optimization task that we focus on. Current. lopology-basee GNNs like TOGL (Horn et al. 2022) rely distinct node features for calculating the filtration, while our proposed FireGNN addresses this by creating sequential-related filtration and learning to aggregate them.
feature (Zhu el. al.,
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 heuristics paaristics/larningg basod attack (Fan et al. 2020 [yer al.] 2013 Grassia et al.) 2021 Fan et al., 2020p. Network resilience was proposed and proved a suitable measurement for describing the robustness and stability of a network system under such attacks (Schneider et al. 2011). 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: Darvariu et al.) 2021 2023). protecting vulnerable edges (Wang el 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 induces fewer functionality changes to the original work and does not impose additional loads the vertices (degree-preserving (Schneider
et al. 2011 Rong & Liu 2018 Yazıciğgu et al.) 2015 By now, there has been no learning-basee inductive edge rewiring strategy for the resilience task.
Extended related work. The related work on network ulility, graph structure learning, groph rewiring, multi-views graph augmentation for GNNs and deep graph generation is deferred to Appendix A
3 Problem Definition
An undirected graph is defined G= E), where V = (1.2...... N} is the set of N nodes, E is the set of M edges, A E {0, N is the adjacency matrix, and F E R is the d-dimensional node fcature matrix [ The degree of node is defined as d; Σÿ= Aij, and a node with degree 0 is called an isolated node. Let Go denote the set of graphs with the same node degrees as G.
Let Go denote the set of graphs with the same node degrecs as G. Given the network resilience metric R(G) (Schneider et al. 2011) and the utility metric {(G) (Latora & Marchiori 2003). the objective of boosting the resilience of G is to find a target graph G E Ga, which maximizes the network resilience while balancing the network utility. Formally, the problem of maximizing the resilience of complex networks is formulated
G = arg max (1 (--.)R(())) a
( (G))))
G' &Ga
where a E R is the scalar weight that balances the resilience and the utility.
For graph with pure topological structure, node feature matrix not available.
4

---

Published in Transactions on Machine Learning Research (08/2023)
To satisfy the constraint of preserving degree, edge rewiring is the default atomic operation for obtaining new graphs G' from G. Combinatorially, a total of T successive steps of edge rewiring has the complexity of ((222).
Following the conventional setting in network science, resilience metrics used in our experiments include graph connectivity-baseed (Schneider et al. 2011) and spectrum-based measurements (adjacency matrix spectrum and Laplacian matrix spectrum). Utility metrics consist of global efficiency and local efficiency (Latora & Marchiori 2001). The details of metrics presented follows.
Resilience metrics
Two kinds of resilience metrics are considered:
The graph connectivity-based resilience measurement is defined
(Schneider et al.
2011
R(G)
Σ s4)), N
1
where (q) is the fraction of nodes in the largest connected remaining graph after removing & nodes from G according to certain attack strategy. The range of possible values of R is [1/N, where These two extreme values correspond to a star network and a fully connected network, respectively.
The algebraic connectivity (AC') is the second smallest eigenvalue of the Laplacian matrix of G.
Utility metrics The global and local communication efficiency are used two representative measure- ments of the network utility, which are widely applied across diverse applications of network science, such as transportation and communication networks (Latora & Marchiori] 2003).
The average efficiency of a network G is defined inversely proportional to the average over pairwise distances
Latora & Marchiori 2001 as
F[G) N(N-1 -
Σ
LøjV d(i,j)
where jii,j) is the length of the shortest path between node and another node j. Based on the average efficiency, the global efficiency and local efficiency are defined as
The global efficiency of a network G is defined as Lattora & Marchiori 2001
E(G)
Egioball (G) F(Gideaa))
where Grdeaa is the "ideal" fully-connected graph on N nodes and the range of Fglobar is 10, 1].
The local elficiency of a network G measures local average of pairwise communication efficiencies and is defined (Latora & Marchiori 2001
Etocat (G) N iEV
Σ B(G.),
where G3 is the local subgraph including only of node i's one-hop neighbors, but not the node itself. The range of (Go is [0, 1].
4 Proposed Approach: ResiNet
In this section, we formulate the task boosting network resilience via edge rewiring as a reinforcement learning task by learning to select two edges and rewire them successively. We first present the graph resilienco-aware environment design and describe our innovation FireGNN in detail. Finally, we present the graph policy network that guides the edge selection and rewiring process.
5

---

Published in Transactions on Machine Learning Research (08/2023)
ResiNet
FNNGNN
State G
Node embedding
First edge embedding
ExG
argmax fi(S,
FicGNN
RestNet
Eav step: Rewire AC and BD to
State Gut and reward R,
Ego argmax fa(S,
Second edge em embedding
AB and CD
Figure 3: Overview of the architecture of ResiNet to select two edges for edge rewiring.
4.1 Boosting Network Resilience via Edge Rewiring as Markov Decision Process
To satisfy the constraint of preserving the node degree, the resilience optimization of given graph is based on edge rewiring. 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 time step relies only on the graph time step and the rewiring operation, reducing the complexity from original O(E²T) to O(TE²). Then we further reduce the complexity O(TE) by designing autoregressive edge selection module shown as follows.
B ResiNet performs the resilience optimization in an aulo-regressive step-wise way through a sequence of edge rewiring actions. Given an imput graph, the agent first decides whether to terminate or not. not, it selects one edge from the graph to remove, receives the very edge it just selected as the aulo-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 terminate.
As shown in Figure
After formulating the resilience optimization lask as MDP; reinforcement learning (RL) can be employed as viable solution approach. RT enables an agent to learn optimal decision-making by interacting with an environment. The enviromment can be modeled as an MDP, comprising a set of states, actions, transition probabilities, and rewards. At each time step, the agent observes the current state, selects an action, and receives feedback the form of reward signal and the subsequent state. The ultimate objective of the agent is learn a policy, which mapping from states to actions, that maximizes the cumulative reward over time. Herein, we provide detailed description of the design for the state representation, action selection, transition dynamics, and reward structure.
The fully observable state is formulated as S, G., where G, the current input graph step t. The widely-used node degree feature cannot significantly benefit the network resilience optimization of single graph due to the degree-preserving rewiring. Therefore, we construct node features for each input graph to aid the transductive learning and inductive learning, including
State.
The distance encoding strategy Li ct al. 2020b). Node degree feature is a part of it.
The 8-dimensional position embedding originating from the Transformer (Vaswani et al. 2017 7) as the measurement of the vulnerability of each node under attack. 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 in practice. In our experiments, used the adaptive node degree for the position embedding.

---

Published in Transactions on Machine Learning Research (08/2023)
Action. ResiNet is equipped with node permutation-iivariantt variable-dimensional action space. Given graph Gt, the action de is to select two edges and the rewiring order. The agent first chooses an edge e1 = AC' and a direction A + C. Then conditioning on the state, e1, and the direction the agents chooses an edge 02 = BD such that AB,CD, AD, BC & E and a direction B - D. The heads of the two edges reconnect as a new edge AB, and so does the lail CD. Although G2 is undirected, we propose to consider the artificial edge directions, which effectively avoids the redundancy representing action space since - C, - D and C + A, D + B refer to the same rewiring operation. The choice of the direction of ei is randomized (this randomized bit is still an imput of choosing e2). Therefore, effectively reduces the size of the 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,e) E E²
proposed action space
Transition dynamics. The formulation the action space implies that if the agent does not terminate at stop f, the selected action must form an odge rewiring. This odge rewiring is executed by the environment, and the graph transits to the new graph.
Note that in some other work, infeasible operations are also included in the action space (to make the action space constant through the process) (You et al. 2018 Trivedi et al. 2020). This reduces the sample efficiency and causes biased gradient est inlimooions (Huang & Ontañón 2020) state-dependent variable action space composed of only feasible operations.
ResiNet takes advantage of the
Reward. ResiNet aims to optimize resilience while balancing the utility, forming a complicated and pos- sibly unknown objective function. Despite this, by Wakuta (1955), an MDP that maximizes complicated objective is up to an 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 as
R₂ (1 a) (R(G.4))R((G))
- R(G.)) + a (E(G.+1) - E(G.))
where R(G) and E(G) are the resilience function and the utility function, respectively. The cumulative reward IT-1 R₁ up to time is then the total gain of such a 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 topology. For given input graph G, FireGNN transforms G from the static version to a temporal version consisting of sequence of subgraphs, by repeatedly removing the node with the highest degree. Observing a sequence of nested subgraphs of G grants FirGNN the capability to observe how G evolves towards being empty. Then FireGNN aligns and aggregates the node, edge, and graph embedding from each subgraph, leading to meaningful representations in node, odge, and graph levels. Formally, the filtration in FireGNN is constructed
as
Uk = argmax DEGREE ((k-1) = ((()) Uks
(V,0) (()) c G(1) C... G(N)
G = [G(0), G()) G(N)),
where ((6) denotes the remaining graph after removing N - k nodes with highest node degrees, Uk denotes the node with highest degree in current subgraph GK²), DEGREE(.) mcasures the node degree, G(N) is the original graph, and (()) contains no edge. The sequence of the nested subgraphs of G is termed the filtrated graph G. We illustrate the filtration process toy dataset in Figure 4
Node embedding. Regular GNN only operates on the original graph G to obtain the node embedding for each node vi as M(mx) = ((GN) = G);, where Φ(-) denotes a standard GNN model. In FireGNN, by using the top K + subgraphs in a graph filtration, the final node embedding l(())) of os is obtained by
M(v.)) AGGN (N)))))o..,............))...)))) NN 13 (w:), 1 (v))
7

---

Published in Transactions on Machine Learning Research (08/2023)
e
Figure Filtration Process in FireGNN on BA-15. The original graph decomposed into sequential-related sub- graphs.
where (-) denotes node-level aggregation function, (h00 (et) is the node embodding of i in the k-th subgraph ((k) obtained by passing G' to a backbone GNN, and K E [N]. In practice, (()))))) is discarded when calculating h(v;) if uy is isolated or not included in (*))
Edge embedding. The directed edge embedding (ee)) of the edge from node to node j in each subgraph is obtained by combining the embeddings of the two end vertices G(k) as
(egy) = m (AGGN-E (1 (
where AGGN==(()) 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 & is given by
h(e))) AGGE (n (N(N (eg),.... (NN"" (es)).
where A.Gg(.) denotes an ldgel aggregation function.
Graph embedding. With the node embedding (()()) (w:) of each subgraph (()) available, the graph embed- ding (k() of each subgraph (kk) is calculated by readout functions (e.g., mean, sum) on all non-isolated nodes in (k)) as
(b)) = READOUT (v:)) Ve; E G(k) and d 2 0.
The final graph embedding of the filtrated graph Ô given by
h(G) = AGGG (G)
where AGGG(.) 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(eg)) E [22 xd and the graph embedding lG() E Rd from the filtrated graph G,, and outputs an action a, representing two selected rewired edges, leading to the new state G:+1 with reward Rt.
canension-varialle action space to model the selection of two edges from graphs with arbitrary sizes and permutations. The detailed
To be inductive, we adapt a special autoregressive node permutation-invarine
8

---

Published in Transactions on Machine Learning Research (08/2023)
mechanism of obtaining the action a, based edge embedding and graph embedding is presented as follows, further reducing the complexity from O(T to O(TE).
Auto-rogrossive latent edge selection. An edge rewiring action dr at time step t involves the prediction of the termination probability a and the selection of two edges (a( and af²) and the rewiring order. The action space of dz binary, however, the selection of two edges imposes a huge action space O(1 B))), which is too expensive sample from even for a small graph. Instead of selecting two edges simultaneously, we decompose the joint action a into a, = (a ( aq )) where af" and 2 are two existing edges which do not share any common node (recall that a the probabilily of a, is
(1) and aj are directed edges for undirected graph). Thus
(2)
P(ay)s)) = P(o, (s ((at
(2) ( (s, @ P(a |s, di aa."))
Prodicting the termination probability. The first policy network nu(-) takes the graph embedding as input and outputs the probability distribution of the first action that decides to terminate or not as P(a (0) (sx) xo(h(G)), where xu(-) is implemented by two-layer MIP. Then the probability of the first subaction is given as
(0) a (Pra (s))) E 10.1).
Selecting edges. If the signal af a given by the agent decides continue to rewire, two edges are then selected in an rego-segeessive way. The signal of continuing to rewire at is input to the selection of two odges as a one-hot encoding vector I.- The second policy network Tı (-)-) takes the graph embedding and le as input and outputs a latent vector 4 E Rd determine the selection of edges. To account for the variability in the action space across different graphs, we employ the pointer network (Vinyals et al.) 2015) that offers the advantages of handling variable-sized outputs, flexible action selection, and end-to-end training. The pointer network measures the proximity between and each edge embodding h(ery) in G to obtain the first edge selection probability distribution. Then, to select the second edge, the graph embedding l(G) and the first selected edge embedding h(e,") and le are concatenated and fed into the third policy network T2(-). T²(-) obtains the latent vector l2 for selecting the second edge using a respective pointer network. The overall process be formulated as
P(a," ( s2 of f1(4, l = T (((()) ((e())) Ie),, P(a, (2) 8/ of a = fa(12,h(eig))
4 = (
where Egj E E and (.).) is a two-layer MLP model, [] denotes the concatenation operator, h(((") is the embedding of the first selected edge at step t, and fe(.) is a pointer network.
5 Experiments
In this section, we demonstrate the advantages of ResiNet over existing non-leanning-based and learning- based methods in achieving superior network resilience, inductively generalizing to unseen graphs, and ac- commodating multiple resilience and utility metrics. Moreover, show that FireGNN can learn meaningful representations from graph data without rich features, while current. GNNs fail. Our implementation is available at https: // g thub. com/ http//angyscRRRRn Restlet
5.1 Experimental Settings
Synthetic and real datascts including EU power network (Zhou & Bialek 2005) and Internet peer-lo-peer networks {Leskovec et al. 2007 Ripeanu el al. 2002) are used to demonstrate the performance of ResiNet in transductive and inductive settings. The details of data generation and statistics of the datasets are presented in Appendix [B.1] Following the conventional experimental scttings, the maximal node size is set be around 1000 (Schneider et al., 2011). taking into account: 1) the high complexity of selecting two edges at each step O(F²); 2) evaluating the resilience metric is time-consuming for large graphs.
Datascts.
9

---

Published in Transactions on Machine Learning Research (08/2023)
Table Resilience optimization algorithm under the fixed maximal rewiring number budget of 20. Entries are the format of X(Y), where 1) X: weighted sum of the graph connectivity- resilience and the network efficiency improvement (in percentage); 2) Y: required rewiring number. X means that the algorithm cannot find solution
reasonable time.
Method
BA-15
BA-50
BA-100
BA-500
BA-1000
EU
22P-Gautella05
P2P-Gautella09
26.8 (10)
30.0 (20)
24.1 (20)
(20)
66.6 (20)
19.8 (20)
6.2 (20)
8.4 (20)
HC
18.6 (11.3)
22.1 (20)
14.9 (20)
(20)
16.4 (20)
16.3 (20)
5.2 (20)
7.0 (20)
21.6 (17.3)
11.9 (20)
12.5 (20)
3.8 (20)
42.9 (20)
14.9 (20)
3.9 (20)
3.7 (20)
SA
0.5
16.8 (19.0)
11.4 (20)
13.4 (20)
4.0 (20)
15.4 (20)
14.0 (20)
6.3 (20)
4.8 (20)
23.5 (6)
48.6 (13)
61.3 (20)
X
0.5 [3)
X
X
Greedy
0.5
5.3 (15)
34.7 (13)
42.7 (20)
X
0.3 (3)
X
X
8.5 (20)
6.4 (20)
4.0 (20)
8.5 (20)
174.1 (20)
8.2 (20)
2.7 (20)
0 (20)
EA
0.5
6.4 (20)
4.7 (20)
2.8 (20)
5.6 (20)
18.7 (20)
9.3 (20)
3.7 (20)
0.1 (20)
DE-
13.7 (2)
0 (1)
(1)
1.6 (20)
11.7 (20)
9.0 (20)
2.2 (20)
0 (1)
GNN-RI
0.5
10.9 (2)
(1)
0 (1)
2.7 (20)
20.1 (14)
2.1 (20)
0 (1)
1.0 (20)
K-GNN-
13.7 (2)
(1)
(1)
(20)
(20)
-0.2 (20)
(1)
RL
(2)
(20)
(20)
(20)
(20)
(1)
DIGL-
(2)
5.9 (20)
RI.
7.2 (20)
SDRF-
9.8 (2)
0 (1)
(1)
4.7 (20)
RL
0.5
8.0 (2)
0 (1)
-1.7 (20)
X
5,3 (20)
X
55
ResiNet
35.3 (6)
61.5 (20)
70.0 (20)
10.2 (20)
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)
Baselines. We compare ResiNet with existing edge rewiring-based graph resílience optimization algorithms including learning-free and learning- based algorithms. Learning-free free methods (upper half of Table include the hill climbing (HC) (Schneider et al. 2011 the greedy algorithm (Chan & Akkoluu 2016), the simulated annealing (SA) (Buesser et al. [011], and the evolutionary algorithm (EA) (Zhou & Liu 2014). Since to our knowledge there is no previous (earning-basee 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 al., 2019) and SDRF (Topping al. 2022)) (lower half of Table D. The classical GIN model is used as the backbone (Xu et al. 2019). All baselines trained using
the same reward ResiNet.
The ResiNet's training setup is detailed as follows. Our proposed FireGNN is used as the graph encoder in ResiNet, including a 5-layer defined GIN (Xu et al. 2019) as the backbone. The hidden dimensions for node embedding and graph embedding in cach hiddon layer are set to 64 and the ScLU activation function is used after each message passing propagate. Graph normalization stralegy is adopted to stabilize the training of GNN [Cai et al., 2021). The jumping knowledge network (Xu et al.) [018)) 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 advanlage normalization (Andrychowicz et al. 2021). the dual-clip PPO (the dual clip parameter is set to 10) (Ye et al. 2020), and the usage of different optimizers for policy network and value network. Additionally, since the step-wise reward range is small (around 0.01), we scale the reward by a factor of 10 to facilitate the training of ResiNet. The policy head model and value function model use two separated FireGNN encoder networks with the same architecture. We run all experiments for ResiNet on the platform with two GEFORCE RTX 3090 GPU and one AMD 3990X CPU.
5.2 Comparisons to the Baselines
In this section, we compare ResiNet to basclines in optimizing the combination of resilience and utility with weight coefficient a E {0. Following conventional setting, the graph connectivity- metric is used as resilience metric (Schneider et al. 2011 and the global efficiency is used as utility metric Latora & Marchiori 2003).
Table 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
10

---

Published in Transactions on Machine Learning Research (08/2023)
performance may be achieved by ResiNet under much fewer number of rewiring operations, such as BA-15 with a = O. In contrast, despite approximately searching for all possible new edges, the greedy algorithm is trapped in a local optimum (as it maximizes the one-step resilience gain) and is too expensive to optimize the resilience of a network with more than 300 nodes. For SA, the initial temperature and the temperature decay rale need to be carefully tuned for each network. EA performs subopt with a limited rewiring budget due to the numerous rewiring operations required in the internal process (e.g., the crossover operator). Learning- based 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 a grid search by varying a from 0 to 1 and summarize the resilience gain, utility gain, and the sum of them in Table 2 Table 2 shows that when we only optimize the resilience with 0, the utility will degrade. Similarly, the resilience would also decrease if we only optimize the utility with = 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 simultancously 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 caleulating the final node embedding, edge embedding, and graph embedding. FireGNN degenerates to existing GNNs when the filtration order K is 0. T validates Validatts the effectiveness and necossity 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 G 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 maximun 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 to K, we run grid search on several datasets to optimize the resilience by setting K = 0, 2,3. As shown in Appendix Table 4 the resilience is improved significantly with K > 0 and ResiNet performs well with K = 1 or K = 2. In practice, the choice of the filtration order, denoted as K, depends on the size of the graph. For small and moderate graphs, it is reasonable to set K to the maximum size of the nodes. This allows for a more comprehensive exploration of the graph's substructures during the filtration process. However, when dealing with larger graphs, computational limitations may arise. In such cases, it is advisable to set K to smaller value, such as or 2, to mitigate the computational burden while still capturing important subgraph information. This approach strikes a balance between compulational efficiency and retaining key insights from the filtration process.
5.4 Stability and Generalization
ResiNet leverages our proposed FireGNN to acquire meaningful representations that enhance the resilience of graphs with purely topological structures. By design, ResiNet inherits the stability properties of the backbone GNN employed in FireGNN. As GNNs have been demonstrated to possess permutation equivalence
and stability against relative perturbations in the underlying graph structure (Gama et al. 2019). it follows that ResiNet exhibits stability in the face of such perturbations.
To demonstrate the induction of ResiNet, we first train ResiNet on two different datasets (BA-10-30 and BA- 20-200), and then evaluate its performance on an individual test dataset. We report the averaged resilience gain for the graphs of the same size for each dataset.
11

---

Published in Transactions on Machine Learning Research (08/2023)
2.0
8.00
233
8.99
(a) Induction on resilience
(b) Induction on utility
(c) Induction on both metrics
Figure 5: The inductive ability of ResiNet the test dataset (BA-10-30) when optimizing (a) network resilience, (b) network utility, and (c) their combination.
Table 2: The effect of the coefficient 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
1
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
-2.7
1.1
1.1
5.4
Reward
35.3
34.2
32.9
29.7
15.2
14.2
19.7
11.4
9.2
6.0
5.4
Resilience
56.7
51.1
42.3
48.6
53.9
59.2
51.4
50.6
48.1
39.3
-19.1
BA-50
Ulility
-3.6
3.4
-2.1
-4.0
-4.2
-4.2
-2.6
-2.2
-2.1
0.5
5.5
Reward
56.7
49.5
39.9
43.1
44.9
45.6
35.7
22.0
11.8
5.5
Resilience
75.4
74.6
74.8
76.1
72.8
72.8
75.1
75.4
74.9
71.6
-11.8
BA-100
Utility
-4.0
-4.6
-5.1
-4.2
-4.2
-3.8
-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
The performance of ResiNet on BA-10-30 is shown in Figure and the results other datasets are deferred Figure M Appendix C Figure 5 shows a nearly linear improvement of resilience with the increase of graph size, which is consistent with the results in the transductive setting that larger graphs usually have larger room to improve their resilience. Moreover, conduct experiments to demonstrate the generalization capabilities of ResiNet in optimizing different utility and resilience metrics, and the details are deferred to Appendix
We also use BA-15 as an example to visualize how the values resilience and utility change as a increases from
1.0
Parelo Funlar
0.28
as shown in Figure The Pareto fron- tier line in Figure p reveals that algorithm results in two tradeoff-friendly regions. Specifically, when falls within the range of 0.6 to 1.0, enhancing network re- silience has minimal impact on network utility.
0.8
Reaitoroe
0.28
0.8
04
0.24
5.5 Limitations and Future Work
02
Inspired by persistent homology, our proposed FireGNN utilizes filtration process generate sequence of sub- graphs to improve the representative power of GNNs. Firstly, FireGNN employs backbone GNN to obtain the embeddings of each subgraph. Subscquently, it learns lo aggregate these embeddings from various sub- graphs to derive the final node and graph embeddings. This approach demonstrates excellent performance on graphs of moderate sizes. However, for larger graphs, the computational cost may become prohibitive due to the requirement of calculating and storing all intermediate subgraph embeddings. To address this lim-
0.22
0.585
0.610 (glsbal efficienay)
0,620
Figure The value changes of graph connectivity- based resilience and global efficiency- utility the increases from to on the dataset BA-15.
12

---

Published in Transactions on Machine Learning Research (08/2023)
itation, it would be valuable to develop an efficient version of the filtration process that avoids redundant GNN computations on subgraphs. A promising avenue is to investigate techniques such as precomputing embeddings Yan et al.) 2023), which can enhance the scalability of FireGNN.
6 Conclusion
We have proposed ResiNet, a learning-based inductive method for the discovery of resilient network topologies via edge rewiring with minimal changes to the graph structure. ResiNet is the first inductive edge rewiring- based method that formulates the task of boosting network resilience as an MDP of successive rewiring operations. Our technical innovation, FireGNN, 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 lacking rich features. By decompasing graphs into sequence of subgraphs and learning to combine the individual representations from each subgraph, FireGNN can learn meaningful representations on the resilience lask to provide sulficient gradients for training an RL agent to select correct edges while current GNNs fail due to the infinite action backtracking. Our method is practical as it effectively balances network utility when boosting resilience. FireGNN is potentially general enough to be applied to solve various graph problems without rich features.
Acknowledgements
We want to thank the reviewers and the editors for their constructive comments during the re- view process. Baoxiang Wang is partially supported by National Natural Science Foundation of China (62106213, 72150002) and Shenzhen Science and Technology Program (RCBS20210609) 1010000000013663,, JCYJ20020324410000 1032). Hongyuan Zha is partially supported by Shenzhen Science and Technology Pro- gram (JCYJ202103241 03011200111100000000000000000010 1032, 2DSYS202200610600002 and grant from Shenzhen Institute of Artifi- cial Intelligence and Robotics for Society.
References
Mehmet E Aktas, Esra Akbas, and Ahmed El Fatmaoui. Persistence homology of networks: methods and applications. Applied Network Science, 4(1):1-28 2019.
Réka, Albert and Albert-Lásdló Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47, 2002.
Réka. Albert, István Albert, and Gary L Nakarado. Structural vulnerability of the north american power grid. Physical Review E, 69(2):225003, 2004.
Marcin Andrychowicz, Anton Raichuk, Piotr Stańczyk, Manu Orsini, Sertan Girgin, Raphaël Marinier, Leonard Hussenot, Matthicu Geist, Olivier Pictquin, Marcin Michalski, Sylvain Gelly, and Olivier Bachem. What matters for on-policy deep actor-critic methods? A large-scale study. In ICLR, 2021.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial opti- mization with reinforcement learning. In ICLR, 2016.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. In NewrIPS, 2021.
Alina Beygelzimer, Geoffrey Grinstein, Ralph Linsker, and Irina Rish. Improving network robustness by edge modification. Physica A: Statistical Mechanics and its Applications, 357(3-4))593--61 2005.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pictro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and Lehuan go cellular: CW networks. In NewrIPS, 2021.
Matteo Boffa, Zied Ben-Houidi, Jonatan Krolikowski, and Dario Rossi. Neural combinatorial optimization beyond the TSP: existing architectures redresee graph structure. In AAAT, 2022.
13

---

Published in Transactions on Machine Learning Research (08/2023)
Béla Bollobás and Oliver Riordan. Robustness and vulnerability of scale-free random graphs. Internet Mathemalics, (11):1 -55, 2004.
Maximilian Böther, Ouo KiBig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What's wrong with deep learning in tree search for combinatorial optimization. In ICLR, 2022.
Pierre Buesser, Fabio Daolio, and Marco Tomassini. Optimizing the robustness of scale-free networks with simulated annealing. In ICANNGA, pp. 167-176. Springer, 2011.
Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tic Yan Liu, and Liwei Wang. GraphNorm: principled approach accelerating graph neural network training. In ICML, 2021.
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 by edge rewiring: general framework. Data Mining and Knowledge Discovery, 30(5):1395 1425, 2016.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In JCML, 2018.
Victor-Alesandru Darvariu, Stephen Hailes, and Mirco Musolesi. Goal-directed graph construction using reinforcement learning. Proceedings of the Royal Society A, 477 (222225))20021066 2021.
Victor-Alexandru Darvariu, Stephen Hailes, and Mirco Musolesi. Planning spatial networks with monte carlo tree search. Proceedings of the Royal Society A, 220220888, 2023.
Herbert Edelsbrunner and John Harer. Persistent homology-A survey. Contemporary Mathematics, 453: 257-282, 2008.
Martin Ester, Hans-Peie Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, volume 96, pp. 226 231, 1996.
Changiun 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.
Scott Freitas, Diyi Yang, Srijan Kumar, Hanghang Tong, and Duen Horng Chau. Graph vulnerability and robustness: A survey, IEEE Transactions on Knowledge and Data Engineering, 35(6):59115 5934, 2022.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability of graph neural networks to relative pertur- bations. In The International Conference on Acoustics, Speech, & Signal Processing (ICASSP), 2019.
Marco Grassia, Manlio De Domenico, and Giuseppe Mangioni. Machine learning dismantling and carly- warning signals of disintegration in complex systems. Nature Communicaatonss, 12(1):1 10, 2021.
Xiaojje Guo, Lingfei Wu, and Liang Zhao. Deep graph translation. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-10, 2022.
Andrew G Haldanc and Robert M May. Systemic risk in banking ecosystems. Nature, (7933)3)3335--33 2011.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In NewrIPS, 2017.
Kaveh Hassani and Amir Hoscin Khasahmadi. Contrastive multi-view representation learning on graphs. In TCML, 2020.
Christoph Hofer, Florian Graf, Bastian Rieck, Mare Niethammer, and Roland Kwitt. Graph filtration learning. In ICML, 2020.
Danijela Horak, Slobodan Maletié, and Milan Rajković. Persistent homology of complex networks. Journal of Statistical Mechanics: Theory and Experiment, P003033), 2009.
14

---

Published in Transactions on Machine Learning Research (08/2023)
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. In TCLR, 2022.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategics for pre-training graph neural networks. In ICLR, 2020.
Shengyi Huang and Santiago Ontañón. A closer look at invalid action masking in policy gradient algorithms. CoRR, abs/2006.14177 2020.
Benjamin Hudson Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. In ICLR, 2022.
Swami Iyer, Timothy Killingback, Bala Sundaram, and Zhen Wang. Attack robustness and centrality of complex networks. PloS One, 8(4):e59613, 2013.
Daniel A Jaume, Adrián Pastine, and Victor Nicolas Schvöllner. 2-switch: (ransition and stability on graphs and forests. arXiv preprint arXiv:2004 11 11164, 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 elficient graph convolutional network tech- nique for the travelling salesman problem. CoRR, abs/1906 hass/996.01227,, 2019.
Chaitanya Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning 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 NewrIPS, 2017.
Thomas N Kipf and Max Welling. Semi-supervisod classification with graph convolutional networks. In ICLR, 2017.
Johannes Kliepera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In NewrIPS, 2019.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! In ICLR, 2018.
Vito Latora and Massimo Marchiori. Efficient behavior of small-world networks. 17(19)1198701, 2001.
Physical Review Letters,
Vito Latora and Massimo Marchiori. Economic small-world behavior in weighted networks. The European Physicul Journal B-Condensed Maller und 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 diam- eters. ACM transactions on Knowledge Discovery from Data (TKDD), 111::-css, 2007.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. DeeperGCN: All you need to train deeper GCNs, arxiv preprint Xiv:22000 2020a.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In NewrIPS, 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 2019.
15

---

Published in Transactions on Machine Learning Research (08/2023)
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In NeurIPS, 2018.
Yao Ma, Suhang Wang, Tyler Derr, Linglei Wu, and Jiliang Tang. Graph adversarial altack via rewiring. In KDD, pp. 1161-1169, ACM, 2021.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen; Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAT, 2019.
Damon MoskaAoyama. Maximum algebraic connectivity angmentation is NP-hard. Operations Research Letters, 36(6):677 679, 2008.
Adilson E Motter, Natali Gulbahce, Eivind Almaas, and Albert-Lásdló Barabási. Predicting synthetic rescues metabolic networks. Moleculor Systems Biology, 4(1):168, 2008.
MohammadReza Nazari, Afshin Oroojlooy, Lawrence V. Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In NeurIPS, 2018.
Bo Peng, Jiahai Wang, and Zizhen Zhang. A deep reinforcement learning algorithm using dynamic attention model for vehiele routing problems. CoRR, http/2002.032222 2020.
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 pro-training. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2020.
Matei Ripeanu, lan Foster, and Adriana lamnitchi. Mapping the gnutella network: Properties of large-scale peer-to-peer systems and implications for system design. arXiv preprint cs/0209028, 2002.
Lci Rong and Jing Liu. A hcuristic algorithm for enhancing the robustness of scale-free networks based on edge classification. Physica A: Statistical Mechanics and its Applications, 503:503-515, 2018.
Christian M Schneider, André A Moreira, José S Audrade, Shlomo Havlin, and Hans J Herrmann. Mitigation of malicious allacks networks. PNAS, 108(10):3838 3841, 2011.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimiza- tion algorithms. CoRR, abs/ ht/p/777000347, 2017.
Ricard V Sole and Ma Montoya. Complexity and fragility in ecological networks. Proceedings of the Royal Society of London. Series B: Biological Sciences, 268(1480) 2003992245,,21 2001.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bron- stein. Understanding over-squashing and bottlenecks on graphs via curvature. In ICLR, 2022.
Rakshit Trivedi, Jiachen Yang, and Hongyuan Zha. GraphOpt: Learning optimization models of graph formation. In ICML, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NewrIPS, 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In NewrIPS, 2015.
Kazuyoshi Wakuta. Vector-valued markov decision processes and the systems of linear inequalities. Stochastic Processes and Their Applications, 56(1):159- 1995.
Xiangrong Wang, Evangelos Pournaras, Robert E Kooij, and Piet Van Mieghem. Improving robustness of complex networks via the ellective graph resistance. The European Plysioall Journal B, 87(9):1-122 122, 2014.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In ICML, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In
ICLR, 2019.
16

---

Published in Transactions on Machine Learning Research (08/2023)
Zuoyu Yan, Junru Zhou, Liangeai Gao, Zhi Tang, and Muhan Zhang. Efficiently counting substructures by subgraph gnns without running gun subgraphs. arXiv preprinl ar arXiv:2303. 10576, 2023.
A Yasin Yazcioglu, Magnus Egerstedt, and Jeff S Shamma. Formation of robust multi-agent networks through self-organizing random regular graphs. TEEE Transactions Network Science and Engineering, 1(4):139-151, 2015.
Deheng Ye, Zhao Liu, Mingfei Sun, Bei Shi, Peilin Zhao, Hao Wu, Hongsheng Yu, Shaojie Yang, Xipeng Wu, Qingwei Guo, al. Mastering complex control moba games with deep reinforcement learning. In AAAI, 2020.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay S. Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In NewrIPS, 2018.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph rastivevvve learning with augmentations. In NewrlPS, 2020.
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Deep latent graph matching. In ICML, 2021.
Mingxing Zhou and Jing Liu. memetic algorithm for enhancing the robustness of scale-free networks against malicious attacks. Physica A: Statistical Mechanics and its Applications, 410:131 110:131-143, 2014.
Qiong Zhou and Janusz W Bialek. Approximate model of european interconnected system benchmark system to study effects of cross-border trades. IEEE Transactions on Power Systems, 20(2):782-788, 2005.
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Yuanqi Du, Jieyu Zhang, Qiang Liu, Carl Yang, and Shu Wu. A survey graph structure learning: Progress and opportunitics. In IJCAI, 2021.
17

---

Published in Transactions on Machine Learning Research (08/2023)
Appendix
A Extended Related Work
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 metric for network utility is the network efficiency Latora & Marchiori] (2003). In many previous work, despite that netw resilience could be improved, the utility may dramatically drop at the same time Carchiolo et al. (0119); Schneider et al. (2011); Chan & Akoglu (2016); [uesser et al. (011]). This contradicts the idea behind improving network resilience and will be infeasible in real-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, GST 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 a graph, while there are generally no rich features in graph generation. Morcover, GSL cannot control the graph's node degree during graph optimization. We refer the interested readers to survey of GSL Zhu et al. (2021) since our work is a constrained graph generation task unrelated to GSL.
Graph rewiring Graph rewiring is typically used in the GNN community to build novel classes of GNNs by preprocessing a given graph to overcome the problems of the over-squashing issue of training GNNs. For example, Klicpera 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-basod 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 a special graph rewiring operator that preserves node degree.
Multi-view graph augmentation for GNNs. Multi-views graph augmentation is one efficient 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 GCA adaptively incorporates various priors for topological and semantic aspects of the graph You et al. (020 Hassani & Khasahmadi (2020) contrasts representations from first-order neighbors and a graph diffuuion. DeGNN Jin et al. (2020) was proposed as an automatic graph decomposition algorithm to 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 [Fdelsbrunner & Harer 2008), we apply the filtration process to enhance the expressive power of GNNs for handling graphs without rich features.
Deep graph generation. Deep graph generation models learn the distribution of given graphs and gen- erate 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 on molecular graph generation. GT-GAN Guo et al. 2022) proposes a GAN-based model on malware cyber-network synthesis. GraphOpt Trivedi et al. learns an implicit model to discover an underlying optimization mechanism of the graph generation using inverse reinforcement learning. GFlowNet learns a stochastic policy for generating molecules with the probability proportional to a given reward based on flow networks and local matchingg conditions Bengio ct al. (2021). Boosting network resilience a degreo-preserving way can be viewed as a constrained graph generation task. However, none of existing graph generation methods can generate desired graphs with the exact node degree preserving constraint, which is required by the resilience task.
(2020)
18

---

Published in Transactions on Machine Learning Research (08/2023)
Table Statistics of graphs used for resilience maximization. Both transductive and inductive settings (x) are report the number of edges by transforming undirected graphs to directed graphs. The edge rewiring has a fixed execution order. For the inductive setting, we report the maximum The action space size of the edge rewiring is measured by 2|
included. Consistent with our implementation,
number of edges.
Dataset
Node
Edge
Action Space Size
Train/ Test
Setting
BA-15
15
541
5832
X
Transductive
BA-50
50
192
73728
X
Transductive
BA-100
100
392
307328
X
Transductive
BA-500
500
996
1984032
X
Transductive
BA-1000
1000
999
1996002
X
Transductive
EU
217
640
819200
X
Transductive
p2p-Grie Goptelneee
400
814
1325192
X
Transductive
D2p-Gnutellady)
300
740
1095200
X
Transductive
BA-10-30 (+)
10-30
112
25088
1000/500
Inductive
20--20-000 (+)
20-200
792
1254528
4500/300 /30
Inductive
B Implementation Details
This section provides the implementation details, including dataset and baseline setup.
B.1
Dataset
We first present the data generation strategies. Table 3 summarizes the statistics of each dataset. Syn- thetic datasets are generated using the Barabasi-Albert (BA) model (known as scale-free graphs) (Albert & Barabási 2002). with the graph size varying from |1|=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 con- nected one existing node for graphs with near 1000 nodes. BA graphs 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.
Transductive setting.
The algorithm trained and tested on the same network.
Randomly generated syuthetic BA networks, denoted by BA-m, are adopted to test the perfor- mance of ResiNet on networks of various sizes, where m (15, 50, 100,5000 1000} is the graph size.
The Gnutella peer-to-peer network file sharing network from August 2002 Leskovec et al. 2007 Ripeanu et al. 2002) and the real EU power network (Zhou & Bialek 2005) are used to validate the performance 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 (Leskovee & Faloutsos 2006).
Inductive setting. Two groups of synthetic BA networks denoted by BA-m-n are randomly generated to test ResiNet's inductivity, where is the minimal graph size, and indicates the maximal graph size. We first randomly generate the fixed nunber of BA networks as the training data to train ResiNet and then evaluate ResiNet's performance directly on the test dataset without any additional optimization.
B.2 Baseline Setup
All baselines share the same action space with ResiNet and use the same action masking strategy to block invalid actions as ResiNet docs. The maximal objective evaluation consistent for all algorithms. Other settings of baselines are consistent with the default values in their paper. The carly-stopping strategy is used for baselines, which means that the search process terminates if no improvement is obtained in successive
19

---

Published in Transactions on Machine Learning Research (08/2023)
Table The effect of the filtration order K on ResiNet in improving network resilience (percentage).
K
BA-15
BA-50
BA-100
F.U
0
11.8 + 2.7
0 + 0
0 0 0
6.1 + 4.2
1
17.6 + 0
49.6 - 2.3
74.9 = 0.8
54.5 + 0.4
2
17.6 + 0
51.0 + 0.1
76.3 + 1.2
57.4 + 1.6
3
17.6 + 0
55.742.3
73.1 + 0.9
54.9 + 0.9
1000 objective function calling trials. All algorithms are repeated for 3 random sceds using default hyper- parameters.
C Extended Experimental Results
In this section, present additional experimental results to show that ResiNet generalizes to unseen graphs, different utility and resilience metries.
C.1 The Effect of Filtration Order K on FireGNN
In this section, we report the ratio of the remaining edges in subgraphs versus different filtration order K in Table 5 and visualize it in Figure The maximum filtration order K of FireGNN of each dataset is summarized in Table D Table @ demonstrates that the maximum filtration order is nearly around the half size of the graph since we gradually remove the node with the largest degree in the filtration process.
Ratio of remaining edges in subgraph
1.0
BA-15
BA-50
BA-100
BA-500
BA-1000
0.6
EU
P2P05
044
P2P09
0.2
C.2 Inductivity on Larger Datasets
0.0
To demonstrate that ResiNet can learn from networks to accommodate different utility and resilience metrics, we conduct experiments based on BA-15 using multiple re- silience and utility metrics. The Pareto points shown Figure G denote the optimmum under different objectives BA-15, implying that ResiNet can obtain the approx- imate 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 C.3 and the optimized network structures are visualized in Figure and Figure 10
100
Number of removed nodes
Figure Ratio of the remaining edges in subgraphs versus different filtration order K.
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 graphs of different sizes by training ResiNet the BA-20-200 dataset, which consists of graphs with the size ranging from 20 to 200, and then report its performance on directly guiding the edges selections on unseen test graphs. The filtration order K is set to 1 for the computational limitation. As shown in Figure g we can see that ResiNet has the best performance for N E [70, 100]. The degrading performance with the graph size may be explained by the fact that larger graphs require a larger filtration order for ResiNet work well. 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 strategy to balance these two metrics.
20

---

Published in Transactions on Machine Learning Research (08/2023)
0.1
15
0.00
Wwlgg suRn of ruailiano and utilty gain
0.15
0,6
0.
Resiieeoe getggee
0.3
0.0
-0.1
0.1
-02
25
60
75
100
150
175
200
100
Graph M
(a) Inductivity on resilience
(b) Inductivity on resilience and utility
Figure The inductive ability of ResiNet the test dataset (BA-20-200) when optimizing (a) network resilience and (b) the combination of resilience and utility.
Table 5: The ratio of remaining edges in subgraphs versus the filtration order
K BA-15
BA-50
BA--10
BA-500
BA-1000
EU
22P-Gmutella03
DP-GGuttlla099
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.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
0.4031
0.7199
0.7698
0.7719
0.8231
0.75
Table Maximum filtration order K each dataset.
Dataset
BA-15
BA-50
BA-100
BA-500
BA-1000
EU
CD--Guutelaa5
P2P-GnutellaOy)
Size (uode)
15
100
500
1000
217
400
300
Maximum of K
7
23
42
226
306
103
216
160
C.3 Learning Balance Different Utility and Resilience Metrics
As shown in Figure we conduct extensive experiments 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-based attack, such as the node betweennes--based attack.
Table 7 records the improvements in percentage of ResiNet for varying objectives on the BA-15 dataset. As visualized in Figure g ResiNet is not limited to defend against the node degree-based attack (Figure 9 (b)- (i)) and also learns to defend against the betweenness based attack (Figure g (k)- Total three resilience metrics are used, with R denoting the graph connectivity
resilience metric, SR being the spectral radius and SR representing the algebraic connectivily. Total two utility metrics are adopled, including the global efficiency Eylobel and the local efficiency Etocal- Not surprisingly, the optimized network with an improvement about 3.6% for defending the betweenness-based attack also has higher resilience (around 7.8%) against the node-degree attack. This may be explained as the similarity between node degree and betweenness for small work.
21

---

Published in Transactions on Machine Learning Research (08/2023)
(a) Original
(b)
(c) AC
(d) RD Eglobal
AC Eglobai
(f) R.D Flocal
(g) ACD + Fiocal
(h) R
(i) ACB
(i) R. + Figtobal
0
(k) AC + Figlobal
()) Ra + Froend
(m) AC + Fioeat
Figure 9: The resilience maximization the BA-15 dataset with 15 nodes and 27 edges with (a) original network. (b)-(i) results of defending the node degree-based attack with different combinations of resilience and utility, and (k)-(() results of defending against the node betweemness-based attack with varying combinations of resilience and utility. For two resilience metrics, R denotes the graph connectivity-based resilience metric and AC represents the algebraic connectivity. For two utility metrics, Eglobal denotes the global efficiency and Elocal the local efficiency.
(a) Original EU network
(b) R
(c) Egglobat
Figure 10: Visualizations the original EU network and optimized networks using ResiNet with different objectives: R means the comnectivity-based resilience measurement and Egtobat is the global efficiency.
Table 7: Performance gain (in percentage) of ResiNet in optimizing varying objectives on the BA-15 network. All objectives are optimized with the same typer-parameters. which means that we did tune hyper-parameters for objectives except for Rp.
Objective
Gain (%)
Objective
Gain(%)
RD
35.3
RB
14.6
ACD
48.2
AC
43.2
22

---

Published in Transactions on Machine Learning Research (08/2023)
Table Resilience optimization algorithm under the fixed maximal rewiring number budget of 200, Entries are the format of X(Y,, where 1) X: weighted sum of the graph connectivity- resilience and the network efficiency improvement (in percentage); 2) required rewiring number. Results are averaged over runs and best performance is in bold.
Method
BA-15
BA-50
BA-100
BA-500
BA-1000
EU
P2P-Gmutella05
Grntellelll9
0
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 (137.7)
IIC
0.5
18.6 (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)
0
26.8 (20)
49.7 (59.0)
84.5 (119.7)
43.2 (200)
271.8 (200)
73.5(160.3)
37.1 (200)
37.2 (134)
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)
0
23.5 (6)
48.6 (13)
64.3 (20)
X
0.5 (3)
X
X
Groody
0.5
5.3 (15)
34.7 (13)
42.7 (20)
X
0.3 (3)
X
X
0
35.3 (X)
50.2 (X)
61.9 (X)
9.9 (200)
174.1 (200)
06.2 (X)
2.3 (200)
0 (200)
EA
0.5
27.1 (X)
38.3 (X)
46.6 (X)
6.8 (200)
18.7 (200)
58.4 (X)
3.2 (200)
(200)
DE-
0
13.7 (2)
0 (1)
(1)
1.6 (20)
41.7 (20)
9.0 (20)
2.2 (20)
0 (1)
GNN-RL
0.5
10.9 (2)
0 (1)
(1)
2.7 (20)
20.1 (14)
2,1 (20)
0 (1)
1.0 (20)
I-GNN-
0
13.7 (2)
0 (1)
0 (1)
(1)
8.8 (20)
4.5 (20)
-0.2 (20)
0 (1)
RT.
0.5
6.3 (2)
0 (1)
(1)
(20)
-24.9 (20)
4.8 (20)
-0.1 (20)
0 (1)
0
35.3 (6)
61.5 (20)
70.0 (20)
10.2 (20)
172.8 (20)
54.2 (20)
14.0 (20)
18.6 (20)
ResiNet
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)
C.4 Performance Comparisons Under Large Rewiring Budget
In this section, we present the resilience improvement and the required number of edge rewiring of each algorithm under a large rewiring budget of 200. The running speed is presented to compare the running time efficiency of each algorithm.
As shown Table traditional methods improve the network resilience significantly compared ResiNet under large rewiring budget of 200. However, traditional 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 a real system. For example, the actual number of rewiring budget for EA is hard to calculate since it is a population-basee algorithm, so it is omitted in Table g All basclines adopt the carly-stopping strategy (hat they will terminate if Lhere no positive resilience gain in a successive 1000 steps.
Table 9 indicates that the time takes for the benchmark algorithm to solve the problem usually increases as the test data set size increases. In contrast, our proposed ResiNet is suitable for testing on large dataset once trained.
Table 9: Running speed (in second) of the resilience optimization algorithm under the fixed maximal rewiring mumber budget. Entries in the format of ( where 1) X: speed under the budget of 20; 2) Y: speed under the budget of 200 x means that the result is not available at a reasonable time. Results are averaged over 3 runs and best performance is in bold.
Method
a
BA-15
BA-G0
100
BA-500
BA-1000
EU
P2P-Gmutella05
P2P-Cnutella09
0
1.0 (1.0)
1.1 (6.4)
1.3 (22.2)
21.9 (354.1)
80.3 (1288.3)
3.1 (94.2)
15.3 (358.1)
4.5 (89.1)
НС
0.5
155 (11.5)
1.1 (12.8)
2.0 (49.0)
40.9 (589.5)
148.7 (2603.7) 7)
5.3 (193.7)
24.7 (462.8)
7.0 (190.6)
0
0.5 (0.5)
0.3 (6.6)
0.6 (22.6)
12.2 (313.0)
45.7 (1051.8)
2.4 (91.2)
10.8 (286.4)
2.6 (89.4)
SA
0.5
0.7 (1.7)
(13.2)
1.7 (47.5)
33.9 (568.9)
99.8 (2166.3)
5.0 (193.5)
23.9 (454.5)
6.3 (188.5)
0.2 (6.0)
34.1 (34.5)
766.3 (X)
3061.7 (X)
Greedy
0.5
0.7 (0.7)
64.1 (65.4)
1478.9 (X)
6192.6 (X)
0.01 (X)
(X)
(X)
10.3 (X)
0.2 (X)
1.6 (X)
0.4 (X)
F.A
0.5
(X)
(X)
(X)
(X)
15.0 (X)
0.4 (X)
(X)
0.8 (X)
DE-
0
0.1 (X)
0.1 (X)
0.1 (X)
14.9 (X)
70.3 (X)
3.6 (X)
8.7 (X)
0.5 (X)
GNN-RL
0.5
0.1 (X)
0.1
0.2 (X)
13.7 (X)
60.9 (X)
4.5 (X)
1.0 (X)
6.7 (X)
I- A-NN
0.02 (X)
0.03 (X)
0.07 (X)
1.3 (X)
56.5 (X)
2.6 (X)
8.2 (X)
0.5 (X)
RT.
0.5
0.02 (X)
0.04 (x)
0.08 (x)
18.3 (X)
76.1 (X)
3.6 (X)
11.5 (X)
0.6 (X)
0
0.5 (X)
188 (X)
2.2 (X)
17.5 (X)
66.8 (X)
4.5 (X)
14.7 (X)
9.3 (X)
ResiNet
0.5
0.5 (X)
1.9 (X)
2.4 (X)
18.0 (X)
67.5 (X)
5.2 (X)
15.0 (X)
10.3 (X)
23

---

Published in Transactions on Machine Learning Research (08/2023)
C.5 Inspection of Optimized Networks
Moreover, to provide deeper inspection inlo 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 10 (b) is the network structure obtained by only optimizing the graph connectivity- based resilience. We can observe a more crowded region on the left, consistent with the "onion-like" structure concluded in previous studies. If we consider the combination gain of both resilience and utility, we observe a more compact clustering "crescent "oone-like structure shown in Figure 10 (c).
D Deep analysis of why regular GNNs fail in the resilience task
Ii is well-known that. GNNs generally work well for graphs with rich features. Unluckily, the graph network in the resilience task has no node/ /eee///geeeeee /dde/graph feature, with only the topological structure available. No rich feature means that the output of the GNNs is not distinguishable, and then it is difficult for the RL agent to distinguish different vertices/eddee /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 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 infinile action backtrucking phenomenon. The agent would select AC and BD at step ++ 1, returning back to G, and forming a cycled loop between G2 and G++1- Formally, the infinite loop is formulated as
((A, (A, (C, = argmax SIM ( (2), (hT kf)), M,)),a.))
((A, C), (B, D)) = argmax SIM (,44)) (h h (),)), haw.)
i.j.M,nEL:N
where SIM is a similarity metric, hi and ha, are embeddings of node i and graph G, at step t, 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 a distinct expressive power and learns to create more meaningful and distinguishable features for each edge. FireGNN is not a simple aggregation of higher-order information of a static graph. It was inspired by homology filtration and the multi-view graph augmentation. Persistence homology motivates us to aggregate more distinct node features 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.
24

---

Published in Transactions on Machine Learning Research (08/2023)
Sealabillty
300
300
100
50
100
20
190
Trainin & Infevvee
Atlent
Arteoraon
S2V
S2V
CAN
RNW
CAN
GAX
GNN
CAN
Probiem Complesity
Table 10: Characteristies of different graph related tasks.
0101
OW
0103
01
0
010
0
O
The 100 UpSooe
Sunngg in Fedi kanoy Cala Solmmn (nl
diange in reel Pence (oele
duangs in cnt wiight
dianng hour coot
chaing in Loii cod
doang in kour cosl
change in hour coet
Logest
in
RL
add mode to auhbod
athert
wid mode to Gni
add mode Lonr
add mode tonr
wige Miliiio
add mode
edge
made love
boods lnved
Bodde lowe
modle level
modde love
gropih looal
gropph
edee
Hos NoslBoan Batun WEtE dilcee
Taok
Max-
TSP
TSP
TSP
VEP
201
Duront 20024
201
SaV-nQQ Kisill ait ml
GANNCL mL
Kook OF
Antontinn
NoNe- PON
RNN--R
Local
SCC
25


Reviews:
[{"review_id": "CshFAXnu6k", "reviewer": "Reviewer_7uvs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Innovation: The paper presents a novel approach (ResiNet and FireGNN) for improving network resilience, providing a significant advancement over existing methods.\n2. Broad Applicability: The proposed methods do not require rich node features, making them widely applicable to various network systems with different graph structures.\n3. Effectiveness: The experimental results provide evidence for the effectiveness of ResiNet, as it outperforms existing methods in enhancing network resilience while maintaining network utility.\n\nWeaknesses:\n1. Lack of Real-world Testing: Although the paper presents a promising approach with extensive theoretical and experimental support, it lacks a crucial element - the application of this approach in real-world network systems. While simulated environments or abstract graphs are suitable for initial testing and concept proofing, they may not encapsulate the complexity and unpredictable nature of real-world networks, which can include fluctuating network loads, varying degrees of node failures, and adaptive attacks. Without tests in practical scenarios, the utility and applicability of the proposed approach may be limited. It would be insightful to include results from tests in real-world conditions, such as telecommunication networks, power grids, or transportation systems, to demonstrate the robustness and applicability of the proposed ResiNet and FireGNN methods in these challenging environments.\n2. Computational Efficiency: Another potential drawback in the paper lies in the computational efficiency of the proposed method. The optimization process described, which includes sequentially selecting the appropriate edges to rewire, could potentially be computationally expensive, especially for large-scale networks with hundreds or thousands of nodes. This can limit the method's scalability and practical utility. For instance, in a real-world scenario like an infrastructure system or a supply chain network, the method may not be feasible if it requires extensive computation resources or takes an unreasonably long time to improve the network's resilience. The paper would be strengthened by including a thorough analysis of the computational complexity of the proposed method and discussions on its scalability to larger networks.\n3. Unclear Failure Scenarios: The paper presented the proposed methods in a very positive light, showing they outperform existing methods significantly. However, no method is foolproof, and it is essential to understand the limitations and potential failure points of the proposed approach. The absence of a discussion on potential limitations or failure scenarios might create a biased perspective towards the method's overall robustness. Such a discussion is important because it helps users and researchers understand when it might be unsuitable to employ the proposed methods, what issues they may encounter, and what improvements could be made in the future. For instance, how would the method perform in networks with a specific structure that makes edge rewiring difficult or in networks experiencing dynamic changes? Are there certain types of networks where the performance of the method might decline significantly? Including such discussions would provide a more balanced and comprehensive view of the proposed methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a novel technique to enhance the resilience of complex networks in the face of structural attacks, by employing a method called degree-preserving edge rewiring. Most existing methods do not effectively generalize across different graphs. To address this, the authors propose a new variant of Graph Neural Networks (GNNs), named Filtration enhanced GNN (FireGNN), and an inductive method called ResiNet. The FireGNN is designed to learn meaningful node representations purely from graph structures. ResiNet takes a step further by transforming the optimization of network resilience into a sequential decision-making process under the frame of a Markov decision process. Experimental results showed that ResiNet significantly outperformed existing methods, achieving near-optimal resilience on various graph structures while also preserving network utility.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The Strengths And Weaknesses section provides some suggestions and questions, which might help improve the quality of the paper.", "broader_impact_concerns": "I have no concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HDlDyGBWbc", "reviewer": "Reviewer_NdKT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n\nThis paper studies a meaningful problem to boost the resilience of complex networks, which are pervasive in our world. The proposed method is a novel learning based method, and the experiments are conducted comprehensively on multiple datasets.\n\nWeaknesses\n\nSome parts are not clear enough, e.g. the motivation of the FireGNN design is unclear, which is a major concern of this work, please see the concerns below:\n\n1. Edge rewiring protects the capacity constraint, while edge addition or deletion cannot. But what if the capacity constraints are considered and the edge addtion is required to not exceed the constraint? Is there any advantage of edge addition and deletion over rewiring?\n\n2.  Edge rewiring minimizes the utility degradation in terms of graph Lapalacian. Why is this important? Is this only important to specific applications like electricity networks?\n\n3. It is stated that learning-free methods has poor transduction capability. However, since the learning-free methods do not learn anything from the graph, when a new graph is given, the algorithm still performs the same procedure, why is this concerened with transduction problem? Learning based methods may experience overfitting and lack of transduction/generalization capability. They also need training process causing extra cost. But the learning-free methods do not sound like to have these issues. \n\n4. With GNNs, the node attributes can also be initialized as the degrees or other graph statistics, this strategies are widely accepted for graphs without node attributes, therefore it is not clear why cannot GNNs be directly used.\n\n5.  Why is the FireGNN designed to operate on a sequence of graphs obtained by filtraton process? Why is the concatenation of the node representation obtained at different graph snapshots beneficial for the target task. How is persistent homology related to this work? Also, it is unclear how is the input  node attribute initialized.\n\n6. Why are the resilience metrics able to reflect the resilience of the networks in real-world? It seems that different real-world networks function differently, and why is the resilience metrics universily applicable?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the resilience bossting problem in complex networks via edge rewiring. Specifically, existing non-learning based methods have limited generalization capability, while GNNs cannot be straightforwardly applied to resolve this problem due to the lack of rich node attributes in the input data.\n\nThe soluton provided in this paper consists of a FireGNN that generates node representations solely based on the graph structures, and a ResiNet that models the resilience bossting as a Markov decision process via the edge rewiring actions. \n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would be better if the concerns above are addressed.", "broader_impact_concerns": "Complex networks are pervasive in our world, therefore this work is related to multiple perspectives like electricity network, the Internet, etc.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8Jc5HAyyse", "reviewer": "Reviewer_PxTN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strengths of the paper are:\n\n1. A principled way of addressing rewiring in a 'learning' scenario.\n2. A well-principled and justified method for balancing network utility and efficiency.\n\nAt the same time, there are some weaknesses that need to be addressed\nbefore this submission is ready for publication. The primary weakness\nis a lack of clarity: some concepts (especially for RL) are lacking a\ndetailed description, making it harder to understand this submission,\nor necessitating referring to additional literature. In addition, the\nterminology is not fully consistent and some experiments require more\ndetails.\n\nSubsequently, I comment on some changes to rectify these issues.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission presents a new algorithm for rewiring networks under the\nconstraints of improving resilience and maintaining network utility. The\nnew method is inspired by concepts from computational topology, and uses\nsuch concepts to learn structure-based node representations. Following a\nrepresentation learning step, network structure is optimised by treating\nthe rewiring operation as a Markov decision process.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please update the rewiring example in the introduction and make it\n  clear *why* some of the edges must not exist (i.e. in order to still\n  have the degree-preserving property).\n\n- Please provide more details on the filtration and its definition. In\n  computational topology, filtrations are typically used to assess\n  functions on structured data via multiple scales. Can you link this\n  motivation to your work?\n\n- When talking about a 'temporal-related filtration,' this might be\n  misleading since the time aspect is referring to the algorithm itself\n  rather than some time encoded on the graph edges; I would suggest to\n  clear that up.\n\n- The terminology for resilience and utility is not used consistently in\n  Section 3.\n\n- Please highlight the relevant edges in Figure 4, I found this figure\n  rather confusing at my first read of the paper.\n\n- When discussing parts of the method in Section 4.1, please provide\n  more background on RL. Moreover, please address to what extent\n  'tottering' or 'loops' are prevented; is it possible that the method\n  will flip back and forth between a set of edges, or is this prevented\n  by your method?\n\n- How is $K$ picked in practice? Please add more details.\n\n- What are the reasons for choosing the pointer network? Please clarify.\n\n- When discussing the experiments, please clarify to what extent other\n  methods can be trained with a similar reward. My impression was that\n  the new objective or reward was designed specifically for the problem\n  at hand. Is it easy to add to existing methods or does the $\\alpha$\n  parameter only refer to a post-hoc evaluation (as opposed to a full\n  training)?\n\n- Please comment on the **stability** and **limitations** of the\n  proposed approach. Some of the existing rewiring algorithms, e.g. ones\n  based on the `PageRank` algorithm or on diffusion, come equipped with\n  stability guarantees and a well-understood behaviour under\n  perturbations. What types of guarantees hold for the proposed method?\n  Are there situations in which the method does not work as expected?\n\nSome minor points concerning the wording and typesetting:\n\n- The main contributions of the paper are duplicated on p. 3\n\n- 'pure topology structure' --> 'pure topological structure'\n\n- 'the environment performs [...]': environment does not seem to be the\n  correct word here.\n\n- Please perform another round of consistency checks for the\n  bibliography. At present, some entries are not consistently spelled or\n  capitalised (e.g. 'lehman' instead of 'Lehman').\n", "broader_impact_concerns": "There are no broader impact concerns to be raised by this work.\n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers were generally unanimous in appreciating the importance of the tackled problem as well as the novelty and effectiveness of the proposed approach.  Some concerns were raised, in particular with regards to presentation and clarity, but these have been effectively addressed by the authors during the discussion period.  In light of this, I recommend accepting the manuscript as is.
Decision: Accept (poster)