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

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

Abstract

Many 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 TANGCOpre, pre-trained on synthetic graphs, matches per-network training on unseen real networks. Training scales near-linearly with graph size, and TANGCOpre 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, trained by policy gradient or by CMA-ES, stay close to the heuristics, so the graph representation carries the gain beyond numerical search; the depth analysis shows most of it arises from one-hop information. 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

Modern online services run on clusters of servers that share a request load. When one server becomes overloaded, its share of the load shifts to the remaining servers; if their updated load with the addition exceeds their capacity, they fail in turn, triggering a cascade that can end in a system-wide collapse. Such overload-driven cascades are a well-documented cause of large-scale outages at major cloud providers. The same pattern is prevalent across many networked systems, including power grids, transportation and traffic networks, supply chains, as well as financial systems where the failure of one institution imposes losses on its counterparties and can push them into failure. In each case a node carries a load and fails when that load exceeds its capacity, and a failed node passes its load to other functioning nodes. The failure of a few components can therefore propagate through the network and bring down the system.

Cascading failures are due to network effects, where entities are connected through dependencies in a graph. The interaction between the graph topology and the capacity allocation of nodes therefore becomes critical in the cascade dynamics. Flow-based models of cascading failure originate with Motter and Lai, who take each node's load to be its betweenness centrality and set its capacity to a fixed multiple of that load, c = (1 + α)l. A large literature builds on this model to relate network structure to robustness and to add mechanisms such as dynamical recovery of failed nodes and heterogeneous rules for how a failed node's load spreads to its neighbors. Almost all work in this line fixes the allocated capacity in advance and studies the robustness that results. The capacity allocation is thus an input to the model rather than a quantity to be designed.

In this work, we treat capacity as a decision variable and address the problem of allocating a limited capacity budget across nodes to maximize robustness against cascading failures, a question that has received far less attention. The few works that study this allocation problem solve it under a global redistribution rule, where a failed node's load is shared equally among all surviving nodes, irrespective of graph topology. That assumption yields a closed-form characterization of the final system size, and its allocations carry optimality guarantees while treating the network as fully connected and discarding topology.

Under local redistribution, where loads pass only to immediate neighbors, cascade outcomes depend jointly on the topology and the initial load and capacity, and the global-redistribution guarantees no longer apply. Existing allocations for local redistribution are hand-designed heuristics rather than optimized methods. Hence, even though prior work has studied robustness extensively by analyzing and modifying network structure, the design question of how to allocate capacities on a given network and load remains far less explored. In contrast, we ask how to allocate a fixed capacity budget over a given network under local redistribution, where no optimal allocation is known.

We introduce TANGCO (Topology-Aware Neural Graph-Guided Capacity Optimization), which employs a graph neural network (GNN) to learn capacity allocations directly from cascade dynamics. Given a graph and its initial loads, TANGCO outputs a capacity allocation that satisfies a fixed capacity budget.

Our paper introduces four main contributions:

• Topology-aware capacity optimization: We cast capacity allocation as a topology-aware policy-learning problem and propose TANGCO to maximize robustness against cascading failures. Hard overload thresholds make the cascade objective piecewise-constant; TANGCO trains a GNN allocation policy from simulator AUC rewards with score-function updates, without differentiating through the discrete failures.

• Synthetic Pre-training and Transfer: We also introduce TANGCOpre, pretrained on diverse synthetic graph topologies and load distributions, and demonstrate strong transfer to unseen real-world networks.

• Effectiveness, Scalability, Speed: Across five graph families, three load distributions, three capacity budgets, and five real-world networks, TANGCO consistently outperforms four competitive heuristics. Training scales linearly with graph size, while TANGCOpre needs no per-target training, yielding the best latency–performance trade-off.

• Characterizing Gains: We show that message passing contributes consistently beyond direct numerical optimization, develop a one-hop rule that recovers most gains in specific regimes, and find that TANGCO's gains are largest on heterogeneous topologies at intermediate capacity budgets.

2. Problem Formulation

