Characterization and Greedy Learning of Gaussian Structural Causal Models under Unknown Interventions

arXiv:2211.14897 · stat.ME, stat.CO, stat.ML · Submitted 2022-11-27 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Characterization and Greedy Learning of Gaussian Structural Causal Models under Unknown Interventions".

Jane: Here's the gist of the paper. The paper addresses the problem of recovering the causal structure underlying observations from different experimental conditions when intervention targets are unknown, assuming a linear structural causal model with additive Gaussian noise.

Tom: Different models can yield the same distributions, leading to competing causal explanations.

Jane: The authors fully characterize this equivalence class and provide identifiability results used to derive a greedy algorithm called GnIES for recovering the equivalence class of the data-generating model without knowing intervention targets.

Tom: Furthermore, they develop a novel procedure to generate semi-synthetic datasets with known causal ground truth but distributions closely resembling real data.

Title and authors: Tom: So we're looking at this paper, "Characterization and Greedy Learning of Gaussian Structural Causal Models under Unknown Interventions," and the main thing here is they're tackling that messy problem where you see the same data from different experiments but you don't know what exactly was changed in each experiment.

Jane: Right, it’s about recovering the causal structure when we only have observations from different environments, and those intervention targets are unknown. The core idea is that even if two different causal models produce the exact same data distribution, they could be totally different explanations for what we see.

Tom: Exactly. They fully characterize this set of models that give the same distributions and then use those conditions to build this greedy algorithm called GnIES to find an estimate of that equivalence class without knowing which intervention happened where.

Lu: What's interesting is the mathematical machinery they develop, specifically how they characterize these equivalent models using matrix expressions involving inverses and covariance matrices, like Definition one in their paper <ref:2211.14897#pg1>. They establish some strong identifiability results based on faithfulness and two specific assumptions.

Meng: So, if we take that characterization—this equivalence class—and apply it to finding the best causal graph, the theorem they prove states that you can find the minimum norm graph within this set using a greedy search approach. That sounds like something practical for model selection.

Jane: It’s not just theoretical characterization; they provide a concrete procedure, GnIES, which is score-based and has two nested greedy steps to search for both the model structure and the intervention targets simultaneously.

Tom: The algorithm uses a score function that balances how well the candidate graph explains the data in each environment against some penalty for complexity related to degrees of freedom. It’s all about finding a balance between fit and simplicity, you know?

Lu: The consistency proof they give shows that when you have infinite data, this greedy search converges to the true structure we are looking for, which is pretty strong evidence for the method. They're essentially showing that this greedy approach actually works in the limit under those assumptions.

Jane: But what about real-world application? They also introduce a way to generate semi-synthetic datasets that look really close to real biological or physical systems but have a known causal ground truth, which is super helpful for testing things out.

Meng: That data generation tool is a big plus because it means we can train and test GnIES on data that actually has the right answer, instead of just relying on synthetic setups that might be too idealized.

Tom: So, to summarize the improvements they suggest, it’s about making this framework more flexible—they want to extend the score function so it can handle interventions that modify the parental coefficients between environments rather than just perturbing targets directly.

Title and authors: Lu: And they also point out that this method is really useful for small sample settings because instead of relying on massive data, you can use gradient-based optimization on a continuous relaxation of the causal discovery problem to get results.

Jane: They also mention that the performance in these small sample scenarios can be competitive with other methods like generalized greedy search, suggesting that this score-based approach isn't just theoretical but has practical value when data is scarce.

Meng: From an engineering standpoint, what I care about is how much it costs to run this algorithm at scale. They’re aiming for a method that can be deployed without needing huge amounts of prior knowledge about the specific intervention targets we are testing.

Tom: And they explicitly state that by greedily adding or removing intervention targets based on how much they improve the regularized maximum likelihood score, you get an estimate of the true intervention set, which is a nice step toward understanding what’s happening in the system.

