Source-linked AI summary
Identifiability of Causal Graphs using Functional Models
Jonas Peters, Joris Mooij, Dominik Janzing, Bernhard Schoelkopf
TL;DR
The paper asks when a causal graph can be inferred from a joint distribution, given that Markov and faithfulness assumptions generally identify only a Markov equivalence class. It defines IFMOCs and proves that, under this assumption, the complete causal graph is identifiable, extending the result beyond linear functional relationships. The paper also discusses assumption testing, gives a finite-sample algorithm, and evaluates it on simulated data.
Problem
The paper addresses how to infer the true causal DAG from i.i.d. samples of a joint distribution when conditional-independence methods identify only its Markov equivalence class.
Method
The paper defines Identifiable Functional Model Classes from bivariate identifiability and uses them to model multivariate data-generating processes.
Results
Under an IFMOC assumption, the joint distribution identifies the complete causal graph, including for nonlinear interactions.
Takeaways & Limitations
Functional-model assumptions can resolve causal directions that conditional-independence methods leave undirected, while supporting a practical graph-recovery procedure.
Takeaways & Limitations
The approach can give a wrong answer if the true process belongs to an IFMOC associated with a graph different from the true causal graph.
Abstract
from arXiv · showhide
This work addresses the following question: Under what assumptions on the data generating process can one infer the causal graph from the joint distribution? The approach taken by conditional independence-based causal discovery methods is based on two assumptions: the Markov condition and faithfulness. It has been shown that under these assumptions the causal graph can be identified up to Markov equivalence (some arrows remain undirected) using methods like the PC algorithm. In this work we propose an alternative by defining Identifiable Functional Model Classes (IFMOCs). As our main theorem we prove that if the data generating process belongs to an IFMOC, one can identify the complete causal graph. To the best of our knowledge this is the first identifiability result of this kind that is not limited to linear functional relationships. We discuss how the IFMOC assumption and the Markov and faithfulness assumptions relate to each other and explain why we believe that the IFMOC assumption can be tested more easily on given data. We further provide a practical algorithm that recovers the causal graph from finitely many data; experiments on simulated data support the theoretical findings.
1 Introduction
Conditional-independence methods can leave causal directions unresolved because Markov-equivalent graphs share the same relevant independence structure. The paper introduces IFMOCs to identify complete causal graphs, extending functional-model identifiability beyond linear relationships and motivating a practical algorithm.
- Existing causal discovery: Conditional-independence methods rely on the Markov condition and faithfulness to infer graph structure from the joint distribution.These methods use conditional independences to identify parts of the graph.
- Existing causal discovery: For two dependent variables, conditional-independence methods cannot distinguish X →Y from Y →X because the graphs are Markov equivalent.Additive noise models instead infer the direction supported in one direction but not the other.
- Functional identifiability: Under suitable conditions, an additive noise model in one direction but not the other identifies that direction as causal.The model requires independent noise and excludes certain combinations of the function and input and noise distributions.
- Functional identifiability: The paper defines Identifiable Functional Model Classes and proves that membership in an IFMOC permits recovery of the complete causal graph, including nonlinear interactions.This addresses a multivariate identifiability problem previously solved only in the linear case.
- Practical implications: The paper argues that IFMOC validity can be assessed by checking whether none, one, or multiple models fit, unlike general faithfulness.It also provides an algorithm for identifying causal structures from finite data and reports experiments on artificial data.
2 Identifiability Results
The paper compares conditional-independence methods with functional-model identifiability for recovering causal DAGs from joint distributions. It introduces IFMOCs, proves complete graph identifiability under this assumption, and discusses practical scope and failure modes.
- The problem is to infer the true causal DAG from i.i.d. samples of a joint distribution under acyclicity, causal sufficiency, and no selection bias.
- Markov and faithfulness assumptions allow conditional-independence methods such as PC to identify the true DAG only up to its Markov equivalence class.The approach relies on conditional-independence tests, including tests with conditioning sets of up to #V−2 variables.
- Functional models use jointly independent noises and an acyclic graph linking each variable to its direct causes, with a unique induced joint distribution.
- Identifiable Functional Model Classes (IFMOCs) extend bivariate functional identifiability to multivariate distributions and ensure that one joint distribution cannot arise from the same class with two different graphs.The construction requires restricting the function class; otherwise any joint distribution can be represented by a functional model in both directions.
- Under the IFMOC assumption, the true causal DAG is identifiable from the joint distribution, including distinctions inside a Markov equivalence class and some non-faithful models.The result applies to nonlinear interactions and includes discrete models, but only for non-deterministic data.
- The functional-model approach has explicit failure modes: multiple graphs may fit, no model may fit, or a different IFMOC graph may fit the data and yield a wrong answer.The authors characterize the last case as requiring a precise matching between cause and conditional-effect distributions, and note that IFMOC validity may be tested by fitting none or multiple models.
3 Proof
The proof shows that two IFMOC instances inducing the same joint distribution must have the same causal DAG. It proceeds by eliminating matching sink nodes and deriving contradictions from d-separation and bivariate identifiability when the graphs differ.
- Theorem 2: Theorem 2 assumes two IFMOC instances induce the same distribution and proves their graphs are identical.The proof compares DAGs G and G′ and seeks a contradiction if they differ.
- Theorem 2: The proof repeatedly removes nodes without children that have identical parent sets in both graphs.Acyclicity guarantees nodes without descendants, allowing the comparison to proceed on smaller DAGs.
- Graph comparison: Parents and children of X are partitioned into sets Y, Z, W, D, and E according to their adjacency and orientation in G and G′.This partition organizes which edges differ between the two candidate graphs.
- Contradiction cases: If the differing-node set T is empty, a node in D or E yields a conditional independence contradicting Lemma 4.The proof treats D and E separately, using conditioning sets built from Z and neighboring nodes.
- Contradiction cases: If T is nonempty, selecting a G′-youngest node and d-separating paths likewise produces an independence that contradicts Lemma 4.For a youngest W node, the proof augments G′, constructs a separating set, and derives X ⊥⊥ W | S.
4 Algorithm
The algorithm fits functional models for candidate graph structures and retains graphs whose fitted residuals are independent of the relevant regressors. It avoids enumerating every DAG by recursively identifying sink nodes and reports uncertainty when zero or multiple DAGs remain.
- Candidate evaluation: For each graph structure, the method fits its functional model and outputs graphs whose residuals are independent.The procedure uses residual independence as the criterion for retaining candidate causal structures.
- Recursive search: The algorithm finds a sink node, removes it, and continues recursively on the smaller graph instead of checking every DAG.This strategy is based on the earlier multivariate ANM approach cited by the authors.
- Output: If no graph or multiple graphs survive, the method indicates that the model assumption is violated or the direction is unresolved.The algorithm is designed to preserve uncertainty rather than force a single graph.
5 Experiments
The experiments evaluate regression and independence-testing implementations across faithful, nonfaithful, nonlinear, and assumption-violating settings. IFMOC methods often recover more structure or abstain, while PC can return incorrect graphs when its assumptions fail.
- Implementation: The implementation uses linear regression or Gaussian Processes and tests residual–regressor independence with HSIC.The PC comparisons use partial correlation or conditional HSIC with a 5% significance level.
- Data Set 1: Finite-sample false zero partial correlations persisted in more than 10% of cases even at sample size 500,000.The authors attribute these type 2 errors to wrong graph conclusions and note that lower significance thresholds would increase them.
- Data Set 2: For nonlinear data sets satisfying both assumptions, PCpart failed, whereas the IFMOC approach could identify the single correct DAG or remain undecided.The authors report greater robustness especially when conditional independence requires conditioning on multiple variables.
- Data Set 3: In 100 nonfaithful data sets, both PC algorithms always returned a wrong DAG, whereas IFMOClin recovered the correct DAG in 89 cases and never returned a wrong graph.Each data set had sample size 400.
- Data Set 4: In the faithful Gaussian-linear setting, PCcorr recovered the true Markov equivalence class in 47 of 100 cases, while IFMOClin succeeded in 94 and was undecided 6 times.The experiment used 100 data sets with sample size 400.
- Data Set 5: When both faithfulness and the additive-noise-model expectation failed, both PC methods always returned wrong results while both IFMOC methods always abstained.This setting used 100 data sets with sample size 400.
6 Conclusion and Future Work
The paper concludes that identifiable functional model classes make the complete causal graph recoverable from the joint distribution, using only causal minimality rather than full faithfulness. It also identifies finite-sample behavior, partial identifiability, Bayesian extensions, and real-data validation as directions for further work.
- Conclusion: IFMOCs identify the whole true causal graph from the joint distribution, including distinctions within a Markov equivalence class.The approach requires only causal minimality as a weak form of faithfulness.
- Conclusion: The proposed finite-sample algorithm was built on an existing graph-recovery algorithm and tested with ANMs on simulated data.
- Future Work: Future work includes connecting IFMOCs with Bayesian structure-learning methods and investigating whether the theoretical results imply their consistency.
- Future Work: Experiments found that the proposed method can outperform PC on finitely many samples even when both methods’ assumptions hold, a behavior requiring further investigation.
- Future Work: Open questions include graphs with mixed identifiable and non-identifiable parts and testing the principle on real data with known ground truth.
Appendix
The appendix establishes edge-count and conditional-independence relationships used to connect functional-model assumptions with causal minimality. It also derives independence properties from jointly independent noise variables and notes the positivity condition needed for an intersection argument.
- Graph comparison: Under the stated Markov and faithfulness assumptions, the true graph has no more edges than the DAG associated with the IFMOC functional model.
- Graph comparison: The proof uses the inclusion of independence relations induced by the model DAG within those induced by the true graph.
- Functional derivations: For X := f(Y, Z, N), the appendix derives the conditional representation X | Z=z,S=s = f(Y | Z=z,S=s, z, N) under the stated support condition.
- Functional derivations: Recursive substitution of structural equations expresses S through ancestors that exclude X, so independent noise variables imply N_X ⫫ S.
- Causal minimality: With a strictly positive density, the appendix states that Lemma 4 is equivalent to causal minimality.
- Causal minimality: The intersection property of conditional independence requires positivity of the densities.