Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation

Xiaohui Chen, Xu Han, Jiajing Hu, Francisco Ruiz, Liping Liu
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:1630-1639, 2021.

Abstract

A graph generative model defines a distribution over graphs. Typically, the model consists of a sequential process that creates and adds nodes and edges. Such sequential process defines an ordering of the nodes in the graph. The computation of the model’s likelihood requires to marginalize the node orderings; this makes maximum likelihood estimation (MLE) challenging due to the (factorial) number of possible permutations. 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 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 are able to generate high-quality graphs that match the structures of target graphs not seen during training.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-chen21j, title = {Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation}, author = {Chen, Xiaohui and Han, Xu and Hu, Jiajing and Ruiz, Francisco and Liu, Liping}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {1630--1639}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/chen21j/chen21j.pdf}, url = {https://proceedings.mlr.press/v139/chen21j.html}, abstract = {A graph generative model defines a distribution over graphs. Typically, the model consists of a sequential process that creates and adds nodes and edges. Such sequential process defines an ordering of the nodes in the graph. The computation of the model’s likelihood requires to marginalize the node orderings; this makes maximum likelihood estimation (MLE) challenging due to the (factorial) number of possible permutations. 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 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 are able to generate high-quality graphs that match the structures of target graphs not seen during training.} }
Endnote
%0 Conference Paper %T Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation %A Xiaohui Chen %A Xu Han %A Jiajing Hu %A Francisco Ruiz %A Liping Liu %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-chen21j %I PMLR %P 1630--1639 %U https://proceedings.mlr.press/v139/chen21j.html %V 139 %X A graph generative model defines a distribution over graphs. Typically, the model consists of a sequential process that creates and adds nodes and edges. Such sequential process defines an ordering of the nodes in the graph. The computation of the model’s likelihood requires to marginalize the node orderings; this makes maximum likelihood estimation (MLE) challenging due to the (factorial) number of possible permutations. 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 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 are able to generate high-quality graphs that match the structures of target graphs not seen during training.
APA
Chen, X., Han, X., Hu, J., Ruiz, F. & Liu, L.. (2021). Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:1630-1639 Available from https://proceedings.mlr.press/v139/chen21j.html.

Related Material