Source-linked AI summary
GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders
Martin Simonovsky, Nikos Komodakis
TL;DR
The paper asks whether generative-model progress can transfer to graphs, where discrete structure and arbitrary connectivity make generation difficult. GraphVAE uses a variational autoencoder whose decoder directly outputs a probabilistic fully-connected graph, and evaluates it on molecule generation, achieving reasonable embeddings for small molecules but struggling with larger chemical interactions.
Problem
Graph research had emphasized graph embeddings rather than decoding graphs from vectors, while graph discreteness and arbitrary connectivity complicate gradient-based generation.
Method
GraphVAE encodes graphs into continuous latent representations and directly decodes them as probabilistic fully-connected graphs using a variational autoencoder.
Results
GraphVAE achieved reasonable-quality embeddings on small molecules, while its decoder struggled to capture complex chemical interactions in larger molecules.
Takeaways & Limitations
The method is presented as an initial step toward more powerful graph decoders and is evaluated on molecule generation.
Takeaways & Limitations
The model is expected to be useful only for small graphs because memory and parameter costs grow as O(k^2) and matching complexity as O(k^4).
Abstract
from arXiv · showhide
Deep learning on graphs has become a popular research topic with many applications. However, past work has concentrated on learning graph embedding tasks, which is in contrast with advances in generative models for images and text. Is it possible to transfer this progress to the domain of graphs? We propose to sidestep hurdles associated with linearization of such discrete structures by having a decoder output a probabilistic fully-connected graph of a predefined maximum size directly at once. Our method is formulated as a variational autoencoder. We evaluate on the challenging task of molecule generation.
1. Introduction
GraphVAE addresses the difficulty of generating discrete graphs by decoding a continuous representation directly into a probabilistic graph. The authors evaluate this VAE-based approach on molecule generation, while noting scope and performance limitations.
- Graph learning had focused mainly on encoding graphs into vector representations, unlike advances in generative models for images and text.
- Graph generation is difficult because graphs are discrete, can have arbitrary connectivity, and lack a canonical construction sequence.Learning construction order also involves nondifferentiable discrete decisions.
- GraphVAE decodes a continuous representation into a probabilistic fully-connected graph of predefined maximum size directly at once.The method models node and edge existence and attributes as independent random variables within a variational autoencoder.
- The method is demonstrated on molecule generation, but it is intended for smaller graphs and its performance still leaves room for improvement.
2. Related work
Related graph-generation work includes incremental probabilistic construction and image-conditioned scene-graph prediction, while GraphVAE generates graphs from continuous vectors without a prescribed construction order. Molecular generation has often relied on SMILES, whereas the proposed decoder operates directly on graph structure.
- Johnson incrementally constructs probabilistic multigraphs from input sentences, whereas GraphVAE uses an autoencoder without a prescribed transformation order.
- Xu et al. generate scene graphs from image object proposals using node and edge embeddings with message passing, unlike GraphVAE’s vector-to-graph generation.
- Earlier graph-generation approaches include random graphs, stochastic blockmodels, and state transition matrix learning.
- GraphVAE’s decoder outputs a probabilistic graph directly, while text-generation methods commonly use teacher forcing to avoid backpropagation through output discretization.
- Molecule-generation research has often used SMILES strings with fixed syntax to exploit progress in recurrent text generation.
3. Method
GraphVAE translates continuous latent codes into probabilistic graphs without imposing a node-construction order. It uses graph matching to align variable-sized inputs with dense decoder outputs, while remaining computationally limited to small graphs.
- Core approach: GraphVAE formulates graph generation as a variational autoencoder that translates continuous codes into probabilistic fully-connected graphs.The decoder outputs node and edge existence probabilities and attribute distributions for a predefined maximum of k nodes.
- Core approach: The decoder outputs the graph directly at once, avoiding sequence linearization despite arbitrary graph connectivity.Dense representations remain tractable when graphs are restricted to a fairly small maximum size.
- Graph alignment: Graph matching aligns decoder outputs with unordered input graphs before likelihood computation and reconstruction-loss optimization.The assignment maps input adjacency and attributes into corresponding predicted tensors, enabling comparison despite permutation-dependent matrix representations.
- Reconstruction loss: The reconstruction loss averages node and edge contributions separately because otherwise the larger number of edges dominates the likelihood.The formulation includes matched and unmatched node and edge existence, but attributes only for matched elements.
- Graph alignment: Max-pooling matching produces continuous assignments that are discretized with the Hungarian algorithm into a strict one-to-one mapping.The non-differentiable discretization did not prevent gradient flow through the loss or training convergence.
- Scope: The model is intended only for small graphs because parameter and GPU-memory growth is O(k^2), while matching complexity is O(k^4).The reported demonstrations reach k = 38, with a small decrease in quality for high values of k.
4. Evaluation
GraphVAE is evaluated for molecule generation on QM9 and ZINC using chemical validity, label accuracy, novelty, variety, and reconstruction-related measures. The method performs well on smaller graphs, while larger graphs expose scalability and validity challenges.
- Model remedies: The decoder predicts symmetric graph tensors, enforces connectivity with a test-time maximum spanning tree, and omits explicit hydrogen generation.Only upper-triangular portions are predicted for undirected molecular graphs, and hydrogen is added as padding.
- QM9 results: About 60% of generated molecules are outside the training dataset across models.These samples are counted as out-of-dataset molecules that the network had not seen during training.
- QM9 results: GraphVAE combines validity and variety better than GVAE and the NoGM ablation, although GVAE reaches 60% validity with less than 10% variance.NoGM produces many valid samples with lower variety, whereas GraphVAE performs well on both metrics simultaneously.
- QM9 results: Table 2 improves Valid, Accurate, and Novel metrics in both conditional and unconditional settings, but lowers variability and increases reconstruction loss.The authors interpret this trade-off as evidence that the added constraint is useful but not fully handled by the model.
- ZINC results: On ZINC, GraphVAE obtains Valid = 0.135, compared with GVAE's Valid = 0.357, while CVAE generates no valid samples.Restricting graphs to at most 20 nodes raises GraphVAE Valid to 0.341; at most 30 nodes yields Valid = 0.185.
- Matching robustness: Matching remains fairly robust as graph size increases at fixed noise, so the authors conclude it is not a major scalability bottleneck.Accuracy decreases with stronger noise, with adjacency being the most sensitive tensor.
5. Conclusion
The method addresses graph generation from continuous embeddings using VAEs and performs reasonably on small molecules, but struggles with complex interactions in larger molecules. The authors frame it as an initial step toward more powerful graph decoders and future chemistry applications.
- The method generates graphs from continuous embeddings in a variational-autoencoder framework and was evaluated on two molecular datasets with different maximum graph sizes.
- The decoder learns reasonable embeddings for small molecules but has difficulty capturing complex chemical interactions in larger molecules.
- The authors identify stronger priors and recurrent error-correction mechanisms as directions for improving the current method.
- Graph-based decoding could support predicting detailed atom and bond attributes alongside molecular structure for chemistry tasks such as property optimization or reaction prediction.
A. Max-Pooling Matching
The max-pooling matcher estimates soft node correspondences by optimizing pairwise similarities, then iteratively updates assignments using normalized similarity propagation. Max-pooling emphasizes the best neighbor match rather than aggregating all neighbors.
- The relaxed matcher represents correspondences with a continuous matrix X* in [0, 1]^(k×n), based on similarities between node pairs.
- The relaxed matching problem maximizes quadratic correspondence similarity subject to assignment constraints on x.
- The optimization uses a power-method update that repeatedly applies Sx and normalizes the result, starting from uniform correspondences.In the authors’ use case, the iterations run for a fixed number of steps.
- Max-pooling updates each candidate using its own similarity plus only the best pairwise similarity from each neighboring node.This is proposed as a more robust alternative to sum-pooling, which can be influenced by irrelevant elements.
B. Unregularized Autoencoder
The unregularized autoencoder isolates reconstruction capacity by removing VAE regularization. On QM9, test log-likelihood improves but remains imperfect, with overfitting limited to tiny fixed training sets.
- VAE regularization opposes perfect reconstruction, especially when the embedding size is small.
- The experiment removes the KL-divergence term and uses a deterministic encoder to evaluate reconstruction ability directly.
- −0.37 mean test log-likelihood log pθ(G|z) is achieved by unconditional QM9 models across embedding sizes c ∈ {20, 40, 60, 80}.The implicit node probability model achieves about −0.50.
- Training log-likelihood reaches zero only on fixed small datasets of hundreds of examples, indicating difficulty learning generally valid output-assembly rules.