📊 statistics

Constraint-based difference graph discovery in a linear setting

This paper introduces a novel causal discovery framework for linear structural causal models that defines a new "diff-separation" criterion and proposes the LDiffPC algorithm to infer difference graphs between environments by testing the equality of regression coefficients.

Original authors: Daria Bystrova, Emilie Devijver

Published 2026-06-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daria Bystrova, Emilie Devijver

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 figure out how a complex machine works. Usually, you'd look at the machine in one room and try to map out how every gear connects to every other gear. But sometimes, you get to see that same machine in two different rooms (let's call them Room A and Room B).

In Room A, the machine runs smoothly. In Room B, someone has tweaked a few gears, changed the oil, or swapped out a specific part. Your goal isn't to draw a new, complete map of the machine for both rooms. Instead, you want to draw a special "Difference Map" that highlights only the parts that changed.

This paper introduces a new detective tool called LDiffPC to create that Difference Map. Here is how it works, broken down into simple concepts:

1. The Problem: Why Old Maps Don't Work

Traditional detective tools (like the famous "PC algorithm") look for things that are independent. They ask, "If I know about Gear X, does that tell me anything about Gear Y?" If the answer is "no," they assume the gears aren't connected.

However, when comparing two rooms, this old method gets confused.

The Analogy: Imagine Gear X and Gear Y are connected by a spring. In Room A, the spring is tight. In Room B, the spring is loose. Even if the connection (the spring) is still there, the way they move together changes.
The Mistake: Old tools might look at the movement and say, "Hey, they don't move the same way anymore, so the connection must be broken!" Or, they might say, "They still move together, so the connection is fine," missing the fact that the strength of the connection actually changed.

The authors realized that to find the changes, you can't just look at whether things are connected or not. You have to look at how strong the connection is (specifically, the "regression coefficient," which is just a fancy math word for the strength of the relationship).

2. The New Tool: "Diff-Separation"

The paper introduces a new rule called Diff-Separation. Think of this as a special filter.

In normal detective work, you block a path between two gears by putting a "wall" (conditioning set) in the way. If the wall blocks all paths, the gears are "separated."

But in the "Difference Detective" game, a path is only interesting if it involves a changed part.

The Analogy: Imagine a river flowing from a mountain to the sea. In Room A, the water flows fast. In Room B, someone built a dam halfway down.
- If you look at the river above the dam, the water speed is the same in both rooms. That path doesn't matter for your Difference Map.
- If you look at the river below the dam, the speed is different. That path matters.
The Rule: The new "Diff-Separation" rule tells the algorithm to ignore paths that haven't changed and focus only on the paths that carry the "change signal."

3. The "Diff-Faithfulness" Assumption

To make this work, the authors make a reasonable promise called Diff-Faithfulness.

The Promise: They assume that if the "strength" of a connection changes between Room A and Room B, it's because the underlying mechanism actually changed. They also assume that two different mechanisms don't accidentally cancel each other out in both rooms at the exact same time (which would hide the change).
Why it matters: Without this promise, the math might get tricked by coincidences. With it, the algorithm can trust that if the numbers change, a real change happened.

4. The Solution: LDiffPC Algorithm

The paper proposes LDiffPC (Linear Difference PC). Here is how it solves the puzzle:

Start with a Blank Slate: Imagine a web where every single gear is connected to every other gear.
Test the Strengths: The algorithm picks two gears and asks, "Is the strength of the connection between Gear X and Gear Y the same in Room A and Room B?"
- It checks this while "holding constant" (conditioning on) other gears to see if the change is direct or caused by something else.
Cut the Ties: If the strength is exactly the same in both rooms, the algorithm cuts the connection. It says, "This didn't change, so it doesn't belong on our Difference Map."
Keep the Changes: If the strength is different, it keeps the connection. This means "Something changed here!"
Draw the Arrows: Finally, it figures out the direction of the changes (which gear affects which) using a set of logical rules, similar to how a detective deduces who pushed whom.

5. Why This is a Big Deal

The authors show that this method is sound (it won't lie to you) and complete (it won't miss anything) under their assumptions.

The "Magic" Part: Unlike older methods that try to rebuild the entire machine map for both rooms first (which is hard and error-prone), LDiffPC goes straight for the changes. It skips the boring parts that stayed the same and focuses entirely on what's different.
The Result: You get a clean, compact map that shows exactly where the "gears" shifted between the two environments.

Summary

Think of this paper as inventing a highlighter pen for causal graphs. Instead of trying to redraw the whole picture of how the world works, this tool scans two versions of reality and highlights only the lines that changed color. It uses a new set of rules ("Diff-Separation") to make sure it doesn't get tricked by things that look different but aren't, or things that look the same but actually changed. This allows scientists to quickly spot exactly where and how systems (like ecosystems or biological processes) are shifting.

Technical Summary: Constraint-based Difference Graph Discovery in a Linear Setting

