GraphGen-Redux: a Fast and Lightweight Recurrent Model for labeled Graph
  Generation
  The problem of labeled graph generation is gaining attention in the Deep
Learning community. The task is challenging due to the sparse and discrete
nature of graph spaces. Several approaches have been proposed in the
literature, most of which require to transform the graphs into sequences that
encode their structure and labels and to learn the distribution of such
sequences through an auto-regressive generative model. Among this family of
approaches, we focus on the GraphGen model. The preprocessing phase of GraphGen
transforms graphs into unique edge sequences called Depth-First Search (DFS)
codes, such that two isomorphic graphs are assigned the same DFS code. Each
element of a DFS code is associated with a graph edge: specifically, it is a
quintuple comprising one node identifier for each of the two endpoints, their
node labels, and the edge label. GraphGen learns to generate such sequences
auto-regressively and models the probability of each component of the quintuple
independently. While effective, the independence assumption made by the model
is too loose to capture the complex label dependencies of real-world graphs
precisely. By introducing a novel graph preprocessing approach, we are able to
process the labeling information of both nodes and edges jointly. The
corresponding model, which we term GraphGen-Redux, improves upon the generative
performances of GraphGen in a wide range of datasets of chemical and social
graphs. In addition, it uses approximately 78% fewer parameters than the
vanilla variant and requires 50% fewer epochs of training on average.
