From graphs to DAGs: a low-complexity model and a scalable algorithm
  Learning directed acyclic graphs (DAGs) is long known a critical challenge at
the core of probabilistic and causal modeling. The NoTears approach of (Zheng
et al., 2018), through a differentiable function involving the matrix
exponential trace $\mathrm{tr}(\exp(\cdot))$, opens up a way to learning DAGs
via continuous optimization, though with a $O(d^3)$ complexity in the number
$d$ of nodes. This paper presents a low-complexity model, called LoRAM for
Low-Rank Additive Model, which combines low-rank matrix factorization with a
sparsification mechanism for the continuous optimization of DAGs. The main
contribution of the approach lies in an efficient gradient approximation method
leveraging the low-rank property of the model, and its straightforward
application to the computation of projections from graph matrices onto the DAG
matrix space. The proposed method achieves a reduction from a cubic complexity
to quadratic complexity while handling the same DAG characteristic function as
NoTears, and scales easily up to thousands of nodes for the projection problem.
The experiments show that the LoRAM achieves efficiency gains of orders of
magnitude compared to the state-of-the-art at the expense of a very moderate
accuracy loss in the considered range of sparse matrices, and with a low
sensitivity to the rank choice of the model's low-rank component.
