Deep-learning-aided dismantling of interdependent networks

1 Introduction

• Existing centrality heuristics lack global optimization and performance guarantees, while earlier learned policies focus on single-layer networks.Prior machine-learning strategies were trained on exact solutions for small synthetic Barabási–Albert networks.Source: §1 · p. 1
• Damage to nodes in one layer can trigger cascading failures in other layers, so dismantling an interdependent network cannot be solved by analyzing its layers in isolation.The passage cites the Italy blackout and COVID-19 supply-chain disruptions as examples of cascading effects.Source: §1 · p. 2
• MultiDismantler uses a graph convolutional network with flexible node-level inter-layer attention and an n-step Deep Q-Network to learn dismantling strategies.Its training corpus is generated from small synthetic networks using the Geometric Multiplex Model, which represents cross-layer interactions and correlations.Source: §1 · p. 2
• MultiDismantler aligns with brute-force optimal node sets and outperforms single-layer adaptations in immunization and network-collapse applications.It is trained on small synthetic multiplex graphs and performs across real-world networks with arbitrary node-removal costs.Source: §1 · p. 2
• The authors apply MultiDismantler to immunization strategies in multilayer social networks and to mitigating collapse in interdependent networks.In both applications, it outperforms dismantling algorithms adapted from single-layer networks.Source: §1 · p. 2

2.1 Dismantling interdependent networks

• The study evaluates fragmentation by tracking LMCC against removal cost and uses AUDC and normalized dismantling cost C∗ to assess sequence quality.It treats the LMCC as non-extensive when it falls below the square root of its original size.Source: §2.1 · p. 2

2.2 Proposed approach to the dismantling of interdependent networks

• MultiDismantler combines a synthetic-network training approach with multiplex representation learning and deep reinforcement learning for interdependent-network optimization.The proposed approach emphasizes preserving intra- and inter-layer structure in learned representations.Source: §2.2 · p. 3
• The agent uses node embeddings as removal actions, a virtual-node embedding as the state, and LMCC decrease as reward, then updates its predictions as the network changes.Its n-step DQN is designed to capture the longer-term influence of removals.Source: §2.2 · p. 3, Figure 1 · p. 4

2.3.1 Performance on synthetic networks

• AUDC and C∗ are 7% and 10% lower than NIRM under unit cost, and 8% and 3.5% lower under degree cost.These are average differences across the tested synthetic networks.Source: §2.3.1 · p. 5

2.3.2 Predicting the ground-truth optimal dismantling sequence

• On the tested unit-cost network, MultiDismantler’s sequence matched the brute-force optimum and achieved the minimum dismantling AUDC.The optimum was computed by evaluating all node combinations, with full dismantling defined as an LMCC of one node.Source: §2.3.2 · p. 5

2.4.1 Dismantling performance and inductive learning capacity on real-world networks

• Across real-world multiplex networks, MultiDismantler outperforms other methods on average under both unit and degree removal costs.Its curves can begin higher and then decline more rapidly, consistent with a long-term strategy; it also performs best on unseen normal and Poisson costs after training with uniform costs.Source: §2.4.1 · p. 5

2.4.2 Analyzing the key components of MultiDismantler

• Removing inter-layer message passing worsens accuracy; changing GMM similarity has limited effect except at the extreme values g = 0 and g = 1.Training on BA networks performs significantly worse than training on GMM networks.Source: §2.4.2 · pp. 5–6

2.5 Application to the prevention of disease spreading and the attack-protect task in various real-world networks

• In multiplex social-network SIR tests, MultiDismantler-guided immunization reduces the number of people needed to suppress spread; its protection strategies also maintain robustness under targeted attacks and random failures.The protection protocol selects 1% of the initial network’s nodes at each iteration; the same strategy often achieves the highest LMCC at a given removal-cost fraction in the Sacchpomb network.Source: §2.5.1 · p. 6, §2.5.2 · p. 6, §2.5 · p. 6

3 Conclusions

