Extendability of causal graphical models: Algorithms and computational complexity

Marcel Wienöbst, Max Bannach, Maciej LiskiewiczUAI 2021 · OpenReview

Abstract

Finding a consistent DAG extension for a given partially directed acyclic graph (PDAG) is a basic building block used in graphical causal analysis. In 1992, Dor and Tarsi proposed an algorithm with $O(n^4)$ complexity. This paper settles the computational limits of this problem, providing a new $O(n^3)$ algorithm and proving its near-optimality under the Strong Triangle Conjecture.

The Consistent DAG Extension Problem

In causal discovery, researchers often represent uncertainty using Partially Directed Acyclic Graphs (PDAGs). These graphs contain both directed edges, representing known causal relationships, and undirected edges, representing potential but unconfirmed directions. A central challenge is the consistent DAG extension problem: orienting all undirected edges to form a Directed Acyclic Graph (DAG) without introducing new directed cycles or new "v-structures" (patterns like $x \rightarrow y \leftarrow z$ where $x$ and $z$ are non-adjacent).

Relationship between various classes of causal graphical models, including MPDAGs, DAGs, and CPDAGs.

Since 1992, the standard solution for this problem has been the Dor and Tarsi algorithm, which runs in $O(n^4)$ time. For decades, the community speculated whether a linear-time $O(n+m)$ algorithm—comparable to chordality testing—was possible. This research definitively answers that question by linking the problem to fundamental complexity classes.

Breaking the $O(n^4)$ Benchmark

The authors introduce a new algorithm that achieves $O(n^3)$ complexity. The approach utilizes a "potential-sink" elimination strategy supported by a specialized data structure. By tracking neighborhood properties (specifically edge patterns $\alpha$ and $\beta$), the algorithm identifies and removes potential sinks more efficiently than previous iterations.

Crucially, the paper establishes a lower bound for this problem. By reducing the TRIANGLE problem (detecting a 3-cycle in a graph) to the PDAG extension problem, the authors show that any algorithm significantly faster than $O(n^3)$ would represent a major breakthrough in fine-grained complexity. Under the Strong Triangle Conjecture (STC), the $O(n^3)$ complexity is likely the best achievable for combinatorial algorithms.

Efficient Algorithms for Subclasses

While the general problem faces a cubic barrier, specific subclasses of graphs allow for greater efficiency. The authors provide the first $O(n+m)$ linear-time algorithms for extending Maximally Oriented PDAGs (MPDAGs) and Chain Graphs (CGs).

Meek orientation rules R1 and R2, which are essential for maintaining consistency in PDAG extensions.

MPDAGs are particularly relevant as they are the standard output of common causal discovery algorithms like PC or GES. The paper demonstrates that once a graph is maximally oriented using rules like those shown above (R1 and R2), the extension problem simplifies significantly, allowing for true linear-time solutions.

Key Insights and Practical Impact

  • The Cubic Barrier: The complexity of general PDAG extension is fundamentally tied to triangle detection, explaining why linear-time solutions remained elusive for 30 years.
  • Degeneracy-Based Performance: While the worst-case is $O(n^3)$, the algorithm's complexity is $O(dm)$, where $d$ is the graph's degeneracy. For sparse, real-world causal graphs, the algorithm performs near-linearly.
  • Recognition Complexity: The paper also proves that recognizing whether a graph is an MPDAG takes $O(n^3)$ time, matching the extension complexity.

These findings suggest that modern causal discovery software (such as pcalg or dagitty) should adopt these $O(n^3)$ and $O(n+m)$ primitives to handle the increasing scale of modern datasets.

Summary updated

Abstract

Finding a consistent DAG extension for a given partially directed acyclic graph (PDAG) is a basic building block used in graphical causal analysis. In 1992, Dor and Tarsi proposed an algorithm with...
BibTeX
@inproceedings{wienobst2021extendability,
  author = {Marcel Wienöbst and Max Bannach and Maciej Liskiewicz},
  title = {{Extendability of causal graphical models: Algorithms and computational complexity}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=_RbZtd5kUrT},
}
Figure