Faster Generic Identification in Tree-Shaped Structural Causal Models
Authors: Yasmine Briefs
Markus Bläser
Venue: NeurIPS 2025 poster ()
Keywords: causality
generic identification
structural causal models
linear structural equation models
Primary area: probabilistic_methods
TL;DR: We provide a faster algorithm for generic identification in tree-shaped linear structural causal models.

Abstract: Linear structural causal models (SCMs) are used to analyze the relationships between random variables. Directed edges represent direct causal effects and bidirected edges represent hidden confounders. Generically identifying the causal parameters from observed correlations between the random variables is an open problem in causality. Gupta and Bl\"aser solve the case of SCMs in which the directed edges form a tree by giving a randomized polynomial time algorithm with running time $O(n^6)$. We present an improved algorithm with running time $O(n^3 \log^2 n)$ and demonstrate its feasibility by providing an implementation that outperforms existing state-of-the-art implementations.

Faster Generic Identification in Tree-Shaped Structural Causal Models
Yasmine Briefs for Informatics Saarland Informaties Campus Saarbrücken, Germany ybriefs@mpi -ipppi--nnf iinf .mp..de
Markus Bläser
Saarland University
Saarland Informaties Campus
Saarbrücken, Germany mblaeser&cs uni -sarrland
Abstract
Linear structural causal models (SCMs) are used to analyze the relationships between random variables. Directed edges represent direct causal effects and bidirected edges represent hidden confounders. Generically identifying the causal parameters from observed correlations between the random variables is an open problem in causality. Gupta and Blüser (AAAI 2024, pp. 20404-204| 20440111 1) solve the case of SCMs in which the directed edges form tree by giving randomized polynomial time algorithm with running time ( We present an improved algo- rithm with running time (n log" n) and demonstrate its feasibility by providing implementation that outperforms existing state-of-it oftte-of-theaart the-art implementations.
1 Introduction
Understanding and predicting causal effects-while while distinguish- ing them from mere statistical correlations-is. a key objective in empirical sciences. For instance, uncovering the causes of dis- eases and health outcomes is essential for developing effective prevention and treatment strategies. A widely accepted method for establishing causality is the randomized controlled trial (RCT), However, RCTs require direct intervention in the system under study, which not always feasible due to ethical, financial, technical constraints. For example, to study the long-tern ing-term effects of air pollution on human health, would be unethical and impractical to expose individuals to harmful pollutants intentionally. In such cases, researchers turn to alternative methods that infer causal relationships by leveraging observational data in conjunction with prior knowledge about the system's is structure. This challenge, known the problem of identification in causal inference, is central concern in many fields, including modern MI..
W1,2
Ao.1
A1
Figure I: An IV example. is e.g. the tax rate on tobacco, the number of cigarettes smoked, and 2 whether one developed lung cancer.
A central component of the causal inference framework is how the underlying structure captures the true generative mechanism the system. This is typically formalized using structural causal models (SCMs) [Parl 2009. Bareinboim et al. 2022]. Here, we focus on the problem of identification within the class of linear SCMs, also known as linear structural equation models (SEMs) [Bollen 1989 Duncan 1975). These models represent causal relationships among observed random variables by assuming that each variable X, is linear combination other variables and an unobserved noise term ej. where the noise terms are jointly normally distributed with zero mean: X, = E, Xi, X; + The error terms are characterized by a covariance matrix Ω (wi.), which models hidden confounding terms. Linear SCMs can be represented random variables. There are two types of edges: A directed edge - j represents a linear influence Xi.j of parent node its child j. A bidirected edge i ++ j represents correlation wij between
graph with nodes (O...., 1} corresponding to the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

error terms E, and Eg. Figure shows classical example of an SCM. In this paper, we primarily consider recursive models, where the directed structure is acyelic- i..., At. = 0 for all i j. Let A = (Aa,)) denote the adjacency matrix of all directed edges, and Ω = (wi,j) the adjacency matrix corresponding to bidirected edges (i.e., covariances of the error terms). Then the covariance matrix Σ = (dx.)) of the observed variables Xo..... X is given by: Σ = (T -)- (2(T-A) A)- where is the identity matrix [Fyyeel et al. 2012]. The central challenge lies in recovering A from the observed covariance matrix Σ, under the assumption that 92 is unknown. Once A is identified, we can also recover S2 using the equation above.
Most approaches for identification in practice are based on instrumental variables (IV). in which the causal direct effect is identified as a fraction of two covariances (Bowden and Turkington [990]. For example in Figure one can calculate first w0,o/o,1 = u and then \1,2 = oo. 1A -0.2 (This follows from Wright's 's trek rule, see Section 2 The variable Xy is then called an instrument. This method is sound, that is, when identifies a parameter, then is always correct. But is not complete, that is, it might fail to identify parameter by IVs, but the parameter might be identifiable by other means.
no.1
An SCM is globally identifiable when we can always uniquely recover the parameters A given observed covariances Σ. Global identification can be decided in polynomial time [Drton et al. 2011 Thm 2). However, it is a very strong property. In Figure I
we can recover the parameter X1,2 as 20.2
do.1
If 00.1 = O, then the identification fails, the SCM is not globally identifiable. But identification fails only in the degenerate case that 00.1 = O. This leads to the concept of generic identifiability. Definition 1 (Generic identification). A parameter X is generically identifiable for almost all Σ that can be generated by the model, there is only one solution for Xp.i-
"Almost all" above means that the Σ for which identification fails form an algebraic variety or alternatively and equivalently, a set of measure 0. A weaker notion is generically k-identifiable: Here we ask whether there a parameter Ap, is generically identifiable, known algorithms also provide a symbolic expression to calculate the coefficient. For instance, in Figure I the parameter \1. is given by the rational expression 60.2 As described above, this is undefined when Ju,1 = 0, however, the equation 001 = 0 specifies an algebraic variety. Therefore, \1.2 is generically identifiable. Characterizing all linear structural causal models that are generically identifiable is a major open problem in causality, see e.g. [Foygel et al. 2012 Problem 1].
most & solutions for the parameter Ap.i for almost all Σ. If such
ro.1
1.1 Previous results
Conditional instrumental variables (cIVss) represent a natural extension of simple IVs [Bowden and Turkington 1990 Pearl 2001]. with an associated identification method that admits an efficient. polynomial- time algorithm for discovering valid cIVs (van der Zander et al. [2015).
Ao,
Several more expressive identification criteria have been introduced, each supported by polynomial-time algorithms. These include instru- mental sets (IS) [Brito and Pearl 2002a], the half-trek criterion (HTC)
W1.2
Figure 2: An example from phy- logenetics. The variables model specific trait of the species. Species O is an ancestor of I and 2 and have direct effect. The bidirected edge between I and 2 can for instance model that and 2 live in a similar en- vironment.
[Foygel et al. 20122. instrumental cutsets (ICs) [Kumor et al. (2019).
and auxiliary instrumental variables (aIVs) [Chen et al. [015]. Fur-
ther generalizations, such as the generalized half-trek criterion (gHTC) [Chen] 2016] Weihs et al. 20188] and auxiliary variables (AVS) [Chen] 2016 2016CChen et al. 2017]. J. are also tractable, assuming the in-degree of each node in the causal graph is bounded. The auxiliary cutsets (ACID) algorithm [Kumor et al. 2020 unifies these approaches by subsuming all instances identifiable by the aforementioned methods.
All methods mentioned above are sound. However, none of them is complete, that is, there are examples in which they fail identify parameters that are identifiable in principle. There are complete methods based on Gröbner bases [García-Puente et al.) 2010]. Recently, Dörfler et al. 20244) proved that generic identification can be expressed in the theory of the reals and can therefore be decided in PSPACE (and with singly exponential running time). In practice, these algorithms however can only identify SCMs with only few nodes. Van der Zander et al. [2022] report that a Gröbner basis based algorithm needed 4 months to solve 879 sample SCMs with 8 nodes each (see

---

Section 5.J). While there is no hardness result known for generic identification, we suspect that it is hard problem. Dörfler al. [2044] proved that related notion of identification, called numerical identification, is hard for the universal theory of the reals (which implies coNd-hardnesss.
When there is little hope for an efficient algorithm for general SCMs, it is natural to look restricted classes of SCMs. Van der Zander et al. (2022) introduced tree-shaped SCMs, in which the directed edges form tree with all edges pointing away from the root. There are no restrictions on the bidirected edges. Figure I shows tree-shaped SCM, there 0- + 1 - 2 is even path. Tree-shaped SCMs naturally occur when we have hierarchical structures, like in biology. Figure presents a toy example from phylogenetics, see e.g. (Thorson et al. [023) for much larger examples. | an der Zander al. [022] give a PSPACE-algorithm called treelD for tree-shaped SCMs, which at that time was an improvement, since all known polynomial time methods for generic identification perform poorly on this class of SCMs [van der Zander al., [022] Prop. 2], so one had to resort to Gröbner bases. Treell) is complete for the class of tree-shaped SCMs, which follows from the later work by Gupta and Bläser [024a]. In this work, Gupta and Bläser (2024a] give a randomized polynomial algorithm that is complete for tree-shaped SCMs. However, their running time is (rz)), which is
feasible only for small instances.
The treeID algorithm by van der Zander et al. [2022] has been implemented, it is available in the DAGitty package [Textor et al. 2016). The SEMID package (Barber al. 2023] is a state-of-the-an R- R-package for generic identification in SCMs.
1.2
Our results
As our first main contribution, we present randomized algorithm that is complete for tree-shaped SCMs with provable running time On log" n). Our key insight is improved polynomial identity testing scheme that we use to implement several of the steps in the algorithm of Gupta and Bläser (2024a] significantly faster. As our second contribution, algorithm. We compare it with two state-of-the-ar implementations for generic identification, treeID of the DAGitty package, which has been explicitly designed for tree-shaped SCM, and the established HTC criterion of the SEMID R-package, which is a general purpose criterion, but which is not complete, even not for tree-shaped SCMs.
provide C++ implementation of our
Our algorithm is randomized. It is complete in the strongest possible sense. For any tree-shaped SCM, it gives the correct answer with high probability, where the probability is taken over the internal randomness of the algorithm. For instance for SCMs with n 200 nodes, the answer is correct with probability 1 4.1 10 > 0.999995, see Appendix C for calculations. This is mathematically proven worst case guarantee. The concrete bound comes from the fact that we do all computations in built-in integers, which speeds up the implementation lot. But by running the algorithm several times, the success probability goes to 1 exponentially fast by the Chernoff bound, see e.g. Mitzznmacher and Upfal 2005).
The paper is structured as follows: the next section, we give more details on generic identification. In Section 3 we describe the algorithm by Gupta and Bläser [202aa], since we follow its general blueprint. However, we are able to speed up all of their steps considerably. Section Jxxemmpiiiis this for rank-computation, which we speed up to O(n²) compared to O log n)). The key construction is an improved identity testing algorithm, presented in Section 4.2 Although generic identification amounts to deciding whether polynomial system over the reals has one or more solutions, by using identity testing, we can reduce this to integer computations instead of manipulation of formal polynomials, which is crucial for achieving polynomial rumning time. In Section 4.3 we describe how to speed-up further parts of the algorithm by Gupta and Bläser. Due to space limitations, we only give sketch, the full explanations along with proofs can be found in Appendices B.1 B. and B.3 In Section 55] we compare the running time of our implementation with treelD and HTC/SEMID. (opendii/AJcontains proofs omitted due to space constraints. Appendix[[contain conerete estimates for the error probabilities of our implementation.
2 Generie identification
mixed graph M = (V, D) a graph with node set and two types of edges, directed and bidirected ones. We can assume w.L.ogg that the node set V {0, I....,n - 1}. D is the set of
3

---

directed edges. We denote directed edges either by (i.j) or + j. We will always assume in this work that the graph (V, D) consisting of the directed edges is acyelic, that is, the model recursive. Furthermore, the nodes are topologically sorted w.l.o.g., that is, for every directed edge i - j. we have < j. B is the set of bidirected edges, which we denote by {i,]] or ++ j. Rach node corresponds to a random variable V. With each directed edge - j. we associate an indeterminate A and with every bidirected edge u + o an indeterminate Wu,e. The random variable Vi depends linearly on its parents and additional error term e;, that is, we can write V2 = Σ3 Aj.a V + E; where the sum runs over all such that j + i is directed edge in D. The error terms are normally distributed and a bidirected edge <+ j indicates that the error terms are potentially not independent and the covariance between and éj is given by the parameter wi.j. This is a standard model, also known as linear structural equation model, see [Drton] 2018 Pearl 2009].
Let o.j denote the "observed" covariance between the random variables Vi and Vj. Wright's trek rule relates i., the parameters of the mixed graph. trek T from to j consists of two directed paths do - 1 - + is = i and ja + j1 - .... + je = in (V, D) such that either in = ju or there is bidirected edge io ++ jo B. The monomial (() of is Ji I Ai, I Aj Now Wright's 's trek rule states that oi = Σx (T), where the sum is taken over all treks from to j.
Let A = (As,)) and Ω = (ws,)) be the n x n-matrices corresponding to the directed and bidirected edges. Since V is topologically sorted, A is upper triangular. The matrix 52 is symmetric. On the diagonals of S2, we will write the variances of the error terms 6G. We denote these variances by wi,i, using double indices make compatible with the matrix notation. Let Σ (oa..) be the matrix containing the covariances between any two of the random variables Vo...., V 1- Σ models the observed covariances and A and f model the internal parameters that we want to identify. The o.d are polynomials in the parameters A and wi.j given by the matrix equation
Σ (1 A) - - AA-1 (I)
equivalently
Ω = -1- A),
(2)
see e.g. Drton 2018 (2.2)]. This is nothing but Wright's trek rule written in matrix form.
We call a bidirected edge i ++ j missing if it is not present in our mixed graph M, that is, i ++ j & B. If i <+ , is missing, then the corresponding entry in Q is O. turns out that exactly the equations in 2 that correspond to these entries are useful for identification, see e.g. [Drton] 2018 Lemma 8. (Intuitively this clear, since if the edge not missing, then Ω contains the variable wi, in this position and since the variable only appears once in 2 we can set it in such way that the equation is satisfied.)
In the case of a tree-shaped SCM with root O these equations simplify: Van der Zander et al. [2022] Lemma 5] prove that a particular parameter Au is generically identifiable (or in general k-identifiable) iff the system of equations
Ap.Ag.oppp Ap.
>as + +.g = for all i <> j & B, i,j #0,
A.p ou,s = for all 0 ++ i B
(4)
has unique solution for Xu,v (k solutions, respectively). In each equation, p denotes the unique parent of and y the unique parent of j in the tree (V, D). We will use this convention frequently in the following. If there is missing edge 0 4+ i, then Ap.s is generically identifiable and even rationally identifiable as Ap.i oo../ by (4. So missing edges to the root allow for easy identification.
3
The algorithm by Gupta and Bläser
Gupta and Bläser 2024a] give a randomized polynomial-time algorithm for generic identification in tree-shaped SCMs. This algorithm is complete, that is, every parameter Xp.i is correctly declared either generically identifiable, 2-identifiable, unidentifiable (no other cases can occur). Their paper is mainly contribution to algorithm theory, an algorithm with proven polynomial running time and correctness. The actual running time O(n)) [Gupta and Bläser 2024b]. J. As our two main contributions, we first improve the theoretical running time significantly to ( log" n) and second prove its practical feasibility by providing an implementation of our algorithm, which outperforms -fate-of-the-arr implementations.
The key observation by Gupta and Blaser 2024a is that 3 can be rewritten as
Ap.
or
A
Ap. -0.00"
(5)

---

This transforms A into Ap,i by the so-called Möbius transformation, see Krantz 1999], with the matrix ( (oie -oss and Ap, into Xg.5 by the inverse Möbius transformation given by the negative (y.. pps
of the adjoint matrix (unique) directed edge entering k. then we can express Ar, in terms of Ap, similar to ( Since we can express Xp.; in terms of Ag by (5). we can express A, in terms of Xy.j- This is again done by Möbius transformation and the matrix of this transformation is the product of the two matrices, cf.
dnn =0:: "p.u -0i.. ). If there is another missing edge, say i ++ k; and let (r, k) be the
[Gupta and Bääer 2024a Eq. (6)].
If we can find a cycle of missing bidirected edges, that is, a directed eycle in the graph (V, B), then
we get an equation that contains only one variable of the form Ap,s = dy.b Ap. which we can use to identify the corresponding parameter by solving for Xp.s. Here the matrix (a d) is the product of the matrices along the cycle of missing edges starting in the head i of the directed edge p -> i with label Ap,. The entries a, b, c, and d are polynomials in the entries of Σ, which are itself polynomials in the entries of A and ? If a 0 and
b o O, then the solution is given by the rational expression X = d/(c - 6). If + O, then there are two solutions given by the symbolic expressions
-c--b)Lv where A = (c b)2 + 4ad denotes the discriminant. In these two cases, we call the 2g cycle identifying. However, it can happen that this equation is trivial. In this case a = d = c - b = O. that is, the matrix b () is a polynomial multiple of the 2 x 2-identity matrix (Gupta and Bläser 2024a Lemma 8).
So the task is to find a cycle of missing bidirected edges that is identifying. However, there are potentially exponentially many missing cycles. Van der Zander et al. [2022] deal with this issue by simply enumerating all cycles in the graph. Gupta and Bläser [024a] design an algorithm to find a cycle that gives a nontrivial equation, if one exists, in polynomial time. Then the solution found can be transferred to the other parameters using the Möbius transformation on the missing edges.
The actual situation is more complicated, since a Möbius transformation is only bijection if the corresponding matrix has full rank two. We call such missing bidirected edge missing rank-two edge. Gupta and Bläser 22024a] Lemma 25] show that whenever there is a missing rank-one edge i ++> j then there is also a missing bidirected edge between i or j and the root 0 and therefore, we can identify or j using 4.. Algorithm[] [ summarizes the algorithm by Gupta and Bläser [2024a]. We will follow this blueprint, but we will provide significantly improved realizations of its steps. To speed up Algorithm iit is sufficient to improve the identification in the rank-two components Ci..... O. However, we will also speed up the first step of the algorithm, the rank test, since is very instructive and explains our new ideas. To identity the edges of the rank-two components, Algorithm | performs four steps:
Detecting an identifying cycle:
This finds the length t of a shortest identifying cycle or reports that none exists. (Line 7 in Algorithm I
Finding an identifying cycle:
The procedure in the first step only detects whether there an iden- tifying cycle and computes its length. If there is one, then we find one using a technique called self-reduction. (Still line 7)
Propagating the solutions: The solution we get from the parameter identified by the cycle is either
of the form >p.: = d/ (c b) (one solution, rational expression, line 9) or >p, = v[ (two solutions, line 10). These solutions are now propagated to the other nodes in the current component using the Möbius transforms on the missing edges (which have all rank two). Rational expressions stay rational expression. In the case of two solutions, the terms become fructional affine square-root terms of polynomials (FASTP), as defined by van der Zander et al. 2022]. A FASTP is an expression of the form u+eyA where u. U, f, A are rH//
2a
polynomials given by arithmetic circuits]] [T Note that the original expression for Ap.s is also a FASTP (with = 0).
'An arithmetic circuit is directed acyclic graph. The nodes with indegree (input gates) are labeled with variables or constants from a given field. The other nodes are either labeled with + (addition gate) or (multiplication gate). Nodes with outdegree 0 are output gates. An arithmetic circuit computes polynomials at the output gates in the natural way. Such arithmetic circuits occur in our setting for instance as iterated matrix products determinants with polynomials as entries. See (Shpilka and Ychudayoff 2010 for more details.
5

---

Algorithm Identification in tree-shaped SCMs
Input: A tree- shaped mixed graph M (V, B)
Output: For each Ap,r, we output whether is generically identifiable, 2-identifiable, or unidentifiable. In the first two cases, we output corresponding FASTPs.
I: Find all rank-1 edges the missing edge graph.
2: Let CI...., C. be the connected components formed by the rank-two edges.
3: for each connected component C, do
4: if C; contains a node connected to the root with missing edge then
5: Propagate the result all nodes in C, and produce corresponding rational expressions.
else
7:
Find an identifying cycle in C₁ of minimum length t. If no such cycle is found. report that all nodes of C; are unidentifiable.
8:
9:
If the cycle produces solution, then propagate it to all the nodes of C, and compute corresponding rational expressions. If the cycle produces two solutions, then propagate them to all the nodes of C. and compute corre- sponding FASTPs,
10:
11: Plug the FASTPs into the equations of C; and use identity testing to check whether all equations are
satisfied. If yes, keep the solution, otherwise, drop it.
Checking the solutions: If we only get one solution, then we are done (since we know that the system has at least one solution). If we get two solutions, then could be that only one of them is valid. This can happen if there is another identifying cycle and only one of the two solutions of the first cycle is solution of the second. (There always has to be one solution by assumption.) To check this, we simply plug the two computed solutions in all missing edge equations and check whether they satisfy of them (line 11). easy calculation shows that this reduces to the problem of checking whether FASTP is identically zero This can be done in polynomial time [van der Zander et al. 2022].
To get our faster algorithm, we improve on the running times of the first, second, and fourth item above.
4 A faster algorithm
We now present an improved realization of Algorithm We will need to compute with polynomials. They will be represented by arithmetic circuits, which can also be implicitly given, for instance by iterated matrix products. All polynomials are defined over the reals, but they all have integer coefficients and can be represented exactly.
4.1 Faster computation of the covariances and rank detection
To compute the rank of an edge (line of Algorithm D. we first need to compute the covariances Tie as polynomials in the Au and Wa,e. This can be done using (I). Gupta and Bläser (2024b) estimate this step with On log n) operations. We here show that we can perform this step even faster with Onn²) operations using Wright's 's trek rule [Wright 1934] see also [Drton 2018 Thm 4.1].
Lemma 1. Given a tree-shaped SCM M, we can construct an algebraic circuit of size (nn?) that computes all covariances L.j.
See Appendix A for the proof. Above, we produce an arithmetic circuit for the polynomials oz,j. To check whether the bidirected edge i <>> j has rank two, need check whether the polynomial vanishes (as a polynomial). Since the entries of the 2 x 2-matrix have small circuits, so has the determinant. Checking whether the determinant vanishes as a polynomial is an instance of the so-called polynomial identity testing problem (PIT), which can be solved efficiently in polynomial time by a randomized algorithm, the Seewwrtz-Ziippe algorithm, see the next section.
del
"t.e a,. op.q -
Remark 1. Since the oú. have only polynomially many monomials, we could explicitly expand the determinant as sum of monomials. However, using the Schwartz- lemma will be faster. Later, we will also encounter (small sized) circuits for polynomials with exponentially many monomials. Then, the only way perform identity tests is via the Siawartz-Ziipee lemma.

---

4.2 More efficient polynomial identity testing
Lemma (Schwartz-Zippel Lemma, see e.g. [S/pppilka and Yehudayofi 2010 Lemma 4.2). Let I be nonzero polynomial of degree S d in n variables. we draw vector E 5th uniformly at random for some finite set S, then (r( = 0] S [8]
Each di.j has degree I 2n 1, since each monomial corresponds to trek and a trek can have at most 2n 1 edges. The corresponding
2-determinants have degree I 2(2n - 1). Thus if we choose r uniformly at random from 5 = {0, ..... 4(2m - 1 we have success probability of 2 1/2. (Which maybe sounds bad a first glance, but we can boost this probability by repeating the test several times or by choosing a larger set S.) It is a major open problem in complexity theory, whether this algorithm can be derandomized, see (Shpilka and Yehudayoff 2010 Ch. 4].
Next, we present a new crucial speedup of multiple identity tests. The polynomial oi can appear in several determinants. Whenever we perform another identity test, we have to evaluate oij at a new point again. We can avoid this recomputation by not choosing new random point every time, but choosing one point for all identity tests at the (small) cost of choosing the random point from somewhat larger set.
Lemma 3 (Generalized Schwartz-Zippel), Let fi...., ft be nonzero polynomials of degree S dx 1 S X S f, and in n variables each. If we draw a vector x E ST uniformly random from some
finite set S, then Pr[[x(x) 0 for least one 1 S X S $ +ds
[S]
Proof. Follows directly from the Schwartz-Zippel lemma applied the polynomial fi ... fe-
The way to apply this generalized lemma is as follows: If we want to compute the rank of all edges,
we compute the dij using Lemma only once, evaluated a point from large enough set according to Lemma 3] Then we use these values to compute all determinants. By Lemma [3] with high probability, each value will be nonzero iff the corresponding polynomial is nonzero. This saves lot of arithmetic operations and brings its number down from O(n)) to O(n²).
Remark 2. In the generalized Schwartz- Sehwartz-Zippel lemma, we assume that all polynomials are indepen- dent of each other, in the sense that all the polynomials are given once first and we then choose the random value. In the actual algorithm, the polynomials will, of course, be evaluated sequentially. However, it turns out that if all randomized identity lests that we perform yield the correct answer (which they will do with high probability), then in our algoritimm, we always construct the same polynomials during the course of the algorithm. Only if test fails, we might construct different polynomials. But then the result is incorrect anyway. Therefore, we can assume that the required independence holds in our algorithm.
While the generalized Schwartz-Zippel lemma allows to compute the rank of all missing bidirected edges by evaluating the arithmetic circuit from Lemma 1 of size O(n²) only once, the numbers occurring during the computation can be quite large. The l 1n-rrrm [p|2 of polynomial p is the sum of the absolute values of its coefficient. Since there are at most (3) treks contributing to oi.j. |aigh S n².
By the submultiplicativity and subadditivity of the fn-norm, det
di. -0i. -op.3
11 S 2n
Proposition 1. Let p be a polynomial in variables of degree d. Let be vector of length such that the absolute value of each entry is bounded by s. Then |(xx) < Iphisd.
The proof is in Appendix A
As a consequence, the resulting numbers in the rank computation of one matrix above might be as large 2n 22(2n-1), This number has polynomially many bits! While we can perform computations with it in time polynomial in n. they do not fit into the register of Word-RAM (for the theoretical analysis) nor a built-in integer (in the actual implementation). Word-RAM is the standard model that is nowadays used in many standard books on algorithms theory, see, for instance, [Mehlhorn and Sanders 2008). Word-RAM registers can only store numbers with (log n) bits in each register, which can be accessed in unit time. If we want to store longer numbers, we have to use many registers and this will result in a higher theoretical running time, since accessing a long number will mean accessing many registers. But it would also yield a higher practical running time, since we would need to use big-integer packages. There is a solution called algebraic fingerprinting (Schönhage 1979]
7

---

Proposition 2. Let be a nonzero integer. If we choose a prime p uniformly at random from a set of N primes, then Prip divides z] I [log2 2 1/N..
Again, see Appendix [A] for the proof. As consequence, instead of computing with the full numbers, it is enough to compute modulo a random prime to preserve nonzeroness. Note that since evalua- tion modulo a prime is a ring homomorphism, all intermediate computations when evaluating the arithmetic circuit for the determinants will be performed modulo the chosen prime and therefore, all intermediate results stay small.
In the example of the determinants above, the total degree of the product of all of them is 2(2n 1)n² and the L -norm of the product is - (2m²)r² (We have to take the product of all polynomials, since we use the generalized Schwartz-Zipped Lemma.) Thus, the number 2 will be S (2n)4n s 22(2n 1)n² and we have log 2 I 4n log + 1)mm log s. Since the quantity 8 can be chosen as polynomially bounded in n by the generalized Schwartz Zippeel lemma, if we take primes of set of, say, size n", then the probability of error goes to 0 as n increases. By the prime number theorem, the primes that we need can be bounded by O(n" log n), i.e., they have Ollog n) bits. Therefore, they fit into register of a Word-RAM and we can count all arithmetic operations at unit costs.
Note that the calculations above are done to explain the overall reasoning. There will be further identity tests in the algorithm and we have to add all the degrees occurring there and multiply all the l norms. The following lemma (proven in Appendix A) shows that for the theoretical analysis of the algorithm on a Word-RAM, RAM, it is enough that the degrees are polynomially bounded and the l1 no-nrmms exponentially bounded. Appendix C contains detailed account of all identity tests performed by the actual implementation and concrete estimates of the l f--orrms and the resulting error probabilities.
Lemma 4. Assume want to perform a polynomial number of identity tests of polynomials with polynomially bounded degree and & En-norm bounded by 2poly(m), Then there is a polynomial s such that if we choose to be vector with entries from set of size s(n) and a random prime among set of s(n) primes, then all identity tests will be correct with probability tending to 1 as n goes to infinity.
4.3 Further improved steps
Figure Bouuee]shoone Jhoowss how we improve the running times of the com- ponents of Algorithm | by us- ing improved PIT. The improve- ment of the mesttests (used in lines 1, 2) have already been de- scribed in Sections 4.1
Gupta & Bläser
This work O(n²)
Location
Rank-tests Cycle-detection Self-reduction FASTP-testing
On"'log log
Sec.
4.1
(n
O log' n) (nn)
App.
B.
(nb)
App.
B.2
(n²)
O(n))
App.
B.3
Figure 3: Our improved running times
Next, we have to find an identifying cycle in line 7. This is done in two steps: First, finding one node in such a cycle and its length and then finding the cycle itself using technique called self-reduction. Let Mmiss = (V, B) denote the graph of missing bidirected edges. To each missing bidirected edge correspond two Möbius transformations as in (5). We replace each missing edge <+ j by two
directed ones and give them the weights Mr, Tp.a -ops)
01.0 -
and My, adj(M.,),. see 5 The
strongly connected components Ō formed by rank-two edges of the resulting graph are considered separately. Gupta and Bläser 2024a Lemma 8] prove that cycle of missing edges gives nontrivial equation, which allows to identify all parameters on this cycle, if the product of the matrices along this cycle, which call the weight of the cycle, is not multiple of the 2 x 2 2-identity matrix. Such
cycle is called identifying. Let W be the adjacency matrix of Ć. The entries of W are 2 x 2-matrices with polynomials as entries and testing whether a weight is a multiple of the identity matrix is an instance of PIT. The entry in position (i, i) of Wt the sum of the products of the edge weights of all closed walks of length starting in node i. If there is an identifying cycle starting in i of length t, then its weight is not a multiple of the
2-identity matrix and it is added to the entry in position (i. i). However, this contribution might be canceled by other walks. Therefore, each edge also gets a label se, which is a variable, and we give e the new weight x, Ma. In this way, each simple walk gets a unique monomial as label and the cancellations cannot happen. Now we can use PIT to find the entry and the shortest length of an identifying cycle. This gives an O(n²) algorithm, since we have to compute all powers W ...., W", To speed up the computation, we add self-loop to every node.
8

