📊 statistics

A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variables

This paper introduces DiCoLa, a theoretically sound and complete recursive decomposition framework that extends divide-and-conquer causal discovery to settings with latent variables, significantly improving computational efficiency while maintaining accuracy in both synthetic and real-world scenarios.

Original authors: Zheng Li, Feng Xie, Shenglan Nie, Xichen Guo, Ruxin Wang, Hao Zhang

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zheng Li, Feng Xie, Shenglan Nie, Xichen Guo, Ruxin Wang, Hao Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Too Many Variables" Puzzle

Imagine you are a detective trying to figure out how a complex machine works. You have a list of 100 different buttons and lights (variables) on the machine. Your goal is to draw a map showing which button causes which light to turn on.

However, there's a catch: some parts of the machine are hidden inside a black box. You can't see them, but they are pulling the strings. In the paper's language, these are latent variables.

To figure out the map, traditional detectives (algorithms) have to ask a massive number of questions like, "If I press Button A and hold Button B, does Light C still turn on?" This is called a Conditional Independence (CI) test.

The Issue: As the number of buttons grows, the number of questions explodes. It becomes so computationally expensive (like trying to solve a puzzle with a calculator that runs on a potato) that it's impossible to finish in a reasonable time.

The Old Solution: "Divide and Conquer" (But with a Flaw)

Previously, smart detectives tried to solve this by breaking the big machine into smaller, manageable rooms. They would solve the puzzle for Room A, then Room B, and then try to glue the maps together.

The Flaw: This old method only worked if the machine was "perfectly transparent" (no hidden black boxes). If there were hidden parts connecting Room A and Room B, the old method would get confused and produce a broken map. It assumed that if two things weren't directly connected, they had no secret common cause.

The New Solution: DICOLA

The authors of this paper, Zheng Li and Feng Xie, say: "What if we can still break the machine into rooms, even if there are hidden black boxes?"

They built a new framework called DICOLA (Divide and Conquer for Latent variables). Here is how it works, using a simple analogy:

1. The "Secret Separator" (The Tripartition)

Imagine you have a huge crowd of people (variables). You want to split them into two groups, Group A and Group B, to study them separately.

The Challenge: If Group A and Group B are secretly chatting through a hidden hallway (latent variables), you can't just split them.
The DICOLA Trick: The algorithm looks for a specific group of people, let's call them the Mediators (Group C).
The Rule: If you put the Mediators in the middle, Group A and Group B stop talking to each other unless they talk through the Mediators.
- Analogy: Imagine Group A is the kitchen, Group B is the bedroom, and the Mediators are the hallway. If you block the hallway, the kitchen and bedroom are effectively isolated. You can study the kitchen's internal wiring and the bedroom's internal wiring separately, knowing that any connection between them must go through the hallway.

2. The Recursive "Russian Doll" Approach

DICOLA doesn't just split the problem once; it does it over and over again.

It finds a hallway (separator) to split the whole house into two wings.
Then, it looks at the Kitchen wing and finds another hallway to split it into the stove area and the fridge area.
It keeps doing this until the rooms are so small that the detective can easily solve the puzzle for that tiny room without getting overwhelmed.

3. The "Glue" Step (Reconstruction)

Once the small rooms are solved, DICOLA has to put the maps back together.

The Smart Glue: It doesn't just paste the maps randomly. It uses a strict rule: "If a connection exists in the final map, it must be supported by both sides of the split."
If the Kitchen map says the stove connects to the fridge, and the Bedroom map says the bed connects to the closet, those stay.
But if the Kitchen map says the stove connects to the bedroom, but the Bedroom map says there is no such connection, DICOLA knows that connection was a false alarm caused by the hidden hallway and removes it.

Why This Matters

The paper proves two main things:

It Works: They mathematically proved that even with hidden variables, this splitting and gluing method will always find the correct map (or the closest possible version of it).
It's Fast: By breaking the big problem into tiny pieces, they drastically reduced the number of "questions" (CI tests) the computer needs to ask.
- Analogy: Instead of asking every person in a stadium of 10,000 how they know everyone else, you ask 10 small groups of 100 people. It's much faster, and you still get the full picture.

Real-World Test

The authors tested this on:

Fake Data: They created thousands of random "machines" with hidden parts and showed that DICOLA solved them much faster than the old methods, without making more mistakes.
Real Data: They applied it to a real dataset about plant genes (specifically Arabidopsis thaliana). They successfully mapped out how different genes interact, correctly identifying that genes involved in different biological pathways (like the "MVA" and "MEP" pathways) formed distinct clusters, just as biologists expected.

Summary

DICOLA is a new strategy for figuring out cause-and-effect relationships in complex systems. It solves the problem of "hidden variables" by finding "neutral zones" (separators) that allow us to break a giant, confusing puzzle into small, solvable pieces, solve them, and then perfectly reassemble the whole picture. It makes the impossible possible by being smarter about how we divide the work.

Technical Summary: A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variables

Problem Statement

Constraint-based causal discovery is a fundamental approach for inferring causal structures from observational data. However, its reliance on exhaustive conditional independence (CI) testing renders it computationally prohibitive in high-dimensional settings. While divide-and-conquer frameworks have been proposed to mitigate this cost by decomposing global learning tasks into smaller subproblems, existing methods critically rely on the assumption of causal sufficiency (i.e., the absence of latent variables). In real-world systems where latent confounders are prevalent, these methods fail because the presence of unobserved common causes induces complex dependencies that violate the assumptions required for standard decomposition.

