From Graphs to DAGs: A Low-Complexity Model and a Scalable Algorithm

Shuyu Dong, Michèle Sebag

Abstract

Learning Directed Acyclic Graphs (DAGs) is a fundamental task in causal inference, yet it is traditionally hampered by a cubic computational complexity $O(d^3)$ relative to the number of nodes $d$. We present LoRAM (Low-Rank Additive Model), a novel framework that utilizes low-rank matrix factorization and an efficient gradient approximation to reduce this complexity to $O(d^2r)$, where $r$ is the rank. Our approach enables scalable DAG estimation for thousands of nodes, achieving significant speedups while maintaining high structural accuracy.

Introduction

Directed Acyclic Graphs (DAGs) are indispensable tools for representing causal relationships in diverse fields such as genetics and social sciences. However, identifying the optimal DAG from data is an NP-hard combinatorial problem. A significant breakthrough occurred with the "NoTears" algorithm, which reformulated the discrete acyclicity constraint into a smooth, differentiable function: $tr(\exp(A \odot A)) = d$. While this allowed for continuous optimization, the computational cost of evaluating the matrix exponential and its gradient scales as $O(d^3)$. This cubic scaling creates a bottleneck for high-dimensional datasets, limiting the applicability of NoTears to systems with a few hundred variables.

Methodology

To overcome the $O(d^3)$ limitation, we propose the Low-Rank Additive Model (LoRAM). The method is built upon three core innovations:

  1. Low-Rank Factorization: Instead of optimizing the full $d \times d$ adjacency matrix, LoRAM represents the graph structure using two low-rank matrices $X, Y \in \mathbb{R}^{d \times r}$, where $r \ll d$. This reduces the parameter space from $d^2$ to $2dr$.
  2. Sparsification Masking: To maintain the ability to represent sparse causal networks, a mask $\Omega$ is applied to the low-rank product, focusing optimization on a candidate set of edges.
  3. Inexact Gradient Approximation: The primary bottleneck in NoTears is the $O(d^3)$ cost of computing the gradient of the matrix exponential. LoRAM introduces an incremental multiplication method based on Taylor expansions. This allows for computing the gradient's action on the low-rank factors in $O(d^2r)$ time.
Comparison of search space, memory requirements, and gradient computation cost across different DAG learning methods.

The optimization is performed using Nesterov’s Accelerated Gradient Descent (AGD) with Barzilai-Borwein stepsize adaptation, ensuring rapid convergence without the need for expensive line searches.

Experimental Evaluation

We evaluated LoRAM against synthetic benchmarks, focusing on scalability and robustness. The experiments utilized Erdős-Rényi (ER) graphs as ground truth and tested robustness against two primary noise models: Bernoulli-Gaussian noise (spurious edges) and cause-effect confusions (reversed edges creating cycles). Scalability tests spanned from 100 to 5,000 nodes.

Results and Discussion

LoRAM demonstrates a significant reduction in computational overhead without sacrificing accuracy. On a 2,000-node graph, LoRAM-AGD achieved convergence in approximately 20 seconds, compared to over 900 seconds for the standard NoTears approach—a 45x speedup. In terms of structural fidelity, LoRAM's performance in "cause-effect confusion" scenarios was nearly identical to NoTears, as measured by Structural Hamming Distance (SHD) and True Positive Rate (TPR).

A key insight is that an exact gradient is not strictly necessary for high-quality DAG recovery. The approximate gradient used in LoRAM maintains high cosine similarity with the true gradient, ensuring stable optimization trajectories. Furthermore, the low-rank assumption is naturally suited to real-world causal graphs that often feature "hub" nodes.

Conclusion

LoRAM successfully decouples the complexity of DAG learning from the cubic growth of the number of nodes. By achieving $O(d^2r)$ complexity, it enables the analysis of large-scale causal systems that were previously computationally inaccessible. Future work will focus on extending this low-rank framework to non-linear causal models and integrating it with auto-encoder architectures for high-dimensional representation learning.

Summary updated

BibTeX
@inproceedings{dong2022from,
  author = {Shuyu Dong and Michèle Sebag},
  title = {{From Graphs to DAGs: A Low-Complexity Model and a Scalable Algorithm}},
  booktitle = {ECML/PKDD},
  year = {2022},
  doi = {10.1007/978-3-031-26419-1\_7},
}
Figure