IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i8p1198-d1377163.html
   My bibliography  Save this article

DAGOR: Learning DAGs via Topological Sorts and QR Factorization

Author

Listed:
  • Hao Zuo

    (National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China
    These authors contributed equally to this work.)

  • Jinshen Jiang

    (National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China
    These authors contributed equally to this work.)

  • Yun Zhou

    (National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China)

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.

Suggested Citation

  • Hao Zuo & Jinshen Jiang & Yun Zhou, 2024. "DAGOR: Learning DAGs via Topological Sorts and QR Factorization," Mathematics, MDPI, vol. 12(8), pages 1-16, April.
  • Handle: RePEc:gam:jmathe:v:12:y:2024:i:8:p:1198-:d:1377163
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/8/1198/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/12/8/1198/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. David M. Blei & Alp Kucukelbir & Jon D. McAuliffe, 2017. "Variational Inference: A Review for Statisticians," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 112(518), pages 859-877, April.
    2. Su, Zhi & Liu, Peng & Fang, Tong, 2022. "Uncertainty matters in US financial information spillovers: Evidence from a directed acyclic graph approach," The Quarterly Review of Economics and Finance, Elsevier, vol. 84(C), pages 229-242.
    3. Abramson, Bruce & Brown, John & Edwards, Ward & Murphy, Allan & Winkler, Robert L., 1996. "Hailfinder: A Bayesian system for forecasting severe weather," International Journal of Forecasting, Elsevier, vol. 12(1), pages 57-71, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Shen Liu & Hongyan Liu, 2021. "Tagging Items Automatically Based on Both Content Information and Browsing Behaviors," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 882-897, July.
    2. Loaiza-Maya, Rubén & Smith, Michael Stanley & Nott, David J. & Danaher, Peter J., 2022. "Fast and accurate variational inference for models with many latent variables," Journal of Econometrics, Elsevier, vol. 230(2), pages 339-362.
    3. Xing Qin & Shuangge Ma & Mengyun Wu, 2023. "Two‐level Bayesian interaction analysis for survival data incorporating pathway information," Biometrics, The International Biometric Society, vol. 79(3), pages 1761-1774, September.
    4. Youngseon Lee & Seongil Jo & Jaeyong Lee, 2022. "A variational inference for the Lévy adaptive regression with multiple kernels," Computational Statistics, Springer, vol. 37(5), pages 2493-2515, November.
    5. Liu, Jie & Ye, Zifeng & Chen, Kun & Zhang, Panpan, 2024. "Variational Bayesian inference for bipartite mixed-membership stochastic block model with applications to collaborative filtering," Computational Statistics & Data Analysis, Elsevier, vol. 189(C).
    6. Nathaniel Tomasetti & Catherine Forbes & Anastasios Panagiotelis, 2019. "Updating Variational Bayes: Fast Sequential Posterior Inference," Monash Econometrics and Business Statistics Working Papers 13/19, Monash University, Department of Econometrics and Business Statistics.
    7. Gael M. Martin & David T. Frazier & Christian P. Robert, 2020. "Computing Bayes: Bayesian Computation from 1763 to the 21st Century," Monash Econometrics and Business Statistics Working Papers 14/20, Monash University, Department of Econometrics and Business Statistics.
    8. Djohan Bonnet & Tifenn Hirtzlin & Atreya Majumdar & Thomas Dalgaty & Eduardo Esmanhotto & Valentina Meli & Niccolo Castellani & Simon Martin & Jean-François Nodin & Guillaume Bourgeois & Jean-Michel P, 2023. "Bringing uncertainty quantification to the extreme-edge with memristor-based Bayesian neural networks," Nature Communications, Nature, vol. 14(1), pages 1-13, December.
    9. Ho, Paul, 2023. "Global robust Bayesian analysis in large models," Journal of Econometrics, Elsevier, vol. 235(2), pages 608-642.
    10. Liang, Xinbin & Liu, Zhuoxuan & Wang, Jie & Jin, Xinqiao & Du, Zhimin, 2023. "Uncertainty quantification-based robust deep learning for building energy systems considering distribution shift problem," Applied Energy, Elsevier, vol. 337(C).
    11. Gael M. Martin & David T. Frazier & Ruben Loaiza-Maya & Florian Huber & Gary Koop & John Maheu & Didier Nibbering & Anastasios Panagiotelis, 2023. "Bayesian Forecasting in the 21st Century: A Modern Review," Monash Econometrics and Business Statistics Working Papers 1/23, Monash University, Department of Econometrics and Business Statistics.
    12. Seokhyun Chung & Raed Al Kontar & Zhenke Wu, 2022. "Weakly Supervised Multi-output Regression via Correlated Gaussian Processes," INFORMS Joural on Data Science, INFORMS, vol. 1(2), pages 115-137, October.
    13. Gary Koop & Dimitris Korobilis, 2023. "Bayesian Dynamic Variable Selection In High Dimensions," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 64(3), pages 1047-1074, August.
    14. Ziqi Zhang & Xinye Zhao & Mehak Bindra & Peng Qiu & Xiuwei Zhang, 2024. "scDisInFact: disentangled learning for integration and prediction of multi-batch multi-condition single-cell RNA-sequencing data," Nature Communications, Nature, vol. 15(1), pages 1-16, December.
    15. Dimitris Korobilis & Davide Pettenuzzo, 2020. "Machine Learning Econometrics: Bayesian algorithms and methods," Working Papers 2020_09, Business School - Economics, University of Glasgow.
    16. Thayer Alshaabi & David R Dewhurst & James P Bagrow & Peter S Dodds & Christopher M Danforth, 2021. "The sociospatial factors of death: Analyzing effects of geospatially-distributed variables in a Bayesian mortality model for Hong Kong," PLOS ONE, Public Library of Science, vol. 16(3), pages 1-20, March.
    17. Jan Prüser & Florian Huber, 2024. "Nonlinearities in macroeconomic tail risk through the lens of big data quantile regressions," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 39(2), pages 269-291, March.
    18. Bansal, Prateek & Krueger, Rico & Graham, Daniel J., 2021. "Fast Bayesian estimation of spatial count data models," Computational Statistics & Data Analysis, Elsevier, vol. 157(C).
    19. Rogelio A. Mancisidor & Kjersti Aas, 2022. "Multimodal Generative Models for Bankruptcy Prediction Using Textual Data," Papers 2211.08405, arXiv.org, revised Feb 2024.
    20. Shota Gugushvili & Frank van der Meulen & Moritz Schauer & Peter Spreij, 2018. "Nonparametric Bayesian volatility estimation," Papers 1801.09956, arXiv.org, revised Mar 2019.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:12:y:2024:i:8:p:1198-:d:1377163. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.