The central question addressed by this work is: Can divide-and-conquer strategies for causal structure learning be theoretically generalized beyond causal sufficiency to settings with latent variables?

Methodology: The DICOLA Framework

The authors propose DICOLA (Divide-and-Conquer for Latent Variables), a recursive decomposition framework designed to recover the Partial Ancestral Graph (PAG) representing the Markov equivalence class of the underlying Maximal Ancestral Graph (MAG) in the presence of latent variables.

Theoretical Foundations

The framework is built upon the properties of m-separation in ancestral graphs. The authors establish three key theorems that justify the decomposition and reconstruction process:

Theorem 1: If a variable set $O$ is partitioned into disjoint subsets $(A, B, C)$ such that $A \perp\!\!\!\perp B \mid C$ , then for any $X \in A$ and $Y \in A \cup C$ , the m-separation of $X$ and $Y$ depends only on subsets of $A \cup C$ . Variables in $B$ are irrelevant for determining separating sets for pairs within $A \cup C$ .
Theorem 2: For distinct vertices $X, Y \in C$ , if they are m-separated in the full set $O$ , a separating set exists within either $A \cup C$ or $B \cup C$ .
Theorem 3 (Reconstruction Principle): The global skeleton can be recovered by merging local skeletons from subproblems. Specifically, edges between variables outside the separator $C$ are inherited directly, while edges within $C$ are retained only if they exist in both sub-solutions.

Algorithmic Implementation

The DICOLA framework follows a "divide-learn-merge" paradigm:

Decomposition (Divide): The algorithm identifies a valid tripartition $(A, B, C)$ of the observed variables $K$ such that $A \perp\!\!\!\perp B \mid C$ . To find this efficiently, it constructs an Undirected Independence Graph (UIG) based on the Markov Blankets of variables. The UIG serves as a surrogate structure where vertex separators correspond to valid conditional independence separators in the underlying MAG.
Local Learning (Learn): The global problem is recursively decomposed into subproblems defined on $A \cup C$ and $B \cup C$ . This continues until leaf subproblems are reached where no further valid tripartition exists. At the leaves, a base causal discovery algorithm (e.g., FCI, RFCI) is executed to learn the local skeleton.
Reconstruction (Merge): Local skeletons are merged bottom-up. The merging step applies Theorem 3: the union of edges from child skeletons forms the parent skeleton, with edges within the separator set $C$ removed if they are missing in either child skeleton. Finally, orientation rules (Zhang, 2008b) are applied to the global skeleton to produce the PAG.

Key Contributions

Theoretical Generalization: The paper establishes the first theoretical foundation for divide-and-conquer causal structure learning in the presence of latent variables. The authors prove that m-separation relations propagate top-down during decomposition and exhibit bottom-up consistency during merging, ensuring that the decomposition does not lose information regarding the Markov equivalence class.
DICOLA Framework: A novel recursive framework that integrates with existing constraint-based algorithms. The authors prove that if the base learner is sound and complete, DICOLA is also sound and complete.
Efficiency via Markov Blankets: The method leverages Markov blanket learning to construct minimal UIGs, enabling the identification of valid decompositions without exhaustive CI testing over the entire variable set.

Experimental Results

The authors evaluated DICOLA by integrating it with five state-of-the-art algorithms: FCI, RFCI, FCI+, L-MARVEL, and ICD. Experiments were conducted on synthetic data (Erdős–Rényi random graphs and benchmark Bayesian networks) and a real-world gene expression dataset (Arabidopsis thaliana).

Computational Efficiency: Across all settings, DICOLA significantly reduced the number of CI tests and execution time compared to the standalone base algorithms. The acceleration was most pronounced in sparse and well-decomposable graphs.
Structural Accuracy: The framework generally maintained or improved the F1-scores of the base methods. In some simpler graph settings, a slight trade-off in accuracy was observed for specific combinations (e.g., DICOLA+L-MARVEL), but this was mitigated in more complex, high-dimensional settings with dense connectivity or increased latent confounding.
Real-World Application: Applied to the Arabidopsis thaliana gene expression data, DICOLA+FCI successfully recovered the modular structure of known metabolic pathways (MEP and MVA), identifying dense intra-pathway connections and sparse inter-pathway interactions consistent with biological literature.

Significance and Claims

The paper claims to provide a theoretically justified solution to a long-standing limitation in causal discovery: the inability to apply divide-and-conquer strategies when latent variables are present. By proving the soundness and completeness of the framework, the authors demonstrate that computational efficiency can be achieved without sacrificing the theoretical guarantees required for valid causal inference in the presence of confounding.

The authors note that while the acceleration is substantial for sparse graphs, the benefits diminish as graph density increases, as finding valid separators becomes more difficult. However, they emphasize that the framework remains sound even in these cases, effectively degrading to the performance of the base learner rather than producing incorrect results. The work opens the door for applying scalable divide-and-conquer techniques to a broader range of real-world causal discovery problems where latent confounding is the norm rather than the exception.