Deep Generative Graph Distribution Learning for Synthetic Power Grids

  • 2019-04-12 16:35:09
  • Mahdi Khodayar, Jianhui Wang, Zhaoyu Wang
  • 0

Abstract

Power system studies require the topological structures of real-world powernetworks; however, such data is confidential due to important securityconcerns. Thus, power grid synthesis (PGS), i.e., creating realistic powergrids that imitate actual power networks, has gained significant attention. Inthis letter, we cast PGS into a graph distribution learning (GDL) problem wherethe probability distribution functions (PDFs) of the nodes (buses) and edges(lines) are captured. A novel deep GDL (DeepGDL) model is proposed to learn thetopological patterns of buses/lines with their physical features (e.g., powerinjection and line impedance). Having a deep nonlinear recurrent structure,DeepGDL understands complex nonlinear topological properties and captures thegraph PDF. Sampling from the obtained PDF, we are able to create a large set ofrealistic networks that all resemble the original power grid. Simulationresults show the significant accuracy of our created synthetic power grids interms of various topological metrics and power flow measurements.

 

Quick Read (beta)

Deep Generative Graph Distribution Learning
for Synthetic Power Grids

Mahdi Khodayar,  Jianhui Wang,  and Zhaoyu Wang,  Mahdi Khodayar and Jianhui Wang are with the Department of Electrical and Computer Engineering, Southern Methodist University, Dallas, TX, USA. e-mail: [email protected] and [email protected] Zhaoyu Wang is with the Department of Electrical and Computer Engineering, Iowa State University, IA, USA. e-mail: [email protected]
Abstract

Power system studies require the topological structures of real-world power networks; however, such data is confidential due to important security concerns. Thus, power grid synthesis (PGS), i.e., creating realistic power grids that imitate actual power networks, has gained significant attention. In this letter, we cast PGS into a graph distribution learning (GDL) problem where the probability distribution functions (PDFs) of the nodes (buses) and edges (lines) are captured. A novel deep GDL (DeepGDL) model is proposed to learn the topological patterns of buses/lines with their physical features (e.g., power injection and line impedance). Having a deep nonlinear recurrent structure, DeepGDL understands complex nonlinear topological properties and captures the graph PDF. Sampling from the obtained PDF, we are able to create a large set of realistic networks that all resemble the original power grid. Simulation results show the significant accuracy of our created synthetic power grids in terms of various topological metrics and power flow measurements.

Power Grid Synthesis, Graph Distribution Learning, Deep Learning, Generative Modeling
\epstopdfDeclareGraphicsRule

.tifpng.pngconvert #1 \OutputFile \AppendGraphicsExtensions.tif \bstctlciteIEEEexample:BSTcontrol

I INTRODUCTION

MANY power system studies require the actual topologies of real-world power networks with real bus and line coordinates as well as real physical charactristics such as power injections and line impedance values. However, due to the confidentiality concerns, there are very few datasets of real power grids such as the IEEE test cases [1] and the Polish grid [2] that are publicly available for such studies. Even these datasets do not contain important information regarding the geographical locations of buses, and lack the diverse characteristics of real topologies. In recent studies, several works are focused on the spatial models for power networks that are realistic but synthesized without revealing any confidential information. [3, 4] create power networks based on the locations of cities and power plants in Texas; however, no geographical or performance comparison with the actual power grid is provided to justify the approach. Although [3, 4] contain useful engineering details, they do not devise a general algorithm that can work with any realistic power network; thus, in practice, these approaches are limited. In this line of research, [5] is the only learning-based power grid synthesis (PGS) model presented in recent literature that applies a Gaussian Mixture Model (GMM) to compute the distributions of bus locations in the Western Interconnect network. However, due to lack of generalization, GMM is theoretically incapable of learning the physical properties of power grid components. Moreover, the data required by [5] exceeds the power grid data as this model represents the demand based on the average residential power usage and city populations. Also, similar to [3] and [4], the GMM approach [5] puts strict assumptions on the node degree and line distributions which do not necessarily hold.