---

Then the power of the adjacency matrix contains the sums of weights of all walks of length at most t. Then we can do binary search to find the smallest in time On log" n),, see Appendix B. The use of the generalized Schwartz-Zipper lemma is essential, since we can reuse precomputed powers of W and do not recompute them with new random values.
Once know starting node in of an identifying cycle and its length t. technique called self-reduction (still line 7 of Algorithm D.. We switch to a layered version of the graph, where layers correspond to time steps. Let W 1, ..... W. be the adjacency matrices between the layers, each is a copy of W. We precompute the suffixes S = W ... W, eig for 1 S j S I, where e,, is the ioth unit vector. This can be done in time On Now start removing the edges leaving in in the first layer one after another. This means that simply set the corresponding entry in W1 to O. Let W be the resulting matrix. We check whether e! W(W ... W. is not a multiple of the 2 x 2 identity matrix. When we found the first edge leaving iu say it goes to node j. such that this is not true, then we know that ++ j is part of an identifying cycle. We now know that eς W2 Wt Cio is not multiple of the identity and we can go recursively. The precomputation time is O(n"). Every edge of the graph is considered at most once and each test of the edge can be done in time O(n). So the overall running time is ((z²) since there are at most n² edges, see Appendix B.2 for details. The use of precomputed values again works by the generalized Schwartz -Zippel lemma.
find it using
When we found an identifying cycle, we get either a rational expression or a FASTP PtoVE for one of r+Va
the parameters. This can be transferred to all other parameters in E using the Möbius transformations on the edges. In the second case, we can either have one or two solutions (since there are potentially two roots). To decide this, we have to test whether the potential two solutions satisfy all other equations of C. This is an instance of identity testing for FASTPs. Van der Zander et al. [022] give such an algorithm, which is involved, since it requires testing whether a polynomial given as a circuit is a perfect square. We show that this can be avoided and we can work with ordinary PIT. improving the running time to (n²)) Altogether, we obtain the following theorem, see Appendix B.3
Theorem 1. There is a randomized algorithm that decides generic identifiability in a tree-shaped SCM in time On log² n) (on a Word-RAM) For each parameter Xp. correctly decides whether the parameter is 1-identiiaable, 2-identifiable, or not identifiable at all. (No other cases can occur.)
Benchmarking
We provide our C++ implementation as the open-source R package fasttreeid, available on GitHub
[Brief's and Bläser 2025b) and CRAN [R Core Team 2025 Briefs and Bläser [222a]]. We tested it against the tree algorithm, which part of the DAGitly package [Textor et al. 2016]. We used the current version 3.1. The treelD- alggorihm is specifically made for tree-shaped SCMs and is based on [van der Zander et al., 2022]. It is the only implementation we are aware of that specifically designed for tree-shaped SCMs. Second we also benchmarked against the half-trek criterion (HTC) [Foygel et al. 2012). which is part of the state-of-the-art R- R-package SEMID [Barber et al. 2023), we used the current version 0.4.1. Note that HTC is designed for arbitrary SCMs. On the other hand, it is not complete, that is, it can fail to identify parameters that are in principle identifiable. We chose HTC from SEMID, since it is the fastest identification routine of the package. All experiments were carried out on a Debian Linux server equipped with an AMD EPYC 7702 64-core processor running at 3.35GHz and an overall memory of 2TB.
5.1
879 graphs benchmark
Van der Zander et al. 2022 provide 879 test cases with 8 nodes each. The directed edges form + 7. The supplementary material of [van der Zander et al. 2022 contains the full classification of all edges, therefore, we used it to check the correctness of our implementation. The result is given in the table in Figure
line 0 - -1--2122 -3 44
Our implementation is faster by factor of 5000. When running all 879 test cases within C++ directly, our program only takes 0.1 seconds, so there seems to be some overhead
Program Our Program 879
Cases solved
Total execution time [s]
7.955
treell) Figure 4: Running times on the 879 graphs benchmark
879
40435.533

---

treelD
250
SEMID
SEMID
80
O(i)) detection ideniitying eyeles
program
log"(" (ni) detection of ideniifying sycles
200
Execation time [s]
60
Executio time
160
100
20
300
20
40
00
80
100
120
140 160
180
200
0
20
40
60
80
100
120
1.00
160
180
200
Number of modies n
Number of modes
Figure 5: Random tree structure, one large cycle of missing bidirected edges
Figure 6: Tree is a path, random set of 80% of the possible bidirected edges (all parameters identifiable by missing bidirected edges to 0)
from IO when invoking the program using shell script. We suspect that the fact that algorithm is much faster than treell) does not only come from the fact that we have a faster way to find identifying cycles: Since there are only few potential missing cycles in the 879 graphs, because the graphs are small, we suspect that it also stems from the fact that the identity tests might be implemented inefficiently in treeID (Appendix B.4..
5.2
One large missing cycle
The overall running time of our algorithm does not depend too much on the actual graph structure, since mainly use linear algebra operations. The minimum length of identifying cycle has some influence on the binary search process, while the edge density of the missing edge graph affects the self reduction step.
The first set of test cases was obtained by creating a random directed tree (each node takes as its parent smaller node uniformly random, this creates trees of logarithmic depth with high probability). The only missing bidirected edges form a cycle 1 + 2 <> ... < (n 1) <> 1. All three programs single core with time limit of minutes per test case. treelD was memory and did not terminate within the time limit for n 2 13. HTC/SEMID did not solve any the test cases, but terminated all of them. One formally prove that HTC cannot identify any nodes there are no missing edges to the root, see Appendix F Our program solved all test cases. Figure shows the execution times of the respective programs. The black line shows the performance of program with cycle detection in O(n*), the green line shows the performance with cycle detection in (n (n)).
were
with 16 GiB of
Random graphs with different densities
Components that connected 0 by missing edges are easy for our program and for treelD. For our program, the execution time on such test cases is very small and dominated by generating the treks to compute the oi.j (O(n²)). Interestingly, treelD does not perform this is due to the implementation graph with a given density, the probability that there are missing edges to 0 is high, so we consider random graphs with no missing edges to O separately (see Appendix D) In Figure [6] the directed edges form a path 0 + 1-.... + (n 1) and the bidirected edges are a random subset containing 80% of all possible bidirected edges. In all test cases, all identifiable nodes are (1- (1-)identifiable due to missing bidirected edges to O, and moreover, only a few nodes are identifiable at all. For our program, much shorter execution time can be observed compared to Figure 5 HTC solved all test cases, but took about three times as long as in Figure 5 treelD exceeds the memory limit 256 GiB for n 30 and n 2 33 (but works for n 31 and n = 32). We have idea why treelD takes so much longer for n = 25 than for n = 26, but this behavior reproducible. Further benchmarks can be found in Appendix D In all of them, implementation outperforms both treeID and HTC.
well, suspect that
the identity tests, see Appendix B.4 When creating a random
10

---

Acknowledgments
The authors thank Batuhan Koyuncu and Isabel Valera for helpful discussions.
References
Rina Foygel Barber, Mathias Drton, Luca Weihs, and Nils Sturma. SEMID: Identifiability of Linear Structural Equation Models, 2023. package version 0.4.1.
R
Elias Bareinboim, Juan D. Correa, Duligur Ibeling. and Thomas Icard. On Pearl's 's Hierarchy and the Foundations of Causal Inference, pages 507-556. Association for Computing Machinery, New York, NY, USA, 2022.
Kenneth Bollen. Structural equations with latent variables. Wiley, 1989.
Roger J. Bowden and Darrell A. TTurkington. Instrumental Variables. Cambridge University Press, 1990.
Yasmine Briefs and Markus Bläser. R package fasttreeid. The Comprehensive R Archive Network (CRAN), 2025a. URL httppp///ccaa.rrppppppeeooorrrrr
Yasmine Briefs and Markus Bläser. C++ and R implementation FastTreelDD. GitHub, 2025b. URL htttps://githuu: wwtp.//aaa....eeeeeeeee/aaaeaaae wtw.eeeeess/aaattteeeeeaaa
Carlos Brito. Instrumental sets. In Rina Dechter, Hector Geffner, and Joseph Halpern, editors, Heuristics, Probability and Causality. A Tribute to Judea Pearl, chapter 17, pages 295-308. College Publications, 2010.
Carlos Brito and Judea Pearl. Generalized instrumental variables. In Proc. Conference on Uncertainty in Artificial Intelligence (UAI), pages 85-93, 2002a.
Carlos Brito and Judea Pearl. A graphical criterion for the identification of causal effects in linear models. In Proc. AAAI Conference on Artificial Intelligence (AAAT), pages 533-538, 2002b.
Bryant Chen. Identification and overidentification of linear structural equation models. Proc. International Conference on Neural Information Processing Systems (NeurIPS), pages 1587-1595. 2016.
Bryant Chen, Judea Pearl, and Elias Bareinboim. Incorporating knowledge into structural equation models using auxiliary variables. Proc. Int. Joint Conference on Artificial Intelligence (ICCAI), pages 3577-3583, 2015.
Bryant Chen, Daniel Kumor, and Elias Bareinboim. Identification and model testing in linear structural equation models using auxiliary variables. In Proc. International Conference on Machine Learning (ICML), pages 757-766. PMLR, 2017.
Julian Dörfler, Benito van der Zander, Markus Bläser, and Maciej Liskiewicz. On the complex- ity of identification in linear structural causal models. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, ed- Neu-
itors, Advances in Neural Information Processing Systems 38: Annual Conference ral Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, Decem- ber 10 15, 2024, 2024. URL httpp:///pp: nips cc hwpprppppr...e feapprrffles___ files/ 2atee//pppe/222/aasll b588896679326455666 1555599669922440066666666002200 cow.rreoto--ttttttttctoooooooeee
html
Mathias Drton. Algebraic problems in structural equation modeling. In The 50th anniversary of Gröbner bases, pages 35-86. Mathematical Society of Japan, 2018.
Mathias Drton, Rina Foygel, and Seth Sullivant. Global identifiability of linear structural equation models. The Annals of Statistics, 39(2)8865-886 2011.
Otis Dudley Duncan. Introduction to structural equation models. Academic Press, 1975.

---

Rina Foygel, Jan Draisma. and Mathias Drton. tref-trek criterion for generic identifiability of linear structural equation models. The Annals of Statistics, 4063):1682-1713, 2012.
Luis D. Guente,Puente, Sarah Spielvogel, and Seth Sullivant. Identifying Causal Effects with Computer Algebra. In Proc. Conferencee on Uncertainty Artificial Intelligence (UAI), pages 193-200, 2010.
Torbjörn Granlund and the GMP development team. GNU MP: The GNU multiple precision arithmetic library. Release 6.3.0, 2023. htR.sttss::////. httpss:///mpi.....m org/
Aaryan Gupta and Markus Bläser. Identification for tree-shaped structural causal models in polynomial time. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan, editors, Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium Ed- ucational Advances Artificial Intelligence, EAAI 2014, February 20-27, 2024, Vancouver, Canada, pages 20404-20411. AAAI Press, 2024a. doi: 0..1609/AAAAVV3111. 33003. URL
https://doi org/ 10. 1609/ 1109//669.a.... aaai. www.v8881..0000
Aaryan Gupta and Markus Bläser. Identification for tree-d structural causal models in polyno- mial time, 2024b. URL /tttps://axxi...t..t// org/ hbsg:/as/22330 2311 14058
S. G. Krantz. Handbook of Complex Variables, chapter Linear Fractional Transformations. Birkhäuser, 1999.
Daniel Kumor, Bryant Chen, and Elias Bareinboim. Efficient identification in linear structural causal models with instrumental cutsets. In Proc. Advances in Neural Information Processing Systems (NeurlPS), pages 12477-12486, 2019.
Daniel Kumor, Carlos Cinelli, and Elias Bareinboim. Efficient identification in linear structural causal models with auxiliary cutsets. In Proc. Int. Conference on Machine Learning (ICML), pages 5501-5510, 2020.
Kurt Mehlhorn and Peter Sanders. Algorithms and Data Structures: The Basic Toolbox. Monographs in Theoretical Computer Science. Springer, Berlin, Heidelberg, 2008. ISBN 978-3-540-77977-3.
doi: 111007/978-3-540-779777
Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge, 2005. ISBN 0521835402
9780521835404.
OpenSSL Project. Openssl: The open source toolkit for SSL/TLS, https://www.opesset org Jan 2024. Version 3.0.13.
Judea Pearl. Parameter identification: A new perspective. Technical Report R-276, UCLA, 2001.
Judea Pearl. Causality. Cambridge University Press, 2009.
Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2025. URL httpp:://wwtt http::///www...pjjjeeeeeo
R-projecct orgg/
Arnold Schönhage. On the power of random access machines. In Hermann A. Maurer, editor, Automata, Languages and Programming, 6th Colloquium, Graz, Austria, July 16-20, 1979, Pro- ceedings. volume 71 Lecture Notes Computer Science, pages 520-529. Springer, 1979. doi: 10.100773-540--95500- LL.2.
Amir Shpilka and Amir Yehudayoff. Arithmetic cireuits: A survey recent results and open questions. Foundations and Trends@ in Theoretical Computer Science. 5(3-))207-3),3388 2010. IS$N 1551- 305X. doi: 10. 1,561/040000033,
doi http:://db..d....ooo......111///
Johannes Textor, Benito van der Zander, Mark S Gilthorpe, Maciej Liškiewicz, and George TH Ellison. Robust causal inference using directed acyclie graphs: the package 'dagitty.. International Journal of Epidemiology, 1887))1887-189) 2016. doi: 10.1093/jjedyyw341.
12