Jane: So, wrapping things up on this paper about "Characterization and Greedy Learning of Gaussian Structural Causal Models under Unknown Interventions," it essentially gives us a rigorous way to find the causal structure when we only see data from different experimental conditions without knowing the intervention targets beforehand.

Lu: It moves beyond just finding *a* model that fits; it helps you identify the entire equivalence class of models that explain your observations, which is a much deeper understanding of what's happening under those conditions.

Meng: For deployment, the main promise is a robust method for causal discovery in environments where you don't have perfect knowledge of the experimental setup, which is something we run into constantly when building complex systems.

Tom: It seems like they’ve put together a solid piece that bridges the gap between theoretical identification results and a practical greedy search algorithm to tackle this ambiguity in causal modeling.

Jane: It’s definitely interesting because it gives us a tool to untangle competing explanations when our data comes from multiple, slightly different experimental setups.

Lu: The real contribution is showing that identifiability *is* possible under certain assumptions, which was a key hurdle in this area for causal learning literature.

Meng: I just wonder how robust this performance stays when we move away from the strict linear Gaussian model they start with and into more complex noise structures.

Tom: That’s a fair question; the current proof relies heavily on those specific Gaussian assumptions, so testing its generalization is definitely the next step for anyone trying to use GnIES in a real production setting.

Jane: And it sets up the groundwork for future work by providing a solid, verifiable algorithm that can be tested on everything from synthetic data to real biological systems.

The paper's summary: Tom: So, to recap, this paper is about figuring out the causal structure of data when you don't know what interventions were applied in different experiments—they show how to find that whole family of possible structures without knowing the intervention targets first.

Jane: Right, so if you have several datasets from different conditions but you can't pinpoint exactly which variables were manipulated in each one, this method gives you a way to map out all the models that could possibly explain what you see.

Lu: The core idea they use is defining these equivalent models based on the means and covariance matrices, specifically using matrix expressions involving the inverse of something related to the graph structure. It’s like they're creating a mathematical fingerprint for each possible explanation.

Meng: And then, instead of just finding one graph that fits, they propose this greedy algorithm called GnIES. It uses a score function that tries to maximize how well the candidate graph explains the data while penalizing complexity related to the degrees of freedom.

Tom: That score function is clever because it balances fitting the observed data against keeping the model simple, and they've shown that this approach can actually work even when you only have a small amount of data.

Jane: They prove consistency in an infinite data limit, which means if you had a huge pile of observations, this greedy search process would eventually settle on the true structure within that equivalence class.

Lu: And they have these experimental results—synthetic and real biological systems—that show GnIES performs competitively with other methods, especially when samples are small. They also give you a way to create semi-synthetic data that looks very much like real stuff but has a known causal truth.

Meng: That data generation tool is useful because it lets us test the algorithm on things that aren't perfectly clean synthetic examples; it bridges the gap between idealized models and messy real experiments.

Tom: And they show how you can use this greedy process to estimate the actual intervention targets by seeing which ones improve that score function more, giving you an idea of what’s actually going on in the system.

Jane: So, it moves beyond just finding *a* model that fits your data and gives you a systematic way to explore the whole set of possible causal explanations under uncertainty about the experiments.

Lu: This is significant because it builds identifiability results from their modeling assumptions, which is a big step for causal learning in general.

Meng: For us at the startup level, being able to get a competitive result with small samples using a score-based approach instead of just relying on massive data sets is actually pretty practical for production deployment.

Jane: So what this means for you listening right now is that if your experiment setup is complex and you're missing information about the exact interventions, this paper gives you a structured, greedy algorithm to systematically explore the most plausible causal explanations without having to guess those targets upfront.

The paper's improvements: Tom: So, moving beyond just the main algorithm, they suggest ways to make this framework even more useful in practice. They want to adapt that score function so it can handle a broader range of interventions, not just simple target changes but also things that modify how variables interact between different environments.

Jane: That's helpful because it means we can apply this method to real-world scenarios where the intervention isn't just about changing a single variable, but about changing the relationship between two things in one environment compared to another.

