Recursive Causal Structure Learning in the Presence of Latent Variables
  and Selection Bias
  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.
