🤖 machine learning

On the Granularity of Causal Effect Identifiability

This paper introduces and analyzes state-based causal effect identifiability, demonstrating that it can be achieved even when traditional variable-based identifiability fails by leveraging additional knowledge such as context-specific independencies and state constraints.

Original authors: Yizuo Chen, Adnan Darwiche

Published 2026-07-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yizuo Chen, Adnan Darwiche

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 Detective's Dilemma: Why "Sometimes" Matters More Than "Always"

Imagine you are a detective trying to solve a mystery using only a map of the city and a logbook of where people were seen. You want to know: "If I force a suspect to take a specific route, where will they end up?" In the world of science, this is called causal inference. It's the art of figuring out what causes what, rather than just noticing that two things happen together. Usually, detectives (or scientists) rely on a map called a causal graph, which shows how different variables—like "smoking," "lung health," or "drug dosage"—are connected. They also look at observational data, which is just a record of what happened naturally without anyone interfering.

The big challenge is that sometimes, the map and the logbook aren't enough to give a single, definite answer. Maybe there are hidden factors (like a secret genetic trait) that the map doesn't show, making it impossible to know for sure if the drug caused the recovery or if the patient just got lucky. For decades, scientists have had rules to decide if a cause-and-effect question is "solvable" (identifiable) or "unsolvable." These rules usually ask a very broad question: "Can we figure out the effect of this drug on any patient, in any situation?" If the answer is "no" for even one tricky scenario, the whole drug's effect was considered a mystery. But what if we don't need to know about every patient? What if we only care about the specific patients who are already taking the drug and want to know if they will recover? This paper asks if zooming in on specific details can turn an unsolvable mystery into a solvable one.

Zooming In: From "All Patients" to "This Patient"

This paper, titled "On the Granularity of Causal Effect Identifiability," suggests that the old way of asking questions might be too broad. The authors, Yizuo Chen and Adnan Darwiche from UCLA, argue that we should stop asking, "Does this treatment work for everyone?" and start asking, "Does this treatment work for this specific type of person?" They call this shift moving from variable-based identifiability (the big picture) to state-based identifiability (the fine details).

Think of it like a weather forecast. The old method asks: "Will it rain tomorrow?" If the weather model is too messy to predict rain for every possible scenario, the answer is "We don't know." But the new method asks: "Will it rain if the temperature drops below 50 degrees?" Even if the model can't predict rain for all temperatures, it might be able to predict it perfectly for that one specific cold snap. The paper shows that by focusing on specific "states" (like a specific temperature or a specific patient's condition), we can often find answers that were previously hidden.

The Secret Clue: Context-Specific Independence

The magic ingredient that makes this zooming-in possible is something called Context-Specific Independence (CSI). In plain English, CSI is a rule that says, "In this specific situation, two things stop influencing each other."

Imagine a light switch. Usually, the light depends on two things: whether the power is on and whether someone is flipping the switch. But if the power goes out (the "context"), the light stops caring about the switch. The switch could be flipped up or down, but the light stays off. This is a CSI: Light is independent of the Switch, given that the Power is Out.

The paper demonstrates that if we know these special "context rules," we can solve mysteries that seemed impossible before. However, there's a catch. The old "variable-based" rules would look at the whole picture and say, "We can't solve this because sometimes the switch matters and sometimes it doesn't." The new "state-based" approach says, "Wait, if we only look at the times when the power is out, the switch doesn't matter anymore, so we can solve it!"

The authors prove that this distinction is real and important. They show that a causal effect might be unidentifiable (unsolvable) when looking at the whole variable, but identifiable (solvable) when looking at a specific state, provided we have these extra context clues. Without these clues, the two approaches are actually the same, and zooming in doesn't help. But with the clues, the "fine-grained" view opens up new doors.

The Power of "State Constraints"

The paper also explores another type of clue: state constraints. This is simply knowing that a variable can only be in certain states. For example, knowing that a "Weather" variable can only be "Rain" or "Snow," but never "Sunshine."

