GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph
  Generation
  Graph generative models have been extensively studied in the data mining
literature. While traditional techniques are based on generating structures
that adhere to a pre-decided distribution, recent techniques have shifted
towards learning this distribution directly from the data. While learning-based
approaches have imparted significant improvement in quality, some limitations
remain to be addressed. First, learning graph distributions introduces
additional computational overhead, which limits their scalability to large
graph databases. Second, many techniques only learn the structure and do not
address the need to also learn node and edge labels, which encode important
semantic information and influence the structure itself. Third, existing
techniques often incorporate domain-specific rules and lack generalizability.
Fourth, the experimentation of existing techniques is not comprehensive enough
due to either using weak evaluation metrics or focusing primarily on synthetic
or small datasets. In this work, we develop a domain-agnostic technique called
GraphGen to overcome all of these limitations. GraphGen converts graphs to
sequences using minimum DFS codes. Minimum DFS codes are canonical labels and
capture the graph structure precisely along with the label information. The
complex joint distributions between structure and semantic labels are learned
through a novel LSTM architecture. Extensive experiments on million-sized, real
graph datasets show GraphGen to be 4 times faster on average than
state-of-the-art techniques while being significantly better in quality across
a comprehensive set of 11 different metrics. Our code is released at
https://github.com/idea-iitd/graphgen.
