TD-GEN: Graph Generation Using Tree Decomposition

Hamed Shirzad, Hossein Hajimirsadeghi, Amir H. Abdi, Greg Mori
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:5518-5537, 2022.

Abstract

We propose TD-GEN, a graph generation framework based on tree decomposition, and introduce a reduced upper bound on the maximum number of decisions needed for graph generation. The framework includes a permutation invariant tree generation model which forms the backbone of graph generation. Tree nodes are supernodes, each representing a cluster of nodes in the graph. Graph nodes and edges are incrementally generated inside the clusters by traversing the tree supernodes, respecting the structure of the tree decomposition, and following node sharing decisions between the clusters. Further, we discuss the shortcomings of the standard evaluation criteria based on statistical properties of the generated graphs. We propose to compare the generalizability of models based on expected likelihood. Empirical results on a variety of standard graph generation datasets demonstrate the superior performance of our method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-shirzad22a, title = { TD-GEN: Graph Generation Using Tree Decomposition }, author = {Shirzad, Hamed and Hajimirsadeghi, Hossein and Abdi, Amir H. and Mori, Greg}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {5518--5537}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/shirzad22a/shirzad22a.pdf}, url = {https://proceedings.mlr.press/v151/shirzad22a.html}, abstract = { We propose TD-GEN, a graph generation framework based on tree decomposition, and introduce a reduced upper bound on the maximum number of decisions needed for graph generation. The framework includes a permutation invariant tree generation model which forms the backbone of graph generation. Tree nodes are supernodes, each representing a cluster of nodes in the graph. Graph nodes and edges are incrementally generated inside the clusters by traversing the tree supernodes, respecting the structure of the tree decomposition, and following node sharing decisions between the clusters. Further, we discuss the shortcomings of the standard evaluation criteria based on statistical properties of the generated graphs. We propose to compare the generalizability of models based on expected likelihood. Empirical results on a variety of standard graph generation datasets demonstrate the superior performance of our method. } }
Endnote
%0 Conference Paper %T TD-GEN: Graph Generation Using Tree Decomposition %A Hamed Shirzad %A Hossein Hajimirsadeghi %A Amir H. Abdi %A Greg Mori %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-shirzad22a %I PMLR %P 5518--5537 %U https://proceedings.mlr.press/v151/shirzad22a.html %V 151 %X We propose TD-GEN, a graph generation framework based on tree decomposition, and introduce a reduced upper bound on the maximum number of decisions needed for graph generation. The framework includes a permutation invariant tree generation model which forms the backbone of graph generation. Tree nodes are supernodes, each representing a cluster of nodes in the graph. Graph nodes and edges are incrementally generated inside the clusters by traversing the tree supernodes, respecting the structure of the tree decomposition, and following node sharing decisions between the clusters. Further, we discuss the shortcomings of the standard evaluation criteria based on statistical properties of the generated graphs. We propose to compare the generalizability of models based on expected likelihood. Empirical results on a variety of standard graph generation datasets demonstrate the superior performance of our method.
APA
Shirzad, H., Hajimirsadeghi, H., Abdi, A.H. & Mori, G.. (2022). TD-GEN: Graph Generation Using Tree Decomposition . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:5518-5537 Available from https://proceedings.mlr.press/v151/shirzad22a.html.

Related Material