New metrics and search algorithms for weighted causal DAGs
This work addresses causal discovery with cost constraints, offering theoretical guarantees for practitioners in fields like medicine or economics, though it appears incremental as it builds on existing adaptive search frameworks.
The paper tackles the problem of discovering causal graphs from observational data with node-dependent interventional costs, showing that no algorithm can achieve better than linear approximation with respect to the verification number benchmark. It introduces a new benchmark capturing worst-case interventional costs and provides adaptive search algorithms achieving logarithmic approximations under various settings.
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.