DAG Learning on the Permutahedron
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.
Code (1)
Similar Papers 제목 키워드 기반
Signal Processing on the Permutahedron: Tight Spectral Frames for Ranked Data Analysis
Ranked data sets, where m judges/voters specify a preference ranking of n objects/candidates, are increasingly prevalent in contexts such as political elections, computer vision, recommender systems, and bioinformatics. …
Recommendation SystemsBandit Online Optimization Over the Permutahedron
The permutahedron is the convex polytope with vertex set consisting of the vectors $(\pi(1),\dots, \pi(n))$ for all permutations (bijections) $\pi$ over $\{1,\dots, n\}$. We study a bandit game in which, at each step $t$…
Beyond the Birkhoff Polytope: Convex Relaxations for Vector Permutation Problems
The Birkhoff polytope (the convex hull of the set of permutation matrices), which is represented using $\Theta(n^2)$ variables and constraints, is frequently invoked in formulating relaxations of optimization problems ov…
Frames for Graph Signals on the Symmetric Group: A Representation Theoretic Approach
An important problem in the field of graph signal processing is developing appropriate overcomplete dictionaries for signals defined on different families of graphs. The Cayley graph of the symmetric group has natural ap…
Efficient Differentiable Discovery of Causal Order
In the algorithm Intersort, Chevalley et al. (2024) proposed a score-based method to discover the causal order of variables in a Directed Acyclic Graph (DAG) model, leveraging interventional data to outperform existing m…
Causal Discovery