PaperlayerView exact revision on arXiv

Source-linked AI summary

A Systematic Survey on Deep Generative Models for Graph Generation

Xiaojie Guo, Liang Zhao

arXiv:2007.06686v3cs.LGstat.ML

TL;DR

Traditional graph generative models are hand-crafted and limited in the graph properties they can model. This survey systematically reviews deep graph generative models, their evaluation measures, applications, and future opportunities.

  • Problem

    Traditional graph generation methods rely on hand-crafted structural assumptions, limiting their ability to model complex dependencies and unknown network properties.

  • Method

    The survey develops taxonomies of unconditional and conditional deep graph generative models, compares their techniques, and reviews evaluation measures and applications.

  • Results

    The survey provides a systematic review, detailed comparisons and discussions of deep graph generative models, evaluation measures, and popular applications.

  • Takeaways & Limitations

    Deep graph generative models address the challenge of learning graph distributions from observed graphs and support applications such as novel drug discovery and protein structure modeling.

  • Takeaways & Limitations

    Existing deep graph generative models typically focus on static graphs, leaving dynamic graph generation and temporal validity constraints to be addressed.

Abstract

from arXiv · show

Graphs are important data representations for describing objects and their relationships, which appear in a wide diversity of real-world scenarios. As one of a critical problem in this area, graph generation considers learning the distributions of given graphs and generating more novel graphs. Owing to their wide range of applications, generative models for graphs, which have a rich history, however, are traditionally hand-crafted and only capable of modeling a few statistical properties of graphs. Recent advances in deep generative models for graph generation is an important step towards improving the fidelity of generated graphs and paves the way for new kinds of applications. This article provides an extensive overview of the literature in the field of deep generative models for graph generation. Firstly, the formal definition of deep generative models for the graph generation and the preliminary knowledge are provided. Secondly, taxonomies of deep generative models for both unconditional and conditional graph generation are proposed respectively; the existing works of each are compared and analyzed. After that, an overview of the evaluation metrics in this specific domain is provided. Finally, the applications that deep graph generation enables are summarized and five promising future research directions are highlighted.

1 INTRODUCTION

Graph generation learns distributions over observed graphs to produce novel graphs, addressing limitations of hand-crafted models. This survey organizes deep graph generation methods, evaluation procedures, applications, and open research directions.

  • Graph generation focuses on learning distributions of observed graphs and generating novel graphs, distinct from prediction and analysis tasks.
  • Traditional random, small-world, stochastic block, and Bayesian network models rely on structural assumptions and model only selected graph families.
  • Deep generative models aim to learn from observed graphs, improving generated-graph fidelity and supporting applications such as drug discovery and protein structure modeling.
  • Challenges: Graph generation faces non-unique representations, complex dependencies, large output spaces, discrete objects, and difficult evaluation of implicit properties.
  • Survey contributions: The survey proposes taxonomies, compares methods and base models, categorizes evaluation metrics and benchmarks, reviews applications, and identifies future research directions.
  • Survey perspective: Its graph-specific perspective extends beyond backbone-based categorization by considering task formulation and graph-generating techniques.

2 UNCONDITIONAL DEEP GENERATIVE MODELS FOR GRAPH GENERATION

Unconditional deep graph generation learns pmodel(G) from observed graphs and is organized into sequential and one-shot paradigms. Sequential methods model local dependencies through ordered generation, while one-shot methods generate graph representations synchronously, with different scalability and expressiveness trade-offs.

  • Sequential generating: Sequential generation produces nodes and edges one by one or group by group, conditioning each step on the already generated subgraph.It represents a graph as a sequence of generation units and naturally models complex local dependencies.
  • Node-sequence-based: Node-sequence-based methods generate each node together with its associated edges, using a predefined node ordering and typically decomposing each unit into node and edge-generation steps.Collective associated-edge generation predicts all candidate edges for a new node simultaneously, whereas progressive generation creates them successively.
  • Node-sequence-based: Hierarchical RNN architectures can model node and associated-edge distributions with outer and inner recurrent networks, while MPNNs update representations of the generated subgraph.The node distribution is parameterized separately from the associated-edge distribution, whose entries can be modeled through dependent Bernoulli variables.
  • Comparisons: O(N^2) is common for node-sequence methods, whereas O(|E|) is typical for edge-sequence methods, making the latter more scalable for sparse graphs.Edge-list-based methods can handle larger graphs with simpler global patterns, while expressive approaches may incur memory and time inefficiency.
  • One-shot generating: Adjacency-matrix-based one-shot methods map latent embeddings directly to adjacency and attribute matrices or tensors, trading off expressive power against efficient mapping.MLP-based models output graphs simultaneously, message-passing and transposed-convolution approaches explicitly model higher-order correlations, and invertible transformations impose expressiveness limitations.
  • Edge-list-based: Random-walk-based edge-list generation learns random-walk distributions, counts edge frequencies in generated walks, and converts those counts into edge probabilities.Compared with adjacency-matrix-based and node-similarity-based edge-list generation, it is described as more scalable because edges are sampled from walk-derived probabilities.

