Learning an efficient constructive sampler for graphs

Discriminative systems that can deal with graphs in input are known, however, generative or constructive approaches that can sample graphs from empirical distributions are less developed. Here we propose a Metropolis–Hastings approach that uses a novel type of graph grammar to efficiently learn proposal distributions in a data driven fashion. We report experimental results in a de-novo molecular synthesis problem where we show that the distribution of the molecules generated by the sampling procedure is accurate enough to improve a predictor's performance in a classification task.