{
  "id": "2102.03129",
  "version": "v1",
  "published": "2021-02-05T12:10:16.000Z",
  "updated": "2021-02-05T12:10:16.000Z",
  "title": "Integer Programming for Causal Structure Learning in the Presence of Latent Variables",
  "authors": [
    "Rui Chen",
    "Sanjeeb Dash",
    "Tian Gao"
  ],
  "categories": [
    "cs.LG",
    "math.OC"
  ],
  "abstract": "The problem of finding an ancestral acyclic directed mixed graph (ADMG) that represents the causal relationships between a set of variables is an important area of research for causal inference. However, most of existing score-based structure learning methods focus on learning the directed acyclic graph (DAG) without latent variables. A number of score-based methods have recently been proposed for the ADMG learning, yet they are heuristic in nature and do not guarantee an optimal solution. We propose a novel exact score-based method that solves an integer programming (IP) formulation and returns a score-maximizing ancestral ADMG for a set of continuous variables. In particular, we generalize the state-of-the-art IP model for DAG learning problems and derive new classes of valid inequalities to formalize the IP-based ADMG learning model. Empirically our model can be solved efficiently for medium-sized problems and achieves better accuracy than state-of-the-art score-based methods as well as benchmark constraint-based methods.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-02-05T12:10:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "latent variables",
      "causal structure learning",
      "integer programming",
      "structure learning methods focus",
      "acyclic directed mixed graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}