DAGOR: Learning DAGs via Topological Sorts and QR Factorization

Hao Zuo, Jinshen Jiang and Yun Zhou ()
Additional contact information
Hao Zuo: National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China
Jinshen Jiang: National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China
Yun Zhou: National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China

Mathematics, 2024, vol. 12, issue 8, 1-16

Abstract: Recently, the task of acquiring causal directed acyclic graphs (DAGs) from empirical data has been modeled as an iterative process within the framework of continuous optimization with a differentiable acyclicity characterization. However, learning DAGs from data is an NP-hard problem since the DAG space increases super-exponentially with the number of variables. In this work, we introduce the graph topological sorts in solving the continuous optimization problem, which is substantially smaller than the DAG space and beneficial in avoiding local optima. Moreover, the topological sorts space does not require consideration of acyclicity, which can significantly reduce the computational cost. To further deal with the inherent asymmetries of DAGs, we investigate the acyclicity characterization and propose a new DAGs learning optimization strategy based on QR factorization, named DAGOR. First, using the matrix congruent transformation, the adjacency matrix of the DAG is transformed into an upper triangular matrix with a topological sort. Next, using the QR factorization as a basis, we construct a least-square penalty function as constraints for optimization in the graph autoencoder framework. Numerical experiments are performed to further validate our theoretical results and demonstrate the competitive performance of our method.

Keywords: causal structural learning; directed acyclic graph; topological sorts; QR factorization; graph autoencoder (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/8/1198/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/8/1198/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:8:p:1198-:d:1377163

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().