Distributional Equivalence in Linear Non-Gaussian Latent-Variable Cyclic Causal Models: Characterization and Learning
Authors: Haoyue Dai
Immanuel Albrecht
Peter Spirtes
Kun Zhang
Venue: ICLR 2026 Oral (2026)
Keywords: causal discovery
latent variables
equivalence
rank constraints
linear non-Gaussian models
cycles
Primary area: causal reasoning

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.

Published as a conference paper at ICLR 2026
DISTRIBUTIONAL EQUIVALENCE IN LINEAR NON- GAUSSIAN LATENT-VARIABE CYCLIC CAUSAL MOD- ELS: CHARACTERIZATION AND LEARNING
Haoyue Dai
Immanuel A
Peter Spirtes'
Kun Zhang! 1.3
'Cameegie Mellon University
2 FemUniversitää in Hagen
MBZUAL
ABSTRACT
Causal discovery with latent variables 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 core obstacle to a general, structural- cittiaalaassmptiin--iiii equivalence characterization: without knowing what can identified, one gener- ally cannot design methods for how to identify it. In this work, 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 distributionally equivalent, that is, they induce the same observed distribution set. Key to our approach is 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 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 structuaal-ssumppioonfree discovery method. Code and an interactive demo are available at httttt:::/// /eee:///qquccc
approach is the lack of an
INTRODUCTION
At the core of scientific inquiry lies causal discovery, the task of learning causal relations from observational data (Spirtes et al. (0000/Pear) 2009). many real-world scenarios, the variables of interest can be unobserved. For instance, in psychology, personality traits are hidden behind survey responses, and in biology, crucial regulators may be unobserved due to technical inaccessibility. Discovering the causal strueture with these latent variables, referred to latent-variably causal discovery, is essential for understanding and reasoning, yet remains a challenging task.
variiale causal discovery has seen significant development over the past three decades. A milestone was the Fast Causal Inference (FCI) algorithm (Spirtes) 1992), which exploits conditional independence (CI) constraints under hidden confounding. However, FCI is typically not regarded as method of latent-variable causal discovery, as it focuses solely causal relations among observed variables, with no intension or capability to identify those among latent variables. In fact, though FCI
is already maximally informative under nonparametric CI constraints (Richardson & Spirtes 2002 Zhang 2008a), it still not informative enough for recovering latent structure.
This limitation has motivated the development of many recent approaches that go beyond CI con- straints, typically by introducing parametric assumptions, such as linearity (Silva al. 2003 Dong et al. 2024), non-Gaussianity (Hoyer et al. 2008 Jin et al.] (024), mixture models (Kivva et al. 2021 and distribution shifts (Zhang et | 2024). Within each setting, a rich array of techniques has emerged.
For example, in the linear non-Gaussian setting alone, methods have been developed based on over- complete independent component analysis (OICA) (Salchkaleybar et al. (2020), regression (Tashiro)
al. 2014). Bayesian estimation (Shimizu & Bollen 2014), independence testing (Xie et al. 2020). cumulants (Robeva & Seby 2021). independent subspace analysis (Dai et al. 2024), and many more.
However, despite this prosperity, most methods share clear limitation: they rely structural assumptions, often about how latent variables are indicated and how they can interact with others.
Common examples include measurement models where observed variables have to be pure measure-

---

Published as a conference paper at ICLR 2026
ments of latents (Silva & Scheines,
2004 Zhang et al. 2018); hierarchical models that prohibit effects from observed variables (Choi et al. 201 Huang et al. 2020): sufficient number of pure children per
latent (Squires al. [2022] in et (024); and assumptions like triangle- or bow-freeness (Dong
et al. 2024 Wang & Drton 2023). In addition, most methods also assume acyclicity, even though
feedback loops are common in real systems. These assumptions, often overly strong and untestable, not only limit applicability but also complicate method selection for practitioners.
A pressing question naturally arises: after decades of progress, is it possible now have general pructural-assumptiinn
approach for latent-variable causal discovery that, like FCI, allows arbitrary relations among latent and observed variables, yet goes beyond FCT's limited informativenes?
One core obstacle, we argue, is the lack of a general equivalence characterization with latent variables. Equivalence is a notion fundamental to causal discovery: when different causal models induce the same observed distribution set (known as distributional equivalence), no method can, or should, distinguish among them, without extra information like interventions or sparsity constraints. The expected discovery output is thus the entire equivalence class, the best one can hope to identify from data. In practice, equivalence can also be defined more coarsely, depending on the specific constraints used. One example is Markov equivalence, capturing when models entail the same CI constraints. A well-known and nice result is that in causally sufficient, acyclic, and nonparametric models, Markov equivalence coincides with distributional equivalence (Spirtes et al., 2000); the resulting equivalence class is represented by a completed partially directed acyclic graph (CPDAG).
In the presence of cycles or latent variables, however, equivalence characterization becomes more complex. For example, the nice coincidence between Markov and distributional equivalences breaks down, even with only cycles (Spirtes 1994 Mooij & Claassen| 2020), or only latent variables (Vermal & Pearl 1991 Richardson et al. (023), , let alone both. The resulting equivalence classes, be it
Markov Richardson & Spirtes| 2002 Claassen Mooij. 2023) or distributional (Nowzohour et al.,
2017 Evans 2018). also become far more complex. Such complications carry over to parametric settings: for cycles alone, distributional equivalence has been characterized in linear non- Gaussiann and Gaussian models (Lacerda et al.; 2008 Ghassami et al. [020);; yet for latent variables, no characterization of any kind, whether distributional or constraint specific, is currently known to us. The closest result (Adams et al. [202I) gives conditions for when linear non-Gaussian acyclic model can be uniquely identified, but leaves open describing the equivalence when such identifiability fails.
All such complications from latent variables and cycles have so far prevented general equivalence characterization, which is exactly what obstruct progress towards a structural -astuuralllssmmtionnn... The need for such characterization is yet clear: without knowing what can be identified, one gen- erally cannot design methods for how to identify it. This is echoed in history: PC algorithm followed CPDAGs; FCI's guarantee followed maximal ancestral graphs (MAGs) (Richardson & Spirtes 2002).
method.
Our goal in this work is hence to overcome these challenges and establish a general equivalence notion with latent variables and cycles. We focus linear non-Gaussian models, parametric setting that has received much attention. Under this setting, we address three questions: 1) When are two graphs with arbitrary latent variables and cycles equivalent? 2) How one traverse the entire cquivalence class? 3) How can one recover latent- variable models up to equivalence from data?
Centered around these three questions, our contributions are summarized follows:
1. We present a general equivalence notion that allows arbitrary latent structure and cycles in linear non-Gaussian models. This is the first such result known us in any parametric setting ($2).
2. We introduce new tool, edge rank constraints. It contributes a missing piece to the broader toolbox for latent- variable causal discovery, with potential use across many settings ($3)
3. We characterize equivalence graphically and provide procedures to traverse the entire class. Re- sults are cleaner than expected. We provide an interactive demo at wtlnttps:///equeete
cc 4
4. We develop an efficient algorithm to recover the equivalence class from data, which is, to our knowledge, the first structural- -asppupoalsssmmiiiooo-reeeee method for latent-variable causal discovery (55)
2 PROBLEM SETUP
In this section, we lay the groundwork for our study. In 1 define the notion of distributional equivalence in linear non-Gaussian latent-variable causal models. Then in 222 we introduce the idea of irreducibility to rule out trivial cases, clearing the way for the main results come.
2

---

Published as a conference paper at ICLR 2026
2.1 PRELIMINARIES FOR LINEAR NON- GAUSSIAN MODELS
Notations on matrices. For a matrix M, we let Ma,5 be its (i, entry. For two index sets A, B, we let MA,B (M..)) be the submatrix of M with rows indexed by A and columns indexed by B. We let MA,: be the rows in M indexed by A, and similarly M. for the columns. For finite set A, we denote its cardinality by |A]. We denote by Scale(d) d) the set of all d diagonal matrices with nonzero diagonal entries, and by Perm(d) the set of all d x d permutation matrices. For permutation æ V V on ground set V, we denote (F) = {ir(i) : F} for any set F S V, and extend this notation to families of sets by TT)) == (x F F for FCC.
directed graph that may contain cycles but no self-loops (edges from a vertex to itself). In digraph G, let V(G) be its vertex set. For vertices a, we say a is a parent of and b is child of a, denoted by a E pag(b) and b E cha when + b is an edge in G, written a + b E G; is an ancestor of b and b descendant of denoted by a E ang(b (6) and b E deg (a), when a = or there is a directed path a - - b in g. These notations extend to sets: e.g., for vertex set A. ang (A) UBEA (n)
Notations on graphs. Throughout, by digraph we refer
Linear non-Gaussian (LiNG) causal models. We consider a linear non-Gaussian model associated with digraph G, in which random variables V = (V1, Vvj)" corresponding to the vertices of g, are generated according to the structural equation:
V BV + +E,
where = (Fi,..., Fiy ) consists of mutually independent, non-constant, non- non-Gaussian exoge- nous noise terms. The matrix B B(G) weighted adjacency matrix (whose entries represent direct causal effects) that follows G. where B(G), all adjacency matrices that follow G, is defined as:
B(g)= = {B E g Bv #0 = - V3 E G}. Assuming 1 - B is invertible, solving for Equation ① gives equivalent mixing form:
(2)
V = (I- B) = AE, where A is called the weighted mixing matrix. The entry Av, v. represents the total causal effect from V; to Vj. All mixing matrices that follow G, denoted by A()), defined as:
(3)
A(G) -)- B E B(G), 1 B invertible).
Latent-variable LiNG models. Let the vertices V of a digraph 9 be partitioned as V = TUX where T. denotes latent (unobserved) variables and X denotes observed variables. A latent-variable model is specified by the tuple (g, X), with latent variables L omitted when clear from context.
Given a full mixing matrix A E A(g). the submatrix Ax, E R x [VI maps exogenous noise terms to the observed variables. The collection of such wide rectangular mixing matrices is defined as: X) = {Ax:: : E A(G)).
(5)
Accordingly, the induced observed distribution set of G on X, that is, the set of all distributions over X that can arise from a LiNG model over X), denoted P(g, X). given by:
X) = {p(X): X = AE, A X)) E E NG((V)),
(6)
where p(X) denotes the probability distribution of the random vector X, and NG(d) denotes the set of all d-dim random vectors with mutually independent, non-constant, and non-Gaussian components.
We now ready formalize the central notion of this work: distributional equivalence. Definition 1 (Distributional equivalence). Let and H be two digraphs with possibly different vertices, and X C V(G)NV (H) be the shared observed variables. We say G and H. are distributionally equivalent (or for short, equivalent) on X, denoted by g X H. when P(g, X)= = P),,
The equivalence (Definition D captures when two models yield identical observed distribution set, i.., observationally indistinguishable. With this notion in place, next we clean up some trivialities.
2.2 IRREDUCIBILITY: TO FIRST RULE OUT TRIVIAL CASES OF EQUIVALENCE
To study identifiability, let us first see what is inherently non-identifiable. For instance, one can freely add latent vertices that are not ancestors of any observed variables X to a digraph g without affecting P(G. X), yielding trivially equivalent models. Identifying those latents is both impossible and meaningless. To rule out such trivialities, we introduce the notion of irreducibility.
3

---

Published as a conference paper at ICLR 2026
L
L
reduce
reduce
reduce
X
X1
X2
X1
X3
X2
Figure I: Examples of reducing models to their irreducible forms via the procedure in Proposition Throughout, white circles denote observed variables and grey squares denote latent variables.
2
Definition (Irreducibilitt). We say a latent- model (9, irreducible, when there exists digraph H. with [V(H) < [V()) such that 9 H.
Irreducibility captures when an observed distribution set cannot arise from any other model with fewer latent variables. We now present a simple graphical condition for this property.
Proposition (Graphical condition for irreducibility). A model (g. X) is irreducible, if and only for each non-empty set 1 L, chg (1) 41 2 2, ie.,, has more than child outside.
Note that when G is acyclic, it suffices to check each single L; E L. consistent with the condition previ- ously derived by SSaehkaaleyaar et 2020). The proof of Proposition along with others, provided in Appendix [B] The key idea here is that any violation of the condition leads to proportional columns in mixing matrices AGG, X), so that the observed distributions can be equivalently generated by a smaller graph with these columns merged to one. Conversely, identifiability results of OICA (Eriksson & Koivunen 2004) suggest that as long as in the absence of such proportional columns, the mixing matrix is identifiable up to column scaling and permutation, the number of latents is identifiable.
We next provide an explicit procedure for reducing an arbitrary model to its irreducible form.
Proposition (Procedure of reduction to the irreducible form). Given any latent-variabls model X), the following procedure outputs digraph H such that H X G and (H, is irreducible. Step I. Initialize as G.
Step 2. Remove vertices ((H) \ (X) from H. i.e., remove latents who have no effects on X.
Step 3. Identify the maximal redundant latents in the remaining latent vertices:
mrl == S V(H))X [1] > 0, |chx (I) < 2, and vt' 21, (chx(t)))( 2 27. (7)
Step 4. For each E mrl, let e be the exact child in chx( (I) for each parent p E pa (L)))..) add an edge p + into if not already present: finally, remove I vertices from H.
Illustrative examples of this reduction are shown in Figure T This reduction lets without loss of generality, restrict attention to irreducible models for the remainder, as arbitrary models are equivalent if and only if their irreducible forms are equivalent. Note that irreducibility is not structural assumption as discussed in T but rather a canonicalization to eliminate trivialities. As a side note, applying the reduction in Proposition 2 does not increase the number of edges or cycles.
DEVELOPING GRAPHICAL TOOLS FOR CHARACTERIZING EQUIVALENCE
In the previous section, we defined distributional equivalence and irreducibility rule trivial unidentifiable cases, so we can focus solely on irreducible models in what follows. Then, when are two irreducible models equivalent? In this section, we tackle this question step by step.
Specifically, in $3.1 we first show that distributional equivalence reduces to an algebraic condition on mixing matrices, and further to graphical condition involving concept familiar the community: path ranks, given by max-flow-min-com to work with due their global, non-local nature, as we illustrate in $3.2 To overcome this, we introduce new tool: edge ranks, local, edge-level constraint that complements path ranks and is easier to manipulate. This new tool, developed in $3.3) not only enables our final result to come in the next section, but also enriches the broader rank-based picture beyond our specific setting.
in digraphs. Although familiar, path ranks are difficult
3.1 EQUIVALENCE VIA PATH RANKS
We start by examining the algebra behind distributional equivalence. By Definition all equivalent irreducible models must have the same number of latents. This follows from OICA, which guarantees
4

---

Published as a conference paper at ICLR 2026
exact recovery of the number of (nontrivial) latent variables. Hence, in what follows, when considering the equivalence of two irreducible models (G, X) and (H. X), we can, without loss of generality, denote their latent variables by same set of labels, so that V(G) (HH) = U.L.
We then observe that distributional equivalence can be rephrased in terms of the mixing matrices: two models are equivalent if and only if for every mixing matrix one model can generate, the other can also generate a version of it up to column scaling and permutation, and vice versa, due to the scaling and permutation closedness of exogenous noise terms. Formally,
Lemma 1 (Equivalence via mixing matrices closure). Two irreducible models are equivalent, written 9 X H. if and only if A(G, = A(H, X), where for a set of matrices A C R.mxd we let: A {APD: A E A, P E Perm(d), D Scale(d)), that is, the closure of A up to column scaling and permutation.
(8)
Then, what are exactly these mixing matrices, namely, A(), As defined in Equations (2) to it arises from mapping over the free parameters in adjacency matrices. Concretely, each entry of the mixing matrix is a rational function: the numerator polynomial reflects "total causal effects" between variables, and the denominator polynomial accounts for "glohal cycle discounts", which is simply 1 when the digraph is acyclic. In cyclic cases, there is small pathological locus where denominators vanish, that is, where 1 B becomes singular and cycles "cancel themselves." But as we will show in the proof, this does not affect our results. So for now, let us progress with the Zariski closure of A(g, X). an algebraic variety that can be defined by finitely many equality constraints.
We now study these constraints. One fundamental class of them is the so-called rank constraints, which admits a nice graphical interpretation in terms of max-flow-nie foow-min-cutt in digraphs, defined below:
Definition 3 (Path ranks). In digraph G. for two sets of vertices Z, Y C VG),, the path rank Pa Z, Y) is defined as the maximum number of vertex -dijoontt directed paths from Y to Z in g. By (Menger 1927). this max-flow quantity can also be defined by its min-cut version:
Pg Y) min {|e]: c's removal from G ensures no directed path from c [cc). (9) eCV(g)
These purely graphical quantities can be read off from the mixing matrices by examining the matrix ranks of corresponding submatrices, which is the well-known (path) rank constraint:
Lemma (Path rank constraints in mixing matrices). In a digruph 9, for any two sets of vertices Z, Y C (G) that need not be disjoint, the following equality holds for generic choice of A E A(G):
rank(Az,y)
(10)
Here, rank denotes the usual matrix rank, and "generic" means the equality holds almost everywhere except for a Lebesgue measure zero set where coincidental lower matrix runks occur.
Rank constraints bridge algebra in matrices with geometry in digraphs. They were initially proved for acyclic graphs only (Lindström) 1973; Gessel & Viennol 1985), and later generalized by (Talaska 2012). They are powerful: we will show in the proof. rank constraints alone, together with column permutation, suffice to determine equivalence. We directly state the result below:
Lemma 3 (Equivalence via path ranks). Two irreducible models are distributionally equivalent, written& G X H. if and only if there exists permutation over the vertices VG)). such that (Z) = (Y)) for all Z C X and Y C V(g).
(11)
From Lemma T to Lemma 3. so far we have arrived at first purely graphical view of equivalence.
3.2 THE COMPLEXITY OF MANIPULATING PATH RANKS
In $ we have arrived at Lemma a purely graphical characterization of equivalence, which, perhaps surprisingly, is expressed in terms of a familiar concept: path ranks. However, this is only a start and far from operational: verifying it requires searching over all vertex permutations and all (Z, Y) pairs, which quickly becomes intractable due to their factorial and exponential growth, let alone the costly graph traversal required for each single path rank computation. As an analogy to the acyelic, causally sufficient case, Lemma 3 is like saying "having all the same d-separations." " whereas what seek is something simpler and more local, like "same adjacencies and v-structures."
5

---

