PaperlayerView exact revision on arXiv

Source-linked AI summary

TANGCO: Learning Topology-Aware Capacity Allocation for Overload-driven Cascading Failures

Orkun Irsoy, Leman Akoglu, Osman Yagan

arXiv:2608.13212v1cs.LGcs.SI

TL;DR

The paper asks how to allocate a fixed capacity budget against overload cascades when local redistribution makes optimal allocations unknown and the objective non-differentiable. It introduces TANGCO, a GNN policy trained through cascade simulation, and reports consistent gains over hand-designed heuristics across synthetic and real networks. The analysis also identifies when local-risk rules suffice and when topology-aware learning remains necessary.

  • Problem

    Under local load redistribution, no optimal capacity allocation is known, while hard overload thresholds make robustness non-differentiable and piecewise constant.

  • Method

    TANGCO uses a graph neural network policy with simulator-based REINFORCE rewards and a heuristic anchor to allocate capacity under a fixed budget.

  • Results

    TANGCO outperforms four competitive heuristics across the evaluated synthetic and real-network settings, while TANGCOpre transfers to unseen real networks without per-target training.

  • Takeaways & Limitations

    Learned allocations reveal when local-risk structure is sufficient, produce an improved closed-form heuristic in those regimes, and retain a role for GNNs elsewhere.

  • Takeaways & Limitations

    The residual parameterization restricts search to softmax perturbations of a chosen anchor, motivating improved anchors and less anchor-tied parameterizations.

Abstract

from arXiv · show

Networked systems, from power grids to traffic networks and cloud clusters, carry loads across nodes with limited capacity. A node whose load exceeds its capacity fails and sheds its load onto its neighbors, which can trigger a system-wide cascade. We study how to allocate a fixed capacity budget across nodes to resist these cascades under local load redistribution. The problem is difficult because no optimal allocation is known, and the fail-or-survive objective is non-differentiable and piecewise constant, so exact and gradient-based optimization methods do not directly apply. We introduce TANGCO (Topology-Aware Neural Graph-Guided Capacity Optimization), which uses a graph neural network policy trained through the cascade simulator with policy-gradient learning and a heuristic anchor. We evaluate TANGCO on five synthetic graph families and five real networks spanning power, road, air, and Internet topologies. The learned policy improves on the best of four hand-designed heuristics in all 450 synthetic instances and in 40 of 45 real-network conditions, with robustness gains ranging from 1.6% to 246%. The learned policies transfer to unseen graphs within a family and partially across related topologies, and TANGCO$^{pre}$, pre-trained on synthetic graphs, matches per-network training on unseen real networks. Training scales near-linearly with graph size, and TANGCO$^{pre}$ allocates on a new network with no per-target training, matching the deployment cost of a hand-designed heuristic. Free-vector variants without the GNN, stay close to the heuristics, so the graph representation carries the gain beyond numerical search. Finally, analysis of the learned allocations identifies when local risk is sufficient, leads to an improved closed-form heuristic, and reveals the regimes where a topology-aware learned policy remains necessary.

1 Introduction

Networked systems can undergo overload-driven cascades because failed nodes redistribute load through dependency networks. TANGCO addresses the underexplored problem of allocating a fixed capacity budget under local redistribution by learning topology-aware allocations from cascade dynamics.

  • Overloaded nodes can shed load to neighbors, triggering further failures and potentially system-wide collapse across cloud, power, transportation, supply-chain, and financial networks.
  • Network topology interacts with node capacities to shape cascade dynamics, making capacity allocation critical for robustness.
  • Capacity allocation under local redistribution is less studied than robustness-oriented network modification, and prior allocation work largely assumes topology-independent global redistribution.
  • TANGCO uses a graph neural network to learn capacity allocations directly from cascade dynamics for a given graph and initial-load vector.
  • Across five graph families, multiple load distributions and budgets, and five real networks, TANGCO consistently outperforms four competitive heuristics while scaling linearly with graph size.
  • TANGCOpre transfers from synthetic graphs to unseen real networks without per-target training and provides the best reported latency–performance trade-off.

