GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation

1 Introduction and Related Work

• GraphGen is presented as assumption-free and domain-agnostic, with the goal of learning local and global graph patterns directly from observed graphs.The paper notes that this may suit domains where traditional distribution assumptions do not fit, such as chemical compounds and protein interaction networks.Source: §1 · p. 1
• Traditional models target preselected graph families, while domain-specific methods often do not generalize well across domains.Traditional approaches may also omit labels and assume homogeneous graph structure.Source: §1 · pp. 1–2
• Learning-based models still face gaps in domain generality, joint modeling of node and edge labels, and scalability to datasets containing millions of graphs.Some methods rely on exponential graph representations, complex neural architectures, or large parameter spaces.Source: §1 · p. 2
• GraphGen is significantly better in quality than state-of-the-art techniques across an array of metrics and is 4 times faster on average.The evaluation uses real million-sized graph databases spanning three domains.Source: §1 · p. 2
• GraphGen combines graph canonization and LSTMs, turning graph generation into sequence modeling over canonical labels that preserve graph structure and labels.A canonical label is the same for two graphs if and only if they are isomorphic.Source: §1 · p. 2

2 Problem Formulation

• The formulation assumes connected graphs with no self-loops and allows node and edge labels through mappings on vertices and edges.Source: §2 · p. 2
• A graph generative model learns a distribution over graphs from observed graphs drawn from an underlying hidden distribution.Source: §2 · p. 2
• The observed graphs may differ in numbers of nodes and edges and in their node and edge label sets.Source: §2 · p. 2
• Effectiveness means generating similar graphs of varied sizes from a distribution close to the hidden distribution, without prior assumptions about structure or labeling.Source: §2 · p. 2

2.1 Challenges

• An n-node adjacency-matrix representation has O(n2) structural values, and node or edge labels make its output space more complex.Source: §2.1 · p. 2
• Graph properties such as degree, clustering, labels, and graph size are dependent, so modeling separate property distributions is insufficient.Source: §2.1 · p. 2
• Dependencies among graph parameters can vary across regions, since not all graph regions are equally dense.Source: §2.1 · p. 2

3 GraphGen: Generative model for labeled graphs

• GraphGen canonizes each graph as a unique sequence rather than using an adjacency matrix, reducing the representation from |V|^2 values to |E| sequence elements.In real graphs, the passage says |E| = |V|^2 is rarely seen.Source: §3 · p. 3
• Canonicalization gives a one-to-one mapping between a graph and its label instead of |V|! adjacency-matrix representations.Source: §3 · p. 3

3.1 DFS Codes: Graphs to Sequences

• A canonical label is a string representation shared by two graphs if and only if they are isomorphic.Source: §3.1 · p. 3
• DFS codes encode graphs as edge sequences whose tuples include endpoint timestamps, node labels, and edge labels.Traversal edges are forward edges with increasing timestamps; edges outside the traversal are backward edges.Source: §3.1 · p. 3
• Backward edges are ordered relative to forward edges and to other backward edges, yielding a total ordering of the graph's edges.Source: §3.1 · p. 3
• The minimum DFS code is the lexicographically smallest DFS code among a graph's possible DFS traversals.Source: §3.1 · p. 3

3.1.1 Computation Cost and Properties

• Finding a minimum DFS code has O(|V|!) worst-case cost, but graph labels can prune the search and invariants can serve as labels when label diversity is low.Source: §3.1.1 · p. 3
• Precise one-to-one graph representations avoid asking the neural network to learn multiple representations of the same graph, supporting a lighter architecture and improved quality and scalability.Source: §3.1.1 · pp. 3–4

3.2.1 Model Overview

• Minimum DFS codes bijectively represent graphs with structure and labels, letting GraphGen learn sequences and recover graphs from sampled codes.Source: §3.2.1 · p. 4

3.2.2 Model Details

• At each step, GraphGen factors sequence likelihood into conditional edge-tuple probabilities, with EOS supporting variable-length sequences and tuple components assumed independent.Source: §3.2.2 · p. 4
• A custom LSTM embeds each sparse edge tuple, updates graph state, and samples its five endpoint, node-label, and edge-label components from separate distributions.Source: §3.2.2 · p. 4

