Contracting tensor networks is often computationally demanding. Welldesigned contraction sequences can dramatically reduce the contraction cost. We explore the performance of simulated annealing and genetic algorithms, two common discrete optimization techniques, to this ordering problem. We benchmark their performance as well as that of the commonlyused greedy search on physically relevant tensor networks. Where computationally feasible, we also compare them with the optimal contraction sequence obtained by an exhaustive search. Furthermore, we present a systematic comparison with stateoftheart tree decomposition and graph partitioning algorithms in the context of random regular graph tensor networks. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources, with an advantage that scales with tensor network size. We compare the obtained contraction sequences and identify signs of highly nonlocal optimization, with the more sophisticated algorithms sacrificing runtime early in the contraction for better overall performance.
Tensor Network Contraction For Network Reliability Estimates
Quantifying network reliability is a hard problem, proven to be #Pcomplete [1]. For realworld network planning and decision making, approximations for the network reliability problem are necessary. This study shows that tensor network contraction (TNC) methods can quickly estimate an upper bound of All Terminal Reliability, RelATR(G), by solving a superset of the network reliability problem: the edge cover problem, EC(G). In addition, these tensor contraction methods can exactly solve sourceterminal (ST) reliability for the class of directed acyclic networks, RelS−T (G). The computational complexity of TNC methods is parameterized by treewidth, significantly benefitting from recent advancements in approximate tree decomposition algorithms [2]. This parameterization does not rely on the reliability of the graph, which means these tensor contraction methods can determine reliability faster than Monte Carlo methods on highly reliable networks, while also providing exact answers or guaranteed upper bound estimates. These tensor contraction methods are applied to grid graphs, random cubic graphs, and a selection of 58 power transmission networks [3], demonstrating computational efficiency and effective approximation using EC(G).
more »
« less
 Award ID(s):
 2037545
 NSFPAR ID:
 10410341
 Editor(s):
 Li, J.; Spanos, P. D.; Chen, J.B.; Peng, Y.B.
 Date Published:
 Journal Name:
 The 13th International Conference on Structural Safety and Reliability (ICOSSAR 20212022)
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract 
Adjacency polytopes appear naturally in the study of nonlinear emergent phenomena in complex networks. The ``"PQtype" adjacency polytope, denoted $\nabla^{\mathrm{PQ}}_G$ and which is the focus of this work, encodes rich combinatorial information about powerflow solutions in sparse power networks that are studied in electric engineering. Of particular importance is the normalized volume of such an adjacency polytope, which provides an upper bound on the number of distinct powerflow solutions. In this article we show that the problem of computing normalized volumes for $\nabla^{\mathrm{PQ}}_G$ can be rephrased as counting $D(G)$draconian sequences where $D(G)$ is a certain bipartite graph associated to the network. We prove recurrences for all networks with connectivity at most $1$ and, for $2$connected graphs under certain restrictions, we give recurrences for subdividing an edge and taking the join of an edge with a new vertex. Together, these recurrences imply a simple, nonrecursive formula for the normalized volume of $\nabla^{\mathrm{PQ}}_G$ when $G$ is part of a large class of outerplanar graphs; we conjecture that the formula holds for all outerplanar graphs. Explicit formulas for several other (nonouterplanar) classes are given. Further, we identify several important classes of graphs $G$ which are planar but not outerplanar that are worth additional study.more » « less

Li, J. ; Spanos, P. D. ; Chen, J. B. ; Peng, Y. B. (Ed.)Infrastructure networks offer critical services to modern society. They dynamically interact with the environment, operators, and users. Infrastructure networks are unique engineered systems, large in scale and high in complexity. One fundamental issue for their reliability assessment is the uncertainty propagation from stochastic disturbances across interconnected components. Monte Carlo simulation (MCS) remains approachable to quantify stochastic dynamics from components to systems. Its application depends on time efficiency along with the capability of delivering reliable approximations. In this paper, we introduce Quasi Monte Carlo (QMC) sampling techniques to improve modeling efficiency. Also, we suggest a principled Monte Carlo (PMC) method that equips the crude MCS with Probably Approximately Correct (PAC) approaches to deliver guaranteed approximations. We compare our proposed schemes with a competitive approach for stochastic dynamic analysis, namely the Probability Density Evolution Method (PDEM). Our computational experiments are on ideal but complex enough sourceterminal (ST) dynamic network reliability problems. We endow network links with oscillators so that they can jump across safe and failed states allowing us to treat the problem from a stochastic process perspective. We find that QMC alone can yield practical accuracy, and PMC with a PAC algorithm can deliver accuracy guarantees. Also, QMC is more versatile and efficient than the PDEM for network reliability assessment. The QMC and PMC methods provide advanced uncertainty propagation techniques to support decision makers with their reliability problems.more » « less

One essential task in practice is to quantify and improve the reliability of an infrastructure network in terms of the connectivity of network components (i.e., allterminal reliability). However, as the number of edges and nodes in the network increases, computing the allterminal network reliability using exact algorithms becomes prohibitive. This is extremely burdensome in network designs requiring repeated computations. In this paper, we propose a novel machine learningbased framework for evaluating and improving allterminal network reliability using Deep Neural Networks (DNNs) and Deep Reinforcement Learning (DRL). With the help of DNNs and Stochastic Variational Inference (SVI), we can effectively compute the allterminal reliability for different network configurations in DRL. Furthermore, the Bayesian nature of the proposed SVI+DNN model allows for quantifying the estimation uncertainty while enforcing regularization and reducing overfitting. Our numerical experiment and case study show that the proposed framework provides an effective tool for infrastructure network reliability improvement.more » « less

null (Ed.)We consider nodeweighted survivable network design (SNDP) in planar graphs and minorclosed families of graphs. The input consists of a nodeweighted undirected graph G = ( V , E ) and integer connectivity requirements r ( uv ) for each unordered pair of nodes uv . The goal is to find a minimum weighted subgraph H of G such that H contains r ( uv ) disjoint paths between u and v for each node pair uv . Three versions of the problem are edgeconnectivity SNDP (ECSNDP), elementconnectivity SNDP (ElemSNDP), and vertexconnectivity SNDP (VCSNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O ( k )approximation algorithm for ECSNDP and ElemSNDP when the input graph is planar or more generally if it belongs to a proper minorclosed family of graphs; here, k = max uv r ( uv ) is the maximum connectivity requirement. This improves upon the O ( k log n )approximation known for nodeweighted ECSNDP and ElemSNDP in general graphs [31]. We also obtain an O (1) approximation for nodeweighted VCSNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our result for ElemSNDP can be used in a blackbox fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for nodeweighted Steiner tree and Steiner forest problems in planar graphs and proper minorclosed families of graphs via a primaldual algorithm.more » « less