A Recursive Markov Boundary-Based Approach to Causal Structure Learning

Ehsan Mokhtarian, Sina Akbari, AmirEmad Ghassami, Negar Kiyavash
Proceedings of The KDD'21 Workshop on Causal Discovery, PMLR 150:26-54, 2021.

Abstract

Constraint-based methods are one of the main approaches for causal structure learning that are particularly valued as they are asymptotically guaranteed to find a structure that is Markov equivalent to the causal graph of the system. On the other hand, they may require an exponentially large number of conditional independence (CI) tests in the number of variables of the system. In this paper, we propose a novel recursive constraint- based method for causal structure learning that significantly reduces the required number of CI tests compared to the existing literature. The proposed approach aims to use Markov boundary information to identify a specific variable that can be removed from the set of variables without affecting the statistical dependencies among the other variables. Having identified such a variable, we discover its neighborhood, remove that variable from the set of variables, and recursively learn the causal structure over the remaining variables. We further provide a lower bound on the number of CI tests required by any constraint-based method. Comparing this lower bound to our achievable bound demonstrates the efficiency of the proposed approach. Our experimental results show that the proposed algorithm outperforms state-of-the-art both on synthetic and real-world structures.

Cite this Paper

BibTeX
@InProceedings{pmlr-v150-mokhtarian21a, title = {A Recursive Markov Boundary-Based Approach to Causal Structure Learning}, author = {Mokhtarian, Ehsan and Akbari, Sina and Ghassami, AmirEmad and Kiyavash, Negar}, booktitle = {Proceedings of The KDD'21 Workshop on Causal Discovery}, pages = {26--54}, year = {2021}, editor = {Le, Thuc Duy and Li, Jiuyong and Cooper, Greg and Triantafyllou, Sofia and Bareinboim, Elias and Liu, Huan and Kiyavash, Negar}, volume = {150}, series = {Proceedings of Machine Learning Research}, month = {15 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v150/mokhtarian21a/mokhtarian21a.pdf}, url = {https://proceedings.mlr.press/v150/mokhtarian21a.html}, abstract = {Constraint-based methods are one of the main approaches for causal structure learning that are particularly valued as they are asymptotically guaranteed to find a structure that is Markov equivalent to the causal graph of the system. On the other hand, they may require an exponentially large number of conditional independence (CI) tests in the number of variables of the system. In this paper, we propose a novel recursive constraint- based method for causal structure learning that significantly reduces the required number of CI tests compared to the existing literature. The proposed approach aims to use Markov boundary information to identify a specific variable that can be removed from the set of variables without affecting the statistical dependencies among the other variables. Having identified such a variable, we discover its neighborhood, remove that variable from the set of variables, and recursively learn the causal structure over the remaining variables. We further provide a lower bound on the number of CI tests required by any constraint-based method. Comparing this lower bound to our achievable bound demonstrates the efficiency of the proposed approach. Our experimental results show that the proposed algorithm outperforms state-of-the-art both on synthetic and real-world structures.} }
Endnote
%0 Conference Paper %T A Recursive Markov Boundary-Based Approach to Causal Structure Learning %A Ehsan Mokhtarian %A Sina Akbari %A AmirEmad Ghassami %A Negar Kiyavash %B Proceedings of The KDD'21 Workshop on Causal Discovery %C Proceedings of Machine Learning Research %D 2021 %E Thuc Duy Le %E Jiuyong Li %E Greg Cooper %E Sofia Triantafyllou %E Elias Bareinboim %E Huan Liu %E Negar Kiyavash %F pmlr-v150-mokhtarian21a %I PMLR %P 26--54 %U https://proceedings.mlr.press/v150/mokhtarian21a.html %V 150 %X Constraint-based methods are one of the main approaches for causal structure learning that are particularly valued as they are asymptotically guaranteed to find a structure that is Markov equivalent to the causal graph of the system. On the other hand, they may require an exponentially large number of conditional independence (CI) tests in the number of variables of the system. In this paper, we propose a novel recursive constraint- based method for causal structure learning that significantly reduces the required number of CI tests compared to the existing literature. The proposed approach aims to use Markov boundary information to identify a specific variable that can be removed from the set of variables without affecting the statistical dependencies among the other variables. Having identified such a variable, we discover its neighborhood, remove that variable from the set of variables, and recursively learn the causal structure over the remaining variables. We further provide a lower bound on the number of CI tests required by any constraint-based method. Comparing this lower bound to our achievable bound demonstrates the efficiency of the proposed approach. Our experimental results show that the proposed algorithm outperforms state-of-the-art both on synthetic and real-world structures.
APA
Mokhtarian, E., Akbari, S., Ghassami, A. & Kiyavash, N.. (2021). A Recursive Markov Boundary-Based Approach to Causal Structure Learning. Proceedings of The KDD'21 Workshop on Causal Discovery, in Proceedings of Machine Learning Research 150:26-54 Available from https://proceedings.mlr.press/v150/mokhtarian21a.html.

Related Material