Lu: And they also look at improving how you find those intervention targets themselves. They show that you can estimate the true set of interventions by greedily adding or removing them based on how much that changes your score function score.

Meng: That ability to estimate the intervention set directly is a big deal for deployment because it gives you an actionable output—a list of what was likely changed—instead of just a model structure that's hard to interpret.

Tom: It sounds like they're trying to make the process more interactive, where the algorithm actively searches for what happened in those experiments while simultaneously refining the causal graph.

Jane: It really changes how we think about causal discovery when we have multiple datasets; instead of just picking one model and sticking with it, you're exploring a whole landscape of possibilities guided by data fitting.

Lu: The paper hints that this structure could be generalized to other models, not just Gaussian ones, if you can adapt the way the score function works to account for different types of noise or relationships.

Meng: If it works for more than just linear Gaussian stuff, that opens up a lot more use cases because real biological or physical systems aren't always perfectly linear and Gaussian.

Tom: It’s about making this a more flexible tool, not just a niche method for Gaussian models; they want to see how robust the core idea is when you introduce more noise complexity.

Jane: So, what this suggests is that the underlying concept—using matrix properties to define equivalent models—is really strong, and it’s about extending that logic into more complex domains.

Lu: They are setting up a path for future work by showing how to handle those modifications to the intervention structure in a way that respects the mathematical constraints of Gaussian noise.

Meng: For me, I'm interested in the runtime; if we can't run this fast enough at scale, it doesn't matter how good the theoretical framework is.

Tom: And they are trying to keep things efficient by using a greedy search approach instead of something that might require an exponential amount of computation to check every single possibility.

Jane: So, the direction for this research seems to be taking this powerful structure-finding idea and making it adaptable enough to tackle more intricate experimental designs and noise levels.

Conclusion: Tom: So we're wrapping up on this paper about "Characterization and Greedy Learning of Gaussian Structural Causal Models under Unknown Interventions." Essentially, they give us a mathematical way to find the entire family of possible causal models that could explain our data when we don't know what interventions were applied.

Jane: Right, so the big picture is that even if two different experimental setups look identical from just the output data, they might have totally different underlying causes, and this method helps us map out all those possibilities.

Lu: They’re showing how to use identifiability conditions—those specific matrix rules involving the inverse of the adjacency matrix and the covariance matrices for each environment—to define exactly which models are equivalent.

Meng: And then they build this GnIES algorithm, which is a greedy search that systematically explores that whole family of possibilities without needing to know what we're looking for in advance.

Tom: The results show it works well even when the data sample size is small, and it performs better than some other greedy methods because of those extra identifiability checks they included.

Jane: It’s a practical tool because they also give you a way to generate semi-synthetic data that looks like real biological systems but has a known true causal structure, which is great for testing the method.

Lu: The paper proves that this greedy process converges to the true model in the infinite data limit, which is solid mathematical grounding for using it as a discovery tool.

Meng: For deployment, if we can reliably use this to estimate intervention targets by watching how the score function changes, that’s a huge step toward building systems that can figure out what was done during testing.

Tom: It’s about moving from just finding one "good enough" model to understanding the entire space of plausible models and figuring out which one is best.

Jane: This research shows that identifiability isn't just a theoretical concept; it’s something we can use as a guide to find hidden causal information in experimental data.

Lu: The real implication is providing a constructive algorithm, GnIES, that leverages these mathematical constraints to achieve this discovery under uncertainty.

Meng: It means we can build more robust tools for analyzing complex systems where the exact setup of an experiment isn't perfectly documented.

Tom: So, this paper lays out a solid framework for handling ambiguity in causal modeling with unknown interventions by focusing on characterization and greedy learning.

Jane: It’s a really concrete method that helps us untangle competing explanations when our data comes from different experimental conditions without knowing the intervention targets beforehand.

Lu: I think what this suggests is that we can use these structural constraints to guide representation learning in a way that respects the causal reality of our data collection process.

Meng: If this approach scales well, it could be useful for production systems where you need to rapidly understand what changed when you run an automated test or experiment.

