Reliable Causal Discovery with Improved Exact Search and Weaker Assumptions

Ignavier Ng, Yujia Zheng, Jiji Zhang, Kun Zhang

Overview

Researchers have developed a new framework for causal discovery that scales exact search algorithms—previously limited to tiny networks—to graphs with hundreds of nodes. By relaxing the restrictive "faithfulness" assumption and utilizing a "divide-and-conquer" local search strategy, the method provides a more reliable way to uncover cause-and-effect relationships in linear Gaussian data.

The Challenge: Faithfulness and Scalability

Causal discovery is the holy grail of data science: moving beyond the adage that "correlation is not causation" to actually map out the directed acyclic graph (DAG) of how variables influence one another.

Most existing methods rely heavily on the faithfulness assumption, which posits that every conditional independence found in the data corresponds to a missing edge in the causal graph. In reality, this assumption is frequently violated. For example, "path cancellations" can occur where two causal paths perfectly offset each other, masking the true relationship. When faithfulness fails, popular algorithms like PC or GES often produce incorrect graphs.

Exact search methods (such as the A* algorithm) are much more robust because they search for the "best" graph according to a well-defined score (like the Bayesian Information Criterion, or BIC). However, because the number of possible graphs grows exponentially with the number of variables, exact search has historically been limited to very small problems—usually under 30 variables. This paper aims to make these robust, exact methods scale to large-scale, real-world problems.

A Two-Stage Methodology

The authors introduce a two-stage approach to bridge the gap between reliability and scalability:

1. Super-Structure Estimation via Inverse Covariance

Instead of searching the entire space of possible graphs, the authors first estimate a "super-structure"—an undirected graph that is guaranteed to contain all the true causal edges. They use the Graphical Lasso (GLasso) to estimate the support of the inverse covariance matrix.

Crucially, they prove that this works under a new, much weaker assumption called Single Shielded-Collider-Faithfulness (SSCF). In a linear Gaussian setting, if two variables are not neighbors and don't share a common child, their partial correlation (given all other variables) is zero. This allows the algorithm to quickly prune the search space without losing true edges.

Minimum absolute values of the inverse covariance matrix entries for neighbors and non-adjacent spouses across varying graph sizes.

To handle large graphs, the researchers propose a "divide-and-conquer" strategy. Instead of running one massive A* search, they perform exact searches on "local clusters" (a variable and its neighbors within two hops in the super-structure). They use an iterative process to fix discovered edges and v-structures, drastically reducing the search space for subsequent clusters.

Experimental Setup

The paper evaluates the method using synthetic datasets generated via:

  • Erdös–Rényi models: Used to create ground-truth DAG structures with varying degrees of sparsity and density.
  • Linear Gaussian SEMs: Data is simulated by assigning weights to edges and adding Gaussian noise.
  • Scale: Experiments range from small 10-node graphs (to test accuracy under assumption violations) up to 300-node graphs (to test scalability).

Key Insights and Results

  • Relaxing Faithfulness: The most significant theoretical contribution is the move toward the Sparsest Markov Representation (SMR) and SSCF assumptions. These are mathematically "weaker," meaning they are more likely to hold true in real-world data than the standard faithfulness used by most algorithms.
  • Iterative Refinement: The "Local A*" algorithm doesn't just run independent local searches; it is an iterative process. By "trusting" the edges found in smaller, easier clusters, the algorithm can "freeze" those parts of the graph, making the search in larger, more complex clusters much faster.
  • Scalability: While standard A search struggles beyond 20 nodes, the proposed Local A successfully scales to 300 nodes** within a reasonable timeframe.
  • Accuracy: On 10-node graphs where faithfulness is intentionally violated, the proposed method maintains a high True Positive Rate (TPR), whereas traditional methods like MMPC see their accuracy plummet.
  • Structural Hamming Distance (SHD): The method consistently achieved lower SHD (meaning fewer errors in the final graph) compared to baselines like FGES, MMHC, and Triplet A*, especially as the graphs became denser.

Limitations and Future Work

While a significant step forward, the current theoretical guarantees and the use of inverse covariance matrices rely on the data being linear and Gaussian. The authors acknowledge that extending this to non-linear or discrete data is a necessary next step.

Additionally, while the local search is much faster, the running time still depends on the maximum size of the local clusters. In very dense graphs, these clusters might still become large enough to slow down the A* search. Future directions include exploring other efficient estimation methods (like QUIC) for the super-structure and adapting the framework for non-Gaussian settings.

Summary updated

Abstract

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.
BibTeX
@inproceedings{ng2021reliable,
  author = {Ignavier Ng and Yujia Zheng and Jiji Zhang and Kun Zhang},
  title = {{Reliable Causal Discovery with Improved Exact Search and Weaker Assumptions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=xVJvlYUGUlf},
}
Figure