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

Haoyue Dai; Immanuel Albrecht; Peter Spirtes; Kun Zhang

cs.LGMar 5, 2026

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

Authors: Haoyue Dai, Immanuel Albrecht, Peter Spirtes, Kun Zhang

Organizations: Carnegie Mellon University · FernUniversität in Hagen · MBZUAI

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.

Figures & tables

Panel of Figure 1 — Figure 1: Examples of reducing models to their irreducible forms via the procedure in Proposition 2 . Throughout, white circles denote observed variables and grey squares denote latent variables.

Panel of Figure 2 — Figure 2: An illustration of path ranks, edge ranks, and their duality. Left: a digraph $\mathcal{G}$ with vertices $V$ partitioned to $Y$ , $C$ , and $Z$ , shown by different colors. The path rank $\rho_{\mathcal{G}}(Z,Y)=2$ , with $C$ being a min-cut. Right: the dual edge rank $r_{\mathcal{G}}(V\backslash Y,\ V\backslash Z)=4$ , given by the maximum bipartite matching from $V\backslash Z$ to $V\backslash Y$ , i.e., from $Y\cup C$ to $Z\cup C$ , with four matched edges highlighted in red. Four corresponding nonzero entries placed on diagonal, also in red, confirm $\operatorname{mrank}(Q^{(\mathcal{G})}_{V\backslash Y,\ V\backslash Z})=4$ . One may examine the duality in Theorem 1 : w.l.o.g. let $m\leq n$ , there is $m-2=m+n+2-n-4$ .

Panel of Figure 3 — Figure 3: An example distributional equivalence class consisting of $6$ digraphs up to $L$ -relabeling.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: Example Hasse diagrams (defined in Lemma 12 ) over the solution sets of matroid-preserving column augmentations. Instances from the earlier Example 3 are used. In each diagram, the root vertices, corresponding to the minimal solutions (see Corollary 2 ) are highlighted in red, while the leaf vertex, corresponding to the unique maximal solution (see Corollary 1 ) are highlighted in blue.

Aspect	Path rank (Matrix rank)	Edge rank (Matching rank)
Intuition	Algebraic independence	Combinatorial independence
Full rank of a $d\times d$ square matrix $M$	$\operatorname{rank}(M)=d\iff$ the determinant of $M$ is nonzero	$\operatorname{mrank}(M)=d\iff$ the permanent of $M$ is nonzero
Graphical constraints in digraphs	$\rho_{\mathcal{G}}(Z,Y)$ , the maximum number of vertex-disjoint directed paths from $Y$ to $Z$ ( Definition 3 ), equals the matrix rank of generic mixing submatrices $A_{Z,Y}$ ( Lemma 2 )	$r_{\mathcal{G}}(Z,Y)$ , the size of the maximum bipartite matching from $Y$ to $Z$ via direct edges ( Definition 4 ), equals the matching rank of the support submatrix $Q^{(\mathcal{G})}_{Z,Y}$ ( Lemma 4 )
Matroid representations	Strict gammoids in digraphs ( Perfect, 1968 )	Transversal matroids in bipartite graphs ( Ingleton and Piff, 1973 )
Duality ( Theorem 1 )	$\min(\|Z\|,\|Y\|)-\rho_{\mathcal{G}}(Z,Y)=\|V\|-\max(\|Z\|,\|Y\|)-r_{\mathcal{G}}(V\backslash Y,\ V\backslash Z)$

Appendix

Table 1: A side-by-side comparison between path ranks and edge ranks.

Panel of Figure 5 — Figure 5: Left: An example distributional equivalence class consisting of 10 digraphs. Right: Transitions among these digraphs, where solid edges indicate edge additions or deletions, and dashed edges indicate cycle reversals.

Panel of Figure 6 — Figure 6: Illustrative presentations of equivalence classes. Left: Presentation of equivalent digraphs $\mathcal{G}_{1},\mathcal{G}_{2},\mathcal{G}_{3}$ under a same cycle-reversal configuration from Figure 3 . The basis digraph shown is the unique maximal equivalent digraph (Step 2 above). In it, solid edges denote those that must appear in all equivalent digraphs, while dashed edges are those that can be removed (Step 3 above). One may use Corollaries 1 and 2 to check how they are determined. Right: A similar presentation for digraphs $\mathcal{G}_{3},\mathcal{G}_{4},\mathcal{G}_{7},\mathcal{G}_{10}$ from Figure 5 . Remark: One might ask why we present the equivalence class separately for each cycle - reversal configuration rather than for the entire class. The reason is that taking the union over all digraphs in the entire class can, unlike within one configuration, yield a supergraph that is itself out of the equivalence class, potentially producing misleading interpretations. In fact, this separation only leads to more informative presentations, shown by Theorem 4 below.

