Reliable Causal Discovery with Improved Exact Search and Weaker
  Assumptions
  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.
