Finding Minimal d-separators in Linear Time and Applications

Benito van der Zander, Maciej Liśkiewicz
Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, PMLR 115:637-647, 2020.

Abstract

The study of graphical causal models is fundamentally the study of separations and conditional independences. We provide linear time algorithms for two graphical primitives: to test, if a given set is a minimal d-separator, and to find a minimal d-separator in directed acyclic graphs (DAGs), completed partially directed acyclic graphs (CPDAGs) and restricted chain graphs (RCGs) as well as minimal m-separators in ancestral graphs (AGs). These algorithms improve the runtime of the best previously known algorithms for minimal separators that are based on moralization and thus require quadratic time to construct and handle the moral graph. (Minimal) separating sets have important applications like finding (minimal) covariate adjustment sets or conditional instrumental variables.

Cite this Paper

BibTeX
@InProceedings{pmlr-v115-van-der-zander20a, title = {Finding Minimal d-separators in Linear Time and Applications}, author = {van der Zander, Benito and Li\'{s}kiewicz, Maciej}, booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference}, pages = {637--647}, 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/van-der-zander20a/van-der-zander20a.pdf}, url = {https://proceedings.mlr.press/v115/van-der-zander20a.html}, abstract = {The study of graphical causal models is fundamentally the study of separations and conditional independences. We provide linear time algorithms for two graphical primitives: to test, if a given set is a minimal d-separator, and to find a minimal d-separator in directed acyclic graphs (DAGs), completed partially directed acyclic graphs (CPDAGs) and restricted chain graphs (RCGs) as well as minimal m-separators in ancestral graphs (AGs). These algorithms improve the runtime of the best previously known algorithms for minimal separators that are based on moralization and thus require quadratic time to construct and handle the moral graph. (Minimal) separating sets have important applications like finding (minimal) covariate adjustment sets or conditional instrumental variables.} }
Endnote
%0 Conference Paper %T Finding Minimal d-separators in Linear Time and Applications %A Benito van der Zander %A Maciej Liśkiewicz %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-van-der-zander20a %I PMLR %P 637--647 %U https://proceedings.mlr.press/v115/van-der-zander20a.html %V 115 %X The study of graphical causal models is fundamentally the study of separations and conditional independences. We provide linear time algorithms for two graphical primitives: to test, if a given set is a minimal d-separator, and to find a minimal d-separator in directed acyclic graphs (DAGs), completed partially directed acyclic graphs (CPDAGs) and restricted chain graphs (RCGs) as well as minimal m-separators in ancestral graphs (AGs). These algorithms improve the runtime of the best previously known algorithms for minimal separators that are based on moralization and thus require quadratic time to construct and handle the moral graph. (Minimal) separating sets have important applications like finding (minimal) covariate adjustment sets or conditional instrumental variables.
APA
van der Zander, B. & Liśkiewicz, M.. (2020). Finding Minimal d-separators in Linear Time and Applications. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, in Proceedings of Machine Learning Research 115:637-647 Available from https://proceedings.mlr.press/v115/van-der-zander20a.html.

Related Material