Falsifying Causal Graphs With Outlier Events

AI summary

Overview

Research area: Causal inference and causal discovery (stat.ML), specifically methods for evaluating and falsifying candidate causal graphs, drawing on information theory, hypothesis testing, and root cause analysis.

Technical level: Advanced. The paper is written for readers comfortable with Causal Bayesian Networks, information-theoretic outlier scores, hypothesis testing, and information-theoretic quantities such as KL divergence, the Strong Data Processing Inequality, and contraction coefficients.

Scope in one sentence: The paper introduces statistical tests that reject a candidate causal graph when the way an outlier event propagates through the system is inconsistent with the graph, with false positive control, power guarantees, and the ability to work from a single outlier sample.

What This Paper Is About

True causal relationships are rarely known, and learned or expert-provided causal graphs can be unreliable due to violated assumptions, incompleteness, or finite-sample issues. The core problem is how to assess a candidate causal graph when no ground truth is available. The authors' goal is to build formal statistical tests for the null hypothesis that a given candidate graph is the true causal graph, using the observed propagation of an outlier event as the source of evidence.

Key Contributions

1. First statistical tests for the "candidate graph is the true causal graph" hypothesis. The authors state that, as far as they are aware, these are the first statistical tests for this null hypothesis that simultaneously have (i) false positive control, (ii) power against a broad class of incorrect causal graphs, and (iii) the ability to operate with only a single outlier sample.

2. Four conditional-score tests with false positive control for DAGs. Using information-theoretic (IT) outlier scores, the paper derives a Fisher-based test (sum of conditional scores), a Tippett-based test (maximum conditional score), a binomial test (count of scores above a threshold), and a Kolmogorov-Smirnov test comparing the empirical CDF of conditional scores to the standard exponential CDF.

3. Marginal-score adaptations with false positive control for polytrees. Because estimating conditional distributions given many parents is statistically ill-posed, the first three tests are re-derived using only marginal outlier scores, with false positive control established under the assumption that the true graph is a polytree.

4. Power guarantees via outlier decay rates. The authors derive lower bounds on the rate at which outlier scores decay along causal paths, using the Strong Data Processing Inequality and contraction coefficients, and use these to characterize the specific graph errors against which the tests have power.

Main Findings

• Outliers are modeled as soft interventions. An outlier sample is generated by replacing the causal mechanisms of a set of "root cause" variables R with corrupted mechanisms, while all other variables follow their ordinary conditional distributions. The paper notes that a root cause need not be a root node in the graph.

• Conditional IT outlier scores are independent standard exponentials under the null. Lemma 1 shows that, subject to a continuity assumption, the conditional outlier scores S(X_i | PA_i) are independent Exp(1) random variables. This is the property that underpins the conditional-score tests.

• Fisher-based test. The test statistic is the sum of conditional outlier scores over the non-root causes, denoted S_sum. The p-value is p = e^(−S_sum) · Σ_{l=0}^{L−1} (S_sum)^l / l!, where L := n − |R| is the number of non-root cause variables. This corresponds to Fisher's method for combining independent p-values.

• Tippett-based test. The test statistic is the maximum conditional outlier score S_max, with p-value p = 1 − (1 − e^(−S_max))^L. This corresponds to Tippett's method.

• Binomial test on scores above a threshold. Counting the non-root causes whose conditional score exceeds a threshold t, N_t, gives the p-value p = Σ_{k=N_t}^{L} C(L,k) e^(−kt) (1 − e^(−t))^(L−k), the upper tail of a binomial distribution with success probability e^(−t).

• Kolmogorov-Smirnov test. The statistic D_L is the supremum distance between the empirical CDF of the non-root-cause conditional outlier scores and the standard exponential CDF; the p-value is p = 1 − K_L(D_L), where K_n is the null distribution function of the KS statistic for sample size n.

• Marginal-score analogues retain false positive control for polytrees. Under the polytree assumption (the skeleton contains no undirected cycles, so parents of a variable are independent), the marginal test statistics are S_sum-hat = Σ |S(X_i) − S(PA_i)|+, S_max-hat = max |S(X_i) − S(PA_i)|+, and N_t-hat counting those differences at or above t. Proposition 8 states that each marginal p-value is stochastically dominated by its conditional counterpart, so the corresponding quantities are valid p-values for H_0. The paper advises using anti-conservative conditional p-values whenever they are available.

