# Reliable Causal Discovery with Improved Exact Search and Weaker Assumptions

arXiv: https://arxiv.org/abs/2201.05666 · HTML: https://mlsanity.com/paper/2201.05666/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 53 references that are in the map.
- First posted on arXiv 14 Jan 2022.

## Builds on (most cited first, 8 of 8)

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [On the Role of Sparsity and DAG Constraints for Learning Linear DAGs](https://mlsanity.com/paper/2006.10201/) (2020)
- [Causal Inference in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/1302.4983/) (2013)
- [High-dimensional learning of linear causal networks via inverse covariance estimation](https://mlsanity.com/paper/1311.3492/) (2013)
- [Discovering Cyclic Causal Models with Latent Variables: A General SAT-Based Procedure](https://mlsanity.com/paper/1309.6836/) (2013)
- [Structural Intervention Distance (SID) for Evaluating Causal Graphs](https://mlsanity.com/paper/1306.1043/) (2013)
- [Learning big Gaussian Bayesian networks: partition, estimation, and fusion](https://mlsanity.com/paper/1904.10900/) (2019)
- [A Uniformly Consistent Estimator of Causal Effects under the k-Triangle-Faithfulness Assumption](https://mlsanity.com/paper/1502.00829/) (2015)

## Built on by (most cited first, 19 of 19)

- [Causal Representation Learning from Multiple Distributions: A General Setting](https://mlsanity.com/paper/2402.05052/) (2024)
- [MissDAG: Causal Discovery in the Presence of Missing Data with Continuous Additive Noise Models](https://mlsanity.com/paper/2205.13869/) (2022)
- [Expert-Aided Causal Discovery of Ancestral Graphs](https://mlsanity.com/paper/2309.12032/) (2023)
- [DCILP: A Distributed Approach for Large-Scale Causal Structure Learning](https://mlsanity.com/paper/2406.10481/) (2024)
- [Generalized Precision Matrix for Scalable Estimation of Nonparametric Markov Networks](https://mlsanity.com/paper/2305.11379/) (2023)
- [Local Causal Discovery with Linear non-Gaussian Cyclic Models](https://mlsanity.com/paper/2403.14843/) (2024)
- [Domain Knowledge in A*-Based Causal Discovery](https://mlsanity.com/paper/2208.08247/) (2022)
- [Since Faithfulness Fails: The Performance Limits of Neural Causal Discovery](https://mlsanity.com/paper/2502.16056/) (2025)
- [On the Sparse DAG Structure Learning Based on Adaptive Lasso](https://mlsanity.com/paper/2209.02946/) (2022)
- [Whole Page Unbiased Learning to Rank](https://mlsanity.com/paper/2210.10718/) (2022)
- [Robust Causal Discovery under Imperfect Structural Constraints](https://mlsanity.com/paper/2511.06790/) (2025)
- [A General Representation-Based Approach to Multi-Source Domain Adaptation](https://mlsanity.com/paper/2604.23790/) (2026)
- [Learning Large Causal Structures from Inverse Covariance Matrix via Sparse Matrix Decomposition](https://mlsanity.com/paper/2211.14221/) (2022)
- [Causal Razors](https://mlsanity.com/paper/2302.10331/) (2023)
- [Probabilistic and Causal Satisfiability: Constraining the Model](https://mlsanity.com/paper/2504.19944/) (2025)
- [Distributionally Robust Skeleton Learning of Discrete Bayesian Networks](https://mlsanity.com/paper/2311.06117/) (2023)
- [Efficient Differentiable Causal Discovery via Reliable Super-Structure Learning](https://mlsanity.com/paper/2601.05474/) (2026)
- [Efficient Causal Structure Learning via Modular Subgraph Integration](https://mlsanity.com/paper/2601.21014/) (2026)
- [Demistifying Data and Simulator Assumptions in Supervised Causal Discovery](https://mlsanity.com/paper/2609.37446/) (2026)

## Abstract (arXiv)

Many of the causal discovery methods rely on the faithfulness assumption to guarantee asymptotic correctness. However, the assumption can be approximately violated in many ways, leading to sub-optimal solutions. Although there is a line of research in Bayesian network structure learning that focuses on weakening the assumption, such as exact search methods with well-defined score functions, they do not scale well to large graphs. In this work, we introduce several strategies to improve the scalability of exact score-based methods in the linear Gaussian setting. In particular, we develop a super-structure estimation method based on the support of inverse covariance matrix which requires assumptions that are strictly weaker than faithfulness, and apply it to restrict the search space of exact search. We also propose a local search strategy that performs exact search on the local clusters formed by each variable and its neighbors within two hops in the super-structure. Numerical experiments validate the efficacy of the proposed procedure, and demonstrate that it scales up to hundreds of nodes with a high accuracy.