The MLE Principle in Autoregressive Graph Generation

September 16, 2021
3:00-4:00pm ET
Halligan 102, in-person only
Speaker: Liping Liu, Schwartz Family Assistant Professor, Tufts University


A graph generative model defines a distribution over graphs. When generating unlabeled graphs, a model often uses a sequential process that creates and adds nodes and edges. The generative process essentially defines the probability of an adjacency matrix. The computation of the likelihood of a graph requires marginalizing all possible adjacency matrices; this makes maximum likelihood estimation (MLE) challenging due to a large number of possible adjacency matrices of the same graph. In this work, we provide an expression for the likelihood of a graph generative model through the marginalization of node generation orders. We show the calculation of a graph's log-likelihood is closely related to the problem of graph automorphism. In addition, we derive a variational inference (VI) algorithm for fitting a graph generative model that is based on the maximization of a variational bound of the log-likelihood. This allows the model to be trained with node orderings from the approximate posterior instead of ad-hoc orderings. Our experiments show that our log-likelihood bound is significantly tighter than the bound of previous schemes. The models fitted with the VI algorithm can generate high-quality graphs that match the structures of target graphs not seen during training.

Bio: Liping Liu received his PhD degree from Oregon State University in 2016, and then worked as a postdoc researcher at Columbia University for one year. He joined Tufts University in 2017 as the Schwartz Family Assistant Professor. His research focuses on probabilistic methods in machine learning, particularly learning techniques for graph data. He has served as a reviewer and meta-reviewer in a series of top-tier conferences in machine learning. He is also on the JMLR editorial board.