Published as a conference paper at ICLR 2026
Y1
Y2
C
C2
Y3
Y
Ym
m
C
TX
X
X
X
X
C2
X
X
OOX
X
21
0
X
Z2
0
0
C
Z
Z2
Zm
Z1
Zn
Figure 2: An illustration of path ranks, edge ranks, and their duality. Left: a digraph 9 with vertices V partitioned Y. C. and Z, shown by different colors. The path rank po Y) with C' being a min-cut. Right: the dual edge rank (Y Z\Z) = 4, given by the maximum bipartite matching from Z Z V.Y, i.e., from Y T to C, with four matched edges highlighted in red. Four corresponding nonzero entries placed on diagonal, also in red, confirm mrank V. v.z) = 4. One may examine the duality in Theorem w.l.o.g. let S there is m - 2 m m++n--
(Q
4.
Then, does simpler local condition naturally follow from Lemma 3 Unfortunately, not quite. Path ranks are hard to work with due to their global nature: they summarize the size of "bottlenecks", but say nothing about which paths are involved how they interact. Each single edge may lie multiple bottlenecks, so even a small local alteration to digraph may trigger unpredictable global changes in path ranks. Conversely, with latent variables, seemingly very different digraphs can still share the same path ranks. We illustrate such complexity with the following example.
Example (Complexity of viewing equivalence via path ranks). Consider the digraph G on the left of Figure with vertices partitioned into Y, C, and Z. Obviously, the path rank Pg (c Y) = 2. Now, suppose vertices {C1, C2} become latent and all others remain observed. What models equivalent? This is not obvious anymore. It usually takes some thought to realize that adding edges or cycles within C. or removing one or two edges from
Z, still preserves path ranks as in Lemma B What about the Y to C' structure then? This is more subtle: when > 2, it must remain fixed; but when n C is no longer a unique bottleneck, and suddenly, Y can point freely to both C and Z.
Things become even less intuitive when other variables are latent. For example, with m = n = 4. if {Ci, C2) are latent, there are 17 digraphs the equivalence class (view them online). When (Yi, Y2) or (Vi, C1) } are latent, this number comes to 872 (view) and 1, 0,024 (view), respectively. Note that all this comes from a well structured digraph; arbitrary structures only lead to greater complexity. A
Example iillustrates the complexity of path ranks in inferring graph structures. In fact, this complex- ity is well recognized in literature: despite various techniques developed to estimate path ranks from data (Dai et al. 2022 Sturma et al. 22044) and well-studied counterparts in the linear Gaussian (Sul- livant et al. 2010) and discrete settings (Chen et al. 2024b) or even with selection bias (Dai et al. 2025b), when it comes to structure learning from ranks, usually restrictive structural assumptions are required to ensure clean interpretation to where and how these paths can be.
All observations above motivate question: is there more local, graph-manipulate alternative to path ranks, not just for building equivalence in this work but also as a piece in the broader toolbox? Interestingly, the answer is yes, and we develop such a tool next: edge ranks.
3.3
EDGE RANKS: A NEW TOOL IN THE RANK- BASSB PICTURE
We now introduce a new tool: edge ranks. As the name suggests, edge ranks directly operate on edges in digraphs, which is more local and accessible in contrast to the paths used in path ranks. For intuition, one may refer to Figure which illustrates all the concepts and results below.
Let us first define edge ranks, similar to how define path ranks previously in Definition 3
Definition 4 (Edge ranks). In a digraph G, for two sets of vertices Z, Y C V(G), the edge rank rg Y) is defined the size of the maximum bipartite matching from Y to Z via edges in G. where self-matches (a to a for a E Y n Z) are allowed. Edge ranks also admit a min-cut version:
min ro( = vCY, =uy22ny
{|2]
|y/ there is no edge from Y y to 7\z in 9). (12)
In parallel to how path ranks correspond to matrix ranks of mixing submatrices (cf. Lemma 2 the pure graphical quantities of edge ranks also have their algebraic counterpart. This time, it is not the mixing matrices at play, but directly the adjacencies.

---

Published as a conference paper at ICLR 2026
For clarity, let us introduce matrix notation, Q. in addition the already familiar notations of B and A, and a new notion of matching ranks, in addition to the already familiar matrix ranks.
Definition 5 (Support matrix). For a digraph G. its binary support matrix in shape [V(9)) (V()), denoted Q is given by:
Vy x V, = V3 or V; + V3 E g, and 0 otherwise.
(9)
(13)
Definition (Matching rank of a matrix). The matching rank of a matrix M E mkmx is given by:
mr) =
max Li=ii--..iin(m... ((MP)) + 0).
(14)
PEPerm(N)
In simple terms, the matching rank of a matrix, denoted mrank, is the maximum number of nonzero entries that can be positioned the diagonal by permuting its columns (or rows).
We can now give the edge rank constraints, as a counterpart to path rank constraints (cf. Lemma 2 Unlike the algebraic efforts required there, this result follows immediately from definition:
Lemma 4 (Edge rank constraints in support matrices). In a digraph G. for any two sets of vertices 7, Y C V(g) that need not be disjoint, the following equality holds:
mrank(QZ.))
rg(2,
(15)
So far, we have defined both path ranks and edge ranks, which first glance appear so different: graphically, one is global, focusing on paths, while the other is local, operating on edges; algebraically. one is tied to weighted mixing matrices, the other to binary support matrices. However, despite these apparent differences, a surprising and elegant duality exists between them:
Theorem 1 (Duality between path ranks and edge ranks). In a digraph 9 with vertices V. for any two sets of vertices Z, Y C V that need not be disjoint, the following equality holds:
min ( [Z] Y)) Pg( |V| max (x1) (V VVZ).
(16)
This duality is powerful: it suggests that every statement phrased in terms of path ranks and its variants, including the familiar d-separation and t-separation. can be equivalently rephrased in terms of edge ranks. It reveals that, despite the very different graphical objects involved in the two ranks, they offer complementary perspectives on a same notion in the digraph, namely, bottleneck, which captures how dependencies arise in observed data, and is thus central to causal discovery.
In fact, this duality has long been studied in the matroid community (König 1931 Perfect 1968 Ingleton& & Piff 1973), while only the path rank side has been well known in causal discovery. We thus introduce edge ranks here, filling the other side to the lank-based toolbox. It is not that edge ranks always better, but having both perspectives is beneficial. Within this work, edge ranks indeed lead to simpler derivations. For instance, let us rephrase Lemma 3 using edge ranks below: Lemma 5 (Equivalence via edge ranks). Two irreducible models are distributionally equivalent, written G X H. if and only if there exists permutation over the vertices V(G), such that (2 Y) r (x), for all Z,Y C VG) with L Y.
(17)
As we will see in the next section, this formulation paves the way to our final criterion for equivalence. To conclude this section, we provide side-by-side comparison of two ranks (Table Appendix C.I
4 THE GRAPHICAL CHARACTERIZATION OF DISTRIBUTIONAL EQUIVALENCE
In previous sections, through step-by step-by-step breakdown of equivalence, we have arrived at key result, L3mma which, notably, is framed by a new tool we introduced: edge ranks. Building on this founda- tion, in this section, we provide our final graphical criterion for distributional equivalence, and present a transformational characterization that enables traversal of all digraphs in the equivalence class.
We first study the task of deciding whether two given models are equivalent. For this purpose, although 3 a more local condition for each rank check, it still requires a large number of total checks: one must go through all sets Y 2 L, which amounts to all subsets æ C X. As noted in our earlier analogy ($3.2), this remains akin to "same d-separations." instead of a practical criterion like "same adjacencies and v-structures."" Then, does Lemma yield such practical criterion?
7

---

Published as a conference paper at ICLR 2026
Fortumately, this time, the answer is yes. Unlike the complexities encountered with path ranks in $3.2 edge ranks allow Lemmaãjt admit a nice local decomposition: instead of checking all subsets æ S X. it suffices to check each singleton X; E X independently. This yields our final graphical criterion:
Theorem 2 (Graphical criterion for distributional equivalence). In digraph G, we define the "children bases" of a vertex set Y C V9) as vertex sets that admit perfect edge matchings from Y: basesg(Y)
{Z S cha(Y) rg(Z,Y)= = |
(18)
Then, two irreducible models (G) X) and (H, X) are distributionally equivalent, if and only if there exists a permulation over the verlices VG),, such that the following conditions hold:
bases; (L) = ((bases (L)). and (LU =x (baaesH (x.))) for each X₃ E X.
(19)
To interpret this criterion, let us consider the causally sufficient case where I, = 2. In this case, each basesg [X.)) is just X, with its children. Then, Theorem 2 immediately reduces to the classical result of exact digraph identification up to permutation (Lacerda et al. 20088. Interestingly, that result has recently been revisited also from a bipartite matching view used here (Sharilian al. 2025).
Having established Theorem 2 as an efficient criterion for determining equivalence, we now turn to another task of traversing all digraphs in an equivalence class. For this purpose, however, a determin- ing criterion alone offers little guidance. Again, we recall the analogy with Markov equivalence. Note that except for the criterion "same adjacencies and v-structures," there an alternative characteri- zation: "two acyelic digraphs are equivalent if and only if one can reach the other via sequence of covered edge reversals," " known as "Meek conjecture" (Meek) 1997). Such a transformational characterization offers natural way for equivalence class traversal. In light of it, we next develop such a transformational characterization, analogous to "Meek conjecture" for our setting.
We start with the permutation part in Theorem 2 which corresponds to row permutations to the support matrix Q(9), Such permutations must result in valid support matrices, i.e., ones with nonzero diagonals. By cycle decomposition of permutations, this leads to an observation: disjoint cycles in the digraph can be freely reversed without affecting equivalence. Formally:
Lemma 6 (Admissible cycle reversals). For digraph G, let C be any collection of vertex-disjoint simple cycles in G. Define a new digraph H where for each edge V; + V, E G:
1. 1fV; - V3 is on a cycle in C, then include V, - V; in Hi 2. Otherwise, V; is cycle in C with the predecessor Vi - Vj, then include V; Vo in H: Otherwise, simply include Vg + Vg in H.
Then, with this new H. the equivalence G X H still holds, for every X C (9).
This result was also shown by (Lacerda al. 2008 It highlights that in the linear non-Gaussian set- ting, cycles do not introduce substantial complexity. One may illustrate it using examples in Figure 3
We then examine a more subtle part in Theorem [ concerning edge rank equivalence, that is, when all the involved perfect bipartite matchings via edges are unchanged. Intuitively, it is about how edges structurally "crucial" for maintaining matchings. This leads to the following criterion about edge additions or deletions, corresponding to flipping entries in the support matrix:
Lemma 7 (Admissible edge additions/delettions). Let (G.X) X) be an irreducible model. For any edge V --,; V, not currently in G, adding to preserves equivalence on X if and only if:
rg(Vi's 's nonchildren', (V1}, (X(()) < rgg(V'ss 's nonchildren, LA(V.)),
(20)
where Vi's nonchildren denotes V(G), chş (Vs((V)))) (V.).V,), i.e., zero entries in support column Conversely, an edge can be deleted if and only if can be re-added by this criterion.
Q.v--
In layman's term, Lemma 7 says that an edge V, + V3 can be added, only when in the bipartite graph from latents to all vertices currently not V,'s children (including V,), V, stands as a "pillar" across the maximum matchings; in matroid terms, it is coloop. Then, since Vú is already "pillar", adding this edge will not be noticed by any containing latent variables. Note that both V; and V, may be in X or L: edges can be added within each or in either direction. Let us examine example.
8

---

Published as a conference paper at ICLR 2026
91
L
L2
G2
L
L2
G3
L
Edge +/-
Edge +/-
X
XI
Xa
X
Xa
Cycle reversal
Cycle reversal
G1
go
Go
Edge +/-
Edge +/-
X3
Figure 3: An example distributional equivalence class consisting of 6 digraphs up to L-relabeling.
Example (lllsstratnng edge additions via Lemma 7). We consider the digraph G1 in Figure 3 and check why the edge X2 + L2 can be added. From L \ [{2] {L1, L2} to X2 's nonchildren {L1, L2, X1}. there a full matching of size 2. with (L1, L2) matched to either (L1, or (X1, L2). Since L2 appears in both a "pillar", adding X₂ - L2 preserves edge ranks. In contrast, X2 L1 cannot be added, which, for instance, will change rg, L1 L2, X1), [L,, X2]) from 2 to 3. A
We have introduced two graphical operations that preserve equivalence, namely, cycle reversals and edge addittions/deletions.. Remarkably, these two operations are not only sufficient but also necessary: together, they fully characterize equivalence. This brings us to our transformational characterization:
Theorem 3 (Transformational characterization of the equivalence class). Two irreducible models (G, X) and (H, are equivalent if and only if G can be transformed into H. up to L-relabeling, via a sequence of admissible cycle reversals and edge additions/deletionss as defined in Lemmas 6 and
Here, "up to L-relabeling" means there exists a relabeling of L in 'H yielding a digraph Ht' such that G reaches H!' via the sequence. Moreover, at most one cycle reversal is needed in this sequence.
Thanks to this transformational characterization, Theorem 3 offers a natural way to traverse an equivalence class by e.g., rumning BFS DFS over the space of digraphs connected via admissible operations. Such equivalence class structures are illustrated by Figure 3 Figure 5
(Appendix C.2).
and more in our (online demo Note that this traversal can be further accelerated implementation, by traversing each vertex's 's children independently in parallel (Lemmas and 12 Appendix B
Finally, let return once more to the analogy with Markov equivalence. We have established counterparts of both "same adjacencies and v-structures" and "Meek conjecture". A natural question is then whether counterpart of the CPDAG, an informative presentation of the equivalence class, can also be developed. The answer is again yes. We show that within each cycle-reversal configuration, there exists unique maximal equivalent digraph of which all others are subgraphs. We further provide efficient criteria to construct this maximal digraph, and to determine edges invariant across the equivalence class (similar arrows CPDAG). Due space limit, this result is presented in Theorem 4 (Appendix C.3). To conclude this section, we provide a side-by-side overview that places our results with their analogues across various classical settings (Table Appendix C.5)
ALGORITHM AND EVALUATION
In this section, we develop structural- -assaaattoon-frreeeee algorithm to recover the underlying causal models from observed data up to distributional equivalence. We name this algorithm as general Jatent- variable Linear Non-Gaussian causal discovery (glvLiNG). Evaluation results are also provided.
stractural-assuuptiion
Algorithm. The glvLiNG pipeline consists of three main steps: it first runs OICA on data to estimate a mixing matrix A, then constructs a digraph & to realize rank patterns in A, and finally, starting from G. traverses the equivalence class using the procedure introduced in Theorem 3 Under the assumptions of access to oracle OICA and faithfulness (no coincidental low ranks in the mixing matrix beyond those structurally entailed; formally stated in Assumption at Appendix (A), gIvLiNG is guaranteed recover the entire class of irreducible models equivalent the ground-truth model.

---

Published as a conference paper at ICLR 2026
Proofs and detailed formulations of the glvLiNG algorithm are deferred to Appendix A for page limit. Here, we briefly highlight the core second step: constructing a digraph to realize the observed ranks.
The main challenge lies in this second step, rank realization task. While the satisfiability nature of this task may suggest brute-force solutions like integer programming, glvLiNG instead offers a more efficient munstraint-based approach. Specifically, it proceeds in two phases. Phase 1 recovers edges from latent variables L to all variables V. which reduces to a bipartite realization problem known in matroid theory. Phase 2 is more delicate: recover edges from observed variables X to V. This may seem combinatorially complex at first glance, since all ranks induced by all subsets of X must be jointly satisfied (Lemma 3). Fortunately, as we have shown in Theorem 2 these global constraints admit a local decomposition, allowing each single X; 's outgoing edges to be recovered independently. To recover these edges, we give an explicit construction (Lemma 10 in Appendix (A) based directly on querying ranks in the OICA mixing matrix, with no need for solving complex constraint systems.
Evaluation. We evaluate our approach from five aspects: 1) quantifying the sizes of equivalence classes, 2) assessing glvLiNG's runtime, 3) benchmarking existing methods under oracle inputs, 4) evaluating glvLiNG's performance in simulations, and 5) applying glvLiNG to a real-world dataset.
For 1), we quantify the sizes of equivalence classes, in order to provide an illustrative sense of the uncertainty in variable models. We exhaustively partition digraphs with up to 6 vertices under various latent configurations. For example, there are 1, 027, 080 weakly connected digraphs with 5 ver- tices, of which 26, 430 are acyelic. When the first 2 vertices are latent, 480, 640 of these digraphs yield irreducible models, which finally form 783 equivalence classes. Full statistics are shown in Table 3
For 2), we assess the efficiency gain enabled by gIvLiNG's the execution time against linear programming baseline for constructing digraphs to satisfy ranks of oracle OICA mixing matrices. Results confirm substantial speedup: glvLiNG solves cases with 10 vertices in under 5s, while the baseline takes hours beyond n Full results in Table
ceastraint-basse design. We compare
For 3), we examine how existing methods behave under structural misspecification by applying them to arbitrary latent-variable models possibly beyond their assumptions. We evaluate LaHiCaSI (Xie) et al. 2024) and PO-LiNGAM (Jin et al. 2024). given oracle access to their required tests. Both meth- ods tend to produce overly sparse graphs and misidentify over half of the edges. Full results in Table 5
For 4), we evaluate glvLiNG with existing methods under finite samples. We simulate data from random irreducible models, varying numbers of observed and latent variables, graph density, and sample size. We observe that gIvLiNG performs particularly better than baselines on denser graphs and stays more robust to latent dimensionality, likely due to avoiding model misspecification, while baselines perform better on sparser graphs. Full setup and results are provided in Appendix (.4]
For 5), we apply gIvLiNG to a real-world dataset of daily stock returns (Jan 2000-Jun 2005) from 14 major Hong Kong companies spanning banking, real estate, utilities, and commerce. glvLiNG recovers meaningful patterns, such as major banks acting as central causal sources. The two latent variables recovered seem also to admit plausible interpretations. Full results are in Appendix D.5
Final remarks. We conclude with a reflection on the use of OICA in glvLiNG. While one may be concerned about OICA's known inefficiency in practice, we would like to note that the main focus of this work is to characterize distributional equivalence. The givLiNG algorithm serves more as a proof of concept, showing that such equivalence is indeed recoverable without any structural assumption.
That said, we do see two promising directions for future improvement. 1) For estimation, several existing methods allow partial access to rank information in the mixing matrix without explicitly running OICA. They could be integrated into givLiNG 2) For algorithmic efficiency, while gIvLiNGG already scales well, further pruning is possible. For instance, Theorem 3 implies that ancestral relations among observed variables are identifiable, which may help reduce the search space.
CONCLUSION AND LIMITATIONS
In this work, we provide a graphical characterization of distributional equivalence for linear non- Gaussian latent-variable models. Based on it, we develop a constraint- based algorithm, glvLiNG, that recovers the underlying model up to equivalence from data without any structural assumptions. Central to our approach is the introduction of edge rank constraints, a new tool in the rank- picture. One limitation is the use of OICA in gIvLiNG, as discussed above. Future directions include developing OICA-free algorithms, and extending new tools to broader settings like linear Gaussian systems.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENT
We would like to acknowledge the support from NSP Award No. 2229881, Al Institute for Societal Decision Making (AI-SDM), the National Institutes of Health (NIH) under Contract RO1HL159805, and grants from Quris AI, Florin Court Capital, MBZUAI-WIS Joint Program, and the Al Deira Causal Education project. We also thank the anonymous reviewers for their helpful suggestions.
Large Language Models Usage: the sentence level.
We used large language models only to aid or polish writing, at
Ethies Statement: This paper presents work whose goal is to advance the field of causal discovery. We do not see any ethical or societal concerns that need to be disclosed.
Reproducibility Statement: We provide code for our algorithm, glvLiNG, along with an interac- tive demo for traversing equivalence classes, available at attttts::/
REFERENCES
Jeffrey Adams, Nicls Hansen, and Kun Zhang. Identification of partially observed linear causal models: Graphical conditions for the Con-Gaussian and heterogeneous cases. Advances in Neural Information Processing Systems, 34:22822-22833, 2021.
Ayesha R Ali, Thomas Richardson, Peter Spirttss and Jiji Zhang. Towards characterizing Markov equivalence classes for directed acyelic graphs with latent variables. arXiv preprint arXiv: 1207.1365, 2005.
Carlos Améndola, Mathias Drton, Alexandros Grosdos, Roser Homs, and Elina Robeva. Third-order moment varietics of linear Son-Gaussian graphical models. Information and Inference: Journal of the IMA, 12(3); iaad007, 2023.
Carlos Améndola, Tobias Boege, Benjamin Hollering, and Pratik Misra. Structural identifiability graphical continuous łyapunov models. arXiv preprint arXiv:2510.0490 2025.
Animashree Anandkumar, Daniel Hsu, Adel Javanmard, and Sham Kakade. Learning linear Bayesian networks with latent variables. In International Conference on Machine Learning, pp. 249-257. PMLR, 2013.
Steen Andersson, David Madigan, and Michael D Perlman. A characterization of Markov equivalence classes for acyelic digraphs. The Annals of Statisties, 25(2):505-54) 541, 1997.
Bryan Andrews, Peter Spirtes, and Gregory F Cooper. On the completeness of causal discovery in the presence of latent confounding with tiered background knowledge. In International Conference on Artificial Intelligence and Staristics, pp. 4002-4011. PMLR, 2020.
Thomas H. Brylawski. An Affine Representation for Transversal Geometries. Studies in Applied Mathe- matics, 54(2):143-160) 1975. doi: 10. (0.10022/apmm9775521433 URL https:://el..rr//10. 1002/
sapm 975542143
Eunice Yuh-Jie Chen, Arthur Choi Choi, and Adnan Darwiche. Enumerating equivalence classes of Bayesian networks using ec graphs. In Artificial Intelligence and Statistics, pp. 591-599, PMLR, 2016.
Wei Chen, Zhiyi Huang. Ruichu Cai, Zhifeng Hao, and Kun Zhang. Identification of causal structure with latent variables based on higher order cumulants. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 38, pp. 20353-20361, 2024a.
Zhengming Chen, Ruichu Cai, Feng Xie, Jie Qiao, Anpeng Wu, Zijian Li, Zhifeng Hao, and Kun Zhang Learning discrete latent variable structures with tensor rank conditions. Advances in Neural Information Processing Systems, 37:17398-17427 2024b.
Zhengming Chen, Yewei Xia, Feng Xie, Jie Qiao, Zhifeng Hao, Ruichu Cai, and Kun Zhang. Identification of latent confounders via investigating the tensor ranks of the nonlincar observations. In second International Conference Machine Learning, 2025. URL URL.Bbttps://opeeee/leww wtwp://wwwwweeeeeee/ooouu.ee.... net/formmi.d WH32R82 ino
David Maxwell Chickering. A transformational characterization of equivalent Bayesian network structures. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI195, pp. 87-98, 1995.
11

---

Published as a conference paper at ICLR 2026
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-554 2002.
Myung Jin Choi, Vincent YF Tan, Animashree Anandkumar, and Alan S Willsky. Learning latent tree graphical models. The Journal of Machine Learning Research, 12:1771-1812, 2011.
Tom Claassen and Ioan Bucur. Greedy equivalence search the presence of latent confounders. Conference on Uncertainty in Artificial Intelligence, 2022.
Tom Claassen and Joris Mooij. Establishing Markov equivalence in eyclic directed graphs. In Uncertainty in Artificial Intelligence, pp. 433-442. PMLR, 2023.
Ruifci Cui, Perry Groot, Moritz Schauer, and Tom Heskes. Learning the causal structure of copula models with latent variables. UAI, 2018
Haoyue Dai, Peter Spirtes, and Kun Zhang. Independence testing-based approach to causal discovery under measurement error and linear Non-Gaussian models. Advances in Neural Information Processing Systems, 35:27524-27536, 2022.
2022.
Haoyue Dai, Ignavier Ng. Yujia Zheng. Zhengqing Gao, and Kun Zhang. Local causal discovery with linear Non- Gaussian cyclic models. International Conference on Artificial Intelligence and Statisties, pp. 154-162 PMLR, 2024.
Haoyue Dai, Ignavier Ng. Jianle Sun. Zeyu Tang, Gongxu Luo, Xinshuai Dong, Peter Spirtes, and Kun Zhang. When selection meets intervention: Additional complexities in causal discovery. In The Thirteenth International Conference on Learning Representations, 2025a.
Haoyue Dai, Yiwen Qiu, Ignavier Ng. Xinshuai Dong, Peter Spirtes, and Kun Zhang. Latent variable causal discovery under selection bias. In Forty-second International Conference Machine Learning. 2025b. URL
https://cpenrett
net wtt.://frmmmiidmmm 33
Xinshuai Dong, Biwei Huang. Ignavier Ng. Xiangehen Song, Yujia Zheng, Songyao Jin, Roberto Legaspi, Peter Spirtes, and Kun Zhang. A versatile causal discovery framework to allow causally-related hidden variables. In The Twelfth International Conference on Learning Representations, 2024.
Xinshuai Dong, Ignavier Ng, Boyang Sun, Haoyue Dai, Guang- Yuan Hao, Shunxing Fan, Peter Spirtes, Yumou Qiu, and Kun Zhang. Permutation-based rank test in the presence of discretization and application in causal discovery with mixed data. In Forty-second International Conference on Muchine Learning, 2025, URL htttss://openrevier net. forum? wwwrrummiddieeeeeee Vew.ddd-TTTddddr
Xinshuai Dong, Ignavier Ng. Haoyue Dai, Jiaqi Sun, Xiangehen Song, Peter Spirtes, and Kun Zhang. Score-based greedy search for structure identification of partially observed linear causal models. In The Fourteenth Inter- national Conference on Learning Representations, 2026. URL,
net forum?
HddBNHp er
Mathias Drton. Algebraic problems in struetural equation modeling. In The 50th anniversary of Gröbner bases, volume 77, pp. 35 87. Mathematical Society of Japan, 2018.
Mathias Drton, Bernd Sturffels, and Seth Sullivant, Algebraic factor analysis: tetrads, pentads and heyond. Probability Theory and Related Fields. 138(3):463-495 2007.
Mathias Drton, Marina Garrote López,
López, Niko Nikov, Elina Robeva, and Y Samuel Wang. Causal discovery for linear Non Gaussian models with disjoint cycles. In The 41st Conference Uncertainty in Artificial Intelligence, 2025a.
Mathias Drton, Benjamin Hollering, and Jun Wu. Identifiability of homoscedastic linear structural equation models using algebraic matroids. Advunces in Applied Mathematics, 163:102794, 2025b. ISSN 0196- 8858. doi: https::/doi..og/1.... 1016/)..........mmm. wttp://.aaam222.12222222 102794. URL UtLtttt:::////w/ http://:wwwwww.cccccceeeeeeeeee science / attpaaatticctteeeeeeeeeee wtt.1/////01110100000000000
Bao Duong and Thi Kim Hue Nguyen. Normalizing flows for conditional independence testing. Knowledge and Information Systems, 2024.
Frederick Eberhardt. Almost optimal intervention sets for causal discovery. In Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence, pp. 161-168, 2008
Frederick Fberhardt and Richard Scheines. Interventions and causal inference. Philosophy of science, 74(5): 981-995, 2007.
12

