CS Paper Radar

Deep-learning-aided dismantling of interdependent networks

Weiwei Gu, Chen Yang, Lei Li, Jinqiang Hou, Filippo Radicchi

cs.SI physics.soc-ph ·submitted 2026-09-24 03:44 UTC · v1
top venuehighly cited

Abstract

Identifying the minimal set of nodes whose removal breaks a complex network apart, also referred as the network dismantling problem, is a highly non-trivial task with applications in multiple domains. Whereas network dismantling has been extensively studied over the past decade, research has primarily focused on the formulations of the optimization problem for single-layer networks, neglecting that many, if not all, real networks display multiple layers of interdependent interactions. In such networks, the optimization problem is fundamentally different as the effect of removing nodes propagates within and across layers in a way that can not be predicted using a single-layer perspective. Here, we propose a dismantling algorithm named MultiDismantler, which leverages multiplex network representation and deep reinforcement learning to optimally dismantle multi-layer interdependent networks. MultiDismantler is trained on small synthetic multiplex graphs; when applied to large, real and synthetic networks, it displays exceptional dismantling performance, clearly outperforming all existing methods that rely on a single-layer approach to network dismantling. We show that MultiDismantler is effective in guiding strategies for the containment of diseases in social networks characterized by multiple layers of social interactions. Also, we show that MultiDismantler is useful in the design of protocols aimed at delaying the onset of cascading failures in interdependent critical infrastructures.

Comment
32 pages including 16-page Supplementary Information; 5 main-text figures
Journal ref
Nature Machine Intelligence 7, 1266-1277 (2025)
DOI
10.1038/s42256-025-01070-2

Closest papers

Nearest neighbours by meaning across the whole index.

NetBreaker: Benchmarking Network Dismantling across Objectives, Scales, and Toplogoies

cs.LG ·2026-11-14 ·Wenchuan Yang, Tianci Bu, Suoyi Tan, Changjun Fan, Zijie Zhou +1 more
benchmark similarity 0.61
Abstract

Network dismantling seeks to fragment a network with as few node removals as possible, which is widely applied in vulnerability analysis, epidemic containment, and infrastructure protection. Although learning-based methods have become increasingly prominent, their progress remains difficult to assess because existing studies differ in method coverage, datasets, evaluation criteria, and experimental protocols. Thus, we introduce NetBreaker, a comprehensive benchmark designed for the learning era of network dismantling. NetBreaker organizes 30 methods (18 non-learning and 12 learning-based) under a common taxonomy and evaluates them on 185 networks from eight unified domains, ranging from 14 to 1.69 million nodes. To enable fair comparison, heterogeneous method outputs are converted into node removal sequences and assessed under a unified execution protocol. The evaluation covers four complementary dimensions: target-based effectiveness, trajectory-based effectiveness, structural diagnostics, and applicability & computational efficiency. Extensive experiments show that current learningbased methods do not consistently outperform strong non-learning approaches, while exposing substantial differences in effectiveness, scalability, and efficiency across network conditions and evaluation perspectives. NetBreaker provides a reproducible basis for measuring progress and developing reliable, scalable, and computationally efficient network dismantling methods.

0.23

A Network Science Perspective on Evaluating Deep Graph Generative Models

cs.SI cs.AI ·2026-09-01 ·Tianrui Mao, Abele Malan, Megha Khosla, Lydia Chen, Huijuan Wang
similarity 0.58
Abstract

Traditional network models from network science, such as the Erdos-Renyi and configuration models, generate random networks that reproduce few selected topological properties observed in real-world networks. Deep graph generative models emerge as a data-driven approach, leveraging deep neural network architectures to learn complex structural distributions directly from real-world networks to generate more realistic synthetic networks. Because real social contact networks cannot be shared due to privacy risks, synthetic networks serve as an alternative for developing and evaluating epidemic mitigation strategies. In this work, we evaluate deep graph generative models as well as the configuration from a network science perspective by assessing both the topological similarity between generated and real-world networks and their utility in identifying effective node immunization strategies to sup- press epidemic/misinformation spreading. It is found that two deep graph generative models produce synthetic networks that closely resemble the structural properties of real-world networks, enabling them to identify effective immunization strategies.

0.15

