TL;DR
This paper proves that learning sparse causal models, even with hidden confounders and selection bias, is not NP-hard. They achieve this by adapting the FCI algorithm to run in polynomial time with respect to the number of variables and the maximum node degree, offering a significant theoretical advancement for causal discovery.
What Problem Does This Paper Address?
Causal discovery, the process of inferring cause-and-effect relationships from observational data, is a fundamental goal in scientific progress. While significant strides have been made, many researchers consider causal discovery to be computationally intractable, often likened to NP-hard problems like learning minimal Bayesian networks. This perceived difficulty stems from the complexity of dealing with unobserved variables (latent confounders) and situations where only a subset of variables is observed (selection bias). The paper aims to challenge this notion by demonstrating that for sparse causal models, the problem is, in fact, computationally tractable.
Methods
The core of the paper's contribution lies in adapting and extending the Fast Causal Inference (FCI) algorithm. The authors introduce a modified FCI algorithm, termed "FCI+", which incorporates a novel "D-SEP search" strategy. This strategy leverages the inherent structure of sparse causal graphs to efficiently identify "D-separating sets" – crucial sets of variables that reveal independencies.
Key methodological aspects include:
- D-SEP Links and Hierarchies: The paper defines and exploits "D-sep links" and their hierarchical structure. This hierarchy allows for a more structured and efficient search for separating sets, breaking down the problem into smaller, manageable subproblems.
- Augmented Skeleton (G+): A new graph representation, G+, is introduced to capture invariant arrowheads and facilitate the identification of potential D-sep links.
- Polynomial Time Complexity: By carefully analyzing the structure of sparse graphs and the relationships between D-sep links, the authors show that the search for separating sets can be performed in polynomial time, specifically O(N²(k+2)), where N is the number of variables and k is the maximum node degree. This is a significant improvement over the exponential complexity associated with general causal discovery or learning minimal Bayesian networks.
- Handling Latent Variables and Selection Bias: The FCI+ algorithm, building on FCI, is designed to be sound and complete even in the presence of unobserved confounders and selection bias, which are common challenges in real-world data.
Datasets
Not discussed in the paper. The paper focuses on theoretical contributions and algorithmic development, relying on an "independence oracle" rather than specific datasets for evaluation.
Key Insights and Ideas
- Causal Discovery is Not Inherently NP-hard (for sparse models): The most significant insight is that the computational barrier for causal discovery is not absolute but depends on the sparsity of the underlying causal graph. This challenges a long-held assumption in the field.
- Structure Enables Efficiency: The paper demonstrates that by exploiting the hierarchical structure of D-separating links and the properties of sparse graphs, a polynomial-time algorithm can be constructed. This highlights the power of leveraging domain-specific structure in algorithmic design.
- D-SEP Links as a Key to Tractability: The concept of D-sep links and their systematic identification is central to the algorithm's efficiency. Their structured nature allows for a more targeted and less exhaustive search compared to brute-force methods.
- FCI's Potential for Polynomiality: The paper shows that a well-established algorithm like FCI, when augmented with a specialized search strategy, can achieve polynomial time complexity, suggesting that existing frameworks might be adaptable to overcome computational hurdles.
Key Results
The paper's primary result is the theoretical demonstration that learning sparse causal models is not NP-hard. This is achieved through the development of the FCI+ algorithm, which has a worst-case running time complexity of O(N²(k+2)) for the number of independence tests. This polynomial complexity holds even in the presence of latent variables and selection bias, provided the underlying causal graph is sparse (bounded node degree k). The paper does not present empirical results on specific datasets but focuses on the theoretical guarantees of its algorithm.
Limitations and Future Work
- Practical Performance for Large N: While polynomial, the O(N²(k+2)) complexity is still considered infeasible for very large numbers of variables (N). The authors acknowledge this and suggest that practical performance is often much better due to the inherent sparsity and structure.
- Sample-Based Limitations: For real-world data (sample-based versions), the conditioning sets used in independence tests might become larger than strictly necessary, potentially reducing statistical power.
- Score-Based Methods: The paper raises an intriguing question about whether polynomial-time score-based causal discovery methods also exist, a direction for future research.
- Optimizing Implementation: The authors explicitly state they are not aiming for an optimal implementation but rather to prove the theoretical possibility of a polynomial solution. Further optimization of the FCI+ algorithm is a natural next step.
- Addressing Selection Bias Impact: While the proofs are valid with selection bias, the paper notes that selection bias can make D-sep links rarer and potentially avoid the need for D-sep node searches. Further investigation into this interaction is suggested.
Summary updated