  Recovering causal relationships from data is an important problem. Using
observational data, one can typically only recover causal graphs up to a Markov
equivalence class and additional assumptions or interventional data are needed
for complete recovery. In this work, under some standard assumptions, we study
causal graph discovery via adaptive interventions with node-dependent
interventional costs. For this setting, we show that no algorithm can achieve
an approximation guarantee that is asymptotically better than linear in the
number of vertices with respect to the verification number; a well-established
benchmark for adaptive search algorithms. Motivated by this negative result, we
define a new benchmark that captures the worst-case interventional cost for any
search algorithm. Furthermore, with respect to this new benchmark, we provide
adaptive search algorithms that achieve logarithmic approximations under
various settings: atomic, bounded size interventions and generalized cost
objectives.
