Greedy Relaxations of the Sparsest Permutation Algorithm

About

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.

Wai-Yin Lam, Bryan Andrews, Joseph Ramsey · 2022

Related benchmarks

Task	Dataset	Result
Causal Discovery	Alarm d=37	Mod. SHD19	21
Causal Discovery	Sachs flow cytometry observational	SHD27	19
Causal Discovery	Supermarket linear synthetic	Dtop4.21	17
Causal Discovery	Cancer linear synthetic	Dtop0	17
Causal Discovery	Covid linear synthetic 3	Dtop1.17	17
Causal Discovery	Sachs linear synthetic	Dtop8.42	17
Causal Discovery	Covid linear synthetic 1	Dtop17	17
Causal Discovery	Climate linear synthetic	Dtop0.83	17
Causal Discovery	Covid linear synthetic 4	Dtop1	17
Causal Discovery	Genetic linear synthetic	Dtop0.25	17