Source-linked AI summary
Causal Discovery with Continuous Additive Noise Models
Jonas Peters, Joris Mooij, Dominik Janzing, Bernhard Schölkopf
TL;DR
The paper addresses recovery of causal DAGs from observational distributions, where the graph is useful for predicting interventions but is not directly observed. It uses additive-noise structural equation models to establish graph identifiability, develops RESIT and independence-score algorithms, and proves RESIT correct in the population setting. The main scope is restricted by additive-noise and related modeling assumptions, while RESIT does not scale well to many nodes or high-dimensional finite-sample independence testing.
Problem
The paper asks whether a causal DAG can be identified from an observational joint distribution rather than recovered only up to Markov equivalence.
Method
It exploits additive-noise structural equation models and develops RESIT plus two independence-score methods for finite samples.
Results
The paper establishes that additive-noise models can identify the causal graph under mild conditions and proves RESIT correct in the population setting.
Takeaways & Limitations
When the data-generating process fits a restricted additive-noise SEM, causal structure can be inferred from the joint distribution rather than only its Markov equivalence class.
Takeaways & Limitations
RESIT does not scale well to many nodes because finite-sample dependence testing between a variable and a vector is statistically difficult in high dimensions.
Abstract
from arXiv · showhide
We consider the problem of learning causal directed acyclic graphs from an observational joint distribution. One can use these graphs to predict the outcome of interventional experiments, from which data are often not available. We show that if the observational distribution follows a structural equation model with an additive noise structure, the directed acyclic graph becomes identifiable from the distribution under mild conditions. This constitutes an interesting alternative to traditional methods that assume faithfulness and identify only the Markov equivalence class of the graph, thus leaving some edges undirected. We provide practical algorithms for finitely many samples, RESIT (Regression with Subsequent Independence Test) and two methods based on an independence score. We prove that RESIT is correct in the population setting and provide an empirical evaluation.
1. Introduction
The paper asks whether a causal DAG can be recovered from an observational distribution and proposes structural-equation assumptions that can identify it beyond Markov equivalence. It frames causal graphs as useful for understanding data-generating processes, interventions, and counterfactual distinctions.
- Causal structure matters because it can reveal data-generating mechanisms and inform drug development, intervention prediction, and machine-learning tasks.
- The central problem is to infer a true acyclic causal graph G from the joint distribution L(X).
- Traditional graph-based assumptions generally recover only a Markov equivalence class, whereas additive-noise assumptions can generically identify the correct graph.
- The paper develops SEM-based identifiability results and practical finite-sample algorithms, including RESIT and independence-score methods, which are empirically tested.
- Causal minimality selects a unique true causal DAG when multiple true causal DAGs otherwise exist.
- The paper distinguishes observational and interventional information from counterfactual information, noting that different SEMs may agree on the former while disagreeing on counterfactuals.
2. Alternative Methods
The paper reviews independence-based, score-based, and non-Gaussian methods for causal graph estimation. These approaches face limits from Markov equivalence, difficult conditional-independence testing, restrictive assumptions, or specialized distributional structure.
- Independence-Based Methods: Independence-based methods such as PC and FCI distinguish graphs only up to Markov equivalence because they rely on conditional independences.
- Independence-Based Methods: Conditional-independence testing becomes difficult with large conditioning sets, and PC may require sets containing up to p −2 variables.
- Independence-Based Methods: Consistency of PC additionally requires strong faithfulness, which the paper describes as a restrictive condition.
- Score-Based Methods: Score-based methods assign scores to candidate DAGs and use greedy search over neighboring graphs because the DAG search space grows super-exponentially.
- LiNGAM: LiNGAM exploits non-Gaussian noise to make a linear SEM graph identifiable and provides an ICA-based method for finite samples.
- Equal-Variance Gaussian SEMs: Equal-variance Gaussian-noise SEMs can also identify the graph, but rescaling variables limits the practical applicability of this assumption.
3. Identifiability of Continuous Additive Noise Models
The paper restricts structural equation models to additive noise and shows that, under conditions such as causal minimality, the causal DAG can be identifiable from the joint distribution. The result extends from bivariate models to restricted multivariate models and supports broader identifiability principles.
- Additive noise assumptions: Additive noise models take the form Xj = fj(PAj) + Nj, with jointly independent noise variables and strictly positive noise densities.Causal minimality holds when each fj is non-constant in every parent argument.
- Exceptional non-identifiable cases: Linear Gaussian models are an exceptional non-identifiable case because they may identify only the Markov equivalence class, whereas non-Gaussian examples can also violate identifiability under special conditions.For Gaussian variables, failure of Condition 18 implies that the structural function is linear; a non-Gaussian counterexample is characterized by specific parameter constraints.
- Bivariate identifiability: Theorem 19 establishes bivariate DAG identifiability when the additive noise model satisfies Condition 18 and causal minimality.Identifiability excludes cases in which both forward and backward additive-noise explanations fit the same distribution.
- Multivariate identifiability: For multivariate models, the restricted additive noise conditions impose requirements across parent, nondescendant, and conditioning sets, together with non-vanishing noise densities and smooth structural functions.Theorem 27 then identifies the graph from the joint distribution under causal minimality.
- Scope and extensions: The multivariate identifiability proof applies to any restriction that guarantees bivariate identifiability, while the paper’s regression-based algorithms specifically rely on additive noise.The same principle extends to discrete additive-noise and post-nonlinear additive-noise SEMs, although the latter are harder to fit empirically.
- Graph ambiguity and ordering: The paper also characterizes graph ambiguity: supergraphs and suitable subgraphs can admit additive-noise models for the same distribution, motivating identification of minimal graphs or true orderings.Under restricted-model assumptions, the set of true orderings can be identified, and RESIT is guaranteed correct in the population setting with consistent regression and an independence oracle.
4. Algorithms
The paper proposes RESIT and independence-score methods for estimating causal DAGs from finite samples, while noting that population guarantees do not ensure practical efficiency or scalability. RESIT is proven correct under restricted additive-noise assumptions with consistent regression and perfect independence testing.
- RESIT: RESIT iteratively identifies sink nodes by regressing each variable on the others and measuring dependence between residuals and the remaining variables.The selected sink is the node with the weakest residual dependence, after which the causal order is built iteratively.
- RESIT: RESIT then removes superfluous edges through variable selection and outputs the estimated parent sets for the recovered causal order.The procedure separates causal-order determination from edge removal.
- RESIT: Given infinite data, consistent non-parametric regression, and an independence oracle, RESIT is guaranteed to recover the correct graph under a restricted additive noise model and causal minimality.This is a population result rather than a finite-sample efficiency guarantee.
- RESIT: RESIT performs O(p^2) independence tests, but high-dimensional dependence testing requires huge sample sizes and prevents good scalability to many nodes.The method is polynomial in node count, yet statistically difficult finite-sample testing limits practical scaling.
- Independence-based scores: Independence-score methods select graph structures by evaluating dependence among regression residuals, with residuals determined by the candidate graph and regression method.The paper explicitly does not claim that the score minimizer is consistent; this may depend on the dependence measure, regression method, and regularization.
- Independence-based scores: Exhaustive DAG scoring becomes computationally intractable as p grows, motivating greedy search over edge additions, removals, and reversals.The exhaustive method already has 1,138,779,265 DAGs for p = 7 and was used only up to p = 4 for comparison.
5. Experiments
The experiments compare causal discovery methods on synthetic linear and nonlinear SEMs and on real cause-effect pairs. RESIT is especially strong for nonlinear data, while performance depends on graph size, model class, and evaluation metric.
- Synthetic data: The study compares GDS, brute force, RESIT, LiNGAM, PC, CPC, GES, and random guessing across synthetic settings.Methods are evaluated using SHD and SID against true DAGs or CPDAGs over 100 simulations.
- Synthetic data: For p = 4, brute force performs best in both linear and nonlinear settings; for p = 15, LiNGAM and GDS lead linear non-Gaussian data while RESIT leads nonlinear data.GDS is presented as a reasonable alternative when the data-generating functional form is unknown.
- Synthetic data: 86 and 90 out of 100 simulations recover the correct graph for GDS and brute force, respectively, at p = 4 and n = 500 in linear SEMs.RESIT and LiNGAM still outperform PC methods and GES in this setting.
- Synthetic data: For p = 15 and n = 500 with nonlinear Gaussian SEMs, RESIT performs slightly better than the other methods on SHD and SID.Its advantage is attributed to using the nonlinear structure of the structural equations.
- Real data: The weather-station analysis considers altitude, temperature, and sunshine duration, with GDS, brute force, and RESIT selecting additive-noise-compatible structures under gam regression.The data may be confounded geographically, involve feedback, or deviate from additive noise; residual independence was not fully clear.
- Cause-effect pairs: Across 86 cause-effect pairs, taking decisions for all pairs yields 72 ± 6% accuracy, while the 20% most confident decisions are all correct.Figure 6 reports accuracy as a function of decision rate with 68% and 95% confidence intervals.
6. Discussion and Future Work
The discussion argues that additive-noise structural equation models can identify causal graphs from joint distributions under mild assumptions. It also highlights scalability and statistical guarantees as unresolved challenges.
- Discussion: Apart from a few exceptions, additive-noise models identify DAGs from bivariate distributions, and this result generalizes to multivariate graphs under mild assumptions.The paper frames structural equation models as a useful way to state and exploit additive-noise assumptions.
- Discussion: Artificial and real datasets indicate that methods based on restricted structural equation models can outperform traditional constraint-based methods.The proposed score reflects independence of residuals, but finding the best-scoring DAG remains difficult when exhaustive search is infeasible.
- Future work: Applying the methods to larger graphs with p > 20 remains a major challenge.The paper also identifies consistency and other statistical properties as important future research topics.
A.1 Proof of Proposition 4
The proof establishes the relationship between causal minimality and whether an edge can be removed while preserving the distribution's Markov property.
- Proof: If causal minimality fails, a parent edge can be removed while the distribution remains Markov with respect to the resulting graph.The proof uses a node X_j and parent Y whose edge Y → X_j is removable without changing the Markov property.
- Proof: With a density, the Markov condition is equivalent to the Markov factorization, allowing the edge-removal claim to be derived from factorization.The argument identifies the relevant parent set after removing Y from the parents of X_j.
A.2 Proof of Proposition 7
The proof constructs a common subgraph from two candidate DAGs and uses it to establish the existence of a least element in the relevant graph family.
- Proof: For every pair of graphs G1 and G2 in the family, the proof constructs a DAG G satisfying G ≤ G1 and G ≤ G2.The construction groups shared parents of each node separately from parents appearing in only one of the two graphs.
- Proof: The construction assigns each node its jointly shared parents and repeats this procedure across all nodes.The resulting distribution is Markov with respect to G by construction.
- Proof: Because the graph family is finite, the existence of such a common lower graph implies a least element.The proof also notes that proper subgraphs of a true causal DAG with respect to which the distribution is Markov are themselves true causal DAGs.
A.3 Proof of Proposition 10
The proof constructs a structural equation model using independent uniform noise variables and functions of each variable’s parents.
- The proof assumes N1, · · ·, Np are independent and uniformly distributed between 0 and 1.
- Each variable is defined structurally as Xj = fj(PAj, Nj), combining its parents with its noise term.
- This construction directly specifies the additive-noise structural equation model used in the proposition.
A.4 Proof of Proposition 16
The proof shows that violating causal minimality forces a parent’s effect to disappear after conditioning on the other parents, making the corresponding structural function constant in that argument.
- If causal minimality fails, some parent Xi does not affect Xj after conditioning on all other parents.
- Writing the remaining parents as XA, the structural function satisfies fj(xA, xi) = cxA almost everywhere.
- Continuity of fj then implies that fj is constant in its last argument.
- The converse statement follows from Proposition 4 as well.
A.5 Proof of Theorem 19
The proof rules out a non-identifiable reverse additive-noise model by deriving differential constraints from two competing factorizations of the joint density and contradicting Condition 18.
- The proof assumes a non-identifiable graph and compares forward and backward additive-noise representations of X and Y.
- The joint log-density is written as π(x, y) := log p(x, y) = ν(y − f(x)) + ξ(x).
- The backward representation yields expressions for mixed and second derivatives of π involving g′(y) and ν̃′′(x − g(y)).
- Combining the derivative identities produces a differential equation whose required vanishing contradicts the assumption of an identifiable bivariate additive-noise model under Condition 18.
A.6 Proof of Proposition 20
For fixed f and noise log-density ν, the proof characterizes backward-compatible ξ functions through a linear inhomogeneous differential equation and bounds them by a three-dimensional affine space.
- Fixing y such that ν′′(y − f(x))f′(x) ≠ 0 for almost all x yields a linear inhomogeneous differential equation for ξ.
- With z := ξ′′, the equation becomes z′(x) = z(x)G(x, y) + H(x, y).
- The solution z is determined by its value z(x0), after which Equation (17) extends it to the remaining points.
- All ξ satisfying the differential equation form a 3-dimensional affine space fixed by ξ(x0), ξ′(x0), and ξ′′(x0).
- For fixed f and ν, ξ functions admitting a backward model lie within this subspace.
A.7 Proof of Corollary 21
The proof establishes identifiability by assuming two restricted additive noise models induce the same distribution and deriving contradictions from functional and graphical properties. It isolates exceptional affine and log-mix-lin-exp cases, then rules out differing graph structures using conditional independence arguments.
- Exceptional case: The appendix defines several asymptotic and mixture-of-exponential density classes used to characterize these exceptional cases.The listed classes include log-mix-lin-exp, one-sided and two-sided asymptotically exponential, and generalized mixtures of two exponentials.
- Exceptional case: Affine f with log-mix-lin-exp noise distributions can yield a nonidentifiable additive noise model under explicit parameter constraints.The proof verifies the parameter restrictions, chooses C to normalize the log-density, and confirms equation (18).
- Proof strategy: The proof assumes two restricted additive noise models induce the same distribution on distinct DAGs and seeks to show the graphs must coincide.It compares models with graphs G and G′ and uses variables and conditioning sets constructed from their differing adjacencies.
- Functional contradiction: A reverse additive noise model contradicts Theorem 19 when the induced conditional models satisfy Condition 18.The construction conditions on S and applies independence of the relevant noise variables before invoking the theorem.
- Graphical contradiction: Graph differences are eliminated by repeatedly removing common childless nodes and analyzing remaining mismatched adjacencies with d-separation and causal minimality.The argument partitions G-parents of L into shared parents, children, and nonadjacent nodes, then derives conditional independences contradicting Lemma 37.