2 Problem Formulation

The paper models overload cascades as iterative local load redistribution and evaluates capacity allocations by aggregated survival across initial failure sizes. A fixed budget, discrete cascade dynamics, and a step-like non-concave objective make the allocation problem simulation-based and difficult for conventional optimization.

  • 2 Problem Formulation: Each node has an initial load and capacity, with capacity determining the maximum load it can carry before failure.
  • 2.1 Cascade Dynamics: A cascade removes an initial failure set, redistributes its load, and repeatedly checks surviving nodes until no new failures occur.
  • 2.1 Cascade Dynamics: A node fails when its current load exceeds capacity, releasing that load for redistribution.
  • 2.1 Cascade Dynamics: Each failing node splits its current load equally among active neighbors, while failures in one iteration resolve simultaneously.
  • 2.1 Cascade Dynamics: A cascade costs O(Nt̄ + E), because each node fails at most once and redistribution touches each edge once.
  • 2.2 Capacity Allocation Problem: The allocation problem chooses nonnegative free space under a fixed total capacity budget, with capacities defined as c_v = ℓ_v + s_v.
  • 2.2 Capacity Allocation Problem: Robustness averages final survival over initial failure sets of a given size and aggregates those averages across evaluated failure sizes into AUC.
  • 2.2 Capacity Allocation Problem: The evaluation uses uniform weights for failure fractions in [0, 0.5], emphasizing low-to-moderate failures and excluding targeted-removal objectives.

3 Proposed TANGCO

TANGCO learns topology-aware, budget-feasible capacity allocations with a GNN policy trained through cascade-simulator rewards. It combines residual corrections around heuristic anchors with Monte Carlo AUC evaluation and REINFORCE optimization despite non-differentiable cascade dynamics.

  • Node Features and GNN Policy: TANGCO uses a message-passing GNN to map graph and load features to feasible capacity allocations, sharing parameters across nodes and aggregating multi-hop information.The policy output is projected onto the budget simplex, and residual connections help avoid oversmoothing.
  • Residual Softmax Allocation: The policy learns residual corrections around uniform or LR-FSA anchor allocations, which provide a reasonable starting point and reduce the noise of high-dimensional search.Uniform allocation is a global-redistribution baseline, while LR-FSA allocates free space in proportion to one-hop local risk.
  • Residual Softmax Allocation: Every sampled allocation remains budget-feasible because the residual logits are added to anchor logits before softmax projection onto the budget simplex.At initialization, zero GNN residuals recover the anchor allocation; training then learns topology- and load-dependent adjustments.
  • Simulator-Based Reward: The simulator estimates robustness with Monte Carlo survival samples over failure fractions, using empirical AUC as the reward while sharing pre-sampled failure sets across allocations.The AUC aggregates survival across a finite failure-fraction grid and is the empirical counterpart of the weighted robustness objective.
  • Simulator-Based Reward: On a representative ClusPowL instance, TANGCO maintains high survival to roughly twice the failure fraction tolerated by the heuristics, producing a larger AUC.Figure 3 compares survival fraction against failure fraction under uniform load at B = 0.5.
  • Non-differentiable Optimization: REINFORCE optimizes expected empirical AUC through score-function gradients because threshold failures and discrete redistribution rounds make the simulator non-differentiable.A batch-mean baseline reduces estimator variance, while periodic deterministic evaluation uses σ = 0.

4 Experiments

