# Greedy Relaxations of the Sparsest Permutation Algorithm

arXiv: https://arxiv.org/abs/2206.05421 · HTML: https://mlsanity.com/paper/2206.05421/

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 43 references that are in the map.
- First posted on arXiv 11 Jun 2022.

## Builds on (most cited first, 3 of 3)

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Causal Networks: Semantics and Expressiveness](https://mlsanity.com/paper/1304.2379/) (2013)
- [A Transformational Characterization of Equivalent Bayesian Network Structures](https://mlsanity.com/paper/1302.4938/) (2013)

## Built on by (most cited first, 30 of 64)

- [Causal-learn: Causal Discovery in Python](https://mlsanity.com/paper/2307.16405/) (2023)
- [Diffusion Models for Causal Discovery via Topological Ordering](https://mlsanity.com/paper/2210.06201/) (2022)
- [Fast Scalable and Accurate Discovery of DAGs Using the Best Order Score Search and Grow-Shrink Trees](https://mlsanity.com/paper/2310.17679/) (2023)
- [Bayesian learning of Causal Structure and Mechanisms with GFlowNets and Variational Bayes](https://mlsanity.com/paper/2211.02763/) (2022)
- [Causal Concept Graph Models: Beyond Causal Opacity in Deep Learning](https://mlsanity.com/paper/2405.16507/) (2024)
- [Self-Compatibility: Evaluating Causal Discovery without Ground Truth](https://mlsanity.com/paper/2307.09552/) (2023)
- [Sample, estimate, aggregate: A recipe for causal discovery foundation models](https://mlsanity.com/paper/2402.01929/) (2024)
- [Causal Discovery with Fewer Conditional Independence Tests](https://mlsanity.com/paper/2406.01823/) (2024)
- [Recursive Causal Discovery](https://mlsanity.com/paper/2403.09300/) (2024)
- [Cloud Atlas: Efficient Fault Localization for Cloud Systems using Language Models and Causal Insight](https://mlsanity.com/paper/2407.08694/) (2024)
- [Py-Tetrad and RPy-Tetrad: A New Python Interface with R Support for Tetrad Causal Search](https://mlsanity.com/paper/2308.07346/) (2023)
- [CausalDynamics: A large-scale benchmark for structural discovery of dynamical causal models](https://mlsanity.com/paper/2505.16620/) (2025)
- [CDANs: Temporal Causal Discovery from Autocorrelated and Non-Stationary Time Series Data](https://mlsanity.com/paper/2302.03246/) (2023)
- [Effective Bayesian Causal Inference via Structural Marginalisation and Autoregressive Orders](https://mlsanity.com/paper/2402.14781/) (2024)
- [Better Simulations for Validating Causal Discovery with the DAG-Adaptation of the Onion Method](https://mlsanity.com/paper/2405.13100/) (2024)
- [Order-based Structure Learning with Normalizing Flows](https://mlsanity.com/paper/2308.07480/) (2023)
- [Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models](https://mlsanity.com/paper/2405.14496/) (2024)
- [Are you doing better than random guessing? A call for using negative controls when evaluating causal discovery algorithms](https://mlsanity.com/paper/2412.10039/) (2024)
- [Causal Representation Learning from General Environments under Nonparametric Mixing](https://mlsanity.com/paper/2604.23800/) (2026)
- [Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning](https://mlsanity.com/paper/2510.04970/) (2025)
- [Bivariate Causal Discovery for Categorical Data via Classification with Optimal Label Permutation](https://mlsanity.com/paper/2209.08579/) (2022)
- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [On Different Notions of Redundancy in Conditional-Independence-Based Discovery of Graphical Models](https://mlsanity.com/paper/2502.08531/) (2025)
- [Causal Discovery and Counterfactual Reasoning to Optimize Persuasive Dialogue Policies](https://mlsanity.com/paper/2503.16544/) (2025)
- [Causal Structure and Representation Learning with Biomedical Applications](https://mlsanity.com/paper/2511.04790/) (2025)
- [Exactly Computing do-Shapley Values](https://mlsanity.com/paper/2602.07203/) (2026)
- [FoundCause: Causal Discovery with Latent Confounders from Observational Data](https://mlsanity.com/paper/2606.17516/) (2026)
- [Greedy equivalence search for nonparametric graphical models](https://mlsanity.com/paper/2406.17228/) (2024)
- [Generative Framework for Personalized Persuasion: Inferring Causal, Counterfactual, and Latent Knowledge](https://mlsanity.com/paper/2504.13904/) (2025)
- [Efficient Latent Variable Causal Discovery: Combining Score Search and Targeted Testing](https://mlsanity.com/paper/2510.04263/) (2025)

## Abstract (arXiv)

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.