Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation


A graph generative model defines a distribution over graphs. Typically, the model consists of a sequential process that creates and adds nodes and edges. The likelihood of such a graph is required for model fitting or evaluation, but unfortunately it is intractable. This makes maximum likelihood estimation (MLE) challenging, and evaluation of the model based log-likelihood is also intractable (and other evaluation metrics are used instead). In this work, we provide an expression for the likelihood of a graph generative model and show that its calculation is closely related to the problem of finding automorphically equivalent nodes, and we derive a lower bound on the log-likelihood based on the color refinement algorithm. In addition, we derive a variational inference algorithm for fitting a graph generative model that is based on the maximization of a variational bound of the lower bound. Our experiments show that our log-likelihood bound is significantly tighter than the bound of previous schemes. The models fitted with the variational inference algorithm are able to generate high-quality graphs that match the structures of target graphs not seen during training.