📊 statistics

Falsifying Causal Graphs With Outlier Events

This paper proposes a novel method to falsify candidate causal graphs by testing whether they can explain the propagation of outlier events based on the principle that weak outliers rarely cause strong ones, offering the first statistical tests with false positive control and power guarantees that can operate with a single outlier sample.

Original authors: William Roy Orchard, Philipp M. Faller, Dominik Janzing

Published 2026-07-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: William Roy Orchard, Philipp M. Faller, Dominik Janzing

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 in a giant, invisible factory. You have a map (a "causal graph") that claims to show how every machine in the factory is connected. Machine A turns on Machine B, which turns on Machine C, and so on. But here's the catch: you don't know if your map is actually right. Maybe Machine A actually turns on Machine D, and your map is just a guess.

Usually, to check if a map is right, you need to see the whole factory running perfectly for a long time. But what if you only have one single snapshot of a weird, chaotic moment? What if, just for a second, a spark flew from Machine A, causing a massive explosion in Machine C?

This paper proposes a clever new way to check your map using that single, chaotic moment. The authors call it "falsifying" the graph, which is a fancy way of saying "proving the map is wrong."

The Golden Rule: Weak Sparks Don't Make Big Explosions

The whole idea rests on one simple, common-sense principle: A weak spark rarely causes a massive explosion.

In the language of the paper, if a small "outlier" (a tiny glitch) happens at the start, it usually stays small as it travels through the factory. If your map says a tiny glitch at the beginning somehow caused a huge, screaming explosion at the end, your map is likely lying.

The authors realized that while scientists usually use this rule to find the root cause of a problem, they can flip it around to test the map itself. If the map predicts that a small glitch should cause a huge one, but the data shows a small glitch causing a small one (or a huge glitch appearing out of nowhere), the map fails the test.

The "Score" System

To make this math work, the authors invented a "score" for every machine.

Marginal Score: How weird is this machine's behavior on its own?
Conditional Score: How weird is this machine's behavior given what its parent machines are doing?

Think of it like a game of "Telephone." If the person at the start whispers a quiet secret (a low score), and the person at the end is screaming (a high score), the game is broken. The paper shows that if your map is correct, the "weirdness" score should generally get smaller or stay the same as it travels down the line. It shouldn't magically jump up.

The Big Test: One Sample is Enough

Here is the most exciting part: You only need one weird event to catch a liar.

Usually, statisticians say, "We need a thousand samples to be sure." But the authors proved that if you have a single sample where a "root cause" (the start of the glitch) is known, you can run a statistical test to see if the map holds up.

They created four different ways to run this test (like four different detective tools):

The Sum Test: Add up all the weirdness scores. If the total is too high, the map is wrong.
The Max Test: Look for the single biggest jump in weirdness. If one jump is too huge, the map is wrong.
The Count Test: Count how many jumps are bigger than a certain limit. If there are too many, the map is wrong.
The Shape Test: Look at the whole pattern of scores. If the pattern doesn't look like what a correct map should produce, the map is wrong.

What They Found (and What They Didn't)

The authors ran these tests on two types of data:

Fake Data (Simulations): They built 200 fake factories with 20 machines each. They knew the real map and then tried to trick the tests with fake maps that had some wrong connections.
- The Result: The tests were great at catching the fake maps. If the fake map had even a few wrong connections, the tests usually said, "Nope, this map is a liar!"
- The Catch: The tests work best when the "glitch" is strong. If the glitch is tiny, it's harder to tell if the map is wrong. Also, the tests work best on maps that look like trees (where branches don't loop back on themselves).
Real Data: They tried this on real-world data from a cloud computing system (PetShop) and a physics experiment (Causal Chambers).
- PetShop: They tested a map based on how the software services talk to each other. The tests rejected this map as the "true" cause for many of the glitches, suggesting the real cause-and-effect is different from the software dependency list.
- Causal Chambers: They tested a map of light measurements. The tests didn't reject this map, which suggests the map is actually pretty accurate.

What the Paper Rules Out

