Cost-Optimal Learning of Causal Graphs
This work addresses the challenge of efficiently learning causal structures with interventions, which is incremental as it builds on existing causal graph learning methods by optimizing costs and handling constraints.
The paper tackles the problem of learning causal graphs with interventions by designing cost-optimal sets of interventions to uniquely identify graphs given a skeleton, showing it is solvable in polynomial time, and provides algorithms for limited interventions with specific skeleton types like trees or chordal graphs.
We consider the problem of learning a causal graph over a set of variables with interventions. We study the cost-optimal causal graph learning problem: For a given skeleton (undirected version of the causal graph), design the set of interventions with minimum total cost, that can uniquely identify any causal graph with the given skeleton. We show that this problem is solvable in polynomial time. Later, we consider the case when the number of interventions is limited. For this case, we provide polynomial time algorithms when the skeleton is a tree or a clique tree. For a general chordal skeleton, we develop an efficient greedy algorithm, which can be improved when the causal graph skeleton is an interval graph.