Tom: It’s a strong piece because they provide both the theory and a working algorithm that actually shows good performance on real-world systems.

Jane: This kind of work really pushes us to think about how we design experiments themselves, knowing that the interpretation of the data depends heavily on those unknown interventions.

Lu: Next time we look at papers, I want to see more work that tackles these identification constraints in even more complex non-linear settings.

Meng: And honestly, I want to see faster ways to run this score function optimization when we're dealing with massive datasets from industrial sensors or things like dynamic network models.

Tom: Yeah, and I'm curious if they can show how this method handles noise that isn't just simple Gaussian noise, because real biology is rarely perfectly clean.

Jane: That’s the next big question for this area, seeing if these structural ideas hold up when we move into more realistic experimental challenges.

Juan L Gamella, Armeen Taeb, Christina Heinze-Deml, Peter Bühlmann

ETH Zurich · University of Washington

stat.ME, stat.CO, stat.ML

Submitted: 2022-11-27

Updated: 2025-03-12

Comments: 60 pages, 13 figures

Journal ref: Journal of Machine Learning Research 27(207):1-64, 2026

Code: https://github.com/juangamella/gnies-paper

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 99/100

The gist: The paper addresses the problem of recovering the causal structure underlying observations from different experimental conditions when intervention targets are unknown…

Key concepts

Structural Causal Model (SCM)
This is a mathematical framework describing how variables influence each other. In this paper, it assumes a linear structure where observed variables ($X_e$) are determined by their parents ($B X_e$) plus some noise ($\epsilon_e$). The goal is to determine the causal relationships (the matrix $B$) among these variables.
Distribution Equivalence Class
Different causal graphs (models) can sometimes produce the exact same set of observed data distributions. This paper focuses on characterizing this set—the equivalence class. It defines specific mathematical conditions on mean and covariance matrices that must be met for two models to be considered equivalent, allowing the algorithm to search within this space.
GnIES Algorithm
GnIES is a score-based, greedy algorithm designed to find the true causal structure without knowing which variables were intervened upon. It uses a nested greedy approach: an inner loop searches for model equivalence classes, and an outer loop greedily selects intervention targets based on how much they improve a specific score function.
Intervention Target ($I$)
An intervention target is a variable that has been manipulated or treated in the experimental setup. The paper aims to recover the set of these targets ($I$) even when their exact identity is unknown, by using the distributional differences across various experimental environments to infer which variables were affected.

Terminology

Summary

The paper addresses the problem of recovering the causal structure underlying observations from different experimental conditions when intervention targets are unknown, assuming a linear structural causal model with additive Gaussian noise. p. 0

Where the paper says it

ch Abstract We consider the problem of recovering the causal structure underlying observations from different experimental conditions when the targets of the interventions in each experiment are unknown. We assume a linear structural causal model with additive Gaussian noise and consider interventions that perturb their targets while maintaining the causal relationships in the system.

Different models can yield the same distributions, leading to competing causal explanations. p. 0
Where the paper says it

We assume a linear structural causal model with additive Gaussian noise and consider interventions that perturb their targets while maintaining the causal relationships in the system. Different models may entail the same distributions, offering competing causal explanations for the given observations.

The authors fully characterize this equivalence class and provide identifiability results used to derive a greedy algorithm called GnIES for recovering the equivalence class of the data-generating model without knowing intervention targets. p. 0
Where the paper says it

Different models may entail the same distributions, offering competing causal explanations for the given observations. We fully characterize this equivalence class and offer identifiability results, which we use to derive a greedy algorithm called GnIES to recover the equivalence class of the data-generating model without knowledge of the intervention targets.

Furthermore, they develop a novel procedure to generate semi-synthetic datasets with known causal ground truth but distributions closely resembling real data. p. 0
Where the paper says it

We fully characterize this equivalence class and offer identifiability results, which we use to derive a greedy algorithm called GnIES to recover the equivalence class of the data-generating model without knowledge of the intervention targets. In addition, we develop a novel procedure to generate semi-synthetic data sets with known causal ground truth but distributions closely resembling those of a real data set of choice.