---

James T. Thorson, Aurore A. Maureaud, Romain Frelat, Bastien Mérigot, Jennifer S. Bigman, Sarah T. Friedman, Maria Lourdes D. Palomares, Malin L. Pinsky, Samantha Price, and Peter Wainwright. Identifying direct and indirect associations among traits by merging phylogenetic comparative methods and structural equation models. Methods Ecology and Evolution, 14(5): 1259-1275, 2023. doi: http:///wo.orry/...1111/24-- 14076. http::tts:///bssoee 210.
onlinelibrary.. wwlphrrrrrrrwrrrr......e.eeeeeee
Benito van der Zander and Maciej Liskiewiez. On searching for generalized instrumental variables. In Proc. International Conference Artificial Intelligence and Statistics (AISTATS), pages 1214- 1222, 2016.
Benito van der Zander, Johannes Textor, and Maciej Liskiewicz. Efficiently finding conditional instruments for causal inference. In Proc. Int. Joint Conference Artificial Intelligence (IJCAI), pages 3243-3249, 2015.
Benito van der Zander, Marcel Wienöbst, Markus Bläser, and Maciej Liskiewicz. Identification in tree-shaped linear structural causal models. In Gustau Camps-Vale Francisco R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AIS- TATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 6770-6792. PMLR, 2022. URL htt.h:ttsss///t http::///roeeeee ptttpp:://proceednngg mlr wwwppsessssvee. v151/ van van-der- 2aa-derrzaadee22a... html
Luca Weihs, Bill Robinson, Emilie Dufresne, Jennifer Kenkel, Kaie Kubjas Reginald McGee II, McGee II Reginald, Nhan Nguyen, Elina Robeva, and Mathias Drton. Determinantal generaliza- tions of instrumental variables. Journal of Causal Inference, 6(1), 2018.
Sewall Wright. The method of path coefficients. The Annals of Mathematical Statistics, 5())1611211, 1934.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claimed correctness and the theoretical runtime of the algorithm is proven in Section and Appendix A] The described experimental evaluation is conducted in
Section 5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: It stated that the algorithm only applies to tree-shaped SCMs. is mentioned that the algorithm is randomized and mathematically proven bounds on the error probability are given in Appendix
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical claims are stated with precise assumptions and mathematically sound proofs are given in Appendix AA] The main text describes the main ideas behind the proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The code, all test cases, detailed explanation on how to reproduce the results and a Dockerfile describing an environment in which all programs can be run are provided in the supplementary material.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
15

