Efficient Permutation Discovery in Causal DAGs
  The problem of learning a directed acyclic graph (DAG) up to Markov
equivalence is equivalent to the problem of finding a permutation of the
variables that induces the sparsest graph. Without additional assumptions, this
task is known to be NP-hard. Building on the minimum degree algorithm for
sparse Cholesky decomposition, but utilizing DAG-specific problem structure, we
introduce an efficient algorithm for finding such sparse permutations. We show
that on jointly Gaussian distributions, our method with depth $w$ runs in
$O(p^{w+3})$ time. We compare our method with $w = 1$ to algorithms for finding
sparse elimination orderings of undirected graphs, and show that taking
advantage of DAG-specific problem structure leads to a significant improvement
in the discovered permutation. We also compare our algorithm to provably
consistent causal structure learning algorithms, such as the PC algorithm, GES,
and GSP, and show that our method achieves comparable performance with a
shorter runtime. Thus, our method can be used on its own for causal structure
discovery. Finally, we show that there exist dense graphs on which our method
achieves almost perfect performance, so that unlike most existing causal
structure learning algorithms, the situations in which our algorithm achieves
both good performance and good runtime are not limited to sparse graphs.