3 CONDITIONAL DEEP GENERATIVE MODELS FOR GRAPH GENERATION

Conditional graph generation learns pmodel(G|y) from graphs paired with auxiliary information, while graph transformation translates source graphs into target graphs. The survey distinguishes transformation settings and compares node-edge co-transformation strategies by how they use input graphs and the magnitude of graph changes they support.

  • Conditional generation learns graph distributions from observed graphs paired with auxiliary information such as labels, semantic context, or graphs from other domains.
  • Graph transformation translates a source graph into a target graph, with surveyed methods divided into edge transformation and node-edge co-transformation.
  • 3.1.1 Edge transformation: Edge transformation changes target edges and edge attributes while keeping the node set and node attributes fixed.
  • 3.1.2 Node-edge co-transformation: Node-edge co-transformation changes both node and edge attributes between source and target graphs, using embedding-based or editing-based techniques.
  • 3.1.2 Node-edge co-transformation: Embedding-based NECT encodes the source graph into latent representations and decodes the target graph, whereas editing-based NECT iteratively modifies the input graph.
  • 3.1.2 Node-edge co-transformation: Embedding-based NECT captures global input patterns and supports sophisticated changes, while editing-based NECT is more suitable for small changes because of efficiency.

4 EVALUATION METRICS FOR DEEP GRAPH GEN-

Evaluating deep graph generation requires comparing learned graph distributions and handling graph structure that is harder to assess than vector or matrix data. The survey organizes evaluation into statistics-based, classifier-based, intrinsic-quality-based, and conditional-generation-specific metrics.

  • Graph-generation evaluation is challenging because models learn distributions rather than deterministic predictions, while graph structure is difficult to evaluate.
  • Statistics-based, classifier-based, and intrinsic-quality-based metrics form the three broad categories for evaluating generated graphs.
  • 4.1.1 Statistics-based: Statistics-based evaluations compare graph-statistic distributions between generated and real graph sets, whereas intrinsic-quality metrics directly measure generated-graph properties.
  • 4.1.1 Statistics-based: Distribution-valued graph statistics are compared using average Kullback-Leibler divergence, Maximum Mean Discrepancy, or Wasserstein distance.
  • 4.1.2 Classifier-based: Classifier-based evaluation trains a graph classifier on real graphs and tests whether generated graphs are classified consistently with their graph types.
  • 4.1.3 Intrinsic-quality-based: Intrinsic-quality evaluation includes validity, uniqueness, and novelty, while conditional generation can additionally assess graph properties and condition-to-graph mapping relationships.

5 APPLICATIONS

Deep graph generation supports applications in molecular design, protein structure modeling, semantic parsing, code modeling, and SAT-instance generation. These applications represent domain objects as graphs and use sequential, one-shot, or motif-based generation strategies tailored to their structures and constraints.

  • Applications include molecule optimization and generation, semantic parsing, code modeling, and pseudo-industrial SAT-instance generation.
  • 5.1 Molecule generation: JT-VAE decomposes a molecular graph into a junction tree of molecular substructures, encodes the tree and graph, then reconstructs the tree before assembling the molecule.
  • 5.2 Protein structure modeling: CO-VAE represents protein structures as graphs whose nodes are amino acids and whose edges reflect pairwise physical distances, then generates node and edge attributes with a VAE.
  • 5.3 Semantic parsing: AMR parsing is formulated as sequence-conditioned graph generation, mapping sentence tokens to nodes and semantic relationships to edges.
  • 5.4 Code modeling: Code modeling represents source code as an abstract syntax tree whose nodes are code constructs and whose edges encode semantic relationships.
  • 5.5 SAT instance generation: G2SAT represents SAT formulas as bipartite graphs of literals and clauses, generating new motifs sequentially in the partially constructed graph.

