Distributional Equivalence in Linear Non-Gaussian Latent-Variable Cyclic Causal Models: Characterization and Learning

AI summary

Overview

Research area: Causal discovery / structure learning with latent variables, specifically linear non-Gaussian (LiNG) causal models with cycles.

Technical level: Advanced. The paper combines graphical causal modeling with algebraic geometry, matrix rank theory, matroid duality, and overcomplete independent component analysis (OICA).

One-sentence scope: The paper characterizes exactly when two linear non-Gaussian causal graphs with arbitrary latent structure and cycles produce the same set of observed distributions, and provides a procedure to traverse that equivalence class and an algorithm to recover models from data up to it.

What This Paper Is About

Most methods for causal discovery with unobserved variables impose strong structural assumptions — for example, that observed variables must be pure measurements of latents, that latents cannot have observed parents, that each latent needs enough "pure children," or that the graph is triangle- or bow-free and acyclic. The authors argue that a core reason no general, assumption-free method exists is that there is no characterization of distributional equivalence with latents: without knowing what can be identified, one cannot design methods for how to identify it. This paper supplies that missing characterization for linear non-Gaussian models with arbitrary latent structure and cycles, and builds a data-driven recovery algorithm on top of it.

Key Contributions

1. A general equivalence notion with arbitrary latents and cycles. The authors present the first equivalence characterization with latent variables in any parametric setting without structural assumptions, covering arbitrary latent structure and cycles in linear non-Gaussian models (Section 2).

2. A new tool: edge rank constraints. Edge ranks operate locally on edges rather than globally on paths, complementing the existing path-rank toolbox for latent-variable causal discovery and, the authors argue, with potential use across broader settings (Section 3).

3. A graphical characterization and class traversal. Equivalence is characterized graphically, and procedures are given to traverse the entire equivalence class; the authors describe the results as "cleaner than expected," and provide an interactive demo at https://equiv.cc (Section 4).

