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.

通过研究自适应干预下的因果图发现，提出了一种新的基准，捕捉任何搜索算法的最坏干预成本，并提出了在各种设置下实现对数逼近的自适应搜索算法。