# From graphs to DAGs: a low-complexity model and a scalable algorithm

arXiv: https://arxiv.org/abs/2204.04644 · HTML: https://mlsanity.com/paper/2204.04644/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 25 references that are in the map.
- First posted on arXiv 10 Apr 2022.

## Builds on (most cited first, 12 of 12)

- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Causal inference using invariant prediction: identification and confidence intervals](https://mlsanity.com/paper/1501.01332/) (2015)
- [DAG-GNN: DAG Structure Learning with Graph Neural Networks](https://mlsanity.com/paper/1904.10098/) (2019)
- [Nonlinear ICA Using Auxiliary Variables and Generalized Contrastive Learning](https://mlsanity.com/paper/1805.08651/) (2018)
- [Learning Sparse Nonparametric DAGs](https://mlsanity.com/paper/1909.13189/) (2019)
- [On the Role of Sparsity and DAG Constraints for Learning Linear DAGs](https://mlsanity.com/paper/2006.10201/) (2020)
- [CAM: Causal additive models, high-dimensional order search and penalized regression](https://mlsanity.com/paper/1310.1533/) (2013)
- [Counterfactual Generative Networks](https://mlsanity.com/paper/2101.06046/) (2021)
- [Structural Agnostic Modeling: Adversarial Learning of Causal Graphs](https://mlsanity.com/paper/1803.04929/) (2018)
- [On Low Rank Directed Acyclic Graphs and Causal Structure Learning](https://mlsanity.com/paper/2006.05691/) (2020)
- [Accelerated Methods for Non-Convex Optimization](https://mlsanity.com/paper/1611.00756/) (2016)

## Built on by (most cited first, 5 of 5)

- [Large-Scale Differentiable Causal Discovery of Factor Graphs](https://mlsanity.com/paper/2206.07824/) (2022)
- [LOCAL: Learning with Orientation Matrix to Infer Causal Structure from Time Series Data](https://mlsanity.com/paper/2410.19464/) (2024)
- [Learning Large Causal Structures from Inverse Covariance Matrix via Sparse Matrix Decomposition](https://mlsanity.com/paper/2211.14221/) (2022)
- [Unsupervised Causal Abstractions Discovery](https://mlsanity.com/paper/2606.19594/) (2026)
- [Causality-Induced Positional Encoding for Transformer-Based Representation Learning of Non-Sequential Features](https://mlsanity.com/paper/2509.16629/) (2025)

## Abstract (arXiv)

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 tr(exp(·)), opens up a way to learning DAGs via continuous optimization, though with a O(d3) 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.