Settings		Markov equivalence in fully observed acyclic graphs	Markov equivalence in acyclic graphs with latents	Distributional equivalence in LiNG models with latents and cycles (this work)
Structural	Level 1	“Same d-separations”	“Same d-separations”	“Same path/edge ranks up to permutation” ( Lemmas 3 and 5 )
	Level 2	“Same adjacencies and minimal complexes/ v-structures” ( Frydenberg, 1990 ; Verma and Pearl, 1991 )	“Same FCI outputs” ( Spirtes and Verma, 1992 ) ; “Same MAG adjacencies, v-structures, and colliders on discriminating paths” ( Spirtes and Richardson, 1996 ; Richardson and Spirtes, 2002 ) ; “Same head and tails” ( Hu and Evans, 2020 )	“Same bases in children for $L$ itself and with each singleton $X_{i}$ , up to permutation” ( Theorem 2 )
	Level 3	“Maximal (deflagged) chain graphs; essential graphs” ( Frydenberg, 1990 ; Andersson et al., 1997 ; Roverato et al., 2006 ) ; “CPDAGs” ( Spirtes and Glymour, 1991 ; Meek, 1995 )	“Arrowhead completeness” ( Ali et al., 2005 ) ; “Full completeness of PAG orientations” ( Zhang, 2008b ) ; With background knowledge (still incomplete; ( Andrews et al., 2020 ; Venkateswaran and Perković, 2024 ) )	“Unique maximal equivalent graph with edges that must always appear, up to cycle reversal” ( Theorem 4 )
Transfor- mational		“Covered edge reversal (Meek conjecture)” ( Chickering, 1995 ; Meek, 1997 ; Chickering, 2002 ) ; “Weakly covered edge reversal” ( Markham et al., 2022 ) for unconditional equivalence	“Covered edge reversal” ( Zhang and Spirtes, 2005 ; Tian, 2005 ; Ogarrio et al., 2016 ; Claassen and Bucur, 2022 )	“Admissible edge additions/deletions and cycle reversals” ( Theorem 3 )
Traversal algorithms		DAGs traversal within one CPDAG ( Meek, 1995 ; Chickering, 1995 ; Wienöbst et al., 2023 ) ; CPDAGs traversal ( Steinsky, 2003 ; Chen et al., 2016 )	MAGs traversal within one PAG ( Wang et al., 2024 ; Wang et al., 2025 )	BFS/DFS by admissible transformations ( Theorem 3 ), with additional parallel speedup by column decomposition ( Lemmas 9 and 12 )

Appendix

Table 2: A side-by-side overview of representative works on equivalence characterizations across different settings using different approaches. The final column summarizes this work’s contributions.

$n$	$\ell$	$\operatorname{avgdeg}$	MILP	glvLiNG	glvLiNG Phase 1	glvLiNG Phase 2
5	1	1	0.045 $\pm$ 0.013	0.015 $\pm$ 0.005	0.014 $\pm$ 0.005	0.001 $\pm$ 0.000
5	1	3	0.112 $\pm$ 0.008	0.020 $\pm$ 0.002	0.019 $\pm$ 0.002	0.001 $\pm$ 0.000
7	1	1		0.101 $\pm$ 0.045	0.098 $\pm$ 0.044	0.002 $\pm$ 0.000
	1	3		0.169 $\pm$ 0.024	0.165 $\pm$ 0.024	0.004 $\pm$ 0.000
	3	1	37.402 $\pm$ 0.000	0.048 $\pm$ 0.013	0.045 $\pm$ 0.012	0.003 $\pm$ 0.001
	3	3		0.083 $\pm$ 0.014	0.075 $\pm$ 0.013	0.007 $\pm$ 0.001

Appendix

Table 4: Running time comparison between our glvLiNG algorithm and a mixed integer linear programming (MILP) baseline for constructing digraphs that satisfy the rank constraints of oracle OICA mixing matrices. Ground-truth graphs are generated from the Erdős–Rényi model with total number of vertices

n

and average in-degree

\operatorname{avgdeg}

, with

\ell

vertices randomly designated as latent. Each entry reports the mean and standard deviation over 50 models (when completed); empty entries indicate runs that did not finish within 10 minutes. All times are reported in seconds. Experiments were run on an Apple M4 chip.