TANGCO is evaluated across diverse synthetic and real network topologies, load distributions, budgets, transfer settings, scalability conditions, and ablations. It consistently improves robustness over heuristics, transfers to related graphs, scales near-linearly, and shows that message passing and higher-order structure account for gains beyond numerical search.

  • Experimental setup: The evaluation spans five synthetic graph families, five real networks, three load distributions, and nine load-budget conditions.The real networks cover power, road, air-transport, and Internet domains; budgets are B/Σ_v l_v ∈ {0.5, 0.75, 1.0}.
  • Overall performance: TANGCO improves on the best heuristic in all 450 synthetic cells and 40 of 45 real-world conditions, with gains from +1.6% to +246%.The five exceptions occur at the tightest budget on spatially embedded networks, where no allocation survives even p≈0.01.
  • Transferability: Within-family transfer is positive on all five families and matches per-instance training within about ±0.002 AUC, while cross-family transfer is strongest among structurally similar families.Policies are trained on eight realizations and evaluated on two held-out realizations per family.
  • Transferability: TANGCOpre reaches mean AUC 0.18 on five real networks without target updates, matching per-instance training and improving over the best heuristic’s 0.12 by about 1.5× on average.It improves on four of five real networks under uniform load and operates at heuristic deployment cost.
  • Scalability: Training scales near-linearly with network size, with fitted exponents between 0.97 and 1.10 across synthetic families up to 40,000 nodes.The cascade simulator dominates computation, while the GNN remains under 2% of runtime; pretrained deployment requires one forward pass.
  • Ablations and gain characterization: TANGCO beats No-GNN in all 10 uniform and all 10 Pareto cells, while one message-passing hop is sufficient and deeper models remain flat.No-GNN has mean ΔAUC −0.001 under uniform load and +0.002 under Pareto; CMA-ES gains more but remains below TANGCO on hub-heavy graphs.
  • Ablations and gain characterization: Gains are largest on heterogeneous topologies at intermediate budgets, while local risk explains allocations in regime A but higher-order or nonlinear structure is needed elsewhere.Local risk alone reaches R^2 ≥ 0.90 in regime A; nonlinear fits reach 0.82–0.98 on extreme-hub Oregon AS and AS1221, where T-LR falls below the best heuristic.

5 Related Work

Prior cascading-failure research largely analyzed propagation or optimized capacities under global redistribution. TANGCO addresses the less-explored problem of capacity allocation under topology-dependent local redistribution and a non-differentiable cascade objective.

  • Cascading failures: Most cascading-failure studies analyze propagation mechanisms, while fewer treat capacity allocation as an optimization variable.Existing allocation analyses include power systems, redundancy allocation, targeted attacks, and multiplex networks.
  • Cascading failures: Earlier allocation methods assume global redistribution, where failed loads spread equally across surviving nodes regardless of topology.This assumption supports closed-form analyses and optimality guarantees, unlike local redistribution.
  • Learning for graph problems: Graph-learning methods commonly optimize differentiable objectives or relaxations, whereas TANGCO handles a piecewise-constant, non-differentiable fail-or-survive objective.Related work also applies reinforcement learning to cascade prediction or mitigation rather than capacity allocation.

6 Conclusion

The paper presents TANGCO as both a topology-aware capacity-allocation method and an analysis tool for extracting simpler principles from local cascade dynamics. Its pretrained variant extends deployment to unseen real networks without per-network training.

  • Conclusion: TANGCO improves robustness when local redistribution creates a non-differentiable objective and no analytical allocation rule is available.The framework uses learned allocations while also analyzing when local risk is sufficient or incomplete.
  • Conclusion: Allocation analysis produces Tuned Local-Risk, which improves the original heuristic where its rule applies, while identifying regimes requiring a GNN.The conclusion distinguishes simpler representable regimes from those needing additional or nonlinear structure.
  • Conclusion: TANGCOpre transfers from synthetic graphs to unseen real networks at the deployment cost of a hand-designed heuristic.The paper positions this pretrained model for settings without per-network training.
  • Conclusion: Future work includes domain-specific redistribution models and graph-adaptive anchor selection from features alone.These directions are stated as extensions of the framework.

A.2 Network Data