GnIES is evaluated on synthetic and semi-synthetic data, as well as real biological and controlled physical systems. p. 0
Where the paper says it

In addition, we develop a novel procedure to generate semi-synthetic data sets with known causal ground truth but distributions closely resembling those of a real data set of choice. We leverage this procedure and evaluate the performance of GnIES on an array of synthetic and semi-synthetic data sets, and real data from a biological system and a tightly controlled physical system.

The underlying model is defined by observing variables under different environments E via the form X e = B X e + epsilon e, where B is the adjacency matrix of a directed acyclic graph (DAG), and epsilon e are independent noise terms across environments. p. 3

Where the paper says it

We denote the resulting collection of distributions as {P e}e∈E . We model these distributions via a parametric model of the form Xe = BXe + ϵ e ∀e ∈ E, (1) where: i) B ∈ R p×p corresponds to the adjacency matrix of a directed acyclic graph (DAG), that is, it has zeros on the diagonal and is lower triangular up to a permutation of rows and columns.

A variable X i has received an intervention if its noise distribution differs across at least two environments. p. 3
Where the paper says it

The effect of interventions is modeled by allowing the distributions of the noise terms to change across environments. We say that variable Xi has received an intervention if ϵ e i ̸ d = ϵ f i for some e, f ∈ E, that is, if the distribution of its noise term is different for at least two environments.

Distribution equivalent models are characterized by conditions on the mean and covariance matrices, specifically Definition 1, which requires equality of certain matrix expressions involving (I - B)-1 and omega e. p. 3
Where the paper says it

Since the distribution over the observed variables is Gaussian, it suffices for two models to entail distributions with the same mean and covariance. Together with (2) we arrive at the following definition: 4

A key graphical characterization is provided in Lemma 1: I-MEC(G(B)) G(B, sigma e), where sigma e is the covariance matrix entailed by the model for environment e. p. 9

Where the paper says it

, hidden confounders. The interventions they consider include those in our model class, and for the case where causal sufficiency is satisfied, the authors provide a graphical characterization which directly applies to our setting (Lemma 3).

Theorem 1 establishes a crucial result: under faithfulness and Assumptions 1 and 2, I-MEC(G(B)) = G in G(B, sigma e) |G| 0.

The proposed greedy algorithm is GnIES, which is score-based and consists of two nested greedy procedures: an inner procedure searching over the space of I-equivalence classes using a modified GES algorithm, and an outer procedure greedily searching the space of intervention targets. p. 2

Where the paper says it

