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

Oct 16, 2026

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

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.

Yang Ni

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

Causal Discovery Causal Identifiability Causal Discovery with Latent Confounding

Ask PDF

Sep 29, 2026

Differentiable Structure Learning for Cyclic Linear Gaussian Models with Latent Confounders

We study causal structure learning from observational data in linear Gaussian structural causal models in the presence of directed cycles and an unknown number of exogenous latent confounders, bounded by a given maximum. We derive the covariance of the observed variables and introduce marginal quasi-equivalence, which characterizes when different causal models share a full-dimensional subset of the observational distributions they can generate. We formulate structure learning as minimization of the Gaussian negative log-likelihood with a logarithmically scaled complexity penalty that counts directed edges and latent variables. For a fixed number of observed variables and a fixed upper bound on latent variables, we establish consistency of global score minimizers up to marginal quasi-equivalence under algebraic faithfulness, structural minimality, and model-overlap assumptions. We parameterize the inclusion of directed edges and candidate latent variables using Bernoulli gates, whose continuous probabilities are optimized jointly with the structural coefficients. Averaging the penalized negative log-likelihood over these gates yields an objective with a closed-form differentiable complexity penalty. We prove that this expected objective has the same global infimum as the corresponding discrete structure-learning objective. Experimental results show that our approach achieves lower recovery error than previous methods in several experimental settings.

Sadegh Khorasani, Ali Najar, Saber Salehkaleybar +1

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

Structural Causal Models Causal Discovery Causal Structure Learning Causal Identifiability Causal Discovery with Latent Confounding

Ask PDF

May 19, 2026

Score-Based Causal Discovery of Latent Variable Causal Models

Identifying latent variables and the causal structure involving them is essential across various scientific fields. While many existing works fall under the category of constraint-based methods (with e.g. conditional independence or rank deficiency tests), they may face empirical challenges such as testing-order dependency, error propagation, and choosing an appropriate significance level. These issues can potentially be mitigated by properly designed score-based methods, such as Greedy Equivalence Search (GES) (Chickering, 2002) in the specific setting without latent variables. Yet, formulating score-based methods with latent variables is highly challenging. In this work, we develop score-based methods that are capable of identifying causal structures containing causally-related latent variables with identifiability guarantees. Specifically, we show that a properly formulated scoring function can achieve score equivalence and consistency for structure learning of latent variable causal models. We further provide a characterization of the degrees of freedom for the marginal over the observed variables under multiple structural assumptions considered in the literature, and accordingly develop both exact and continuous score-based methods. This offers a unified view of several existing constraint-based methods with different structural assumptions. Experimental results validate the effectiveness of the proposed methods.

Ignavier Ng, Xinshuai Dong, Haoyue Dai +3

Carnegie Mellon University · University of California, San Diego · Mohamed bin Zayed University of Artificial Intelligence

Latent Variable Models Structural Causal Models Score-Based Causal Discovery Causal Discovery Causal Structure Learning Causal Identifiability+1

Ask PDF

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