# Membership Testing in Markov Equivalence Classes via Independence Query Oracles

arXiv: https://arxiv.org/abs/2403.05759 · HTML: https://mlsanity.com/paper/2403.05759/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 71 references that are in the map.
- First posted on arXiv 9 Mar 2024.

## Builds on (most cited first, 15 of 15)

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Causal Inference in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/1302.4983/) (2013)
- [Greedy Relaxations of the Sparsest Permutation Algorithm](https://mlsanity.com/paper/2206.05421/) (2022)
- [Causal Discovery with Language Models as Imperfect Experts](https://mlsanity.com/paper/2307.02390/) (2023)
- [Learning Sparse Causal Models is not NP-hard](https://mlsanity.com/paper/1309.6824/) (2013)
- [Causal Order: The Key to Leveraging Imperfect Experts in Causal Inference](https://mlsanity.com/paper/2310.15117/) (2023)
- [High-dimensional consistency in score-based and hybrid structure learning](https://mlsanity.com/paper/1507.02608/) (2015)
- [Parameter Priors for Directed Acyclic Graphical Models and the Characterization of Several Probability Distributions](https://mlsanity.com/paper/1301.6697/) (2013)
- [A Transformational Characterization of Equivalent Bayesian Network Structures](https://mlsanity.com/paper/1302.4938/) (2013)
- [Fast Scalable and Accurate Discovery of DAGs Using the Best Order Score Search and Grow-Shrink Trees](https://mlsanity.com/paper/2310.17679/) (2023)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [On the Logic of Causal Models](https://mlsanity.com/paper/1304.2355/) (2013)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs](https://mlsanity.com/paper/2012.09679/) (2020)
- [Active causal structure learning with advice](https://mlsanity.com/paper/2305.19588/) (2023)
- [SparsityBoost: A New Scoring Function for Learning Bayesian Network Structure](https://mlsanity.com/paper/1309.6820/) (2013)

## Abstract (arXiv)

Understanding causal relationships between variables is a fundamental problem with broad impact in numerous scientific fields. While extensive research has been dedicated to learning causal graphs from data, its complementary concept of testing causal relationships has remained largely unexplored. While learning involves the task of recovering the Markov equivalence class (MEC) of the underlying causal graph from observational data, the testing counterpart addresses the following critical question: Given a specific MEC and observational data from some causal graph, can we determine if the data-generating causal graph belongs to the given MEC? We explore constraint-based testing methods by establishing bounds on the required number of conditional independence tests. Our bounds are in terms of the size of the maximum undirected clique (s) of the given MEC. In the worst case, we show a lower bound of exp(Omega(s)) independence tests. We then give an algorithm that resolves the task with exp(O(s)) tests, matching our lower bound. Compared to the learning problem, where algorithms often use a number of independence tests that is exponential in the maximum in-degree, this shows that testing is relatively easier. In particular, it requires exponentially less independence tests in graphs featuring high in-degrees and small clique sizes. Additionally, using the DAG associahedron, we provide a geometric interpretation of testing versus learning and discuss how our testing result can aid learning.