Problem Definition
The paper addresses the challenge of inferring a difference graph (or difference DAG) between two distinct environments, $e_1$ and $e_2$ , where the underlying causal mechanisms may vary. While traditional causal discovery aims to reconstruct a single causal graph from observational data, this work focuses on identifying changes in causal relationships across populations. The goal is not to relearn the full causal structure in each environment but to characterize specific structural differences, such as changes in direct effects (soft interventions) or removal of edges (hard interventions).

Existing methods for difference graph discovery often rely on parametric assumptions (e.g., linearity, Gaussianity) and lack a systematic graphical characterization within the classical constraint-based framework. Specifically, there is no established analogue to d-separation that explains when the equality (or inequality) of statistical quantities across environments reflects underlying causal changes. Standard conditional independence tests (e.g., based on mutual information or partial correlation) are insufficient because changes in dependence structures can occur even when direct causal effects remain invariant, due to shifts in other parts of the system.

Methodology and Key Contributions

The authors propose a constraint-based approach tailored for Linear Structural Causal Models (SCMs). The core methodology involves three main theoretical and algorithmic contributions:

Diff-Separation Criterion:
The paper introduces diff-separation, a new graphical criterion that extends beyond standard d-separation. The authors demonstrate that invariance of regression coefficients across environments is governed by conditions more complex than simple path blocking.
- Diff-relevant paths: A path is considered diff-relevant if it contains an edge present in the difference DAG or if it involves nodes with ancestors connected to the difference DAG.
- Definition: A set $Z$ diff-separates $X_i$ from $X_j$ if it blocks all diff-relevant paths and all conditionally diff-relevant paths between them.
- Significance: This criterion characterizes exactly when a conditioning set ensures that the regression coefficient of $X_i$ on $X_j$ remains equal across environments, even if the underlying graphs differ.
Diff-Faithfulness Assumption:
To link the graphical criterion to statistical tests, the authors introduce diff-faithfulness. Unlike traditional faithfulness, which links d-separation to conditional independence, diff-faithfulness links diff-separation to the equality of regression coefficients.
- Assumption: $r_{X_i X_j | Z}^{P_1} = r_{X_i X_j | Z}^{P_2}$ if and only if $Z$ diff-separates $X_i$ from $X_j$ .
- Robustness: The authors argue that this approach avoids the pitfalls of traditional faithfulness (e.g., exact parameter cancellations) by focusing on the difference in coefficients. If a cancellation occurs in one environment but not the other, the difference graph correctly identifies the edge, whereas standard methods might erroneously remove it.
The LDiffPC Algorithm:
Building on these concepts, the paper proposes LDiffPC (Linear Difference PC), a PC-style algorithm for recovering difference graphs.
- Mechanism: Instead of testing for conditional independence, LDiffPC performs equality tests of regression coefficients across the two environments.
- Skeleton Recovery: The algorithm starts with a fully connected undirected graph and iteratively removes edges $X_i - X_j$ if there exists a conditioning set $Z$ such that the regression coefficients are statistically equal ( $r_{X_i X_j | Z}^{P_1} = r_{X_i X_j | Z}^{P_2}$ ).
- Orientation: It identifies v-structures and applies Meek's rules to orient edges, similar to the standard PC algorithm.
- Adaptation: The authors note that the standard PC algorithm's strategy of restricting conditioning sets to adjacent nodes is insufficient for difference graphs. LDiffPC employs a sequential conditioning strategy (increasing set size) and utilizes separation sets to ensure the correct skeleton is recovered, even when intermediate nodes in a path are not adjacent in the difference graph.

Results and Theoretical Guarantees
The paper provides theoretical proofs establishing the soundness and completeness of the proposed method under the stated assumptions:

Lemma 1 & 2: Under the diff-faithfulness assumption, the skeleton of the true difference graph is identifiable via equality tests of regression coefficients, and v-structures can be correctly identified.
Theorem 1: The LDiffPC algorithm correctly recovers the true partially directed difference graph (including the skeleton, v-structures, and orientations implied by Meek's rules) given access to perfect conditional equality information.
Statistical Implementation: The paper outlines a practical implementation using a permutation test to assess the significance of differences in regression coefficients, though it also acknowledges the use of F-tests as an alternative.

Significance and Claims
The authors claim that this work fills a critical gap in causal discovery by providing a constraint-based framework specifically for difference graphs.

Theoretical Contribution: It establishes the first graphical criterion (diff-separation) that explains when statistical equality of regression coefficients implies causal invariance, moving beyond standard d-separation.
Practical Utility: By avoiding the need to reconstruct full causal graphs for each environment and by relaxing the strict faithfulness assumption regarding parameter cancellations, LDiffPC offers a more robust tool for identifying causal changes.
Scope: The method is designed for linear SCMs and assumes causal sufficiency (no latent confounders) and a shared topological ordering across environments.
Future Directions: The paper modestly suggests that future work could explore relaxing the topological ordering constraint and incorporating latent variables (analogous to the FCI algorithm) adapted for difference graph inference.

In summary, the paper presents LDiffPC as a principled, theoretically grounded method for detecting causal mechanism changes in linear systems, leveraging regression coefficient equality tests and a novel graphical separation criterion to overcome limitations of existing approaches.