💻 computer science

Clustering and Pruning in Causal Data Fusion

This paper proposes pruning and clustering as preprocessing techniques to reduce the complexity of causal graphs in multi-source data fusion, deriving conditions under which these operations preserve causal identifiability and enable the construction of identifying functionals for complex models.

Original authors: Otto Tabell, Santtu Tikka, Juha Karvanen

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Otto Tabell, Santtu Tikka, Juha Karvanen

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

Imagine you are a detective trying to solve a mystery: "Does smoking during pregnancy cause premature birth?"

In the real world, you rarely have one perfect file containing every single clue. Instead, you have a messy pile of evidence from different sources:

Source A has data on smoking habits and education levels.
Source B has data on smoking and birth outcomes, but no education data.
Source C has data on education and income, but no smoking data.

To solve the mystery, you need to combine these files. This is called Causal Data Fusion. However, trying to combine these files is like trying to solve a massive jigsaw puzzle where the picture is huge, the pieces are scattered, and some pieces are missing entirely. The more variables (pieces) you have, the harder it is for computers to figure out the answer.

This paper introduces two clever tricks to make the puzzle easier to solve without losing the answer: Pruning and Clustering.

1. Pruning: The "Cut the Clutter" Trick

The Metaphor: Imagine you are looking for a specific key in a giant, messy room. You don't need to look under the rug in the corner, in the attic, or inside the locked safe if you know the key is definitely on the kitchen counter. You can safely ignore (prune) the rest of the room to focus on what matters.

What the paper says:
Sometimes, certain variables in your data are completely irrelevant to the specific question you are asking.

Non-Ancestors: If a variable (like "Eye Color") has no path leading to the outcome you care about (like "Premature Birth"), you can throw it out.
Disconnected Variables: If a variable is only connected to the rest of the puzzle by a single thread, or if it becomes useless once you intervene (like forcing someone to smoke), you can remove it.

The Benefit: By cutting out these useless variables before you start the heavy math, you shrink the puzzle. The paper proves that if you cut the right pieces, the answer to your mystery remains exactly the same. You haven't lost any truth; you've just removed the noise.

2. Clustering: The "Grouping" Trick

The Metaphor: Imagine you are organizing a library. Instead of listing every single book by its exact title, author, and year, you group them into "Fiction," "History," and "Science." You treat the whole "History" section as one big block. You don't need to know the details of every book inside the "History" block to know that the block belongs in the History section.

What the paper says:
Sometimes, you have a group of variables that act very similarly. For example, "Income," "Education," and "Job Status" might all be part of a "Socioeconomic Status" block.

Transit Clusters: The paper focuses on a specific type of group called a "Transit Cluster." Think of this as a hallway where information flows in one end and out the other. If you can prove that the "hallway" works as a single unit, you can replace the whole hallway with a single door (a single variable).
The Catch: You can only do this if the data you have covers the "entrance" and "exit" of the hallway properly. If your data is missing the exit, you can't group them yet.

The Benefit: Instead of solving a puzzle with 50 pieces, you solve a puzzle with 10 pieces (where each piece represents a whole group). This makes the computer calculation much faster.

3. The "Do-Search" Engine

The paper mentions a tool called Do-search. Think of this as a super-smart robot that tries every possible way to combine your data files to find the answer.

The Problem: If your puzzle is huge, the robot takes hours or days to find the answer, or it gives up.
The Solution: The authors show that if you Prune (cut the clutter) and Cluster (group the pieces) first, the robot can find the answer in seconds.

4. Why This Matters (According to the Paper)

The authors tested this on thousands of random puzzles. They found:

Speed: For medium-to-large puzzles, using Pruning and Clustering made the computer hundreds of times faster.
Safety: They proved mathematically that if the answer is "Yes" (identifiable) in the small, simplified puzzle, it is "Yes" in the big, messy one. If the answer is "No" in the simplified puzzle (and they checked specific rules), it is "No" in the big one too.
No Harm: Even if the tricks don't make it faster, they don't slow you down much. The time spent checking if you can use the tricks is tiny compared to the time saved.

Real-World Examples from the Paper

The authors didn't just use made-up numbers; they used real-world scenarios:

Infant Mortality: They looked at a study on cigarette prices and infant death. By removing variables that didn't matter (like "GDP" for a specific question) and grouping "Education" and "Maternal Age," they simplified the model and found the answer faster.
Heart Disease: They looked at a study on how life-long socioeconomic status affects heart health. They showed that even if you don't know the exact details of every variable inside a "Socioeconomic" group, you can treat the whole group as one unit and still get the right answer.

The Bottom Line

This paper gives researchers a rulebook for simplifying complex data problems. It says: "Before you try to solve the whole giant puzzle, look for pieces you can throw away and groups you can bundle together. If you follow these rules, you will get the same answer, but you'll get there much, much faster."

It's about working smarter, not harder, by knowing exactly which parts of the data are essential and which are just background noise.

Technical Summary: Clustering and Pruning in Causal Data Fusion

Problem Statement

The paper addresses the general causal effect identification problem, where the goal is to combine observational and experimental data from multiple sources to identify a causal effect $p(y \mid do(x))$ that is not identifiable from any single source. While do-calculus (Pearl, 1995) serves as the general-purpose tool for this task, algorithms based on it (such as Do-search) face significant computational challenges as the number of variables increases and the causal graph becomes complex.

