Title: A Deep Generative Model for Graphs: Supervised Subset Selection to Create Diverse Realistic Graphs with Applications to Power Networks Synthesis,
Abstract: Creating and modeling real-world graphs is a crucial problem in various
applications of engineering, biology, and social sciences; however, learning
the distributions of nodes/edges and sampling from them to generate realistic
graphs is still challenging. Moreover, generating a diverse set of synthetic
graphs that all imitate a real network is not addressed. In this paper, the
novel problem of creating diverse synthetic graphs is solved. First, we devise
the deep supervised subset selection (DeepS3) algorithm; Given a ground-truth
set of data points, DeepS3 selects a diverse subset of all items (i.e. data
points) that best represent the items in the ground-truth set. Furthermore, we
propose the deep graph representation recurrent network (GRRN) as a novel
generative model that learns a probabilistic representation of a real weighted
graph. Training the GRRN, we generate a large set of synthetic graphs that are
likely to follow the same features and adjacency patterns as the original one.
Incorporating GRRN with DeepS3, we select a diverse subset of generated graphs
that best represent the behaviors of the real graph (i.e. our ground-truth). We
apply our model to the novel problem of power grid synthesis, where a synthetic
power network is created with the same physical/geometric properties as a real
power system without revealing the real locations of the substations (nodes)
and the lines (edges), since such data is confidential. Experiments on the
Synthetic Power Grid Data Set show accurate synthetic networks that follow
similar structural and spatial properties as the real power grid.