A Bayesian Approach for the Network Reconstruction of Interdependent Critical Infrastructure Systems from Cascading Failures

Technical Summary: A Bayesian Approach for Network Reconstruction of Interdependent Critical Infrastructure Systems

Problem Statement
Analyzing the behavior of complex interdependent networks, particularly Interdependent Critical Infrastructure (ICI) systems (e.g., coupled water, power, and gas networks), requires complete knowledge of network topology and interdependencies. However, such data is frequently unavailable due to security concerns or decentralized operations. While some interdependencies are revealed only after a disruption, existing methods often rely on model-driven assumptions or synthetic data generation. This study addresses the inverse problem of reconstructing the unknown topology of ICI networks using observed cascading failure data. The challenge lies in inferring the network structure from dynamic failure sequences while accounting for the specific physical and topological constraints inherent to infrastructure systems, where data is often partial and uncertain.

Methodology
The authors propose a scalable, nonparametric Bayesian approach to infer the discrete posterior distribution of the network topology ($A$) given a set of cascading failure observations ($C$). The core of the methodology involves:

1. Bayesian Formulation: The problem is framed as estimating $P(A|C) \propto P(C|A)P(A)$.

   • Likelihood ($P(C|A)$): Modeled using a Susceptible-Infected (SI) epidemic model to simulate the propagation of failures across infrastructure sectors. The likelihood calculates the probability of observing specific failure sequences given a candidate adjacency matrix.
   • Prior ($P(A)$): Modeled using a Hierarchical Stochastic Block Model (HSBM). Unlike generic random or scale-free graphs, the HSBM captures the block structure (different infrastructure sectors) and hierarchical levels (supply, transmission, and demand facilities) characteristic of ICIs.

2. Sampling via Metropolis-Hastings (M-H): Since the posterior distribution does not admit a closed-form solution, the authors employ the Metropolis-Hastings algorithm to sample possible network topologies.

   • Infrastructure-Dependent Proposal (IP): A novel proposal distribution is devised to ensure that only topologies conforming to ICI physical constraints are generated. This includes 10 specific constraints, such as ensuring connectivity from supply to demand nodes, preventing cycles within infrastructure networks, and enforcing directional flow (e.g., from demand to supply for interdependent links). This significantly reduces the sampling space compared to random-walk proposals.
   • Convergence: The Markov chain's convergence is theoretically proven and numerically demonstrated.

3. Computational Optimization: To address the exponential growth of possible topologies in large-scale networks, three optimization techniques are introduced:

   • Likelihood Calculation: Reducing complexity from $O(|V|^2)$ to $O(|V| + |E|)$ by traversing edge lists of failed neighborhoods rather than iterating over all node pairs.
   • Graph Validation: Leveraging the tripartite structure of ICI networks and Theorem 1 to validate topological constraints in linear time by checking only the in/out-degrees of modified nodes, rather than performing full path searches.
   • Tie-No-Tie (TNT) Sampler: Replacing random node pair selection with a sampler that prioritizes removing edges in sparse graphs, thereby increasing the acceptance rate of proposals.

Key Contributions
The paper makes two primary methodological contributions:

1. Infrastructure-Dependent Proposal (IP): The integration of topological and physical constraints into the MCMC sampling process. This approach utilizes the block structure of ICI networks to calculate prior probabilities and drastically shrinks the candidate topology space, improving both sampling accuracy and mixing time.
2. Computational Optimization: The design of three specific techniques (edge-list likelihood calculation, linear-time graph validation, and the TNT sampler) that enable the reconstruction of large-scale networks where standard MCMC methods would be computationally prohibitive.

Results
The proposed approach was validated using synthetic Interdependent Critical Infrastructure Networks (SICINs) representing water, power, and gas systems.

• Accuracy: The IP-based method significantly outperformed existing baselines. In experiments with 40 cascading failure scenarios, the IP-based method achieved a maximum F1-score of 0.964, compared to 0.710 for a non-IP Bayesian approach and 0.712 for a Variational Graph Auto-Encoder (VGAE) baseline.
• Data Efficiency: The Bayesian approach demonstrated superior performance with limited data compared to graph-embedding methods, which typically require massive amounts of information.
• Robustness: Sensitivity analyses showed that the IP-based method is less sensitive to variations in the ratio of initial failed nodes and noise levels in the data compared to non-IP methods. Moderate initial failure ratios (0.2–0.4) yielded the best reconstruction accuracy.
• Scalability: The method was successfully applied to a larger $120 \times 120$ random ICI network, achieving a moderate F1-score of 0.664, demonstrating transferability to larger systems.
• Optimization Impact: Among the tested configurations, the combination of IP, Edge List optimization, and TNT sampling (Method M-1) offered the best trade-off between reconstruction accuracy and computational time.

Significance and Claims
The authors claim this work constitutes the first attempt to develop network reconstruction methods specifically for solving data and uncertainty challenges in complex interdependent infrastructure systems. The significance of the work lies in its ability to uncover uncertain network interdependencies during disruptions when complete data is unavailable.

The paper asserts that by accurately reconstructing the topology of real-world ICI networks, policymakers and practitioners gain a clearer basis for informed decision-making regarding risk mitigation and economic benefits. The proposed approach is presented as a practical tool for scenarios where data is restricted by security or operational decentralization, offering a data-driven alternative to purely assumption-based modeling. The authors remain modest regarding future applications, noting that while the current study uses the SI model, future work could explore more advanced failure simulation models (e.g., SIR) and time-varying network structures.