# DAG Learning on the Permutahedron

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 68 references that are in the map.
- First posted on arXiv 27 Jan 2023.

## Builds on (most cited first, 30 of 36)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [DAG-GNN: DAG Structure Learning with Graph Neural Networks](https://mlsanity.com/paper/1904.10098/) (2019)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Gradient-Based Neural DAG Learning](https://mlsanity.com/paper/1906.02226/) (2019)
- [Differentiable Causal Discovery from Interventional Data](https://mlsanity.com/paper/2007.01754/) (2020)
- [Learning Sparse Nonparametric DAGs](https://mlsanity.com/paper/1909.13189/) (2019)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [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)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization](https://mlsanity.com/paper/2209.08037/) (2022)
- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [Causal Machine Learning: A Survey and Open Problems](https://mlsanity.com/paper/2206.15475/) (2022)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [A survey of Bayesian Network structure learning](https://mlsanity.com/paper/2109.11415/) (2021)
- [Efficient Neural Causal Discovery without Acyclicity Constraints](https://mlsanity.com/paper/2107.10483/) (2021)
- [Permutation-Based Causal Structure Learning with Unknown Intervention Targets](https://mlsanity.com/paper/1910.09007/) (2019)
- [BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery](https://mlsanity.com/paper/2112.02761/) (2021)
- [Gradient Estimation with Stochastic Softmax Tricks](https://mlsanity.com/paper/2006.08063/) (2020)
- [SoftSort: A Continuous Relaxation for the argsort Operator](https://mlsanity.com/paper/2006.16038/) (2020)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [Learning Gaussian Networks](https://mlsanity.com/paper/1302.6808/) (2013)
- [SparseMAP: Differentiable Sparse Structured Inference](https://mlsanity.com/paper/1802.04223/) (2018)
- [Causal Discovery Toolbox: Uncover causal relationships in Python](https://mlsanity.com/paper/1903.02278/) (2019)
- [Differentiable DAG Sampling](https://mlsanity.com/paper/2203.08509/) (2022)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)

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

- [BayesDAG: Gradient-Based Posterior Inference for Causal Discovery](https://mlsanity.com/paper/2307.13917/) (2023)
- [CoLiDE: Concomitant Linear DAG Estimation](https://mlsanity.com/paper/2310.02895/) (2023)
- [Ordering-Based Causal Discovery for Linear and Nonlinear Relations](https://mlsanity.com/paper/2410.05890/) (2024)
- [Constraint-Free Structure Learning with Smooth Acyclic Orientations](https://mlsanity.com/paper/2309.08406/) (2023)
- [Learning DAGs from Data with Few Root Causes](https://mlsanity.com/paper/2305.15936/) (2023)
- [Order-based Structure Learning with Normalizing Flows](https://mlsanity.com/paper/2308.07480/) (2023)
- [Tree Search in DAG Space with Model-based Reinforcement Learning for Causal Discovery](https://mlsanity.com/paper/2310.13576/) (2023)
- [Concomitant DAG Learning: On the Roles of Noise Adaptivity, Sparsity, and Non-negativity](https://mlsanity.com/paper/2605.23537/) (2026)
- [Causal Order Discovery based on Monotonic SCMs](https://mlsanity.com/paper/2410.19870/) (2024)

## Abstract (arXiv)

We propose a continuous optimization framework for discovering a latent directed acyclic graph (DAG) from observational data. Our approach optimizes over the polytope of permutation vectors, the so-called Permutahedron, to learn a topological ordering. Edges can be optimized jointly, or learned conditional on the ordering via a non-differentiable subroutine. Compared to existing continuous optimization approaches our formulation has a number of advantages including: 1. validity: optimizes over exact DAGs as opposed to other relaxations optimizing approximate DAGs; 2. modularity: accommodates any edge-optimization procedure, edge structural parameterization, and optimization loss; 3. end-to-end: either alternately iterates between node-ordering and edge-optimization, or optimizes them jointly. We demonstrate, on real-world data problems in protein-signaling and transcriptional network discovery, that our approach lies on the Pareto frontier of two key metrics, the SID and SHD.