Source-linked AI summary
Constrained Generation of Semantically Valid Graphs via Regularizing Variational Autoencoders
Tengfei Ma, Jie Chen, Cao Xiao
TL;DR
Graph generative models struggle to enforce semantic validity, such as molecular valence and node-type compatibility. The paper regularizes VAE decoder distributions in a matrix-based graph representation, and reports substantially higher valid-graph sampling rates, including 98.4% versus 40.2% on node-compatible graphs.
Problem
Graph generative models have difficulty incorporating contextual validity constraints, including molecular valence and compatibility between connected protein types.
Method
The framework regularizes matrix-based VAE decoder distributions with penalty terms for validity constraints over node and edge labels.
Results
98.4% valid graphs were sampled by the regularized method versus 40.2% for the standard VAE on the node-compatible dataset.
Takeaways & Limitations
The framework encourages semantic validity across molecular-graph and node-compatible-graph generation tasks.
Takeaways & Limitations
The probabilistic graph model assumes independence when assigning probabilities to graph components.
Abstract
from arXiv · showhide
Deep generative models have achieved remarkable success in various data domains, including images, time series, and natural languages. There remain, however, substantial challenges for combinatorial structures, including graphs. One of the key challenges lies in the difficulty of ensuring semantic validity in context. For examples, in molecular graphs, the number of bonding-electron pairs must not exceed the valence of an atom; whereas in protein interaction networks, two proteins may be connected only when they belong to the same or correlated gene ontology terms. These constraints are not easy to be incorporated into a generative model. In this work, we propose a regularization framework for variational autoencoders as a step toward semantic validity. We focus on the matrix representation of graphs and formulate penalty terms that regularize the output distribution of the decoder to encourage the satisfaction of validity constraints. Experimental results confirm a much higher likelihood of sampling valid graphs in our approach, compared with others reported in the literature.
1 Introduction
Deep generative models remain less mature for graphs because graph parameterization must preserve semantic validity. Matrix-based generation also struggles with global properties and application-specific node–edge constraints.
- Graph generation is less mature than generation for continuous data and sequences because efficient parameterization must preserve semantic validity.
- Sequential graph-generation methods insert nodes and edges one by one, but long decision sequences are challenging for large training graphs.
- Sequential approaches also rely on a predefined ordering, leaving the role of permutation unresolved.
- Matrix-based models represent edge and node existence probabilistically, but global properties such as connectivity are hard to control.
- Molecular valence and protein node-type compatibility exemplify constraints requiring valid combinations of nodes and edges.
- The proposed VAE regularization framework penalizes constraint violations in matrix representations and is evaluated on molecule and synthetic node-compatible datasets.
2 Related Work
Prior graph-generation methods use random graph models, matrix reconstruction, sequential paths, or molecular string representations, but general graph expressiveness and semantic validity remain limited.
- Classical Erdős–Rényi and scale-free models describe specific graph properties but lack sufficient expressiveness for richer real-life graphs.
- GraphVAE reconstructs matrix representations, while the proposed work adds regularization to impose semantic constraints on sampled graphs.
- NetGAN generates random paths and assembles them into a graph, learning the connectivity structure of a single graph rather than a graph distribution.
- SMILES-based molecular methods are brittle because small string changes can violate chemical validity, while grammar-based methods guarantee syntax but leave semantic validity questionable.
- The cited molecular-generation methods do not generalize to general graphs.
3 Regularized Variational Autoencoder for Graphs
The paper represents graphs with probabilistic node and edge labels, trains a VAE with an ELBO objective, and adds regularization derived from validity constraints. The formulation marginalizes constraints over latent variables and penalizes only violations during training.
- 3.1 Graph Representation and Probability Model: Graphs use a node-label matrix F and edge-label tensor E, with one-hot entries encoding node and edge types or nonexistence.
- 3.1 Graph Representation and Probability Model: Relaxing one-hot labels to probability vectors makes eG a sampling distribution over graph realizations.
- 3.2 Variational Autoencoder: The generative network decodes latent z into eG, while the inference network approximates the posterior with qφ(z|G).
- 3.2 Variational Autoencoder: The ELBO combines expected reconstruction performance with KL regularization that keeps the variational posterior close to the prior.
- 3.3 Regularization: The regularized VAE objective is motivated by equivalence between constrained optimization and an unconstrained regularized objective under the stated theorem conditions.
- 3.3 Regularization: Validity is required for almost all latent values, so the framework marginalizes squared constraints to eliminate their direct dependence on z.
- 3.3 Regularization: Squaring the constraints is required for the stated if-and-only-if relationship between pointwise and marginalized feasibility.
- 3.3 Regularization: The final loss uses a ramp function g+ = max(g, 0), avoiding penalties for desirable cases where gi(θ, z) ≤0.
4 Constraint Formulation
The framework regularizes decoder outputs to encourage semantically valid graphs, using constraints on node labels and edge labels. It covers ghost-node and valence limits, connectivity, and node-type compatibility.
- 4 Constraint Formulation: The framework imposes regularization constraints on decoder outputs eG=(eF,eE), with node constraints written as gi and edge constraints as gij.Regularization is applied alongside the standard VAE objective using synthetic latent samples.
- 4.1 Ghost Nodes and Valence: Ghost nodes have no incident edges, while molecular bonds must keep each atom’s total bonding-electron capacity within its valence.These constraints jointly limit the existence and types of edges incident to each node.
- 4.1 Ghost Nodes and Valence: Edge-type capacities are assigned as 0 for nonexistent bonds, 1 for single bonds, 2 for double bonds, and 3 for triple bonds.Expected edge capacities are summed across incident edges because decoder edge distributions are not one-hot.
- 4.1 Ghost Nodes and Valence: For non-molecular graphs, ghost nodes retain the no-incident-edge constraint, while non-ghost nodes use capacity 1 for existing edges and N−1 as their upper bound.The molecular valence interpretation is replaced by a general capacity rule.
- 4.2 Connectivity: Connectivity is enforced by requiring every pair of non-ghost nodes to have a path, while pairs involving ghost nodes must remain disconnected.The adjacency-derived matrix B encodes path existence, and the constraint penalizes violations.
- 4.2 Connectivity: A differentiable connectivity constraint replaces discrete path indicators with probabilistic node and edge existence, sigmoid-transformed matrix powers, and the penalty gij.The transform suppresses amplification from tiny nonzero connection probabilities.
- 4.3 Node Compatibility: Node compatibility is represented by a matrix D, where compatible non-ghost type pairs receive 1 and pairs involving ghost nodes receive 0.The compatibility probabilities are computed as P=eF D eF^T.
- 4.3 Node Compatibility: Constraint (11) lowers the allowed edge-existence probability for node pairs with low compatibility, while highly compatible pairs may connect regardless of edge probability.The threshold is α/[1−P(i,j)], with α∈(0,1).
5 Experiments
Experiments evaluate regularized VAEs on molecular and node-compatible graph generation, comparing validity, reconstruction, novelty, ELBO, latent-space smoothness, and denoising.
- Tasks, Data Sets, and Baselines: The experiments cover molecular graphs from QM9 and ZINC, plus a synthetic node-compatible graph dataset.QM9 molecules contain at most 9 heavy atoms; node-compatible graphs contain 10–15 nodes with five possible labels.
- Tasks, Data Sets, and Baselines: The node-compatible dataset contains 100,000 graphs whose edges are sampled with probability 0.4 only between compatible node-label pairs.Graphs are not necessarily connected.
- Tasks, Data Sets, and Baselines: For molecular graphs, the method is compared with character VAE and grammar VAE baselines using the SMILES representation; the node-compatible task compares regularized and standard VAEs.No external baseline is used for the newly introduced node-compatible task.
- Results: Regularization noticeably increases validity across all datasets, while lowering ELBO as expected; the ELBO difference remains small.For node-compatible graphs, validity rises from 40.2% with the standard VAE to 98.4% with the regularized VAE, while ELBO changes from -42.5 to -51.2.
- Results: The regularized method substantially improves validity, novelty, and reconstruction compared with character VAE and grammar VAE.The reported comparison uses % Valid, % Novel, and % Recon. as evaluation metrics.
- Results: Latent-space visualizations use a two-dimensional grid and one-dimensional interpolations, and the reported graph transitions are quite smooth.The denoising experiment adds edges between incompatible node pairs before reconstruction; regularized VAE reconstructs valid graphs with high probability, whereas standard VAE fails in most cases.
6 Conclusions
The paper proposes regularized VAEs to encourage semantically valid graph generation, evaluating the framework on molecular and node-compatible graph tasks.
- The framework trains VAEs with regularization terms that encourage graph validity constraints.The approach is motivated by transforming constrained optimization into a regularized unconstrained problem.
- The evaluation covers molecular graph generation and node-compatible graph generation.
A Proof of Theorem 1
The proof establishes convergence properties for penalized optimization near a regular local minimizer, then derives first-order conditions using constraint transformations and Lagrange multipliers.
- The inequality penalties are defined with positive parts, eg_j+(x) = max{0, eg_j(x)}, and incorporated into a sequence of penalized problems.
- The penalized minimizers converge to the constrained local minimizer x∗ as k tends to infinity.The proof uses boundedness, feasibility of limit points, and a quadratic proximity term to show x = x∗.
- For sufficiently large k, the penalized minimizer becomes an unconstrained local minimum inside the closed sphere S.
- The first-order condition combines the objective gradient, equality and inequality penalty gradients, and a proximity term.The condition is written as equation (17).
B Additional Experiment Details
The experiments use mini-batch SGD, task-specific latent dimensions and regularization weights, and a defined protocol for validity, novelty, and reconstruction metrics.
- Training: Models are trained with mini-batch SGD using batches of 200 and weights initialized from a zero-centered normal distribution with standard deviation 0.02.
- Training: The latent-space dimensions are 128 for QM9, 256 for ZINC, and 128 for node-compatible graphs.
- Constraints: Molecular constraints include ghost nodes, valence, and connectivity, while node-compatible graphs use ghost nodes and node compatibility.
- Constraints: The tuned regularization weights are 1.0 for QM9 constraints, 0.05 for ZINC constraints, and 5.0 for node-compatible constraints.
- Metrics: Validity and novelty are estimated from 1000 prior latent vectors decoded 500 times each, while reconstruction uses 5000 held-out graphs.Baselines follow the same protocol; the proposed method uses deterministic maximum-likelihood decoding once per latent vector.