BETA This research page is an early version. Explanatory text, figure selection, and presentation are still being revised.

JMLR 2021

A Recursive Markov Boundary-Based Approach to Causal Structure Learning

Ehsan Mokhtarian^* · Sina Akbari^* · AmirEmad Ghassami · Negar Kiyavash

^* Equal contribution.

Proceedings of The KDD'21 Workshop on Causal Discovery · 2021

Paper GitHub PMLR KDD workshop

Keywords.

causal discovery Markov boundaries constraint-based learning structure learning

TL;DR.

MARVEL learns a causal DAG recursively from Markov-boundary information. At each step it identifies a removable variable, learns its neighborhood, removes it, and continues on a smaller graph. We prove strong upper bounds on the number of required CI tests, give a general lower bound for constraint-based methods, and show MARVEL outperforms state-of-the-art methods on synthetic and real-world structures.

Why this matters.

The recursive viewpoint converts local Markov-boundary information into global causal structure while sharply reducing the number and size of CI tests. This gives both a theoretical efficiency result and a practical route to scaling constraint-based discovery.

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.

Main message. Markov boundaries provide enough local structure to peel a causal graph apart recursively—and doing so brings the number of CI tests close to the fundamental limit.

The paper at a glance

An informal guide to the problem, the idea, and the main results.

Markov boundaries causal discovery recursive peeling constraint-based learning

1. The problem

Learning a causal graph from conditional independences becomes hard because the search is global and the conditioning sets can become large. The challenge is to find a principled way to reduce the problem using only trustworthy local information.

2. The key idea

We use Markov boundaries as the local primitive. If a variable satisfies the right boundary-based conditions, it can be removed safely, shrinking the graph and allowing the discovery problem to be solved recursively.

3. Removable variables

Theory

We introduce removable variables and give a Markov-boundary-based procedure for identifying them. Removing such a variable preserves the statistical dependencies among the remaining variables, which makes recursive structure learning sound.

4. CI-test complexity

Theory

We derive an upper bound on the number of CI tests used by MARVEL and a lower bound that applies to any constraint-based causal-discovery method. Comparing the two bounds shows that the recursive approach is close to the best possible worst-case complexity.

5. How it works

Estimate or characterize relevant Markov boundaries.
Use them to certify a removable variable.
Remove the variable and recurse on the remaining graph.
Reconstruct the graph from the sequence of local decisions.

What the experiments show

Main empirical message.

On synthetic graphs and real-world Bayesian-network structures, MARVEL uses substantially fewer CI tests and achieves strong runtime and structural-recovery performance relative to state-of-the-art constraint-based methods.

Where this helps

Good fit

You want a local-to-global route for causal structure learning.
Markov boundaries are easier for you to estimate than full graph structure directly.
You care about scalable discovery in settings where boundary structure is informative.

Keep in mind

MARVEL turns estimated Markov boundaries into an end-to-end causal-structure-learning algorithm, not merely a local neighborhood procedure.
The recursive reduction simultaneously lowers the number of CI tests and the size of the conditioning sets used later in the run.

Cite this paper

@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},
  volume    = {150},
  series    = {Proceedings of Machine Learning Research},
  publisher = {PMLR},
  url       = {https://proceedings.mlr.press/v150/mokhtarian21a.html}
}