The authors found that knowing the limits of a variable's states doesn't help much on its own. It's like knowing a die only has numbers 1 through 6; that doesn't tell you if you can predict the roll. But, when you combine this knowledge with those CSI clues (the "context rules"), it becomes a superpower. It's like having a map that says "The switch doesn't matter when the power is out" and knowing that "The power is only ever out or on." Together, these constraints can make a previously unsolvable puzzle solvable.

The New Detective Toolkit

To prove these ideas, the authors didn't just talk about it; they built new algorithms (computer programs) to test them. They created a method called ID-CSI and an extended version called ID-CSI-STATE. These tools act like a super-detective that can:

Look at a specific situation (a specific "state").
Use the context clues (CSI) to prune away unnecessary parts of the map.
Check if the answer can be found for that specific slice of reality.

They tested these tools on thousands of randomly generated "mystery maps" with different numbers of variables (from 6 up to 50). The results were clear:

More clues = More answers: As they added more CSI constraints, the number of solvable mysteries increased.
The gap widens: The difference between what the old "broad" method could solve and what the new "specific" method could solve got bigger as the puzzles got more complex.
Speed matters: Their new method was much faster than existing tools (like a package called DOSEARCH) when dealing with large, complex maps. In fact, for maps with 50 variables, the old tools often gave up after 5 minutes, while the new method solved them in seconds.

The Bottom Line

This paper doesn't claim that we can now solve every causal mystery. Instead, it suggests that we have been asking the wrong questions. By being more specific—by asking about "this patient" instead of "all patients," and by using specific context clues—we can solve problems that were previously thought impossible.

The authors show that the world of cause-and-effect is more nuanced than we thought. Sometimes, the answer isn't "we don't know," but rather "we know the answer for this specific case." It's a reminder that in science, as in life, sometimes the most powerful way to see the whole picture is to focus intently on a single, small detail.

Technical Summary: On the Granularity of Causal Effect Identifiability

Problem Statement

The classical notion of causal effect identifiability is defined at the variable-based level: determining whether the causal effect of a set of treatment variables $X$ on a set of outcome variables $Y$ (denoted $Pr_X(Y)$ ) can be uniquely estimated from observational data and a causal graph. This approach assumes that if the effect is identifiable, it must be identifiable for every possible intervention on $X$ and every possible state of $Y$ .

However, in many practical scenarios, researchers are interested in state-based causal effects: the effect of a specific intervention $X=x$ on a specific outcome state $Y=y$ (denoted $Pr_x(y)$ ). The paper argues that the variable-based definition is often too coarse-grained, especially when additional knowledge beyond the causal graph and observational data is available. Specifically, the authors investigate whether state-based effects can be identifiable even when the corresponding variable-based effect is not, and how additional constraints—specifically Context-Specific Independencies (CSIs) and state constraints—influence this distinction.

Methodology

1. Formalizing State-Based Identifiability

The paper defines State-Based Identifiability (Definition 2) as the unique computability of $Pr_x(y)$ from the observational distribution $Pr(V)$ for specific states $x$ and $y$ , given a causal graph $G$ .

Classical Equivalence: In the absence of additional constraints (only $G$ and $Pr(V)$), the paper proves (Proposition 1) that variable-based and state-based identifiability are equivalent. If one is identifiable, the other is too.
The Role of Constraints: The distinction becomes meaningful only when additional knowledge is introduced. The paper focuses on two types of constraints:
- Context-Specific Independencies (CSIs): Constraints of the form $(Y \perp\!\!\!\perp P_1 | p_2, P_3)$ , indicating independence holds only under specific context states $p_2$ .
- State Constraints: Knowledge restricting the possible states of certain variables (e.g., a variable is binary).

2. Theoretical Separation Results

The authors demonstrate that additional knowledge can create a separation between the two levels of identifiability:

