I-CAM-UV: Integrating Causal Graphs over Non-Identical Variable Sets Using Causal Additive Models with Unobserved Variables

This paper proposes I-CAM-UV, a novel approach that integrates Causal Additive Models with Unobserved Variables (CAM-UV) across multiple datasets with non-identical variable sets to overcome the limitations of existing methods in identifying causal relationships obscured by unobserved confounders.

The Gist

Imagine you are a detective trying to solve a mystery: Who caused what? In the world of science, this is called "causal discovery." Usually, detectives look at one big case file (a dataset) to figure out the story. But in the real world, we often have many different case files that don't quite match up.

Some files only have clues about suspects A, B, and C. Others only have clues about suspects B, C, and D. Some files have missing pages (unobserved variables), and some suspects never appear together in the same file.

This paper introduces a new detective tool called I-CAM-UV. Here is how it works, explained simply:

1. The Problem: The "Jigsaw Puzzle" with Missing Pieces

Imagine you have three different jigsaw puzzles.

• Puzzle 1 shows the sky and some clouds.
• Puzzle 2 shows the ground and some trees.
• Puzzle 3 shows the trees and the sky.

If you just try to glue them together by matching the edges you can see, you might miss the big picture. For example, you might not know if the clouds cause the rain on the ground because no single puzzle shows both clouds and rain together. Also, sometimes a "ghost" variable (like wind) is pulling the strings, but it's invisible in the photos.

Previous methods tried to just overlap the pictures they had. If a connection wasn't visible in any picture, they gave up. This paper says: "We can do better by using logic to fill in the gaps."

