Timezone: »

 
Poster
Reliable Causal Discovery with Improved Exact Search and Weaker Assumptions
Ignavier Ng · Yujia Zheng · Jiji Zhang · Kun Zhang

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
in Poster Session 1 »

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 super-structure. Numerical experiments validate the efficacy of the proposed procedure, and demonstrate that it scales up to hundreds of nodes with a high accuracy.

Keywords: Generative Model · Graph Learning · Causality

Author Information

Ignavier Ng (Carnegie Mellon University)
Yujia Zheng (Carnegie Mellon University)
Jiji Zhang (Lingnan University)
Kun Zhang (CMU)

More from the Same Authors