This letter presents a novel deep graph distribution learning (DeepGDL) algorithm to create synthetic power grids. We present a recurrent model that efficiently captures node/edge distributions of arbitrary complex networks. Leveraging a deep architecture, DeepGDL captures complex nonlinear manifolds of nodes/edges in the actual power network, and generates synthetic power grids that imitate the original network. To the best of our knowledge, DeepGDL is the only deep learning-based PGS solution. Also, in contrast to all previous works, the presented algorithm needs no additional information other than the network topology and the bus/line physical properties; hence, it can be applied as a general framework to any PGS problem with minimum amounts of data.

II DeepGDL for Power Grid Synthesis

Let us consider the actual power grid obtained from the Columbia University Synthetic Power Grid (CUSPG) dataset [6] that contains 14430 buses and 18884 lines located in Western US. We represent this network as an undirected weighted graph GP=(V,E) where niV denotes the i-th node while an edge li,jE is a transmission line connecting two nodes ni and nj. For each node ni, GP contains four features including the latitude x(ni), longitude y(ni), power supply pw(ni) (i.e., power generated at the bus i), and power demand pd(ni). A weight Wi,j=X(li,j) is defined to represent the reactance of the line corresponding to each li,j. Our objective is to learn the PDFs of nodes niV as well as edges li,jE, and sample from them to generate synthetic power grids.

Algorithm 1 is the pseudocode of our presented model. First, using the modularity optimization in [7], GP is decomposed into K communities (i.e., subgraphs) Ψ={C1,C2,,CK} where the nodes inside each Ck(1kK) are densely connected while the nodes in distinct communities have sparse connections. For each Ck=(Vk,Ek), the adjacency matrix Ak is modeled based on the node ordering τ that maps any niVk to a row/column index τ(i) in Ak. Having the set of all |Vk|! node permutations denoted by T, one can write a new adjacency matrix AτAT={Aτ|τT} defined by Ai,jτ=Aτ(i),τ(t)k=X(eτ(i),τ(t)); hence, we model Ck as an arbitrarily-sized sequence of node orderings each with a unique nodal and edge feature sequence. Considering the ordering τ, a nonlinear function fn maps (Ck,τ) to a 2-dimensional node feature tensor Fτk using the following formulation:

Fτk=fn(Ck,τ)=(Fτk(1),Fτk(2),,Fτk(|Vk|)) (1)

where Fτk(i)=<x(nτ(i)),y(nτ(i)),pw(nτ(i)),pd(nτ(i))> is the nodal feature of the i-th node w.r.t the ordering τ. Similarly, we define fΩ that maps (G,τ) to a 2-dimensional edge feature tensor Ωτk computed by:

Ωτk=fΩ(G,τ)=(Ωτk(1),Ωτk(2),..,Ωτk(|Vk|)) (2)

where Ωτk(i)=<A1,iτ,A2,iτ,,Ai-1,iτ>T is the weighted adjacency vector of node τ(i); thus, for an undirected weighted Ck, the tensor <Fτk,Ωτk> uniquely defines the graph Ck. As a result, one can recover Ck by the mapping Fr(<Fτk,Ωτk>)=Ck; hence, in order to learn the distribution of the nodes and edges in communities Ck(kK) denoted by P(Ck), we maximize the likelihood of their observation in actual network GP by:

Maxk=1K[P(Ck)=<Fτ,Ωτ>P(Fτk,Ωτk)𝕀(fr(Fτk,Ωτk)=Ck)] (3)

where 𝕀(x)=1 if x is true and zero otherwise. Using this optimization, we maximize the observation of GP’s communities, hence finding a model that can imitate GP.

