Practical Algorithms for Orientations of Partially Directed Graphical Models

Malte Luttermann, Marcel Wienöbst, Maciej Liskiewicz
Proceedings of the Second Conference on Causal Learning and Reasoning, PMLR 213:259-280, 2023.

Abstract

In observational studies, the true causal model is typically unknown and needs to be estimated from available observational and limited experimental data. In such cases, the learned causal model is commonly represented as a partially directed acyclic graph (PDAG), which contains both directed and undirected edges indicating uncertainty of causal relations between random variables. The main focus of this paper is on the maximal orientation task, which, for a given PDAG, aims to orient the undirected edges maximally such that the resulting graph represents the same Markov equivalent DAGs as the input PDAG. This task is a subroutine used frequently in causal discovery, e.g., as the final step of the celebrated PC algorithm. Utilizing connections to the problem of finding a consistent DAG extension of a PDAG, we derive faster algorithms for computing the maximal orientation by proposing two novel approaches for extending PDAGs, both constructed with an emphasis on simplicity and practical effectiveness.

Cite this Paper

BibTeX
@InProceedings{pmlr-v213-luttermann23a, title = {Practical Algorithms for Orientations of Partially Directed Graphical Models}, author = {Luttermann, Malte and Wien\"obst, Marcel and Liskiewicz, Maciej}, booktitle = {Proceedings of the Second Conference on Causal Learning and Reasoning}, pages = {259--280}, year = {2023}, editor = {van der Schaar, Mihaela and Zhang, Cheng and Janzing, Dominik}, volume = {213}, series = {Proceedings of Machine Learning Research}, month = {11--14 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v213/luttermann23a/luttermann23a.pdf}, url = {https://proceedings.mlr.press/v213/luttermann23a.html}, abstract = {In observational studies, the true causal model is typically unknown and needs to be estimated from available observational and limited experimental data. In such cases, the learned causal model is commonly represented as a partially directed acyclic graph (PDAG), which contains both directed and undirected edges indicating uncertainty of causal relations between random variables. The main focus of this paper is on the maximal orientation task, which, for a given PDAG, aims to orient the undirected edges maximally such that the resulting graph represents the same Markov equivalent DAGs as the input PDAG. This task is a subroutine used frequently in causal discovery, e.g., as the final step of the celebrated PC algorithm. Utilizing connections to the problem of finding a consistent DAG extension of a PDAG, we derive faster algorithms for computing the maximal orientation by proposing two novel approaches for extending PDAGs, both constructed with an emphasis on simplicity and practical effectiveness.} }
Endnote
%0 Conference Paper %T Practical Algorithms for Orientations of Partially Directed Graphical Models %A Malte Luttermann %A Marcel Wienöbst %A Maciej Liskiewicz %B Proceedings of the Second Conference on Causal Learning and Reasoning %C Proceedings of Machine Learning Research %D 2023 %E Mihaela van der Schaar %E Cheng Zhang %E Dominik Janzing %F pmlr-v213-luttermann23a %I PMLR %P 259--280 %U https://proceedings.mlr.press/v213/luttermann23a.html %V 213 %X In observational studies, the true causal model is typically unknown and needs to be estimated from available observational and limited experimental data. In such cases, the learned causal model is commonly represented as a partially directed acyclic graph (PDAG), which contains both directed and undirected edges indicating uncertainty of causal relations between random variables. The main focus of this paper is on the maximal orientation task, which, for a given PDAG, aims to orient the undirected edges maximally such that the resulting graph represents the same Markov equivalent DAGs as the input PDAG. This task is a subroutine used frequently in causal discovery, e.g., as the final step of the celebrated PC algorithm. Utilizing connections to the problem of finding a consistent DAG extension of a PDAG, we derive faster algorithms for computing the maximal orientation by proposing two novel approaches for extending PDAGs, both constructed with an emphasis on simplicity and practical effectiveness.
APA
Luttermann, M., Wienöbst, M. & Liskiewicz, M.. (2023). Practical Algorithms for Orientations of Partially Directed Graphical Models. Proceedings of the Second Conference on Causal Learning and Reasoning, in Proceedings of Machine Learning Research 213:259-280 Available from https://proceedings.mlr.press/v213/luttermann23a.html.

Related Material