SNAP: Sequential Non-Ancestor Pruning
for Targeted Causal Effect Estimation

Estimating causal effects, for example to understand how human activities drive climate change, is fundamental to our scientific understanding and practical decision-making. The gold standard for this is to conduct experiments, but these can be expensive or unethical. For instance, deliberately increasing greenhouse gas emissions to study their effects would be irresponsible. Fortunately, causal effects can also be estimated from observational data, using adjustment variables. These adjustment sets are determined by the causal graph of the underlying process, which can also be estimated by causal discovery methods.

Causal discovery estimates the causal graph, from which valid adjustment sets can be read off for causal effect estimation.

However, discovering the full causal graph can be computationally expensive for large numbers of variables. If we are only interested in the causal effects between a small set of target variables, we may not need to learn the entire causal graph, but just a smaller subgraph that includes the targets and their statistically efficient adjustment sets.

Removing \(V_3\) and \(V_5\) in the previous example decreases the cost of causal discovery, while yielding the same efficient adjustment sets.

We formalize this problem as targeted causal effect estimation with an unknown graph, which focuses on identifying the causal effects between all pairs of target variables in a computationally and statistically efficient way.

We introduce Sequential Non-Ancestor Pruning (SNAP), which iteratively identifies and removes definite non-ancestors, and provide two implementations: SNAP(\(k\)) and SNAP(\(\infty\)). SNAP(\(k\)) is a constraint-based causal discovery algorithm that adapts the PC-style skeleton search. It iteratively increases conditioning set sizes of conditional independence (CI) tests starting from order 0. At every iteration, it orients v-structures using the intermediate skeleton and discovered separating sets to identify and prune some definite non-ancestors of the targets before proceeding to the next iteration.

SNAP(\(k\)) progressively identifies and prunes non-ancestors by orienting v-structures at every order of the PC-style skeleton search.

Orienting v-structures based with intermediate skeletons and CI test results restricted to a maximum order requires particular care. For instance, we need to handle conflicting v-structures, and additional steps are needed for proper orientation starting from order 2. We discuss these details and provide the complete pseudocode in the full paper.

SNAP(\(k\)) considers fewer and fewer variables as conditioning set sizes increase, reducing higher-order CI tests significantly. We can stop SNAP(\(k\)) at any iteration k and run a standard causal discovery algorithm on the remaining variables, which always form a possibly ancestral set, to identify valid and efficient adjustment sets. We call this approach pre-filtering with SNAP(\(k\)).

Pre-filtering with SNAP(\(k\)) can efficiently reduce the number of variables before causal discovery.

SNAP(\(\infty\)) extends SNAP(\(k\)) into a stand-alone causal discovery algorithm. It runs SNAP(\(k\)) until completion, then applies Meek's rules, and identifies and removes non-ancestors one final time. The result is the full graph restricted to the possible ancestors of the targets, ensuring the same valid and efficient adjustment sets as full-graph discovery.

SNAP(\(\infty\)) needs much fewer CI tests than PC to find optimal adjustment sets for the causal effects between targets, by progressively removing definite non-ancestors.