• "Score typicality" formalizes the principle that weak outliers rarely cause strong ones. Definition 6 states that an observation (x, y) satisfies score typicality if S(y | x) ≥ |S(y) − S(x)|_+. Lemma 7 shows that, although typicality may fail for a particular x, for a randomly chosen x it holds approximately with probability at least 1 − 2/c, up to a slack of 2 log c.

• Outlier scores decay along causal paths. Lemma 12 shows that when an outlier is propagated by an intact mechanism, η S(x) ≥ S(y), where η is the contraction coefficient of the channel — i.e. the score decays by at least a factor of η. Lemma 11 establishes the link that makes this possible: the marginal outlier score equals a KL divergence, S(x) = D(P_{X|E_x} || P_X).

• Reversing an edge produces a detectable score jump. Lemma 13 gives the anti-causal score jump lower bound |S(x) − S(y)|_+ ≥ (1 − η) S(x).

• Two concrete classes of channels with η < 1. For the linear Gaussian model Y := βX + N with correlation coefficient ρ, η = ρ². For a bounded Gaussian additive noise model with |f(x)| ≤ B and N ~ N(0, σ²), η ≤ 2Φ(B/σ) − 1.

• Conditioning on a non-descendant of a root cause also inflates the conditional score. Under an "effectiveness" assumption (there exists λ > 0 such that every variable X_j among the descendants of the root causes in the true graph satisfies S(X_j) ≥ λ), Lemma 16 states that with probability at least 1 − 1/c, S(x_i | pa_i) ≥ λ − log c when the assigned parents are non-descendants of root causes.

• A monotonicity condition links marginal and conditional power. Lemma 14 shows that under a stated monotonicity property, S(x | y) ≥ |S(x) − S(y)|_+, so whenever the marginal-score tests have power, the conditional-score tests do too. Proposition 15 gives the additive log-concave noise model with non-decreasing f and strictly increasing S_X, S_Y as an example where this holds.