---

Published as a conference paper at ICLR 2026
Frederick Eberhardt, Clark Glymour, and Richard Scheines. On the number of experiments sufficient and in the worst case necessary to identify all causal relations among n variables. In Proceedings of the Twenty-Fing First Conference on Uncertainty in Artificial Intelligence, pp. 778-184, 2005.
Jan Eriksson and Visa Koivunen. Identifiability, separability, and uniqueness of linear ica models. IEEE signal processing letters, 11(7):601-66) 00146,64,2220 2004.
Robin Evans. Graphs for margins of Bayesian networks. Scandinavian Journal of Statistics, 43(3):225-645 2016.
Robin Evans. Margins of discrete Bayesian networks. The Annals of Statistics, 46(64))262322266663 2018.
Patrick Forré and Joris M Mooij. Markov properties for graphical models with cycles and latent variables. arXiv preprint 1rX.0.1710.00775, 2017.
Morten Frydenberg. The chain graph Markov property. Scandinavian joundna of statistics, pp. 333- 333-353,10 1990.
Dan Geiger and Christopher Meek. Graphical models and exponential families. arXiv preprint 1996.
Ira Gessel and Gérard Viennot. Binomial determinants, paths, and hook length formulae. Advances in mathematics, 58(3):300-33) -211, 1985.
AmirEmad Ghassami, Saber Salchkaleybar, Negar Kiyavash, and Kun Zhang. Learning causal structures using regression invariance. Advances in Neural Information Processing Systems, 30, 2017.
AmirEmad Ghassami, Alan Yang. Negar Kiyavash, Kun Zhang. Characterizing distribution equivalence and structure learning for cyclic and acyclic directed graphs. In International Conference on Machine Learning. pp. 3494-3504. PMLR, 2020.
Yugi Gu and Gongjun Xu. Identifiability of hierarchical latent attribute models, arXiv preprint 17X.091900.007869 2023.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs. The Journal of Machine Learning Research, 13(1):2409-244 2464, 2012.
Alain Hauser and Peter Bühlmann. Jointly interventional and observational data: estimation of interventional Markov equivalence classes of directed acyclic graphs. Journal of Royal Statistical Society Series Statistical Methodology, 77(1):291-318, 2015.
Yang- Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(Nov):2523 -547, 2008.
Patrik O Hoyer, Shohei Shimizu, Antti Kerminen, and Markus Palviainen. Estimation of causal effects using linear Non- Gaussian causal models with hidden variables. International Journal of Approximate Reasoning. 49(2):362-378, 2008
Yingyao Hu. Identification and estimation of nonlinear models with misclassification error using instrumental variables: general solution. Journal of Econometrics, 144(1):27-61, 2008.
Yingyao Hu. The econometrics of unobservables: Applications of measurement error models in empirical industrial organization and labor cconomics. Journal of econometrics, 200(2):154- 168, 2017.
Zhongyi Hu and Robin Evans. Faster algorithms for Markov equivalence. In Conference Uncertainty in Artificial Intelligence, pp. 739-748. PMLR, 2020.
Biwci Huang, Kun Zhang, Jiji Zhang, Joseph Ramscy, Ruben Linchez-Romero Clark Glymour, and Bernhard Schölkopf. Causal discovery from hecerogenccushoossaaiionnyy data. Journal of Machine Learning Research, 1--89) 2020.
Biwei Huang, Charles Jia Han Low, Feng Xie, Clark Glymour, and Kun Zhang. Latent hicrarchical causal structure discovery with rank constraints, Advances neural information processing systems, 35:5549-5555 5561, 2022.
Aubrey W Ingleton and Mike J Piff. Gammoids and transversal matroids. Journal of Combinatorial Theory, Series 15(1)511-68 1973.
13

---

Published as a conference paper at ICLR 2026
Fattaneh Jabbari, Joseph Ramsey, Peter Spirtes, and Gregory Cooper. Discovery of causal models that contain latent variables through Bayesian scoring of independence constraints. Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2017, Skopje, Macedonia, September 18 22, 2017, Proceedings, Part II 10, pp. 142 157. Springer, 2017.
Yibo Jiang and Bryon Aragam, Learning nonparametric latent causal graphs with unknown interventions. Advances Neural Information Processing Systems,
2023.
Songyao Jin, Feng Xie, Guangyi Chen, Biwei Huang, Zhengming Chen, Xinshuai Dong, and Kun Zhang. Structural estimation partially observed linear Non-Gaussian acyclic model: A practical approach with identifiability, In The Twelfth International Conference on Learning Representatioss, 2024.
Joseph Johnson and Pardis Semnani. Characteristic imsets for cyclic linear causal models and the chickering ideal. arXiv preprint arXiv:2506.1 13407, 2025.
Bohdan Kivva, Goutham Rajendran, Pradeep Ravikumar, and Bryon Aragam. Learning latent causal graphs via mixture oracles. Advances in Neural Information Processing Systems, 34: 1087-18118,, 2021.
Yaroslav Kivva, Saber Salchkaleybar, and Negar Kiyavash. cross moment approach causal effect estimation. Advances Neural Information Processing Systems, 36:9944-9955, 2023.
Murat Kocaoglu, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. Characterization and learning of causal graphs with latent variables from soft interventions. Advances in Neural Information Processing Systems, 32, 2019.
Dénes König. Graphs and matrices. Matematikai és Fizikai Lapok, 38:116 119, 1931.
Erich Kummerfeld and Joseph Ramsey. Causal clustering for 1-factor measurement models. In Proceedings 22nd ACM SIGKDD international conference on knowledge discovery data mining, pp. 1655-1664. 2016.
Gustavo Lacerda, Peter Spirtes, Joseph Ramsey, and Patrik O. Hoyer. Discovering cyclic causal models by independent components analysis. In Conference on Uncertainty in Artificial Intelligence, 2008.
Bernt Lindström. On the vector representations of induced matroids. Bulletin of the London Mathematical Society, 5(1):85-90, 1973.
Yiheng Liu, Elina Robeva, and Huanqing Wang. Learning lincar Con-Gaussian graphical models with multidi- rected edges. Journal of Causal Inference, 91):2500 1235002--,,,00 2021.
Gongxu Luo, Haoyue Dai, Loka Li, Chengqian Gao, Boyang Sun, and Kun Zhang. Gene regulatory network inference in the presence of selection bias and latent confounders. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL attps://openzeeee /tt.//ett///eeeeee forts/Eoumm? id=
14irkkvo11
Gongxu Luo, Loka Li. Guangyi Chen, Haoyue Dai, and Kun Zhang. Characterization learning of causal graphs with latent confounders and post treatment selection from interventional data. In The Fourteenth Inter- national Conference on Learning Representations, 2026. URL
not uorum?
1d=gc 1Nnb XXNJ
Yichen Lyu and Pengkun Yang. Identifiability and estimation in high dineesiinnnion nonparametric latent structure models. In Nika Haghtalab and Ankur Moitra (eds.), Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pp. 3879-3880, PMLR, 30 Jun-04 Jul 2025.
Takashi Nicholas Maeda and Shohei Shimizu. RCD: Repetitive causal discovery of linear non- Ganssaausiin acyclic models with latent confounders. In International Conference Artificial Intelligence and Statistics, 2020.
Sara Magliacane, Tom Claassen, and Joris M Mooij. Ancestral causal inference. Advances Neural Information Processing Systems, 29, 2016.
Alex Markham and Moritz Grosse Weesrup. Measurement dependence inducing latent causal models. In Conference on Uncertainty in Artificial Intelligence, pp. 590-599. PMLR, 2020.
Alex Markham, Danai Deligeorgaki, Pratik Misra, and Liam Solus. A transformational characterization of unconditionally equivalent Bayesian networks. In International Conference Prohabilistic Graphical Models, pp. 109-120. PMIR, 2022.
14

---

Published as a conference paper at ICLR 2026
J.H. Mason. On class of matroids arising from paths in graphs. Proceedings of the London Mathematical Society, 3(1):55-74 74, 1972.
Christopher Meek. Causal inference and causal explanation with background knowledge. In Proceedings of the Eleventh conference on Uncertainty in artificial intelligence, pp. 403-410, 1995.
Christopher Meek, Graphical Models: Selecting causal and statistical models. PhD thesis, Carnegie Mellon University, 1997.
Nicolai Meinshausen, Alain Hauser, Joris M Mooij, Jonas Peters, Philip Versteeg, and Peter Bühhmann. Methods for causal inference from gene perturbation experiments and validation. Proceedings the National Academy of Sciences, 113(27)77311-766 2016.
Karl Menger. 7ur allgemeinen kurventheorie. Fund. Math., 10:96- 159, 1927.
Joris M Mooij and Tom Claassen. Constraint Constraint-based causal discovery using partial ancestral graphs in the presence of cycles. In Conference on Uncertainty in Artificial Intelligence, pp. 1159-1 168. Pmir, 2020.
Joris M Mooij. Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. Journal of Machine Learning Research, 21(99)11-10S 2020.
Ignavier Ng. Xinshuai Dong. Haoyue Dai, Biwei Huang. Peter Spirtes, and Kun Zhang. Score-based causal discovery of latent variable causal models. In Forty-first International Conference on Machine Learning. 2024.
Christopher Nowzohour, Marloes H Maathuis, Robin J Evans, and Peter Bühlmann. Distributional equivalence and structure learning for bow-free acyclic path diagrams. Electronic Journal of Statistics, 2017.
Juan Miguel Ogartio, Peter Spirtes, and Joe Ramsey. A hybrid causal search algorithm for latent variable models. In Proceedings of the Eighth International Conference on Probabilistic Gruphicul Models, pp. 368-379,
2016.
James G Oxley. Matroid theory, volume 3. Oxford University Press, USA, 2006.
Judea Pearl. Causality: models, reasoning and inference. Cambridge University Press, 2009.
Judea Pearl and Rina Dechter. Identifying independencies causal graphs with feedback. ArXiv, 1996.
Hazel Perfect. Applications of menger's graph theorem. Journal of Mathematical Analysis and Applications, 22 (1):96-111, 1968.
Emilija Perković, Markus Kalisch, and Maloes H Maathuis. Interpreting and using CPDAGs with background knowledge. arXiv preprint 1rXiv:1707.02171, 2017.
Anastasia Podosinnikova, Amelia Perry, Alexander S Wein, Francis Bach. Alexandre d' A'srrmmnnt and David Sontag. Overcomplete independent component analysis via sdp. In The 22nd international conference on artificial intelligence and statistics, pp. 2583-2592. PMLR, 2019.
Thomas Richardson and Peter Spirtes, Ancestral graph Markov models. The Annals of Statistics, 3064))222300))) 2002.
Thomas S Richardson. Discovering cyclic causal structure. Department of Philosophy, Carnegie Mellon University, 1996.
Thomas S Richardson. Robin J Evans. James M Robins, and llya Shpitser. Nested Markov properties for acyclic directed mixed graphs. The Annals of Staristios, (1),13333,,, 2023.
Elina Robeva and Jean- Baptiste Seby. Multi-trek separation in linear structural equation models. SIAM Journal on Applied Algebra and Geometry, 5(2):278-30$ 2021.
Dominik Rothenhäusler, Christina Heinze, Jonas Peters, and Nicolai Meinshausen. Backshift: Learning causal cyclic graphs from unknown shift interventions. Advances in Neural Information Processing Systems, 28, 2015.
Alberto Roverato, Milan Studený, and David Madigan. A graphical representation of equivalence classes of amp chain graphs. Journal of Machine Learning Research, 7(6), 2006.
Saber Salehkaleybar, AmirEmad Ghassami, Negar Kiyavash, and Kun Zhang. Learning linear Non-Gaus Gaussian causal models in the presence of latent variables. The Journal of Machine Learning Researck, 21(1): 1436-1459, 2020.
15

---