\DontPrintSemicolon\KwInActual Power Network GP=(V,E) Define GRU’s starting token START and ending token END. Community counter k=1 \WhilekK Initialize: [Ωτk(0),Fτk(0)]=START, i=1
\While[Ωτk(i),Fτk(i)]END Compute graph state Si using (5)
Create a new node (i-th node) using (6)
i=i+1 Generate Synthetic Community CSynk using (6) \justifyTrain GRU, fFnn, and fΩnn using gradient descent PSyn=(VSyn=k=1KVSynk,ESynk=1KESynk) \WhilePSyn has multiple components \justifycompute φ(ni) as the mean Euclidean distance between ni and its 10 closest neighbor nodes in VSyn. \justifySelect ni whose degree is at most 2 from all nodes in VSyn using the probability φ(ni)-1. \justifyAdd an edge between two nodes ni and nj with probability d(nj)(Euci,j)-1. Here, d(nj) denotes the nj’s degree while Euci,j is the Euclidean distance of ni and nj. \KwOutSynthetic Network PSyn=(VSyn,ESyn)
\algorithmcfname 1 Deep Graph Distribution Learning

Let us write a decomposition for P(Fτk,Ωτk) in (3) using conditional probabilities of the observed sequence of nodal and edge features implied by τ for any community Ck:

i=1|Vk|P((Fτk(i),Ωτk(i))|(Fτk(1),Ωτk(1)),,(Fτk(i-1),Ωτk(i-1))) (4)

The recursive characteristics of the graph features in (4) motivates us to model nodal and edge features by a recurrent neural network. Therefore, we model P(Fτk,Ωτk) using a deep Gated Recurrent Unit (GRU) network. For each community Ck, at each iteration i of our deep recurrent model, the GRU computes a graph state Si using the previous node/edge observations I(t) (j=1,2,,i) by the following recurrent structure:

I(t)=[αk(t)=Fτk(t),βk(t)=Ωτk(i,j)]z(t)=Sig(W1[I(t),M(t)])r(t)=Sig(W2[I(t),M(t)])M~(t)=tnh(WM[I(t),r(t)*M(t-1)])M(t)=(1-z(t))*M(t-1)+z(t)*M~(t) (5)

Here, αk(t) and βk(t) in I(t) are the intermediate nodal and edge features of Ck observed at the j-th round of the recursive formulation. At each round j, the temporal features, z(t) and r(t), are computed for the graph observation I(t) using a sigmoid function Sig with weights W1 and W2, respectively. Then, the GRU’s updating vector M~(t) is computed using the intermediate graph features, r(t) and I(t), as well as the GRU state at the previous round M(t-1). Here, tnh denotes a tangent hyperbolic function with weight WM applied to compute M~(t). The GRU state M(t) is finally computed as a linear regression of M(t-1) and M~(t) weighted by the temporal feature z(t). After running the recursion (5) for i rounds, the final GRU state C(j=i) is our extracted graph state Si.

At each iteration i, we model the node/edge distribution of each community Ck, and generate a new synthetic community CSynk=(VSynk,ESynk) corresponding to Ck using the following formulations:

ξiF=fFnn(Si),ξiΩ=fΩnn(Si)Fτk(i)PξiF{Samplingthefeaturesofi-thnode}Ωτk(i)PξiΩ{Samplingtheweightofi-thedge} (6)
Fig. 1: Visualization of the actual power grid GP and the synthetic network GSyn
TABLE I: Topological properties and power flow analysis of the actual and synthetic networks
Topological Properties Power Flow Statistics (MW)
Networks #Nodes #Edges davg ω D ρ*10-4 Q C Average Median STDV Max
GP 14430 18554 2.572 15.061 37 1.782 0.953 0.072 168.93 33.32 320.93 4,777.07
GSyn 14408 18302 2.510 15.253 37 1.820 0.961 0.072 173.27 29.31 302.21 4,687.83
GMM 14269 19881 2.269 16.229 35 1.953 0.804 0.063 110.25 42.78 479.08 5,521,37
DeepDGL Mean(STDV)
14301
(3.1*𝟏𝟎𝟑)
17869
(4.3*𝟏𝟎𝟑)
2.561
(0.08)
15.226
(0.29)
36.71
(0.13)
1.726
(0.15)
0.952
(0.02)
0.071
(0.004)
171.18 (11.34) 30.42 (1.20) 307.18 (15.59) 4,590.25 (217.01)

