Source-linked AI summary
Discovering Cyclic Causal Models by Independent Components Analysis
Gustavo Lacerda, Peter L. Spirtes, Joseph Ramsey, Patrik O. Hoyer
TL;DR
The paper addresses discovery of linear non-Gaussian SEMs when the generating graph may contain cycles. It generalizes ICA-based LiNGAM to output all distribution-compatible SEMs, and shows that stability can sometimes select a single candidate.
Problem
The central problem is finding all SEMs that describe samples from a causally sufficient LiNG process when cyclic graphs are allowed.
Method
The paper generalizes Shimizu et al.’s ICA-based LiNGAM approach from acyclic to general linear non-Gaussian SEMs and uses distribution-entailment equivalence.
Results
LiNG-D outputs exactly the SEMs that entail the population distribution in the large-sample limit, rather than selecting a unique cyclic graph from observational data alone.
Takeaways & Limitations
Assuming stability can sometimes narrow the output equivalence class to a single SEM.
Takeaways & Limitations
The method assumes no self-loop has coefficient 1, a case the paper identifies as unresolved.
Abstract
from arXiv · showhide
We generalize Shimizu et al's (2006) ICA-based approach for discovering linear non-Gaussian acyclic (LiNGAM) Structural Equation Models (SEMs) from causally sufficient, continuous-valued observational data. By relaxing the assumption that the generating SEM's graph is acyclic, we solve the more general problem of linear non-Gaussian (LiNG) SEM discovery. LiNG discovery algorithms output the distribution equivalence class of SEMs which, in the large sample limit, represents the population distribution. We apply a LiNG discovery algorithm to simulated data. Finally, we give sufficient conditions under which only one of the SEMs in the output class is 'stable'.
1 Linear SEMs
Linear SEMs represent substantive variables as linear functions of their direct causes and error terms, with associated directed graphs encoding nonzero structural coefficients. Their simultaneous equations can describe equilibrium or dynamical systems, but equilibrium data cannot determine self-loop coefficients.
- The model: Each substantive variable is written as a linear function of its direct causes and corresponding error term.The model separates typically unobserved error terms from substantive variables.
- The model: A directed graph represents the SEM’s causal structure, with an edge xi to xj exactly when xi has a nonzero coefficient in xj’s equation.
- Matrix representation: Solving x = (I −B)x + e yields the reduced-form representation x = (I −B)−1e = Ae when I −B is invertible.A is called the reduced form matrix, or mixing matrix in ICA terminology.
- Interpretations: The same simultaneous equations may describe equilibrium variables or, under further assumptions, coefficients of a deterministic dynamical system.One interpretation averages the dynamical state over an observation period with reaction lag ∆θ = 1/n.
- Self-loops: Equilibrium data cannot determine diagonal entries of B, so the discovery algorithms output SEMs without self-loops.For underlying self-loop coefficient ba,a ≠ 1, rescaling the error term can produce an equivalent no-self-loop form; ba,a = 1 is excluded.
- Self-loops: The coefficient case ba,a = 1 is a genuine unresolved problem, and the paper assumes that no self-loop has coefficient 1.The attempted transformation requires division by 1 − ba,a, which is infinite when ba,a = 1.
2 The problem and its history
The paper seeks the set of linear SEMs that describe an observed equilibrium distribution, extending causal discovery beyond acyclic graphs. Earlier methods either represented broad zero-partial-correlation equivalence classes or, under LiNGAM assumptions, uniquely recovered acyclic models.
- The problem: Given samples from a causally sufficient LiNG process, the problem is to find all SEMs that describe the observed equilibrium distribution.The formulation assumes that the set of compatible SEMs is non-empty.
- Prior work: CCD was the only previously known provably correct algorithm for general linear directed graphs, outputting a partial ancestral graph.
- Prior work: CCD’s graph set can be large because its members share zero partial correlations but may differ in covariances or joint distributions.Consequently, the set may include cyclic graphs that do not fit the data well, and reducing it can be intractable.
3 Shimizu et al’s approach for discovering LiNGAM SEMs
LiNGAM applies ICA to linear non-Gaussian SEM data, then resolves row permutations and scales to recover the structural coefficient matrix. Acyclicity guarantees one admissible permutation, and the method does not require faithfulness.
- Independent Components Analysis (ICA): ICA estimates a mixing matrix from observed x = Ae by finding a transformation whose implied error distributions are maximally non-Gaussian.The matrix is identifiable up to scaling and permutation when at most one independent component is Gaussian.
- The LiNGAM discovery algorithm: For SEM data, ICA returns a row-scaled, row-permuted version of I −B, leaving permutation and scaling to be resolved.
- The LiNGAM discovery algorithm: A row permutation is admissible when its diagonal contains no zero, because the correct W = I −B has zero diagonal in B.
- The LiNGAM discovery algorithm: Acyclicity guarantees exactly one admissible row permutation, uniquely matching each ICA error term to its substantive variable.
- The LiNGAM discovery algorithm: After normalizing rows so W has diagonal entries 1, the algorithm computes B = I −W′.Here W′ is the normalized, correctly permuted ICA output.
- The LiNGAM discovery algorithm: LiNGAM determines every causal-arrow direction without requiring the faithfulness assumption used by conditional-independence-based methods.
4 Discovering LiNG SEMs
LiNG-D relaxes acyclicity to permit cyclic SEMs, generating all admissible models from ICA estimates while addressing finite-sample zero detection and permutation search.
- General LiNG discovery: LiNG-D replaces acyclicity with the assumption that the diagonal of Bdyn contains no 1s, allowing cyclic SEM discovery.Candidates are row-permutations of WICA with zeroless diagonals.
- General LiNG discovery: When the true model contains cycles, multiple admissible models may be output instead of LiNGAM’s single model.LiNGAM’s singleton output follows from its acyclicity assumption.
- Finite-sample discovery: Finite-sample algorithms prune entries of WICA judged to be zero, then find every admissible row-permutation using Constrained n-Rooks.The search places n non-threatening rooks on non-zero entries and moves them onto the diagonal.
- Finite-sample discovery: Thresholding is simple but ignores differing coefficient spreads and can miss coefficients smaller than its cutoff.The method sets entries below an absolute threshold to zero.
- Finite-sample discovery: Bootstrap quantile testing estimates coefficient distributions across resampled datasets and prunes an edge when zero is not an outlier.Each bootstrap WICA must first be row-permuted to match the original WICA.
- Non-local methods: Local methods assume coefficient estimates are independent, an assumption generally false with finite samples, motivating non-local methods.The non-local assignment approach is insufficient for general LiNG discovery because multiple admissible permutations may exist.
- Non-local methods: The non-local method fails to account for differing spreads among WICA estimates, although its loss function could be modified to use bootstrap-based null testing.The paper also describes k-th best assignment as a way to search successive low-penalty permutations.
- Simulation: A simulation generated 15000 samples from the example SEM with symmetric Gaussian-squared errors, and Fig. 3 reports local thresholding at a 0.05 cutoff.The paper provides code and instructions for reproducibility.
5 Theory
LiNG-D returns the distribution-entailment equivalence class of linear non-Gaussian SEMs, extending ICA-based discovery to cyclic graphs. Under disjoint-cycle and stability assumptions, the true SEM is the only stable candidate.
- 5.1 Notions of DG equivalence: With non-Gaussian errors, distribution equivalence is stricter than covariance or d-separation equivalence, enabling unique identification in the acyclic case but not generally for cyclic graphs.For Gaussian errors, opposite two-variable directions can remain distribution equivalent; with non-Gaussian errors, the corresponding acyclic directions are not distribution equivalent.
- 5.1 Notions of DG equivalence: For cyclic graphs, observational data alone cannot reliably select a unique causal graph when distinct graphs are distribution equivalent.The two cyclic graphs in Fig. 3 are distribution equivalent, so both remain admissible without further assumptions.
- 5.2 The output of LiNG-D is correct and as fine as possible: Any two SEMs output by LiNG-D entail the same distribution, while the algorithm outputs all SEMs that entail that distribution.Candidate models arise through admissible row permutations of the ICA weight matrix, with scaling normalized after the correct permutation is found.
- 5.2 The output of LiNG-D is correct and as fine as possible: LiNG-D outputs all SEMs that entail the population distribution in the large-sample limit under linearity, nonzero error variances, i.i.d. samples, at most one Gaussian error, and jointly independent errors.The output therefore forms a distribution-entailment equivalence class rather than necessarily a single model.
- 5.3 Adding the assumption of stability: A simple cycle with cycle-product π is unstable when |π| ≥1; equivalently, it has an eigenvalue with modulus at least 1.For disjoint cycles, the SEM is stable if and only if it has no unstable cycles.
- 5.3 Adding the assumption of stability: If the true SEM is stable and its cycles are disjoint, it is the only stable model among LiNG-D’s admissible alternatives.Any distinct admissible alternative reverses at least one cycle and inverts its cycle-product, making that alternative unstable.
6 Discussion
The paper generalizes ICA-based LiNGAM discovery to cyclic linear non-Gaussian SEMs and characterizes distribution-entailment equivalence classes. It also shows that stability can sometimes reduce the candidates to a single SEM, while leaving computational and modeling extensions open.
- The method generalizes Shimizu’s ICA-based LiNGAM approach from acyclic to general linear non-Gaussian SEMs.
- Its output is only the distribution-entailment equivalence class, rather than the larger d-separation equivalence class, and it relaxes the faithfulness assumption.
- Stability can provide a powerful constraint that sometimes narrows the candidate models to a single SEM.
- The algorithm generates all admissible permutations, creating a worst-case search problem and leaving efficient stable-model search as an open question.
- Open directions include incorporating prior information, relaxing causal sufficiency, allowing Gaussian mixtures, and handling noisy or nonlinear dynamics.