Revisiting Causal Discovery from a Complexity-Theoretic Perspective

Robert Ganian, Viktoriia Korchemna, Stefan Szeider

Abstract: Causal discovery seeks to unveil causal relationships (represented as a so-called causal graph) from observational data. This paper investigates the complex relationship between the graph structure and the efficiency of constraint-based causal discovery algorithms. Our main contributions include (i) a near-tight characterization of which causal graphs admit a small d-separating set for each pair of vertices and thus can potentially be efficiently recovered by a constraint-based causal discovery algorithm, (ii) the explicit construction of a sequence of causal graphs on which the influential PC algorithm might need exponential time, although there is a small d-separating set between every pair of variables, and (iii) the formulation of a new causal discovery algorithm which achieves fixed-parameter running time by considering the maximum number of edge-disjoint paths between variables in the (undirected) super-structure as the parameter. A distinguishing feature of our investigation is that it is carried out within a more fine-grained model which more faithfully captures the infeasibility of performing accurate independence tests for large sets of conditioning variables.

Introduction

Constraint-based causal discovery, exemplified by the industry-standard PC algorithm, relies on conditional independence tests to reconstruct the hidden directed acyclic graph (DAG) of cause-and-effect relationships. While these algorithms are widely used, their efficiency is often taken for granted in sparse graphs. This paper provides a rigorous complexity-theoretic audit, demonstrating that the PC algorithm can be exponentially slow even on seemingly simple structures and proposing a more robust alternative: $PC_{cut}$.

The Problem: The Cost of Independence

In practice, testing conditional independence ($X \perp Y | Z$) becomes exponentially more difficult and statistically unreliable as the size of the conditioning set $Z$ increases. This paper adopts a fine-grained oracle model, where the computational cost of a test grows with the size of $Z$. The central question is: which graph structures allow us to find the causal skeleton using only small conditioning sets?

The Failure of the PC Algorithm

A key insight of this research is that the PC algorithm is "myopic." It builds the size of the conditioning set $Z$ greedily, starting from empty sets and increasing the size step-by-step. The authors prove that this strategy can fail catastrophically.

An adversarial graph construction demonstrating the exponential failure of the PC algorithm.

As shown in Figure 1, the authors construct adversarial graph families where a d-separating set of size 3 exists, yet the PC algorithm is forced to check sets of size $2^n$. Theorem 11 formalizes this, showing that for any $n$, there exists a graph where the PC algorithm must test a set of size $2^n + 2$, rendering it unusable for large-scale discovery in these cases.

Methods and Structural Characterization

To address these limitations, the paper utilizes Parameterized Complexity, seeking algorithms that are Fixed-Parameter Tractable (FPT). The authors link d-separation properties to undirected edge-cuts in the graph's skeleton. They use mathematical "fractal" graph constructions, such as the $D_i$ family, to establish these complexity bounds.

The fractal graph construction $D_2$, used to establish lower bounds for causal discovery algorithms.

By analyzing these structures (e.g., Figure 3), the authors prove that the number of edge-disjoint paths in the undirected skeleton is a superior predictor of d-separation than traditional measures like treewidth. Specifically, if $X$ and $Y$ can be separated by $k$ edges, they can be d-separated by a set of size at most $2k^2$.

The $PC_{cut}$ Algorithm

The proposed $PC_{cut}$ algorithm avoids the myopic pitfalls of the standard PC algorithm. Instead of searching through local neighborhoods, it identifies a minimum edge-cut in a provided "super-structure" (a graph containing all possible edges). It then restricts its independence tests to variables incident to that cut.

Theorem 16 proves that $PC_{cut}$ runs in time $2^{2k^2} B^{2k^2} O(nk)$, where $k$ is the maximum edge-cut size and $B$ is the domain size. This ensures efficiency for a much broader class of graphs, including those with high-degree "hubs" that typically cause standard algorithms to fail.

Key Results and Implications

  • Near-Tight Characterization: A bounded number of undirected edge-disjoint paths is sufficient to guarantee the existence of a small d-separating set.
  • Exponential Speedup: $PC_{cut}$ can be exponentially faster than both the standard PC and the improved PC* algorithms on specific graph classes.
  • Fixed-Parameter Tractability: Causal discovery is shown to be efficient when parameterized by the maximum edge-cut size of the super-structure.

Conclusion and Future Work

This work shifts the focus of causal discovery from local sparsity to global connectivity. While $PC_{cut}$ offers significant theoretical advantages, its practical performance depends on the availability of a reasonably sparse super-structure. Future research will focus on empirical validation with noisy real-world data and exploring whether every orientation of a skeleton with many edge-disjoint paths necessarily implies a large d-separating set.

Summary updated

Abstract

Causal discovery seeks to unveil causal relationships (represented as a so-called causal graph) from observational data. This paper investigates the complex relationship between the graph structure and the efficiency of constraint-based causal discovery algorithms. Our main contributions include (i) a near-tight characterization of which causal graphs admit a small d-separating set for each pair of vertices and thus can potentially be efficiently recovered by a constraint-based causal discovery algorithm, (ii) the explicit construction of a sequence of causal graphs on which the influential PC algorithm might need exponential time, although there is a small d-separating set between every pair of variables, and (iii) the formulation of a new causal discovery algorithm which achieves fixed-parameter running time by considering the maximum number of edge-disjoint paths between variables in the (undirected) super-structure as the parameter. A distinguishing feature of our investigation is that it is carried out within a more fine-grained model which more faithfully captures the infeasibility of performing accurate independence tests for large sets of conditioning variables.
BibTeX
@inproceedings{ganian2024revisiting,
  author = {Robert Ganian and Viktoriia Korchemna and Stefan Szeider},
  title = {{Revisiting Causal Discovery from a Complexity-Theoretic Perspective}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=5D9zIvx5Ay},
}
Figure