3.2.3 Graph Generation

• Generation samples each edge tuple’s components and appends them to the sequence until any component produces EOS.Source: §3.2.3 · p. 5, §3.2.4 · p. 5

3.2.4 Graph Modeling

• Training feeds observed tuples at successive steps rather than the model’s predictions, and optimizes cumulative binary cross-entropy.Source: §3.2.4 · p. 5

3.2.5 Parameters

• Independent MLP output heads and a linear embedding feed a weight-shared LSTM; fixed training-set dimensions bound graph size and available labels.Source: §3.2.5 · p. 5

3.2.6 Complexity Analysis of Modeling and Inference.

• Forward and backward modeling and graph generation each scale O(|E|) in edge count; the analysis excludes weight-optimization cost.Source: §3.2.6 · pp. 5–6

• GraphGen is significantly better in quality on average than GraphRNN and DeepGMG.Source: §4 · p. 6
• 4 times faster on average than GraphRNN, GraphGen’s reported speed advantage is measured against that baseline.Source: §4 · p. 6
• GraphGen scales better with graph size in both quality and efficiency.Source: §4 · p. 6
• The code and datasets used for the empirical evaluation are available from the project repository.Source: §4 · p. 6

4.1.1 Datasets

• The evaluation spans chemical compounds, citation graphs, and enzyme protein structures, with nodes and edges assigned domain-specific meanings and labels.Enzymes have three node-label types; the authors also supplement node labels with node degrees to examine graph invariants.Source: §4.1.1 · p. 6

4.1.2 Baselines

• GraphGen is compared with DeepGMG and GraphRNN, with GraphRNN extended to support node and edge labels.The DeepGMG implementation was modified from an unlabeled-graph version.Source: §4.1.2 · p. 6

4.1.3 Parameters and Training sets

• The default train, validation, and test split is 80%, 10%, and 10%, while Cora and Citeseer training graphs are sampled using random walks with restarts.The experiments specify model and optimizer settings, including four LSTM layers, Adam, and dropout.Source: §4.1.3 · p. 6

4.1.4 Metrics

• Evaluation covers graph structure and size, node and edge label distributions, joint node-label/degree distributions, and holistic graph similarity using NSPDK.Lower NSPDK distance indicates better performance; it compares pairs of subgraphs at varying radii and distances.Source: §4.1.4 · p. 6
• Novelty measures whether generated graphs are unseen relative to training graphs, while uniqueness measures the share not duplicated among generated graphs.Quality metrics use 2,560 generated graphs against 2,560 test graphs; results average repeated samples or runs.Source: §4.1.4 · p. 7

4.2 Quality

• GraphGen significantly outperforms GraphRNN and DeepGMG across datasets on NSPDK and orbit-count distributions, capturing global similarity and motifs.The authors identify these combined measures as establishing better graph modeling by GraphGen.Source: §4.2 · p. 7
• GraphGen is consistently best on node- and edge-label preservation, edge-count graph size, and the joint node-label/degree metric.On Enzymes, GraphRNN marginally surpasses GraphGen on degree and clustering coefficient, while GraphGen is better on six of eight metrics.Source: §4.2 · p. 7
• GraphGen achieves at least 98% uniqueness across datasets; GraphRNN has 45% uniqueness on Lung and regenerates at least 30% of graphs in several datasets.The authors suggest random sequence representations could contribute to GraphRNN's duplication, whereas GraphGen's DFS codes map one-to-one to graphs.Source: §4.2 · p. 7
• GraphRNN generates much smaller graphs on labeled data, but mirrors test graph sizes when labels are removed; DeepGMG is generally stronger than GraphRNN but extremely slow and does not scale to larger networks.The authors attribute GraphRNN's size issue in labeled graphs to labels adding complexity that simple extensions of unlabeled models do not solve.Source: §4.2 · pp. 7–8

4.2.1 Visual Inspection

• In Lung samples, GraphGen's graphs look most similar to real graphs, with comparable sizes and structures, while GraphRNN's look most dissimilar and lack larger motifs such as benzene rings.For Cora, visual inspection cannot reliably rank GraphGen against GraphRNN, but GraphGen's generated graphs display label homogeneity within densely connected communities.Source: §4.2.1 · p. 8, Figure 4 · p. 8

