Abstract
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.
Introduction
Modeling and generating real-world graphs, such as molecular structures or social networks, is a fundamental challenge in data mining. A primary hurdle is the permutation invariance of graphs: a graph with $n$ nodes can be represented by $n!$ different adjacency matrices. Existing learning-based models, such as GraphRNN, attempt to handle this by converting graphs into sequences via Breadth-First Search (BFS). However, because a single graph can produce multiple BFS sequences, these models rely on data augmentation—feeding many random representations of the same graph into the network. This "one-to-many" mapping introduces significant computational overhead, limits scalability to large databases, and often ignores semantic node and edge labels.
The GraphGen Framework
To address these limitations, we propose GraphGen, a domain-agnostic technique that ensures a deterministic "one-to-one" mapping between graphs and their sequence representations.
Graph Canonization via Minimum DFS Codes
Instead of random traversals, GraphGen utilizes graph canonization. Every graph is converted into a unique sequence known as a minimum DFS code. Two graphs are isomorphic if and only if they share the same minimum DFS code. This reduction from $O(|V|^2)$ to $O(|E|)$ provides the neural network with a precise target, eliminating the need for noisy data augmentation. While finding a minimum DFS code is theoretically NP-hard, GraphGen leverages node/edge labels and structural invariants (like node degree) to prune the search space, making the process highly efficient for real-world datasets.
Custom LSTM Architecture
The complex joint distribution of graph structure and semantic labels is learned through a novel auto-regressive LSTM architecture. At each time step $i$, the model predicts a 5-tuple $s_i = (t_u, t_v, L_u, L_e, L_v)$, where $t_u$ and $t_v$ are timestamps of connected nodes, $L_u$ and $L_v$ are their labels, and $L_e$ is the edge label.
By predicting these tuples sequentially, the model captures the intricate dependencies between the graph's topology and its semantic properties. Unlike standard NLP models, which often fail on the unique timestamping rules of DFS codes, this custom architecture is specifically designed for the structural constraints of graph sequences.
Experimental Evaluation
We evaluated GraphGen on eight real-world datasets, including the massive ZINC database containing 3.2 million chemical compounds, as well as citation and protein networks.
Speed and Scalability
GraphGen demonstrates significant performance gains, operating on average 4 times faster than state-of-the-art baselines like GraphRNN. While competing models failed to complete training within three days on datasets exceeding 100,000 graphs, GraphGen scaled comfortably to millions of graphs. This efficiency stems from the precise canonical training target, which avoids the data bloat associated with random sequence representations.
Generative Quality
Across 11 different metrics, GraphGen consistently outperformed baselines. It achieved superior Neighborhood Subgraph Pairwise Distance Kernel (NSPDK) scores, indicating a better capture of global structural similarity. Furthermore, GraphGen maintained high diversity, achieving 98-100% uniqueness in generated graphs, whereas baselines often struggled with low uniqueness and incorrect graph sizes.
Conclusion
GraphGen provides a scalable, domain-agnostic solution for labeled graph generation by combining graph canonization with a specialized LSTM architecture. By reducing the representation space and focusing on canonical sequences, it achieves state-of-the-art results in both speed and quality. Future work will focus on extending the model to handle continuous feature vectors and scaling to the generation of single, massive graphs with millions of nodes.
Summary updated