Effective Resistance and Graph Neural Network Reliability in Tissue-Specific Interactomes

cs.LG q-bio.MN ·2026-10-01 ·Jianru Shen
similarity 0.57
Abstract · Accepted at IEEE BIBM (Doctoral Forum)

Protein function annotation needs to know which predictions to distrust, not only what a model predicts. We ask whether tissue-specific interaction structure carries that information. Our candidate signal is effective resistance, used previously to relieve over-squashing by rewiring. Across 24 tissue-specific interactomes it is dominated by inverse degree, and the degeneration deepens as the co-expression filtered network grows, with a Spearman correlation of -0.955. The residual departure from that limit exceeds degree-preserving null graphs in all 24 networks. Controlling for predictive entropy, degree, annotation cardinality, local structure and feature-only difficulty, the residual explains additional per-node loss in 19 of 24 held-out networks once a permutation floor is subtracted, at every depth, and the effect strengthens monotonically with depth. The increment reaches 0.37% of the variance the controls leave unexplained, 5.6 times a permutation floor, against 1.5 times when the model is retrained in a degree-preserving null world. Selective prediction improves negligibly. The signal is reproducible; degree degeneration bounds it.

0.31

Target-Aware Network Dismantling with Limited Budgets

cs.SI ·2026-10-06 ·Jiaqi Song, Fei Jing, Wenjie Huang, Xingqin Qi, Qingpeng Zhang
similarity 0.57
Abstract

During epidemics, limited resources dictate critical decisions about whom to isolate or monitor. Conventional public health strategies intuitively prioritize known infected individuals and their immediate contacts. Here, we reveal that this contact-centric approach is fundamentally suboptimal under realistic resource constraints. By formulating this challenge as target-aware network dismantling, we uncover a counter-intuitive, budget-dependent intervention transition. Generating-function analysis demonstrates that when intervention budgets are scarce, isolating structurally central individuals, rather than the immediate neighbours of the infected, protects a vastly larger population. The conventional neighbour-targeting strategy only becomes optimal as available resources increase. Because this critical transition point shifts dynamically with the intervention budget, network topology, and spatial distribution of infections, static strategies inevitably fail. To overcome this, we develop Risk-Aware Isolation Learning (RAIL), a deep reinforcement learning framework that adaptively selects optimal interventions based on the evolving residual network. Across diverse synthetic and real-world networks, RAIL consistently maximizes population protection and suppresses outbreak spread. Ultimately, our findings challenge prevailing epidemiological intuitions, establishing a generalizable framework for adaptive interventions against localized risks in public health and other complex systems.

0.23

Graph-dependent pooling: adaptive granularity in hierarchical graph neural networks

cs.AI cs.LG ·2026-10-24 ·Bohan Yoon, Hyejin Jang
similarity 0.57
Abstract

Graph Neural Networks are widely used to learn structural representations of relational data. Hierarchical graph pooling learns multi-level representations by progressively coarsening graphs; however, prior methods rely on predefined cluster numbers or fixed pooling ratios, limiting adaptability to individual graphs. We propose Graph-Dependent Pooling (GDPool), which dynamically determines pooling granularity for each graph. We analyze optimization conflicts among layer-wise objectives through gradient alignment, showing that independently supervised pooling levels can send conflicting gradients to shared parameters. GDPool uses self-attention to select graph-specific anchors representing structurally important nodes and constructs coarse graphs through soft node assignment. Experiments on metal-organic framework and molecular graph benchmarks show that GDPool consistently achieves the best predictive performance across all benchmarks. Evaluations using modularity and the effective number of clusters show that GDPool achieves consistently higher modularity than existing methods while the number of active clusters decreases monotonically with depth. Sensitivity analyses confirm stable behavior across hyperparameter and architectural choices.

0.13

MUGEN: Generating Unlearnable Graph Examples for Multiple Learning Tasks

cs.LG ·2026-09-01 ·Ziyan Liu, Chengshuai Zhao, Huan Liu
similarity 0.55
Abstract

