Technical Summary: Coarsening Linear Non-Gaussian Causal Models with Cycles

Problem Statement

Causal discovery from observational data has historically focused on Directed Acyclic Graphs (DAGs). However, many scientific systems, such as gene-regulatory networks and dynamical systems, inherently contain feedback loops (directed cycles). While existing methods for learning cyclic causal models exist, they often face significant limitations:

1. Identifiability Ambiguity: In the Linear Non-Gaussian (LiNG) setting, cyclic Structural Causal Models (SCMs) are identifiable only up to a distributional equivalence class. Members of this class differ by the reversal of directed cycles, making the exact micro-level graph structure unidentifiable from observational data alone without strong assumptions (e.g., stability or disjoint cycles).
2. Computational Complexity: Existing approaches to learning summaries of causal structures, such as the GroupLiNGAM algorithm, often suffer from exponential time complexity in the number of variables.
3. Applicability: Many high-dimensional models with cycles are excluded from standard causal abstraction frameworks because those frameworks assume acyclicity.

This paper addresses the challenge of summarizing high-dimensional cyclic causal structures into low-dimensional representations that are both identifiable and computationally tractable, without requiring the restrictive assumptions of disjoint cycles or stability.

Methodology

The authors extend the framework of causal coarsening—which groups variables into clusters to form a quotient graph—to directed graphs containing cycles.

1. Theoretical Framework: The SCC Floor

The core theoretical insight is that any valid DAG-coarsening of a cyclic graph must respect its Strongly Connected Components (SCCs).

• Proposition 1: Nodes within the same SCC must be grouped into the same cluster in any DAG-coarsening. If they were split, the quotient graph would necessarily contain a cycle, violating the DAG requirement.
• Structural Floor: The partition of variables into SCCs forms the "structural floor" of the coarsening lattice. It is the finest valid DAG-coarsening. The resulting quotient graph is the condensation ($G_{sc}$) of the original graph, which is a DAG by definition.

2. Identifiability via ICA

The paper leverages the properties of Linear Non-Gaussian (LiNG) cyclic SCMs:

• Model: $X = BX + \varepsilon$, where $\varepsilon$ has mutually independent, non-Gaussian components.
• Observational Equivalence: Following [19], the mixing matrix $A = (I-B)^{-1}$ can be recovered via Independent Component Analysis (ICA) up to row permutation and scaling. Different permutations yield different members of the distributional equivalence class (differing by cycle reversals).
• Theorem 1 (Condensation Identifiability): The authors prove that while the micro-level graph $G$ is only identifiable up to the equivalence class, the condensation $G_{sc}$ is invariant across all members of this class.
  • Reasoning: Cycle reversals occur strictly within SCCs and do not alter the SCC partition itself. Furthermore, edges between different SCCs (inter-cluster edges) cannot lie on a directed cycle; thus, cycle reversals cannot add, remove, or redirect these edges. Consequently, the cluster-level DAG is fully identifiable from observational data alone.

3. Algorithm: Condensation Recovery

The proposed procedure (Algorithm 1) recovers the condensation in polynomial time:

1. Estimation: Apply FastICA to observational data to estimate the demixing matrix $\hat{W}$.
2. Permutation: Select a single admissible row permutation $P$ (e.g., via the Hungarian algorithm) such that the diagonal of $P\hat{W}$ is non-zero.
3. Candidate Construction: Compute a candidate adjacency matrix $\hat{B} = I - \text{diag}(P\hat{W})^{-1}P\hat{W}$.
4. Thresholding: Apply a threshold $\tau$ to $\hat{B}$ to determine the support (edges).
5. SCC Extraction: Apply Tarjan's algorithm to the support of $\hat{B}$ to identify SCCs.
6. Condensation Construction: Form the quotient graph where nodes are the SCCs and edges exist if there is any edge between the corresponding clusters in $\hat{B}$.

Complexity: The algorithm runs in worst-case $O(k \cdot n \cdot d^2 + d^3)$ time, where $n$ is sample size, $d$ is variables, and $k$ is ICA iterations. This avoids the $O(d!)$ complexity of enumerating all equivalence class members.

Key Results

The paper provides theoretical guarantees and empirical validation on synthetic data:

• Theoretical Guarantees:

  • Identifiability: The condensation $G_{sc}$ is identifiable from observational data without invoking stability assumptions or disjoint cycle constraints.
  • Sample Complexity: The paper derives bounds showing that recovering the true condensation with probability $1-\delta$ requires a sample size $n = \Theta(d / (\beta_{min}^2 \sqrt{\delta}))$, where $\beta_{min}$ is the minimum non-zero edge weight.
  • Failure Modes: The authors characterize two failure modes of thresholding: (a) splitting a true SCC due to dropped edges (refinement), and (b) merging distinct SCCs due to spurious edges (coarsening).

• Empirical Performance:

  • Consistency: Experiments on synthetic LiNG cyclic SCMs ($d=10$) show that the Adjusted Rand Index (ARI) of the recovered SCC partition and the F1 score of the cluster-DAG converge to 1 as sample size increases, regardless of whether the system is in a stable ($\rho(B) < 1$) or unstable ($\rho(B) > 1$) regime.
  • Scalability: Compared to the state-of-the-art disjoint-cycle baseline [9], the proposed method scales significantly better. While the baseline's fit time grows exponentially and performance plateaus for $d \ge 50$, the proposed method maintains high accuracy and fit times under 10 seconds even for $d=100$.
  • Robustness: The method successfully recovers the cluster-level structure even when the variable-level structure is unidentifiable (e.g., in the unstable regime where the "first-stable" filter fails to recover the true $B$).

Significance and Claims

The paper claims to bridge the gap between cyclic causal modeling and causal abstraction:

1. Resolution of Ambiguity: It provides a natural representative for the distributional equivalence class of cyclic LiNG models. While the exact micro-graph is ambiguous, the condensation is a unique, identifiable object that captures the causal flow between clusters of variables.
2. Enabling Downstream Causal Inference: By identifying $G_{sc}$ from observational data, the paper supplies the necessary prerequisite for applying C-DAG (Cluster DAG) identification theorems (from [2]). This allows researchers to perform causal effect identification at the cluster level in cyclic systems using standard acyclic machinery, a task previously limited to acyclic systems or requiring interventional data.
3. Computational Efficiency: The approach offers a polynomial-time alternative to exponential-time methods for learning causal summaries, making it applicable to higher-dimensional problems.
4. Relaxed Assumptions: Unlike previous works requiring disjoint cycles or specific noise skewness, this approach relies only on general non-Gaussianity and standard ICA, applicable to overlapping cycles.

The authors note limitations, specifically that the method assumes no latent confounders (or requires overcomplete ICA extensions) and that at most one noise component can be Gaussian to avoid rotational ambiguity merging distinct SCCs. They position the work as a foundational step toward practical causal discovery in complex, cyclic systems.