Published as a conference paper at ICLR 2026
Daniela Schkoda and Mathias Drton. Goodness-of-fit tests for linear Non-Gaussian structural equation models. Biometrika, pp. asaf046, 2025.
Daniela Schkoda, Elina Robeva, and Mathias Drton. Causal discovery of linear Non-Gaussian causal models with unobserved confounding, arXiv preprint arXiv:2408. 049007 2024.
Ehsan Sharifian, Saber Salrhkaleybar, and Negar Kiyavash. Near-optimal experiment design in linear Non- Gaussian eyclic models. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL
net./ Eorum? www.mmidddooooooooooooo dd-opAU0pOoop
Shohei Shimizu. Statistical causal discovery: LiNGAM approach. Springer, 2022.
Shohei Shimizu and Kenneth Bollen. Bayesian estimation causal direction in acyclic structural equation models with -ndividual-speciffe confounder variables and Non-Gaussian distributions. Journal of Machine Learning Research-IMI.R, 15(1 2:2629-2652, 2014.
Shohei Shimizu, Patrik Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear Non-Gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
Ricardo Silva and Richard Scheines. Generalized measurement models. Carnegie Mellon University, Center for Automated Learning and Discovery, 2004.
Ricardo Silva and Shohei Shimizu. Learning instrumental variables with structural and Non-Gaussianity assumptions. Journal of Machine Learning Research, 18(120):1-49, 2017.
Ricardo Silva, Richard Scheines, Clark Glymour, and Peter Spirtes. Learning measurement models for un- observed variables. In Proceedings of the Nineteenth Conference Uncertainty in Artificial Intelligence. UAI'03, 2003.
Ricardo Silva, Richard Scheines, Clark Glymour, and Peter Spirtes. Learning the structure of linear latent variable models. Journal of Machine Learning Research, 7(2), 2006.
Peter Spirtes. Building causal graphs from statistical data in the presence of latent variables. Department of Philosophy technical report, 1992.
Peter Spirtes. Conditional independence in directed eyclic graphical models representing feedback mixtures. Technical report, Philosophy, Methodology and Logic Technical Report 59, CMU, 1994.
Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review, 9:62 72, 1991.
Peter Spirtes and Thomas Richardson. polynomial time algorithm for determining DAG equivalence in the presence latent variables selection bias. Proceedings of the International Workshop on Artificial Intelligence and Statistics, volume 12, 1996.
Peter Spirtes and Thomas Verma. Equivalence causal models with latent variables. Carnegie Mellon University Tech Report, 1992.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Hcckerman. Causation, prediction, and search. MIT press, 2000.
Peter L Spirtes. Calculation of entailed rank constraints in partially non-linear and cyclic models. arXiv preprint arXiv: arXiv:1309. 111..13.000000 7004, 2013.
Chandler Squires, Yuhao Wang, and Caroline Uhler. Permutation-bast causal structure learning with unknown intervention targets. In Conference on Uncertainty in Artificial Intelligence, pp.
PMLR, 2020.
Chandler Squires, Annie Yun, Eshaan Nichani, Raj Agrawal, and Caroline Uhler. Causal structure discovery between clusters of nodes induced by latent factors. In Conference on Causal Learning and Reasoning, pp. 669-687, PMLR, 2022.
Bertran Steinsky. Enumeration of labelled chain graphs and labelled essential directed acyclic graphs. Discrete mathematics, 270(1-3):267 278, 2003.
Nils Sturma, Chandler Squires, Mathias Drton, and Caroline Uhler. Unpaired multi-domaii causal representation learning. Advances in Neural Information Processing Systems, 36, 2024.
Seth Sullivant, Kelli Talaska, and Jan Draisma. Trek separation for Gaussian graphical models. The Annals of Statistics, 38(3): 1665:666651185, 2010.
16

---

Published as a conference paper at ICLR 2026
Kelli Talaska. Determinants of weighted path matrices. arXiv: Combinatorics, 2012. URL https://api semanticschclae wtw.aaa....rrrrooo....:.: 1196677799
Tatsuya Tashiro, Shohei Shimizu, Aspo Hyvärinen, and Takashi Washio. Parcelingam: A causal ordering method robust against latent confounders. Neural computation, 26(1):57-83, 2014.
Eric J Tchetgen Tchetgen, Andrew Ying. Yifan Cui, Xu Shi, and Wang Miao. An introduction to proximal causal inference. Statistical Science, 39(3)3375-394 2024.
Henry Teicher. Identifiability of mixtures of product measures. The Annals of Mathematical Statistics, 38(4): 1300-1300 10000-302,110 1967.
Jin Tian. Generating Markov equivalent maximal ancestral graphs by single edge replacement. In Conference on Uncertainty in Artificial Intelligence, 2005.
Jin Tian and Judea Pearl. Causal discovery from changes. arXiv preprint arXiv:1301.2312 2001.
Danicle Tramontano, Anthea Monod, and Mathias Drton. Learning linear Kon-Gaussian polytrec models. In Uncertainty in Artificial Intelligence, pp. 1960-1969. PMLR, 2022.
Daniele Tramontano, Mathias Drton, and Jalal Etesami. Parameter identification in linear Non-Gaussian causal models under general confounding, arXiv preprint arXiv:2405.20856 2024.
Daniele Tramontano, Yaroslav Kivva, Saber Salchkaleybar, Negar Kiyavash, and Mathias Drton, Causal effect identification in IvLiNGAM from higher-order cumulants. In Forty-second International Conference on Machine Learning, 2025. Utt.httss::///// http:cppps./ppereeiiieeeeeeseeee wtt.ne/e/oooummmmm333k
Aparajithan Venkateswaran and Emilija Perković. Towards complete causal explanation with expert knowledge. arXiv preprint arXiv:2407.07338, 2024.
Thomas S Verma and Judea Pearl. Equivalence and synthesis of causal models. In Uncertainty in Artificial Intelligence, 1991.
Tian-Zuo Wang, Wen-Bo Du, and Zhi-Hua Zhou. An efficient maximal ancestral graph listing algorithm. In Forty-first International Conference on Machine Learning, 2024.
Tian-Zuo Wang, Wen-Bo Du, and Zhi-Hua Zhou. Polynomial- delay mag listing with novel locally complete orientation rules. In Forty-second International Conference Machine Learning, 2025.
Y Samuel Wang and Mathias Drton. Causal discovery with unobserved confounding and Non-Gaussian data. Journal of Machine Learning Research, 24(271):1-61. 2023.
Yuhao Wang, Liam Solus, Karren Yang, and Caroline Uhler. Permutation based causal inference algorithms with interventions. Advances in Neural Information Processing Systems. 30, 2017.
Marcel Wicnöbst, Malte Luttermann, Max Bannach, and Macicj Liskiewicz. Efficient enumcration of Markov equivalent DAGs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 12313- 12320, 2023.
Yewei Xia, Zhengming Chen, Haoyue Dai, Fuhong Wang, Yixin Ren, Yiging Li, Kun Zhang, and Shuigeng Zhou. Conditional independent component analysis for estimating causal structure with latent variables. In The Fourteenth International Conference Learning Representations, 2026. htL/hhtts:///peeee
net/ pet/forum?10 www.ummmddddmtt d-TAAppCPPnjg
Feng Xie, Ruichu Cai, Biwei Huang, Clark Glymour, Zhifeng Hao, and Kun Zhang. Generalized independent noise condition for estimating latent variable causal graphs. Advances Neural Information Processing Systems, 33:14891 1891- 2020.
Feng Xie, Yangbo He, Zhi Geng, Zhengming Chen, Ru Hou, and Kun Zhang. Testability of instrumental variables in linear Non-Gaussian acyelic causal models. Entropy, 24(4):512, 2022.
Feng Xic, Biwei Huang, Zhengming Chen, Ruichu Cai, Clark Glymour, Zhi Geng, and Kun Zhang, Generalized independent noise condition for estimating causal structure with latent variables. Journal of Machine Learning Research, 25(191):1-11, 2024. URL / www.:r.rrrgppeeeee wttp://appp//////222333333 1052. htmll
Baoying Yang, Jing Qin, Jing Ning, and Yukun Liu. Double robust conditional independence test for novel biomarkers given established risk factors with survival data. Biometrics, 81())ujaf133, 2025.
Karren Yang, Abigail Katcoff, and Caroline Uhler. Characterizing and learning equivalence classes of causal DAGs under interventions. In International Conference on Machine Learning, pp. 5541-5550.. PMIR, 2018.
17

---

Published as a conference paper at ICLR 2026
Yuqin Yang, AmirEmad Ghassami, Mohamed Nafea, Negar Kiyavash, Kun Zhang, and Ilya Shpitser. Causal discovery in lincar latent variable models subject to measurement error. Advances Neural Information Processing Systems, 35:874-888 2022.
Yuqin Yang. Mohamed S Nafea, Negar Kiyavash, Kun Zhang, and AmirEmad Ghassami. Causal discovery linear models with unobserved variables and measurement error. In NeurlPS 2024 Causal Representation Learning Workshop, 2024. WtRLhttss://// http::/::///peeeeeee..... net forum d- df &
Binghua Yao and Joris Mooij. Sigma-maximal ancestral graphs. In The 41 Conference on Uncertainty in Artificial Intelligence, 2025. URL htLLtttts////peeeveliet net To Bdd
Dingling Yao, Dario Rancati, Riccardo Cadei, Marco Fumero, and Francesco Locatello. Unifying causal representation learning with the invariance principle. In The Thirteenth International Conference on Learning Representations, 2025. URL/tttpps//opeeeeeeiewww net forumm witpummmmidddi 1d-
Bixi Zhang and Wolfgang Wiedermann. Covariate selection in causal learning under Non- Non-Gaussianity. Behavior Research Methods, 56(4)=4019-4037, 2024.
Jiaqi Zhang, Kristjan Greenewald, Chandler Squires, Akash Srivastava, Karthikeyan Shanmugam, and Caroline
Uhler. Identifiability guarantees for causal disentanglement from soft interventions. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Jiji Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17::1773 1896, 2008a.
Jiji Zhang. Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 9(7), 2008b.
Jiji Zhang and Peter Spirtes. A transformational characterization of Markov equivalence for directed acyclic graphs with latent variables. In Conference Uncertainty in Artificial Intelligence, 2005,
Kun Zhang, Biwei Huang. Jiji Zhang, Bernhard Schölkopf. and Clark Glymour. Discovery and visualization of nonstationary causal models. arXiv preprint arXiv: urXiv:1509.08056 2015.
Kun Zhang, Mingming Gong, Joseph D Ramsey, Kayhan Batmanghelich, Peter Spirtes, and Clark Glymour. Causal discovery with linear Non Non-Gaussian models under measurement error: Structural identifiability results. In UAI, pp. 1063 1073,107..000 2018.
Kun Zhang, Shaoan Xie, Ignavier Ng. and Yujia Zheng. Causal representation learning from multiple dis- tributions: A general setting. In Forty-first International Conference on Machine Learning, 2024, URL https: net/ wtt.://www............meeeeeeee.
18

---

