ExDAG: an MIQP Algorithm for Learning DAGs
This addresses the challenge of efficiently learning causal DAGs, which is important for fields like statistics and machine learning, though it appears incremental by building on integer programming techniques.
The paper tackles the problem of learning directed acyclic graphs (DAGs) for causal structures by proposing ExDAG, a mixed-integer quadratic programming algorithm that guarantees exact learning and uses lazy constraints to improve scalability. Empirical results show it outperforms state-of-the-art solvers in structural Hamming distance and F1 score on medium-sized graphs with Gaussian noise.
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 an associated algorithm that identifies DAGs with a low structural Hamming distance between the identified DAG and the ground truth, under identifiability assumptions. The eventual exact learning is guaranteed by the global convergence of the branch-and-bound-and-cut algorithm, which is utilized. In addition to this, integer programming techniques give us access to the dual bound, which allows for a real time assessment of the quality of solution. Previously, integer programming techniques have been shown to lead to limited scaling in the case of DAG identification due to the super exponential number of constraints, which prevent the formation of cycles. The algorithm proposed circumvents this by selectively generating only the violated constraints using the so-called "lazy" constraints methodology. Our empirical results show that ExDAG outperforms state-of-the-art solvers in terms of structural Hamming distance and $F_1$ score when considering Gaussian noise on medium-sized graphs.