Local Causal Discovery for Statistically Efficient Causal Inference

AI summary

Overview

Research area: Causal discovery and causal effect estimation (statistical machine learning / causal inference).

Technical level: Advanced. The paper relies on graphical causal models (CPDAGs, d-separation, amenability, forbidden projections) and constraint-based causal discovery algorithms.

Scope: The paper introduces LOAD (Local Optimal Adjustments Discovery), a sound and complete method for recovering optimal adjustment sets for a target pair using only local information around the targets, and evaluates it against global, targeted, and local baselines on synthetic and semi-synthetic data (arXiv:2510.14582v2, 2025-10-16, CC BY 4.0).

What This Paper Is About

Estimating the causal effect between two variables usually requires knowing a valid adjustment set — the covariates to condition on — and the best possible set (the one with the lowest asymptotic variance) is the "optimal adjustment set." Global causal discovery methods (e.g., PC) can recover optimal adjustment sets but learn the entire graph, which becomes computationally prohibitive as the number of variables grows; local methods scale better but are restricted to statistically suboptimal adjustment sets. LOAD aims to get both: the statistical quality of global methods with the computational profile of local ones.

Key Contributions

1. A method for determining whether the causal effect between a pair of targets is identifiable using only local information, including tests for explicit ancestry, possible ancestry, definite non-ancestry, and a local amenability test.
2. LOAD (Local Optimal Adjustments Discovery), described as a sound and complete method for identifying the optimal adjustment set using only local information around the target variables and their siblings.
3. A modified forbidden projection that projects over the variables excluding the possible descendants of the treatment, shown to preserve the optimal adjustment set as the parents of the outcome while reducing the size of the projected graph.
4. An empirical evaluation on synthetic and realistic data, reporting that LOAD can recover high-quality adjustment sets at low computational cost.

The paper also reports issues with prior local methods: LDECC and other LocalPC-based methods are argued to be not sound (they may misidentify a non-adjacent spouse as adjacent because they only test separating sets among neighbors), LDECC is argued to be not complete (it may fail to orient all orientable edges around the treatment), and LDP may misreport an effect as unidentifiable when an identifiable effect between the target pair is zero.

Main Findings

• Local identifiability is achievable: LOAD determines whether the causal effect is identifiable using only local information. Lemma 4.2 shows a necessary condition — for X a possible ancestor of Y, the effect is identifiable only if X is an explicit ancestor of Y. Lemma 4.3 gives a local amenability test over the siblings of the treatment. Corollary 4.1 states LOAD is sound and complete in determining identifiability.
• Optimal adjustment sets from local information: Theorem 4.3 states LOAD is sound and complete in finding optimal adjustment sets for a pair of target variables. The optimal set is the parents of the outcome in a modified forbidden projection over V \ PossDe(T) ∪ {T, O}, excluding the treatment (Lemma 4.4).
• Scalability advantage: The reported complexity of LOAD with caching is O(L) for a local discovery algorithm of complexity O(L), versus the global PC algorithm's worst-case O(|V|^(d_max+2)); the paper notes |MB_max| ≪ |V| typically. In experiments, MARVEL could not be run on more than 400 nodes in any setting, and LDECC+ could not be run on 1000 nodes with Fisher-Z tests or on any number of nodes with G² tests due to memory issues.
• Accuracy versus local methods: The abstract reports that on synthetic and realistic data LOAD outperforms global methods in scalability while providing more accurate effect estimation than local methods. The discussion of Figure 1 states LOAD provides comparable accuracy in causal effect estimation to global causal discovery methods while being only slightly more computationally [expensive] — the provided text is truncated at this point.
• Algorithmic output structure: LOAD returns the causal relation between the targets, whether each directional effect is identifiable, and either the optimal adjustment set (empty for a zero causal effect) or the locally valid parent adjustment sets.
• Prior method limitations: LocalPC-based local methods are shown to be unsound and LDECC incomplete; LDP may misreport an identifiable zero effect as unidentifiable; CBL requires all other variables to be non-descendants of the targets; SNAP still requires causal discovery over all possible ancestors of the targets.

Methodology in Plain English

The paper starts from a standard assumption in causal discovery: the data come from a causal directed acyclic graph, the distribution is Markov and faithful to it, and there are no hidden confounders or selection bias ("causal sufficiency"). Under these assumptions, conditional independence tests can reveal the graph's structure — but only up to a Markov equivalence class, represented as a CPDAG with directed and undirected edges.

LOAD works in four steps:

