Verification and search algorithms for causal DAGs

Davin Choo, Kirankumar Shiragur, Arnab Bhattacharyya

TL;DR

This paper tackles the fundamental problems of verifying a proposed causal graph and searching for the true causal graph using interventions. The authors introduce the concept of "covered edges" to provide elegant characterizations and efficient algorithms for both problems, significantly advancing the state-of-the-art in causal discovery with minimal interventions.

What Problem Does This Paper Address?

In causal inference, a major goal is to understand the causal relationships between variables. This is often represented by a Directed Acyclic Graph (DAG). However, observational data alone is insufficient to fully determine the causal structure; we need to perform interventions (actively manipulating variables). This paper focuses on two key problems in this context:

  1. Verification: Given a proposed causal graph (from an expert or a previous analysis) and observational data (which defines a Markov Equivalence Class of possible DAGs), how can we efficiently check if the proposed graph is indeed the true underlying DAG? This requires finding the minimum number of interventions to confirm or refute the proposed structure.
  2. Search: How can we discover the true causal DAG from observational data and a minimal set of interventions? This is the core problem of causal discovery.

The challenge in both problems is to minimize the number or cost of interventions, as real-world experiments can be expensive and time-consuming. The paper aims to provide efficient algorithms for these tasks, especially for general graphs, and to establish theoretical guarantees on their performance.

Methods

The paper's core innovation lies in the introduction and utilization of "covered edges." An edge $u \sim v$ is defined as a covered edge if the set of parents of $u$ (excluding $v$) is the same as the set of parents of $v$ (excluding $u$). This concept proves crucial for:

  • Verification: The authors show that an intervention set is a verifying set (i.e., it can fully orient the essential graph) if and only if it "separates" every unoriented covered edge. This provides a clean characterization and leads to efficient algorithms for finding minimal atomic verifying sets (by computing minimum vertex covers of unoriented covered edges) and near-optimal bounded-size verifying sets. They also extend these results to handle varying intervention costs.
  • Search: For the search problem, the authors propose an adaptive algorithm based on graph separators. Graph separators are well-studied tools in graph theory that divide a graph into smaller components. Their algorithm iteratively uses clique separators to orient edges, achieving an approximation factor of $O(\log n)$ for atomic interventions and $O(\log n \cdot \log k)$ for bounded-size interventions (of size at most $k$), relative to the optimal verification size. This is a significant improvement, especially for general graphs.

Datasets

Not discussed in the paper. The experiments are conducted on synthetic graphs (cliques, trees, and general graphs of varying sizes) and potentially on known benchmark graphs from prior work.

Key Insights and Ideas

  • Covered Edges as the Key: The concept of "covered edges" is the central unifying idea. It provides a powerful lens through which to understand the structure of causal graphs and the requirements for intervention-based learning.
  • Verification Simplified: The equivalence between verifying sets and separating unoriented covered edges offers a much simpler and more elegant way to characterize and compute verifying sets compared to previous approaches.
  • Search and Verification are Closely Linked: The paper demonstrates that the search problem, in terms of the number of interventions required, is not significantly harder than the verification problem. The $O(\log n)$ approximation factor for search relative to the verification size highlights this.
  • Graph Separators for Efficient Search: Leveraging graph separators, a standard algorithmic tool, for causal graph search is a novel and effective approach, leading to provable approximation guarantees.
  • Tightness of Bounds: The paper establishes that the $O(\log n)$ approximation for atomic search is tight in the worst case, meaning no algorithm can do significantly better for general graphs.

Key Results

  • Efficient Verification Algorithms: The authors provide the first provably efficient algorithms for computing minimal sized atomic verifying sets and near-optimal bounded-size verifying sets on general graphs.
  • Characterization of Verifying Sets: A new characterization of verifying sets based on separating unoriented covered edges is presented.
  • Near-Optimal Bounded-Size Verification: For bounded size interventions (size $\le k$), their algorithm achieves a size of at most OPT + 1, where OPT is the optimal size, for general graphs.
  • Near-Optimal Search Algorithms:
    • For atomic interventions ($k=1$), the search algorithm uses $O(\log n \cdot v_1(G^*))$ interventions, where $v_1(G^*)$ is the minimum atomic verifying set size for the true DAG $G^*$.
  • For bounded-size interventions (size $\le k$), the algorithm uses $O(\log n \cdot \log k \cdot v_k(G^*))$ interventions.
  • Tightness for Search: The $O(\log n)$ approximation factor for atomic search is shown to be tight in the worst case.
  • Handling Intervention Costs: The framework is extended to handle additive intervention costs, providing efficient algorithms for minimizing a weighted combination of intervention cost and size.

Limitations and Future Work

  • Ideal Interventions: The work assumes "ideal interventions" (hard interventions with infinite samples), which may not always be feasible in practice. Soft interventions and sample complexity are acknowledged as important considerations for future work.
  • Assumptions: The study relies on standard causal inference assumptions: the Markov assumption, faithfulness, and causal sufficiency (no unobserved confounders). Relaxing these assumptions is a significant open challenge.
  • Societal Impact: While causal inference is crucial for understanding systems and designing interventions (e.g., in fair algorithms), the paper notes that violating its assumptions can lead to incorrect conclusions. Future work should focus on making these assumptions more robust.
  • Experimental Validation: While experiments are performed on synthetic graphs, a broader evaluation on real-world datasets would be valuable. The paper mentions their implementation is available for further research.

Summary updated

Abstract

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 $\Omega(\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.
BibTeX
@inproceedings{choo2022verification,
  author = {Davin Choo and Kirankumar Shiragur and Arnab Bhattacharyya},
  title = {{Verification and search algorithms for causal DAGs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=4F7vp67j79I},
}
Figure