We study overload-based cascading failures on an undirected graph G = (V, E) with N = V nodes. Each node v ∈ V has an initial load lv and a capacity cv. The capacity is the maximum load that the node can carry before it fails. We write l = (lv)v∈V and c = (cv)v∈V for the load and capacity vectors.

2.1 Cascade Dynamics

Consider a fixed graph G, load vector l, capacity vector c, and initial failure set F0 ⊆ V. The cascade starts by removing the nodes in F0. The loads of these nodes are then redistributed to the remaining network. After this redistribution, the surviving nodes are checked for overload. The same procedure is repeated in discrete iterations t = 1, 2,... until no new node fails.

Let lv(t) denote the load carried by node v at iteration t. The capacity cv is fixed during the cascade. A node remains active at iteration t if its current load does not exceed its capacity, i.e., lv(t) ≤ cv. If this condition is violated, the node fails and releases its current load for redistribution.

Let Ft, At, and Nt(v) denote the nodes that fail at iteration t, the nodes still active at that iteration, and the active neighbors of a node v. A failing node v ∈ Ft splits its current load lv(t) equally among its active neighbors Nt(v); if it has none (Nt(v) = ∅), the load spreads equally over all active nodes so that the total load is conserved in the system. Failures within an iteration resolve simultaneously, so an active node u accumulates the shares of its failing neighbors along with its part of the global term gt:

lu(t+1) = lu(t) + Σ v∈Ft, u∈Nt(v) lv(t)/Nt(v) + gt, where gt = (1/At) Σ v∈Ft, Nt(v)=∅ lv(t).

This additional load may cause neighboring nodes to exceed their capacities, which can trigger further failures in later iterations. The cascade stops when an iteration produces no new failures. Let t* denote the stopping iteration. The set of nodes still active at t* is the survivor set S. Then, for fixed G, l, c, and F0, the final surviving fraction is Φ(G, l, c; F0) = S/N. We use this quantity as the robustness measure for a single cascade.

Computational Complexity: Each cascade is cheap: a node fails at most once, so redistribution touches each edge once, and each round tests surviving nodes against their capacities. A cascade halting after t̄ rounds costs O(N t̄ + E), with t̄ ≤ N in the worst case but far smaller in practice.

2.2 Capacity Allocation Problem

The cascade model above determines the survival outcome for any fixed capacity assignment. Next, we consider how to allocate a given total capacity budget across the nodes of a given input graph to maximize robustness.

2.2.1 Capacity Constraint. Because additional capacity is costly in practice, we fix a total capacity budget and treat the node capacities as the decision variables. With an unlimited budget, robustness is trivially maximized. We parameterize a node v's capacity as cv = lv + sv, where sv ≥ 0 is the excess capacity, or free space, assigned to node v before any initial failures. This parameterization rules out trivial initial failures and simplifies the notation. Rather than optimize over capacities subject to lv ≤ cv, we optimize over non-negative free space under a fixed budget on the total free space. Let s = (sv)v∈V denote the free-space vector. For a given free-space budget B, the feasible allocations are ΔB = s ∈ R+N: Σ v∈V sv = B. Thus, optimizing the capacity vector c is equivalent to choosing a free-space allocation s ∈ ΔB, with capacities given by cv = lv + sv.

2.2.2 Robustness Objective. The fraction Φ(G, l, s; F0) measures robustness against one fixed initial failure set, F0. To evaluate an allocation for failures of a given size, let Fk = F0 ⊆ V: F0 = k be the collection of all initial failure sets containing exactly k nodes. The exact average survival fraction under k initial failures is Jk(G, l, s) = (1 / (N choose k)) Σ F0∈Fk Φ(G, l, s; F0). This is a finite average over the initial failure sets of size k. Weighting the members of Fk equally evaluates expected survival under uniformly random initial failures; targeted removal calls for a worst-case rather than an average-case objective and lies outside our scope. To obtain a single robustness score across failure sizes, we aggregate the average survival fractions over a set of failure sizes K ⊆ 0,..., N: AUC(G, l, s) = Σ k∈K wk Jk(G, l, s), where wk ≥ 0 and Σ k∈K wk = 1. The weights specify how much emphasis is placed on different failure sizes. Plotting Jk against the failure fraction p = k/N traces the survival curve J(p), and with uniform weights the objective is the discretized area under that curve, hence the name AUC. In our experiments we place uniform weight on failure fractions p ∈ [0, 0.5] and zero weight outside this range. This range focuses the evaluation on low-to-moderate failure fractions, where robustness depends strongly on how the cascade propagates after the initial failures, while keeping the same evaluation criterion for all methods.

