Greedy Relaxations of the Sparsest Permutation Algorithm
This work addresses the challenge of causal discovery for researchers and practitioners, offering incremental improvements in efficiency and consistency under weaker assumptions.
The paper tackles the problem of efficiently searching for directed acyclic causal models by extending the Sparsest Permutation algorithm with a new permutation-based operation called 'tuck', resulting in the GRaSP class of algorithms that outperform state-of-the-art methods in simulation, handling dense graphs and over 100 variables with high accuracy.
There has been an increasing interest in methods that exploit permutation reasoning to search for directed acyclic causal models, including the "Ordering Search" of Teyssier and Kohler and GSP of Solus, Wang and Uhler. We extend the methods of the latter by a permutation-based operation, tuck, and develop a class of algorithms, namely GRaSP, that are efficient and pointwise consistent under increasingly weaker assumptions than faithfulness. The most relaxed form of GRaSP outperforms many state-of-the-art causal search algorithms in simulation, allowing efficient and accurate search even for dense graphs and graphs with more than 100 variables.