1. Find the relation between the two targets. It runs a local causal discovery algorithm (MB-by-MB in the main implementation) on each target, then uses tests from Fang et al. (2022) to determine whether one target is an explicit ancestor, a possible ancestor, or a definite non-ancestor of the other. If a target is a definite non-ancestor of the other, its effect on the other is trivially zero and identifiable.
2. Test identifiability. If one target is a possible ancestor of the other, the effect is identifiable only if it is an explicit ancestor. Then a local amenability test checks each sibling of the treatment: if a sibling is adjacent to the outcome, or is not independent of the outcome given the sibling's parents plus the treatment, the effect is not identifiable. In that case LOAD returns the locally valid parent adjustment sets instead.
3. Find possible descendants of the treatment. Local tests identify which variables could be descendants of the treatment.
4. Get the optimal adjustment set. LOAD runs local causal discovery on the outcome in a modified forbidden projection that excludes the treatment's possible descendants and re-expands edges over them. The parents of the outcome in this projected graph are the optimal adjustment set.

The complexity argument rests on caching: running a local method on all variables naively costs O(L × |V|), but if Markov blankets and local structures are cached and reused, LOAD's worst case reduces to O(L).

Why This Matters

Impact on research. The paper bridges a long-standing trade-off in causal discovery: global methods give statistically optimal adjustment sets but do not scale, while local methods scale but give suboptimal sets. LOAD claims both, without requiring full graph recovery and without assumptions on the ancestral relationship between targets. It also surfaces correctness problems in prior local methods and proposes fixes.

Real-world applications (from the evaluation and framing):

• Epidemiology and public health: MAGIC-NIAB from bnlearn is a realistic network used for testing causal effect estimation pipelines where effects must be read off learned structure.
• Earth and environmental systems: the ANDES network from bnlearn, used in the binary-data experiments, is a large realistic network (n_V = 223).
• Genomics and high-dimensional biology: the paper's motivation is settings with hundreds or thousands of variables, where global causal discovery becomes computationally prohibitive.
• Decision-making under uncertainty: the introduction frames causal effect estimation as essential in science and decision making, where the graph is typically unknown.

Industry relevance. Because the reported cost metric is the number of conditional independence tests — hardware and implementation independent — the method is relevant to any pipeline that must estimate causal effects at scale on observational data, including A/B testing alternatives, policy evaluation, and feature attribution. The authors publish code at https://github.com/matyasch/load.

Future Directions

• Relaxing causal sufficiency. LOAD assumes no latent confounders or selection bias. The related work notes recent local extensions to the causally insufficient case; extending LOAD's optimality guarantee to hidden confounders is a natural follow-up.
• Robustness to noisy CI tests. The evaluation uses significance level α = 0.01 with oracle, Fisher-Z, G², and KCI tests. How the soundness and completeness guarantees degrade under finite-sample CI test errors is not resolved in the provided text.
• Scaling further. The paper shows baselines failing at 400 and 1000 nodes for memory or runtime reasons; how LOAD behaves beyond the tested node counts, and whether the caching trick fully realizes the O(L) bound in practice, remain open.
• More general background knowledge. The authors simplify the forbidden projection from Witte et al. (2020), which originally handles maxPDAGs. Whether LOAD extends beyond CPDAGs with additional edge orientation background knowledge is not addressed in the provided content.

Target Audience

Researchers and practitioners in causal inference and causal discovery who need to estimate causal effects between a pair of variables on datasets with many variables and unknown causal structure. It will be most useful to readers already comfortable with CPDAGs, d-separation, conditional independence testing, and adjustment set theory; the empirical sections are accessible to applied scientists who primarily care about scalability and effect estimation accuracy. Applied statisticians, epidemiologists, and machine learning engineers working on large observational datasets are the main beneficiaries.

Authors’ abstract

Causal discovery methods can identify valid adjustment sets for causal effect estimation for a pair of target variables, even when the underlying causal graph is unknown. Global causal discovery methods focus on learning the whole causal graph and therefore enable the recovery of optimal adjustment sets, i.e., sets with the lowest asymptotic variance, but they quickly become computationally prohibitive as the number of variables grows. Local causal discovery methods offer a more scalable alternative by focusing on the local neighborhood of the target variables, but are restricted to statistically suboptimal adjustment sets. In this work, we propose Local Optimal Adjustments Discovery (LOAD), a sound and complete causal discovery approach that combines the computational efficiency of local methods with the statistical optimality of global methods. First, LOAD identifies the causal relation between the targets and tests if the causal effect is identifiable by using only local information. If it is identifiable, it finds the possible descendants of the treatment and infers the optimal adjustment set as the parents of the outcome in a modified forbidden projection. Otherwise, it returns the locally valid parent adjustment sets. In our experiments on synthetic and realistic data LOAD outperforms global methods in scalability, while providing more accurate effect estimation than local methods.