  Generative models for graphs are increasingly becoming a popular tool for
researchers to generate realistic approximations of graphs. While in the past,
focus was on generating graphs which follow general laws, such as the power law
for degree distribution, current models have the ability to learn from observed
graphs and generate synthetic approximations. The primary emphasis of existing
models has been to closely match different properties of a single observed
graph. Such models, though stochastic, tend to generate samples which do not
have significant variance in terms of the various graph properties. We argue
that in many cases real graphs are sampled drawn from a graph population (e.g.,
networks sampled at various time points, social networks for individual
schools, healthcare networks for different geographic regions, etc.). Such
populations typically exhibit significant variance. However, existing models
are not designed to model this variance, which could lead to issues such as
overfitting. We propose a graph generative model that focuses on matching the
properties of real graphs and the natural variance expected for the
corresponding population. The proposed model adopts a mixture-model strategy to
expand the expressiveness of Kronecker product based graph models (KPGM), while
building upon the two strengths of KPGM, viz., ability to model several key
properties of graphs and to scale to massive graph sizes using its elegant
fractal growth based formulation. The proposed model, called x-Kronecker
Product Graph Model, or xKPGM, allows scalable learning from observed graphs
and generates samples that match the mean and variance of several salient graph
properties. We experimentally demonstrate the capability of the proposed model
to capture the inherent variability in real world graphs on a variety of
publicly available graph data sets.