where fFnn and fΩnn are two sigmoidal neural networks (SNNs) with the input Si and output vectors ξiF and ξiΩ, respectively. The vector ξiF encodes the nodal feature distribution of the i-th node in CSynk. Similarly, ξiΩ encodes the edge weight distribution corresponding to this node. Sampling from these two distributions in (6), we create a new node (i.e., the i-th synthesized node) of CSynk. We run (6) to create new nodes and edges until the GRU reaches a predefined END state, which terminates the graph generation process and outputs CSynk for every community Ck. Each of the generated communities CSynk is a component of our final synthetic power network PSyn.

As shown in [5], in dense regions of real-world power grids, the low-degree buses are generally connected to high-degree buses. Thus, in order to merge the generated components and form a single-component robust network PSyn, we connect the low-degree nodes nik=1KVSynk in dense regions, to high-degree nodes njk=1KVSynk until the PSyn becomes single-component. The resulting PSyn is finally reported as the output.

III Simulation Results

First, we set several hyperparameters defined in the DeepGDL algorithm. The GRU state variables S, z and r, are considered to have 120 dimensions. Both ffnn and fΛnn are modeled as a SNN with 45 neurons in its first layer and 35 neurons in the second layer. The gradient descent is considered to have a learning rate of 10-3 while its batch size is 30. In this study, K=72 graph communities are considered for GP. We generate 102 synthetic power grids via DeepGDL. Fig. 1(a) and (b) depict the actual network GP and one of our synthetic networks GSyn, respectively. Each community is shown by a distinct color. Moreover, Fig. 1(c) and (d) show the amount of power supply at each bus (node) in the two networks. To compare the performance of the generated grids with the actual grid, we conduct cascading failure experiments using DC power flow. Fig. 1(e) and (f) demonstrate the Yield (i.e. ratio of demand supplied after cascades to the actual value of demand) in the two power grids for cascades initiatd in 103 regions of radius 100km. Each point shows the computed Yield at the center of its corresponding region. As shown in Fig. 1, GSyn accurately resembles the actual grid regarding the topological characteristics and power flow measurements. Table I reports detailed topological measurements and power flow statistics obtained by GP, DeepGDL algorithm, and the state-of-the-art GMM [5] model. It is shown that DeepGDL has significant improvements over GMM in terms of average node degree davg, average path length ω, network Diameter D, Density ρ, Modularity Q, and Average Clustering Coefficient C. Also, Table I shows the substantial accuracy improvements of DeepGDL over the state-of-the-art in terms of power flow measurements.

IV Conclusions

This letter presents a deep graph distribution learning algorithm for the problem of power grid synthesis. A novel recurrent model is proposed to capture deep nodal and edge features from a realistic power network. To the best of our knowledge, DeepGDL is the only deep learning model that can synthesize large-scale networks. Simulation results show significant accuracy of DeepGDL in terms of topological measurements and power flow analysis metrics.

References

  • [1] “IEEE benchmark systems,” www.labs.ece.uw.edu/pstca/, accessed: 2019-01-20.
  • [2] “Polish grid,” www.pserc.cornell.edu/matpower/, accessed: 2019-01-21.
  • [3] K. M. Gegner, A. B. Birchfield, T. Xu, K. S. Shetye, and T. J. Overbye, “A methodology for the creation of geographically realistic synthetic power flow models,” in Power and Energy Conference at Illinois (PECI), 2016 IEEE, 2016, pp. 1–6.
  • [4] A. B. Birchfield, T. Xu, K. M. Gegner, K. S. Shetye, and T. J. Overbye, “Grid structural characteristics as validation criteria for synthetic networks,” IEEE Transactions on power systems, vol. 32, no. 4, pp. 3258–3265, 2017.
  • [5] S. Soltan, A. Loh, and G. Zussman, “A learning-based method for generating synthetic power grids,” IEEE Systems Journal, no. 99, pp. 1–10, 2018.
  • [6] S. Soltan, A. Loh, and g. Zussman, “Columbia university synthetic power grid with geographical coordinates,” Tech. Rep., 1 2018.
  • [7] X. Lu, K. Kuzmin, M. Chen, and B. K. Szymanski, “Adaptive modularity maximization via edge weighting scheme,” Information Sciences, vol. 424, pp. 55–68, 2018.