4.3 Scalability

• GraphGen trains 2 to 5 times faster than GraphRNN across datasets, while DeepGMG is the slowest and has 100 to 200 times higher time per epoch than GraphGen.GraphGen's time per epoch is approximately 30% faster than GraphRNN on average, and it runs for fewer epochs to reach validation-loss minimization.Source: §4.3 · p. 8

4.3.1 Impact of Training Set Size

• GraphGen finishes within two and a half days on more than 3 million training graphs, whereas GraphRNN and DeepGMG fail to finish within three days above 100,000 graphs.GraphGen's growth rate slows at larger training sizes as fewer epochs are needed to reach validation-loss minima.Source: §4.3.1 · p. 8
• As training sets grow from approximately 10,000 to 50,000 graphs, GraphRNN's NSPDK and orbit quality improves steeply, while GraphGen's improvement is milder.GraphRNN still fails to finish within three days even at 100,000 graphs; the authors conclude scalability matters for productivity and modeling quality.Source: §4.3.1 · p. 8

4.3.2 Impact of Graph Size

• Quality drops as graph sizes increase, but GraphGen's decline is more gradual than GraphRNN's and DeepGMG's; DeepGMG fails on larger graph-size buckets and GraphRNN runs out of 12GB GPU memory on the largest Cora bucket.The analysis partitions datasets by graph size and trains and tests within each bucket.Source: §4.3.2 · pp. 8–9, Figure 5 · p. 9
• Minimum-DFS-code construction is a small share of GraphGen's training time: 30 seconds for 10,000 chemical graphs and 50 minutes for the largest Cora bucket, against total times of four and ten hours, respectively.The experiments support canonical graph labels over random sequence representations; GraphRNN's BFS-sequence preprocessing is slower in chemical compounds.Source: §4.3.2 · p. 9, Figure 6 · p. 9

4.4 Impact of Invariants

• On Enzymes, which has only three node labels and no edge labels, node degree and clustering coefficient augment labels used in minimum DFS code generation.The experiment compares original labels alone, labels plus degree, labels plus clustering coefficient, and both invariants together.Source: §4.4 · p. 9
• DFS code generation time steadily decreases as more invariants are used, while total training time shows no such trend.Additional features may increase or decrease the optimizer's time to find the validation-loss minimum.Source: §4.4 · p. 9
• Using invariants reduces NSPDK distance and Orbit, with degree providing slightly better results than clustering coefficient.The authors conclude that invariants improve quality while reducing the cost of minimum DFS code generation.Source: §4.4 · p. 9

4.5 Alternatives to LSTMs

• The comparison reports Lung and Cora due to space constraints, with a similar trend observed in other datasets.The two metrics presented are NSPDK distance and Uniqueness.Source: §4.5 · p. 9
• SentenceVAE causes a huge increase in NSPDK distance and uniqueness close to 0, indicating inferior quality and repeated generation of the same structure.Table 5 compares LSTM with SentenceVAE; the reported results cover Lung and Cora.Source: §4.5 · pp. 9–10
• DFS-code tuples are unique because of timestamps, so sentence-modeling techniques that rely on repeated words and phrases perform poorly.The authors say this indicates a need for architectures custom-made for DFS codes, but does not show LSTMs are the only choice.Source: §4.5 · p. 10

5 Concluding Insights

• Minimum DFS codes provide canonical graph labels, reducing redundant representations and learning complexity; despite worst-case factorial construction, labels and vertex invariants keep it a small part of training time.The authors conclude that precise representations are preferable for modeling quality and scalability.Source: §5 · p. 10
• GraphGen satisfies the study's quality criteria across metrics covering local node properties, motifs, global similarity, graph sizes, labels, and redundancy.The authors argue that graph quality requires enough metrics to cover these different aspects.Source: §5 · p. 10
• GraphGen and other existing learning-based techniques cannot scale to graphs containing millions of nodes, and extending label modeling to feature vectors remains open.The authors plan to explore both questions by extending the GraphGen platform.Source: §5 · p. 10