The combinatorial problem of learning directed acyclic graphs (DAGs) from
data was recently framed as a purely continuous optimization problem by
leveraging a differentiable acyclicity characterization of DAGs based on the
trace of a matrix exponential function. Existing acyclicity characterizations
are based on the idea that powers of an adjacency matrix contain information
about walks and cycles. In this work, we propose a new acyclicity
characterization based on the log-determinant (log-det) function, which
leverages the nilpotency property of DAGs. To deal with the inherent
asymmetries of a DAG, we relate the domain of our log-det characterization to
the set of $\textit{M-matrices}$, which is a key difference to the classical
log-det function defined over the cone of positive definite matrices. Similar
to acyclicity functions previously proposed, our characterization is also exact
and differentiable. However, when compared to existing characterizations, our
log-det function: (1) Is better at detecting large cycles; (2) Has
better-behaved gradients; and (3) Its runtime is in practice about an order of
magnitude faster. From the optimization side, we drop the typically used
augmented Lagrangian scheme and propose DAGMA ($\textit{DAGs via M-matrices for
Acyclicity}$), a method that resembles the central path for barrier methods.
Each point in the central path of DAGMA is a solution to an unconstrained
problem regularized by our log-det function, then we show that at the limit of
the central path the solution is guaranteed to be a DAG. Finally, we provide
extensive experiments for $\textit{linear}$ and $\textit{nonlinear}$ SEMs and
show that our approach can reach large speed-ups and smaller structural Hamming
distances against state-of-the-art methods. Code implementing the proposed
method is open-source and publicly available at
this https URL

该研究提出了一种基于对数行列式函数的新型有向无环图（DAG）的无环性描述，该描述利用 DAG 的幂零属性将其与正定矩阵锥定义的经典对数行列式函数进行了区分。该方法与现有技术相比，对于检测大型循环性更好，在梯度方面更好，并且实际运行时间大约快一个数量级。在数值实验中表明，该方法能够获得较大的速度提升和较小的结构 Hamming 距离。