On Low Rank Directed Acyclic Graphs and Causal Structure Learning
This work addresses a bottleneck in causal inference for non-sparse graphs, offering incremental improvements for researchers in machine learning and statistics.
The paper tackles the challenge of learning causal structures in high-dimensional settings by exploiting a low rank assumption on DAG adjacency matrices, showing that scale-free networks tend to be low rank and demonstrating improved performance in experiments with large, dense graphs.
Despite several advances in recent years, learning causal structures represented by directed acyclic graphs (DAGs) remains a challenging task in high dimensional settings when the graphs to be learned are not sparse. In this paper, we propose to exploit a low rank assumption regarding the (weighted) adjacency matrix of a DAG causal model to help address this problem. We utilize existing low rank techniques to adapt causal structure learning methods to take advantage of this assumption and establish several useful results relating interpretable graphical conditions to the low rank assumption. Specifically, we show that the maximum rank is highly related to hubs, suggesting that scale-free networks, which are frequently encountered in practice, tend to be low rank. Our experiments demonstrate the utility of the low rank adaptations for a variety of data models, especially with relatively large and dense graphs. Moreover, with a validation procedure, the adaptations maintain a superior or comparable performance even when graphs are not restricted to be low rank.