The paper is very careful about what it doesn't do:

It does not say you can always find the perfect map. It only says you can prove a map is wrong.
It does not work if you don't know where the glitch started (the root cause). If you don't know the start, you can't run the test (unless you try every possible start, which is slow).
It does not claim to be better than every other method in every situation. For example, if you have a huge amount of data, other methods might be better. This method shines when you have only one weird event.

The Verdict

The paper suggests that by looking at how "weirdness" travels through a system, we can catch bad maps with just a single snapshot of chaos. It's like checking if a story makes sense by seeing if a whisper turns into a shout in the middle of the sentence. If the story says it does, but physics says it shouldn't, the story is fake.

The authors proved mathematically that their tests won't cry "Liar!" when the map is actually right (they control the false alarms), and they showed through simulations that they are good at catching lies. But remember, this is a tool for falsifying (proving wrong), not for finding the perfect truth from scratch. It's a lie detector for causal maps, and it works even when you only have one chance to catch the culprit.

Technical Summary: Falsifying Causal Graphs With Outlier Events

Problem Statement

True causal relationships are rarely known a priori, and inferring causal graphs from data remains a challenging task. A fundamental difficulty lies in assessing the validity of a given candidate causal graph in the absence of ground truth. While previous methods have utilized interventional data or consistency checks across variable subsets, these often require multiple samples, access to conditional independence oracles, or assume specific parametric forms. In practical settings such as cloud monitoring or manufacturing, it is often prohibitively expensive or impossible to gather multiple samples of rare anomalous events. Furthermore, existing methods for falsifying causal models using observational data often lack valid statistical tests with controlled false positive rates.

This work addresses the problem of falsifying a candidate causal graph using a single outlier sample. The goal is to test the null hypothesis $H_0: \hat{G} = G$ , where $\hat{G}$ is an estimated causal graph and $G$ is the true causal graph, by leveraging the propagation characteristics of outlier events.

Methodology

The proposed approach is grounded in the principle that weak outliers rarely cause strong outliers. This principle, previously utilized in root cause analysis to identify causes without prior graph knowledge, is inverted here to falsify graphs: if a candidate graph implies an outlier propagation pattern inconsistent with this principle, the graph is rejected.

Core Concepts

Outlier Modeling: Outliers are modeled as the result of a "soft-intervention" on a subset of root cause variables $R$ . The distribution of an outlier sample is a "corrupted" version of the true distribution where the mechanisms for variables in $R$ are altered.
Information-Theoretic (IT) Outlier Scores: The method utilizes IT outlier scores defined as $S(x) = -\log P(\text{event})$ $S (x) = - lo g P (event)$ .
- Marginal Scores: $S(x_i) = -\log P(\tau_i(X_i) \geq \tau_i(x_i))$ .
- Conditional Scores: $S(x_i | pa_i) = -\log P(\tau_i(X_i) \geq \tau_i(x_i) | PA_i = pa_i)$ .
  Under the null hypothesis that the graph is correct and the sample is drawn from the ordinary mechanism (excluding root causes), these scores follow an independent standard exponential distribution, $\text{Exp}(1)$ .

Statistical Tests

The authors propose four statistical tests based on these scores to reject $H_0$ . The tests are designed to have false positive control (valid p-values) and power guarantees against specific classes of incorrect graphs.

1. Conditional Score Tests (Assuming Root Causes Known)

When the root causes $R$ are known and the graph is a Directed Acyclic Graph (DAG), the conditional scores of non-root variables are independent $\text{Exp}(1)$ variables under $H_0$ . The paper proposes:

Fisher-based Test: Sums the conditional scores ( $S_{sum}$ ). The p-value is derived from the Erlang distribution (sum of exponentials).
Tippett-based Test: Uses the maximum conditional score ( $S_{max}$ ). The p-value is derived from the distribution of the maximum of exponentials.
Binomial Test: Counts the number of scores exceeding a threshold $t$ ( $N_t$ ). The p-value follows a Binomial distribution.
Kolmogorov-Smirnov (KS) Test: Compares the empirical CDF of the scores against the theoretical $\text{Exp}(1)$ CDF ( $D_L$ ).