Then, given an input graph G and budget B, the capacity allocation objective is max s∈ΔB AUC(G, l, s).

2.2.3 Why the Optimization is Difficult. Although the feasible set ΔB is simple, the objective in (8) is not. Each node's survival is set by a hard overload threshold, so the outcome stays fixed as s varies until a threshold is crossed, then jumps. The objective AUC(G, l, s) is therefore step-like and non-concave: convex methods do not apply, and gradients are uninformative on flat regions and undefined at the jumps. Exact evaluation is also intractable: Jk(G, l, s) sums over (N choose k) initial failure sets, each requiring a full multi-round cascade. Because the outcome couples topology, load and capacity, and the location and order of failures, no closed-form characterization is available as in prior global-redistribution models, which motivates a simulation-based learning approach.

3. Proposed TANGCO

TANGCO combines a message-passing GNN policy with simulation-based reinforcement learning. For a fixed instance (G, l) and free-space budget B, the goal is to learn a policy that outputs an allocation s ∈ ΔB with high robustness. The pipeline works as follows: node features feed a GNN policy, whose output is projected onto the budget simplex as a feasible free-space allocation. The allocation can only be evaluated through the cascade simulator, whose hard failure thresholds and discrete redistribution steps make the robustness score non-differentiable. We therefore train the policy with REINFORCE: at each iteration, the algorithm samples candidate allocations, scores them using empirical AUC rewards, and updates the policy from these rewards.

3.1 Node Features and GNN Policy

The allocation depends on both the load vector and each node's local topology. We therefore use a message-passing GNN rather than learning N unrelated parameters. The GNN shares parameters across nodes and aggregates multi-hop information, which is useful since failures can propagate beyond one round. For each node v we compute a log-transformed feature vector xv from its own load, its degree, the mean, maximum, and variance of its one-hop neighborhood loads, and its two-hop degree. The GNN stacks K message-passing layers; its architecture follows GraphSAGE with mean aggregation, differing in two respects: messages are normalized by the sender's degree, in parallel with the load-redistribution mechanism where a failing node splits its load among its neighbors, and each layer adds a residual connection to its MLP update to avoid oversmoothing. A final linear map produces one scalar residual logit μθ,v per node, and we write μθ(G, X) = (μθ,v)v∈V for the vector of outputs. The output layer is zero-initialized, so the initial residual logits are exactly zero and the policy starts at the anchor allocation described next.

3.2 Residual Softmax Allocation

Directly searching over all allocations in ΔB is high-dimensional and noisy. We therefore learn a residual correction around a fixed anchor allocation: the anchor gives the policy a reasonable starting point, and the GNN shifts capacity from it using the graph and load features. Let sanchor ∈ ΔB be a fixed anchor allocation. We use two anchors in the experiments. The first is the uniform allocation, sv uniform = B/N. Beyond serving as an intuitive baseline, the uniform allocation is optimal under global redistribution, where the network is treated as fully connected, with extensions to partial load loss and max-load targeted attacks. The second anchor is a local-redistribution heuristic. Irsoy and Yağan allocate free space in proportion to a node's one-hop local-risk, giving the Localized Risk-based Free-Space Allocation (LR-FSA) heuristic, sv lrfsa = B (rv / Σ u∈V ru), where rv = Σ u∈N(v) lu/du. The score rv estimates the load that node v may receive from its neighbors in one round of local redistribution. We train a separate policy for each anchor. Reported TANGCO performance uses the better of the two completed runs (each trained and evaluated independently), a two-start procedure that uses the cascade simulator already required for training.