• MultiDismantler outperforms existing state-of-the-art dismantling methods, and its sequences match brute-force optima on small networks.The approach uses multiplex embedding and a DQN-based decoder.Source: §3 · p. 6
• With the same number of removed nodes, MultiDismantler strategies yield consistently smaller disease outbreaks and a slight advantage in maintaining robustness.The robustness comparison concerns the Sacchpomb network under targeted attack and random failure.Source: Figure 5 · p. 9
• MultiDismantler generalizes across network topologies and node-removal cost distributions, including previously unseen networks.The authors also report its usefulness for disease-spreading prevention and infrastructure attack-and-protect tasks.Source: §3 · p. 10
• The work points to future research on improving the scalability and adaptability of graph neural networks combined with reinforcement learning.Source: §3 · p. 10

4.1.1 Problem formulation

• Random node costs are sampled from uniform, normal, or Poisson distributions, while degree cost sums removed-node degrees across layers and counts shared edges once.Unit cost is the number of removed nodes.Source: §4.1.1 · p. 11
• The objective is to find a minimum-cost node set that reduces the largest mutually connected component below 1/√NI in a two-layer network with one-to-one interdependence.Removal costs may be unit, degree-based, or random.Source: §4.1.1 · pp. 10–11

4.1.2 Approximating solutions of the network dismantling problem

• AUDC and normalized dismantling cost evaluate approximate solutions; both range from 0 to 1, with lower values indicating better performance.AUDC is approximated using contributions up to the point where the LMCC fraction reaches 1/NI.Source: §4.1.2 · p. 11

4.2.1 Encoder

• The encoder initializes node features from normalized degree, aggregates within-layer neighbor information, and uses node-level attention to integrate representations across layers.The inter-layer attention weights can be asymmetric, allowing influence from one layer to another without requiring the reverse influence.Source: §4.2.1 · pp. 11–12

4.2.2 Decoder

• The decoder combines node action vectors with a virtual-node representation of each layer’s current state, then attends across layer-level removal returns.The resulting Q-value represents the expected return for removing a node under the state of the whole network.Source: §4.2.2 · pp. 12–13

4.2.3 Loss Function and Dismantling Process

• Training combines Q-learning loss with graph reconstruction loss and uses n-step targets to capture delayed effects of node removal on connectivity.The reconstruction-loss weight balances the two losses.Source: §4.2.3 · p. 13
• During application, MultiDismantler repeatedly removes the remaining node with the highest Q-value until no macroscopic LMCC remains.Training selects the highest-Q action with probability 1−ε and otherwise explores randomly.Source: §4.2.3 · p. 13

4.3.1 High degree adaptive (HDA); 4.3.2 Collective Influence (CI)

• HDA removes the highest-degree node with scores updated after each removal, while CI ranks by distance-v neighborhood degree information and also updates scores.The reported CI setting uses v = 1 and the maximum score across the two layers.Source: §4.3.1 · p. 14, §4.3.2 · p. 14

• W.W. and F.R. wrote the paper; W.W., C.Y., and F.R. designed the model and experiments; W.W., C.Y., and L.L. performed experiments; C.Y., L.L., and J.H. plotted figures.Source: Author contributions statement · p. 16

• All data used in the paper are publicly available at the Code Ocean capsule.Source: Data availability statement · p. 16

1.1 Differences

• MultiDismantler trains on GMM-generated multiplex networks with realistic cross-layer correlations, unlike FINDER’s single-layer synthetic training data.The passage attributes FINDER’s reduced ability to capture interdependent-network dependencies partly to the absence of GMM training data.Source: §1.1 · p. 18, §1.3 · p. 18
• Its Multiplex Graph Neural Network combines intra-layer graph convolution with node-level inter-layer attention to represent both within-layer structure and cross-layer interactions.Source: §1.1 · p. 18
• MultiDismantler dynamically fuses node scores across layers, whereas FINDER’s multilayer generalization scores each layer independently.Source: §1.1 · p. 18

1.2 Similarities

• Both methods use virtual nodes to encode network state, reconstruction loss to preserve topology, and a cross product to model state-action dependencies.Source: §1.2 · p. 18

1.3 Experimental Comparison