The evaluation uses canonical synthetic families, structurally varied synthetic training graphs, and five real networks spanning diverse topology types. TANGCO represents each node with local load, neighborhood, and two-hop structural features processed by a residual message-passing GNN.

  • Network data: Synthetic evaluation fixes one canonical setting per topology, while the curated training suite varies graph structure across size, density, and family parameters.The training suite contains 64 graphs from ER, PowL, CorPer, and RandGeo families.
  • Network data: The five real networks span power-grid, autonomous-system, road, airport, and router topologies.They range from low-degree, long-path networks to extreme-hub systems.
  • Network data: Loads include uniform, heavy-tailed Pareto, and bimodal distributions representing different forms of heterogeneity.Pareto loads place much larger loads on a small number of nodes, while bimodal loads separate high- and low-load groups.
  • Node features: Each node is represented by six log-transformed features covering own load, degree, one-hop neighbor-load statistics, and two-hop degree.The features capture steady neighborhood inflow, spikes from failing hubs, and potential second-round spread.
  • GNN policy: The policy uses a GraphSAGE-family GNN with sender-degree-normalized mean aggregation and residual updates.The normalization parallels local load redistribution, while residual connections mitigate oversmoothing.

A.5 Reward Estimation and Training

Training estimates cascade robustness on a selected failure-fraction grid using shared sampled failure sets, then optimizes sampled allocations with REINFORCE and regularization toward an anchor. The implementation uses fixed sampling and optimization settings, with scientific claims reviewed by the authors.

  • Reward estimation: The reward grid spans the region where the anchor’s survival curve transitions from intact to collapsed.Failure fractions outside this band provide weak separation and add variance without useful signal.
  • Reward estimation: For each failure fraction, uniformly sampled initial failure sets are pre-sampled so allocations in a batch face identical failure conditions.This makes within-batch reward comparisons use shared failure sets.
  • Policy gradient: REINFORCE uses the simulator only through scalar AUC rewards, with gradients passing through sampled residual-logit log-probabilities.A batch-mean baseline reduces the policy-gradient variance.
  • Policy gradient: An L2 penalty keeps residual logits near the anchor and stabilizes policy-gradient updates.The regularizer is applied alongside the baselined policy-gradient term.
  • Implementation: Training uses 200 Adam iterations, 32 sampled allocations per iteration, and 32 failure samples per fraction on a 41-point grid.The exploration scale is annealed from 0.3 to 0.1, with λ=10^-4 residual-logit regularization.

B Additional Results and Analyses

TANGCO’s two-anchor design improves robustness across synthetic and real networks, while transfer experiments show strong within-family generalization and partial cross-family transfer.

  • B.1 Anchor Selection: Keeping both anchors recovers the strongest allocation when one heuristic collapses, as on Oregon AS under Pareto load.LR-FSA collapses while Uniform holds at B=0.5, so optimizing over both anchors recovers the strongest allocation.
  • B.1 Anchor Selection: LR-FSA anchors the winning policy across synthetic families, while Uniform wins in several tight-budget and hub-heavy real-network conditions.LR-FSA typically wins 10/10 synthetic realizations; Uniform wins all CorPer cases at B=0.5 and all nine conditions on Oregon and AS1221.
  • B.2 Transferability: TANGCOpre is trained on 64 synthetic graphs without seeing test graphs or real networks, then applied to held-out targets without retraining.Pre-training uses 6,400 iterations versus 200 for per-instance training because one policy fits many graphs jointly.
  • B.2 Transferability: Within-family transfer remains positive under Pareto load and reaches within 0.001 AUC of per-instance training on four of five families.Cross-family transfer improves on the target heuristic in 14 of 20 cells under Pareto load.
  • B.2 Transferability: Under Pareto load, cross-family transfer improves on the target heuristic in 14 of 20 cells, with failures concentrated among structurally dissimilar family pairs.The reported failures involve transferring policies between heavy-tailed, spatial, and core-periphery families.
  • B.2 Transferability: Shared within-family training exceeds per-instance training by 0.010 AUC under uniform load but trails by 0.010 AUC under Pareto load.The direction of this difference changes with the load distribution.

B.3 Scalability Details

