Ancestor Relations in the Presence of Unobserved Variables

Pekka Parviainen, Mikko Koivisto

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.

Illustration of path contraction where paths through unobserved nodes (outside set T) are represented as direct ancestor relations (red arrows).

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

Abstract

Bayesian networks (BNs) are an appealing model for causal and non-causal dependencies among a set of variables. Learning BNs from observational data is challenging due to the nonidentifiability of the network structure and model misspecification in the presence of unobserved (latent) variables. Here, we investigate the prospects of Bayesian learning of ancestor relations, including arcs, in the presence and absence of unobserved variables. An exact dynamic programming algorithm to compute the respective posterior probabilities is developed, under the complete data assumption. Our experimental results show that ancestor relations between observed variables, arcs in particular, can be learned with good power even when a majority of the involved variables are unobserved. For comparison, deduction of ancestor relations from single maximum a posteriori network structures or their Markov equivalence class appears somewhat inferior to Bayesian averaging. We also discuss some shortcomings of applying existing conditional independence test based methods for learning ancestor relations.
BibTeX
@inproceedings{parviainen2011ancestor,
  author = {Pekka Parviainen and Mikko Koivisto},
  title = {{Ancestor Relations in the Presence of Unobserved Variables}},
  booktitle = {ECML/PKDD},
  year = {2011},
  doi = {10.1007/978-3-642-23783-6\_37},
}
Figure