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.
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.
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