We encode an anchor allocation as a logit vector aanchor by taking elementwise logs, aanchor = log(sanchor + ε). Since Σ v sv anchor = B, the softmax maps these logits back to sanchor at initialization; the budget B re-enters through the leading factor, and the sm…

Improvements to AI Systems Based on This Paper:

1. Non-Differentiable Optimization with Graph Neural Networks (GNNs)

• Improvement: Use GNN policies trained via REINFORCE (policy gradient) with a residual-softmax parameterization around a heuristic anchor, avoiding the need for differentiable objectives or closed-form solutions.

• Capability: AI can optimize piecewise-constant, non-convex objectives (e.g., fail-or-survive thresholds) in networked systems, where gradient-based methods fail.

2. Topology-Aware Capacity Allocation

• Improvement: Incorporate multi-hop graph structure (via message passing) and node features (load, degree, neighborhood load variance) into allocation decisions, rather than treating nodes independently.

• Capability: AI can allocate limited resources (e.g., capacity, budget, redundancy) across heterogeneous networks (power grids, cloud clusters, transport) to maximize resilience against cascading failures.

3. Transferable Pre-Training Across Graph Topologies

• Improvement: Pre-train a single policy (TANGCOpre) on diverse synthetic graphs (varying families, sizes, densities) and deploy it on unseen real networks without per-network retraining.

• Capability: AI can generalize to new, unseen network structures at near-zero deployment cost, matching or exceeding per-instance training performance.

4. Simulator-in-the-Loop Reinforcement Learning

• Improvement: Train policies directly against a cascade simulator using Monte Carlo AUC rewards, with batch-mean baselines and L2 regularization for variance reduction.

• Capability: AI can learn robust strategies in environments with discrete events (e.g., node failures) and stochastic dynamics, without requiring analytical models or differentiable simulators.

5. Interpretable Allocation via Feature Attribution

• Improvement: Use nested regression models (local-risk, degree, load, k-core) to explain learned allocations, identifying regimes where simple rules suffice vs. where nonlinear/higher-order structure is needed.

• Capability: AI can generate explainable policies that reveal dominant factors (e.g., one-hop local risk) and automatically derive improved closed-form heuristics (e.g., Tuned Local-Risk) for specific regimes.

6. Scalable Optimization for Large Networks

• Improvement: Achieve near-linear training scaling with graph size (O(N+E) per iteration) and negligible GNN overhead compared to simulation, enabling deployment on networks with tens of thousands of nodes.

• Capability: AI can optimize resource allocation in large-scale infrastructure (e.g., 40,000-node networks) within practical time budgets.

7. Robustness Under Tight Budgets and Extreme Topologies

• Improvement: Use dual-anchor training (uniform and local-risk) to avoid heuristic failure modes (e.g., over-concentration on hubs) and maintain gains across tight-to-loose capacity budgets.

• Capability: AI can maintain performance even in adversarial conditions (e.g., hub-heavy networks, minimal free capacity) where single heuristics collapse.

8. Automatic Heuristic Discovery

• Improvement: Analyze learned allocations to derive new closed-form rules (e.g., T-LR with exponent γ) that recover most of the performance gap in regimes where local risk dominates.

• Capability: AI can distill complex learned policies into simple, deployable rules for resource-constrained or real-time applications, while flagging regimes where full GNN reasoning is required.

What the Improved AI System Can Do:

• Design capacity allocations for power grids, cloud server clusters, or transport networks to maximize survival against cascading failures, even when the objective is non-differentiable.

• Deploy a pre-trained model on a new network (e.g., a city’s road system) in under a second, with robustness gains of 1.6%–246% over hand-designed heuristics.

• Explain its allocations by identifying whether local risk, degree, or nonlinear interactions drive decisions, and automatically generate simpler rules where possible.

• Scale to networks with tens of thousands of nodes, training in near-linear time and transferring across related topologies without retraining.