Local Causal Discovery for Estimating Causal Effects

Even when the causal graph underlying our data is unknown, we can nevertheless narrow down the possible values that an average treatment effect (ATE) can take by (1) identifying the graph up to a Markov equivalence class; and (2) estimating that ATE for each graph in the class. While the PC algorithm can identify this class under strong faithfulness assumptions, it can be computationally prohibitive. Fortunately, only the local graph structure around the treatment is required to identify an ATE, a fact exploited by local discovery algorithms to identify the possible values for an ATE more efficiently. In this paper, we introduce Local Discovery using Eager Collider Checks (LDECC), a new local discovery algorithm that finds colliders and orients the treatment's parents differently from existing methods. We show that there exist graphs where our algorithm exponentially outperforms existing local discovery algorithms and vice versa. Moreover, we show that LDECC and existing algorithms rely on different sets of faithfulness assumptions. We leverage this insight to show that it is possible to test and recover from certain faithfulness violations.