Global Directional Priors with Local Statistical Validation for Scalable Causal Discovery

Abstract

Constraint-based causal discovery relies on conditional independence (CI) tests whose reliability degrades as conditioning sets grow, particularly in hub-dominated graphs. Existing methods constrain adjacency or global structure, but leave conditioning-set dimensionality uncontrolled. In this paper, we propose Ordering-Constrained Markov Blanket discovery (OCMB), a paradigm that treats conditioning-set dimensionality as a first-class constraint. OCMB decouples discovery into two stages: lightweight global ordering estimation providing directional priors, followed by local Markov blanket validation within small, ordering-constrained candidate sets. By enforcing directional constraints before any CI test, OCMB ensures bounded conditioning sets even with hub nodes. We show that OCMB recovers correct parent sets provided a high-recall ordering assumption holds, without requiring the ordering to be globally correct. Experiments demonstrate that OCMB significantly improves precision and robustness over constraint-based and hybrid methods in high-dimensional regimes where conventional CI-based approaches fail.