---

(d)
reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is made available in the supplementary material and will be made public after reviewing. We also provide Docker environment in which all programs can be executed. The supplementary material provides detailed descriptions on how to run the Docker container and how to execute program and the two other benchmarked programs in the file README.md. In addition, we provide all test cases and scripts to run the programs the test cases.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (nttps://nips.co
Seaiidde//oodSSubmisse
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips wwtp:/cccppcpcuueeueeeeeeec http:p/ic/c.uuuieeoeeeeeeeaaeaia hwtp///ooeeeessiooooooe ssi.iiissoopyiiyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: See Section 5 and Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
16

---

The execution times of all tested programs are very consistent over multiple runs, so for time and simplicity reasons, we only ran each program once per test case. For all executed test cases, we also checked correctness, and in all of them, our output was correct.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eτror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The program code is included in the supplementary material. We do not see any other ethical issues.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
17

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There are no direct societal impacts of our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymeett of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There such data models in work.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All code packages used are cited in the work. The version used is mentioned in the work. (Section(5)
Guidelines:
18

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thcode. com/ com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Detailed code documentation is provided in the supplementary material. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The work does not include crowdsourcing experiments and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
19

---

Justification:
The work does not include crowdsourcing experiments and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Our program does not involve LLMs as a component.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
cwaeeiippscccCooffeeee / LLMM
20

---

A Omitted proofs
Given tree-shaped SCM M, we can construct an algebraic circuit of size (n that computes all covariances dt.j.
Lemma 1,
Proof. We have 0n.0 = w0.0- For 0:o0 with > O, we have 05.0 = -p.0 =...0 +-i.n where p is the parent if This follows from (4) where in general the left-hand side is wi,0- o. For i.j both greater than 0, let p and be the parents of i and j. respectively. We have Tij p + oi. - Ap.a + wi.j The first term contains all treks that end in p and j and extends them by the directed edge p - The second term does the same for all treks that end in i and 9. respectively. We are counting all treks twice in this way that ended in p and q and were extended by the directed edges p + i and q + j- They are subtracted once through the third term. The fourth term is the new trek which corresponds to a bidirected edge between i and j. Alternatively, we can also use B (In all these computations, if bidirected edge is missing, the corresponding w-variable is replaced by 0). The number of arithmetic operations per Ti,j constant, therefore, the overall size of the circuit (nn)).
Proposition Let p be a polynomial in n variables of degree d. Let a be a vector of length n such that the absolute value of each entry is bounded by s. Then [p(x)] S lphi...
Proof. Each monomial of has total degree d. If we evaluate the monomial at a point with coordinates bounded by s, the maximum value we get is sd. The monomials are multiplied with the coefficients and then added up. therefore, we get an upper bound by multiplying s" with the nnrrr of p. O
Proposition 2. Let be a nonzero integer. If we choose a prime p uniformly at random from a set of N primes, then PrIp divides z) S [loga 2 1/N.
Proof. The product of any N pairwise distinct prime numbers is lower bounded by 2 On the other hand, z can have at most log prime divisors. Therefore at most log of the N primes can divide and we get the statement of the lemma.
Lemma 4. Assume we want to perform a polynomial number of identity tests of polynomials with polynomially bounded degree and l fn-nrrm bounded by 2poly(n), Then there is a polynomial s such that if we choose x to be a vector with entries from set of size s(n) and a random prime among a set of s(n) primes, then all identity tests will be correct with probability tending to 1 as n goes to infinity.
Proof. Let p(n) be the number of identity test and d(nz) be an upper bound for the degrees and assume that the f--norm of each polynomial is bounded by 24(m), By the generalized Schwartz-Zippel lemma, if we choose the entries of x from a of size r)p(n)d(n). then the error probability of selecting bad a will tend to O. The -n-ormm of the product polynomial in the generalized Schwartz-Zippel lemma will be bounded by 20(m)p(n). Therefore, by Proposition the size of the number after plugging in a will be < 29(m)p(m)) (mp(n)d(m)))dd)) set of (g(n))(()) + d(n)) log( (pp(1 (n)(()) many primes, the error probability when computing modulo this prime will go to 0, too. The overall error will go to zero, too, by the union bound.
By Proposition if we choose a prime at random from a
B Further details on the algorithm
B.1 Faster detecting of identifying cycles
The main difficulty in Algorithm Dis is line 7, finding an identifying cycle of missing edges, that is, a cycle that gives nontrivial equation for identifying a parameter. Let Manis (V, B) denote the graph of missing bidirected edges. Muiis denotes the directed version of Mmiss in which each bidirected edge i ++ is replaced by two directed edges (i.j) and (j.i). Furthermore, (i.j) has dt.. -ass
2 x 2-matrix M.j
as weight and (j, has the matrix Mj,,, which is - adj Mc.), see (5). The edges (i,j) )) in the directed missing edge graph are classified into rank-1 and rank-2 edges, depending on whether the rank of M., if 1 or 2, respectively. By definition, the rank of M the same as Mi,, so we can also classify the edges of Muiss Let Miniss and Muiss, denote the subgraph of Miss and M Mmiss respectively, that consists only of the rank 2 edges. Any weakly
dp.e -
21

---

connected component of Muiss,2 is always strongly connected. In the following C denotes a strongly
connected component of Mmiss i.e. the directed version of a connected component C₁ considered in the for loop in line 3 of Algorithm
Cupta and Bläser [024a] give an efficient randomized algorithm to test whether there is an identifying cycle in the component C. This test takes time O(n*) as reported in [Gupta and Bläser 2024b].
We here improve this to (n log" n)). Gupta and Bläser 2022aa Lemma 8] prove that cycle is identifying, if the product of its edge weights Me.- ... Me. is not a multiple of the identity matrix, where e1,...,6e Et the edges of the cycle. Note that this again instance of polynomial identity testing, since we need to check whether the entries in position (2, 1) and (1,2) are zero and whether the difference of the entries positions (1,1) and (2,2) are zero. Let W denote the weighted adjacency matrix of C. that is, the entry in position (} is the 2 x 2-matrix Mi.j- It is well known, see e-g. [Gupta and Bläser 2024a| Fact 15], that the entry in position (i,j) of the /th power W is the sum of all weights of paths of length from to j. Here, the weight a path is the product of the weights of its edges. However, it can happen that the contribution of several walks cancel each other, therefore, although there might be identifying cycles, which are walks from i i, the entry in position (i, i) is a multiple of the identity matrix.
The basic idea to repair this is that each directed edge (u, v) in Ò gets the weight Fu,, Mu,, instead of its original matrix weight Ma Here Fu is an additional indeterminate. Let W be the new modified adjacency matrix. If w is walk from u to e consisting of edges Ei,.... Ct. then the weight of this walk is Fei ... T., .......,... ..,, We call f(w) = Zea Le, the label of and M (w) Me.- Me, its matrix.
Lemma 5. The entry of Wt in position (i.j) equals
Σ
((w) ((w)
walks from to j lengihh
Proof. Follows from Gupta and Bläser 2024a Fact 15] applied to W. We give proof for the sake of completeness, though. The proof is by induction on t. The case t= 1 is obvious. For L >>> 1, we can write V = W W. Each walk from i to j of length t is walk from i to some node k of length & 1 extended by the edge (k. Thus
W
Σ
l(w') ((w')((w') Mk. =
Σ
(w)M(w)
walks wo from é to & of length t
walks w from a to j of length
Observation 1. If is a simple walk, then the label Ne, ... Tey is unique, since two simple walks have to differ in at least one edge.
Remark 3. If we have a simple closed walk w of length I, then w can have every of its nodes as a starting point, which is then also its end point. This will not change the label. However, depending on the chosen starting node i, w will contribute to W therefore, these labels will not mix up.
Remark 4. While the label will not change, the matrix Mww) can change depending on its starting point i. Although the matrix M (w) itself may change, it will not change whether w is identifying or not. This is due to the fact that whenever Me,... ..g,.,,.,,,, = a 1, i.e., the product is a multiple of the identity matrix, then the product of any cyclic permutation is 1, too. (Multiply the equation from the left with M,,1 and with Me, from the right and repeat if needed.)
However, two arbitrary walks can consist of the same set of edges and can still be different. To avoid this, Gupta and Bläser [2024a] Section 6] use layered version of the graph. This increases the size of the underlying graph by a factor of n, resulting in the running time of O(n²). However, we observe that we only need that simple walks get different weight by the following lemma.
Lemma 6 (Gupta and Bläser 2024a Lemma 21). A shortest identifying closed walk is always simple. Corollary 1. Let 1 be minimal such that there is an identifying closed walk. Then there is un such that the matrix power Wi in position (i, i) is not multiple of the identity matrix.
Proof Since L is minimal, every identifying closed walk is simple. Let wo be such an identifying walk. Then M (wo) is not multiple of the identity matrix. Let i be a node on w. The entry of /
22

---

in position (i, 2) is the sum of all f(w)- M (w) over all closed walks from i to of length t. Since the label ((wo) of wy is unique among all these walks, the term (M will not be canceled in a. Since M (wo) is not multiple of the identity matrix, a is not multiple of the identity matrix. I7
We could now compute the powers W 1 < S n. and do identity testing to search for the smallest t such that there is an identifying walk of length f. However these are matrix multiplications and it takes time O(n*) in total. This is not faster than [Gupta and Bläser 2024a].
We improve this as follows. W corresponds to walks of length exactly t. We would like to have a matrix that corresponds to all walks of length at most t. We form a new graph C. with matrix W., which we obtain from C and W, respectively, by adding a self loop to each node with label 1 and matrix ( 9. Each walk w of length in C gives rise to multiple walks in C. of any length s' 2 8, by inserting self loops at any place. Note that by construction, this neither changes the label nor the matrix of the walk.
Lemma 7. The entry of W in position (i.j) equals
(2) E(10) M(w).
Σ
walks w. from of length a S in C
Proof. In total there are (t) walks in C. of length s' that correspond to w of length s, since there are (t) ways to insert the self loops into w. Conversely, every walk w' in C. of length s' corresponds to one walk in C of some length S s' after removing all self loops from w'.
Corollary 2. If there is an identifying cycle, then there is an i such that the matrix power W in position (i, is not multiple of the identity matrix.
Theorem 2. We can find (minimal) t and a node i such that there is an identifying cycle of length t that contains in time On log" n).
Proof. We compute one matrix power W which can be done by repeated squaring with arithmetic circuit of size Or²² n). We now need to perform identity tests for the entries in positions (i, 1, of W As explained in Section 4.2, we can do them all at once by plugging in
0 S i S large enough value. Furthermore, all computations will be done modulo the chosen prime, therefore, each single arithmetic operation in the evaluation of the circuit takes constant time. If we want to find the smallest length of any identifying cycle, we can now do so by binary search, which gives the additional log factor.
For small n, the O(n)) algorithm will outperform the O(n" log" n) one. Our experiments show that the break-even point is around n 50. We have implemented both routines, see Figure
B.2 Faster self reduction
Once we have found a node is on an identifying cycle and its length t, we have to find this cycle. (This is still done in line 7 of Algorithm D.. This is done via technique called self-reduction. In the algorithm by Gupta and Bläser (2024b). this takes time O(n'c) O(n"), where e is the number of missing edges. We here give a significantly improved procedure with running time O(n²).
Let / be the length of a shortest identifying cycle and assume that the node in is contained in a shortest identifying cycle. and in can be found using Theorem 2 To find the identifying cycle, we will use self-reducibilitt. It will be beneficial to switch to the layered graph as in (Gupta and Bläser [024a Section 6]: Every node is replaced by f copies vo: -.. Uy- All nodes with the same index form a layer. Edges only go from one layer to the next, that is, if there is an edge (v, u) in č. we will have edges (v,, M++1) for 0- < 5 < t in the layered graph. We can think of the layers as "time steps". the edge from layer 7 to T + 1 the edge taken the (r + 1)th step of the walk. Let W,,..., W, be the weighted adjacency matrix corresponding to the layers of the graph, an edge (Vr, 1y+1) has the weight u My... We know that ex W, ... W eip is not multiple of the identity matrix, where eig is the i0th unit vector, since there is identifying cycle containing ig. Note that since the entries
23

---

Algorithm 2 Faster self-reduction
Input: A node is known to lie on shortest identifying cycle and its length t Output: An identifying cycle of length containing
I: Compute the suffixes S) W, Wt Cio for < S.
2: Set L 0.
3: Set = (bl). Product the matrices the edges found far.
4: Remove the edges leaving io one after another (using Lemma until the identity test does not report that
there is an identifying cycle.
5: Add the edge (fo.j) found to I.
6: Let M M Min.-
7: Repeat with the next layer.
of the matrices are 2 x 2- 2-matrices, the entries of 6 are also 2 2-matrices, the identity matrix in position in and the zero matrix in all other positions.
Algorithm 2 describes our improved procedure: We precompute the suffixes S, = W, W ei for S f, where all variables are replaced with our random values and all computation are reduced with our chosen prime. This can be done in time O(n²t), since these are only matrix-vector products. Now start removing the edges leaving ig in the first layer one after another. This means that we simply set the corresponding entry in W1 to O. Let W be the resulting matrix. We check whether ex, W(W2 ... W₁- Eig is not a multiple of the identity matrix. S2 = W2- W, 6ig is already precomputed. eT W can be computed from Gig W1 in time ((1) by the lemma below. Thus we can compute e% W2 ... We Ci, in time (nn) as e W -2-
Lemma 8. Let be vector and A be matrix. Let A' be the matrix obtained from A by setting the entry in position (i.j) to 0. From v = uT A, we can compute v = A''A' in time (()).
Proof. We can write v = U3 U and vi. = Ug for j.
When we found the first edge leaving io. say it goes to node j. then we know that in ++ j is part of a missing cycle. Now we know that Me W2 We- e% not multiple of the identity and we can go on recursively.
The precomputation time is Onn)). Every edge of the graph Ö is considered at most once and each test of the edge can be done in time (n)). So the overall running time is (nz)) since there are at most n² edges. Thus we have proved the following theorem.
Theorem 3. Giyen a node in and an integer such that a in lies on an identifying cycle of length t, then Algorithm 2 returns the edges of an identifying cycle of length I containing in in time O(n²)
B.3 Simplified identity testing of FASTPs
Once we have found an identifying cycle, we get solution for some Ap.i. given as rational expression or a FASTP [uupta and Bläser 2024a Lemma 8). We propagate this solution to other parameters in the connected component C' using the Möbius transformation along the edges (lines 9 and 10 of Algorithm D. This takes time (n). there are two solutions for the parameter, we have to check whether both of them satisfy all equations (line 11). Gupta and Bläser (024b) report time complexity O(n² e) = O(r²) for this step. We here improve this running time to O(n²). This improvement comes first from the fact that we use our improved identity testing scheme that only chooses one random point for all tests and second that we can avoid a square root computation in the identity tests for FASTPs.
Appendix B.4 explains the details how perform identity testing for FASTPs in general. We can avoid the square root computation by the following observation. Since the observed covariances are generated by the underlying model, we know that there always at least one solution. For a missing edge, we are given two candidate solutions as FASTPs, which have the same square root term /s by [Gupta and Bläser 2024a Remark 5J. When we plug these into the missing edge equation 3 we get again a FASTP with square root term Vs. We now need to check whether a term of the form
p + Vaq zero for both possibilities of the sign. If s = O, then there only one square root. So we can assume that is not identically zero. Since we know that there is one solution, p + /sq 0 can
24

---

only have two solutions if both and q are identically zero. Otherwise, there is only one solution. So in total, we just have (n²²) many tests, each one requiring constant time.
Lemma 9. Testing whether component Ö has or two solutions (line 10 and 11 of Algorithml ! can be done in time O
Proof of Theorem 7 The correctness of our algorithm follows from the correctness, proof by Gupta and Bläser [2024a], since we follow the blueprint of the algorithm and present faster implementations of each step. The running time of our algorithm follows from Table
B.4 Details on identity testing of FASTPs
We give some further details how general testing of FASTPs works for the sake of completeness. Consider FASTP p+ It is sufficient perform the identity test of the denominator and numerator rtivs"
separately, since we first need to check whether the denominator nonzero and the numerator is zero. Therefore consider a term of the form + gvs. If s is not square, then p + qv = 0 iff 0 and 9 = 0. it perfect square, that is. $ 2²2 for some polynomial u, then p + qv5
iff p + qu 0 (depending on which of the two possible roots +u we have chosen for v*). The identity test for FASTPs proposed by vaa der Zander et al.] [2022] therefore decides whether is perfect square. If is not perfect square, then it checks whether p 0 and 0. If s is perfect square, then it computes a root u (as a circuit) and checks whether p + qu = 0.
Note that the TreeID algorithm as currently implemented in the DAGitty package also avoided this square root computation. Van der Zander et [2022 Section B] write: "Rather than using PIT on FASTPs, we have fully expanded the equations in the CAS." For small n this does not make too much of difference, however, even for moderate n, the expanded polynomials become really huge. This might explain why the TreeID implementation does not perform too well once the graph size is about 20, even when the given graph has only few missing cycles, which should be good situation for TreelD, since it enumerates all potential missing cycles.
C Estimates
We give enror estimates for the values 200, when the observed rumning time is about 40s in the worst case (see Figure 5) as well as n = 1000. In the latter case, the running time is about 9500s, i.c. more than two hours.
To lower the error probability, one can run the algorithm several times with new random numbers. The error bound will drop exponentially in the number of runs. Alternatively, one can enlarge the size of the random primes used. Again, with each new bit, the error rate decreases exponentially. However, at the moment, this requires using big integer package, since we are at the limit of built-in integers.
Using built-in integer computations instead of symbolic polynomial manipulations is the key to the speed of our algorithm.
C.1 Estimation of the number of identity tests and the corresponding degrees
We assume that the number of bidirected edges and the number of missing bidirected edges is n² for simplicity, since this is the worst-case for all estimates. All estimates are upper bounds.
Rank computation:
For each missing edge we perform checks of degree 2n to check if the rank is 0 and one check of degree 2(2n - 1) 4n - 2 to check if the rank is 1. This means that the rank computation contributes 5n identity tests, 4n² of degree 2n 1 and n² of
degree 4n - 2.
Cycle detection:
The worst case for the number and degree of the checks is one component of size
this case, for each cycle length and node, we have checks of degree n1(2- + = 2n (product of matrices of degree 2n 1 and indeterminates) each to check whether the corresponding entry is multiple of the identity matrix, so cycle detection amounts to 2n? checks of degree 2n each.
25

---

and there are at most 2nd such Self reducibility: Just like cycle detection, self reducibility amounts to 2n checks of degree 2n² each.
Checking the solutions:
For each node, we check whether 0 [Gupta and Bläser 2024a Lemma 8, case 2]. In the component, FASTPs are propagated to all nodes via shortest paths. Each propagation adds 2n 1 (degree of the oz..) to the degree of p. 9. f in the FASTP, so their total degree is 2n² + n22n 1) 4n²
This means identity tests of degree 4n² - 71 each. Once per component, we check whether the discriminant is 0 [Gupta and Bläser 2024a, Lemma 8, case 1J. This means at most identity tests of degree 4n.. Once per missing edge, we check whether both options satisfy the corresponding equation. This requires two identity tests (getA, getB). A is of degree 2( 244 -n) + 4n 2n 12n - +42
and B is of degree 2(4n" - n) + 2n 1 = Sn - 1. This means n² identity tests of degree 12n² 1 and n² identity tests of degree 8n? 1.
Summing up these values, we get an upper bound 5n + 2n + 2n + + 11n² +2m identity tests. The maximal degree is 12n² 1 and the sum of all degrees is
4n² (2n 1) + n² (4n 2) + 2n² 2n² + 2n² 2n²
+ n (4n² - n) n n (12m² 1) + n² (8n² - 1) +
= Sn - 4n² +m 2n² + 4n² + 4n
+ 4n -n n -2² 4n 12n - n² 8n n²²
= 28n + 20n 9n2
For 1000, for example, the value of this polynomial is 3. 1013, For 200, is S 5 1010.
C.2
Estimation of the & norm
Rank computation: Each trek contributes one monomial with coefficient 1 one of the otj- For
fixed otj, there are most (n 1)/2 n n² treks, so the l norm of the os is at most n2?
During rank computation, we check whether the æıj are nonzero and whether the deter- minants of the x 2 matrices corresponding to the missing bidirected edges are nonzero. Checking whether the dij are nonzero amounts to a total & norm of at most (n²)"². Checking whether the determinants are nonzero amounts to a total & norm of at most (2n2)=².
Detection and self-reduction: The entries of W have an l norm of at most 2nn 2n²"(n2))
(2n²)" < (2n)3n (multiplying by the indeterminates does not change the e, norm). During cycle detection, there are up n² checks whether 0 (nodes eycle length), which contributes at most ((2n)3x)n* to the total & norm. Additionally, there are up to n² checks whether b * c, which contributes at most (2(2n)3n))) 3m)n² to the total & norm. During self reducibility, there the same kind of checks.
Checking the solutions:
Once per component, we check whether the discriminant is 0. The total f (6(2n) )mn)2 The l1 norm of p, q, r, of the first FASTP (the node for which the cycle was found) is 2(2n)3n In each propagation, the & norm of p. r, t is multiplied by at most 2nd, which amounts to a total E norm of at most 2(2m) 3n (2n)2x = 2(2n)on for the p. p,g.rt in the FASTPs. For each node, we check whether a = The total & norm of this is at most )2m)2 (6(2r) 3mm2)3m2244 ((2) 2un + 4(2n) 10m (s 12 check whether A and B are nonzero. The E, norm of each of these A/B is at most 2(2m)5=2(2n)) (6(2n) 3mnnmn = 4(2m) 10m (6(2n)3n) checks, so (4(2n) 10n (6(2n) ( 2 jan" in total.
norm of this most (2(2n) 3m + 4(22))nn22
(2(2))))))() 0). For each edge, we
p2 12-77
Hence, the product of all polynomials for which we do identity testing has & norm at most
(n²)n² (2 ((2n) zmyn² (2(2n) 3n)2n² (6(2n) 3m 22n 2(2m) 5m ((6(2n) (mn2nn))annaam ((nn) 10p + 4(2n) 10n)- (4(2n) 10n (6(2n) 3m)) 2n 2)22n z 212n +33m" +19. gd(n²+n) -n (12nn + 22. + +22n+15).
26

---

The logarithm is bounded by
(12n² + 33n + 22n2 + +3n + +)(1 + log, n).
For = 1000, this 1.4 10 For n 200, this 1.7 104h
C.3 Error estimation
We choose a random prime with 59 bits. By the prime number theorem, there are at least 1.3 10 such prime numbers. (Wolfram alpha provides such values.) The prime is generated using the OpenSSL package (version 3.0.13, Jan 2024) [OpenSSL Project, 2024). Alternatively. one can also use GMP, the GMP multiprecision arithmetic library Granlund and the GMP development team 2023].
Choosing a non-prime: This can happen with probability 2 according to the openssl specifica- tion.
Choosing bad point: The total degree of all polynomials is bounded by 3 1000 (n 1000) and 5 10t0 (n = 200). We pick random values from a set of size 268 ~ 3 1017 in the generalized Schwartz-Zippel Lemma. This size is limited by the size of built-in integers. Thus the error here is bounded by 10-4 (for n 1000) and 1.6 10-7 (n 200).
Choosing a bad prime:
We have to estimate the probability that random prime divides the product of the evaluations of all polynomials the chosen random point. For this, we have to estimate log, (og2(Ls"), where the product of all fnnorms, is the sum all degrees and is the size of the smallest prime. This can be estimated by the preceding items by
1.4 10 + 3- 1013 logg (258)
< 1
(n 1000)
1.7 10 + 5- 1000 log, (268)
(268)
< 3.1 1012
(n = 200)
The error is bounded by (1.9 1000100/////3 1016.
58)
< 0.0026 for 1000 and (3.1
10.3/(1.3. 1026 58) S 1..1.10-00 6 by Proposition (Note that we can divide by the extra 58 log, (258), since the smallest prime has 58 bits whereas the proof of the proposition just assumes that is 2.)
Overall error:
By the union bound, the overall error probability is sum of all three probabilities, which is dominated by the third one. Since there is some slack in the estimates, one can safely estimate the sum by the last error probability. So for n 1000, the overall error probability is < 0.0026 and for n 200, the overall error probability is < 4.1 10-6
While for n 200, the error probability might be acceptable, one has to run the algorithm a few times for n 1000 reduce the error probability. But all estimates above very conservative worst-case estimates. For instance, the proof of the Schwartz- -Zippel lemma assumes that all roots of all polynomials occurring are integers. So, the typical error probability is much lower than our worst-case estimates.
D Further benchmarking
D.1 Random graphs of density 0.8, random tree structure
These test cases have random tree structure and random set of 80% of all possible bidirected edges.
test cases, all identifiable nodes are identifiable due to missing bidirected edges to O, and in all of them, most of the nodes are (I-)identifiable. Both SEMID and our program solve all test cases, and our program takes less than 0.5 seconds on each test case. treeID solved all test cases up to = 30 in less than 5 seconds each, but for 31 already, it failed with JavaScript heap out of memory after about minutes even when given 256 GiB of memory. Figure shows the execution times of the programs.
D.2 Random graphs of density 0.2, random tree structure, missing edges to 0
can be proven that these test cases cannot be solved by the half-trek criterion, see Appendix Due to the large number of missing edges, all test cases can be identified by threc-cycles (in many cases
27

---

250
SEMID
Our program
Our program
Execation time [s]
Execuiion time
30
150
20
100
60
10
20
40
00
80
100
120
140
160
180
200
0
20
40
60
80
100
120
180
160
180
200
Number of modies n
Number of modes
Figure 7: Random tree structure, random set of 80% of the possible bidirected edges (all identifiable by missing bidirected edges to 0)
Figure 8: Random tree structure, no missing edges to O: apart from that random set of 20% of the possible bidirected edges
TreelD SEMID
40
-
Our program
35
Execution tine [6]
Executio
20
20
15
10
100
120
140
160
150
200
20
40
60
80
100
120
180
160
180
200
Number of modes
Number modes
Figure 9: Random tree structure, missing edges to apart from that random set of 50% of the possible bidirected edges
Figure 10: Random tree structure, missing edges to O: apart from that random of 90% of the possible bidirected edges
even 1 + 2 + 3 ++ 1). treelD runs out of memory (memory limit: 256 GiB) for n 2 25. We did not benchmark against HTC/SEMID since provably cannot identify any edges and its running times were fairly oblivious to the graph structure. The results can be found in Figure
D.3 Random graphs of density 0.5, random tree structure, no missing edges to 0
treeID seems to perform better with higher density, most likely because there are less missing edges and therefore less identifying cycles to check. treeID runs out of memory (memory limit: 256 GiB)
for n 2 26. The results can be found in Figure
D.4 Random graphs density 0.9, random tree structure, no missing edges to 0
There seems to be bug in treelD. For 20, it crashes with if (newfastp. lenggh == 0) throw "Inconsistent solutions", but when run with --trace- (to show where the exception was thrown). no occurs and the output is correct. treelD runs out of memory (memory limit: 256 GiB) for n 2 34. The results can be found in Figure I0
E Limitations of HTC with no missing edges to the root
We explain that HTC fails to identify any parameter all when there are no missing edges the root. Recall that HTC works as follows: A set Y V satisfies the halftrek criterion with respect to e V
28

---

if |Y] equals the number of parents of u, Y does not contain nor any of the nodes that are connected by a bidirected edge to v, and there is system of halftreks with no sided intersections from Y the parents of v. A halftrek here is trek whose left part consists of a single node. 'wo treks have sided intersection, if the left parts have node in common or the right parts have node common or both.
A family Y., E V, of subsets of nodes satisfies the half-trek criterion if for every Y, satisfies the half-trek criterion with respect w. < v whenever w E Y, n htr(v) where htt(v) are all nodes u that can be reached by half-trek from and that are neither nor connected with a bidirected edge v. Foygel et al. [2022 Thm 1]
and addition, there is a total ordering of the nodes such that
prove that if an SCM satisfies the halftrek criterion, then all parameters are rationally identifiable.
Proposition 3. In a tree-shaped SCM with no missing edges to the root, HTC fails to identify any parameter.
Proof. Since there are no missing bidirected edges to O, all nodes can reach each other via halftreks. In particular, every node that is a candidate for Y, is also contained in htr(t). Now assume that there is total ordering on the nodes, For the minimum node vo + O in this ordering, there is no sel Y since there is no smaller node that could be put into Yoo
This is drawback of all state-of-the-au identification methods on general graphs. Van der Zander Proposition 2] show that any edge that is identifiable by the ACID algorithm [ummor et al. 2020 on tree-shaped SCMs is identifiable via missing edge to the root and then potential propagation via a Möbius transform along directed edges. Note that ACID subsumes all known polynomial time methods for generic identification in arbitrary SCMs.
al. 2022,
29


Reviews:
[{"review_id": "D6RsPiEeRf", "reviewer": "Reviewer_8jdN", "summary": "In linear structural causal models (SCMs), where the directed edges form a tree and undirected edges are arbitrary, Gupta and Blaeser (AAAI 2024, https://arxiv.org/abs/2311.14058) have demonstrated a polynomial-time algorithm for deciding generic identifiability. The present paper simplifies and implements the algorithm of Gupta and Blaeser. In particular, it uses the DeMillo–Lipton–Schwartz–Zippel algorithm for polynomial identity testing (https://www.sciencedirect.com/science/article/abs/pii/0020019078900674), and several further improvements in cycle-detection.", "questions": "Q1: To push the practical relevance further, one could ask whether in data that are not generated by tree-shaped SCM, but by some SCM of low structural complexity, the method performs better than commonly considered heuristics for the general, non-tree-shaped case. I would imagine it may improve upon their results substantially?", "limitations": "The limitations are well discussed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\nS1: The paper makes an substantial improvement on computational complexity of a fundamental problem, but also makes a substantial effort on implementing the approach in practice. \n\nS2: Overall, the paper and esp. the use of DeMillo–Lipton–Schwartz–Zippel is very elegant, but also practically useful and well motivated. \n\nWeaknesses:\n\nW1: The paper follows the same steps as Gupta and Blaeser (AAAI 2024, https://arxiv.org/abs/2311.14058), except better. Both intrinsically and in terms of the writeup, there is some overlap. Having said that, either it is self-plagiarism or \"the greatest form of flattery\", so I doubt that Gupta and Blaeser would mind. \n\nW2: While the writeup is generally to be commended, further improvements could be made. Starting from Section 4.2, the paper becomes rather technical, less well organized, and the 9-page version skips several important definitions (e.g., a trek, Word-RAM, ring homomorphisms). It may be worth skipping some of the standard definitions (such as SCMs), perhaps, and including those less common in AI/ML venues instead? Also, the papers ends in Section 5.3 very abruptly.", "was_revised": true, "final_justification": "I really like the paper. While perhaps limited in its practical importance, the contribution is very elegant and completes the picture of complexity of learning causal models. The numerical results are very strong, considering the focus has been on the theory.", "rebuttal": "Thank you for your thoughtful comments.\n\nRegarding the weaknesses:\n\nW1: While we generally follow the strategy of Gupta and Bläser, we would like to emphasize that our improvements are nontrivial and crucial for making the algorithm practical. Moreover, one can interpret the soundness proof by Gupta and Bläser as suggesting that identifying cycles is, in some sense, the only viable approach to solving the problem.\n\nThe running time of the Gupta and Bläser algorithm is $O(n^6)$, whereas ours is $O(n^3 \\log^2 n)$. Of course, the additional polylogarithmic factor in our bound is non-negligible for small and moderate values of $n$. However, as shown in Figure 5, for $n = 100$, our algorithm is already faster than $O(n^4)$ (as mentioned in the paper, the break-even point is around $n = 50$). Since the Gupta and Bläser algorithm employs techniques similar to ours, the constants hidden in the $O$-notation of a potential implementation of the Gupta and Bläser algorithm will be comparable to ours. Therefore, our implementation is faster by a factor of at least $n^2$ on moderately sized instances — for example, a factor of $10.000$ (!) for $n = 100$.\n\nW2: We appreciate your comments regarding the write-up. Since the paper lies at the intersection of algebraic statistics and causality and employs methods from algebraic algorithms and computer algebra, many concepts from different areas need to be introduced. Our intention was to first provide a gentle introduction to the topic, then explain our main ideas for the improvements in Sections 4.1 and 4.2 using the example of covariance computation, and finally present the further improvements in Section 4.3, with more details provided in the appendix. But we see your points and will incorporate your suggestions.\n\nRegarding the questions:\n\nQ1: Generic identifiability is a property of an SCM, not of a particular data set. Given a tree-shaped SCM, we produce circuits (or determine that none exist) that compute the parameters for almost all possible observed sets of covariances. This does not directly apply to the scenario outlined in your question. However, one could attempt to find a tree-shaped SCM in a first step that approximates the observed scenario, and then use our methods to estimate the parameters. This seems like an interesting direction for future research. Thank you for raising this question."}, {"review_id": "igGd7cvU1j", "reviewer": "Reviewer_wxcS", "summary": "This paper provides an algorithm to identify linear tree-shaped SCMs. The contribution of this paper lies in the O((n^3)*(log^2(n))) temporal complexity of the proposed algorithm compared to the state of the art O(n^6).", "questions": "* An overview of the algorithm's steps and their respective complexity would be useful.\n\n* In my opinion, it is very important to give more intuition as to why this very specific class of linear tree-shaped SCMs are interesting and useful.\n\n* The benchmark section should be extended.\nFor exemple, how do your algorithm perform when the size of the cycles of missing bidirected edges vary.\nYou explain that treeID performs especially bad because of the implementation of the identity test. Could you show how treeID with a better identity test implementation perform?\nThe plotted graphs should also include the theoretical complexities of the different algorithms.\nWhat is the goal of adding the black plot which shows a worst version of your algorithm (with O(n^4) detection of identifying cycles)? I do not understand the added value.\nFor figure 5: You plot the execution time of SEMID HTC while saying that it cannot identify any of the cases. I do not understand the added value. I believe it would be more relevant to compare with another algorithm that is complete (e.g. the ID algorithm) ideally the most efficient one .\n\n* I believe \"Gupta and Bläser 2024a\" is not cited properly in the abstract.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The main strength of this paper lies in the thorough step by step description of the algorithm.\nMoreover, the improvement of temporal complexity allows the practical identification of SCMs with more nodes. The authors are clear about their contributions do not over sell it. While the improvement described by the authors seem sound, all proofs are left to the appendix.\nThe biggest weakness of this paper in my opinion is the small significance and originality and especially the lack of motivation. The authors focus on identifying a very restrictive type of SCMs (linear and tree-shaped), however they do not give any example of application where this specific task is useful. The only argument in favor of this line of study is the fact that identifying a broader class of SCMs would be harder.\nOn top of that, the author do not give the first algorithm to solve this problem nor even the first polynomial algorithm. They only improve an existing algorithm.\nLastly, the benchmarking section seems fairly weak when the only contribution is an improved theoretical temporal complexity.", "was_revised": true, "final_justification": "The authors addressed most of my questions so I slightly increased my score. However, I remain somewhat unconvinced of its broad applicability", "rebuttal": "Thank you for your thoughtful comments.\n\nRegarding weaknesses:\n\n- The complexity of generic identifiability is a long-standing open problem: This means one can either look for methods that are not complete or for restricted graph classes for which we can design an efficient complete algorithm. This work takes the second route as have done others before, like van der Zander et al. (2022) or Gupta and Bläser (2024), all references are in the paper.\n\n- While the algorithm by Gupta and Bläser is also polynomial time, our algorithm is the first that is practical. We are not aware of an implementation of the algorithm by Gupta and Bläser. With some extra effort, we could have also implemented it using our code framework. However, as already pointed out in the answer to reviewer 8jdN, the algorithm is not practical even for moderate $n$: The running time of the Gupta and Bläser algorithm is $O(n^6)$, while ours is $O(n^3 \\log^2 n)$.  Since the Gupta and Bläser algorithm uses similar techniques to ours, the constants hidden in the $O$-notation will be comparable. Therefore, our implementation is faster by a factor of at least $n^2$ on moderately sized instances, which for instance means a factor of $10000$ for $n = 100$.  \n\nRegarding questions  (our answer items follow the same order as the question items): \n\n- Thank you for providing this nice idea. Page 5 contains an outline of the algorithm at the top, but we will add a more detailed description with complexities.\n\n- Finding efficient criteria for deciding whether an SCM is generically identifiable has been a long-standing open problem, see e.g. Foygel et al. (2012, Problem 1). Therefore, looking for subclasses of SCMs for which this is possible is a natural approach to this problem. Moreover, whenever we have hierarchical data, tree-shaped SCMs naturally occur, see for instance Thorson et al. (2023).\n\n- Regarding benchmarking: We are happy to extend the benchmarking. However, the running time of our algorithm is very stable, it essentially depends on only two parameters: whether there are missing edges to the root, and the length of the identifying cycles. Beyond that, the specific graph structure has little impact. If there are missing edges to the root, we can identify almost immediately (as shown in Figures 6 and 7). After that, the runtime depends only on the length of the missing cycle, since we use iterated matrix products to search for all potential missing cycles in parallel. However, since we use binary search to find the length of the missing cycle (which is the most costly step), this also has little influence, since we always need to check for length $n/2$. If the length is $n$, then we will always branch in the more costly part during binary search, so this is the worst case.  Similar observations apply to the runtime of the treeID algorithm, aside from the inefficiencies in identity testing, and HTC.\nRegarding your concrete questions:\n  - For exemple, how do your algorithm perform when the size of the cycles of missing bidirected edges vary: \nIn Figure 5 we use the worst case for our algorithm, only one missing cycle which contains all nodes. In the random graphs in Figures 8,9,10, the identifying cycles are short, since this happens with high probability in a random graph (see also Section D.2). These are the two extreme cases. One could add cases in between, these would however be quite comparable.\n  - You explain that treeID performs especially bad because of the implementation of the identity test. Could you show how treeID with a better identity test implementation perform: This would require recoding treeID, since we think, after we inspected the code, that the current implementation uses a computer algebra system to perform the identity test, which would be hard to remove. Even with more efficient identity tests, the treeID algorithm still brute-forces over all potential cycles, which can be exponentially many.\n  - The plotted graphs should also include the theoretical complexities of the different algorithms: One can do this, however, this would mean that one has to set the constant of the O-notation to some \"guessed\" value to fit the observed running times. But we agree that this is helpful for comparison reasons and we will add them.\n  - What is the goal of adding the black plot which shows a worst version of your algorithm (with O(n^4) detection of identifying cycles)? I do not understand the added value: While $O(n^3 \\log^2n)$ is asymptotically faster than $O(n^4)$, it is not clear whether this is true for small $n$ (due to hidden constants). (See lines 965-966 in the paper.) The plot confirms that the break-even point is indeed small.\n  - For figure 5: You plot the execution time of SEMID HTC while saying that it cannot identify any of the cases. I do not understand the added value: This still tells you something about the running time of HTC, even if it fails to identify any parameters. In this case, it will perform $n$ max-cut computations, which is a lower bound for its running time in general, since it performs between $n$ and $n^2$ many max-cut computations depending on the instance.\n  - I believe it would be more relevant to compare with another algorithm that is complete (e.g. the ID algorithm) ideally the most efficient one: There are only two complete methods known. One is based on Gröbner bases. This only works for small graphs. For instance, van der Zander et al. (2022) report that the Gröbner basis algorithm took more than four months (sic!) on the benchmark of Figure 4 (where we need 8s). The second one is based on the existential theory of the reals, see Dörfler et al. (2024). We are not aware of any implementation, but it will, like the Gröbner basis approach, only work for small $n$. So there are no efficient complete algorithms known for general graphs. In the light of the related hardness results by Dörfler et al. (2024), the problem might be hard in general. We do not know what you mean by \"the ID algorithm\". The most general algorithm we know is the ACID algorithm by Kumor et al. (2020). However, on tree-shaped SCMs it has the same problems as HTC, as shown by van der Zander et al. (2022), see lines 1180 - 1184. As ACID is an extension of HTC, it is more involved and slower.\n\n- Thank you for pointing this out, we will add the bibliographic details of the reference to the abstract."}, {"review_id": "nYbMWfaBTe", "reviewer": "Reviewer_KPLf", "summary": "This paper focuses on the problem of generic identifiability in linear structural equation models (SEMs) with tree-structured graphs. The authors build on the recent complete algorithm by Gupta and Bläser, which determines the identifiability of model parameters with a high computational cost of $O(n^6)$.\nTo improve efficiency, this paper proposes a series of optimizations for each step in the Gupta-Bläser framework. These include simplifying the covariance computations using Wright's trek rule, applying generalized Schwartz–Zippel-based identity testing to replace symbolic rank checks, using modular arithmetic to avoid large integer computations, and designing an efficient graph-based method for finding identifying cycles and paths. Together, these steps reduce the overall runtime to $O(n^3 \\log^2 n)$, while preserving correctness guarantees with high probability.\nThe method is implemented and evaluated empirically on synthetic SEM instances, showing strong improvements in runtime and coverage compared to existing tools.", "questions": "(1) Can the authors give a realistic example where the data distribution would naturally follow a tree-structured linear SEM?\n\n(2) If the given tree structure contains some errors, such as incorrect edge directions or wrong connections, what kind of results would the algorithm produce?", "limitations": "See weakness and questions.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n(1) The reduction in computational complexity brought by the optimized algorithm makes it more practical for moderate-sized SEMs.\n\n(2) The proposed optimizations still maintain correctness with high probability under a randomized setting.\n\n(3) The method comes with a C++ implementation, which further improves its runtime efficiency.\n\nWeakness\n\n(1) The method only applies to tree-structured linear SEMs, which is too restrictive and therefore limits its applicability in practice.\n\n(2) The specific optimizations, such as using the Generalized Schwartz–Zippel lemma for randomized polynomial identity testing, are based on standard existing techniques.\n\n(3) The method is evaluated on only one dataset.", "was_revised": true, "final_justification": "While the focus on tree-shaped structures is somewhat too specific, it nonetheless represents a meaningful contribution to the field. After the discussion, I maintain a generally positive evaluation.", "rebuttal": "Thank you for your thoughtful comments.\n\nRegarding the weaknesses:\n\n(1) It is true that tree-shaped SCMs represent a restricted class. However, the complexity of generic identification has remained an open problem for more than 20 years. In light of the (related) hardness results by Dörfler et al. (2024), the problem may indeed be computationally difficult. Therefore, it is reasonable to search either for criteria that are efficient but not complete, or for classes of SCMs for which the identification problem can be solved. We here follow the second path, as has also been done by van der Zander et al. (2022) or Gupta and Bläser. \n\n(2) While it is true that some of the underlying techniques—such as the Schwartz-Zippel lemma or self-reduction—are well-known in algorithm theory, they are rarely used in practical implementations. Translating the algorithm by Gupta and Bläser into practice was a highly nontrivial task. In particular, the idea of choosing random values only once at the beginning is novel, and care must be taken with dependencies, especially in the self-reduction part, which required new local update techniques, too. We improve upon the algorithm by Gupta and Bläser by a factor of more than $n^2$ (nearly $n^3$ for large $n$), which is crucial for making it practical. It saves a factor of about $10.000$ for SCMs of size $n = 100$. (More details on this can be found in the answer to reviewer 8jdN).\n\n(3) While it is true that we only used one graph per input size to draw the figures for simplicity, the running time of our algorithm does only depend on two parameters of the graph: whether there are missing edges to the root and the length of an identifying cycle. In the first case identification is very fast. In the second case, the most costly part of the algorithm uses linear algebra techniques (iterated matrix products) to find the identifying cycles and is oblivious to the actual edges in the SCM, since the product matrices get dense very fast. The longer the cycle, the more time we need, since we have to compute longer matrix products. However, this influence is also small, since we use binary search and always need to test for length $n/2$. If the cycle is long ($n$ in the worst case), then we always branch in the more costly part in the search. But the overall effect is small.  There are some parts in the algorithm where the actual edges play some role (computation of covariances, self reduction), but they are of lower complexity and their influence is minor (as can be seen in Figures 7,8,9).\n\nRegarding the questions:\n\n(1) Finding efficient criteria for determining whether a graph is generically identifiable has been a long-standing open problem—see, for example, Foygel et al. (2012, Problem 1), which remains unresolved. (Full references provided in our paper.) Consequently, investigating subclasses of SCMs for which identifiability can be determined is a natural approach. Moreover, in cases involving hierarchical data, tree-shaped SCMs arise naturally—see, for instance, Thorson et al. (2023). Of course, in practice, the tree structure may not be perfect. In such cases, one could attempt to remove a few edges to obtain a tree. If this resulting SCM is not generically identifiable, then the original one will not be either. The converse, however, does not hold, and in such cases, the identification result must be manually transferred to the original instance.\n\n(2) Generic identifiability is a property of an SCM, not of a particular data set. It means that all parameters are uniquely determined for almost all sets of observed covariances. (This is why, for example, Brito and Pearl (2002) refer to it as \"almost everywhere identifiability.\") Typically, one also obtains circuits that compute these parameters. So the \"easy\" answer to your question is that our algorithm will determine whether the perturbed SCM is generically identifiable, and if so, it will produce expressions for the parameters. More interesting, of course, is the question you intended: whether we can transfer the results from the perturbed SCM to the original one. Since we still lack a clear understanding of the complexity of generic identification, we are far from having general methods to determine how modifying a few edges affects the number of solutions. However, depending on the perturbations, certain properties might be preserved. For instance, adding directed edges will preserve nonidentifiability."}, {"review_id": "OZSguVd5al", "reviewer": "Reviewer_hSv9", "summary": "This paper presents a randomized algorithm with an improved time complexity from $O(n^{6})$ to $O(n^{3}(log(n))^{2})$ that is complete for identifying the functional parameters in linear structural causal models in which the directed edges form a tree. The key contribution of this paper is to develop a more efficient method for polynomial identity testing (lines 238-242) via Lemma 3. It also provides a theoretical analysis of the running time of the proposed method via algebraic fingerprinting.", "questions": "- Why did the authors not compare their algorithm with that by Gupta and Blaser [2024a] instead of [van der Zander et al. 2022] and [Barber et al., 2023]?\n- Line 120: ‘Our implementation vastly outperforms the treeID algorithm of the DAGitty package with respect to running time.’ Does that mean the difference is only due to implementation, but not the algorithmic improvement?\n- In the proof of Lemma 1, isn’t $\\omega_{0,0}$ ill-defined in a mixed graph?\n- In line 334, since the layers correspond to time steps, I am a bit perplexed by the use of the index t for $W_t$, is that the same as the length t?\n- How can we know the difference of the execution time in Figure 4 is not affected by the choice of programming languages, e.g., C++ vs R that are used to implement the algorithms? \n- How many test cases were used per number of nodes in Figure 5, similarly in Figure 6? I am guessing the y-axis execution time is the sum of all execution times of all cases? If not, shouldn’t there be variations?\n\nSuggestions:\n\n- Typos: Line 121: ‘eges’ -> ‘edges’\n- I find it very confusing to see the index 0 represent the root in the SCM and the actual number 0 appear in equations 3 and 4 at the same time.\n- I think the proofs can be more thorough without skipping steps. For example, in the proof of Lemma 1, the authors should explain why $\\sigma_{i,0} = \\sigma_{p,0}\\lambda_{p,i} + \\omega_{i,0}$? I think it should be something like this $Cov(X_{i},X_{0}) = \\sigma_{i,0} = Cov(\\lambda_{p,i}X_{p}+\\epsilon_{i}, X_{0}) = Cov(\\lambda_{p,i}X_{p} + \\epsilon_{i}, X_{0}) = \\lambda_{p,i}Cov(X_{p}, X_{0}) + Cov(\\epsilon_{i}, X_{0})$ given the condition that X_{i} has a unique parent under a tree-shaped SCM. Also, in the proof of Proposition 2, it would be better to elaborate on why the integer can have at most log z distinct prime divisors to increase clarity.\n- Line 309: ‘This is done in two steps: First finding’ -> ‘This is done in two steps: first, finding’\n- In lines 323, it will be good if the authors can give an example to illustrate how the contribution may be cancelled by other closed walks\n\nI am willing to increase my score if the authors can address my concerns well.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n- The paper improves the Algorithm proposed by Gupta and Blaser in several aspects:\n   - It replaces the step of computing the rank of an edge with a more efficient method using Wright’s trek rule to reduce the time complexity from $O(n^{3}\\log n)$ to $O(n^{2})$.\n   - It uses the Schwartz-Zippel lemma to achieve faster polynomial identity testing. The idea of performing multiple identity tests is innovative. Lemma 3 is the result that follows the idea. It brings down the complexity from $O(n^{4})$ to $O(n^{2})$.\n  - The authors clearly explain how to possibly handle the large number of rank computations with algebraic fingerprinting to substantiate their algorithmic contribution.\n  - For finding identifying cycles, the simple trick of adding a label on the edge to avoid cancellation is creative.\n  - The authors show that ordinary polynomial identity testing is more efficient for FASTPs. \n\n- Generic identification is an important and hard problem. This work makes the existing algorithm more efficient to scale in a restrictive case.\n\n- I have checked the proofs and I couldn’t find any glaring issues other than some relatively minor clarity issues.\n\n**Weaknesses:**\n\n- The algorithm is not compared with the algorithm by Gupta and Blaser empirically, while that is the main baseline. I think even if the code is not available publicly, the authors should be able to code up this algorithm, as it is a closely related work.\n\n- I find the space in the paper can be better utilized to enhance the quality of the discussion in the paper.\n  - For example, instead of describing what specific programming languages the baselines are written in. The authors could have used to space to discuss things that are more important, e.g., writing the definition of a trek or giving the short proofs in the main paper. Also, if the introduction has already said that Gupta and Blaser improved treeID, there is no need to say ‘Our implementation vastly outperforms the treeID algorithm of the DAGitty package with respect to running time.’  \n  - I think the following sentences can be moved to the experiments section, and the authors can keep the key takeaway message, which is that the proposed algorithm outperforms the baselines. Otherwise, I think it makes the introduction less clear.  It unnecessarily leaves readers the room to question the significance of the contributions. For example, why do the authors need to hand-pick scenarios to show that the proposed algorithm is better? Are those scenarios significant? If so, why?\n       -   ‘…our algorithm outperforms HTC, too. On certain worst case instances for our algorithm, we are still faster than HTC. However, if one wants a smaller error probability than 0.000005, we have to run our algorithm a few times and we are somewhat slower than HTC. On the other hand, HTC fails to identify any nodes on these graphs, so the results are incomparable.’ \n  - The second section ‘Generic identification’ repeats many definitions that have already been discussed in the introduction e.g., directed edge, bidirected edge, linear SCM, etc.\n  - Section 3 defines what has been defined in the introduction as well,l e.g., the meaning of completeness.\n  -  Line 176 “The conference version does not give any concrete bound, the arXiv version [Gupta and Bläser, 2024b] states a running time of $O(n^6)$.” I am not sure why there is a need to elaborate on this point in the main paper.\n  -  The space can also be used to put on some definitions for improving readability. For example, some wordings are not defined in the introduction, and they appear later in section 2, e.g., in line 121: ‘…Missing bidirected edges to the root…’, it is not clear whether the authors simply mean there is no bidirected edge adjacent to the root until I have read section 2. The idea of a trek is frequently used, but its definition is missing from the paper. Other concepts like simple walk, strongly connected components can also be defined.\n  - The subsection 5.1 title is very strange.", "was_revised": true, "final_justification": "Previously, my concerns were mostly about clarity, especially for the experimental section. After the rebuttal, the authors have clarified why the baseline algorithm is not included, and I think they have provided a reasonable answer. Based on the authors' willingness to accept my suggestions and the promised revision, I believe the experimental section will now be better prepared for a wider range of audiences to understand.", "rebuttal": "Thank your for your thoughtful comments:\n\nRegarding weaknesses:\n\n- We are not aware of any existing implementation of the algorithm by Gupta and Bläser. With some additional effort, we could have implemented it within our code framework. However, as already pointed out in our response to Reviewer 8jdN, the algorithm will not be practical even for moderate values of $n$. We provide more details in the answer to your first question below.\n\n- Thank you for your suggestions for improving the presentation. We will take them into account and incorporate them. Since the paper lies at the intersection of algebraic statistics and causality and employs methods from algebraic algorithms and computer algebra, many concepts from different areas need to be introduced. Depending on the background of the actual reader, concepts might be more or less well-known. So we are really grateful for your input.\n\nRegarding questions (our answer items follow the same order as the question items):\n\n- We did not compare our algorithm with that of Gupta and Bläser for two main reasons. First, we are not aware of any existing implementation of their algorithm. Their result is primarily of theoretical interest, identifying a graph class for which generic identification is provably feasible in the sense of algorithm theory. Second, their algorithm, in its current form, is not practical even for moderate $n$. With some additional effort, we could have adapted our framework to implement the Gupta and Bläser algorithm. However, the running time of their algorithm is $O(n^6)$, while ours is $O(n^3 \\log^2 n)$. As shown in Figure 5, for $n = 100$, our algorithm already performs clearly below $O(n^4)$ (with the break-even point around $n = 50$). Given that both algorithms use similar techniques, the constants hidden in the $O$-notation are likely comparable. Thus, our implementation is faster by a factor of at least $n^2$ on moderately sized instances — for example, a factor of $10.000$ for $n = 100$.\n\n- Both factors contribute. The treeID algorithm has exponential worst-case running time as it brute-forces over all potential identifying cycles, which is one reason why our method is faster. Additionally, the implementation of identity tests in treeID appears to be inefficient. From our understanding of the treeID code, identity tests are performed by expanding polynomials and passing them to a computer algebra system. This approach can take exponential time (and even space) in the worst case. We believe this, at least partly, explains the irregular behavior observed when $n$ reaches 20.\n\n- $\\omega_{0,0}$ denotes the variance of the error term $\\epsilon_0$ (see line 31) at the root node $0$. $\\omega_{0,0} = \\sigma_{0,0}$, since the root has no incoming directed edges. One could have used the notation $\\omega_0$, but using double indices makes the summation formulas derived from Wright’s trek rule more elegant. (Similarly, $\\omega_{i,i}$ denotes the variance of the error term at node $i$.) We will clarify this in the revised version.\n\n- $t$ always means the length of an identifying cycle, which we are currently looking for. This is stated in line 321. In the layered graph in the self reduction part, time steps go from $1$ to $t$, so $t$ is the \"total time\". We understand your confusion and maybe it is better to rename $t$ into $\\ell$ for length.   \n\n- Of course, running times are affected by the choice of programming language and other implementation details. However, these factors only influence the leading constants in the running time. If we have only one input size as in Figure 4, it is very hard to estimate the influence of the different effects. But as shown in Figure 5, we are also faster when $n$ increases, which means that the main effect comes from our faster algorithm. The reason we tested our algorithm on the benchmark of 879 graphs in Figure 4 was that the expected output was known from the paper by van der Zander et al. (2022), and we used it to verify correctness.\n\n- The runtime of our algorithm is very stable, and two main features influence it: whether there are missing edges to the root, and the length of the identifying cycles. Beyond that, the specific graph structure has little impact. If there are missing edges to the root, we can identify almost immediately (as shown in Figures 6 and 7). After that, the runtime depends only on the length of the missing cycle, since we use iterated matrix products to search for all potential missing cycles in parallel. However, this influence is also small, since we use binary search and we always need to check for length $n/2$. In the worst case of length $n$, we will always branch in the more costly half of the binary search, but the overall effect is minor. Similar observations apply to the runtime of the treeID algorithm, aside from the inefficiencies in identity testing, and HTC. Execution times were consistent across multiple runs. For simplicity, we used a single input instance to generate the plots, as noted under \"7. Experiment statistical significance\" in the paper checklist. The actual edge distribution can influence the running time somewhat, but only lower order terms: the tree structure slightly affects variance computation (an $O(n^2)$ term), and the density of bidirected edges influences the self-reduction step ($O(n^3)$), though the overall impact is small (as seen in Figures 8, 9, and 10).\n\nRegarding suggestions:\n\n- Thank you, we will correct this.\n\n-  We adopted this convention from previous papers on the topic. It is convenient because nodes can be used directly as indices. However, we understand the potential confusion and will add a clarifying remark.\n\n- We are using equations (3) and (4) on page 4 in the proof of Lemma 1, which are exactly your calculations. We should have mentioned this explicitly — thank you for pointing it out.\nRegarding Proposition 2: Let $n$ be the number of different prime factors. Since the smallest possible prime factor is $2$ and $z$ is the product of all its prime factors, $2^n \\le z$, which gives the bound. We will add this to the proof.\n\n- Thank you, we will correct this.\n\n- This behavior can occur because matrix entries may be negative. For example, consider two disjoint paths between nodes $i$ and $j$ of the same length, where all weights are equal except for the last edges, which are negatives of each other. With a bit more care, one can construct such examples that stem from tree-shaped SCMs. We will add an example to the appendix of our paper."}]

Author rebuttal:

Meta-review: The paper focuses on improving the computational complexity of identification for linear tree-shaped SCMs, which is an interesting and underxplored area in causality. It provides a few rigorous theoretical contributions and a sound analysis, and the reviewers have appreciated the elegance of its methods and the technical clarity. Some of the reviewers had concerns regarding to the limited experiments, but these have been adequately addressed in the rebuttal by the authors. On the other hand, some concerns remain about the method's broader applicability based on the quite restrictive assumptions (linear+tree shaped SCMs). Nevertheless, the paper's theoretical contributions are interesting enough to recommend an acceptance.
Decision: Accept (poster)