This paper, presented at AAAI-2024, tackles a fundamental problem in causal inference: understanding the space of possible causal models that fit a given set of undirected connections. The authors present the first Fixed-Parameter Tractable (FPT) algorithm for counting the number of Markov Equivalence Classes (MECs) that share the same undirected skeleton.
The Problem: Counting Causal Structures
In causal discovery, we often represent relationships between variables using Directed Acyclic Graphs (DAGs). However, observational data usually cannot distinguish between different DAGs that represent the same conditional independence relations. These indistinguishable DAGs form a Markov Equivalence Class (MEC).
A key property of an MEC is that all DAGs within it share the same skeleton (the underlying undirected graph) and the same set of v-structures (patterns like $a \to b \leftarrow c$). A long-standing question in the field is: Given an undirected graph $G$, how many distinct MECs have $G$ as their skeleton? This is vital for understanding the complexity of the causal model space.
As shown in the figure above, a simple skeleton $B-A-C$ can correspond to multiple MECs. $M_1$ represents the class where no v-structure is formed, while $M_2$ represents the class containing the v-structure $B \to A \leftarrow C$.
Methodology: Shadows and Tree Decomposition
The paper introduces a sophisticated dynamic programming approach based on tree decomposition. Tree decomposition is a technique that "thickens" a graph into a tree-like structure, where the "width" of the decomposition (treewidth) measures how far the graph is from being a tree.
The core technical innovation is the "shadow" of an MEC. Because MECs are defined by global constraints (like being a "chain graph" and having "strongly protected" edges), they cannot be counted by looking at small, isolated pieces of the graph. The authors' "shadow" acts as a local summary of these long-range constraints. It tracks:
- The local orientation of edges.
- The existence of "triangle-free paths" between vertices.
By defining how these shadows can be "projected" and "extended" across the nodes of a tree decomposition, the authors can recursively count the total number of valid MECs without having to enumerate them all. The authors identify that "triangle-free paths" (paths where no two non-adjacent nodes share an edge) are the crucial link for maintaining the "strongly protected" property of directed edges across different parts of the graph.
Key Results and Complexity
The algorithm runs in $O(n(2^{O(k^4 \delta^4)} + n^2))$ time, where $n$ is the number of nodes, $k$ is the treewidth, and $\delta$ is the maximum degree of the graph. This is the first algorithm to show that the problem is Fixed-Parameter Tractable. This means that if a graph is "relatively simple" (low treewidth and low degree), the algorithm remains efficient even as the number of variables ($n$) grows very large. As a corollary, the algorithm provides a polynomial-time solution for tree graphs with bounded degrees.
Limitations and Future Work
While a significant theoretical milestone, the algorithm has some limitations. The exponent in the complexity ($k^4 \delta^4$) is quite high, meaning it might still be slow for graphs that aren't very sparse. Furthermore, it remains an open question whether a fully polynomial-time algorithm exists or if the counting problem is #P-hard for general graphs. This work provides a significant theoretical bridge, moving us closer to a complete understanding of the combinatorial structure of causal models.
Summary updated