Reliable Causal Discovery with Improved Exact Search and Weaker Assumptions

Ignavier Ng, Yujia Zheng, Jiji Zhang, Kun Zhang

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

Abstract

Many of the causal discovery methods rely on the faithfulness assumption to guarantee asymptotic correctness. However, the assumption can be approximately violated in many ways, leading to sub-optimal solutions. Although there is a line of research in Bayesian network structure learning that focuses on weakening the assumption, such as exact search methods with well-defined score functions, they do not scale well to large graphs. In this work, we introduce several strategies to improve the scalability of exact score-based methods in the linear Gaussian setting. In particular, we develop a super-structure estimation method based on the support of inverse covariance matrix which requires assumptions that are strictly weaker than faithfulness, and apply it to restrict the search space of exact search. We also propose a local search strategy that performs exact search on the local clusters formed by each variable and its neighbors within two hops in the superstructure. Numerical experiments validate the efficacy of the proposed procedure, and demonstrate that it scales up to hundreds of nodes with a high accuracy.

Original languageEnglish
Title of host publication35th Conference on Neural Information Processing Systems (NeurIPS 2021)
EditorsMarc'Aurelio Ranzato, Alina Beygelzimer, Yann Dauphin, Percy S. Liang, Jenn Wortman Vaughan
PublisherNeural Information Processing Systems Foundation
Pages20308-20320
Number of pages13
Volume24
ISBN (Electronic)9781713845393
Publication statusPublished - 6 Dec 2021
Event35th Conference on Neural Information Processing Systems, NeurIPS 2021 - Virtual, Online
Duration: 6 Dec 202114 Dec 2021

Publication series

NameAdvances in Neural Information Processing Systems
Volume34
ISSN (Print)1049-5258
NameNeurIPS Proceedings

Conference

Conference35th Conference on Neural Information Processing Systems, NeurIPS 2021
CityVirtual, Online
Period6/12/2114/12/21

Scopus Subject Areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint

Dive into the research topics of 'Reliable Causal Discovery with Improved Exact Search and Weaker Assumptions'. Together they form a unique fingerprint.

Cite this