Published as a conference paper at ICLR 2026
Appendix
Table of Contents
Details of the glvLiNG algorithm
A. Basics of ransversal Matroids
19
A.2 Algorithm Overview
21
A.3 Phase I: Bipartite Graph Realization
22
A.4
Phase 2: Augmenting Bipartite Graph for Matroid Extensions
22
B
Proofs of Main Results
24
B.1
Proofs of Irreucciiility Results
24
B.2
Proof from Rank Equivalence to Distrihutional Equivalence
25
Proots Matroid Preserving Column Augmentation: a Core Component
27
B.3.1
Constructing Particular Solutions Column Augmentation
27
B.3.2
Traversing All Solutions Column Augmentation
28
B.3.3
From One Column Augmentation to Multiple Columns" Joint Augmentation
31
B,4
Prools of the Graphical Criterion and Transformational Characterization
32
B.5
Other Immediate or Known Results
35
Discussion
36
Summary: A side-by-side Comparison Between Path Ranks and Edge Ranks
36
Another Example Distributional Equivalence Class
A Presentation of the Equivalence Class
C.4
Examples Non-Rank Constraints Mixing Matrices
38
C.S
Related Work
39
D
Evaluation Results
43
D.1
Quantifying the Sizes of Equivalence Classes
43
D.2
Assessing givLiNG Algorithm's 's Runtime
44
D.3
Benchmarking Existing Methods under Oracle Inputs
45
Evaluating glvl.ING Performance with Existing Methods in Simulations
46
Analyzing Real- World Dataset with glvLiNG Algorithm)
47
A DETAILS OF THE GLVLING ALGORITHM
A.1 1 BASICS OF TRANSVERSAL MATROIDS
Before proceeding, let us introduce some basic concepts from matroid theory that will be used later. Throughout, define matroids in terms of binary matrices, interpreted adjacency matrices of bipartite graphs where columns point to rows. The matroid is defined over row indices, corresponding what known transversal matroid. For more, one may refer (Oxley 2006).
Definition 7 (Basics of transversal matroid). Let Q E (0.1) mxx be binary matrix, interpreted as the adjacency matrix of a bipartite graph where columns [n] point to rows E == [m], where E is called the ground set. For simplicity, for each row Z E we denote its rank as:
r(Z)
mrank((2z.).
(A.1)
though with a slight notation abuse to the letter r we used previously for edge ranks (Definition 4 Here, mrank is the matching rank we defined in Definition 6 This rank function turns E into transversal matroid presented by Q. We record the following basic concepts of this matroid, together with some useful properties, written directly in terms of Q and
19

---

Published as a conference paper at ICLR 2026
Independenn/depenndent sets.
Ind(() = 22 : r(Z) |Z|}
(A.2)
Dep(Q) = 2 Ind(().
Note. Z is independent if and only if the rows Z admit a matching into the columns; dependent sets are those with a matching deficiency.
Bases.
(Qses( = (BCE: B [n)( [B] |B| =r()))
(A.3)
Note. Bases the maximal independent sets: all its subsets are independent, and all its proper supersets are dependent. Bases are the maximum-cardinalig independent sets (all have size r(E)). Bases uniquely determine the matroid.
Circuits.
circuits(Q) = E C Dep(Q) and AC C,, C' E Ind(Q)).
(A.4)
Note. Circuits the minimal dependent sets: r(C) - |C| and every proper subset is independent. Every dependent set contains a circuit as subset. Circuits do not necessarily have the same cardinalities. Circuits uniquely determine the matroid.
Cocireuits.
cocircuits(Q) = C D) -1 and A Ç CD r(F (() r(F)) (A.5)
Note. Cocircuits the minimal rank-dropping blockers: removing lowers the full rank (by exactly one), while removing any proper subset does not. Cocircuits meet every basis:
Dn 2 1, A cocircuits((), B bases(Q). Equivalently, D is a minimal set intersecting all bases. By minimal we mean, for any cocircuit D, no proper subset of D can be cocircuit.
(A.6)
When cocircuits meet circuits, the intersection size is never 1. In particular,
ID n Cl E 2,, Equivalently, is minimal set not intersecting any circuit with size Cocircuits uniquely determine the matroid.
A D E cocircuits(Q). C E circuits(Q).
(A.7)
Coloops.
coloops(Q) = E
- 1}.
(A.8)
Note. coloop is an element whose presence always increases rank by 1. A coloop is an element that is in every basis. For each element E E, the following are equivalent:
e coloops(Q) = {e} E cocircuits(()) (Q) > e in every basis < is in no circuit. (A.9)
Coloops do not determine the matroid. Flats.
flats(Q) (F VIE r(FU = r(F) 1}. Note. Flats are the C-maximal sets that have a given rank r(F). The family of flats uniquely determines a matroid.
(A.10)
Fundamental circuit with respect basis. unique circuit Cz(e) such that
For any basis B and any e E B, there is
E CB(C) s (u(e),
(A.11)
called the fundamental circuit of w.r.t. B. Moreover, for every Cы(e) \ (e), the set BVffu(e)) is a basis. Every circuit is a fundamental circuit to some B and e.
Fundamental cocireuit with respect to basis. cocircuit D (e) such that
For any basis B and any B, there is unique
DB(c) C (E\B)U(e)
(A.12)
called the fundamental cocireuit of w.n.t. B. Moreover, for every f Dz(c) \ {e), the set BV(e) U (/) is a basis. Every cocircuit is fundamental cocircuit to some B and
Having introduced these basics of transvesal matroids, below explain algorithm in detail.
20

---

Published as a conference paper at ICLR 2026
A.2 ALGORITHM OVERVIEW
Let us first formally define the faithfulness assumption required by the givLiNG algorithm:
Assumption 1 (Faithfulness). Let dx X be the number of observed variables. We assume that in the true mixing matrix Ax, that generates data (as defined in Equation (5)) all dx x dx and (dx 1) x (dx - 1) minors exhibit matrix ranks consistent with the corresponding path ranks entailed by the true causal graph (as characterized in Lemma
In other words, there is no coincidental parameter cancellation in the data generating process that would lead matrix ranks lower than those structurally entailed by the graph. Note that such faithfulness assumption, often also referred to as the genericity assumption, is standard in the literature (Adams et al., 2021). It holds almost everywhere in the parameter space except for Lebesgue measure zero set where coincidental lower ranks occur.
We next elaborate on our glvLiNG algorithm. The core to the glvLiNG algorithm is query matrix ranks from the mixing matrix estimated from data using overcomplete ICA (OICA), and then construct a binary support matrix (corresponding
digraph) that satisfies these matrix ranks.
Let p(X) be a data distribution generically generated by an unknown latent- variable model (G, X)). that is, p(X) E P(G,X) Without loss of generality we assume that (9, X) is irreducible. Let X|x [V] be a mixing matrix estimated on p(X) by OICA, and for now, we index the rows and
Á E R columns of Á by X and V, respectively. By the identifiability of OICA, À is the true mixing matrix up column permutation and scaling. Further, with the duality between path ranks and edge ranks (Theorem D. we have that, there exists a permutation æ of V, such that for all Z C X and Y S V. the following equality holds:
rank(Az,y) = pe (Z, xY)) = |Z| + Y - | (V
(A.13)
In other words, there exists unknown binary matrix E 10 whose matching ranks varank(Qzyy can be queried for any Z, Y C with T. C Y, despite its exact entry values being unknown. Such a matrix must exist, with one specific matrix, Q(9) with rows permuted by æ, being an example. As long as one can recover this matrix Q, one can then permute rows to place nonzero entries on the diagonal, and the resulting matrix must exactly be some support matrix for digraph H with G X H. by Lemma 5 Such a row permutation to have nonzero diagonals must also exists, as mrank (Q) VV. by setting Z, Y both to Ø in Equation 4A.13).
Our problem then reduces to: how can one recover such a Q matrix from rank queries? We express this problem in more general formulation, as follows:
Key Problem: Matrix Recovery to Satisfy Matching Rank Queries
Let Q E [0,1) be a binary matrix whose entries are unknown. Let the columns be partitioned as [|] L X, where L is fixed subset. For any Z [m] and any Y C [n] satisfying L C Y, one may query the matching rank of the submatrix Qz,y, which, for simplicity, is denoted as an oracle function:
r(Z, Y) = mrank mrann(Q2))) (Qzy)-
(A.14)
The task is: using only access to this oracle, construct a binary matrix E {0, 1]mxx such that for all Z C [m] and Y C [m] with L Y, the following condition holds:
mraak((H2.y) r(Z,Y).
(A.15)
That is, required satisfy the matching rank oracle on all valid (Z, Y) pairs.
Clearly, the key problem posed above is essentially a satisfiability problem, and can be solved via brute-force methods such as linear programming. However, in what follows, we present significantly more efficient and structured procedure. Note that the matching rank queries in the problem equivalent to providing the transversal matroids each submatrix Q... Thus, for convenience, throughout the rest this appendix, we may freely use the matroid language introduced in Definition 7
21

---

Published as a conference paper at ICLR 2026
Overview of our procedure: Our reconstruction procedure consists of two phases:
Phase I:
Impute the columns H indexed by L to satisfy the matroid bases Equivalently, this is construct bipartite graph that realizes given transversal matroid.
Phase 2: Impute the remaining columns indexed by X such that all matroids induced by Q., for S X are satisfied. Although this may appear combinatorially complex at first glance, we show that each singleton column in X can in fact be imputed independently.
A.3 PIIASE 1: BIPARTITE GRAPHI REALIZATION
Let us first formulate the problem of Phase 1:
Problem of Phase 1: Bipartite Graph Realization of Transversal Matroids
Let Q E {), 1j be binary matrix with unknown entries, but known matroid bases (Q).
The task is: Construct a binary matrix E {0, 1 such that:
bases H) = bases(Q).
(A.16)
That is, construct an example bipartite graph, represented by H, to realize transversal matroid, given by bases(Q).
By duality, this problem is equivalent to reconstructing the digraph representation of the strict gammoid that is the dual of the transversal matroid based on the seminal paper by (Mason 1972) and dualizing the result using the Fundamental Lemma by (Ingleton & Pifi 1973).
The bases of the dual matroid Q" are given by bases(Q") = {E\B| B E basse((Q): The a-system for Q" is defined the bipartite graph with the following incidence relation
IQ. ((e, (F,1)) E (flats(Q"),)) F
eq (F)), (A.17)
where
aq. (F) = =| rq- (F)
U
ag (G)
(A.18)
GERlat(Q*));GE
Since Q a transversal matroid, Q" is a strict gammoid, and therefore all aq-(F) 2 0. Ereaas((")) (gg((D) = E -Q- (E)((E) - rQ (E), and the a-system for Q' has maximal matching that covers all i), and each such matching has the property that the set of unmatched elements from E forms basis T of Q".
Now fix such a maximal matching, let T' C be the unmatched basis, and let (e) be the vertex that is matched to for all E E\T. Define the digraph D (V, A) with == E and A= {u, v) E E x E | u & T, v E Fu, u # w). The digraph D represents the strict gammoid Q" MMason 1972). Using the fundamental lemma (Ingleton & Pifi 1973), obtain that
H ((ett) E E (E\T) e Fi)
(A.19)
represents the transversal matroid Q.
A.4 PIIASE 2: AUGMENTING A BIPARTITE GRAPHI FOR MATROID EXTENSIONS
Having imputed the values in H then impute the remaining X columns:
22

---

Published as a conference paper at ICLR 2026
Problem Phase Augmenting Bipartite Graph Realize Matroid Extensions
Let Q E {0, 1jmxn be a binary matrix with unknown entries, and columns partitioned as [n] L for fixed For every subset æ S X, the matroid bases known.
Let H & {0, 1jmxx be a partially imputed matrix such that bases( H.,r.) bases Q.,r.) is already satisfied, while the columns indexed by X remain unassigned.
The task is: Fill in the remaining columns of H such that for all æ C X,
bases H LLm)) = bases Q.,
(A.20)
That is, augment the bipartite graph, represented by H., L, by adding more "sources" X, so that matroids are realized for all subsets of extended with L.
One may first question whether such an imputation is possible, since overall the already assigned HI only realizes the matroid equality bascs L.,)) = bases (Q.,)), but the exact entry values recovery H.L Q. not guaranteed (and also impossible).
We show that such an imputation is indeed possible, via the following result:
Lemma 8 (How the transversal matroid changes when augmenting more sources). For two binary matrices Q1 E {0, 1]mmx and Q2 E {0, 1]mxx9, we denote by [Q1Q2] E {0, 10,1)mxxm (m1 the matrix obtained by horizontally concatenating Q1 with Q2. Then, we have:
Ind((Q:(Q2)) (71 72 Zi Ind(Q1), Z2 E Ind(Q2))
(A.21)
In other words. two matrices' matroids sufficiently determine the matroid of their augmentation.
With Lemma 8 every bases( H. equals (as..((Q.....H.. and thus the imputation is possible.
Then, how to solve for this imputation? At the first glance, one may have concern on the complexity: in contrast to solving Phase I's realization problem for only one matroid induced by now we need to realize combinatorially many matroids induced by L U x for all æ S X. When trying to impute single column H. this column can appear in many subsets
X,-
Interestingly, all these subsets can be disentangled: one do not need to explicitly realize each æ C X. Instead, suffices to just realize each singleton augmentation for X, X independently.
We show this by the following result:
Lemma 9 (Reducing all union equivalence checks singleton checks), Let Q, H {0, mxn be two binary matrices with columns partitioned as [n]] = LU X for fixed L. Then, the condition
bascs bascs (Q., = bases H. wum), Wa S XX
(A.22)
holds, if and only if the condition
Maaess(Q.1. bases(H...) and basos( (Ss.s(Q., bases H. H.x))) VX, e
(A.23)
holds.
With Lemma 9 the remaining problem of Phase 2 can be reduced to solving for each singleton augmentation, formulated as follows:
23

---

Published as a conference paper at ICLR 2026
Problem Phase 2 (Reduced); Augmenting a Bipartite Graph with a Singleton Source
Let H/ E {0. 1) be partially known binary matrix whose columns partitioned as [ { for a fixed L. The two matroids bases H)) and (H. are known,
[+ = LU
while the exact values at the column H. remain unknown.
The task is: Fill in the column H to satisfy the given matroid bases(H)
That is, augment the bipartite graph, represented by H. by adding one extra "source" so that it extends the current transversal matroid correctly.
To solve this singleton augmentation problem, one could at worst exhaustively try all 2 possible fillings. In what follows, however, we present efficient, deterministic construction:
Lemma 10 (Constructing a particular solution for singleton augmentation). Let H {0. 1) mmx(+))) be binary matrix with columns partitioned as (1 + 1| LU {x}. Define
D= (ie (i. VC circuits(H)) i iEC CVti & Ind Ind
(A.24)
Define new matrix H' where H -.,r. O otherwise. Then, the whole matroid remains unchanged after this column x replacement:
r. and the column x is replaced by H 1ifi E D and
bases H') = bases(H).
(A.25)
With this result, we complete the final step the Key Problem defined above and can obtain a binary matrix H that satisfies all rank constraints.
Proofs of Lemmas 8 to 10 are all given in Appendix B
To interpret H as digraph representation, along the diagonal. Standard algorithms such as the n-rooks method may be used for the row permutation. We keep the column indices of L U X fixed and reindex the to match the same ordered list LUX. The resulting matrix encodes a model distributionally equivalent to the underlying model that general the data. One may then run BFS/DFS using Theorem to obtain the whole equivalence class.
perform final row permutation place nonzeros
With all above, conclude the algorithm part.
B PROOFS OF MAIN RESULTS
Note that present the proofss in order that differs slightly from their appearance, arranged instead according to their logical dependencies.
B. PROOFS OF IRREDUCIBBILITY RESULTS
The irreducibility results rely on the identifiability (overcomplete) independent component analysis (ICA). So we first restate them here.
linear irreducible ICA model can be described by the equation
X AE,
(B.1)
where E = (E,, Em) are unknown mutually independent random variables, namely sources, and X = (X,.... ,x,,) are observed random variables, namely mixtures. E Rx namely the mixing matrix, constrained to have pairwise proportional columns (including zero columns). The tuple (A, F)) is called an irreducible ICA representation of X.
X,.)
Lemma (Identifiability ICA; (Eriksson & Koivunen, 2004h). Let (A, E) and (B, S) be two irreducible ICA representations of p-dim random vector X, where A E IR and B E Rpxn, If every component of E follows a non- Gaussian distribution, then the following properties hold:
1.
24

---

Published as a conference paper at ICLR 2026
2. Every column of A is proportional some column B, and vice versa.
3. Every component follows non-Gaussian distribution
Proposition 1 (Graphical condition for irreducibility). A model (g, X) is irreducible, if and only for each non-empty set 1 S I, chg 2 2, Le., has more than one child outside.
Proof of Proposition Due to the identifiability of OICA, irreducibility equivalent to that there are no proportional columns in the mixing matrix, which, with Lemma 2 is that
pg (X, 2 2, Vo C V with | 2 2.
(B.2)
When contains more vertices from observed X, this condition is naturally satisfied. So only need to consider u that contains at most one vertex from X and at least one vertex from L.
When v contains only L vertices, the violation of Equation (B.2) leads the graphical criterion. When v contains one X vertex, say, X;, and Equation B.2)) is violated, it means the min-cut from v X simply { {X;}. which implies that the min-cut from the remaining latent vertices {X;} to X is either Ø or {X;}. This also leads to the graphical criterion.
Proposition 2 (Procedure of reduction to the irreducible form). Civen any latent-variable model X), the following procedure outputs a digraph H such that H X G and (H, X) is irreducible.
Step I. Initialize H as G.
Step 2. Remove vertices V(H) \ (X) from H. i.e., remove latents who have effects on X.
Step 3. Identify the maximal redundant latents in the remaining latent vertices:
mrl (1 V(H))X |1] > 0, [chx(()\M < and VI' ? 21, |hh ((')(()) 2}. (7)
Step 4. For each E mrl, let be the exact child in (I)( for each parent p E pa (1) add an edge p- - into if not already present; finally, remove I vertices from
Proof of Proposition 2 This graphical operation directly translates the operation merge all maxi- mally proportional columns in the mixing matrix into single columns. This ensures the irreducible H.
Note that by removing maximally redundant latents, the added edges in step 4 will not be removed later, i.c., for each 1 operated in step 4,
(I) \ I = 1, and (ch pa \ (U 2.
(B.3)
This ensures the well-defined graphical operation.
B.2 PROOF FROM RANK EQUIVALENCE DISTRIBUTIONAL EQUIVALENCE
Lemma 3 (Equivalence via path ranks). Two irreducible models are distributionally equivalent,
written 9 X H. if and only if there exists a permutation æ over the vertices V(g), such that pa pz(Z,Y) pn Z, (YY)) for all Z C X and Y Y VG).
(11)
But note that unlike 2., S may still be unreachable from E via only permutation and scaling. In other words, the model identifiabl,, but not unique. See Example 2 of Eriksson & Koivunen (X4))
25

---

Published as a conference paper at ICLR 2026
Proof of Lemma 3
We first show the "=" direction.
By Lemma 2 there is a generic choice A E A(g) that realizes the rank structure for all Z,Y C (g)):
rank(.Az, = Pg Z, Y). With Lemma we obtain from 9 X H. with A E A A(H, X) that there is a matrix B E A(H, permutation matrix P. and a scaling matrix D such that Ax,: = BPD. Let æ be the Celluumtpermttationn that corresponds to the matrix P.
Now, let 2 S X and Y _ (g) = ((H), then we have the desired equation Pg Pc (2 = rank (a2,)(A2y)) = rank ((PP((()B)2 = rBP)(()))2,))
(B.4)
rank (ank(B>,m(M)) PH
(B.5)
We then show the *== direction.
For any Z X, the partial application Pg pZ. is the rank function of strict gammoid Mg,z = I'G Z, V()) defined by the digraph G on the ground set VG) with the set of termi- nals Z. Analogously, Pzx (Z. the rank function strict gammoid Mx,2 defined by the digraph H on the same ground set and the same set of terminals.
Equation (TT) implies that an isomorphism between Mg.z and Mn.z, for all Z S X simultane- ously. Clearly, is also an isomorphism between the dual matroids M2,2 and M,
follows from the Fundamental Lemma (Ingleton& & Piff 1973) that the support matrices Q(9) and Q(H) define isomorphic families of transversal matroids that are represented by the corresponding row-sub-matrices of all (1 - (g) with sufficiently general weights and Bg E B(G); and (1 - Bx) with sufficiently general weights and BH ((H), respectively.
In (Brylawski 1975) it is shown that every transversal matroid may be represented by vectors that lie in the faces of simplex such that for every minimal non-trivial combination of the zero vector by set of representing vectors, this set lies on common simplex face with rank one less than the cardinality of the set of vectors. Over IP such vectors can be found almost surely by taking the incidence matrix of the transversal system and choosing a random value for each nonzero entry. All matrices over TR. that represent the transversal matroid can be produced by this procedure.
Choosing random values for the nonzero entries of Q(9) (and Q(*)) gives almost surely a matrix that represents the respective family of transversal matroids in such a general simplex position, with nonzero entries on the diagonal. By row scaling, this matrix can be brought into the desired form
(T - B) where all diagonal entries are equal to 1. Scaling the columns and rows of a matrix by nonzero factors does not alter the family of matroids represented by a matrix, and does not change whether matrix is in general simplex position.
The matrices in A E A(G, X) (and X)) are row-restrictions of inverses of diagonal-1-scale versions of matrices in general simplex position;
= (SR) -1 x:: = =R
(B.6)
where R is randomized valuation of (19), and is a diagonal matrix consisting of the multiplicative inverses of the diagonal entries of R.
Let P be the permutation matrix for π, and let T be the diagonal matrix consisting of the multiplicative inverses of the diagonal entries of PR. Then there is
A' = (TPR)x! E A(H.
(B.7)
Since and T are invertible diagonal matrices, we have
A' = R
ASP-1T-1 AP-1(SPT
(B.8)
where Sp is a diagonal matrix with (Sp)i,) = Sa())
So A' arises from A by permuting and scaling columns, thus A(G = -)H, Finally, with Lemma 1 we have G X H.
26

---

Published as a conference paper at ICLR 2026
B.3 PROOFS OF PRESODDII COLUMN AUGMENTATION: A CORE COMPONENT
B.3.1 CONSTRUCTING PARTICULAR SOLUTIONS TO A COLUMN AUGMENTATION
We begin with the two auxiliary lemmas introduced in Appendix A namely, Lemmas 8 and TO
Lemma 8 (How the transversal matroid changes when augmenting more sources), For two binary matrices Q1 E 1) and Q2 E {0, 1 we denote by [Q1122] E {0, mm the matrix obtained by horizontally concatenating Q1 with Q2. Then, we have:
Ind((Q:)22)) ( U 72 Zi E Ind(Q1), Z2 E Ind(Q2))-
(A.21)
In other words, two matrices' matroids sufficiently determine the matroid of their augmentation.
Proof of Lemmna 8 Straightforward. Let Ni [n]] and N₂ [n2] be the column indices. For the "S" direction, we just consider for each Z E [nd[[Q]]Q2]) its matched sources in N1 U N2 can be split back into N1 and N2. For the "2" direction, Z1 can be matched into N1 and Zz \ Zi can be matched into N2, which, when put together, is still independent, since N1 and N2 are disjoint.
Lemma 10 (Constructing a particular solution for singleton augmentation). Let H e {0, 13 mmxx(t))))))) be a binary matrix with columns partitioned as [++ 1] L (z). Define
D EiE .m] VC E circuits(H) iE CVi & (Hd
(A.24)
Define a new matrix H' where It',,, H.. and the column x is replaced by H = iffi E D and O otherwise. Then, the whole matroid remains unchanged after this column x replacement:
bases H") bases( H).
(A.25)
Proof of Lemma 10 We show that and H' represent the same transversal matroid by comparing their independent families.
In case that Ind(H, [.,,) = HH), then D is the set of coloops of H.,.- Since every maximal partial transversal of H. already contains each d E D, the bases of H' are precisely the bases of H. so the matroids for H, H.,,, and H' are the same.
Otherwise, if In,(H. S. Ind(H), then H. L has maximal partial transversal that can be extended by some element e with He,z = 1. Because the cardinality of the bases of H is one more than the cardinality of the bases of H.,., we have that every basis B with respect to H can be partitioned into a basis Bn of H.,. and an extra element E B,Bo where Hb. = 1. Clearly Bo In'(H") and if 6 E D, then B is also basis for H'.
Assume that & D, then there is a circuit C of H with b E C such that CVbb3 E Ind(H., The corresponding partial transversal of H., can be extended by sending d(b) x. but then this extended partial transversal proves that C' is independent, contradicting that C is circuit of H, so b E D must be the case. Thus Ind(H) S Ind(H).
Now let B be a basis for H' and assume that B & Ind(H). By set inclusion, B o Ind(H.,). So there is maximal partial transversal @ of H' and some b b B such that
((b) = and dBB L.
(B.9)
Hence,
BVb}} E Ind(H..)) S Ind(H).
(B.10)
Since B & Ind(H), there is a circuit C C B with e C. But then CV(b) C BV(b is independent in H. so b & D. This is contradiction to Hi,000) = Hy_- = 1, because @ is partial transversal of H'. Therefore Ind(H') C Ind H) establishing the equality Ind(H') Ind(H) which implies bascs H') = bascs( H) since bases are precisely the maximal independent sets.
27

---

Published as a conference paper at ICLR 2026
B.3.2 TRAVERSING ALL SOLUTIONS TO COLUMN AUGMENTATION
Now, we have proved the two auxiliary lemmas introduced in Appendix
We observe that these two lemmas are centering around one problem, as formulated in the text box titled "Problem of Phase 2 (Reduced)": suppose we already know both a transversal matroid itself and the transversal matroid of it after augmented with an unknown singleton column, how can we recover this unknown singleton column to satisfy these two matroids?
we have shown particular solution. Then, what are all the possible solutions, and how can we find them? Among all solutions, there anything special about the particular solution given in Lemma
In Lemma T0
TOP
Are there any other particular solutions that might enjoy other properties?
Let us first define all these solutions:
Definition 8 (Solution set of matroid- preserving column augmentations). Let Q {0, l)mxx be a binary matrix. For each x E [n]]. we denote all column vectors that can be used to replace Q's column while preserving Q's matroid by:
volaug(Q,
(DC 2im); bases(( (....))(( [b ]) = bases(() }.
(B.11)
where the name colaug stands for "column augmentation". 1 denotes column vector with ones at entries in D and zeros elsewhere, and the notation [-1.] denotes matrices' horizontal concatenation. Apparently, colaug(Q, (Q, x)) is non-empty, since at least the current column Q... satisfies the condition, as well as the particular column Dp defined in Lemma [0] which may be different from Q.
Before we study how we may traverse all solutions in colaug(Q, z), let us pay more attention to the particular solutions, since 1) they offer efficient way to get solution directly from the matroids, without the need to solving alpha systems, which leads to algorithm speedups, and 2) as we will show below, they have meaningful implications to characterize the whole solution class.
We already have a particular solution from Lemma 10, which checks when a single-element deletion from each new circuit still leads dependent sets before augmentation. In other words, these items are those who contribute to the newly introduced circuits. Following the proof to Lemma [O) we have that these items forms not only solution, but also a unique maximal inclusive solution:
Corollary (Determining items that must not appear in any solution). Let Q {o, 1)mx((+11
be a binary matrix with columns partitioned as [1 +1 L (x}. Let D S [m] be the particular
solution constructed in Lemma 10 and let colaug(Q, S 21 be all the solutions of x-column
augmentation defined Definition g Then, the following condition holds:
D
Ucolaug(Q,a
(B.
In other words, by giving unique maximal solution, Lemma 10 charactterizes which items in [m] can be included in some solution(s), or equivalently, which items must not appear in any solution.
This then naturally leads to another question: which are the items that must be included in all solutions, and more importantly, is there an efficient way to determine them, just like Lemma I0 without having traverse the whole solution set? The answer is yes, by taking complements to Lemma TO
Corollary (Determining items that must appear in all solutions). Let Q {0, 1)m(((+))) be binary matrix with columns partitioned as L {z}. We define the "difference in cocircuits" as
diffco(Q, = cocircuits(() cocirenits(Q...).
(B.13)
Further, for any A C 2V, set of subsets of some universe V, we define the minimum-sized elements of A (with a slightly special treal on Ø3) as:
minimum(A)) (A) = ( {a fa A: |al mina |a'],
if A Ø
(B.14)
otherwise.
The minimal--nclusion elements of A (with a slightly special treat on 2 is then:
28

---

Published as a conference paper at ICLR 2026
minimal(A) = Ma A: Da'e e A with d' Cah, if Ø, [(0),
A
(B.15)
otherwise.
Then, the following conditions always hold:
1. The minimum-sized new cocircuits are all particular solutions. Moreover, they are exactly those minimal-inclusiin ones among all solutions, which have a same (minimum) size:
minimal(colaug(Q..) = minimum (Q,x)) minimum((dificc Q,,
(B.16)
2. Non-mininn mam-mmiiim-sszzee new cocircuits are not solutions, that is, (diffoc(Q, x) minimum(((ifcc(((2)))) O colaug(Q, Ø.
(B.17)
3. The intersection of minimum sized new cocircuits may not be solution itself. but charac- terizes exactly items that must appear in all solutions:
minimum (diffcc(Q,xx)) = n colaug(Q,x))
(B.18)
Roughly speaking, Corollary 2 takes a complement to Corollary D for any valid solution, must complete bases (witnessed by minimal new cocircuits). any item that appears in every such minimum new cocircuit must appear all valid solutions.
We use an example to illustrate these definitions above. Example 3 (llustrationn of Definition 8). Suppose Q is matrix with row indices (1,2,3,4) and column indices {a, B, 7), follows.
Y
0
X
0
bascs(() = ([1,2,3), (1,3,4))
2
X
0
Q
then
circuits (Q) ([2,4)), cocircuits(Q) ((1), (8), (2,
(B.19)
X
X
X
0
Consider the case with
The remaining columns are:
B
1
0
bases ( (Q., = ({1,3)}.
2
0
0
Q.(0.)
=3
with
(Q.,(its(QQ((nn))) ([2), (4)),
(B.20)
X
X
cocireuuiss(Q.(((...)) (11,{(8)
4
0
The particular solution (also the maximal unique solution) given by Lemma and and Corollary I is:
D (1,2,3,4)
(B.21)
where 1 and 3 are coloops, and 2 and 4 lead to the new circuits in Q.
The particular solutions given by Corollary are:
minimu(((iffc((..a))
minimum(cocircuits(() cocireuits (Q..ntt)
minimum( ([(imumm((1)),, (3), 42) \ ((1).(3))
(B.22)
= minimum(((2,4))
-[22,4) 4)).
In total, there four possible columns that can replace Q.. without changing the matroid:
colaug(Q, ([2, (),,4,, (1,2,4) (1,24), (2,3, (1,2,,,)))
(B.23)
For example, choose D (1,2,4) E colaug(( (aanggQQur a:), one may verify that
29

---

Published as a conference paper at ICLR 2026
B
7
1
X
X
07
2
0
0
Let Q'
still have bases(Q)) bases(Q) (11,33))
3
X
X
X
0
0
(B.24)
For now, let us not consider how these whole solutions colaug( Q, a:) are obtained; one may just think of them obtained by exhaustively searching over all 2 possible columns.
Consider the case with r B.
The remaining columns are:
1 X
07
bases (A.sa.Q..fa.)) (3,4)]
Qulant
with
circuits(Q.. = (2,), cocircuits(Q = ((3), (2,44)
(B.25)
X
So, the maximal solution (Lemma 10 and Corollary is: D = {1,3}.
The minimal solutions (Corollary) are: minimum(disfco((1)) And all the possible solutions are: colaug(Q,8) = ((1), (1,3)}.
(0))
Consider the case with x = 7.
The remaining columns are:
8
1
O
X
= (1)))) (U... (12,4), (1,3,4) cocircuits (Q.,aa.)) =
2
X
O
(o....))
with
3
X
X
4
X
0
(B.26)
So, the maximal solution (Lemma 10 and Corollary is: D (1,3).
The minimal solutions (Corollary are: minimum((iffcc(((1)))) (3))
And all the possible solutions are: colaug(Q, {(1), (3), (1.3)).
A
So far, we have introduced the definitions about "matroid- mmatroid-preserving column augmentations", and have provided particular ways to construct both the unique maximal solution and the set of minimal solutions. Then, starting from these particular solutions, or starting from any solution, how can we span to the whole solution set? This is answered by the following result.
We now present the structure among all column augmentations, which descrihes how how the whole solutions be traversed, and is thus important particular, any two solutions can reach each other by a sequence of "edge additiins/delletions..
result about equivalence class traversal. In
Lemma 12 (The whole column augmentations can be traversed by edge additiios/ddelttions). For any matrix Q E {0, m and a column index E [n], we define a digraph termed Goug which is a Hasse diagram with vertices being elements of colaug( Q, x), and edges being:
Dj DD Dj E gaug
Dj D with [Dj D =1 VD,, D, E colaug(Q, (B.27)
Then, this digraph is weakly connected.
We illustrate Lemma 12 by recalling Example
3
30

---

Published as a conference paper at ICLR 2026
(2,4)
{1}
(1)
(3)
(1,2,4)
{2, 32,3,4]
{1,3)
{1,
{1, 2, 3, 4)
(a) 9Q
(b) 9
cang (c) 9Q.7
Figure 4: Example Hasse diagrams (defined in Lemma 12 over the solution sets of sautroid-preservngg column augmentations. Instances from the earlier Example are used. 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 are highlighted in blue.
Proof of Lemma 12
Let
D e (L.... ..... m) VC circuits(Q)) :E CMi & Ind(O.p))))))
(B.28)
From Lemma 10. we know E colang(Q.z))
Let D' colaug(Q, 2), then D' S D, because if there is d' D' with d' & D, then there exists circuit C in Q with d' E C' such that CV{d') has partial transversal omitting the column x. This partial transversal may be extended C by sending d' the column I, which then can be extended to basis Bc 2 C' in the transversal matroid represented by (Q.(m))(a) 1rr). But Q cannot have basis that contains one of its circuits, which implies that D' & colaug Q x). So D is the maximal element of (0,aug(Q,2)).
Let D' E colaug Q,x) with D' + D and let E DVD', Let B E bases(Q), then B E bases((Q. (ee.s(((.,)))) (n/M)) In)).. The maximal partial transversal é that witnesses the independence of B with respect (Q.,(m]) (mr 1 also witnesses the independence of B with respect to (Q.(())(=) (mu())). So we have
bases(Q) = bases((Q., 1 S basos((Q..n)))e)) D(()))))
(B.29)
(x) Inw))))) The maximal partial transversal witnessing B with respect to (m)())) 1 D'u(d}) is also maximal partial transversal with respect to (Q.[mu)Ma) 1)) so B E bases((Q.,n))
Now, let B bases bases((Q..m))) (QQ..()))
1D) = basos(Q). Therefore,
bases Mases((Q..InMMe) 1 ('u(d))) bases(Q), (Q); and D' U {d} E colaug(Q,x))
(B.30)
Hence, for every Do. D1 E colaug( (olaug(Q,x)) there is a directed path to D which gives
Do + .... + D + ... + D1.
(B.31)
Therefore, Gaue is weakly connected.
B.3.3 FROM ONE COLUMN AUGMENTATION TO MULTIPLE COLUMNS' JOINT AUGMENTATION
We have now shown how one can obtain particular solutions or traverse all solutions to single column augmentation. what follows, we shift from one column augmentation to multiple column augmentation, which directly relates to our final graphical criterion to be shown in next section: need to augment whole columns, identifying their outgoing edges.
Interestingly, this seemingly combinatorially complex satisfiability problem can be decomposed locally, that is, suffices to satisfy each singleton column augmentation independently, shown below.
31

---

Published as a conference paper at ICLR 2026
Lemma 9 (Reducing all union equivalence checks to singleton checks). Let Q, H {0, 1 be two binary matrices with coluins partitioned as [m] LU X for a fixed L. Then, the condition
bases (ases(Q = bases H. LUw), Vo S X
(A.22)
holds, if and only if the condition
bases( = bases(H,,L)) and bases(Q.. bases (H, (u(x))) VX, e ex,
(A.23)
holds.
Proof of Lemma Clearly, condition A.23 is special case of condition A.22 with the choices {00,
{Xx)) ]. thus A.22 holds, then so does A.23
If Af22 does not hold, then there is some S X such that bases L. # bases H, H.,) W.l.o.g. we may assume that there some bascs(Q..Iue) with & bases H. ..w).
If x < 1, then A.23 clearly does not hold.
Now assume that [x| 1. Choose B e bases
(.,.)))) (ases(Q.. bases (mm)) and partial transversal Φ: B + T a for Q., Lue such that ő := [|b E B Hb.o(b) 0)] is minimal. Due to the minimality of (may be obtained via basis exchange), there exactly one B such that Ho,0() 0. Let
B' {b' B 6(b)
L LU (o(b))
(B.32)
then B' is a basis of Q. but B' is not basis of H.(t))))))>> shown below:
Assume that is a basis (. then there is partial transversal th B' + LU (d(b))
Construct
8': B L
(B.33)
such that
o'(b') = [bb()
for E B', for E B.B.
(B.34)
(o(b')
o' is partial transversal, because
= Ø,
(B.35)
due to the definition of B'. Thus if o' ('(bn) 0' (bi). Then:
19 Either (bo,br b.) S B': in this case, db(b)) = (bb) = vbbb)) = (b(b) implies bo = by;
2 Otherwise have foo, b1) B'B', and then o' (bb) ((bb) d(b1) d'(b)) implies bo bj.
But then Ø' witnesses that B is basis of H. ruz, contradicting the original assumption. Thus bases( (Q., # bases (u(())))) and A.23 does not hold, too.
We have then finished proof Lemma 9
B.4 PROOFS OF THE GRAPHICAL CRITERION AND TRANSFORMATIONAL CHARACTERIZATION
We first note that the graphical criterion (Theorem is a direct consequence of Lemma that is, instead of checking for bases of all subsets C X, we only need to check for bases for each singleton X, E X. Since Lemma D is already proved above, in this section, we focus on the proof of the transformational characterization (Theorem
32

---

Published as a conference paper at ICLR 2026
Lemma 7 (Admissible edge additions/deletionss) Let (G, X) be an irreducible model. For any edge V + 5 not currently in G, adding to preserves equivalence on X if and only if:
rg(Vi's nonchildren', (V3), (X(V)) < (V'''ss nonchildren, LA(V,));
(20)
where Vi's nonchildren denotes V(G) chę (V.). i.e., entries in support column Q Conversely, edge can be deleted and only if can be re-added by this criterion.
Proof of Lemma 7 Let first prove weaker version of this result, that is, without the permutation part involved in checking equivalence (Lemma Put formally, let H be the digraph after altering an edge Vi > V, G. We study the if and only if condition (in terms of this edge) for the following
rg(Z,Y) (x( for all Z S V()) and L Y V
(B.36)
to hold. According to Lemma | this condition holds if and only if a reduced version hold:
bases (9) ( = bases(Q (?t)
(B.37)
That is, one only need to check whether a single transversal matroid is changed. Then, when can an edge in bipartite graph be altered while the transversal matroid induced by this bipartite graph keeps unchanged? We show the condition by the following lemma.
Lemma 13 (When edge in a bipartite graph be altered without changing the transversal
matroid). Let Q E {0. 1 1 jmxn be a binary support matrix. For any (Vj. V2) E [m] x [n] such that and Hz.y Qzy for all other entries. For
Qvy,v. define H E {0, 1m by Hv,.v. convenience, denote V; non-children in Q and column indices except for V; by:
R = {z E [m] Qz.v. = 0}:
(B.38)
== [V]]
Then, the following conditions are equivalent to each other:
1. bases( (Q) = bases (H);
2. bases(QR..) = bases H R.:);
3. mrank(QR..) = mrank(HRR.)
4. matroid induced by QRY, and so removing it from ground set lowers the rank (by 1).
(ran)(QR((V3,.)) < mrank (n,,)) that is, Vj is coloop among R in the transversal
Proof of Lemma 13 We first have two immediate observations. (i) By construction, Q2,(V.) is the zero column, whereas H Hn, (v.) has single in row Vj. (ii) For any Z C [m] with V, & Z, the submatrices Qz and Hz coincide, hence their matching ranks (and base behavior) coincide.
We now prove the implications among the four conditions by
Trivial. Taking restrictions ground sets preserves equality of matroids.
Trivial. Same matroids have the same ranks.
Let = mrank(Qn.)) and v = mrank(QQ Note that mrank(Hn.y) v, because the column V; is useless (full zero) for R in Q. In H. the only new edge incident to R is (Vi, Vj); therefore any matching on R in is either:
mrank(Qn.)) = mQann((Qn.))
(B.39)
matching that does column Vú, hence has size most v,
33

---

Published as a conference paper at ICLR 2026
matching that does use the edge (V,, Vÿ) and then matches the remaining R (V,) into Y, hence has size at most + v/..
Consequently,
mrank(HR.)) max(v, 1+ t/). Thus mrank( HR.)) mrank(QR.)) holds if and only if 1 + v sviie. v' < v, which is precisely This proves
(B.40)
Assume In the transversal matroid M induced by QR, the inequality mrank (QAI))))) < mrank(QR.)) means that Vj is coloop of M (see Definition 7b A standard matroid identity for coloops states that for all Z C R (V₂),
Combining this with Equation (B.40) (applied mrank (arank(Qz,y)) +1.
mrank(QZuuV,))))
(B.41)
each Z C R) shows that adding the edge (V, Vÿ) cannot change the matching rank of any Z C R: so in particular, the bases on R unchanged: bases QR..) (HR.)
For any Z S [m]. write ZR == Z R and Zout = Z Z R.
If maximum matching of Hz, does not use (V, Vj), then it is also matching in Qz and the ranks agree.
If a maximum matching of Hz.: does use v. Vj), then its restriction to ZR is a maximum matching of Hzg. that the column V4. By (2) (which holds for all subsets of R as shown above), there exists a maximum matching of QZa.: of the same size that avoids V.. Replacing the H-matching on ZR by this Q-matching on ZR (and keeping the -part unchanged) yields a matching of Qz of the same cardinality as the original one in Hz
Hence mrank(Qz.) = (urank(Hz.)) for all Z C [m]] which is equivalent to bases (Q) = bases ()).
All implications are proved, so the four conditions are equivalent. The result on deleting an edge is just the same as adding back this edge from the resulted graph.
The condition shown in Lemma 13 is exactly the condition we have in Lemma and hence the weaker version without permutation (Equation (B36)) is already proved.
The prove the full version, we only need show that when the condition in Equation (B37 fails, then with any permutation they still cannot be rendered equivalent. This is straightforward, since with edge difference, the independent sets Ind(Q ( LU(()) and Ind (,L if not equal, must admit strict inclusion relation between them, there is no way for these two matroids be isomorphic.
We have now finished the proof of Lemma
Theorem 3 (Transsormaaional characterization of the equivalence class). Two irreducible models (G and (H, are equivalent and only if can be transformed into H. up to L-relabeling, via a sequence of admissible cycle reversals and edge additions/deletions, as defined in Lemmas 6 andd
Here, "up to L-relabeling" means there exists a relabeling of in yielding a digraph H'' such that G reaches H!' via the sequence. Moreover, at most one cycle reversal is needed in this sequence.
Proof of Theorem 3 The proof to this result for traversing the equivalence class for the whole class directly relates to the helpful lemmas we have shown in Appendix [B3] i.c., how the whole solution set of column(s) augmentation is structured.
34

---

Published as a conference paper at ICLR 2026
Lemma 12 is core to result: it shows that the whole space of satisfiable column augmentations can be traversed by applying sequences of "one-edge different" operations, and these operations exactly the "admissible edge addittions/deletions" we show in Lemma [ (for edges from X), and Lemma 13 for edges from L). From Lemma [2] we also have a way to traverse all bipartite graphs that realizes given transversal matroid. This can be viewed generalization from single-column to multi-column augmentation:
Corollary 3 (Traverse all bipartite graphs that realize transversal matroid). Let Q H (0, 10.1m be two binary matrices. Q and H induce a same transversal matroid, i.e., bases Q) bases( H), if and only ifQ can reach H via sequence of admissible edge additions/deletions defined in Lemma [3 followed by column permutation. Moreover, similar to Corollary [ among all matrices that can be reached from Q via sequences of edge alditions/deletions. there exists a unique maximal matrix whose support is the union of supports of all these reachable matrices.
Corollary directly relates to our traversal on the Q.7. part. But it is worth noting that unlike the independent decomposition of column augmentations for each X,, here the edge additionns/elletinns have be operated within the whole matrix space. We cannot simply run column augmentation for each L; and take the Cartesian product. To this, let Q [[L 1]] with columns a, 8. Obviously,
colaug (2, a) = 12, {1}}, and also colaug (Q, 3) = { (0, {1}}. However, we cannot take a product and let [0, O]], which induces matroid different from Q.
Now, putting Lemma 12 Corollary 3 and Lemma 9 together, we have way traverse all digraphs that achieve the same matroids over the tower of all sources that include some latent vertices:
Corollary 4 (Traverse all digraphs that realize same matroid tower under latents). Let Q H {0, 1) 1)mxn be two binary matrices with columns partitioned as [n]] = L.X. X. Then, the condition
bases (Q.,, = bases H.,
Vo X,
(B.42)
holds, if and only the bases Q..L) = bases (H.)es (graphical criterion Corollary 3) and for all X, E X, {i [m]] Qx,x, 1} colaug(H,,uuxx.))
(graphical criterion in Lemma 12
In other words, Q can reach via a sequence of admissible edge additions/deletions, followed by a permutation only among the columns in L. Corollary 4 directly relates to our traversal on the Q(9)
If we are to allow the equivalence up to row permutation, i.c., permuting the ground set as in Lemmal only a row permutation appended the end of the operations Corollary is needed.
Finally, treatment to ensure nonzero diagonals for digraphs.
Since in our case need exclude matrices with zero diagonals, this row permutation becomes the "at most one step" within the sequence (Theorem 3), instead of at the end.
The L-relabeling part, however, can still be put at the end, since to relabel the L vertices in digraph G. it is to apply a permutation on the columns Q first, and then to apply the same permutation back on the rows Q!9) This operation still ensures the nonzero diagonals. This becomes the "up to L-relabeling" term in Theorem
We have now finished the proof of Theorem
B.5 OTHER IMMEDIATE OR KNOWN RESULTS
We omit the proofs of the remaining results occurred in this manuscript: some of them follow immediately from the already proved results, including Lemmas] T and and the others are results shown by existing work, including Lemmas 2 and 6 and Theorem
35

---

Published as a conference paper at ICLR 2026
C DISCUSSION
C.I SUMMARY: A SIDE-BY-SIDE COMPARISON BETWEEN PATH RANKS AND EDGE RANKS
Table 1: A side-by-side comparison between path ranks and edge ranks.
Aspect
Path rank (Matrix rank)
Edge rank (Matching rank) Combinatorial independence
Intuition
Algebraic independence
Full rank of a x square matrix M
rank (M) d < the determi- nant of M is nonzero
mrank(M) = d < the perma-
nent of M is nonzero
Graphical constraints in digraphs
Pe Pe Y), the maximum number of vertex- direx-- directed paths from Y to Z (Definition 3) equals the matrix rank of generic mixing sub- matrices Az,Y (Lemma
ng YY. the size of the maximum bipartite matching from Y to via direct edges (Definition) 4 equals the matching rank of the support submatrix Q (9) 2,Y (Lemma 4)
Matroid representations
Strict gammoids in digraphs (Per- fect 1968)
Transversal matroids in bipartite graphs (Ingleton & Pifi 1973)
Duality (Theorem
min (in((Z),|))) (.. IV
max(IZ]: Y)) rg YY, V\Z)
C.2
ANOTHER EXAMPLE DISTRIBUTIONAL EQUIVALENCE CLASS
G1
G2
Go
G
L
63
9
X
X
X1
X2
X
$
X3
X3
X3
G3
L
G
La
G7
Gs
X
X
X2
X
X2
X
X
96
Gs
L
Gg
L1
G10
L1
910
G8
X1
X
Xi
X₂
X1
X2
X
Go
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.
We show another example distributional equivalence class in Figure 5 in addition to the Figure already shown in main text. The points of this example, different from those of Figure are that:
Partitioned by cycle reversals (removing the dashed edges in the right of Figure 5). the classes connected by only edge additions/dellttinns (solid edges) are not necessarily isomorphic to each other. Here, there are 3, 3, 4 digraphs within each such class, respectively.
2. To illustrate cases where cycles intersect.
36

---

Published as a conference paper at ICLR 2026
C.3 A PRESENTATION OF THE EQUIVALENCE CLASS
In the main text, we have presented both a graphical criterion check for equivalence (Theorem) 2 and transformational characterization to traverse the entire equivalence class (Theorem B) These results are analogous to the "same adjacencies and v-structures" and the "covered edge reversal (Meek conjecture)" in the fully observed, acyclic, Markov equivalence setting.
However, note that in that classical setting, there is another familiar result, CPDAG, which serves as an informative presentation of the equivalence class. This naturally raises the question: can we construct an analogous presentation in the context of this work? We answer this affirmatively. In what follows, we outline how this presentation can be constructed step by step.
Step 1. Identifiability of ancestral relations among observed variables. As preliminary observation, we first note that the ancestral relations among observed variables X are invariant across all equivalent digraphs (this follows from how admissible edge additions/delltions are defined, and the fact that cycle reversal does not alter the ancestral relations). Thus, presenting an arbitrary digraph in the equivalence class suffices to inform users the ancestral relations among X. For applications such as experimental design involving observed variables, this alone is informative enough.
Step 2. Unique maximal digraph within the class. We show that under each cycle-reversal con- figuration, there exists unique maximal digraph in the equivalence class such that every equivalent digraph is subgraph of it. We further provide an explicit construction of this maximal digraph (Corollary M] without needing to enumerate all equivalent digraphs and then take the maximal one. Analogous to the "largest chain graph" in |Frydenberg (1990), this maximal digraph serve basis of the presentation, informing users which causal relations are guaranteed to be absent.
Step 3. Characterizing edges that must appear. Building on the previous step, we also charac- terize edges that must be present in all equivalent digraphs. Again, these edges can be determined efficiently via a graphical condition (Corollary 22, without needing to enumerate all equivalent digraphs and then take the intersection. Note that it is an explicit construction, so iterative procedures (such as arrow propagation in Meek rules (Meek 1995)) are not needed either. These edges can be visually highlighted on the basis maximal digraph, in analogous to the arrows in CPDAGs, or "visible edges" in PAGs (Zhang) 2008b). They inform users which causal relations they can fully trust.
Such presentation is formally defined in Theorem and examples of it are shown in Figure 6
X3
Figure 6: Illustrative presentations of equivalence classes. Left: Presentation of equivalent digraphs Gi, G2, Ga under a same cycle-reversal configuration from F The basis digraph shown 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 above). One may use Corollaries [ 2 to check how they are determined. Right: A similar presentation for digraphs Gv. G4, Gr, 910 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.
Theorem 4 (Presentation of an equivalence class). For an irreducible model X), we construct a digraph whose vertices are V(G) and whose directed edges come in two types: solid and dashed. All edges are determined by Corollary and among them the solid ones are determined by Corollary 2 We denote this digraph by CP(G), echoing the sense of "complete partial" as in CPDAGs.
37

---

Published as a conference paper at ICLR 2026
For convenience, let (() be the whole equivalence class, that is, the of all digraphs H. on vertices V(g) such that H X G. Let F()) denote the set of all digraphs reachable from G via sequences of admissible edge addition/deletios as defined in Lemma 7 Clearly, F(g) - Eg)).
Then, the presentation CP(g) enjoys the following properties:
1. CP(g) E F(G):
2. For every H E F(9), the edge set of is a subset of the edge set of CP)));
3. The intersection of the edge sets of all H. E F(G) equals the solid edges of CP(G);
4. For every H Eg), lei (P()) its own presentation. Then, CP can be transformed into CP(G) via an T-relabel and a cycle reversal (alongside the solid/dashed edge types).
It is worth noting that dashed edge in a presentation means that there exists at least one equivalent digraph without this edge. However, it does not imply that dashed edges can be arbitrarily removed without affecting equivalence: they have to obey the rank constraints. This is in similar spirit of undirected edges in a CPDAG: an undirected edge means that there exist at least two equivalent DAGs who have different orientations on this edge. However, it does not imply that undirected edges can be arbitrarily oriented: there are additional constraints like no new v-structures, no cycles, etc.
We are not sure whether such additional constraints can, should, be also incorporated into the presentation, or at least summarized as a set of rules like Meek rules (especially given the availability of interactive traversal tool). But in any case, we put here possible future step:
Step 4. Quantifying bounds on edges between vertex groups. Extending step 3, one may describe bounds on the number of edges between vertex groups (e.g.. "at least 2 and at most 4 edges from vertices Y vertices ""). Such constraints may be presented like "underlined bows" in cyclic digraphs (Richardson) 1996) or "hyperedges" in mDAGs (Evans) 2016). We have not developed this result (though we hypothesize that they likely also follow from Theorem 2, because we are not sure how much practical informativeness it can offer to users.
Lastly, we also list the presentation of prior knowledge as a future step.
Step 5. Incorporating additional prior knowledge. As with other equivalence presentations, prior knowledge such as acyclicity, stable cycles, or certain causal orderings can further refine the cquivalence class and its presentation (Perković al., (0177) While we have not explored this part either, it motivates future theoretical developments, such as interventional equivalence classes, and parameter identifiability results based on the equivalence class established in this work.
C.4 EXAMPLES OF NON-RANK CONSTRAINTS IN MIXING MATRICES
In Lemma we have shown that path rank equivalence in mixing matrices sufficiently lead to distributional equivalence. However, this does not imply that there are no other constraints in mixing matrices. As an analogy, in the causally sufficient linear Gaussian system, CI equivalence (zero partial correlations in covariance matrices) sufficiently lead to distributional equivalence, but there are still other constraints, like the Tetrad constraints in the covariance matrices.
Below we give an example of non-rank constraints in mixing matrices.
Consider digraph G with 4 vertices:
a
d
2
4
b
38

---

Published as a conference paper at ICLR 2026
Its mixing matrix is:
2
4
bc
c
c
2
cde
1
A
(C.1)
3
ab +
de
abc
cde
bed
od
1 abc
We can verify the following constraint holds:
A2,1 A3,2 A4,1
A2, A3,4 A1.2
ace x xd X bed
(C.2)
= 0.
Just like rank constraints, this constraint is also immune arbitrary column scaling, that is, it also survives in the OICA estimated mixing matrix. However, this not a rank constraint.
One may also verify some other non-rank constraints in this A, for example.
A2,2 A3,4 A4,1 + 22,4 A3,1 A42 A2,1 A3,2 A4,4
(C.3)
A2,1 A3,4 As.2 An A3,1 A4,1
and
A2,, A3,1 A3.2 A4,2 + A2,1 22, 13,4 A4,2 + A2, A2, A3,2 As,4
(C.4)
= 2 A2,1 22,4 A3,2 As,4 A4,2 + A2,2 A2,1 A3,1 A3,2 As,4:
both of which are also immune to column scaling.
We are sure whether there are any specific geometry interpretations underlying these equality constraints. These examples are brutal-force searched from ideal elimination.
We notice that these equality constraints occur among the {2,3, 3, 4} rows, meaning that when vertex {1} is latent and {2,3, 4] observed, these constraints will also appear in the OICA mixing ma- trix. Fortunately, with Lemma we know rank constraints alone can determine the distributional equivalence, the equivalence among these constraints well.
For example, one may verify that these constraints also occur all digraphs in the equivalence class, shown below, while this equivalence class is obtained only by the rank-based criterion (which trivial in this case since only cycle reversals are applied).
2
3
Note that the nice result Lemma 3 only occurs at the linear non- Gaussian case, where path ranks one-sided, so that it can be directly dualized to transversal matroid that can be represented by vectors that lie in the faces of some simplex.
In the linear Gaussian case, with the two-sided path ranks in covariance matrices, there can be more constraints. In that setting, however, rank constraints equivalence do not necessarily imply distributional equivalence: there can be other unmatched equality constraints, c.g., the Pentad, Hexad constraints and beyond (Drton et al. 2007), let alone other inequality constraints.
C.5 RELATED WORK
Equivalence characterizations We first review various approaches to characterize equivalence of causal models. At the same time, we summarize the multiple results developed in this work and situate them within this broader landscape of related literature.
39

---

Published as a conference paper at ICLR 2026
Table A side-by-side overview representative works on equivalence characterizations across different settings using different approaches. The final column summarizes this work's contributions.
Distributional equivalence in LING models with latents and cycles (this work)
Markoy equivalence in fully observed acyelic graphs
Markov equivalence in acyelic graphs with latents
Settings
"Same path/edge ranks up to permutation"
Level
"Same d-separations"
"Same d-separations"
(Lemmas and 5
"Same FCI outputs"
(Spirtes & Verma 1992):
"Same MAG adjacencies. v-structures, and colliders
"Same adjacencies and minimal complexes/ v-structures" (Frydenberg)
"Same bases in children for L itself and with each singleton X,, up to permutation" (Theorem
discriminating paths"
Level 2
Structural
T990; Verma Pearl
Spirtes & Richardson
1996 Richardson & Spirtes 2002): "Same head
1991
and tails (Hu & Evans
2020
"Arrowhead completeness"
"Maximal (deflagged)
(Ali al. 2005); "Full
chain graphs; essential
completeness of PAG
"Unique maximal equivalent graph with edges that must always appear, up to cycle reversal" (Theorem
graphs" (Frydenberg)
orientations" (Zhang
1990:
Andersson et al.
2008a); With background knowledge (still
Level
1997
Roverato al.]
2006);
"CPDAGs" (Spirtes
incomplete; (Andrews al. 2020; Venkateswaran & Perkovic 2024))
& Glymour 1991
Meek
1995
"Covered edge reversal (Meek conjecture)"
"Covered edge reversal"
[Chickering 1995 Meek
"Admissible edge additions/delltionss and cycle reversals" (Theorem) 3)
(Zhang Spirtes 2005
Transfor- mational
1997] Chickering 2002):
Tian 2005/Ogarrro et al.)
"Weakly covered edge
2016
Claassen & Bucur 2022
reversal" (Markham et al.,
2022) for unconditional
equivalence
DAGs traversal within one
BFS/DFS by admissible transformations (Theorem 3p. with additional parallel speedup by column decomposition (Lemmas 9 and [2)
CPDAG (Meek 1995:
Chickering 1995
MAGs traversal within one
Traversal algorithms
Wienöbst et al. 2023);
PAG (Wang al. 2024
CPDAGs traversal
2025
(Steinsky 2003 Chen
let al.
2016)
In general, approaches characterize equivalence can be categorized into three types:
Structural characterizations, which provide conditions for determining equivalence be- tween given graphs, and give rise to summary presentations. However, they do not directly lead to equivalence class traversal methods. They can be further stratified by their complexity, informativeness, purpose, follows:
40

---

Published as a conference paper at ICLR 2026
Level 1. Graphical conditions necessary and sufficient for determining equivalence, but more as definitions than practical criteria; usually require combinatorial complexities.
Level 2. Practical graphical criteria for determining equivalence; still necessary and sufficient, but more efficient than Level 1.
Level 3. Sound and complete conditions or presentations that summarize the equiva- lence class. While Level 2 criteria efficiently determine equivalence, they do not fully capture what can be identified; Level 3 addresses this gap. Level can also be used for determining equivalence, but will be less efficient than Level 2.
2. Transtormational characterizations, which provide natural ways for traversing the equiva- Ience class, and are useful for developing score-based algorithms. However, as a comple- ment, they are not suited for directly determining equivalence between given graphs, or for developing summary presentations to the equivalence class.
3. Traversal algorithms, for enumerating, sampling, or counting elements of the equivalence class, where transformational characterizations are usually helpful.
We present in Table 2 side-by-side overview of representative prior works and this work across these approaches in different settings. This unified view may help to better understand the contributions of this work, and as well to clarify the methodological implications among these approaches.
There is also a wide range of additional work characterizing equivalences under many other settings, which are not put in Table Doole/dus due to space limit. These include efforts to develop Markov properties and establish Markov equivalence in fully observed models with cycles, such as in linear Gaussian settings (Richardson) 1996] Claassen & Mooij, 2023), discrete settings (Pearl & Dechter 1996). and general nonlinear settings (Spirtes Forré & Mooij 2017: Mooij M00j
& Claassen| 20220), as well as nonlinear settings with latent variables and selection bias Yao & Mooij, 2025). The distributional equivalence of fully observed linear Gaussian cyclic models has been studied in Ghassami al. (2020); Drton et al. (2025b). Nonparametric equivalence with latent variables (usually referred to as Memi-Markov models) has also been characterized in (Evans 2018 Markham & Grosse Grosse-Wentrup!
2020 Jiang& & Aragam| 2023 Richardson et al. 2023). beyond the original CI constraints (Richardson
Spirtes 2002] Zhang (008a). When interventions or multi-domain data are involved, Markoy equivalence (typically as Cls in each domain and invariant changes across domains) has been studied extensively in (Tian & Pearl [2001] Eberhardt et al. 2005 [Eberhardt & Scheines 2007 Eberhardt
2008: He & Geng, 2008 2008 Hauser & Büühlmann] 2012 2015|
et al.] 2015] Rothenhäusler et al. 2015 Meinshausen et al. [006]] Magliacane et al. [016] Ghassami et al. 2017 Wang et al. 2017 7
Yang et 2018 Kocaoglu et al. [2019] Huang al. [2020] Mooij et al. 2020; Squires al. 2020
Zhang et al., 2023 Dai et al. 2022a Luo et al. 2025 2026 Yao et al. 2025). with various focuses
spanning across latent variables, selection bias, unknown intervention targets, active experimental
design, and so on. From a method view, transformational characterizations have gained increasing
attention recently, including (Ghassami et al.. 2020 Markham et al., 2022 Wang al. 2024 2025
Johnson & Semnani
2025 Améndola et al. 2025)
Below, we then provide more comprehensive review of the relevant literature on latent-variable causal discovery, in particular those under the linear non-Gaussian models (Shimizu et al. 2006).
Parametric settings for latent-variable causal discovery A prosperous line of statistical tools beyond conditional independencies have been developed. These include rank constraints (Sullivant et al. 2010; Spirtes et al. 2000)) and more general equality constraints (Drton] (001)) in the linear Gaussian setting; and high-order moment constraints (Xie et al. 2020: Adams et al. 2021 Robeva
Seby 202T; Dai et al., 2022: 2024, Chen et al.] 2024a] Xia et al. (0026, which exploit non-
Gaussianity for identifiability. In addition to these, matrix decomposition methods (Anandkumar
al. 2013), copula-base based constraints (Cui et al. 2018). and mixture oracles (Kivva et al. 2021
were also developed.
Algorithms for latent-variable causal discovery Building on these statistical tools, many latent variable causal discovery algorithms have been proposed. Many of them fall within the constraint- based framework, by using CI tests and algebraic constraints to infer causal relations. Examples
include those based rank or tetrad constraints (Silva et al. 2003 2006 Silva & Scheines 2004
41

---

Published as a conference paper at ICLR 2026
Choi et al. 2011 Kummerfeld & Ramsey 2016 Huang et al. 2022 Dong et al. 2024: 2025) Recent
efforts have also attempted to formalize score- based methods for variable causal discovery
(Jabbari et al. 2017: Ng al. 2024 Dong et al. 2026
Linear non-Gaussian models
Thanks to the strong identifiability results given by OICA, the linear
non- non-Gaussian models have received much attention for causal discovery with latent variables or cycles:
(Améndola et al. [2023; (Saehkklleybrr et al. [2020] Wang & Drton [2233] Maeda & Shimizu 2020
Silva & Shimizu 2017: Dai et al. [2024] Yang et al. 2022 2024;
Shimizu 2022; Drton et al.) 2025a
Liu et | 2021 Schkoda et al. 2024. Trammonaano et al. [022] Rothenhäusler et al. 2015), together
with those discussed in | and many more. Beyond structure learning, LiNG models also provide
benign conditions for many other tasks, including causal effect identification (Tchetgen Tchetgen et al.
2024; Kivva et al.] [023] Xie et al. [2022] Tramontano et al. 2024; (025)), model selection (Schkoda
& Drton 2025), covariate selection (Zhang & Wiedermann 2024). experimental design (Sharifian
et al. 2025), etc.
Below, we also discuss how the results in this work, especially the edge rank tools and the motivation of a bipartite matching view, may be generalized to other parameter settings.
For the linear Gaussian setting, existing results in the literature can be directly translated into our edge rank language. Unlike the -on-Gausiian setting where the mixing matrix is identifiable, in the Gaussian setting, only the covariance matrix is available. The graphical characterization of covariance matrix ranks, known as "trea--cparation."" " has been established by Sullivant et al. (2010). Specificallyy the concept of bottleneck, which we term the "path rank" on the one-sided directed paths, is extended to the bottleneck along the two-sided directed paths, known as "treks". Since the duality between path ranks and edge ranks hold universally in graphs regardless of the parametric setting, the existing characterization on trek-based path ranks can be directly translated into trek-based edge rank language. As for the technical roadmap, one may first note that the non-Gaussian equivalence condition we build in this work is necessary but not sufficient for the Gaussian setting. That is, two graphs that are equivalent in non- non- Gaussian models are guaranteed to remain equivalent in Gaussian models; however, graphs that are distinguishable under non Noon-Gassiaaity may collapse into the same equivalence class under Gaussianity. We see the closing of this gap as the most immediate future direction for extending our current work.
For the discrete setting, our results are likely generalizable as well. Several recent works have explored path ranks in graphs from discrete data (Gu & Xu, |023] Chen et al.) [0024b 2025 Lyu & Yang 2025), where the algebraic counterpart becomes the tensor ranks the contingency table (Teicher
1967). However, a precise graphical characterization, analogous to "trek-separatiion in the Gaussian case above, has yet to be developed. That said, such a characterization is promising, since the linear Gaussian and discrete models behave similarly in many aspects. For example, both are closed under marginalization and conditionalization; both admit a correspondence between Markov and distributional equivalence, in both cyclic and acyclic cases (Geiger & Meek 1996 Pearl & Dechter 1996). Motivated by these parallels already noted in literature, we believe our results can also extend the discrete setting, and will be directly applicable once the corresponding graphical characterization is developed.
For nonlinear or even nonparametric settings, theoretical generalization remains possible. When the model is partially linear and partially nonlinear, low-dimensional bottlenecks in the linear component remain directly observable through covariance ranks (Spirtes) 2013). When the model is fully nonlinear or even nonparametric, there also exists prior results on the identifiability of latent-variable models (Hu) 2008; 2017). Although the techniques differ, the underlying motivation remains closely related to ranks, particularly those in the Jacobian matrix. However, despite the theoretical meaningfulness, the practical estimation and reliable testing of these ranks remain an open challenge. This challenge can be echoed by viewing rank constraints as generalizations of conditional independence constraints. In linear models, conditional independencies correspond to low ranks in the covariance matrix and can be directed tested via Fisher's Z. test. In contrast, robust conditional independence tests in nonlinear settings are still under active development (Duong & Nguyen 2024 Yang et al. 2025).
42

---

Published as a conference paper at ICLR 2026
D EVALUATION RESULTS
D.1 QUANTIFYING THE SIZES EQUIVALENCE CLASSES
For different numbers of vertices and latent vertices report the total number of weakly connected digraphs with vertices. the subset that are irreducible when the first vertices are latent (both with and without L-isomorphic variants), and the corresponding Table 3: numbers of distributional equivalence classes they fall into. The final two columns present statistics on how irreducible digraphs (both with and without L-isomorphic variants) are distributed among those equivalence classcs.
300
401
803
403
Stats of #digraphs per
Ioby Sittrmakee gem cilwed
class (unique up
L-relabeling ling)
3
M01131
Stats of Adigraphs per class (with L-isomorphic variants
Garge
#DDstributionall equivallent sunivalence
90.085 3990
12,608 550
41
1,788
201
230,436
28.650
783
453,742
3,297
#lreducible digraphs (unique up to (-relabeling)
54
3,834
464
1,027,080
712,512
242,320
50,112
1,067,308,
8G8. 762,
352, 352.061,220 ,248
93.975.744
17.646.433
AIrroducible digraphs (with L-isommrrhiic variants)
54
16
3,834
2,000
896
1,027.080
712.12
480,640
294.400
1067,308,488
R68.762.432
702.697.497 .722
560.760.320
419.405.834
#Latents
(3, 79,566,762222 DAG5) DAGs)
#All weakly
connected digraphs
54 (18 DAGs)
3,834 (446 DAGs)
1,027,08 ,000
(26,430 DAGs)
1,067.30 308 488
#Nodes
43

---

Published as a conference paper at ICLR 2026
D.2 ASSESSING GLVLING ALGORITHM'S RUNTIME
Table 4: Running time comparison between our glvLiNG algorithm and mixed integer linear programming (MILP) baseline for constructing digraphs that satisfy the rank constraints of oracle OICA mixing matrices. Ground-truth graphs generated from the Erdös-Rényi model with total number vertices n and average in-degree avgdeg, with 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 seconds. Experiments on an Apple M4 chip.
i avgdeg
MILP
glvLiNG
givLiNG Phase
glvLiNG Phase 2
0.013 0.112 = 0.008
0.045
0.015 0.005
0,014 0.005
0.001 0.000
1
3
0.020 + 0.002
0.019 + 0.002
0.001 + 0.000
0.101 = 0.045
0.098 = 0.044
0.002 = 0.000
1
3
0.169 + 0.024
0.165 0.024
0.004 + 0.000
37.402 + 0.000
0.048 = 0.013
0.045 = 0.012
0.003 + 0.001
3
0.083 = 0.014
0.075 0.013
0.007 0.001
0.691 0.304
0.687 0.303
0.004 + 0.001
3
1.129 = 0.191
1.122 + 0.190
0.007 + 0.001
0,319 0.091
0.308 0.090
0.009 0.001
3
3
0.667 = 0.132
0.634 + 0.128
0.031 + 0.007
0.082 +: 0.023
0.075 + 0.022
0.005 + 0.001
5
0.260 0.057
0.230 0.051
0.023 + 0.005
3.637 + 1.533
3.630 1.532
0.007 + 0.000
1
7.706 0.883
7.693 0.881
0.013 0.002
2.174 0.499
2.142 0.500
0.030 0.002
3
3
4.979 + 0.763
4.873 + 0.748
0.102 + 0.021
0.530 + 0.111
0.492 + 0.111
0.032 + 0.002
5
2.348 0.426
2.170 0.396
0.159 + 0.045
22.838 + 9.6667
22.827 = 9.667
0.011 + 0.001
1
38.173 + 7,725
38.155 7.721
0.017 + 0.005
13
12,501 + 4.602
12.404 = 4.593
0.094 + 0.016
3
3
23.517 5.807
23.362 = 5.751
0.150 - 0.062
4.277 1.430
4.069 1.433
0.190 0.009
5
3
13.150 + 4.009
12.376 + 3.712
0.723 12233:00 0.310
44

---

Published as a conference paper at ICLR 2026
D.3 BENCHMARKING EXISTING METHODS UNDER ORACLE INPUTS
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ényí model with total number of vertices and average in-degree avgdeg, with 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 larger (which seems not happened), we planned to choose removal that leads to best result. Finally, the best possible result is reported, i.e., choose the digraph in the ground truth equivalence class that is closer to their output as the truth. The latent variables are viewed unlabeled.
l
avgdeg
PO-LiNGAM
LaHiCaSI
15.48 2.75
31.64 4.62
24.30 = 4.41
36.80 + 4.22
3
35.40 3.61
39.96 4.88
4
45.22 = 3.53
41.04 + 3.81
10
18.04 = 3.99
32.36 + 4.38
28.44 = 3.48
36.68 4.31
5
39.18 = 3.60
40.42 = 4.40
50.00 + 3.45
41.00 + 4.57
31.10 + 4.87
74.22 + 8.04
48.26 6.67
76.80 6.66
3
64.12 = 5.59
81.64 = 8.28
84.60 = 5.73
85.56 8.61
35.02 + 5.74
71.70 6.94
15
54.84 6.04
78.44 7.01
5
72.96 = 6.62
79.98 + 8.15
92.28 7.71
82.50 7.35
36.44 5.63
71.34 8.37
58.00 + 6.24
77.90 + 8.25
7
79.90 = 7.34
79.16 8.79
101.04 = 5.90
84.56 = 8.99
48.60 6.12
129.88 14.18
76.92 = 8.29
136.36 + 13.05
3
103.04 = 8.30
138.24 11.98
129.14 = 10.46
146.86 + 13.02
54.04 = 5.23
122.78 = 12.67
84.10 = 8.44
136.04 = 12.85
5
115.72 + 8.72
139.76 13.64
20
146.44 + 9.10
141.64 10.75
58.70 + 6.36
128.46 + 11.96
92.86 8.41
132.48
12.36
7
124.00 + 9.60
140.76 + 12.31
155.48 = 7.83
143.76 = 11.55
64.40 = 7.38
120.08 12.43
98.04 10.43
135.24
12.75
9
134.16 + 10.34
137.52 + 12.30
167.86 11.28
142.76 11.39
45

---

Published as a conference paper at ICLR 2026
D.4
EVALUATING GLVLING's PERFORMANCE WITH EXISTING METHODS IN SIMULATIONS
OICA estimation part
We first describe how handle the OICA estimation part.
For our choice of OICA implementation, we have tried multiple options and find that overall, the MATLAB implementation 2 of SDP-ICA (Podosinnikova et al. 2019) tends to provide best estimated mixing matrices across multiple settings. We thus adopt it in our experiments.
For the number of latent variables, although theoretically identifiable, existing OICA implemen- tations still require specifying this number as an input. Hence, following the common practice as in (Salchkaleybar et al.) 2020), we test multiple candidate values and select the one minimizing the loss on a held out set.
Handling empirical ranks in OICA matrix We then explain how we process the mixing matrix estimated from OICA. Having obtained an OICA-estimated mixing matrix, the core task of glvLiNG becomes constructing bipartite graph to realize the rank patterns this mixing matrix, which define a transversal matroid. When OICA is not an oracle, these empirical ranks may violate matroid axioms, just like how conditional independencies in data may violate a graphoid in nonparametrie settings.
To address this, in our implementation, we assign "full-rank confidence score" to each relevant block of A. Specifically, let miin be A's 's minimum singular value, we use the score 1+exp(-o((win) -+) and in experiments, we set a = 25 and = 0.02. Then, in phase I (recovering latent outgoing edges), approximate the closest valid transversal matroid that maximizes agreement with these scores. In phase 2 (recovering observed outgoing edges), for efficiency we simply threshold these scores to determine each variable's 'ss outgoing edges independently. We have simulated and verified that this procedure is robust to moderately noisy ranks, by e.g., assigning true full-rank blocks scores from (0.775, 0.2) and others from (0.255, 0.2), both 0, truncated.
Simulation setup In simulation, we compare glyLiNG with existing methods including LaHi- F (Xie et al. 2024) and PO-LiNGAM Jii et al. 2024). We generate random Erdös-Rényi model with total number of vertices from 5 to 13, number of latent variables from to 5, average in-degree d of and 3, and sample size N from 1, 000 to 200, 000. We sample data with linear causal weights uniformly from 2-2., -0.5] U (0.5. 2.5]. and exogenous noise are sampled from uniform distribution [-0.5, 0.5). following (Podosinnikova et al. 2019). We calculate the minimum SHD between all graphs in the true equivalence class to the discovery output graph as the SHD result.
Simulation results The results are presented in Figure From we have the following observa- tions:
First of all, is not surprising to see that LaHiCaSI and PO-LiNGAM perform better when the graph is sparser. For example, when d = 1, these two methods perform better than glvLiNG, though the difference remains modest. This is perhaps because, when the graph is sparser, maintaining irreducibility typically means more edges outgoing from latent variables, while edges from observed ones to others are fewer. This aligns well with the model assumptions of these two methods. For example, LaHiCaSI assumes a hierarchical latent-variable model in which all observed variables are leaf nodes. Given this additional benefit from their sparsity constraints, and the fact that both LaHiCaSl and PO-LiNGAM estimates ranks using the GIN condition which is more efficient than OICA, it is not surprising to see that they perform better in this setting.
However, when the graph is denser, givLiNG performs particularly better. For example, when d = glvLiNG consistently outperforms the other two methods, and the difference is considerable. This is perhaps because, when the graph denser, more complex structures become common, including ar- bitrary edges between latent and observed variables, as well as cycles. Model assumptions of existing methods are more likely to be violated, making them less effective at recovering these structures. In contrast, with ausetural-assupptiin still allows the recovery of these structures.
design, givLiNG avoids such model misspecification, and
46

---

Published as a conference paper at ICLR 2026
gIVLING
LaHiCaSI
PO-LINGAM
8= B.I,aa d=1
2=3,d=1
(=5, d=1
1= d=3
d=3,d=3
(=5, d=3
10
20
SHD (mean:sta), lower better
10
40
20
60
40
R=13
20
10 10 10"
10¹ 10
10
10
10
10"
10
10
10
10
10
107
10'
10
10'
Sample size (log scale)
Figure 7: Simulation results comparing gIvLiNG 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 É, and the average degreee d. Mean and standard deviation of SHD calculated from 25 random irreducible models.
We also observe that glvLiNG tends be more robust latent dimensionality. For example, when = 13 and d = 3. increasing the number of latents l from 1 to 5, the average SHD of glvLiNG increases from 33.1 35.7, while other method, such PO-LiNGAM, increases from 35.3 50.7. This is perhaps because glvLiNG jointly recovers all latent- latent-ouggoing edges at once, using an OICA mixing matrix whose dimensionality is already fixed. In contrast, the other two methods requires incrementally clustering and adding latent variables.
D.5 ANALYZING REAL-WORLA DATASET WITH GLVLING ALGORITHM
For the real-world experiment, we use a Hong Kong stock market dataset that involves the daily dividennd/slli-aajjsstd closing prices for 14 major stocks from January 4, 2000 to June 17, 2005 (1331 samples). These stocks represent the dominant sectors of the market: of them are on banking (HSBC Holdings, Hang Seng Bank, Bank of East Asia), 5 on real estate (Cheung Kong, Henderson Land, Hang Lung Properties, Sun Hung Kai Properties, Wharf Holdings), 3 on utilities (CLP Holdings. HK & China Gas, HK Electric), and 3 on commerce (Hutchison. Swire Pacific A', Cathay Pacific Airways). All of them were constituents of Hang Seng Index (HSI), and they were almost the largest companies of the Hong Kong stock market at the time.
By applying gIvLiNG on this dataset, we recovered an equivalence class of causal graphs containing 2 latent variables. The presentation (see Appendix C.3) of this equivalence class is shown in Figure Here is summary: the class consists of 19,008 causal graphs with 16=14+2 vertices, and among them the numbers of edges range between 29 34. In the presentation, there are 20 "solid" (must appear) and 14 "dashed" (may appear) edges.
This result suggests several interesting observations, follows:
47

---

Published as a conference paper at ICLR 2026
Seng
Caiber
Warfilllog
Chllaag Tang
Arts
<i:Chearg Keng
all Sux Harp Pryp
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 at least one equivalent graph(s).
1. Large banks seem to be major upstream causes. For example, the two largest banks, HSBC Holdings and Hang Seng Bank, together form 2-cycle that has 9 children across sectors, but there are no edges into them.
2. Real estates, in contrast, seem to be downstream effect receivers. For example, Cheung Kong has 10 parents, but only edge pointing out from it.
3. Utilities are heavily involved in cycles. For example, among 17 simple cycles in the graph, CLP Holdings belongs to of them. These cycles are often across sectors as utilities real estate commerce utilities.
4. One latent variable seems interpretable. It has one parent HSBC Holdings, and three children (all with solid edges): Cheung Kong, Hutchison, and Swire Pacific 'A', Among them. Cheung Kong and Hutchison were core holdings of same group.
5. Stocks under the same sector tend to be connected more closely.
48


Reviews:
[{"review_id": "DJs2iB9qYs", "reviewer": "Reviewer_GjKP", "summary": "The paper studies characterization and learning of distributional equivalence classes in linear non-Gaussian models with latent confounding and cycles. It first gives a graphical condition under which a latent variable is not reducible and a reduction procedure to the irreducible form. It then relates the rank of submatrices of the mixing matrix $A$ to path rank (a global property that is costly to check) and introduces a local notion, edge rank, proving a duality between the two. Using edge ranks, the paper provides a graphical characterization of equivalence (Theorem 2) and a way to traverse the class. The learning pipeline runs OICA to estimate columns of $A$ up to scaling/permutation and then applies the graphical operations to recover the equivalence class.", "questions": "- For linear non-Gaussian cyclic models without latent confounding, (Sharifian et al. 2025) characterized the distributional equivalence class and showed it corresponds to perfect matchings in a bipartite graph. It would be valuable to check whether your paper’s equivalence conditions (via edge rank) reduce to theirs in the no-latent case.\n\n- In the acyclic setting with latent confounding, (Salehkaleybar et al. 2020) gave graphical conditions when a model is irreducible. It would be good to clarify that your irreducibility condition matches the one in there in acyclic models.\n\n- Given only a recovered $A$ from OICA, how should we test the coloop condition in Lemma 7? How can we have a robust solution in the finite sample case?\n\n- What is the computational complexity of the two phases in the learning algorithm?\n\nSharifian, E., Salehkaleybar, S., & Kiyavash, N. (2025). Near-Optimal Experiment Design in Linear Non-Gaussian Cyclic Models. arXiv:2509.21423. \n\nSalehkaleybar, S., Ghassami, A., Kiyavash, N., & Zhang, K. (2020). Learning Linear Non-Gaussian Causal Models in the Presence of Latent Variables. Journal of Machine Learning Research, 21(39): 1–24.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- A local graphical notion (edge rank) that makes rank constraints easier to verify.\n\n- A full graphical characterization of distributional equivalence with latent variables and cycles.\n\n- A constructive traversal algorithm for the equivalence class with the admissible moves.", "weaknesses": "- As mentioned by the authors, the learning algorithm relies on solving the OICA problem, which, in general, is hard to solve with existing methods. That being said, the result of characterizing the equivalence class has a theoretical contribution regardless of the learning algorithm.\n\n- The evaluation mostly counts class sizes and compares to a MILP baseline for rank-realization under oracle ranks. There is no empirical test in the finite sample case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RT29NIklPY", "reviewer": "Reviewer_FDU9", "summary": "The paper provides a transformational characterization of observationally equivalent latent linear nonGaussian (possibly cyclyc) directed graphical models, including helpful tools (edge ranks, and an interactive equivalence class explorer) along the way, as well as an ICA-based learning algorithm.\nI think this is a solid paper considering the foundation it provides for future work and the interesting mathematics it uses, but it perhaps falls short in terms of potential for direct impact, due to its theoretical focus.", "questions": "The main reason I didn't rate the paper higher is because of limited (direct) potential impact. I think this is inline with how the authors present the work in the paper (e.g., presenting the glvLiNG algorithm as a \"proof of concept\" rather than a practical tool for causal discovery from real data), but nevertheless answers to the following questions could lead me to increase my rating: \n1. Do the authors have any real-data applications in mind, where the learned equivalence classes are sufficiently informative? I'm thinking of how a CPDAG can still be relatively useful in practice, while it's less clear how useful one of these equivalence classes would be.\n2. Any ideas for an interpretable representative a given equivalance class (analogous to a CPDAG)?\n3. Any ideas for how to refine these to interventional equivalence classes?\n\nThe following are suggestions I hope the authors will find useful but that don't require a response and don't affect my rating:\n1. Without providing finite sample guarantees, it doesn't really make sense to talk about \"identifying\" a graph from data---the graph is rather identified from (parameters of) the data-generating distribution. In many but not all instances, the paper correctly uses \"recover\" (and \"estimate\" or \"learn\" would also be appropriate words) for this case, but there are still some places where \"identify\" is used incorrectly (including L015, L027, L064).\n2. L211: \"share the same latent variables\" seems too strong; can the authors justify the step from the same *number* of latents in the previous sentence to the same latent variables here? or use more precise language here if nothing more is meant.\nwriting: L238 (\"is\" -> \"are\", or \"constraints\" -> \"constraint\"), L297 (\"to the\" -> \"in\"), L346 (\"in edges term\" -> \"in terms of edge ranks\").\n3. reference formatting: ensure all words (e.g., 'Bayesian') are capitalized correctly; use the correct characters in Dénes Kőnig's name.\n4. Consider adding additional citations, e.g., to work on transformational characterizations for other settings [1], [2], [3], [4], [5], and identifiability in nonparametric latent measurement models (without graphical assumptions beyond acyclicity) [6], [7], [8].\n5. Remove the \"if not all\" part in the second sentence of the abstract. Papers [6], [7], and [8] (and I imagine others) don't make structural assumptions---they just use minimality, which is essentially the author's irreducibility but for identifiability up to nonparametric independence model equivalence rather than up to LiNG distributional equivalence.\n\n[1] Zhang, J., & Spirtes, P. (2005). A transformational characterization of Markov equivalence for directed acyclic graphs with latent variables. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (pp. 667-674).\n\n[2] Chickering, D. M. (1995). A Transformational Characterization of Equivalent Bayesian Network Structures. In UAI (pp. 87-98).\n\n[3] Johnson, J., & Semnani, P. (2025). Characteristic Imsets for Cyclic Linear Causal Models and the Chickering Ideal. arXiv preprint arXiv:2506.13407.\n\n[4] Markham, A., Deligeorgaki, D., Misra, P., & Solus, L. (2022). A transformational characterization of unconditionally equivalent Bayesian Networks. In International Conference on Probabilistic Graphical Models (pp. 109-120). PMLR.\n\n[5] Améndola, C., Boege, T., Hollering, B., & Misra, P. (2025). Structural Identifiability of Graphical Continuous Lyapunov Models. arXiv preprint arXiv:2510.04985.\n\n[6] Markham, A., & Grosse-Wentrup, M. (2020). Measurement dependence inducing latent causal models. In Conference on Uncertainty in Artificial Intelligence (pp. 590-599). PMLR.\n\n[7] Jiang, Y., & Aragam, B. (2023). Learning nonparametric latent causal graphs with unknown interventions. Advances in Neural Information Processing Systems, 36, 60468-60513.\n\n[8] Pearl, J. and Verma, T. (1995). A theory of inferred causation. In Studies in Logic and the Foundations of Mathematics, volume 134, pages 789–811. Elsevier.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- addresses an important open problem\n- provides a rigorous, elegant solution\n- overall well written, including helpful examples", "weaknesses": "The main weakness is the lack of immediate applicability to real problems. While the paper makes great progress on an extremely challenging problem, it remains unclear to me (and unsupported by the experiments) how useful the current implementation actually is. If the authors could provide a real-data application and show meaningful practical interpretation of the (accurately) learned equivalence class, I would change my mind about this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OoO0wbUBJL", "reviewer": "Reviewer_Tajr", "summary": "This paper studies a fundamental problem in causal discovery: the distributional equivalence criterian of causal structure from observational data when both latent confounders and cycles are allowed, in linear non-Gaussian models. It provides graphical characterization of equivalence class under arbitrary latent structures and loops via path and edge rank constraints. It also provides graphical transformation rules to traverse within equivalence class. An algorithm glvLiNG is proposed for structure learning from data.", "questions": "- Do the geometric equivalence results in this paper, such as Lemma 3, 5, 6, generalize beyond LiNG models? It seems they also hold in general models. \n- What is formally the faithfulness assumption in Line 440-441 for the proposed algorithm to work?\n- Alhough improving on Lemma 3 from paths to edges, it is still hard to check equivalence via Lemma 5, as one needs to verify for all sets of variables $Z,Y$. The condition is is still not as clean as simply stating something like \"same skeleton + v-structures\".", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work is the first equivalence characterization for causal models with latent variables and cycles, providing the foundation needed for future assumption-free latent causal discovery.\n- It introduces the edge rank constraints, a new local graphical tool complementing path-rank constraints.\n- It provides clean connection between algebraic rank constraints and graph operations.\n- The examples provided in Figure 1-3 are helpful for readers to understand the concepts.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oDnFGJRWl0", "reviewer": "Reviewer_Czvx", "summary": "In this paper, the authors propose a characterization of equivalence classes of causal graphs with both latent variables and cycles. To this end, they propose a novel graphical tool of edge ranks (which is dual to path ranks), which makes results cleaner and more intuitive than path ranks do. They further provide a straightforward algorithm to traverse this set of distributionally equivalent causal models.", "questions": "1. Your paper currently focuses on minimal DGs, where minimality is measured in terms of numbers of variables. However, one might also be interested in minimally cyclic graphs, at the cost of more latent factors. Is there any way to establish results to determine equivalence classes of such graphs?\n2. Your paper currently makes LiNG assumptions. However, low-dimensional bottlenecks should still be noticeable in linear Gaussian, or in nonlinear settings. What prevents us from generalizing the approach to these cases?\n3. Given this classification of equivalence classes, is there any hope (and need) for a GES-like algorithm to learn the (equivalence class of) the causal graph? Would this provide any benefit?\n4. Would it be possible to explain more about why certain graphs are not equivalent? For example, in the example in section C.2, Figure 5, one could think that the graph $G_1$, but with the edge $X_3 \\rightarrow X_1$ removed (equivalently, $G_10$ with the edge $X_3 \\rightarrow X_2$ removed) might lie in the same equivalence class. \n\nAs a side note, it appears that your sections D.1-D.3 and their contents are currently struggling a little with formatting.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The classification of equivalence classes of causal models with cycles and latent variables is an important topic.\n2. Edge ranks seem to be a very useful tool for future results.\n3. Despite the complexity of the topic, the paper is clearly written and examples are well-chosen.", "weaknesses": "1. It would be nice to have a little more description of the algorithm in the main paper, especially the decomposition of global rank constraints into local rank queries.\n2. It is unclear how this method works when we do not have an OICA oracle, and in particular when we don't know the number of latent variables.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)