@inproceedings{RantanenHJ:PGM2018,
title = {Learning Optimal Causal Graphs with Exact Search},
author = {Kari Rantanen and Antti Hyttinen and Matti J\"arvisalo},
editor = {Vaclav Kratochvil and Milan Studeny},
booktitle = {Proceedings of the 9th International Conference on
             Probabilistic Graphical Models (PGM 2018)},
volume = {72},
series = {Proceedings of Machine Learning Research},
pages = {344--355},
publisher = {JLMR.org},
year = {2018},
}

Abstract:

Discovering graphical models over very general model spaces with high accuracy
requires optimally combining conflicting (in)dependence constraints in sample data,
and thus results in a computationally hard combinatorial optimization problem.
Recent advances in exact algorithmic approaches in this  constraint-based setting
build upon off-the-shelf declarative optimization solvers. In this paper, we propose
the first truly specialized exact search algorithm for optimal causal graphs in a
general model space, allowing both cycles and latent confounding variables. Our
problem-oriented approach enables directly incorporating domain knowledge for
developing a wider range of specialized search techniques for the problem, including
problem-specific propagators, branching heuristics, and bounding techniques, as well
as directly incorporating different constraints on the model space, such as sparsity
and acyclicity constraints. We empirically evaluate a first implementation of the
approach, showing that it clearly outperforms current state of art in exact
constraint-based causal discovery on real-world instances.