Experimental Design for Cost-Aware Learning of Causal Graphs

Causal Inference


  • Erik M. Lindgren
  • Murat Kocaoglu
  • Alexandros G. Dimakis
  • Sriram Vishwanath

Published on


We consider the minimum cost intervention design problem: Given the essential graph of a causal graph and a cost to intervene on a variable, identify the set of interventions with minimum total cost that can learn any causal graph with the given essential graph. We first show that this problem is NP-hard. We then prove that we can achieve a constant factor approximation to this problem with a greedy algorithm. We then constrain the sparsity of each intervention. We develop an algorithm that returns an intervention design that is nearly optimal in terms of size for sparse graphs with sparse interventions and we discuss how to use it when there are costs on the vertices.

Please cite our work using the BibTeX below.

  author    = {Erik M. Lindgren and
               Murat Kocaoglu and
               Alexandros G. Dimakis and
               Sriram Vishwanath},
  title     = {Experimental Design for Cost-Aware Learning of Causal Graphs},
  journal   = {CoRR},
  volume    = {abs/1810.11867},
  year      = {2018},
  url       = {},
  archivePrefix = {arXiv},
  eprint    = {1810.11867},
  timestamp = {Wed, 31 Oct 2018 14:24:29 +0100},
  biburl    = {},
  bibsource = {dblp computer science bibliography,}

Close Modal