Membership Testing in Markov Equivalence Classes via Independence Queries

Understanding causal relationships between variables is a fundamental problem with broad impact in numerous scientific fields. While extensive research has been dedicated to \emph{learning} causal graphs from data, its complementary concept of \emph{testing} causal relationships has remained largely unexplored. While \emph{learning} involves the task of recovering the Markov equivalence class (MEC) of the underlying causal graph from observational data, the \emph{testing} counterpart addresses the following critical question: \emph{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 \emph{learning} problem, where algorithms often use a number of independence tests that is exponential in the maximum in-degree, this shows that \emph{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.