论文标题
验证和搜索因果关系的算法
Verification and search algorithms for causal DAGs
论文作者
论文摘要
我们研究了两个问题与从介入数据中恢复因果图有关的问题：（i）$ \ textit {verifififie} $，其中任务是检查声称的因果图是否正确，并且（ii）$ \ textit {search} $，在其中任务是恢复正确图形。对于这两者，我们都希望最大程度地减少执行的干预措施的数量。对于第一个问题，我们给出了一组最小尺寸的原子干预措施的表征，这些干预措施是必要且足以检查所要求的因果图的正确性。我们的表征使用$ \ textit {coving edges} $的概念，这使我们能够获得简单的证据，并且很容易就早期的已知结果推理。我们还将结果推广到有限尺寸干预措施和依赖节点的干预成本的设置。对于上述所有设置，我们提供了第一种已知的可证明算法，用于有效地计算（接近）在一般图上的最佳验证集。对于第二个问题，我们基于图形分离器给出了一种简单的自适应算法，该算法会产生一个原子干预集，该集合在使用$ \ MATHCAL {O}（\ log n）$ times $ times $ $ \ textit {vertitify} $（verifyify} $（验证）上$ n $ n $ n $ n $ vertices所需的最佳干预措施所需的最佳干预措施。相对于验证尺寸，此近似值是$ \ textit {any} $搜索算法的最差情况近似比为$ω（\ log n）$相对于验证大小。使用有限的大小干预措施，每个大小$ \ leq k $，我们的算法给出了$ \ MATHCAL {O}（\ log n \ cdot \ log k）$ factor actialation。我们的结果是第一种已知的算法，该算法对一般未加权图和有界尺寸干预的验证尺寸提供了非平凡的近似保证。
We study two problems related to recovering causal graphs from interventional data: (i) $\textit{verification}$, where the task is to check if a purported causal graph is correct, and (ii) $\textit{search}$, where the task is to recover the correct causal graph. For both, we wish to minimize the number of interventions performed. For the first problem, we give a characterization of a minimal sized set of atomic interventions that is necessary and sufficient to check the correctness of a claimed causal graph. Our characterization uses the notion of $\textit{covered edges}$, which enables us to obtain simple proofs and also easily reason about earlier known results. We also generalize our results to the settings of bounded size interventions and node-dependent interventional costs. For all the above settings, we provide the first known provable algorithms for efficiently computing (near)-optimal verifying sets on general graphs. For the second problem, we give a simple adaptive algorithm based on graph separators that produces an atomic intervention set which fully orients any essential graph while using $\mathcal{O}(\log n)$ times the optimal number of interventions needed to $\textit{verify}$ (verifying size) the underlying DAG on $n$ vertices. This approximation is tight as $\textit{any}$ search algorithm on an essential line graph has worst case approximation ratio of $Ω(\log n)$ with respect to the verifying size. With bounded size interventions, each of size $\leq k$, our algorithm gives an $\mathcal{O}(\log n \cdot \log k)$ factor approximation. Our result is the first known algorithm that gives a non-trivial approximation guarantee to the verifying size on general unweighted graphs and with bounded size interventions.
