ServiceNow Research

DAG Learning via Sparse Relaxations


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.

International Conference of Learning Representations (ICLR)
Valentina Zantedeschi
Valentina Zantedeschi
Research Scientist

Research Scientist at Human Decision Support located at London, UK.