CSI Constraints: While CSIs can render some variable-based effects identifiable (Proposition 7), they can also render specific state-based effects identifiable while leaving the variable-based effect unidentifiable (Proposition 6). For example, a policy might ignore a variable's degree only for entry-level employees; this CSI makes the effect of experience on salary identifiable for entry-level workers but not for senior workers, rendering the overall variable-based effect unidentifiable.
State Constraints: Alone, state constraints do not improve identifiability in semi-Markovian graphs (Proposition 8). However, when coupled with CSIs, they can significantly improve both variable-based and state-based identifiability (Proposition 9). Furthermore, they can enable state-based identifiability for specific states while the variable-based effect remains unidentifiable (Proposition 10).

3. Algorithms for Identification

To test identifiability under these constraints, the paper proposes a systematic approach based on graph decomposition:

Context-Induced Graphs (CI-graphs): The authors introduce CI-graphs, which are pruned versions of the original causal graph where edges are removed based on active CSIs under a specific context. This reduces the parameter space and simplifies the graph structure.
Algorithm 1 (ID-CSI): An algorithm for testing state-based identifiability under CSI constraints. It enumerates possible CI-graphs under the context of the treatment and outcome states ($xy$), decomposes the resulting mutilated graph into c-components, and checks the identifiability of the induced c-factors using a modified recursive procedure (ID-QFUNC).
Algorithm 2 (ID-CSI-STATE): An extension that handles both CSIs and state constraints. It utilizes context-partitions to split the identification problem into sub-queries. The algorithm iterates over all possible context-partitions of variables constrained by state constraints, reducing the problem to identifying sub-queries $Pr_x(y, s_i)$ using Algorithm 1.
Heuristics: To address the exponential complexity of enumerating CI-graphs and context-partitions, the paper proposes heuristics (Section 5.4) that select a single choice for graph pruning and context partitioning, reducing complexity to polynomial time for CSI-only cases.

Key Contributions

Granularity of Identifiability: The paper establishes that state-based identifiability is a strictly finer-grained concept than variable-based identifiability when additional constraints (CSIs and state constraints) are present. It proves that a causal effect can be identifiable for a specific state pair while the general variable-based effect remains unidentifiable.
Impact of Constraints: It characterizes how CSIs and state constraints interact. While CSIs alone can separate the two levels, state constraints are shown to be ineffective in isolation but powerful when combined with CSIs, potentially widening the gap between state-based and variable-based identifiability.
Novel Algorithms: The paper introduces Algorithm 1 and Algorithm 2, which extend classical identification methods (like IDENTIFY) to handle CSIs and state constraints. These algorithms utilize context-induced graphs and modified c-factor decomposition to derive identifying formulas or determine unidentifiability.
Empirical Validation: The authors conduct empirical studies on randomly generated causal graphs to evaluate the completeness and efficiency of their proposed algorithms compared to classical methods and the DOSEARCH package.

Results

Identifiability Gains: Empirical results show that imposing CSI constraints and state constraints increases the number of identifiable causal effects for both variable-based and state-based levels.
Widening the Gap: As the number of CSIs increases (controlled by parameter $r$ ), the gap between the number of identifiable state-based effects and variable-based effects widens. For instance, with $n=50$ variables and state constraints, the number of identifiable state-based effects exceeded variable-based effects by 16 when $r=0.8$ .
Efficiency: The proposed heuristic algorithms (ID-CSI-HEU and ID-CSI-STATE-HEU) demonstrate significantly higher computational efficiency compared to DOSEARCH, which relies on exhaustive search and frequently times out on graphs with $n \ge 15$ variables. The proposed methods successfully identify a comparable or larger number of variable-based effects while maintaining tractable runtimes.
Completeness: The algorithms are proven sound. When constraints are absent, Algorithm 1 is equivalent to the complete IDENTIFY algorithm.

Significance

The paper claims that the distinction between variable-based and state-based identifiability is not merely theoretical but has practical implications for causal inference in domains where specific interventions and outcomes are of interest (e.g., policy analysis for specific demographic groups or medical treatments for specific patient states). By showing that additional knowledge (CSIs and state constraints) can render specific state-based effects identifiable where variable-based methods fail, the work highlights the need for more refined, state-based approaches to causal identification. The proposed algorithms provide a practical tool for leveraging this additional knowledge to extract causal insights that would otherwise be inaccessible.