QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917823537741824 |
|---|---|
| author | Shahverdikondori, Mohammad Mokhtarian, Ehsan Kiyavash, Negar |
| author_facet | Shahverdikondori, Mohammad Mokhtarian, Ehsan Kiyavash, Negar |
| contents | Causal discovery is essential for understanding relationships among variables of interest in many scientific domains. In this paper, we focus on permutation-based methods for learning causal graphs in Linear Gaussian Acyclic Models (LiGAMs), where the permutation encodes a causal ordering of the variables. Existing methods in this setting are not scalable due to their high computational complexity. These methods are comprised of two main components: (i) constructing a specific DAG, $\mathcal{G}^π$, for a given permutation $π$, which represents the best structure that can be learned from the available data while adhering to $π$, and (ii) searching over the space of permutations (i.e., causal orders) to minimize the number of edges in $\mathcal{G}^π$. We introduce QWO, a novel approach that significantly enhances the efficiency of computing $\mathcal{G}^π$ for a given permutation $π$. QWO has a speed-up of $O(n^2)$ ($n$ is the number of variables) compared to the state-of-the-art BIC-based method, making it highly scalable. We show that our method is theoretically sound and can be integrated into existing search strategies such as GRASP and hill-climbing-based methods to improve their performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23155 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs Shahverdikondori, Mohammad Mokhtarian, Ehsan Kiyavash, Negar Machine Learning Methodology Causal discovery is essential for understanding relationships among variables of interest in many scientific domains. In this paper, we focus on permutation-based methods for learning causal graphs in Linear Gaussian Acyclic Models (LiGAMs), where the permutation encodes a causal ordering of the variables. Existing methods in this setting are not scalable due to their high computational complexity. These methods are comprised of two main components: (i) constructing a specific DAG, $\mathcal{G}^π$, for a given permutation $π$, which represents the best structure that can be learned from the available data while adhering to $π$, and (ii) searching over the space of permutations (i.e., causal orders) to minimize the number of edges in $\mathcal{G}^π$. We introduce QWO, a novel approach that significantly enhances the efficiency of computing $\mathcal{G}^π$ for a given permutation $π$. QWO has a speed-up of $O(n^2)$ ($n$ is the number of variables) compared to the state-of-the-art BIC-based method, making it highly scalable. We show that our method is theoretically sound and can be integrated into existing search strategies such as GRASP and hill-climbing-based methods to improve their performance. |
| title | QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs |
| topic | Machine Learning Methodology |
| url | https://arxiv.org/abs/2410.23155 |