Abstract
Causal discovery in Bayesian networks (BNs) typically relies on the assumption of causal sufficiency—the premise that all relevant variables have been observed. In practice, however, latent variables often introduce spurious correlations. This paper presents a novel dynamic programming algorithm for calculating the exact posterior probability of ancestor relations. Our findings indicate that Bayesian model averaging is remarkably robust to unobserved variables, effectively recovering the causal "skeleton" of a system through a process of path contraction, even when more than half of the variables remain hidden.
Introduction
A fundamental challenge in causal discovery is the presence of unobserved variables. When learning the structure of a Bayesian network from data, these latent factors can create dependencies that mimic direct causal relationships. While constraint-based methods like the Fast Causal Inference (FCI) algorithm are designed to handle such scenarios, they often lack statistical power or fail to provide a measure of posterior certainty. This research bridges the gap by evaluating how score-based Bayesian methods perform under model misspecification—specifically, when the model assumes no hidden nodes while the underlying data generating process includes them.
Methodology
The primary contribution of this work is a dynamic programming (DP) algorithm designed for exact Bayesian discovery of ancestor relations.
The Computational Challenge
While calculating the probability of a single arc ($X \to Y$) is a local property, determining an ancestor relation ($X \rightsquigarrow Y$) is a global property, requiring the summation of probabilities across all possible paths in all possible graphs. To address this combinatorial complexity, the authors developed a DP approach that iterates through subsets of nodes.
Algorithm and Complexity
The algorithm tracks which nodes within a subset are descendants of a specific source node, building global ancestry probabilities incrementally. By utilizing the Fast Zeta Transform to optimize inner summations, the algorithm achieves a time complexity of $O(n^2 3^n)$ and a space complexity of $O(3^n)$. This allows for exact inference on networks containing up to approximately 20 observed nodes.
Key Insights: Path Contraction and Robustness
A critical insight from this study is the phenomenon of path contraction. When a node is unobserved, a Bayesian learner does not simply fail; instead, it tends to "shrink" the graph. For instance, if a true causal path exists as $A \to \text{Hidden} \to B$, the algorithm frequently identifies a direct arc $A \to B$. While this arc is technically a false positive in the context of the original full graph, it correctly identifies the underlying ancestor relation.
Furthermore, the research highlights that Bayesian model averaging—which considers all possible graphs weighted by their posterior probability—is significantly more robust than selecting a single Maximum A Posteriori (MAP) graph. The MAP graph is often sensitive to noise, whereas the average captures the persistent causal signals.
Experimental Results
The approach was evaluated using synthetic 14-node networks and real-world datasets (UCI ADULT and HOUSING).
- Resilience to Hidden Variables: In synthetic tests, the algorithm maintained a ~75% true positive rate for ancestor relations even when 10 out of 14 nodes were hidden, provided sufficient data was available.
- Statistical Power: Compared to the FCI algorithm, the Bayesian approach exhibited much higher statistical power. While FCI is conservative and avoids false positives, it often fails to detect existing causal relations that the Bayesian method successfully identifies.
- Computational Feasibility: Exact computation for a 14-node network took approximately 8 hours on 2011-era hardware, establishing a "gold standard" for high-confidence inference in small-to-medium networks.
Conclusion
This work demonstrates that Bayesian methods are surprisingly effective at identifying ancestor relations even when the assumption of causal sufficiency is violated. The "shrunken ground truth" resulting from path contraction provides a reliable proxy for the true causal structure. Future work may explore scaling these insights through MCMC sampling or hybrid heuristic approaches to handle larger systems where exact DP remains computationally prohibitive.
Summary updated