• Expected and high-probability conditional bounds under the anti-causal error. Lemma 17 gives E[S(x | Y)] ≥ (1 − η) S(x), and Lemma 18 gives a high-probability version with a variance-dependent slack involving V_x = Var[S(x | Y)]. Proposition 19 bounds V_x for bounded additive noise models, including a bound of (2 L_N B)² when the noise has a log-Lipschitz density (explicitly including the Cauchy, Laplace, Logistic and Student's t distributions) and a bound of 4B²/σ⁴ (B² + σ²) + 2B³/σ⁴ √(B² + σ²) + B⁴/(4σ⁴) for Gaussian noise N(0, σ²).

• Characterization of detectable errors. Remark 20 states the tests are sensitive to two kinds of errors in the candidate graph: (1) assigning a descendant of a root cause no parents, or parents that are not descendants of a root cause — the score jump is lower bounded by approximately λ; and (2) assigning a descendant of a root cause parents that are themselves descendants of the root cause — the lower bound is (1 − η_max) λ, where η_max is the maximum contraction coefficient over non-root-cause variables. The paper calls b := (1 − η_max) λ the lowest lower bound and introduces π, the fraction of non-root causes whose parents in the candidate graph are incorrect in either way.

• The known-root-cause assumption can be relaxed. The tests are stated assuming the root causes of the outlier event are known; the paper states that this assumption can be dropped when an upper bound on the number of root causes is known.

• A selection-bias caveat is stated. The paper notes the tests assume the outlier sample is not selected because it is anomalous and then also used for testing.

• Empirical results are not reported in the available content. Section 5 is described in the introduction as comparing the proposed methods to several baselines on synthetic and real-world data, but the provided text is truncated before Section 5, so no numbers, benchmark names, or dataset sizes from that evaluation are available here.

Methodology in Plain English

The authors start from a simple physical intuition: a small anomaly usually does not produce a huge anomaly downstream. If you measure how surprising each variable's value is — using an information-theoretic score equal to the negative log probability of an event at least as extreme as what was observed — that intuition becomes a mathematical statement about how scores behave as they travel along causal edges.

They then reverse the logic that root cause analysis uses. Instead of using the propagation pattern to find the cause, they treat the candidate causal graph as the hypothesis under test. If the graph were correct, then by the time the outlier reaches variables that are not root causes, their conditional outlier scores should look like draws from a known reference distribution (independent standard exponentials). If the graph misplaces causes and effects, the scores will be inflated instead. The authors build four different ways of turning those scores into a p-value — summing them (Fisher), taking the maximum (Tippett), counting how many exceed a threshold (binomial), and comparing their whole distribution to the reference (Kolmogorov-Smirnov).

Because conditional distributions given many parents are hard to estimate reliably, they also replace conditional scores with differences of marginal scores, which requires the true graph to be a polytree so that a variable's parents are independent. To show the tests are not just valid but useful, they then prove lower bounds on how large the score inflation will be when specific errors are made, using information-theoretic tools (KL divergence and the Strong Data Processing Inequality) to quantify how much an outlier decays as it propagates through an intact mechanism. These bounds convert directly into statements about which graph mistakes the tests can detect and how strong an outlier event must be for detection.

Why This Matters

Impact on research. Most causal discovery work focuses on producing a graph; this paper focuses on auditing one, and it does so with genuine statistical guarantees rather than heuristics. It also connects two previously separate literatures — root cause analysis and causal model falsification — by showing the propagation principle used to find causes can also be used to reject graphs. The use of the Strong Data Processing Inequality to bound outlier decay introduces a quantitative handle on propagation that may be useful beyond falsification.

Real-world applications.

• Cloud service monitoring, where the paper references root cause analysis for anomalous events in monitored cloud services [Hardt et al., 2024], and where collecting many samples of a rare failure can be prohibitively expensive.
• Manufacturing, where the paper cites root cause analysis of rare events [Göbler et al., 2024].
• Personalised medicine, where the paper notes it may not be possible to gather repeated samples from an anomalous event [Li et al., 2025].
• Any setting where a causal graph has been assembled from expert knowledge or learned from limited data, and its reliability is uncertain.

Industry relevance. The requirement of only a single outlier sample is the paper's most operationally significant property. In production systems, incidents are rare, and by the time a second example is collected the system may already have been changed. A test that can reject a suspected causal model from one event, without needing a conditional independence oracle or a large interventional dataset, is practical for incident review, model governance, and validating expert-authored dependency graphs.

Future Directions

• Dropping the polytree assumption for marginal scores. The paper requires the true graph to be a polytree to use only marginal scores, and explicitly points to Li et al. [2025] and Ebtekar et al. [2025] for why this is not straightforward to remove. Extending marginal-score tests to general DAGs is an open problem.
• Generalizing past a known upper bound on the number of root causes. The paper shows the known-root-cause assumption can be dropped given an upper bound on the number of root causes; whether tighter or assumption-free approaches exist is left open.
• Comparing the tests empirically under the conditions where each has power. The paper poses the question of when to prefer Fisher, Tippett, binomial, or KS, and defers to the power analysis in Section 4.5 and the empirical comparison in Section 5, which is not described in the available content.
• Characterizing additional detectable error types. Remark 20 covers two kinds of graph error; whether the tests have power against broader classes of misspecification — and how the contraction coefficient η and the effectiveness level λ behave in real systems — remains to be explored.

Target Audience

This paper is best suited to causal inference researchers working on causal discovery, model validation, and falsification; machine learning researchers interested in anomaly detection and root cause analysis who want formal guarantees; and information theorists interested in applications of the Strong Data Processing Inequality. It is also relevant to practitioners in cloud reliability, manufacturing quality, and personalised medicine who need to audit a causal or dependency model from a small number of anomalous events, provided they are comfortable with the statistical machinery being invoked.

Note: the supplied paper content is truncated partway through Proposition 21, so the empirical evaluation promised for Section 5 cannot be summarized here.

Authors’ abstract

True causal relationships are rarely known, and inferring causal graphs from data is hard. A fundamental challenge is how to assess whether a given causal graph is good in the absence of a ground truth. We propose falsifying candidate causal graphs based on whether they can explain the propagation of an outlier event. Our approach leverages a key principle: weak outliers rarely cause strong ones. While this principle has previously been used in root cause analysis to identify root causes without prior knowledge of the graph, we turn it on its head and use it to falsify candidate causal graphs whose implied outlier propagation is inconsistent with the data. To this end, we present the first statistical tests for the hypothesis that a candidate graph is the true causal graph, and show they have false positive control, power guarantees against incorrect causal graphs, and can operate with a single outlier sample.