Learning high-dimensional directed acyclic graphs with latent and selection variables
Open accessAbstract
We consider the problem of learning causal information between random variables in directed acyclic graphs (DAGs) when allowing arbitrarily many latent and selection variables. The FCI (Fast Causal Inference) algorithm has been explicitly designed to infer conditional independence and causal information in such settings. However, FCI is computationally infeasible for large graphs. We therefore propose the new RFCI algorithm, which is much faster than FCI. In some situations the output of RFCI is slightly less informative, in particular with respect to conditional independence information. However, we prove that any causal information in the output of RFCI is correct in the asymptotic limit. We also define a class of graphs on which the outputs of FCI and RFCI are identical. We prove consistency of FCI and RFCI in sparse high-dimensional settings, and demonstrate in simulations that the estimation performances of the algorithms are very similar. All software is implemented in the R-package pcalg.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Subsequent improvements such as RFCI, PC-Stable, and PCMCI have consistently failed to overcome the fundamental flaw that CI tests are highly prone to statistical errors under high-dimensional, sparse logs.
“Although subsequent improvements exist, such as RFCI[14] (sacrificing information for speed), PC-Stable[15] (eliminating order dependency), and PCMCI[16] for time-series data, they have consistently failed to overcome the fundamental flaw that CI tests are highly prone to statistical errors under high-dimensional, sparse logs.”
From From Correlation to Intervention: A Survey on Log-Based Causal Analysis for Security and AIOps (2026) · cites this paper as [14]
The Introduction (§1.3; page not supplied) says RFCI is faster than FCI, may be less informative, and avoids some low-power conditional-independence tests in small samples. But §4 and the Discussion (§6) prove consistency for RFCI in sparse high-dimensional settings; the paper does not assess PC-Stable, PCMCI, or sparse logs, and does not establish that these methods consistently fail because of testing errors. (LLM, conf=0.88)
Experimental — accuracy not yet measuredThese algorithms have been shown to be consistent, even in certain sparse high-dimensional settings.
“These algorithms have been shown to be consistent, even in certain sparse high-dimensional settings [Kalisch and B¨ uhlmann (2007), Colombo et al. (2012)].”
From A generalized back-door criterion (2015) · cites this paper as Colombo et al. (2012)
There are algorithms to estimate CPDAGs and PAGs from data.
“since there are algorithms to estimate CPDAGs and PAGs from data (e.g., the PC algorithm [Spirtes, Glymour and Scheines (2000)], greedy equivalence search [Chickering (2002)] and versions of the FCI algorithm [Spirtes, Glymour and Scheines (2000), Colombo et al. (2012), Claassen, Mooij and Heskes (2013)]).”
From A generalized back-door criterion (2015) · cites this paper as Colombo et al. (2012)
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Causal inference in statistics: An overview
Pearl, J. (2009) · Statistics Surveys · doi:10.1214/09-ss057 · Cited by 2,336 · cited 1× · see citing works
“hat causal information between variables can be represented by a directed acyclic graph (DAG) in which the vertices represent random variables and the edges represent direct causal effects (see, e.g., [13, 14, 20]). In particular, X 1 is a direct cause of X 2 only if X 1 →X 2 (i.e., X 1 is a parent of X 2), and X 1 is…”
BackgroundPredicting causal effects in large-scale systems from observational data
Maathuis, M. H., Colombo, D., Kalisch, M., & Bühlmann, P. (2010) · Nature Methods · doi:10.1038/nmeth0410-247 · Cited by 217 · see citing works
Self-citation
Flagged first, then by citations
Research works printed but not linked: 11
- AHO, A., HOPCROFT, J. and ULLMAN, J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley, Boston, MA.
- COLOMBO, D., MAATHUIS, M. H., KALISCH, M. and RICHARDSON, T. S. (2012). Sup- plement to "Learning high-dimensional directed acyclic graphs with latent and selection variables." DOI:10.1214/11-AOS940SUPP. · DOI
- COOPER, G. (1995). Causal discovery from data in the presence of selection bias. In Prelim- inary Papers of the Fifth International Workshop on Artificial Intelligence and Statistics (D. Fisher, ed.) 140-150.
- PEARL, J. (2000). Causality. Models, Reasoning, and Inference. Cambridge Univ. Press, Cam- bridge. MR1744773
- RAMSEY, J., ZHANG, J. and SPIRTES, P. (2006). Adjacency-faithfulness and conservative causal inference. In Proceedings of the 22nd Annual Conference on Uncertainty in Artifi- cial Intelligence. AUAI Press, Arlington, VA.
- RICHARDSON, T. S. and SPIRTES, P. (2003). Causal inference via ancestral graph models. In Highly Structured Stochastic Systems. Oxford Statistical Science Series 27 83-113. Oxford Univ. Press, Oxford. MR2082407
- SPIRTES, P. (2001). An anytime algorithm for causal inference. In Proc. of the Eighth Inter- national Workshop on Artificial Intelligence and Statistics 213-221.
- Morgan Kaufmann, San Francisco.
- SPIRTES, P., GLYMOUR, C. and SCHEINES, R. (2000). Causation, Prediction, and Search, 2nd ed. MIT Press, Cambridge, MA. MR1815675
- SPIRTES, P., MEEK, C. and RICHARDSON, T. (1999). An algorithm for causal inference in the presence of latent variables and selection bias. In Computation, Causation, and Discovery 211-252. AAAI Press, Menlo Park, CA. MR1689972
- VERMA, T. and PEARL, J. (1990). Equivalence and synthesis of causal models. In Proceed- ings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence 255-270. Elsevier, New York.
Cited by
Sorted by citations
Methods for causal inference from gene perturbation experiments and validation
Meinshausen, N., Hauser, A., Mooij, J. M., Peters, J., Versteeg, P., & Bühlmann, P. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1510493113 · Cited by 140 · see citing works
Learning Functional Causal Models with Generative Neural Networks
Goudet, O., Kalainathan, D., Caillou, P., Guyon, I., Lopez-Paz, D., & Sebag, M. (2018) · The Springer Series on Challenges in Machine Learning · doi:10.1007/978-3-319-98131-4_3 · Cited by 123 · see citing works
A generalized back-door criterion
Maathuis, M. H., & Colombo, D. (2015) · The Annals of Statistics · doi:10.1214/14-aos1295 · Cited by 88 · see citing works
Self-citationCausal Structure Learning: A Combinatorial Perspective
Squires, C., & Uhler, C. (2023) · Foundations of Computational Mathematics · doi:10.1007/s10208-022-09581-9 · Cited by 31 · see citing works
From Correlation to Intervention: A Survey on Log-Based Causal Analysis for Security and AIOps
Zhu, Y., Li, X., Suo, J., Yin, Y., & Huang, C. (2026) · 2026 International Conference on AI in Education Technology and Applications (AIETA) · doi:10.1109/aieta69357.2026.11508946
- Authors
- Colombo, D., Maathuis, M. H., Kalisch, M., & Richardson, T. S.
- Affiliations
- University of Washington (US)
- ORCID
- Maathuis, Marloes H.
- Venue
- The Annals of Statistics
- Publisher
- Institute of Mathematical Statistics
- Published
- 2012-02-01
- Volume
- 40
- Issue
- 1
- Pages
- 294-321
- ISSN
- 0090-5364 (ISSN-L)
- 2168-8966
- OpenAlex
- W2163687466
- Cited by
- 384
- References
- 2
- Citations by year
- 2026: 34 · 2025: 26 · 2024: 27 · 2023: 40 · 2022: 34 · 2021: 38 · 2020: 48 · 2019: 34 · 2018: 19 · 2017: 22 · 2016: 17 · 2015: 16 · 2014: 17 · 2013: 5 · 2012: 7
- FWCI
- 14.17
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- The Annals of Statistics (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Project Euclid (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (0855230, R01 AI032475)
- National Institutes of Health (AI032475)
- National Institute of Allergy and Infectious Diseases (R01AI032475)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Modeling and Causal Inference
- Physical Sciences › Mathematics › Statistics and Probability › Statistical Methods and Inference
- Physical Sciences › Mathematics › Statistics and Probability › Advanced Causal Inference Techniques
- Keywords
- directed acyclic graphs, causal discovery, latent variables, conditional independence, high-dimensional causal inference, consistency, sparse graphs
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
