Membership Testing in Markov Equivalence Classes via Independence Query
  Oracles
Jiaqi Zhang Kirankumar Shiragur Caroline Uhler
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.