Learning equivalence classes of acyclic models with latent and selection variables from multiple datasets with overlapping variables

Robert E. Tillman, Peter SpirtesAISTATS 2011 · OpenReview

Abstract

Causal discovery often faces the challenge of "structured missingness," where variables are measured across multiple datasets with only partial overlap. Traditional methods like ION attempt to merge independently learned graphs, often failing due to statistical contradictions. We present the Integration of Overlapping Datasets (IOD) algorithm, which pools statistical power across datasets using meta-analysis of p-values. IOD is shown to be more accurate, efficient, and robust than previous state-of-the-art methods, as evidenced by synthetic benchmarks and real-world fMRI data analysis.

Introduction

In fields like neuroscience or genomics, it is often impossible to measure all relevant variables simultaneously. Researchers frequently work with multiple datasets that measure different, overlapping subsets of variables. Standard causal discovery algorithms typically require a single unified dataset. The previous approach, ION, attempted to resolve this by learning local graphs and stitching them together. However, minor statistical noise can lead to logical contradictions between local graphs, causing these algorithms to fail or produce inaccurate models.

Methodology: Integration at the Statistical Level

The core innovation of the IOD algorithm is shifting integration from the graph level to the statistical test level. Instead of resolving conflicts between finished graphs, IOD combines the underlying evidence from every dataset capable of performing a specific conditional independence test.

Robust Conditional Independence Testing

IOD utilizes Fisher’s method to combine p-values from multiple datasets. This approach pools statistical power, making the resulting tests more reliable than those performed on any single dataset.

The IOD algorithm for pooling p-values across datasets using Fisher's method.

The algorithm operates within the framework of Maximal Ancestral Graphs (MAGs) and Partial Ancestral Graphs (PAGs), allowing it to account for latent confounders and selection bias. The learning process follows a two-stage approach: first identifying adjacencies and inducing paths, then systematically constructing the equivalence class consistent with the marginalized independence constraints of the input data.

Experimental Evaluation

The authors evaluated IOD against the ION algorithm using both synthetic simulations and real-world fMRI data.

  • Simulated Data: Random directed acyclic structures (8 and 14 variables) were tested under various degrees of overlap.
  • Real-world fMRI Data: Data from 13 subjects performing a word-pair task was used. The inherent recording limitations created a natural "overlapping variables" scenario across 11 brain regions.

Key Results

IOD demonstrates significant improvements in both accuracy and computational efficiency compared to the ION baseline.

Performance comparison between IOD and ION across various metrics and sample sizes.

Accuracy and Robustness

In simulations, IOD maintained high precision and recall as sample sizes increased. ION, conversely, frequently failed to return results because it could not resolve contradictions between local graphs. By merging evidence (p-values) rather than conclusions (graphs), IOD avoids these "dead ends" and achieves asymptotic correctness.

Computational Efficiency

IOD is orders of magnitude faster and more memory-efficient. In 14-variable scenarios where ION required over 300MB of memory and several minutes of runtime, IOD completed in seconds while staying under 50MB of memory usage.

fMRI Validation

On real brain data, IOD successfully reconstructed a causal map consistent with neuroscientific domain knowledge, identifying a clear signal flow from the left to the right hemisphere.

Conclusion and Future Work

IOD provides a robust framework for causal discovery from fragmented data. While currently assuming a shared underlying process and linear relationships, future work could extend IOD to non-linear or non-Gaussian settings to further refine the identified equivalence classes.

Summary updated

BibTeX
@inproceedings{tillman2011learning,
  author = {Robert E. Tillman and Peter Spirtes},
  title = {{Learning equivalence classes of acyclic models with latent and selection variables from multiple datasets with overlapping variables}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=vMVkOX_o4ZI},
}
Figure