Existing identification algorithms for specific scenarios (e.g., g-identifiability, g-transportability) often rely on restrictive assumptions, such as the availability of entire joint distributions where the union of observed and intervened variables covers all endogenous variables. In contrast, real-world data fusion often involves partially overlapping input distributions (e.g., one source measures $p(x, z)$ and another $p(z, y)$ ), where no current algorithm can determine identifiability without resorting to computationally expensive search-based methods.

The core challenge is that reducing the size of a causal graph (via preprocessing) does not automatically preserve the identifiability of causal effects. If a graph is modified, there is no guarantee that inferences made on the modified graph transfer back to the original. The paper seeks to establish rigorous conditions under which pruning (removing variables) and clustering (combining variables) can be applied to causal data fusion problems without altering the status of identifiability.

Methodology

The authors propose a framework for preprocessing causal graphs in the context of multiple data sources. They generalize previous results (Tikka and Karvanen, 2018; Tikka et al., 2023) which were limited to single observational data sources.

1. Pruning

Pruning involves removing variables that are irrelevant for the identification of a specific causal effect. The paper derives three theorems for pruning in the presence of multiple input distributions $I = \{p(a_i \mid do(b_i), c_i)\}$ :

Theorem 7 (Pruning Non-Ancestors): Variables that are not ancestors of the response variable $Y$ can be removed, provided they are not involved in the conditioning or intervention sets of any input distribution.
Theorem 8 (Pruning Post-Intervention): Variables that become d-separated from $Y$ after an intervention on $X$ can be removed, subject to conditions ensuring that the removal does not alter the d-separation properties between members of $X$ or violate the structure of the input distributions.
Theorem 9 (Pruning Isolated Vertices): Vertices connected to the rest of the graph only through a single variable can be removed if they are not part of any input distribution's conditioning or intervention sets.

2. Clustering

Clustering replaces a set of vertices $T$ with a single vertex $\mathcal{T}$ . The paper focuses on transit clusters, defined as sets of vertices where information flows from "receivers" (nodes with parents outside $T$ ) to "emitters" (nodes with children outside $T$ ) in a specific, uniform manner.

Definition 13 (Transit Cluster): A set $T$ is a transit cluster if all receivers share the same external parents, all emitters share the same external children, and internal connectivity ensures every node is linked to a receiver or emitter.
Identification Invariance: The paper introduces Algorithm 1 (VerifyInputs) to check if a clustering operation preserves identifiability.
- Theorem 17: If a causal effect is identifiable in the clustered graph, it is identifiable in the original graph.
- Theorem 18: If a causal effect is not identifiable in the clustered graph, and VerifyInputs returns TRUE, then it is not identifiable in the original graph.
- Theorem 19: A special case where clustering is always identification invariant if the set of receivers and emitters intersect (i.e., a node serves as both).

3. Recovering Identifying Functionals

The paper demonstrates that identifying functionals derived from pruned or clustered graphs can be mapped back to the original graph:

Theorem 20: For pruning, the identifying functional remains unchanged ( $f(I) = g(I')$ ).
Theorem 21: For clustering, the functional is obtained by replacing the clustered variable $\mathcal{T}$ with the specific subset of the original cluster $T$ that appears in the corresponding input distribution.

Key Results

Generalization to Multiple Sources: The authors successfully extend pruning and clustering invariance results from single-source settings to the general case of multiple, partially overlapping data sources. This is non-trivial because standard concepts like c-components and latent projections are ill-defined when entire distributions are not available.
Algorithmic Verification: The development of VerifyInputs (Algorithm 1) provides a practical method to determine when non-identifiability in a clustered graph implies non-identifiability in the original graph, a critical step for avoiding false negatives.
Computational Efficiency: A simulation study using Do-search on 108,933 instances shows that the reduction strategy (pruning + clustering) significantly outperforms the direct strategy (running Do-search on the original graph) for larger graphs.
- For graphs with 12 vertices, the median time savings in non-identifiable cases (Setting B) exceeded 12 minutes.
- The overhead of checking pruning/clustering conditions is negligible (median < 0.05 seconds).
- In cases where reduction is not applicable, the time penalty is minimal.
Practical Application: The methods were applied to two real-world examples:
- Infant Mortality Study: Demonstrated how pruning reduces a complex graph to a manageable size for identifying the effect of tobacco price on second-hand smoking.
- Atherosclerosis Study (ELSA-Brasil): Showed how clustering variables (e.g., socioeconomic factors) allows for the assessment of identifiability without needing detailed internal structures of the clusters, provided certain conditions are met.

Significance and Claims

The paper claims that pruning and clustering serve as essential preprocessing tools for causal data fusion, particularly in scenarios with partially overlapping data where current polynomial-time algorithms are inapplicable.

Efficiency: The primary significance is the reduction of computational load. By reducing the graph size before applying search-based identification algorithms, the method makes the identification of causal effects feasible for larger, more complex models.
Simplification: The methods allow for more concise presentation of causal graphs and simpler identifying functionals.
Data Collection Planning: The authors note that these techniques can guide data collection strategies. If a variable can be pruned, it need not be measured. If a transit cluster is used, only the "emitters" of the cluster need to be measured to preserve identifiability.
Theoretical Contribution: The work provides sufficient conditions for identification invariance without relying on concepts (c-components, hedges) that require full distributional knowledge. This bridges a gap between theoretical causal inference and practical data fusion constraints.

The authors remain modest regarding the scope, noting that the results apply to marginal causal effects and that the completeness of do-calculus for the general unconstrained case remains an open theoretical question. They emphasize that the application of these operations is a researcher's decision, balancing computational gains against the potential loss of interpretability or the need for specific domain knowledge.