Yet, our model in Section 2 is still much more flexible than the ones for observational data only (Chickering, 2002; van de Geer and B¨uhlmann, 2013) or when interventions have known targets (Hauser and B¨uhlmann, 2012, 2015; Wang et al. Our proposed algorithm GnIES can be seen as an extension of the celebrated greedy equivalence search (GES) of the penalized maximum likelihood estimator for observational data (Chickering, 2002) to the setting of interventional data with unknown intervention targets.

The score function S(G, I) is defined as S(G, I) = B about G diag(pos def. p. 7
Where the paper says it

Gamella, Taeb, Heinze-Deml and Buhlmann ¨ We conjecture that this technical assumption directly holds as a consequence of faithfulness and the modeling assumptions. A violation would imply that, given some conditioning set, the conditional variance of a variable is not a function of the variance of its noise term.

epsilon e) e in E X e P(X e; B, omega e) - lambda D DoF(G, I). Consistency of GnIES is proven in the infinite data limit under faithfulness and Assumptions 1 and 2, showing that maximizers of G S(G, I) converge to I-MEC(G). p. 6
Where the paper says it

Then, I−MEC (G(B)) ⊆ G (B, {Ω e }e∈E ). If we additionally assume faithfulness for the data-generating model, its graph G(B) has the minimal number of edges2 and the I-equivalence class is a subset of the sparsest graphs in G (B, {Ω e}e∈E ): Proposition 1 Consider a model B, {Ω e}e∈E resulting in a set of distributions which are faithful with respect to its underlying graph G(B).

Experimental results demonstrate that GnIES performs competitively with other algorithms, especially when samples are small. p. 2

Where the paper says it

In Section 5 we evaluate the performance of the algorithm on synthetic and real data sets. The results show that despite the strong distributional assumptions (linearity and normality), GnIES is robust to an array of model violations, and is competitive in recovering the causal structure in small-sample settings.

It recovers the true equivalence class in the synthetic data setting better than GES due to additional identifiability. p. 0
Where the paper says it

We fully characterize this equivalence class and offer identifiability results, which we use to derive a greedy algorithm called GnIES to recover the equivalence class of the data-generating model without knowledge of the intervention targets. In addition, we develop a novel procedure to generate semi-synthetic data sets with known causal ground truth but distributions closely resembling those of a real data set of choice.

Performance is robust across synthetic and real biological/physical systems. p. 0
Where the paper says it

In addition, we develop a novel procedure to generate semi-synthetic data sets with known causal ground truth but distributions closely resembling those of a real data set of choice. We leverage this procedure and evaluate the performance of GnIES on an array of synthetic and semi-synthetic data sets, and real data from a biological system and a tightly controlled physical system.

The procedure for generating semi-synthetic data sets is available via the simpler package. p. 0
Where the paper says it

We fully characterize this equivalence class and offer identifiability results, which we use to derive a greedy algorithm called GnIES to recover the equivalence class of the data-generating model without knowledge of the intervention targets. In addition, we develop a novel procedure to generate semi-synthetic data sets with known causal ground truth but distributions closely resembling those of a real data set of choice.

The software contributions include gnies (the GnIES algorithm), ges (a pure Python implementation of the GES algorithm), gies (an implementation of GIES from Hauser and Bühlmann, 2012), and sempler (for data generation). The core contribution is GnIES, which recovers the true equivalence class of Gaussian Causal Models under unknown intervention targets by leveraging identifiability results derived from modeling assumptions. p. 0

Where the paper says it

Different models may entail the same distributions, offering competing causal explanations for the given observations. We fully characterize this equivalence class and offer identifiability results, which we use to derive a greedy algorithm called GnIES to recover the equivalence class of the data-generating model without knowledge of the intervention targets.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Greedy noise-interventional equivalence search (GnIES) can recover causal structures from interventional data with unknown intervention targets by searching over a space of distributional equivalence classes, providing an estimate of the true model class without knowing intervention targets.

  2. The GnIES algorithm can be extended to more general models by adapting its score function, allowing it to handle interventions that modify the parental coefficients of a target between environments.

  3. The system can perform robust causal discovery in small-sample settings by leveraging the score-based optimization approach, which is competitive with other methods and shows better performance than generalized greedy search (GES).

  4. The system can estimate intervention targets by greedily adding or removing them based on how much they improve the regularized maximum likelihood score, leading to an estimate of the true intervention set I star.

Abstract

We consider the problem of recovering the causal structure underlying observations from different experimental conditions when the targets of the interventions in each experiment are unknown. We assume a linear structural causal model with additive Gaussian noise and consider interventions that perturb their targets while maintaining the causal relationships in the system. Different models may entail the same distributions, offering competing causal explanations for the given observations. We fully characterize this equivalence class and offer identifiability results, which we use to derive a greedy algorithm called GnIES to recover the equivalence class of the data-generating model without knowledge of the intervention targets. In addition, we develop a novel procedure to generate semi-synthetic data sets with known causal ground truth but distributions closely resembling those of a real data set of choice. We leverage this procedure and evaluate the performance of GnIES on an array of synthetic and semi-synthetic data sets, and real data from a biological system and a tightly controlled physical system. We provide, in the Python packages gnies and sempler, implementations of GnIES and our semi-synthetic data generation procedure.

Sources

Related papers