2. Marginal Score Tests (Polytree Assumption)

Inferring conditional distributions is statistically ill-posed with limited data. The authors adapt the first three tests to use only marginal scores, provided the true graph is a polytree (a DAG with no undirected cycles).

Score Typicality: The method relies on the condition $S(y|x) \geq |S(y) - S(x)|_+$ . When satisfied, it implies that a weak outlier rarely causes a strong one.
Test Statistics: The marginal tests use the "jump" in scores: $|S(x_i) - S(PA_i)|_+$ .
Validity: Under the polytree assumption and score typicality, these marginal statistics are stochastically dominated by their conditional counterparts, ensuring valid p-values.

3. Unknown Root Causes

If the root causes are unknown but an upper bound $k$ on their number is known, the authors propose a maximum leave- $k$ -out procedure. The test statistic is computed for every subset of $k$ variables treated as potential root causes, and the maximum p-value is taken. This controls the false positive rate without introducing selection bias.

Theoretical Guarantees

False Positive Control: The tests provide rigorous p-values, ensuring $P(\text{reject } H_0 | H_0 \text{ is true}) \leq \alpha$ .
Power Guarantees: The paper derives lower bounds on the rate of decay of outlier scores along causal paths using the Strong Data Processing Inequality (SDPI).
- If a true descendant of a root cause is assigned incorrect parents (e.g., non-descendants or parents further from the root), the resulting "score jump" is lower-bounded.
- The power of the tests increases with the strength of the outlier ( $\lambda$ ) and the proportion of incorrect edges ( $\pi$ ).
- Specific optimality results (Uniformly Most Powerful) are shown for the sum test (Fisher) against global shifts in rate parameters and the max test (Tippett) against single dominant outliers.

Experimental Results

The authors evaluated their methods on both synthetic and real-world datasets, comparing them against baselines including a permutation-based test (Eulig et al., 2025) and a causal discovery algorithm (GRaSP).

Synthetic Data

Setup: Random DAGs with 20 nodes. Outliers were injected into a random root cause and propagated. The "ground truth" graph was partially corrupted to create test graphs with varying fractions of correct edges ( $|K|/|N|$ ).
Findings:
- The proposed tests showed increasing rejection rates as the fraction of incorrect edges increased.
- Conditional score tests generally outperformed marginal score tests, as expected.
- The GRaSP baseline was overly sensitive, rejecting almost all graphs (including the ground truth) due to finite-sample discrepancies.
- The permutation baseline behaved as expected, rejecting graphs only when they were worse than random.
- Power increased with stronger injected anomalies and when multiple outlier samples were available.

Real-World Data

PetShop Dataset (Cloud Computing): The study tested a "service dependency map" (with edges reversed) as a proxy for the causal graph.
- Result: The proposed tests rejected this graph at a rate significantly higher than the significance level, particularly in high-traffic scenarios. This suggests the service map, while better than random, is not the true causal graph.
Causal Chambers Dataset: A physical testbed with a known accurate causal structure.
- Result: The tests rejected the graph at a rate consistent with the significance level (i.e., they did not falsely reject the correct graph), validating the false positive control.

Significance and Claims

The paper claims to present the first statistical tests for the null hypothesis that a given causal graph is the true causal graph that satisfy three specific criteria:

False Positive Control: They provide valid p-values, ensuring the rate of false rejections is bounded.
Power Guarantees: They have proven power against a broad class of incorrect causal graphs, specifically those where the propagation of outliers violates the "weak-to-strong" principle.
Single Sample Operation: They can operate effectively with only a single outlier sample, a critical feature for domains where anomalous events are rare and expensive to observe.

The authors emphasize that this work bridges the gap between root cause analysis literature and causal graph evaluation, turning the principle of outlier propagation into a rigorous falsification tool. The method does not require interventional data or multiple samples from the anomalous regime, making it applicable to scenarios where traditional causal discovery or falsification methods fail.