ExDAG: Exact learning of DAGs

Pavel Rytír, Ales Wodecki, Jakub MarecekarXiv 2024 · arXiv · OpenReview

Abstract

There has been a growing interest in causal learning in recent years. Commonly used representations of causal structures, including Bayesian networks and structural equation models (SEM), take the form of directed acyclic graphs (DAGs). We provide a novel mixed-integer quadratic programming formulation and associated algorithm that identifies DAGs on up to 50 vertices, where these are identifiable. We call this method ExDAG, which stands for Exact learning of DAGs. Although there is a superexponential number of constraints that prevent the formation of cycles, the algorithm adds constraints violated by solutions found, rather than imposing all constraints in each continuous-valued relaxation. Our empirical results show that ExDAG outperforms local state-of-the-art solvers in terms of precision and outperforms state-of-the-art global solvers with respect to scaling, when considering Gaussian noise. We also provide validation with respect to other noise distributions.

Introduction

Causal discovery aims to uncover the underlying directed acyclic graph (DAG) structure that governs the relationships between variables in a system. A primary challenge in this field is the acyclicity constraint; the number of possible cycles grows superexponentially with the number of variables, making exact learning computationally intensive. Historically, researchers have chosen between exact methods, which are guaranteed to find the global optimum but are limited to very small graphs, and continuous relaxations (e.g., NOTEARS), which scale well but may get stuck in local minima.

ExDAG (Exact learning of DAGs) bridges this gap. By combining the mathematical rigor of Mixed-Integer Quadratic Programming (MIQP) with efficient algorithmic strategies, ExDAG achieves global optimality for medium-sized graphs (up to 25–50 variables), offering a significant improvement in accuracy over popular continuous optimization methods.

Methodology: MIQP with Lazy Constraints

ExDAG formulates DAG learning as an MIQP problem based on a Linear Structural Equation Model (SEM). In this model, each variable is represented as a linear combination of its parents plus noise. The objective is to minimize a score function—specifically the Frobenius norm of the error—augmented with a sparsity-inducing regularization term.

Lazy Constraints and Cycle Detection

To handle the exponential number of acyclicity constraints, ExDAG employs a "branch-and-bound-and-cut" approach using lazy constraints. Rather than imposing all cycle-exclusion constraints upfront, the algorithm begins with a relaxed problem. When a candidate solution is found, a Depth-First Search (DFS) is performed to detect cycles. If a cycle is present, a corresponding constraint is added to the solver. This "lazy" approach significantly reduces the memory footprint and initial complexity while maintaining the requirement for a valid DAG.

Optimization Strategy

The authors found that the simplex algorithm is particularly effective for this formulation. Unlike barrier methods, the simplex algorithm identifies "corner points" of the search space, which are more easily partitioned by cycle-exclusion cuts, leading to faster overall convergence.

Experimental Evaluation

ExDAG was evaluated against state-of-the-art solvers, including NOTEARS, DAGMA, BOSS, and MICODAG, across various synthetic ensembles (Erdős-Rényi and Scale-Free models) and real-world benchmarks.

Structural Hamming Distance (SHD) performance across various graph types (ER, SF) and sample sizes (n). ExDAG (red) consistently achieves lower SHD compared to continuous optimization methods.

As shown in the figure above, ExDAG consistently outperforms continuous methods like NOTEARS and DAGMA in terms of Structural Hamming Distance (SHD) across a wide range of graph densities and sample sizes. By finding the global minimum of the score function, ExDAG avoids the structural inaccuracies often present in local optima found by continuous relaxations.

Convergence and Efficiency

While exact DAG learning is NP-hard, ExDAG demonstrates practical efficiency for medium-scale problems. A key feature of the MIQP approach is the provision of a "dual bound," which provides a mathematical guarantee of how close the current solution is to the global optimum.

Convergence of SHD over time for ExDAG on graphs with 20 and 25 nodes. The method typically reaches a high-quality plateau within approximately 2000 seconds.

Empirical results indicate that ExDAG often reaches a high-quality solution plateau relatively quickly, as illustrated in the convergence plots. This makes it a viable tool for researchers requiring high-fidelity causal models for systems with up to 30 variables. On the alarm.csv benchmark, ExDAG achieved a best SHD of 55, significantly outperforming NOTEARS' plateau of 65.

Conclusion

ExDAG represents a significant advancement in exact causal discovery. By leveraging MIQP with lazy constraints, it provides global optimality guarantees that were previously computationally prohibitive for medium-sized graphs. While scaling to hundreds of variables remains a challenge for exact methods, ExDAG's superior precision and reliable convergence make it a powerful alternative to continuous relaxations for many practical applications. Future work may involve incorporating structural graph theory or pre-processing steps to further extend the method's scalability.

Summary updated

Abstract

There has been a growing interest in causal learning in recent years. Commonly used representations of causal structures, including Bayesian networks and structural equation models (SEM), take the form of directed acyclic graphs (DAGs). We provide a novel mixed-integer quadratic programming formulation and associated algorithm that identifies DAGs on up to 50 vertices, where these are identifiable. We call this method ExDAG, which stands for Exact learning of DAGs. Although there is a superexponential number of constraints that prevent the formation of cycles, the algorithm adds constraints violated by solutions found, rather than imposing all constraints in each continuous-valued relaxation. Our empirical results show that ExDAG outperforms local state-of-the-art solvers in terms of precision and outperforms state-of-the-art global solvers with respect to scaling, when considering Gaussian noise. We also provide validation with respect to other noise distributions.
BibTeX
@misc{rytir2024exdag,
  author = {Pavel Rytír and Ales Wodecki and Jakub Marecek},
  title = {{ExDAG: Exact learning of DAGs}},
  year = {2024},
  eprint = {2406.15229},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.15229},
}
Figure