• With the same reward mechanism, FINDER performed significantly worse than MultiDismantler, and the comparison identifies architectural differences as part of the performance gap.The table compares AUDC; its caption states that bold marks the lowest values.Source: Table 1 · p. 18, §1.3 · p. 18

2.1 Dataset statistics

• Networks are treated as undirected and unweighted; analyses generally select the two layers with the most edges, or the largest layer for single-layer analyses.Source: §2.1 · p. 19
• The transportation and trade datasets represent airports linked by flights across airline layers and countries linked by food-product trade layers, respectively.Source: §2.1 · p. 19
• Biological datasets encode genetic and protein interactions, while Facebook&Twitter, NetSci co-authorship, and Sanremo2016 capture social contacts, research collaboration, and Twitter interactions.The biological networks use genes or proteins as nodes; NetSci layers are arXiv categories, and Sanremo2016 includes retweets, mentions, and replies.Source: §2.1 · p. 19
• Supplementary Table 2 is identified as reporting statistical properties of the real-world networks.Source: Table 2 · p. 19

2.2 Model Parameters

• Supplementary Table 3 lists the model hyper-parameter settings.Source: Table 3 · p. 20

3.1 Ablation study on factors influencing MultiDismantler’s performance

• The ablation study includes three tests of essential components, including an ablation on inter-layer attention.Source: Table 4 · p. 20, §3.1 · p. 20

3.2 Performance on other layers in real-world multiplex networks

• The other-layer comparison covers the two layers with relatively more edges and the two with relatively fewer edges in each real-world multiplex network.Source: Table 5 · p. 21

3.3 Sequence consistency between MultiDismanlter and the optimal dismantling sequence

• The brute-force comparison evaluates dismantling-sequence consistency using AUDC and 1 − NED, with synthetic networks ranging from 10 to 30 nodes.The table reports the first n nodes of each solution, where n is the optimal sequence length.Source: Table 6 · p. 22, Figure 1 · p. 23

3.4 Dismantling performance under more cost scenarios of real-world networks

• The real-world cost-scenario comparison covers Random, Normal, and Poisson removal costs on the two layers with the most edges.Source: Table 7 · p. 24

3.5 Dismantling performance on single-layer networks

• On single-layer tasks, the multiplex-trained MD outperforms all comparison algorithms; removing inter-layer attention or replacing GMM training data with BA networks worsens performance.The BA-trained variant shows a significant drop; the study attributes MD’s superior performance primarily to inter-layer components.Source: §3.5 · pp. 24–25

3.6 Dismantling performance of single-layer algorithms using aggregated scores

• MultiDismantler achieves the overall best performance against single-layer algorithms using aggregated or maximum layer scores.FINDER and NIRM show no significant improvement with aggregation, and NIRM declines on USAir and Celegans.Source: §3.6 · p. 25, Table 9 · p. 25

• On a 15-node synthetic network, MultiDismantler removes bridge node 3 at step two, splitting the network into parts of 5 and 6 nodes, while HDA leaves a 13-node LMCC.Both algorithms first remove node 9.Source: Figure 2 · p. 26
• On the 16-node Padgett-Florentine Families network, MultiDismantler reduces the LMCC to 6 nodes after step one and 4 after step two, versus HDA’s 9 and 5.Source: Figure 3 · p. 27
• A separate figure depicts dismantling processes on real-world multiplex networks under unit costs.Source: Figure 4 · p. 28

• Supplementary Tables 10 and 11 report synthetic multiplex dismantling performance under unit and degree costs, respectively.The captions identify lowest AUDC and C* as the best results.Source: Table 10 · p. 29, Table 11 · p. 30
• Supplementary Table 12 reports real-world multiplex performance under unit and degree costs.Its caption identifies the lowest AUDC and C* as the best results.Source: Table 12 · p. 31

6 MGNN Framework

• MGNN combines feature initialization, intra-layer message propagation, layer projection, and inter-layer information aggregation.Source: Figure 5 · p. 32
• Within each layer, graph convolution updates node embeddings using their local neighborhood structure.Source: Figure 5 · p. 32
• Across layers, attention aggregates node embeddings to capture both intra-layer and inter-layer structural information.Source: Figure 5 · p. 32