Training cost is dominated by cascade simulation rather than the GNN, and scaling is near-linear for fixed-mean-degree synthetic families but depends on cascade depth in real networks.

  • B.3 Scalability Details: Cascade simulation costs O(N t̄ + E), whereas each GNN layer costs O(Eh + Nh^2) for K message-passing layers of width h.At K=3 and h=64, GNN computation is negligible beside approximately 8.4 million cascade simulations per run.
  • B.3 Scalability Details: Over 94% of training time is spent in cascade simulation, while GNN forward and backward passes take under 2%.A 200-iteration run takes 24–50 minutes at 40,000 nodes on 16 CPU cores and under nine minutes on every evaluated network.
  • B.3 Scalability Details: Synthetic-family training time follows edge count near-linearly because fixed mean degree makes |E| proportional to N.Figure 6 presents median training time against |E| on a log–log scale over graphs up to 40,000 nodes.
  • B.3 Scalability Details: TANGCOpre reaches near-instance robustness at heuristic deployment cost on both uniform and Pareto loads.The deployment comparison separates no-per-target-training methods from methods retrained for each target.
  • B.3 Scalability Details: Failure-set simulations and sampled allocations are independent, allowing parallel evaluation and leaving additional parallelism available.Failure sets are currently parallelized, while sampled allocations and failure fractions are evaluated sequentially.
  • B.3 Scalability Details: US grid and AS1221 sit above the edge-count trend because deeper cascades inflate the O(N t̄) simulation term.Edge count alone therefore does not explain real-network training time.

B.4 No-GNN Ablation

Removing message passing leaves reward-driven search close to heuristic performance, while TANGCO’s advantage appears when the policy can use graph structure.

  • B.4 No-GNN Ablation: The No-GNN ablation replaces the GNN with a free per-node residual logit while retaining the same residual-softmax allocation head.Residual logits are zero-initialized so the initial deterministic allocation matches the training anchor.
  • B.4 No-GNN Ablation: No-GNN and TANGCO use the same REINFORCE loop, schedules, exploration, regularization, sampling budget, two anchors, and five seeds.The ablation covers all ten networks, with one realization per synthetic family.
  • B.4 No-GNN Ablation: TANGCO beats the No-GNN variant in all 20 family-load cells, while No-GNN stays close to the best heuristic.The comparison uses AUC at B=0.75 across five synthetic families and two load distributions.
  • B.4 No-GNN Ablation: The depth sweep evaluates K∈{0, ..., 5} to isolate gains from message passing beyond each anchor’s contribution.Relative improvement is measured against each anchored policy’s own anchor.
  • B.4 No-GNN Ablation: The K=0→K=1 improvement is large under Uniform but small under LR-FSA because LR-FSA already carries one-hop structural signal.Uniform provides no structural signal, whereas LR-FSA supplies a local-risk-based starting allocation.

B.6 Per-Cell Fits for the Regime Map

The learned allocation follows local risk in some regimes, requires additional structure in others, and changes regime with topology, load, and budget jointly.

  • B.6 Per-Cell Fits for the Regime Map: Cells are omitted when the policy remains at its anchor and leaves no learned allocation to explain.At B=0.5, these omissions correspond to the feasibility floor described in Section 4.6.
  • B.6 Per-Cell Fits for the Regime Map: Eight of nineteen cells change regime when budget changes while graph and load remain fixed.This supports attributing regimes jointly to topology, load, and budget rather than topology alone.
  • B.6 Per-Cell Fits for the Regime Map: Regime-A power-rule exponents range from 0.57 to 1.10, so T-LR fits an exponent separately for each graph.Risk and degree are correlated at 0.61–0.77, motivating separate single-feature fits in Figure 8.
  • B.6 Per-Cell Fits for the Regime Map: Local risk alone explains the allocation on ten of nineteen cells, while degree closes much of the remaining gap.The regime map uses nested R^2 fits that add local features cumulatively.
Loading 2608.13212v1…