Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias

Sina Akbari, Ehsan Mokhtarian, AmirEmad Ghassami, Negar Kiyavash

Introduction: The Challenge of Hidden Variables

In real-world systems, we rarely observe every variable that influences a given outcome. We frequently encounter latent variables (unobserved common causes) and selection bias (where our data is inadvertently conditioned on certain outcomes). Standard Directed Acyclic Graphs (DAGs) struggle to represent these scenarios effectively because they are not "closed" under marginalization and conditioning. To accurately model these complex systems, researchers rely on Maximal Ancestral Graphs (MAGs).

Historically, the gold standard for learning MAGs has been the FCI (Fast Causal Inference) algorithm. However, FCI is computationally expensive. It performs a massive number of Conditional Independence (CI) tests, often requiring very large conditioning sets. For practitioners, large conditioning sets are highly problematic because they demand enormous amounts of data to remain statistically reliable. While faster alternatives exist, they often sacrifice "completeness," meaning they might miss valid causal relationships.

To address this, researchers have introduced L-MARVEL (Latent MARVEL), a novel, recursive constraint-based method that is both sound and complete, significantly reducing the computational burden of learning causal MAGs.

The L-MARVEL Algorithm: A Recursive Solution

Unlike traditional methods that attempt to solve the entire graph at once, L-MARVEL employs a "divide and conquer" strategy. The algorithm breaks the problem down by shrinking the graph at each step, ensuring that the conditioning sets—the variables held constant during a statistical test—remain as small as possible.

The core logic of L-MARVEL follows three main steps:

  1. Identify a "Removable" Variable: Not every variable can be deleted from a graph without distorting the relationships between the remaining ones. L-MARVEL uses a formal graphical definition and a statistical test to find variables that can be safely extracted.
  2. Local Discovery: Once a removable variable is found, the algorithm identifies its immediate neighbors.
  3. Recurse: The removable variable is removed from the dataset, and the process repeats on the remaining variables.
Illustration of removable variables: (a) Original DAG, (b) MAG, (c) Valid removal of T preserves structure, (d) Invalid removal of W introduces false dependencies (red edges).

As shown in the figure above, identifying the right variable to remove is crucial. Removing a valid variable preserves the underlying causal logic (m-separation) of the rest of the graph, while removing an invalid one introduces false dependencies.

Key Insights and Theoretical Guarantees

The primary advantage of L-MARVEL's recursive approach is reliability through reduction. In causal discovery, the error rate of CI tests increases exponentially with the size of the conditioning set. By continuously shrinking the graph, L-MARVEL naturally keeps these sets small, leading to far fewer false discoveries compared to non-recursive methods.

Furthermore, the paper bridges a significant gap in the literature by providing rigorous complexity analysis. The authors establish the tightest known upper bound for the number of CI tests required in MAG learning. They demonstrate that the complexity is primarily driven by the local density of the graph rather than the total number of variables. They also provide a lower bound, proving that L-MARVEL is nearly as efficient as any constraint-based algorithm can theoretically be.

Experimental Results: Speed and Accuracy

L-MARVEL was evaluated against state-of-the-art methods on both synthetic structures (Erdos-Renyi graphs and DAGs) and standard benchmark causal networks (ranging from 22 to 95 observed variables, with varying degrees of latent and selection variables).

The results highlight massive improvements in both efficiency and accuracy:

  • Efficiency: On the "Arth150" benchmark (95 variables), L-MARVEL completed the structure learning task in just 0.36 seconds. In stark contrast, the next best complete method (RFCI) took over 1000 seconds.
  • CI Test Reduction: The number of CI tests performed by L-MARVEL is often orders of magnitude lower than traditional methods. In the "Hailfinder" benchmark, L-MARVEL required only 333 tests, while RFCI executed over 250,000.
  • Accuracy: L-MARVEL consistently achieved higher F1-scores and Recall. For example, on the "Alarm" network, it achieved an F1-score of 0.92, outperforming both RFCI (0.89) and FCI (0.88).

Limitations and Future Directions

While L-MARVEL represents a significant leap forward, it does have limitations. The algorithm relies on an initial estimate of the "Markov Boundary" (the set of variables that renders a node independent of the rest of the graph). If this initial discovery is inaccurate—perhaps due to very low sample sizes—the subsequent recursive steps may suffer.

Additionally, one of the theoretical guarantees assumes that the part of the graph induced by selection bias is "chordal." While common in real-world scenarios, this remains a mathematical constraint. Future work will likely focus on developing even more robust methods for initial Markov boundary discovery, making the algorithm increasingly resilient to noisy, real-world data.

Summary updated

Abstract

We consider the problem of learning the causal MAG of a system from observational data in the presence of latent variables and selection bias. Constraint-based methods are one of the main approaches for solving this problem, but the existing methods are either computationally impractical when dealing with large graphs or lacking completeness guarantees. We propose a novel computationally efficient recursive constraint-based method that is sound and complete. The key idea of our approach is that at each iteration a specific type of variable is identified and removed. This allows us to learn the structure efficiently and recursively, as this technique reduces both the number of required conditional independence (CI) tests and the size of the conditioning sets. The former substantially reduces the computational complexity, while the latter results in more reliable CI tests. We provide an upper bound on the number of required CI tests in the worst case. To the best of our knowledge, this is the tightest bound in the literature. We further provide a lower bound on the number of CI tests required by any constraint-based method. The upper bound of our proposed approach and the lower bound at most differ by a factor equal to the number of variables in the worst case. We provide experimental results to compare the proposed approach with the state of the art on both synthetic and real-world structures.
BibTeX
@inproceedings{akbari2021recursive,
  author = {Sina Akbari and Ehsan Mokhtarian and AmirEmad Ghassami and Negar Kiyavash},
  title = {{Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=eElERAwRbo},
}
Figure