Constrained Generation of Semantically Valid Graphs via Regularizing
  Variational Autoencoders
  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.