4. An algorithm to recover the equivalence class from data. The paper develops what it states is the first structural-assumption-free method for latent-variable causal discovery (Section 5). (The truncated content provided does not include the algorithm's details or any empirical results.)

Main Findings

• Equivalence reduces to matrix-set closure. Two irreducible models are distributionally equivalent if and only if their mixing-matrix sets are equal up to column scaling and permutation (Lemma 1). Formally, the closure of the mixing matrices over permutation and nonzero diagonal scaling must coincide.

• Path ranks suffice, but are unwieldy. Equivalence can be expressed in terms of path ranks — the maximum number of vertex-disjoint directed paths, equivalent by Menger's theorem to a min-cut quantity. Two irreducible models are equivalent iff there exists a permutation π over vertices such that ρ_G(Z,Y) = ρ_H(Z, π(Y)) for all Z ⊆ X and Y ⊆ V(G) (Lemma 3). The authors compare this to saying "having all the same d-separations" rather than a practical criterion.

• A new concept, edge ranks, is introduced. The edge rank r_G(Z,Y) is the size of the maximum bipartite matching from Y to Z via edges in G, with self-matches allowed. It has a min-cut formulation and an algebraic counterpart: in the binary support matrix Q^(G), the matching rank (the maximum number of nonzero entries placeable on the diagonal by column permutation) equals the edge rank (Lemma 4).

• A duality connects path ranks and edge ranks. The two ranks satisfy min(|Z|,|Y|) − ρ_G(Z,Y) = |V| − max(|Z|,|Y|) − r_G(V\Y, V\Z) for any Z, Y ⊆ V (Theorem 1). The authors note this duality has long been studied in the matroid community, but only the path-rank side was well known in causal discovery. In Figure 2's illustration, ρ_G(Z,Y) = 2 while the dual edge rank r_G(V\Y, V\Z) = 4.

• Equivalence can be restated via edge ranks. Two irreducible models are equivalent iff there exists a permutation π over V(G) with r_G(Z,Y) = r_H(π(Z), Y) for all Z, Y ⊆ V(G) with L ⊆ Y (Lemma 5).

• A practical, local criterion follows. Defining the "children bases" of Y as the vertex sets Z ⊆ ch_G(Y) ∪ Y admitting perfect edge matchings from Y (r_G(Z,Y) = |Z| = |Y|), two irreducible models are equivalent iff there is a permutation π making bases_G(L) = π(bases_H(L)) and bases_G(L ∪ {X_i}) = π(bases_H(L ∪ {X_i})) for each X_i ∈ X (Theorem 2). The paper notes that when L = ∅ each bases_G({X_i}) is just X_i with its children, so Theorem 2 reduces to the classical exact digraph identification result up to permutation (the sentence trails off in the truncated content).

• Trivial cases are ruled out by irreducibility. A model (G, X) is irreducible iff for every non-empty latent set l ⊆ L, |ch_G(l) \ l| ≥ 2 (Proposition 1). The authors note that for acyclic G it suffices to check each single L_i ∈ L, consistent with a condition derived by Salehkaleybar et al. (2020).

• Any model can be reduced to an equivalent irreducible one. A four-step procedure — remove latents with no effect on X, find maximal redundant latents (mrl), then for each such set redirect parents to its exact child and delete the latents — yields an equivalent irreducible model without increasing the number of edges or cycles (Proposition 2).

• Path-rank equivalence is genuinely complex. In Example 1, with a set C = {C_1, C_2} made latent, three different latents choices give equivalence classes of 17, 872, and 1,024 digraphs when m = n = 4, and whether the Y-to-C structure must stay fixed depends on whether n > 2 or n = 2.

Methodology in Plain English

The authors proceed in stages, translating the abstract question "do two graphs generate the same observed data distributions?" into progressively simpler conditions.

1. Restrict to non-trivial models. They define distributional equivalence as equality of the observed distribution sets, then define irreducibility so that models cannot be trivially relabeled or padded with useless latents. They prove a simple graphical test for irreducibility and give a procedure that turns any model into an equivalent irreducible one.

2. Translate distributions into algebra. Because exogenous noises are independent and non-Gaussian, distributional equivalence becomes a statement about the sets of mixing matrices each graph can produce, up to permuting and rescaling noise components.

3. Translate algebra into graph structure. Matrix ranks of submatrices of the mixing matrix equal a purely graphical quantity: path ranks, computed by max-flow/min-cut. This gives an equivalence statement in terms of paths.

4. Replace paths with edges. Because path ranks are global and awkward to manipulate, the authors introduce edge ranks — matching-based, local, edge-level quantities — and prove a duality theorem showing the two rank families encode the same bottleneck information. The edge-rank view makes the final criterion decomposable.

5. Decompose the check. Instead of checking all subsets of observed variables, the criterion only needs the "children bases" of the latent set and of each latent set plus one observed variable, plus a permutation search. This is the form an algorithm can target.

6. Turn the criterion into an algorithm. Section 5 develops a procedure to recover the equivalence class from data. The truncated content does not include the algorithm's steps or any reported experimental results.

Why This Matters

Impact on research. Equivalence characterization is the theoretical backbone of causal discovery — the authors draw an explicit historical parallel: the PC algorithm followed from CPDAGs, and FCI's guarantee followed from maximal ancestral graphs. Prior to this work, the authors state, no characterization of any kind — distributional or constraint-specific — was known for latent variables, and the closest result (Adams et al., 2021) only gives conditions for when a linear non-Gaussian acyclic model is uniquely identifiable, leaving the equivalence question open when identifiability fails. This paper supplies that missing piece for linear non-Gaussian models and, in the authors' framing, removes the main obstacle to structural-assumption-free latent-variable discovery. The edge-rank tool is also positioned as a general addition to the rank-based toolbox, extendable to d-separation and t-separation statements.

Real-world applications (grounded in examples the paper itself describes, plus the settings its assumptions target):

• Psychology: personality traits are hidden behind survey responses; the latents of interest are unobserved and may interact with observed variables in arbitrary ways.
• Biology: crucial regulators may be unobserved due to technical inaccessibility, and the paper's framework does not require these regulators to have pure measured children.
• Systems with feedback loops: the method permits cycles, which the authors note are common in real systems, whereas most competing methods assume acyclicity.
• Practitioner model selection: by removing the need to pick among a menu of untestable structural assumptions (measurement models, hierarchical models, triangle- or bow-freeness, pure-children counts), the framework gives a single, testable notion of what can be recovered.

Industry relevance. The paper targets a broad class of settings — linear, non-Gaussian, possibly cyclic data with hidden confounders — that matches many engineering, economic, and biomedical datasets where the noise is empirically non-Gaussian and feedback is plausible. A demo is available at https://equiv.cc, and the authors state that code is available there as well. The truncated content does not report runtime, scalability, or benchmark performance figures.

Future Directions

• Extending beyond linear non-Gaussian models. The edge-rank tool is presented as a "missing piece" for latent-variable causal discovery "in even broader settings," which invites analogous characterizations for other parametric families.
• Filling in the algorithm's empirical story. The truncated content contains no data experiments, benchmark datasets, or accuracy figures; evaluating the Section 5 recovery algorithm on real and simulated data is the obvious next step.
• Scaling and permutation search. Theorem 2 still requires a permutation π over vertices; designing efficient search over this permutation space is a natural engineering problem.
• Reusing edge ranks elsewhere. The duality theorem implies that statements about d-separation and t-separation can be rephrased in edge-rank terms; identifying which existing rank-based methods benefit is left open.
• Comparing with the closest prior result. How the new equivalence characterization relates to the identifiability conditions of Adams et al. (2021) when identifiability holds is a natural theoretical question.

Target Audience

This paper is for causal inference researchers and graduate students working on structure learning with latent confounders, particularly those in the linear non-Gaussian tradition (OICA, LiNGAM-style methods, rank-based discovery). It will also interest theoretical computer scientists and statisticians working on graphical models, algebraic statistics, and matroid theory, given the path-rank/edge-rank duality. Practitioners should note the paper focuses on characterization and algorithmic design; the truncated content does not include empirical validation, so readers seeking benchmark numbers should consult the full paper.

Authors’ abstract

Causal discovery with latent variables is a fundamental task. Yet most existing methods rely on strong structural assumptions, such as enforcing specific indicator patterns for latents or restricting how they can interact with others. We argue that a core obstacle to a general, structural-assumption-free approach is the lack of an equivalence characterization: without knowing what can be identified, one generally cannot design methods for how to identify it. In this work, we aim to close this gap for linear non-Gaussian models. We establish the graphical criterion for when two graphs with arbitrary latent structure and cycles are distributionally equivalent, that is, they induce the same observed distribution set. Key to our approach is a new tool, edge rank constraints, which fills a missing piece in the toolbox for latent-variable causal discovery in even broader settings. We further provide a procedure to traverse the whole equivalence class and develop an algorithm to recover models from data up to such equivalence. To our knowledge, this is the first equivalence characterization with latent variables in any parametric setting without structural assumptions, and hence the first structural-assumption-free discovery method. Code and an interactive demo are available at https://equiv.cc.