Experimental Design for Cost-Aware Learning of Causal Graphs
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.
Summary: The authors study the problem of designing experiments for learning causal structure under the assumption that each variable has a cost to intervene on, and the objective is to minimize the total experiment cost. It is first shown that the problem is in general NP hard, and then a greedy algorithm is proposed which is proven to be an approximate algorithm. Furthermore, the case that in each intervention, a limited number of variables can be intervened on is considered. An approximate algorithm is proposed for this case as well. Finally, the proposed approach is evaluated on synthetic data. The work for most of the part, is written clearly and is easy to understand.  Comments: - In line 69, the vice versa part does not seem to be necessarily true.  - In line 102, when we force a variable to just take a certain value, it may not necessarily change the distribution of its children. Also, what does the authors mean by "new skeleton" in line 105?  - In Definition 2, the minimum cost intervention design problem is defined as finding a graph separating system of size at most m. What if there is no such separating system? I recommend changing it to minimum possible size, or m>m^*, where m^* is the minimum possible size.  - In Definition 4, it seems that in reality we always need to have |I_i|=k. If so, can we say that Definition 5 is a special case of Definition 6?  - How should we choose the cost values in practice? Do the authors recommend that these values should be defined manually by an expert? If so, this restricts the application of the proposed approach.  - A major concern as usual regarding this work and similar work is its practicality aspects. It is not clear if the proposed method can be applied in practice, where there are latent confounders, statistical errors, undefined cost values, etc.  - It seems that in reality the values of the costs may not follow a distribution similar to the design of experiments. I expect much larger costs following a heavy tailed distribution, or even more realistically, many variables should have cost equal to infinity, representing that intervention on those variables are not possible. Especially the latter situation is not considered in this work.  - The cost quantization step seems unjustifiable in practice and seems to be only useful for theoretical guarantees to work. Clearly, this step can possibly change the significance of costs and make the distribution of costs close to uniform.  - One important missing experiment in the last section is evaluating the approach on graphs with different sparsities.   - Also, it would have been more useful if the authors performed simulations with the initial observational test step, so that we can see the effect of that step on the total performance as well. This will include error in estimating the skeleton, not having chordal graph, etc.  - The proof of proposition 10 in the supplementary materials is not clear. Especially, it is not clear why S should be an independent set. This is important as Theorem 11 is also using this proposition.  - One question regarding the presentation of the work: the case of restricting the number of intervened variables in each intervention is the general case, and the whole section 5 could be considered as a special case of that. The same is true for definition. I was wondering if there was a special reason that the authors did not merge these results and definitions?