Exact Sampling of Directed Acyclic Graphs from Modular Distributions

Topi Talvitie, Aleksis Vuoksenmaa, Mikko Koivisto
Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, PMLR 115:965-974, 2020.

Abstract

We consider the problem of sampling directed acyclic graphs (DAGs) from a given distribution. We assume the sampling distribution is modular, i.e., the probability of a DAG is a product of local factors, each of which only depends on a node and its parents in the DAG. Using inclusion–exclusion recurrence relations, we give an exact sampler that requires Õ(3^n) time for preprocessing and Õ(2^n) per sample, where n is the number of nodes and Õ suppresses polylogarithmic factors. We also consider the symmetric special case where the factors only depend on the size of the parent set—this covers uniform sampling under indegree constraints. In this case, our exact sampler requires O(n^3) time for preprocessing and O(n^2) per sample; this outperforms the previous best bound even for the uniform distribution. We demonstrate the performance of both samplers also empirically.

Cite this Paper

BibTeX
@InProceedings{pmlr-v115-talvitie20a, title = {Exact Sampling of Directed Acyclic Graphs from Modular Distributions}, author = {Talvitie, Topi and Vuoksenmaa, Aleksis and Koivisto, Mikko}, booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference}, pages = {965--974}, year = {2020}, editor = {Adams, Ryan P. and Gogate, Vibhav}, volume = {115}, series = {Proceedings of Machine Learning Research}, month = {22--25 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v115/talvitie20a/talvitie20a.pdf}, url = {https://proceedings.mlr.press/v115/talvitie20a.html}, abstract = {We consider the problem of sampling directed acyclic graphs (DAGs) from a given distribution. We assume the sampling distribution is modular, i.e., the probability of a DAG is a product of local factors, each of which only depends on a node and its parents in the DAG. Using inclusion–exclusion recurrence relations, we give an exact sampler that requires Õ(3^n) time for preprocessing and Õ(2^n) per sample, where n is the number of nodes and Õ suppresses polylogarithmic factors. We also consider the symmetric special case where the factors only depend on the size of the parent set—this covers uniform sampling under indegree constraints. In this case, our exact sampler requires O(n^3) time for preprocessing and O(n^2) per sample; this outperforms the previous best bound even for the uniform distribution. We demonstrate the performance of both samplers also empirically.} }
Endnote
%0 Conference Paper %T Exact Sampling of Directed Acyclic Graphs from Modular Distributions %A Topi Talvitie %A Aleksis Vuoksenmaa %A Mikko Koivisto %B Proceedings of The 35th Uncertainty in Artificial Intelligence Conference %C Proceedings of Machine Learning Research %D 2020 %E Ryan P. Adams %E Vibhav Gogate %F pmlr-v115-talvitie20a %I PMLR %P 965--974 %U https://proceedings.mlr.press/v115/talvitie20a.html %V 115 %X We consider the problem of sampling directed acyclic graphs (DAGs) from a given distribution. We assume the sampling distribution is modular, i.e., the probability of a DAG is a product of local factors, each of which only depends on a node and its parents in the DAG. Using inclusion–exclusion recurrence relations, we give an exact sampler that requires Õ(3^n) time for preprocessing and Õ(2^n) per sample, where n is the number of nodes and Õ suppresses polylogarithmic factors. We also consider the symmetric special case where the factors only depend on the size of the parent set—this covers uniform sampling under indegree constraints. In this case, our exact sampler requires O(n^3) time for preprocessing and O(n^2) per sample; this outperforms the previous best bound even for the uniform distribution. We demonstrate the performance of both samplers also empirically.
APA
Talvitie, T., Vuoksenmaa, A. & Koivisto, M.. (2020). Exact Sampling of Directed Acyclic Graphs from Modular Distributions. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, in Proceedings of Machine Learning Research 115:965-974 Available from https://proceedings.mlr.press/v115/talvitie20a.html.

Related Material