Source-linked AI summary
Learning Deep Generative Models of Graphs
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, Peter Battaglia
TL;DR
Graph generation needs models that capture richly structured relational data without the restrictive assumptions of random graph models or the brittleness of graph grammars. The paper generates graphs sequentially with graph nets, achieving strong results on synthetic and molecular tasks, while identifying ordering and sequence length as limitations.
Problem
Existing graph models either make strong structural assumptions or are brittle and difficult to learn, limiting expressive probabilistic modeling of richly structured graphs.
Method
The model sequentially adds nodes and edges, using graph nets to parameterize node addition, edge addition, and node-selection decisions from the evolving graph.
Results
The model performs well across synthetic and molecular graph-generation experiments and outperforms random graph models and LSTM baselines.
Takeaways & Limitations
Graph neural networks provide a flexible basis for generating arbitrary graphs, including unconditional and conditional molecular graphs.
Takeaways & Limitations
The approach relies on predefined node and edge orderings, while learning an ordering remains future work; its decision sequences can also be 2–3x longer than SMILES sequences.
Abstract
from arXiv · showhide
Graphs are fundamental data structures which concisely capture the relational structure in many important real-world domains, such as knowledge graphs, physical and social interactions, language, and chemistry. Here we introduce a powerful new approach for learning generative models over graphs, which can capture both their structure and attributes. Our approach uses graph neural networks to express probabilistic dependencies among a graph's nodes and edges, and can, in principle, learn distributions over any arbitrary graph. In a series of experiments our results show that once trained, our models can generate good quality samples of both synthetic graphs as well as real molecular graphs, both unconditionally and conditioned on data. Compared to baselines that do not use graph-structured representations, our models often perform far better. We also explore key challenges of learning generative models of graphs, such as how to handle symmetries and ordering of elements during the graph generation process, and offer possible solutions. Our work is the first and most general approach for learning generative models over arbitrary graphs, and opens new directions for moving away from restrictions of vector- and sequence-like knowledge representations, toward more expressive and flexible relational data structures.
1. Introduction
The paper introduces an expressive graph generative model that avoids structural assumptions and grammar brittleness by generating graph structure sequentially with graph neural networks. It performs well on synthetic and molecular graph generation, outperforming random graph and LSTM baselines across experiments.
- Graph representations support applications including discovering molecular configurations, modeling semantic graph distributions, and providing priors for Bayesian structure learning.
- Random graph models make strong independence assumptions and capture limited properties, while graph grammars are expressive but difficult to learn and brittle.
- The proposed model avoids structural assumptions and grammar brittleness by adding nodes or edges sequentially, with probabilities conditioned on the derivation history.
- Graph-structured neural networks represent the evolving graph during generation and express dependencies among its structural elements.
- The model performs well for synthetic topological graph generation and unconditional or conditional molecule generation, outperforming random graph models and LSTM baselines.
2. Related Work
Related work spans random graph models, graph grammars, tree-generation systems, and graph neural networks. The paper distinguishes its goal—learning graph densities—from approaches that use graphs primarily for reasoning or impose strong generation assumptions.
- Early random graph models provide mathematical foundations but are too simplistic for graphs that violate independent-edge assumptions.
- Grammar-based and neural methods have modeled trees for language, source code, and molecule structures using recursive, sequence, or transition-based generation.
- RNN language models combined robustness, expressiveness, and learnability compared with formal grammars and n-gram models.
- Graph nets learn graph, node, and edge representations through information propagation with graph-size-independent parameters and invariance to graph isomorphism.
- Unlike reasoning-oriented graph construction, this work learns unconditional or conditional graph densities from representative graph datasets.
3. The Sequential Graph Generation Process
The model generates graphs as sequential structure-building decisions: it adds nodes, repeatedly creates needed edges, and can terminate at each stage. Graph nets parameterize these decisions using the partial graph’s structure.
- The generation process adds one node at a time and connects it to the existing partial graph through one-by-one edge creation.
- Each iteration samples whether to add a node or terminate, initializes the node, and repeatedly decides whether and where to add connecting edges.
- The process can model directional or typed edges and impose constraints such as forbidding self-loops or multiple edges.
- Generation consists of add-node, add-edge, and node-selection decisions parameterized by faddnode, faddedge, and fnodes.
- Graph nets replace conventional LSTM sequence modeling so decision probabilities are more sensitive to the structures being constructed.
4. Learning Graph Generative Models
The model uses graph-net propagation and aggregation to represent partial graphs, then predicts node addition, edge addition, and node selection probabilities. Training and evaluation must address the intractable sum over node and edge orderings.
- Graph-net propagation computes edge messages and updates node embeddings by aggregating information from local neighborhoods.
- The implementation uses GRU-based node updates, with LSTM and GRU cores reported to perform similarly.
- Graph-level representations aggregate node embeddings using a gated sum, with mean or max as alternative reduce operators.
- The faddnode module predicts termination or node-type choices, while fnodes scores existing nodes and normalizes connection choices with a softmax.
- New node states combine node features with an aggregated graph representation, which can disambiguate identical inputs added at different generation stages.
- Conditional generation adds conditioning information to selected modules; these experiments provide it only to node-state initialization.
- The model’s graph marginal sums over all orderings, making exact likelihood intractable for moderately large graphs and requiring sampling or approximation.
- Training maximizes expected joint log-likelihood using a chosen ordering proposal, aligning training with evaluation and improving marginal-probability estimation.
5. Experiments
The experiments evaluate graph generative models on synthetic topologies and molecules, comparing graph-structured generation with LSTM and other baselines. Results show strong adaptation to varied graph distributions, competitive molecular likelihood, and substantially better validity and novelty in several settings.
- Experimental setup: The model is tested on cycles, trees, Barabási–Albert graphs, and molecular graphs using unconditional and conditional generation tasks.Synthetic graphs test adaptation to differing topological properties, while molecule experiments use typed nodes and edges from ChEMBL.
- Synthetic graph generation: Graph nets outperform the LSTM baseline asymptotically on training curves for the synthetic graph-generation tasks.The comparison uses similar-sized models, with 32k parameters for the graph model and 36k for the LSTM.
- Synthetic graph generation: The same graph model matches cycles, trees, and Barabási–Albert training distributions well while adapting to their different characteristics.Evaluation uses validity for cycles and trees and KL divergence between degree distributions for Barabási–Albert graphs.
- Molecule generation: In molecule generation, the graph model produces significantly more valid and novel samples than LSTM models, although SMILES LSTM has a slight canonical-ordering likelihood advantage.Under the generic graph-generation decision sequence, the graph model also outperforms LSTM in NLL.
- Molecule generation: On small molecules, random-order graph training yields better marginal likelihood, while canonical training orderings are not always optimal.These results suggest potential value in learning the ordering rather than fixing it in advance.
- Molecule generation: The molecule model achieves 89.2% validity with canonical ordering and 74.3% with random ordering, with fewer than 0.1% duplicate training samples.The experiments compare graph generation against GrammarVAE and other molecular-generation baselines.
6. Discussions and Future Directions
The proposed graph model can generate arbitrary graphs, but its use raises challenges involving ordering, sequence length, scalability, and training stability.
- Ordering: Node and edge ordering is critical for both learning and evaluation, with predefined ordering distributions used in the experiments.The paper suggests learning the ordering as a latent variable as a future direction.
- Long Sequences: Graph generation typically requires a long sequence of decisions, making likelihood estimation and training more difficult than with shorter linearizations.Domain-specific modifications could reduce multiple decision steps and loops to single steps.
- Scalability: Scalability is limited because large graphs require more propagation steps for sufficient information flow in the graph nets.The paper suggests sequential edge sweeps or coarse-to-fine generation as possible solutions.
- Difficulty in Training: Training is more difficult than for typical LSTM models because long sequences and changing model structure lead to unstable training.Lowering the learning rate resolves many instability problems, while more satisfying solutions remain possible through model modifications.
7. Conclusion
The paper presents a deep generative model that generates arbitrary graphs through a sequential process. It reports promise on graph-generation problems and advantages over standard LSTM models.
- The proposed deep generative model generates arbitrary graphs through a sequential process.
- The model shows promise on several graph-generation problems and advantages over standard LSTM models.
- The graph generation process is documented in Algorithm 1.
- Different node and edge orderings can produce distinct decision sequences for the same graph.
B. Model Implementation Details
The implementation represents graph-generation decisions with graph neural networks and computes graph, node, and edge states through propagation and aggregation. Training evaluates graph likelihood under specified canonical or random orderings.
- Graph and node representations are updated through message passing using neural message functions and recurrent node-update cells.
- A gated sum aggregates transformed node representations into a graph representation vector, and it performs consistently better than a simple sum.
- The faddnode module predicts whether and what type of node to add, while faddedge predicts whether to add another edge.
- The model represents graph generation as sequential decisions to add nodes, add edges, and select edge endpoints.
- New node states combine node-type or feature inputs, a summary of the current graph, and optional conditioning information.
- Training maximizes expected joint likelihood over graphs and node-edge orderings, using either canonical or uniform random ordering.
C. More Experiment Details and Results
The supplementary experiments specify optimization settings for the evaluated models. Learning rates were selected from a small candidate set and Adam was used throughout.
- One experiment uses an LSTM hidden size of 64, graph node states of 16, and T = 2 propagation steps.
- The supplementary experiments use Adam optimization for both model classes.
- Learning rates were selected from {0.001, 0.0005, 0.0002} on each of the three datasets.
C.2. Molecule Generation
Molecule-generation experiments compare chemical-property distributions, ordering strategies, and controllable generation biases. The graph model matches training distributions well, while ordering affects overfitting and bias controls alter molecule size and edge density.
- Molecule property distributions: The models generate 100,000 samples each, whose chemical-metric histograms are compared with the training set using KL divergence.
- Molecule property distributions: All models match the training distributions on the examined chemical metrics fairly well.
- Molecule property distributions: Graph and LSTM models trained on permuted node and edge sequences show biases toward higher SA scores, while the graph model also favors larger molecules.
- Controllable generation: Changing the faddnode bias shifts the distribution of atom counts while retaining a high percentage of valid samples.
- Controllable generation: Changing the faddedge bias shifts bond counts and edge density, with molecule size changes partly compensating for the bias.
- Ordering effects: Uniform random ordering rarely overfits, whereas canonical ordering overfits more quickly but makes learning harder.
- Ordering effects: Models trained with canonical ordering may assign higher probabilities to orderings near, rather than exactly at, the canonical ordering.
C.3. More Details on Comparison with Previous Approaches
The Zinc comparison reports complete sample-quality results for the graph models and prior approaches, alongside qualitative samples examining what the models learned. The study also notes a validity discrepancy for GrammarVAE based on its provided implementation.
- Quantitative comparison: Table 5 compares graph models trained with fixed and random orderings against CVAE, GrammarVAE, and GraphVAE on Zinc sample quality.The prior-model results came from pretrained models or reported results identified in the table caption.
- Quantitative comparison: The reported GrammarVAE validity figure is 34.9% in this study, while earlier sources reported 7.2% and 35.7% for GrammarVAE.The authors state that their 34.9% figure was obtained using the provided code and pretrained model, and that many valid samples were empty or invalid strings under their analysis.
- Experimental setup: The graph models in this experiment use the same hyperparameter range as the ChEMBL experiment.This specifies the tuning relationship but does not report a separate performance result.
C.4. More Details about the Conditional Molecule Generation Tasks
The conditional molecule-generation experiment trains on molecules with selected aromatic-ring counts and evaluates interpolation and extrapolation to unseen counts. Conditioning vectors are normalized and transformed before entering the graph or LSTM models.
- Conditioning mechanism: The 3-D conditioning vector c is normalized, linearly mapped to 128 dimensions, and passed through tanh before being fed into the models.For the graph model, the resulting vector is concatenated with other inputs; for LSTMs, it is mapped to hidden-state and cell-state vectors.
- Data and evaluation: The models train on 30,000 ChEMBL molecules with 0, 1, or 3 aromatic rings and evaluate interpolation or extrapolation to molecules with 2 or 4 rings.The training set contains 10,000 randomly selected molecules for each of the 0-, 1-, and 3-ring settings.
- Data and evaluation: Evaluation samples 10,000 conditioning vectors from the training set, 2-ring molecules, and 4-ring molecules, with the latter two sets withheld from training.The three conditioning-vector sources distinguish seen conditions from the two unseen ring-count settings.
C.5. Extra Conditional Generation Task: Parsing
The parsing experiment evaluates conditional graph generation of parse trees from natural-language sentences against LSTM baselines. The graph model outperforms the LSTM using generic graph-generation decisions but trails the LSTM on sequentialized trees, while limited propagation and harder training constrain its use.
- Task and evaluation: The task generates parse trees conditioned on Wall Street Journal sentences, with results reported on the Eval set.Table 6 reports perplexity and exact tree-match sample quality for the compared models.
- Task and evaluation: The graph model uses top-down depth-first ordering and is additionally evaluated with breadth-first traversal ordering.LSTM sequence-to-sequence baselines are trained on sequentialized trees and on the graph model’s decision sequences, with attention used for conditioning.
- Results: The LSTM on sequentialized trees performs better on both metrics, while the graph model beats the LSTM trained on the same generic graph-generation decision sequences.The metrics are length-normalized perplexity and exact ground-truth parse-tree matching.
- Limitations: The graph model runs T = 2 propagation steps, limiting how quickly remote tree regions can receive information about structural changes.Increasing T can extend information flow but increases computation and training difficulty; T = 2 is presented as a balance for this task.
- Limitations: Graph-model training is harder than LSTM training because the graph structure and model structure change during the longer decision sequence.The stated limitation concerns the interaction between changing graph structure, propagation, and training complexity.
- Model details: The graph model uses 64-dimensional node states, while the LSTM encoder has hidden size 256 and baseline encoder-decoder LSTMs use hidden size 512.These are the selected model details for the parsing experiment.
- Model details: The graph model’s propagation depth was selected from T ∈ {1, 2, 3, 4, 5}, balancing representation quality against computation and instability.The authors selected T = 2 for this task.
- Ordering analysis: Figures 11 and 12 visualize step-by-step generation under canonical and permuted random node orderings.Figure 13 shows the negative log-likelihood distribution under different orderings for one small molecule trained with canonical ordering.