2. The Tool: "CAM-UV" (The Detective's Notebook)

Before combining the puzzles, the researchers use a special tool called CAM-UV. Think of this as a detective's notebook that doesn't just list what it sees, but also writes down what it suspects is missing.

• Standard Detective: "I see A and B connected. I don't see C."
• CAM-UV Detective: "I see A and B connected. I suspect there is a hidden 'Ghost' variable (C) pulling the strings, or maybe A and B are connected through a secret tunnel we can't see."

This tool creates a "mixed map" that includes both solid lines (proven connections) and dotted lines (suspected hidden connections).

3. The Solution: "I-CAM-UV" (The Master Architect)

Now comes the magic part: I-CAM-UV.

Instead of just pasting the maps together, I-CAM-UV acts like a Master Architect who takes all the "mixed maps" from the different datasets and tries to build one single, perfect 3D building (a full causal graph) that fits all the clues.

Here is how the Architect works:

1. The Consistency Check: The Architect asks, "If I build a wall here (a causal link), does it break the rules of Puzzle 1? Does it break the rules of Puzzle 2?"
2. Filling the Gaps: If Puzzle 1 says "A and B are linked via a ghost," and Puzzle 2 says "B and C are linked," the Architect tries to build a bridge between A and C that makes both puzzles happy.
3. The "Best-First" Search: There are billions of ways to build this building. The Architect doesn't try them all randomly. Instead, they use a smart search strategy (like a GPS finding the shortest route). They start with the most likely building and only explore variations that are "close enough" to the truth. If a variation is too weird (too many contradictions), they ignore it.

4. The Result: A List of "Most Likely" Stories

Because the data is imperfect, the Architect might not find just one perfect building. Instead, they might find a small list of very similar buildings that all fit the clues reasonably well.

• Old Method: "I can only tell you about the parts I saw. The rest is a mystery."
• I-CAM-UV: "I can't tell you the exact truth with 100% certainty, but here are the top 5 most likely stories that explain all the evidence we have, including the hidden parts."

Why is this a big deal?

• It handles the "Invisible": It can guess relationships between variables that were never seen together in the same dataset.
• It handles the "Hidden": It accounts for "ghost" variables (unobserved confounders) that mess up simple analysis.
• It's efficient: Even though there are billions of possibilities, the smart search algorithm finds the good ones quickly, making it usable on real computers.

In a Nutshell

If you have a bunch of incomplete, messy reports about a complex system, I-CAM-UV is the smart system that reads all of them, spots the hidden patterns, and builds a complete, logical story of cause-and-effect that makes sense of the whole mess. It turns a pile of confusing, partial clues into a clear, actionable map.

Technical Summary

1. Problem Definition

The paper addresses the challenge of causal discovery from multiple observational datasets that share a common causal structure but differ in their variable sets (non-identical variables).

• Context: In many scientific fields (biology, environmental science), researchers often have multiple datasets where different subsets of variables are measured. Standard causal discovery methods typically assume a single dataset with no unobserved confounders.
• Limitations of Existing Approaches:
  • Simple Overlapping: Estimating a graph for each dataset and merging them fails because unobserved variables in one dataset can act as confounders, and some variable pairs may never be observed simultaneously in any dataset.
  • Partial Ancestral Graphs (PAGs): Methods like ION, IOD, and COmbINE output PAGs (which represent equivalence classes) rather than full Directed Acyclic Graphs (DAGs), leaving causal directions ambiguous.
  • Linear Assumptions: Methods like CD-MiNi are restricted to linear non-Gaussian models, failing to capture non-linear relationships common in real-world data.
• Core Challenge: How to integrate results from multiple datasets with different observed variables and unobserved confounders to recover a full, non-linear causal DAG, specifically identifying relationships between variables that are never observed together.

2. Methodology: I-CAM-UV

The authors propose I-CAM-UV (Integrating CAM-UV), a framework that leverages Causal Additive Models with Unobserved Variables (CAM-UV) to integrate causal structures.

A. Theoretical Foundation

• CAM-UV: Unlike standard CAM, CAM-UV allows for unobserved variables ($U$). It outputs a mixed graph containing:
  • Directed edges ($A$): Identified causal relationships.
  • Undirected edges ($N$): Pairs of variables where the causal relationship is unidentifiable due to an Unobserved Causal Path (UCP) or Unobserved Backdoor Path (UBP).
• Consistency Definition: A global DAG is considered "consistent" if, for every dataset $k$, the unobserved paths (UCP/UBP) implied by the global graph match the undirected edges ($N_k$) found by CAM-UV on that specific dataset.
• The Goal: Enumerate all global DAGs that satisfy this consistency condition across all $m$ datasets.

B. Algorithm: Best-First Combinatorial Search

Since the number of possible DAGs is exponential, the authors propose an efficient search algorithm:

1. State Space: The algorithm searches over the set of variable pairs $E$ that are either unidentifiable (from $N_k$) or unobserved simultaneously ($E_{uno}$). For each pair, it decides to: (1) add a directed edge $v_i \to v_j$, (2) add $v_j \to v_i$, or (3) exclude the edge.
2. Monotonicity & Cost Function: The algorithm defines an inconsistency cost $C(\tilde{G})$, which counts the number of variable pairs where the global graph's implied UCP/UBP status contradicts the CAM-UV results.
   • Crucially, the cost function is monotonic: extending a partial graph never decreases the inconsistency cost.
3. Best-First Search: Using a priority queue (heap), the algorithm explores states in ascending order of their lower-bound inconsistency cost.
   • It stops when the cost exceeds a user-defined threshold ($C^* + b$).
   • This allows the algorithm to find the most consistent DAGs first without exhaustively searching the entire space.
4. Efficiency: The algorithm uses polynomial-time subroutines (Breadth-First Search) to detect UCPs and UBPs during the search, keeping the per-state computation manageable.

C. Handling Real-World Imperfections

In practice, CAM-UV estimation may contain errors. The authors introduce a relaxed problem formulation where the algorithm enumerates DAGs with an inconsistency cost within a tolerance $b$ of the minimum possible cost. This ensures the method remains robust even if the initial CAM-UV estimates are imperfect.

3. Key Contributions

1. I-CAM-UV Framework: A novel approach to integrate causal graphs from multiple datasets with non-identical variable sets, specifically handling non-linear relationships and unobserved confounders.
2. Theoretical Guarantees: Proof that the ground truth DAG is consistent with CAM-UV results under ideal conditions (no estimation error, no hidden variables outside the union of observed sets).
3. Efficient Algorithm: A best-first search algorithm that exploits the monotonicity of inconsistency costs to efficiently enumerate consistent DAGs, avoiding the need to output Partial Ancestral Graphs (PAGs) and instead providing explicit DAGs.
4. Unobserved Pair Resolution: The method uniquely enables the identification of causal directions between variable pairs that are never observed together in any single dataset, a task impossible for standard overlapping methods.

4. Experimental Results

The authors evaluated I-CAM-UV on 100 synthetic datasets (10 variables, non-linear functions) against baselines: CAM-UV-OVL (simple overlap), PC-OVL, Imputation (k-NN), and CD-MiNi.

• Recall (Q1 & Q2): I-CAM-UV demonstrated superior recall compared to all competitors on both observed and unobserved variable pairs. It successfully recovered causal relationships missed by single-dataset CAM-UV and identified directions for unobserved pairs.
• Precision & F1 (Q1 & Q2): While precision decreased slightly compared to the simple overlap (due to the exploration of more possibilities), the overall F1 scores were comparable to the best baselines, indicating a balanced trade-off.
• Enumeration Behavior (Q3): The number of enumerated DAGs varied widely. However, the accuracy distribution of these DAGs formed a single cluster, meaning most enumerated graphs had similar high accuracy. This suggests that random sampling from the output set is effective for practical analysis.
• Computation Time (Q4): The enumeration process was generally fast and comparable to other methods, validating the efficiency of the best-first strategy. However, computation time is exponential in the worst case, making it most suitable for sparse graphs or small numbers of unobserved pairs.

5. Significance and Limitations

Significance:

• Practical Utility: The method bridges the gap between theoretical causal discovery and real-world data limitations (missing variables, multiple sources).
• Non-Linearity: It extends causal integration beyond linear models (LiNGAM) to non-linear additive models, broadening applicability to complex scientific domains.
• Explicit DAGs: By outputting explicit DAGs rather than equivalence classes (PAGs), it provides more actionable insights for decision-making.

Limitations:

• Dependency on CAM-UV: The accuracy of I-CAM-UV is heavily dependent on the quality of the initial CAM-UV estimates.
• Output Volume: In some cases, it may generate a large number of DAGs, requiring human filtering or sampling strategies.
• Scalability: As an exponential-time algorithm, it faces challenges with very large numbers of unobserved variable pairs, though it remains tractable for small-to-medium systems (e.g., ~10 variables).

Future Work: The authors suggest extending the framework to other causal discovery methods (e.g., RCD), developing compressed representations for the output DAGs, and improving the underlying CAM-UV estimation accuracy.