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.

近年来对因果学习的兴趣逐渐增加。常用的因果结构表示方法，包括贝叶斯网络和结构方程模型（SEM），采用有向无环图（DAG）形式。我们提供了一种新颖的混合整数二次规划表达和相关算法，用于识别可识别的50个顶点的DAGs。我们称之为ExDAG，即精确学习DAGs的方法。尽管存在阻止循环形成的超指数个约束条件，该算法通过添加违反找到解的约束条件，而不是在每个连续值放宽中施加所有约束条件。我们的实验结果表明，在考虑高斯噪声时，ExDAG在精度方面优于当地最先进的求解器，在扩展性方面优于最先进的全局求解器。我们还提供了对其他噪声分布的验证。

ExDAG: 精确学习有向无环图