$n$	$\ell$	$\operatorname{avgdeg}$	PO-LiNGAM	LaHiCaSl
10	3	1	15.48 $\pm$ 2.75	31.64 $\pm$ 4.62
		2	24.30 $\pm$ 4.41	36.80 $\pm$ 4.22
		3	35.40 $\pm$ 3.61	39.96 $\pm$ 4.88
		4	45.22 $\pm$ 3.53	41.04 $\pm$ 3.81
	5	1	18.04 $\pm$ 3.99	32.36 $\pm$ 4.38
		2	28.44 $\pm$ 3.48	36.68 $\pm$ 4.31

Appendix

Table 5: Evaluation of existing methods under possible model misspecification on arbitrary latent-variable models. Ground-truth graphs are generated from the Erdős-Rényi model with total number of vertices

n

and average in-degree

\operatorname{avgdeg}

, with

\ell

vertices randomly designated as latent. Only irreducible models are chosen. Each entry reports the mean and standard deviation of the structural Hamming distances (SHDs) between the result and truth over 50 random models. Algorithms are provided with their oracle tests, that is, for them to directly query oracle generalized independent noise (GIN) conditions from the digraph. When the number of their identified latent variables is fewer than truth, we simply add isolated latent variables into the result. When the identified number of latents is larger (which seems not happened), we planned to choose the removal that leads to best result. Finally, the best possible result is reported, i.e., we choose the digraph in the ground-truth equivalence class that is closer to their output as the truth. The latent variables are viewed as unlabeled.

Figure 7: Simulation results comparing glvLiNG with existing methods with varying sample size $N$ (the global x-axis), and each subplot shows a setting under a specific number of total variables $n$ , number of latent variables $\ell$ , and the average in-degree $d$ . Mean and standard deviation of SHD are calculated from $25$ random irreducible models.

Figure 8: Presentation of the equivalence class that glvLiNG estimates from the stock market data. Different colors of nodes indicate different sectors. Solid and dashed edges indicate edges that must appear in all or at least one equivalent graph(s).

Causal Discovery

Causal discovery infers cause-and-effect structures from observational and interventional data, distinguishing causal relationships from correlation.

See all 221 papers

Causal Discovery beyond Conditional Independence: Identifiability, Algorithms, and Statistical Inference for Directed Acyclic and Cyclic Graphs
Oct 16, 2026Yang NiCausal Discovery Causal Identifiability
Department of Statistics and Data Science, The University of Texas at Austin
Differentiable Structure Learning for Cyclic Linear Gaussian Models with Latent Confounders
Sep 29, 2026Sadegh Khorasani, Ali Najar, Saber Salehkaleybar +1Structural Causal Models Causal Discovery
School of Computer and Communication Sciences, EPFL, Lausanne, Switzerland · Leiden Institute of Advanced Computer Science (LIACS), Leiden University, Leiden, The Netherlands · College of Management of Technology, EPFL, Lausanne, Switzerland
Score-Based Causal Discovery of Latent Variable Causal Models
May 19, 2026Ignavier Ng, Xinshuai Dong, Haoyue Dai +3Latent Variable Models Structural Causal Models
Carnegie Mellon University · University of California, San Diego · Mohamed bin Zayed University of Artificial Intelligence

Oct 16, 2026J/K move · Enter open · S save

Causal Discovery beyond Conditional Independence: Identifiability, Algorithms, and Statistical Inference for Directed Acyclic and Cyclic Graphs

Yang Ni

Department of Statistics and Data Science, The University of Texas at Austin

Causal Discovery Causal Identifiability Causal Discovery with Latent Confounding

Open paper AskPDF arXiv

Learning causal structure from data requires assumptions about mechanisms, noises, observation schemes, and interventions. Historically, causal discovery has relied primarily on conditional independence. This review focuses on modern causal discovery methods that exploit properties of distributions beyond conditional independence. Our organizing principle separates the source of identification from the statistical estimator and its computational implementation. This perspective connects conditional-independence methods with distributional asymmetries, conditional-moment restrictions, and variation across environments or individuals. We examine discovery under latent confounding and feedback, distinguishing causal information about observed variables from reconstruction of latent structure and emphasizing the additional semantics required by cyclic models. We also distinguish population identification, frequentist and Bayesian consistency, uncertainty quantification, and algorithmic guarantees. Throughout, examples show why the same observational distribution can support different conclusions under different model classes. We conclude with guidance for comparing methods at their identifiable targets and a research agenda for uncertainty, heterogeneous populations, non-scalar variables, and the intersection of discrete data, feedback, and hidden confounding.

Abstract

Causal Discovery

Explore similar work

Causal Discovery beyond Conditional Independence: Identifiability, Algorithms, and Statistical Inference for Directed Acyclic and Cyclic Graphs

Differentiable Structure Learning for Cyclic Linear Gaussian Models with Latent Confounders

Score-Based Causal Discovery of Latent Variable Causal Models