Graph data across diverse domains can expose valuable relational information to unauthorized representation learning, creating a pressing need for protection against such misuse. Unlearnable examples offer a data-level defense by perturbing a training release so that models trained on it fail to generalize to clean data. Existing methods generate unlearnable graph examples for only a specified downstream task. Consequently, a release protected against one task may remain learnable for other plausible uses, including node classification, graph classification, and link prediction, which the data owner cannot anticipate. We introduce MUGEN, to our knowledge the first framework for generating unlearnable graph examples that jointly protect all enabled tasks. From one clean dataset, MUGEN produces a single feature-perturbed release that protects every enabled task through a shared GNN encoder and task-specific heads. We devise a Task-Aligned Separability Objective (TASO), which leverages task prediction and classwise separability to strengthen unlearnability and its transfer across GNN backbones and enabled tasks. We further introduce Type-Adaptive Perturbation (TAP), which tailors perturbation optimization to node-attribute type, with direct search over feasible hard flips that accept only loss-improving updates for discrete node attributes and customized gradient-based updates for continuous node features, thereby enabling strong unlearnability across both settings. Experiments across five benchmarks, four backends and three learning paradigms demonstrate that MUGEN generates transferable unlearnable graph examples across GNN backbones and all three tasks, and remains effective under adversarial training and data augmentation.

0.14

Criticality and universality in network dismantling

cs.SI physics.soc-phcond-mat.stat-mech ·2026-08-27 ·Lorenzo Cirigliano, Claudio Castellano, Minsuk Kim, Filippo Radicchi, Hanlin Sun
similarity 0.55
Abstract · 17 pages, 11 figures, 2 tables + supplemental material

Identifying the smallest set of elements whose removal dismantle a complex network, known as the network dismantling problem, is a fundamental task with many practical applications. Whereas network dismantling has been extensively studied over the past decade, most work has focused on developing efficient algorithms for large but finite networks. By contrast, the physics of the network dismantling process, namely how the network structural connectivity is affected by the removal of nodes or edges, remains largely unexplored in the thermodynamic limit. Here, we shed light on this understudied aspect of network dismantling by introducing an adaptive biased percolation process able to optimally dismantle a network. Through a systematic analysis of synthetic network models, we find that the proposed percolation process displays a universal phase transition, characterized by the abrupt and simultaneous disappearance of both the giant connected component and the largest 2-core, across networks with markedly different degree distributions. Simulations on real networks further support this universality, indicating that the physics of network dismantling is insensitive to a broad range of topological properties. Together, these results suggest that a topology-agnostic theory could be developed to explain the critical behavior of network dismantling.

0.26

Generating Intervention Hypotheses using Explainable Explanations on Graphs: G2I, a Two-Stage Greedy Framework

cs.LG cs.SI ·2026-08-24 ·Mulin Tian, Ajitesh Srivastava
top venue similarity 0.55
Abstract · 11 pages, 3 figures. Accepted at the 35th ACM International Conference on Information and Knowledge Management (CIKM 2026)

Real-world decision-making in public health and social science can greatly benefit from predictive models, yet translating predictions into effective interventions requires explaining the model behavior. While Graph Neural Networks (GNNs) are well-suited for modeling relational data, existing explanation methods largely operate at the node level and fall short of supporting actionable, network-level intervention design. Existing counterfactual GNN explainers, such as CF-GNNExplainer and CF$^2$, rely on continuous mask optimization over features and edges, which implicitly assume feasible edge manipulation, may allocate effort to immutable or non-actionable attributes, and incur substantial computational overhead. Further, the method of arriving at the explanation itself is difficult to explain to a domain specialist who is not an AI expert. Can simple methods generate good explanations? To explore this, we reframe counterfactual explanation as an intervention design problem. At the local level, we generate counterfactuals via a greedy search that directly identifies minimal, actionable changes to node features and neighbor-level conditions. We derive conditions under which the greedy search provides guarantees, and empirically show that these conditions are approximately met. These counterfactuals are converted into interpretable rules suitable for real-world intervention. At the network level, we formulate intervention selection as a Disjunctive Normal Form (DNF) coverage problem under a budget constraint, which is nondecreasing and approximately submodular, enabling a greedy algorithm with theoretical guarantees. Experiments on synthetic graphs and real-world suicide risk networks demonstrate that our approach produces scalable, cost-effective intervention strategies with significantly improved efficiency over mask-based counterfactual methods.

0.33