6 FUTURE OPPORTUNITIES

Future work centers on scaling deep graph generation, enforcing graph validity, improving interpretability and novelty, and extending models to dynamic graphs.

  • Scalability: Existing models typically have super-linear node complexity, so most studies focus on graphs ranging from dozens to thousands of nodes.Only a few methods achieve O(N) or O(M) time complexity.
  • Validity constraint: Discrete, non-differentiable validity constraints remain difficult to enforce during training, and smooth relaxations can introduce errors.Examples include molecular valency and gene-ontology constraints in protein interaction networks.
  • Interpretability: Graph-generation research has barely explored interpretable latent variables that control generated properties or disentangle local dependencies among subgraphs.Existing interpretability work has focused mainly on graph embedding rather than generation.
  • Beyond training data: Novelty beyond training data is constrained by the data and model properties, while graph-generation methods for controllable novelty remain lacking.The survey notes that graph generation may require techniques different from those used for image generation.
  • Dynamic graphs: Dynamic graph generation remains largely unexplored despite evolving node attributes and topology in social, mobility, and protein-folding networks.Future models must jointly address temporal patterns, graph patterns, and temporal validity constraints.

7 CONCLUSION

The survey systematically reviews deep generative models for graph generation, covering their architectures, evaluation, applications, and open research directions. It explains representative generative paradigms including VAEs, GANs, RNNs, and normalizing flows.

  • Survey scope: The survey develops a systematic review and taxonomy of deep graph generative models, compares methods, reviews evaluation measures, and summarizes applications.It addresses both unconditional and conditional graph generation.
  • Variational auto-encoders: VAEs combine a top-down generator with a bottom-up inference network and train by optimizing a tractable evidence lower bound.The encoder uses qφ(z|x), while the decoder uses pθ(x|z).
  • Generative adversarial nets: GANs train a generator and discriminator adversarially, with the generator producing samples and the discriminator distinguishing real from fabricated data.Alternating optimization seeks generated samples that are difficult for the discriminator to distinguish from real samples.
  • Generative adversarial nets: GANs can produce high-quality objects but may be difficult to train, suffer mode collapse, and require substantial computation for alternating optimization.Mode collapse limits diversity, while convergence can be prolonged.
  • Generative RNNs: RNN-based generators model sequences by predicting each next element from previously generated elements and sampling from the resulting predictive distributions.Training maximizes the total log likelihood of the sequence.
  • Normalizing flows: Normalizing flows use an invertible transformation between a latent space and observation space to calculate exact likelihoods and generate samples.Sampling first draws z from pz(z), then computes x=fθ(z); efficient operations require an easily computable Jacobian determinant.

APPENDIX B BENCHMARK RESULTS AND DATASETS

Because deep graph generation is relatively new, the survey emphasizes quantitative comparison of existing algorithms and unified benchmark datasets for future research.

  • Benchmark results and datasets: The survey summarizes benchmark datasets and compares published deep graph generation results using evaluation metrics introduced earlier.The benchmark discussion is intended to support quantitative comparison across existing and future algorithms.

B.1 Datasets

Benchmark datasets for deep graph generation are categorized into synthetic and real-world datasets and made publicly available by the authors.

  • Datasets: Existing benchmark datasets are categorized into synthetic datasets and real-world datasets.The authors state that all collected datasets are published through their dataset repository.

B.1.1 Synthetic Datasets

The survey describes synthetic graph datasets spanning community, grid, ego, preferential-attachment, cyclic, tree, and ladder structures, with varied graph sizes and construction rules.

  • Community contains 500 two-community graphs with 60 ≤|V| ≤160, generated from two Erdős–Rényi communities with link probability p = 0.3.
  • Grid includes 100 standard 2D grid graphs of 100–400 nodes and 100 large 2D grid graphs of 1296–2025 nodes.
  • Ego contains 757 three-hop Citeseer ego networks with 50 ≤|V| ≤399, where nodes are documents and edges represent citations.
  • B-A contains 500 Barabási–Albert graphs with 100 ≤|V| ≤200, connecting each new node to 4 existing nodes.
  • Cycles, Trees, and Ladder provide 500 cyclic graphs, 500 power-law trees, and 180 ladder graphs, generally ranging from 10 to 100 nodes.

B.1.2 Real-world Datasets

The survey catalogs real-world graph datasets from molecular, protein, enzyme, and citation domains, differing in size, structural complexity, and node or edge semantics.

  • QM9 enumerates around 134k stable organic molecules with up to 9 heavy atoms and no filtering beyond basic structural constraints.
  • ZINC contains 250k curated drug-like compounds averaging about 23 heavy atoms and greater structural complexity than QM9.
  • CEPDB contains photovoltaic-focused organic molecules averaging 28 heavy atoms and six to seven rings each.
  • Protein contains 918 graphs with 100 ≤|V| ≤500, representing amino acids as nodes and proximity within 6 Angstroms as edges.
  • Enzymes contains 600 protein tertiary-structure graphs whose nodes are secondary-structure elements and whose labels identify helices, turns, or sheets.
  • Cora and Citeseer are citation networks with publications as nodes, citation links as edges, and publication areas as node labels.Cora has 2708 nodes and 5429 edges; Citeseer has 3327 nodes and 4732 edges.

B.2 Results

The survey compares deep graph-generation methods across domain-agnostic and domain-aware tasks, including general graph synthesis and molecule structure generation, using published evaluations.

  • Table 4 compares published quantitative results for general graph-generation tasks using metrics for node degree, clustering coefficients, and average orbit counts.
  • Table 5 evaluates molecule structure generation using motif count, node count, uniqueness, novelty, and validness.
  • The survey divides graph-generation evaluation into domain-agnostic tasks without domain knowledge and domain-aware tasks requiring validity and property constraints.

B.2.1 Results on Domain-agnostic Graph Generation

For domain-agnostic graph generation, the survey finds that sequential models generally outperform one-shot models, attention-based recurrent models perform strongly on Protein, and permutation-invariant strategies can improve scalability.

  • Comparison between sequential-based and one-shot-based graph generation for domain-agnostic graphs: Sequential methods, especially RNN-based models, outperform one-shot models on many benchmark datasets.
  • Comparison between sequential-based and one-shot-based graph generation for domain-agnostic graphs: GraphVRNN achieves the lowest Community MMD at 0.025 on average, versus 0.246 for other methods, while GraphRNN achieves the lowest Ego MMD at 0.017 versus around 0.060.
  • Influence of the attention mechanism on graph generation: On Protein, attention-based recurrent models GRAN and GRAN-I obtain the smallest average MMD scores, 0.063 and 0.046, respectively.
  • Influence of the attention mechanism on graph generation: Attention helps distinguish newly added nodes and learn different weights for edge types during generation.
  • Experimental comparisons of complexity: Most methods have O(N^2) complexity, while permutation-invariant strategies such as GRAN can improve sequential generation from O(N^2) to O(N · |E|).
  • Experimental comparisons of complexity: The survey attributes the complexity challenge primarily to node permutation during loss calculation, while one-shot adjacency-matrix representations remain limited to O(N^2).

B.2.2 Results on Domain-aware Graph Generation

Domain-aware graph generation emphasizes valid and diverse molecules, with molecule generation commonly evaluated on QM9 and ZINC. Incorporating domain-specific knowledge improves validity and uniqueness by directly optimizing application-specific objectives while satisfying chemical rules.

  • Molecule generation is the most widely explored domain-aware graph generation task, with 13 models compared on QM9 and ZINC.
  • Domain-specific knowledge improves the validity and uniqueness of generated molecules through learning rewards or regularization.These mechanisms support direct optimization of application-specific objectives while maintaining realistic molecules that satisfy chemical rules.
  • On ZINC, JT-VAE achieved 100% uniqueness, about 26.41% higher than the average of the other methods.

Experimental comparison of complexity on molecule

For molecule generation, motif-sequential methods provide the lowest complexity, while sequential methods generally improve molecular uniqueness, novelty, and validity over one-shot approaches. Their advantages arise from modeling variable graph sizes and generating structures from coarse-grained motifs.

  • Motif-sequential methods achieved the lowest generation complexity, with JT-VAE and GCPN reaching O(C), where C is the number of motifs.Grouping nodes into motifs reduces the number of generation iterations.
  • On ZINC, sequential methods achieved average uniqueness of 81.99% and validity of 86.16%, exceeding one-shot methods by 12.34% and 26.84%.
  • Sequential generation models variable graph sizes, while motif-based generation reduces invalid results by constructing graphs from coarse-grained motifs.
Loading 2007.06686v3…