Strong and Weak Identifiability of Optimization-based Causal Discovery in Non-linear Additive Noise Models
Authors: Mingjia Li
Hong Qian
Tian-Zuo Wang
ShujunLi
Min Zhang
Aimin Zhou
Venue: ICML 2025 poster (2025)
Keywords: Optimization-based Causal Discovery
Identifiability
Additive Noise Model
Order Search
Implicit Function
Primary area: general_machine_learning->causality

Abstract: Causal discovery aims to identify causal relationships from observational data. Recently, optimization-based causal discovery methods have attracted extensive attention in the literature due to their efficiency in handling high-dimensional problems. However, we observe that optimization-based methods often perform well on certain problems but struggle with others. This paper identifies a specific characteristic of causal structural equations that determines the difficulty of identification in causal discovery and, in turn, the performance of optimization-based methods. We conduct an in-depth study of the additive noise model (ANM) and propose to further divide identifiable problems into strongly and weakly identifiable types based on the difficulty of identification. We also provide a sufficient condition to distinguish the two categories. Inspired by these findings, this paper further proposes GENE, a generic method for addressing strongly and weakly identifiable problems in a unified way under the ANM assumption. GENE adopts an order-based search framework that incorporates conditional independence tests into order fitness evaluation, ensuring effectiveness on weakly identifiable problems. In addition, GENE restricts the dimensionality of the effect variables to ensure \emph{scale invariance}, a property crucial for practical applications. Experiments demonstrate that GENE is uniquely effective in addressing weakly identifiable problems while also remaining competitive with state-of-the-art causal discovery algorithms for strongly identifiable problems.

Strong and Weak Identifiability of Optimization-based Causal Discovery in Non-linear Additive Noise Models
Mingjia Li! Hong Qian*!
Tian-Zuo Wang Shujun Li! Min Zhang' Aimin Zhou'
Abstract
1. Introduction
Causal discovery aims to identify causal rela- tionships from observational data. Recently,
Discovering causal relationships behind variables is erucial to data science and plays a key role in a wide range of fields, including telecommunication network fault diagnosis (Li et al. 2024), education (Schochet 2013) and human ethol- ogy (Cai et al. (2017). While randomized controlled trials (RCTs) are considered the gold standard for studying causal relationships, they are usually expensive or even impossible to implement. This limitation motivates causal discovery methods that can infer causal relationships from observa- tional data. Recent advances in this field have made causal discovery an increasingly vital topic (Spirtes et al. 2000 Pearl 2009).
optimization-based causal discovery methods have attracted extensive attention in the liter- ature due to their efficiency in handling high- dimensional problems. However, observe that optimization-basee methods often perform well on certain problems but struggle with others. This paper identifies a specific characteristic of causal structural equations that determines the difficulty of identification in causal discovery and, in turn, the performance of optimization-basee methods. We conduct an in-depth study of the additive noise model (ANM) and propose to further divide iden- tifiable problems into strongly and weakly identifi- able types based on the difficulty of identification. We also provide a sufficient condition to distin- guish the two categories. Inspired by these find- ings, this paper further proposes GENE, a generic method for addressing strongly and weakly iden- tifiable problems in unified way under the ANM assumption. GENE adopts an order-based search framework that incorporates conditional indepen- dence tests into order fitness evaluation, ensuring effectiveness on weakly identifiable problems. In addition, GENE restricts the dimensionality of the effect variables to ensure scale invariance, a property crucial for practical applications. Exper- iments demonstrate that GENE is uniquely effec- tive in addressing weakly identifiable problems while also remaining competitive with state-of- the-art causal discovery algorithms for strongly identifiable problems.
Optimization- causal discovery is a class of methods that aims to identify causal relationships from observational data by leveraging optimization techniques. The core idea behind optimization-bant
causal discovery is to first assign fitness score given causal structure based on how well it fits the observed data. Optimization techniques are then employed to search for causal graphs with high fitness scores, thereby facilitating the discovery of causal relation- ships. In recent years, continuous continuous-optimmzaatoo optimization based causal discovery methods (Zheng et al.] 2018 2020 Lachapelle
et al. 2020 Yu et al. 2019 Liu al. 2024) have garnered extensive attention in the literature due their capability to deal with high high-dimensional problems efficiently, making them particularly appealing for large-scale data analysis.
However, we observe that even under the same causal model assumption, namely, the additive noise model (ANM) (Hoyer et al., [008)), optimization- based causal dis- covery may perform very differently. Figure ! presents two pairs of such examples (a) and (b), where in each pair, the causal models above and below are both under ANM and share the same causal structures. For Figure
I (a. 1). where = x² + N and N is a noise term, it is easy to identify the true causal structure using only regression, as regression along the correct causal direction fits well but not vice versa. In contrast, for Figure (a.2). where y = x² +2+ regres- sion generally fits well for both directions. Distinguishing the fitting difference between the two directions may re- quire extremely large amount of data; otherwise, a wrong causal graph is likely to be learned with limited samples. In
Shanghai Institute Al Education, and School Computer Science and Technology, East China Normal University, Shanghai, China. 'National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China. "School of Artificial Intelli- genee, Nanjing University, Nanjing, China. Correspondence to: Hong Qian <hqian www...cc...c.........
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Strong and Weak Identifiability of Optimization-aan based Causal Discovery in Non-lincar Additive Noise Models
(a.1) N, strongly sdemifiuble
(b.1) = x² y N, stoongly ideniiiable
sionality of the effect variable by exploiting R instead of mean square error (MSE) during order estimation. By doing so, it ensures scale invariance ! meaning it performs sta- bly under different data scales, which is crucial attribute in practical applications. By leveraging these advantages, GENE provides a robust solution for causal discovery across a wide range of scenarios. Refer to Appendix for a de- tailed review of related work.
X
Y
1a.23 - x² + N. weakly ademifuuble
Z
(b a x y y-+
weakly identifiblle
Extensive experiments are conducted on both synthetic and real-world Sachs (Sachs et al. 2005) datasets. The results indicate that, compared to the state-of-the-an algorithms (SOTAs), only GENE is effective for weakly identifiable problems, while for the strong ones, GENE remains compet- itive. It is worth noting that, on the real-world Sachs dataset, GENE is significantly superior SOTAs.
Figure 1. Examples of the strongly and the weakly identifiable causal models. Here N is a Gaussian noise term.
such cases, additional properties must be utilized (Hoyer jet al. 2008; Zhang & Hyvärinen 2009). Similar situations apply the examples in Figure [ (b.1) and (b.2). These ex- amples demonstrate that even for identifiable causal models with the same causal structure, the difficulty of identification can vary significantly.
2. Preliminaries
Before delving into the specifics of our approach, we first outline the foundational concepts for understanding causal discovery, identifiability, and order-based methods.
We highlight that this difference arises from the existence of implicit functions within the structural equations of the causal model. These implicit functions categorize problems into strongly and weakly identifiable types. Additionally, we derive a sufficient condition to distinguish between these categories. Specifically, strongly identifiable models are easier to identify, as they yield clear distinction in the re- gression process metrics between different causal directions. Conversely, weakly identifiable models lack this distinction due to the existence of implicit functions, making them more difficult to identify. With limited samples, additional criteria, such residual independence (Hoyer al., 2008 Zhang & Hyvärinen| 2009), are necessary in the identification process of weakly identifiable models.
2.1. Causal Discovery
Causal discovery, also known as causal structure learning, aims to discover the graph of the causal graphical model (CGM) M (Po. 9) behind the observational data. Our work primarily considers scenarios in the absence of latent variables (though see (Wang al. 2023 Ni et al., 2025) for approaches addressing causal discovery with latent vari- ables). Formally, given the sample matrix D E Rnxd with n i.i.d. observations sampled from the joint prob- ability distribution P. over a variable set of d variables V = (Vi V2..... ... V2), the task is to find a directed acyelic graph (DAG)
(V, E) which best describes P.. A struc- tural equation model (SEM) is defined as S (S, P.). S is set of d structural equations, and P, is the joint proba- bility distribution of mutually independent noise variables N = (Ni, ..)...,,,,
Unfortunately, the strength of identifiability can rarely be known in advance. To address both strongly identifiable and weakly identifiable problems in a unified manner, this paper proposes GENE: a generic causal discovery method for both strongly and weakly identifiable problems under ANM. GENE employs order-based search framework that integrates conditional independence tests into the fit- ness evaluation of the order, which is vital for enhancing its effectiveness in addressing weakly identifiable problems. Interestingly, our results align well with (Reisach et al.] 202I). which points out that certain continuous optimiza- tion methods may suffer from data rescaling processes, such as data standardization and changing the units of variables; furthermore, we reveal that this limitation of continuous optimization methods arises because their optimization pro- cess does not explicitly distinguish between cause and effect in causal relationships, making it unable to control the data scale during fitting. In contrast, GENE restricts the dimen-
Se: V3 = f((Vpa()) pato, 1,,,=1,2, ..,, dd
(1)
where Vpa(s) denotes the parents of node in G, and fa is a function p/ + IR. Like CGM, SEM also entails P.. as sampling from P. is equivalent to sampling from P,, and then propagating the samples through S.
2.2. Causal Identifiability
Definition 2.1 (Identifiabillity. Given a set of assumptions A on CGM M = (P., graph g is said to be identifiable from P, if there exists no other CGM MM = (P.,, p 9) satisfy- ing all assumptions in A such that & + & and P. = P..
Details are discussed in the Causal Order Estimate section.
2

---

Strong and Weak Identifiability of Optimization- Causal Discovery in Non-lincar Additive Noise Models
Generally speaking, the identifiability of a CGM is deter- mined by whether multiple distinct DAGs can represent the same probability distribution P.; if so, these DAGs are said to belong to the same equivalence class. In fact, under causal faithfulness and Markov assumptions, causal discovery of- ten only recovers a graph up to its Markov equivalence class (MEC) Chickering 1995| Spirtes et al. 2000; Wang et al.] 2024). There are many studies on the causal identifiability under some specific scenarios, such as linear functions with non-Gaussian noise (LiNGAM) (Shimizu et al. 2006), non- linear functions with additive noise (ANM) (Hoyer et al. 2008 and post-nonlinear functions (Zhang & Hyvärinen
reduces to estimating and searching for the causal order. This idea can least date back to TTyssier & Koller (2005); Schmidt et al. (2007). First, compared to DAG space search, order-based based methods deal with a much smaller search space. Second, it avoids the issue of enforcing acyclicity since the order naturally guarantees no cycles in the graph. Third, the causal order is closely related to identifiability since they both focus on the cause-effect direction, which means that the existing identifiability techniques can be incorporated into order-based methods.
3. Strength of Identifiability
2009). This paper follows the ANM setting with the SEM
written as:
In this section, we propose a formal definition for the strength of identifiability, dividing SEMs into strongly and weakly identifiable ones. We further disclose sufficient condition to distinguish between strong and weak identi- fiability, which is proved based on the implicit function theorem (Rudin et al. 1976).
Vi = ((pp)()) + i = 1,2, .d,
d,
where fi is a non-linear function from R/Vassil + R. In ANM, (Hoyer et al. 2008) show that for bivariate case, i.e., only consider two variables X and Y. identifiability is acces- sible through residual independence analysis. Specifically, can first apply non-linear regression of Y on X, and calculate the residual between the predicted value and the true value, then test the independence of the residual and the cause variable (here is X). Do the same thing in another direction (regress X on Y). If the regression direction is correct, the residual should be independent of the cause variable, and this does not hold if the direction is incorrect under some mild assumptions (Hoyer al.) 2008). Thus the causal direction between X and Y is identifiable.
Given an SEM with its structural equation set S {S), S2...., Sa} that follows the assumptions of ANM as in Eq. ( we consider the structural equation S,, which describes the causal relation between the parent set pat() and V4. It can be rewritten as:
V; = f(((ea))) + N,
= V- fi(Vpa()) N₁ = 0, EV,, pa(i),, (aa());,a((i22.))) pa(i))....... pa.)).......p((i................ pa(i),, = 0, (3)
where pa(t); denotes the jthh parent of V4. Eq. 3 is defined as the equivalent implicit equation of S, Now we introduce the definition of the strength of identifiability.
2.3. Order-Search-basee Causal Discovery
It is well known that for CGM, there exists a causal order defined on the variable set V = {Vi, V/2 V2...,, Vaj. This order is a permutation of magnitude d that specifies the cause-effect relation: Only a preceding variable in the order can be the parent (cause) of a subsequent variable and not conversely. It is worth noting that there an intrinsic con- nection between orders and complete DAGs (also known as fully connected DAGs): for any order π. can construct complete DAG C*,, where each variable (i()) has directed edge connecting to all Va() with i < j, = 1, 2........ d. Besides, for a given DAG G. we define the true order set as:
Definition 3.1 (Strength of Identifiability) Given an SEM following the ANM assumptions, with its structural equation set S {SI..... Sz). we consider S; and its equivalent implicit equation in Eq. (3). If for every pa(i)) Vpa(t)- Fi cannot give an implicit function as:
pa()): = (a(K,,))))...... pa......ppaaaa......... pa0) pa(i),, N.),
where g(-) denotes a function from R +1a + I, that is, if such an implicit function does not exist for every pa(i)., then S; is defined as strongly identifiable. Oth- erwise, it is weakly identifiable. Moreover, if all S, E S are strongly identifiable, S is strongly identifiable; otherwise, S is weakly identifiable.
11 = { the complete DAG C" is a super-DAG of G):
where the term a super-DAG of G denotes a DAG that the edge set of G is subset of the edge set of this DAG. Evi- dently, the true order for any incomplete G is not necessarily unique, i.e., the magnitude of 11 is possibly greater than 1.
According to Definition 3.1 the strength of identifiability is determined by the existence of implicit function. If an implicit function for the parent variables does not ex- ist, the SEM can be identified through simple regression. Otherwise, we need to check the independence between the regression residual and the regressors. However, in practice, it is still challenging to distinguish between strong and weak
Order-based causal discovery is motivated by the following fact. If the causal order among the variables is known, the remaining task is simply variable selection, which can be handled by multivariate regression. Therefore, the problem
3

---

Strong and Weak Identifiability of Optimization-basee Causal Discovery in Non-lincar Additive Noise Models
identifiability because we often do not have access to the analytic expression of F. Therefore, we further provide sufficient condition for distinguishing between strong and weak identifiabilityy, which is related to the implicit function theorem (Rudin et al. 1976). Let x denote (#1, (2,.,,,.....2 Jn))
4. A Generic Approach to Strong and Weak Identifiability in ANM
In this section, we introduce GENE, method designed to address both strongly and weakly identifialle problems in a unified manner. Broadly, GENE operates in two phases: order search and parent search. The order search phase is further divided into order estimation and optimization. Next we give details of these steps and discuss how GENE effectively overcomes the limitations of existing methods.
Lemma 3.2 (Global Existence of Multivariate Implicit Function). Let F(21, ,n,.., be continuous on the set E = {1 (n,,,, E R=+1 a S I1, Tg...., In S b, 00000 < uy= < oo}. Suppose that the partial derivative function F2
exists for y) E E, and there exist positive con- stants < m < M s.l.
all (I1,
4.1. Causal Order Estimate
In this subsection we present the first step of GENE: estimat- ing causal orders. First, for any true order of G. there exists upper triangular representation of Eq. 2 (Bühlmann et al., 2014 Formally, given an order π,, the SEM equation of Eq. can be rewritten as:
m F2 (2 ................................ Fn , S M, V(I1, fn v) E,
then the equation F( (2,,,,,,...... ,2,...,, y) = 0 has a solution
y = ((1,, 42, Fnn which is continuous over [a,
Va(1)= = f((Ven(o) + 1,2,
(4)
Proof Sketch:
To prove the existence and uniqueness of
where V()(1) (V3 : xj) < (1)) refers to the variables preceding V; in the causal order To estimate such an order, the first aspect that we should consider is how well the preceding nodes in the order can be used to predict subsequent nodes, i.c.. the goodness of fit. This task can be handled using log- log-likelihood (consider fis and N,s as parameters, then apply maximum likelihood estimate), as in CAM (Bühlmann et al., 2014). In this paper, we propose to apply R metric of goodness of fit ranging from 0 to 1, to evaluate the quality of regression. More specifically, for each node (x))). we train a fully connected neural net- works (NN) with 2 hidden layers of size h, parameterized by (i) = {W!, W where W and W2 are the weight matrix. The NN takes (Va(1):--VV<
continuous solution y = -p(x) to the equation F(x, y) = O, we define an operator T on the space of continuous func- tions Cla. bj. By applying the Lagrange mean value the- orem (Rudin et al. 1976) and the assumptions on F, we show that T is a contraction mapping. The Banach fixed point theorem (Rudin et al. 1976) then guarantees the exis- tence of a unique fixed point T,, which corresponds to the solution (zx)). The complete proof is in Appendix B
With Lemma 3.2
we derive sufficient condition to deter- mine the strength of identifiability, as Theorem 3.3 below.
E Ri-1 as input to predict Vx())- other words, we use a NN to fit the potential function between Vz*(1) and V4, and the degree of fitness is evaluated by
Theorem 3.3 (Sufficient Condition for the Strength of Iden- tifiability). Given structural equation St and its equiva- lent implicit equation Fi(Vi, pa(i)),--..; "aahh.....---.;;;--. No) O, if there is pa(i) such that F; and pa(i); satisfy the con- dition for F and y in Lemma 3.2 St is weakty identifiabl..
(V =1 (SV((.(V<=())) V*G))
(5)
Var(Va(s)
Theorem
3.3 can be proved using Definition and Lemma 3.2 It indicates that a structural equation is weakly identifiable under mild condition on the partial derivatives of its equivalent implicit equation. Theorem 3.3 serves as an operational condition to determine the strength of iden- tifiability of a given structural equation. We refer to as "operationa" because this theorem only requires knowledge of the partial derivatives of the equation without needing analytic expression. It is worth noting that this condition is not necessary because the implicit function may exist even if the condition does not hold. For example, consider the equation F(I, y) = y² - I. At the point (z, y) = (0, 0), the partial derivative F,, = O. Consequently, the constant m does not exist. However, the equation F(x, y) = still has a solution, which obviously y = *p()) = V/.
where f denotes the approximated function, Var(V (V)) is the variance of Va(s) and MSE refers to the mean square error between the predictions and the true values of Vi(()-
It is worth noting that continoousooptimizztionn based meth- ods (details in Appendix A.2 perform differently after data rescaling (Reisach et al.) 202T 2023). whereas GENE is scale invariant. This because these methods encode the entire SEM into connectivity matrix and then minimize the overall MSE, implying that they are not not able to explicitly distinguish between cause and effect during optimization. Consequently, rescaling affects the MSE. In contrast, GENE controls the variance of the effect variable, as in R², and is therefore scale invariant.
4

---

Strong and Weak Identifiability of Optimization-basce based Causal Discovery in Non-lincar Additive Noise Models
For strongly identifiable SEMs, considering the goodness of fit in an order-based manner is sufficient for causal discov- ery. In contrast, for weakly identifiable problems, leveraging residual independence is necessary. Therefore, after training a neural network (NN) for variable Va(i), we calculate the residual by subtracting the predicted values from the true val- ues of Va(e) We then apply independence tests to determine whether the residual is independent of the input variables, V=(); (((i))
Consider starting with a random permutation (order) of magnitude d, denoted as x A straightforward approach is to apply operations (e.g., changing the position of some elements in x9) to modify X" and check if the fitness im- proves. If so, we save the modification and proceed to the next operation until no further improvement in fitness is possible. This process is known as greedy search in the optimization literature and is widely used in combinatorial optimization problems and causal discovery, such as Greedy Equivalence Search (GES) (Chickering) 2002). We define such an operation as follows:
which can be expressed as 1, where IT refers to the indepen- dence tests. If variables X and Y are independent, then P(X, Y = P(X)- P(Y). For the residual and V=() to be tested, we discretize them into m bins and calculate the contingency table. For the null hypothesis that the residual and Vi(s are independent, we apply the statistic x² to test it. The statistic x² is used to compute the p-value for the null hypothesis. We compare the p-value with the significance level of 0.05 to determine whether the residual is indepen- dent of V=))- The residual independence term discussed above is then added as a penalty term, yielding the final fitness function fi) for an order π as follows:
for j =
Definition 4.1 (Operation). Given permutation of magni- tude d, denoted as π = (TT,, T2, ... Ta), and two integers i, j. where i, = 1, 2, ..., d and i + j. A mapping maps π to à such that
(TT (TT...... Ti Te41, Ty. Ti, Tjth.......... ma); if j, (TI. (TI...., 1y
To. TT, Ti mi+t. Ta); if > j,
is defined as an operation OPij, i... = (T))
With the operations defined, the greedy search process can be described by Algorithm [ Appendix D We wonder how effective such a greedy optimization strategy is. Fortu- nately, Theorem 4.3 guarantees that, under mild assump- tion, this search process can always find the global optimum, i.e., a true order π E ITS, within finite number of steps.
lit(z)= = d
1 ; Σ R2 (Va(o) (1 (1-a) 3 IT (A(Vente) - Vato, Vacs)
(6)
where IT returns if the p-value is less than the significance level; otherwise, it returns 0. The hyper-parament to control the weight of the penalty term. The intuition be- hind this formula is straightforward: for each potential par- ent, if it is not independent of the residual, its contribution to predicting the regressor should be discounted. Generally speaking, this approach of combining the goodness of fit with residual independence is both neat and effective. For strongly identifiable SEMs, R²² is sensitive to the direction of regression (i.e., R differs significantly when regressing in the correct direction compared to the incorrect direction) and to the residual independence. In contrast, for weakly identifiable SEMs, the residual independence remains sensi- tive. Since in most cases it is unknown in advance whether a problem is strongly or weakly identifiable, GENE, as a generic approach, demonstrates its advantage over other methods that exploit only one of these aspects.
Before introducing the theorem, we define a metric to mea- sure the discrepancy between an order and the true causal order of DAG. Given an order IT and a DAG G, we define the degree of reversal for π w.r.t. G, denoted as Rev(G, Definition 4.2 (Degree of Reverse). Given DAG g (V, E') and a permutation π V. the degree of reverse for ı on G i.e., Rev(G, is defined as:
used
Rev(G,
[[V, v5) a path V; + Vj exist in 9 and V3 precedes V2 in T)|-
In other words, Rev x) is defined as the number of vari- able pairs that form path in G but are incorrectly ordered in म. Obviously, for any π E II Rev(g, T) = O. Further- more, for given DAG G, Rev can be used to measure the distance between an order π and its true order set IT The larger Rev(G, T). the less accurately π describes the causal order. With this definition, we present Theorem 4.3
In our implementation, the syper-paramette are set as fol- lows: hidden layer size h = 256, number of discretization bins m = 10, a = 1, and the significance level of the chi-square test is set to 0.05.
Theorem 4.3 (Global Optimality of Greedy Order Search). Given an order fitness evaluation function fit and a sam- ple matrix D sampled from the DAG G. if for any or- ders कi and T2 with Rev mi) < Rev(G, T2), we have fit(D, TI) >> fit(D, T2), then starting from any initial order To and greedily applying operations until the fitness value cannot increase (as in Algorithmm 1), the final order Tt" will
4.2. Greedy Order Search
We now have the fitness function for a given order n. In this subsection, we describe how to search for the order with the highest fitness.
be in ITC
5

---

Strong and Weak Identifiability of Optimization- Causal Discovery in Non-lincar Additive Noise Models
Crusal Order Estimate
Greedy Order Search
Pruning
Vz(i-1)- The above process is depicted in Algorithm 2 Appendix
in
Goodreus
The overall framework of the least pruning is simple yet effective. There are mainly two points: How to evaluate the parent with least after- frtting effect and how to determine whether prune it or not. In this implementation we use the difference in R² before and after a pruning to measure its influence. The insight is that a variable with the least difference is with the least possibility to be the parent.
Indeoendence
Figure 2. An overview of GENE. Cireles with different colors
stand for different variables.
Proof Sketch: To prove Theorem 4.3 we demonstrate that for any order with non-zero Rev, there exists an operation that can improve its f't.. We find pair of variables (Vi, V2) such that path V2 + Vj exists in G and Vj precedes Vi in R. If V, and Vj are adjacent in ft moving Vú in front of Vj decreases Rev and increases fil. If they are not adjacent, we consider two cases: (1) if variables between V, and Vi do not form a path to V3 in G. the same operation decreases Rev; (2) if a variable Vú forms a path Vi - V,, path V - V must exist due to the definition of a path in DAG. We recursively consider the pair (V,, Vÿ) until the variables are adjacent or case (I) holds. Thus, operation exists to increase fit, and the greedy search will find '² with Rev(g, x² = 0. The complete proof is in Appendix C
Based on the above aspects, we show the process of GENE in Figure 2 In the next section, we present experimental results on both synthetic datasets and real-world application.
5. Experiments
In this section, present experimental results of perfor- mance comparison between GENE and several algorithms on synthetic datasets as well as real-world application.
The baselines are chosen from different categories of methods: continuous cutiinouss-ppiimzzatoo---sssssss clude Notears-MLP (Zheng et al. 2020 and Gran- DAG (Lachapelle al. 2020). For combinatorial- optimization-basee methods in DAG space, we choose SELF (Cai et al. 2018). GSF (Huang et al. (018) (Chick) ering 2002), and PC-ANM, which respectively represent score-hased and hybrid methods (pure constraint- methods are not included since they can only output graphs with undirected edges). For order-based based methods, 2023) CAM (Bühlmann al.) 2014)). R2Sort (Reisach et al.
methods in-
Theorem 4.3 provides a theoretical guarantee for the global optimality of the greedy order search. Namely, it can always find the true order under mild assumptions.
4.3. Least Pruning
RESIT (Peters al., 2014).
CaPS (Xu al.) 2024) and
After the above two two steps, we get a causal order. The remain- ing task is select appropriate parents for each variable, which is essentially variable selection problem. If we assume an additive SEM, this can be handled by Group LASSO (Ravikumar et al. 2007) or its improved version with sparsity-smoothness penalty (Meier et al. 2009). How- ever, ANM is not additive since here additive means the effect of each parent is additive, but not additive noise. To this end, we propose a pruning strategy named least pruning which applies parent pruning to deal with such a parent selection issue. The intuition is: Starting from the given order, we construct its corresponding complete DAG, and then for each variable we try to prune one parent with least -etrr-p effect. More specifically, for variable Vx(i)- we first calculate its fully connected Rt, i.e., all the vari- ables preceding V=(s) x. denoted as the set {< Vi(1)} are used as input of NN. After that we try to prune each V in {< Va(a) } and caleulate R² respectively, the variable with highest after-pruning R²2 are called candidate since pruning it casts least effect to the overall R²2. We measure whether the decline of R² caused by pruning the candidate is less than a threshold, if so, prune this candidate and find the next one or else stop pruning for Vx(i) and start to prune
NHTS (Hiremath et al. 2024 are included.
For evaluation, we choose Fl Score and SHD (Structural Hamming Distance) as metrics. The F1 Score ranges from 0 to I and provides an intuitive and comprehensive assessment of the prediction quality, while the SHD is an integer that indicates the number of missing and unexpected edges. All conducted
computer equipped with an AMD Ryzen 5 3600 6-Core processor, 16 GB of RAM, and a 512 GB SSD. The operating system was Windows 11, 64-bit. All computational analyses were performed using Python 3.8. This setup provided robust environment for running the extensive simulations and data processing required for the study (note that our experiments do not necessarily require GPU).
the experiments
The codes and datasets involved in our experiments are avail- able at /nttps://giitine www.:ttw....c.cceeeaeeeeeeee Btt..//ooooOOOOOOOO/GGGGEAE ILOG/GENE
5.1. On Synthetic Datasets
To study the performance of our proposed GENE for prob- lems with different features, we follow the popular exper- iment pipeline in the causal discovery community, which
6

---

Strong and Weak Identifiability of Optimization- based Causal Discovery in Non-linear Additive Noise Models
Notears-MLP
Gran-DAG
CAM
RESIT
PC-ANM
R25ort
CaPS
NHTS
(a.1) MIM (d-10)
(a.2) MIM (d-20)
(a.3) MLP (d-10)
(a.4) MLPP (d-20)
(a.5) GP (d-10)
[a.6) GP (0)
0.5
F1 5core
0.4
0.4-
0.4
0.2
02-
0.2
0/-
0.2
0.0
0.0
0.0
0.0
0.0
(b.1) MIM (d-10)
(b.2) (d-20)
(b.3) MLP (d-10)
(b.4) MLP (d=20)
(b.5) GP (d-10)
(b.6) (d-20)
30-
80
30-
60-
30
SHD
20
20
40
20-
10-
Graph Density
Graph Density
Graph Density
Graph Density
Graph Density
Graph Density
Figure 3. Effectiveness of the compared methods. The higher Fl the better, the lower SHD the better.
randomly generates DAGS and samples from them. We then attempt to infer the underlying DAG from the sampled data.
1. I. EFFECTIVENESS
The performance measured by FI Score and SHD is given in Figure B If curve for particular baseline is missing in a graph, it indicates that the method is unable to produce results within 2 hours under the corresponding setting. From the figure, we observe that for F1 Score (shown in the upper part), GENE has advantages over other methods in terms of both F1 Score and stability to problem density in MIM and GP when d = 10, and in MIM when d = 20. However, in MLP, Notears-MLP achieves higher F1 Score. This can be explained by information leakage, as discussed before, where its performance varies significantly after standardiza- tion. Related experiments are discussed later. The results of the performance estimated by SHD are shown in the lower part of Figure 3 From the figure, we observe that in (b. and (b.5), GENE achieves superior performance compared to other methods. In (b.2) and (b.4), GENE is only outper- formed by Notears-MLP, whose performance is unreliable (as it drops significantly after standardization, which we will demonstrate later).
We evaluate the compared methods and GENE with the assumption of ANM, whose SEM is of the form Eq. (2). Specifically,, we generate samples according to the fol- lowing configurations: The graph sampling scheme is Erdös Rényi (ER), the number of nodes d = {10, 20). the density of the graph (the number of edges divided by the number of nodes) density- {1, 2, 4), the sample size 3000, the non-linear function f has 3 forms: trigono- metric function, randomized Gaussian process (GP) and randomized NN denoted as MIM, GP and MLP respectively, where MIM and GP are considered as strongly identifiable and MLP is weakly identifiable. They are given as
MIM: V- = tan(Vnnnnaaa (Va(t)) Wi) + sin(Vpa(t) W2)+
cos(/))()) W3) +c.N,
MLP: V, =Sigmoid(VVin Vpa(t) W1) W2 c NN,
It is worth noting that methods relying solely on good- ness of fit, namely CAM, Notears-MLP, R2Sort, CaPS, and NHTS, demonstrate universally and significantly better per- formance on strongly identifiable problems (GP and MIM) compared weakly identifiable problems (MLP). This phe- nomenon further support the meaningfulness of the division between strong and weak identifiability. Besides, Figure suggests the performance of GENE and CAM is very close, even in weakly identifiable cases. To address this point, we conduct an ablation experiment comparing only the quality of orders given by order-based methods in Section 5.1.5] From this, it is clear that the quality of orders given by GENE far exceeds that of CAM and RESIT. Therefore, we infer that the closeness of Fl Score and SHD is due to differences in pruning.
GP: Vi =GP((Vpa()) No. c.
where W are random weight matrix in which the weights are calculated by w = + where & is uniformly distributed in range( 1, 1) and the sign is evenly divided, cis the noise coefficient which set to I and N; ~ N(O, 1).
All in all, there are 2 x 3 3- = 18 settings in total, for each setting we generate 10 different graphs and sample from them, so we get 10 sample matrix (10 problems) for each setting. All the results for one setting shown below are aver- aged over 10 times independent repetition on each of these 10 problems. The data generation process are implemented using the geastle python toolkit (Zhang et al. 2021).
7

---

Strong and Weak Identifiability of Optimization-base Causal Discovery in Non-lincar Additive Noise Models
5.1.2. STANDARDIZATION
With resiual independente term
Without reddual independence term
This part serves supplement the effectiveness anal- ysis discussed above. As discussed above, continuous- optimization-basse methods are sensitive to data scaling. (Reisach et al., 2021) show this for the linear case, and we extend their results to the non-linear case.
E Score (d=10)
6.-
24-
Specifically, for problems with d = 10 and density = 2, we standardize the sample matrix (i.e., each variable is sub- tracted by its mean and divided by its standard deviation) to examine whether the performance of the ahove methods is influenced. The results are shown in Figure 4 From the figure, we observe that continuous-opioe optimization- based methods, namely Notears-MI.P and Gran-DAG, are greatly affected by standardization, while others remain largely unaffected. This observation aligns with our expectations. Moreover, for strongly identifiable problems, the average F1 Score decline ratio is 34% while for weakly identifiable problems, this number is 52%. This suggests that standard- ization has larger impact on weakly identifiable problems for continouu-oppimiiztionnn based methods.
6.
F1 Scooe (d=20)
c.-
6.4
62
GP
Figure 5. The Fl Score before and after removing the residual independence term GENE, = (10, 20), density =
we try to only exploit the goodness of and ignore the resid- ual independence in order estimation, more specifically, we use (it = Σi= R²2 (Va(e) in place of Eq. (6) and keep other settings the same. From the results we can tell that for strongly identifiable problems (GP, MIM), the per- formance is not influenced (results are even slightly better for GP and MIM in 10-node case while for MLP, which is considered weakly identifiable, the performance drops significantly. This phenomenon supports the discussions about the strength of identifiability.
5.1.3. EFFICIENCY
To study the efficiency of the compared methods, we report the average after standardization F1 Score vs. wall-clock execution time in two-objective Pareto graphs problems with d 10 and d 20, as shown in Figure g in Ap- pendix F. The result suggests that GENE is on the Pareto front of effectiveness and efficiency, i.e., nondominated by other methods w.r.t. these two objectives.
5.1.4. ABLATION STUDY
5.1.5. EFFECTIVENESS OF ORDER SEARCH
Figure 5 shows the result of the ablation study for GENE where consider the case density 2. In this experiment,
The performance of order-search-baste based methods (namely CAM, RESIT, CaPS, NHTS and GENE) not only af- fected by the quality of obtained order, but also by the parent search (pruning) process. Thus to study the effectiveness of order search, i.e., only consider the quality of orders ob- tained by these methods, we drop the pruning process and only compare the ability to search for correct causal orders of these methods, which can be evaluated by the degree of reverse Rev (defined in Section 4.2 of the found order. Specifically, we conduct experiments for order-search-bbased methods on problems with the graph sampling scheme ER, the number of nodes d = 10 and density = {1, 2). the sample size n = 3000 and the non-linear form MIM, GP and MLP. and the output an order rather than a DAG, for which we calculate its degree of reverse Rev in Eq. The result is shown in Figure
Or Oinanal data
08
0.6
08
66
60
From Figure 6 we can see it more clearly about the power of Eq. (6): In (b) which is considered as weakly identifi- able, GENE performs apparently better than other compared methods (its Rev is almost a half of that of CAM and a quar- ter of RESIT) and in (a) and (c) which are considered as
MLP
DAG
AN8
Figure The Score before and after data standardization different causal discovery methods when d = 10, density = 2, The error bars show the standard deviation.
8

---

Strong and Weak Identifiability of Optimization- Causal Discovery in Non-lincar Additive Noise Models
(m) MIM (d=10)
(b) MLP (d=10)
(c) GP (d=10)
28
32-
Table 1. Results Sachs (bold means the best).
24-
20
24
28
28-
20
CAM
GENE
Method
Fl Score
SHD
12
16
12
16
R2Sort
RESIT
GENE
0.65
11
8-
CaPS
Notears-MLP
0.24
19
4-
NHTS
Gran-DAG
0.33
16
1 2
2
2
CAM
0.38
16
Graph Density
RESIT
0.15
23
Figure The average degree reverse for output order by GENE, CAM and RESIT. (a) MIM with d= 10. (b) MI.P with d 10. (c) GP with 10. The lower Rev the better.
PC-ANM
0.1
18
GSF
0.23
20
R2Sort
0.35
CaPS
0.07
17
NHTS
0.17
19
strongly identifiable, GENE can find orders with Rev nearly equals to that means the order found by GENE is very close to the true order. It worth noting that even in strongly identifiable case ((a) and (c)), GENE performs better than CAM especially when density = 4, it means that even for strongly identifiable problems the residual independence term also provide some help to find the true order, this is what we do not expected before.
The results are shown in Table 1 From which, GENE re- markably outperforms other methods on both Fl Score and SHD. The comparison between the causal graphs discovered by GENE and the ground truth is in Figure
For more experimental results and analysis, including the re- sults of efficiency and analysis of slyee-paramette influence, please refer to Appendix F In the next subsection, we will verify how the proposed GENE performs in a real-world application with bioinformatics background.
PKC
Plcg
Comnet Föge
P38
PKA
PIP3
Mieting Cóges
Raf
PIP2
Jnk
5.2. On Real-World Application
Uniqaated
Causal discovery has significant and far-reaching applica- tions in causal protein signaling networks (Sachs et al.] 2005). Pathways in protein signaling networks can be sim- ply understood as a series of pathways through which molecular signals are transmitted from outside the cell through the cell membrane to the inside of the cell to produce an effect. The various biochemical reaction pathways that perform different functions in the cell are composed of a series of different proteins, and the regulation of the activation or inhibition state of different proteins is mainly achieved by adding or removing phos- phate groups. The above problems can be solved with the idea of causal graphical models (Sachs al. 2005), which illustrates the causal relations between the components of the pathway in the form of DAG-represented causal graph.
Mek
Erk
Akt
Rovered
Edga
reaction
Figure 7. The protein signaling graph discovered by GENE.
6. Conclusion & Discussion
This paper focuses on the additive noise causal discovery problems and proposes to divide identifiability into strong and weak ones. The existence of implicit functions making large difference on the difficulty of a causal discovery problem, and the existing methods mainly perform well on causal models with strong identifiability. We show that this failure is due to the ignorance of residual independence. Based on this observation, we propose GENE, a unified and generic approach for both the strong and the weak ones. GENE takes the residual independence into account and thus is able to deal with both types of problems.
We consider a popular causal protein signaling network dataset in causal discovery community named Sachs (Sachs al. 2005). Sachs contains 7466 observational and inter- ventional samples of a protein signaling network based on expression levels of proteins and phospholipids. The ground truth causal graph is labeled by domain experts and it has 1l nodes and 17 edges (Sachs et al. 2005). Sachs is widely used in the community of causal discovery, and it is chal- lenging for the most causal discovery methods. Herein, we use the 853 observational data to conduct causal discovery.
For the future work, the performance of pruning strategy in GENE can be further enhanced. Besides, the strength of identifiability can be considered and generalized under other assumptions and scenarios, e.g., the post-nonlinear case.

---

Strong and Weak Identifiability of Optimization-basc Causal Discovery in Non-lincar Additive Noise Models
Acknowledgements
Hiremath, S., Maasch, J. R. M. A., Gao, M., Ghosal, P., and Gan, K. Hybrid top-down global causal discovery with local search for linear and nonlinear additive noise models. In Advances in Neural Information Processing Systems 38, pp. 133147-133179, Vancouver, Canada, 2024.
The authors would like to express the sincere thanks to the anonymous reviewers for their constructive comments and suggestions. This work supported by the National Natural Science Foundation of China (No. 62476091) and National Postdoctoral Program for Innovative Talent (BX20240162).
Hoyer, P. O., Janzing, D., Mooij. J. M., Peters, J., and Schölkopf, B. Nonlinear causal discovery with additive noise models. In Proceedings of the 22nd Conference on Neural Information Processing Systems, pp. 689-696, Vancouver, Canada, 2008
Impact Statement
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Huang, B., Zhang, K., Lin, Y., Schölkopf, B., and Gly- mour, C. Generalized score functions for causal discov- ery. In Proceedings of the 24th International Conference on Knowledge Discovery & Data Mining, pp. 1551-1560, London, UK, 2018.
References
Bhattacharya, R., Nagarajan, T., Malinsky, D., and Shpitser, I. Differentiable causal discovery under unmeasured con- founding. In Proceedings of the 24th International Con- ference on Artificial Intelligence and Statistics, volume 130, pp. 23 2314-2322. virtual, 2021.
Lachapelle, S., Brouillard, P., Deleu, T., and Lacoste-Julien S. Gradient-based neural DAG learning. In Proceedings of the Sth International Conference on Learning Repre- sentations, Addis Ababa, Ethiopia, 2020.
Brouillard, P., Lachapelle, S., Lacoste, A., Lacoste-Julien, S., and Drouin, A. Differentiable causal discovery from interventional data. In Proceedings of the 33rd Con- ference on Neural Information Processing Systems, pp. 21865-21877, virtual, 2020.
Lee, H., Danieletto, M., Miotto, R., Cherng, S. T., and Dud- ley, J. T. Scaling structural learning with NO-BEARS to infer causal transcriptome networks. In Pacific Sym- posium on Biocomputing, pp. 391-402, Hawaii, USA, 2020.
Bühlmann, P., Peters, J., and Ernest, J. Cam: Causal additive models, high- nigh-dimensional order search and penalized regression. The Annals of Statistics, 22(6):2526-2556 2014.
Li, M., Liu, S., Qian, H., and Zhou, A. A simple yet scalable granger causal structural learning approach for topologi- cal event sequences. In Advances in Neural Information Processing Systems 38, pp. 97124-97144 Vancouver, Canada, 2024.
Cai, R., Zhang, Z., and Hao, Z. SADA: A general framework to support robust causation discovery. In Proceedings of the 30th International Conference on Machine Learning, pp. 208-216. Atlanta, Georgia, 2013.
Liu, Y., Cai, R., Chen, W., Qiao, J., Yan, Y., Li, 7.,, Zhang, K., and Hao, Z. Tnpar: Topological neural poisson auto-regressive model for learning granger causal struc- ture from event sequences. In Proceedings of the 38th AAAI Conference Artificial Intelligence, volume 38, pp. 20491-20499, 2024.
Cai, R., Zhang, Z., Hao, Z., and Winslett, M. Understanding social causalities behind human action sequences. IEEE Transactions on Neural Networks and Learning Systems, (8(8):1801-1811 2017.
2017
Cai, R., Qiao, J., Zhang, Z., and Hao, Z. SELF: structural equational likelihood framework for causal discovery, In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 1787-1794, New Orleans, Louisiana, 2018.
Meier, I.., Van de Geer, S., and Bühlmann, P. High- dimensional additive modeling. The Annals of Statistics. 37 2009.
Ng. I., Ghassami, A., and Zhang, K. On the role of sparsity and DAG constraints for learning linear dags. In Pro- ceedings of the 33rd Conference on Neural Information Processing Systems, virtual, 2020.
Chickering, D. M. A transformational characterization of equivalent bayesian network structures. In Proceedings of the 1 Ith Conference on Uncertainty in Artificial Intel-
ligence, pp. 87-98, Montreal, Canada, 1995.
Chickering, D. M. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3: 507-554, 2002.
Ni, H., Wang, T., Tao, H., Huang, X., and Hou, C. Gradient- based causal discovery with latent variables. Machine Learning, 11((2)46,, 2025.
10

---

Strong and Weak Identifiability of Optimization-base Causal Discovery in Non-linear Additive Noise Models
Pamfil, R., Sriwattanaworachai, N., Desai, S., Pilgerstor- fer, P., Georgatzis, K., Beaumont, P., and Aragam, B. DYNOTEARS: structure learning from time-series data. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statisties, volume 108, pp. 1595-1605, Palermo, Italy, 2020.
Schochet, P. Z. Estimators for clustered education rets using the neyman model for causal inference. Journal of Educational and Behavioral Statistics, 38(3):21-2238, 2013.
Shimizu, S., Hoyer, P. O., Hyvärinen, A., and Kerminen, A. J. A linear non-Gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7: 2003 2030, 2006.
Pearl, J. Causality, Cambridge university press, 2009.
Peters, J., Mooij, J. M., Janzing, D., and Schölkopf, B. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 15(1):0009-2553, 2014.
Spirtes, P., Glymour, C., and Scheines, R. Causation, Predic- tion, and Search (Second Edition). Adaptive computation and machine learning. MIT Press, 2000.
Ravikumar, P., Liu, H., Lafferty, D., and Wasserman, L. A. Spam: Sparse additive models. In Proceedings of the 21 Conference on Neural Information Processing Systems, pp. 1201-1208, Vancouver, Canada, 2007.
Teyssier, M. and Koller, D. Ordering-based search: A simple and effective algorithm for learning bayesian networks. In Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, pp. 548 248-549, Edinburgh, Scotland, 2005.
Reisach, A. G., Seiler, C., and Weichwald, S. Beware of the simulated dag! causal discovery benchmarks may easy to game. In Proceedings of the 34th Conference on Neural Information Processing Systems, pp. 3895-3906, virtual, 2021.
Verma, T. and Pearl, J. Equivalence and synthesis of causal models. In Proceedings of the 6th Conference on Uncer- tainty in Artificial Intelligence, pp. 255-270, Cambridge, Massachusetts, 1990.
Vowels, M. J., Camgöz, N. C., and Bowden, R. D'ya like dags? A survey on structure learning and causal discovery. arXiv, abs/2103.02253
Reisach, A. G., Tami, M., Seiler, C., Chambaz, A., and Weichwald, S. A icale-invariant sorting criterion to find causal order in additive noise models. In Advances in the Annual Conference on Neural Information Processing Systems 36, New Orleans, LA, 2023.
2021.
Wang, T.-Z., Qin, T., and Zhou, Z.-H. Sound and complete causal identification with latent variables given local back- ground knowledge. Artificial Intelligence, 322:103964, 2023.
Rolland, P., Cevher, V., Kleindessner, M., Russell, C., Janz- ing, D., Schölkopf, B., and Locatello, F. Score match- ing enables causal discovery of nonlinear additive noise models. In Proceedings of the 39th International Confer- ence on Machine Learning, pp. 18741-18753 Baltimore, Maryland, 2022.
Wang. T.-.., Du, W.-B., and Zhou, Z. An efficient maxi- mal ancestral graph listing algorithm. In Proceedings of the 41st International Conference on Machine Learning. pp. 50353-50378 Vienna, Austria, 2024.
Rudin, W. et al. Principles of mathematical analysis, vol- ume 3. McGraw-hill New York, 1976.
Wei, D., Gao, T., and Yu, Y. Dags with no fears: A closer look at continuous optimization for learning bayesian networks. In Proceedings of the 33rd Conference on Neural Information Processing Systems, pp. 3895-3906. virtual, 2020.
Sachs, K., Perez, O., Pe'er, D., Lauffenburger, D. A., and protein-signaling
Nolan, G. P. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 308(5721); 523 529, 2005.
Xu, Z., Li, Y., Liu, C., and Gui, N. Ordering- based causal discovery for linear and nonlinear relations. In Advances in Neural Information Processing Systems 38, pp. 4315 4340, Vancouver, Canada, 2024.
Sanchez, P., Liu, X., O'Neil, A. Q., and Tsaftaris, S. A. Diffusion models for causal discovery via topological ordering. In Proceedings of the 11th International Con- ference on Learning Representations, Kigali, Rwanda, 2023.
Yu, Y., Chen, J., Gao, T., and Yu, M. DAG-GNN: DAG struc- ture learning with graph neural networks. In Proceedings of the 36th International Conference on Machine Learn- ing, volume 97, pp. 7154-7163, Long Beach, California, 2019.
Schmidt, M., Niculescu-Mizil, A., and Murphy, K. P. Learn- ing graphical model structure using 11 -e-reuularization paths. In Proceedings of the 22nd AAAI Conference on Ar- tificial Intelligence, pp. 1278 1283, Vancouver, Canada, 2007.
Zhang, K. and Hyvärimen, A. On the identifiability of the post-nonlinear causal model. In Proceedings of the 25th

---

Strong and Weak Identifiability of Optimization-based Causal Discovery in Non-lincar Additive Noise Models
Conference on Uncertainty in Artificial Intelligence, pp. 647-655, Montreal, Canada, 2009.
Zhang, K., Peters, J., Janzing, D., and Schölkopf, B. Kemel- based conditional independence test and application in causal discovery. In Proceedings of the 27th Conference in Uncertainty in Artificial Intelligence, pp- 804-813, Barcelona, Spain, 2011.
Zhang. K., Zhu, S., Kalander, M., Ng, I,, Ye, J., Chen, Z., and Pan, L. geastle: A python toolbox for causal discovery, 2021.
Zheng, X., Aragam, B., Ravikumar, P., and Xing, E. Dags with NO TEARS: continuous optimization for structure learning. In Proceedings of 31st Conference on Neural In- formation Processing Systems, pp. 9492-9503, Montreal, Canada, 2018.
Zheng, X., Dan, C., Aragam, B., Ravikumar, P., and Xing, E. Learning sparse nonparametric dags. In Proceed- ings of the 23rd International Conference on Artificial Intelligence and Statistics, pp. 3414-34444 3425, Palermo, Italy, 2020.
12

---

Strong and Weak Identifiability of Optimization- Causal Discovery in Non-lincar Additive Noise Models
Appendix
as an optimization problem and do not explicitly discuss the identifiability of the output graph. Besides, due the use of gradient-free optimization to search for structures across the entire DAG space, score-based methods often have significant efficiency shortcomings.
A. Detailed Related Work
From the perspective of optimization, the existing causal discovery methods can be divided into two types: combinatoral-optiiizaton--- based methods and continuous- optimization-basel methods. The task of causal discovery is naturally a combinatorial optimization problem since the search space of DAG is discrete. However, Zheng et al. (2018) present another possibility for causal diseovery. They reformulate the problem continuous space via transform- ing the discrete objective function and constraint into con- tinuous and differentiable ones. In this section, we briefly introduce these two classes of causal discovery methods respectively.
The hybrid methods first apply constraint- methods to identify the V-structure. The remaining undirected edges are seen as cause-effect pairs and the direction is deter- mined following those identifiability results such as ANM aforementioned in the introduction (details will be intro- duced in Section 2.2). Representative algorithms include PC-ANM (Hoyer et al.) 2008), scalable causation discov- ery algorithm (SADA) (Cai et al. 2013). However, due to the aforementioned drawbacks of conditional indepen- dence tests, especially kerne--baeed independence tests for non-linear problems, the performance of constraint- based methods is not stable, which indeed infects the effectiveness of hybrid methods.
A.1. CombinatorrallOppiiiiztttoooool Methods
The combinatooialloopiiizzzoo based methods address the causal discovery problem via searching for graph repre- sented by a connectivity matrix in the DAG space. They can be further classified by its search space, i.e., the DAG space and the order space. For methods searching in the DAG space, there are three categories: constraint-based, score-based and hybrid methods.
Except for searching in a DAG space, an alternative is searching in an order space. The proposed GENE belongs to this class. In the sedde--earch-based non-linear causal discovery, representative algorithms include causal additive model (CAM) (Bühlmann et al. 2014), regression with sub- sequent independence test algorithm (RESIT) (Peters et al., 2014), causal discovery with parent score (CaPS) (Xu et al.
Constraint- based methods apply independent tests and con- ditional independence tests to infer the independence prop- erty between variables. Particularly, when considering non- linear problems, kernel-based independence tests are of- ten applied, such as (Zhang et al., 201T). Representative constraint-basee algorithms include Peter-Clark algorithm (PC) (Spirtes et al.) 2000), inductive causation algorithm (IC) (Verma & Pearl 1990). The main drawback of this kind of methods is that they cannot identify graphs in the same MEC, and thus there may exist undirected edges in the output graph. Besides, constraint-based methods also suf- fer from a series of problems of conditional independence tests including conflict handing, sample inefficiency, and hyper-parameter sensitivity, etc.
2024 and causal discovery for non-linear ANMs with local
ancestor deecedordescenneett relationships (NHTS) (Hiremath et al. 2024).
On the one hand, CAM applies a log-likelihood-based mea- surement which captures the goodness of fit to estimate order. With such measurement, CAM just greedily adds edges to maximize this log- until getting a complete directed graph, which yields an order as the result. NHTS (Hiremath et al. 2024) propose a hybrid ap- proach that first establishes a top-down hierarchical ordering leveraging ancestral relationships, applicable to both linear and nonlinear additive noise models, and subsequently em- ploys a nonparametric search for pruning spurious edges. Similarly. CaPS (Xu) et al. 2024 is presented as an ordering- algorithm specifically designed to handle a mixture of linear and non- linear relations. CaPS introduces a novel identification cri- terion for topological ordering and incorporates parent score, quantifying the strength of average causal effects, to optimize its pruning stage. Unfortunately, these methods only consider the goodness of fit, and thus they can only handle strongly identifiable problems.
munstraint-based algorithm with local
The second category is score-based methods, which first define a score function using to evaluate the fitness degree of the input DAG and the observational data. For non- linear causal discovery task, the generalized score function (GSF) (Huang et al. 2018) and the structural equational like- lihood framework (SELF) (Cai et al., 2018) are proposed. SELF takes the both two aspects into account. However, SELF does not discuss the relationships between the two aspects and identifiability. After defining the score func- tion, score-based methods then conduct a searching process to find the DAG that maximizes the score. The popular search strategies include hill climbing (HC), greedy equiva- Ience search (GES) (Chickering, 2002). The defect of this kind of methods is that they formulate the whole problem
On the other hand, RESIT considers the problem from an- other perspective. For each node V,, the corresponding noise term N is independent from all non-descendants of V4. Thus for the leaf node Vieaf. its noise Neef is inde- pendent of all other variables. Based on the above obser-
13

---

Strong and Weak Identifiability of Optimization-base Causal Discovery in Non-linear Additive Noise Models
vation, RESIT proposes to iteratively pick one node with least dependency between other variables and its residual regressing on all other variables. This process undoubtedly yields an order (from leaf to root). This leaf-node- based order search method is also applied by recently proposed score matching causal discovery algorithms (Rolland et al. 2022, Sanchez et al. 2023). However, RESIT does not work well for strongly identifiable problems since it ignores the information from the goodness of fit.
B. Proof of Lemma 3.2
Proof. Consider T: Cla, 6)" + Cla, defined by
1
(Tz)(x) pp(x) M
F pox)),
forall E [a, and y E Cla,
T is a contraction on Cla, b|mh since
((T)))(x) (T+))(z))
The existing order-search-based based approaches only consider one of the two aspects to estimate the causal order, and both of them have limitations. This motivates the work in this paper, ie., unifying these two aspects under one framework and proposing a generic method for both strongly and weakly identifiable problems.
= 122(z)) - 1 F(x, (((x)) - pi(x)) + + ((x
(1 t (2, pi(()) + (()((2) -
(12((x) - (z)))
$ (1 - x p2(z) - وم (z)
A.2. Continuous-Optiiizzatonnn
Methods
where the second equation holds because of the Lagrange mean value theorem (Rudin et al. 1976). The fact that T is a contraction implies
Unlike combinatorial methods which solve the problem in discrete spaces, Zheng et al.) (2018) propose to con- duct causal discovery via optimizing mean square error (MSE) based loss function subject to an equivalent continu- ous acyclicity constraint. This idea achieves a remarkable performance on popular benchmarks and many successful extensions have been proposed including (Lachapelle et al.
dis dis, S a dis(p2,.11).
where dis is a metric on space Cla, 6)" and a E (0, Hence, by the Banach fixed point theorem (Rudin) et al. 1976). there exists a unique yo E Cla, 6)" that 0 on bj", and the lemma holds.
2020
[Bhattacharya et al.) 202T Pamfil et al. 2020 Yu
Flx az) (()))
al.
2019
Brouillard et al. 2020 Ng et al. 2020 Wei
ett al.
2020
Lee et al. 2020 Zheng et al. (020). Vow-
els et al. (2021) provide comprehensive review of these methods.
C. Proof of Theorem
continuousoopiimiiztoonnooo
Proof. Theorem 4.3 states that, under the assumption that if an order is with lower Rev, it is with higher fit, then greedy order search procedure will result in correct causal order. To prove this, it is equivalent prove the following statement. For any with non-zero Rev, there exist some operations can increase its fit. If this statement holds, obviously the greedy search will finally find x with Rev x*) = 0, i.e., n² E ITS. Without loss of generality, we consider a â that Rev(G, +) > O. From the definition of Rev, we can at least find pair of variables (V,, V/)) such that path V, + V, exists in G and Vj precedes V, in a. If there are no variables between V; and Vj. i.e., they adjacent in A, then the operation that moves V; in front of Vj can make Rev minus 1 and fit increases. This means that such an operation exists, and thus the statement holds.
However, Reisach et al. (2021) point out that these citiiuuus-oopimizzaionn based methods may exploit infor- mation inadvertently leaked by the data generating process to achieve such extraordinary performance. |Reisach al. (2021) show that under the linear model with additive noise case, the performance of hotpruuoouo-piiiizttoo-bbbao methods drop significantly after data rescaling, i.e., chang- ing the units of measurement for variables (e.g., multiply- ing 1000 from kilometer to meter) or data standardization. This result also holds under non-linear settings (Reisach et al., 2023), which is also shown in our experiment sec- tion. Apparently the existence of causal relationships should not depend on the scale of data. This phenomenon is be- cause these coatinuuuuu-ptimizttinii based methods treat the DAG connectivity matrix as a whole during optimiza- tion, which means that they do not explicitly distinguish between the cause variables and the effect variable. How- ever, in GENE the cause variables and the effect variable are clear when conducting regression. Hence GENE is scale invariant. Besides, these methods are also lack of discussion about identifiability.
Else if Vú and V3 are not adjacent in म,, we still consider the above operation, i.c., moving VÚ in front of V,. Now there are two cases. For the first case, if all variables between Vi and V; do not form path to V; in G. then such an operation still makes Rev minus 1. For the second case, if there exists a variable V, forming a path Vn2 + V2 in G. then such an operation no longer decreases Rev since it introduces a new pair (V, Vi) which is reversed after the operation. However, from the definition of path in DAG, we know that if path
14

---

Strong and Weak Identifiability of Optimization- Causal Discovery in Non-lincar Additive Noise Models
V V and another path V + Vi both exist, then path Vi V exists. So we can consider the pair (Vi, V2) just like considering the pair (V,, Vÿ) before. This is a recursive process until we find that the pair of variables are adjacent in á or the pair of variables are not adjacent but variables between them do not form path to the latter one (as the first
Algorithm 2 Least Pruning
Input: the sample matrix D E Rendd an order n, and a threshold 0
G 0
for -ori=11 d do
3:
the parent set Pa <- Vea(()
case). Therefore the operation exists under both of two circumstances, and the theorem holds.
4: regress Va(a) over V<=(i) and calculate It, fit +
R²
while Pa > do
D. Greedy Order Search
for j = + do remove ViO) from Pa and calculate R2. end for find the parent Vieast with the least fit R
The pseudocode of the greedy search algorithm described in the main text 'Greedy Order Search' section shown in Algorithm D
10:
if fil Reasst < 0 then
11:
prune it, Pa t- Pa \ (alleast) fit <- fit 1
Algorithm 1 Greedy Search for Order
Input:
the sample matrix I= the fitness evaluation
12:
else
function fit.
13:
break While
I:
initialize the current best order x² RRandom Order, the best fitness value fe <- fit((D, x ).a Boolean value continue & Truee
14:
end if
15:
end while
16: for each parent left in Pa, add edge V42 to g
2: while continue = True do
17:
end for
3: continue + False
18: Output: the causal graph G
4: for + d do
5: for j 1 j i- f do
6:
#* (T*) if (Di A²) " bestfit fit then
7:
8:
x² t #², best it t- fit(D,
continue <- True 10: end
9:
end for end for
13:
end while
14: Output: the order found with the highest fitness x²"
Ececution Time [s]
Notoors
RESIT
E. Least Pruning
03
The pseudocode of the least pruning algorithm described in the main text 'Least Pruning' section is shown in Algo- rithm 2
515crr
F. Additional Experimental Results
300
2005
2000
Esecution Time (s)
F.1. Efficiency
GENE
Notears-MLP
Gran-DAG e CAM RESIT PC-ANM R25ort
The results of efficiency are shown in Figure 8 the related analysis is available in Section 5.1 Efficiency part.
Figure 8. The wall-clock time vs. after standardization Fl score when 10 and 20.
F.2 Hyper-parameter Analysis
a = 1 as default in previous experiments, here we change it to {0.2, 0.5, 2, 5) and report the performance on datasets generated by MLP, MIM and GP with d = 10, density = 2. The results are shown in Figure
We investigate the influence of syper-parameterd namely a in Eq. 66) which is used to control the ratio the penalty term given by residual independence. Specifically, we set
15

---

Strong and Weak Identifiability of Optimization-baser Causal Discovery in Non-lincar Additive Noise Models
1.0
Score
0.6
0.4
e-0.2
0.2
0.0
MIM
MLP
GP
Figure 9. The performance of GENE with different values of hyper- parameter when d = 10, density 2.
can observe from Figure 9 that for MIM and GP, which are strong identifiable problems, the smaller a seems perform better and when 0.2, 0.5, the performance close. For MLP, the weakly identifiable one, too small (e.g., 0.1) may lead poor performance since the residual independence term plays an essential role for weak prob- lems. Generally speaking, GENE is not sensitive to the hyper-parameter a in a proper range (from 0.5 2) and we recommend to set a in this range.
16


Reviews:
[{"review_id": "yoSLUBkWCG", "reviewer": "Reviewer_GHeP", "summary": "This paper proposes to further divide the structure identifiability of ANM into strong one and weak one. The authors also proposes GENE, a generic method for causal discovery that works for both cases. The method is validated by both synthetic and real life data experiments.\n\n## update after rebuttal\n Thank you for the author's response. After reading all the review comments I decide to keep my rating unchanged.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive feedback and insightful suggestions. Below, we address each point raised in the review.\n### **Claims and Evidence**\n1. **Optimality of Eq. 6**  \n\nThank you for this constructive suggestion. We agree that Equation (6) could benefit from refinements like family-wise error control, especially when conducting multiple independence tests across variable pairs. Our current design prioritizes simplicity and computational efficiency, as greedy search over orders inherently involves numerous hypothesis tests. While thresholding via p-values (with Bonferroni-like penalties) helps mitigate false positives, we acknowledge that stricter error control (e.g., hierarchical testing or weighted penalties) might improve robustness. We will explore these enhancements in future work, balancing statistical rigor with scalability. Your insight aligns with our long-term goal of refining GENE’s theoretical grounding, and we appreciate your guidance on this critical aspect.\n\n### **Other Comments Or Suggestions**\n1. **Typo**  \nWe sincerely appreciate your careful reading, and we will make sure to correct this in the revised manuscript.\n\n### **Questions For Authors**\n1. **Extension to Post-nolinear Case**  \n\nThank you for this forward-looking suggestion. Extending GENE to post-nonlinear (PNL) models is indeed a promising direction. While PNL models introduce additional complexity (e.g., nonlinear transformations of both causes and effects), the core idea of leveraging implicit function theory to characterize identifiability can generalize. For instance, existence of implict functions in PNL mechanisms could similarly mask causal directions, necessitating adaptive criteria like residual independence. However, formalizing strong/weak identifiability in PNL settings requires careful theoretical work, as identifiability hinges on stricter functional constraints. We plan to explore this extension in future work, adapting GENE’s framework to address PNL-specific challenges while retaining its unified approach to identifiability.", "claims_and_evidence": "Yes. The claims are well-supported by theory and experimental results.", "methods_and_evaluation_criteria": "The method makes sense to me, though I am not sure the way to use p value in eq6 is optimal or not.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "Yes. The experimental setting including the ablation study looks plausible to me.", "relation_to_broader_scientific_literature": "The key contributions of the paper looks novel compared to previous findings.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths\n\n1. The paper is well-written and the idea is clearly presented.\n2. The claims made are supported by theory and empirical study.\n\nWeaknesses\n\n1. The design of eq 6 seems not optimal to me. Probably it can be improved, e.g., by family wise error control.", "other_comments_or_suggestions": "A typo in line 217.", "questions_for_authors": "1. Is it possible to extend to post-nonlinear setting?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Cf6J4Sk0b7", "reviewer": "Reviewer_YjMg", "summary": "The paper considers nonlinear ANMs for observational data, providing new structural identifiability results based on \"implicit functions\". Using these results, it proposes a learning algorithm that provably learns the correct order (in the large sample limit) and then heuristically prunes down to a sparse graph. The first phase of the algorithm does greedy score-based search over causal orderings, using independence tests to penalize the score---the unpenalized part of the score measures goodness of fit and is sufficient in the \"strongly identifiable\" case (the easy case), while the penalization suffices for the \"weakly identifiable\" (hard) case; the second phase starts at the complete graph with the learned causal order and heuristically prunes away edges.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive feedback and insightful suggestions. Below, we address each point raised in the review.\n### **Claims and Evidence**\n1. **Identifiability vs. Consistency**  \n   Thank you for highlighting this distinction. We agree that identifiability and consistency are distinct concepts. In Section 2 and Theorems 3.3/4.3, we clarified these notions. We will further revise the Introduction to explicitly differentiate them and ensure consistency in terminology.\n2. **Title Specificity**  \n   We appreciate this observation. The title will be revised to:  \n   *\"Strong and Weak Identifiability of Optimization-based Causal Discovery under Nonlinear Additive Noise Models\"*  \n   This better reflects the scope of our work.\n3. **Theoretical and Experimental Extensions for Pruning**  \n  Please refers to the discussion on pruning in the response to Reviewer XUn3 below.\n### **Methods and Evaluation Criteria**\n1. **Observational Data in Sachs**  \n  The Sachs dataset is continuously updated and has different versions. The version we used contains a total of 7466 samples, including 853 observational samples . Our usage aligns with prior works like *Causal Discovery with Reinforcement Learning* (ICLR 2020) and *Ordering-Based Causal Discovery with Reinforcement Learning* (IJCAI 2021). \n2. **Comparison to Other SOTA Methods**  \n   - **O-MCMC**: Designed for discrete Bayesian networks\n   - **GRaSP**: Focuses on linear models  \n   Neither of these two methods falls within the scope of the ANM studied in this paper. Additionally, the CPDAG method is a compromise for unidentifiable models, and its metrics are also difficult to align with those of deterministic causal graphs. Therefore, we did not include these comparisons in our study.\n### **Experimental Designs and Analyses**\n1. **Graph Size and Density**  \n   For ordering-based methods, especially in the context of nonlinear problems, 20 nodes is already a significant number. In Generalized Score Functions for Causal Discovery (KDD 18) and Ordering-Based Causal Discovery for Linear and\n Nonlinear Relations (NeurIPS 24), simulation experiments were conducted with a maximum of only 10 nodes.\n### **Essential References**\n1. **Novelty of Identifiability Results**  \nPrevious work has focused on identifiability in causal discovery, which originated from Bayesian network structure learning that limited to distinguishing up to the MEC via CPDAGs. However, Shimizu et al. (2006) showed that unique DAG identification is possible under linear causal relationships with non-Gaussian noise, leading to LiNGAM. Hoyer et al. (2008) extended this with ANM, which is identifiable under certain conditions. However, function properties in ANM affect practical identifiability, prompting the introduction of identifiability strength to guide metric usage in causal discovery practice.\n### **Other Comments and Suggestions**\n1. **Writing Improvements**  \n  Thank you for your thorough comments and pointing out the areas where our writing was not up to standard. We will carefully revise our manuscript according to your suggestions.\n2. **Minor Questions**  \n   - **Dimensionality Restriction**: The dimensionality restriction process is described in Eq. (5). Dividing the MSE by the variance of the effect variable below eliminates the influence of dimensionality (e.g., the measurement units of the effect variable) on fitness.\n   - **Def 3.1 Notation**: $pa(i)_k$ denotes the  k-th parent of $V_i$\n   - **Non-Standardized Data**: While Reisach et al. (2021) point out the significance of standardization, most benchmarks still use raw data. We compare both settings to validate our claims of scale variance/invariance.  \n### **Questions for Authors**\n1. **Operation in Definition 4.1**  \n   Our operation differs from Cycle Sort's cycle-based swaps. \n2. **Independence Test Choice**  \n   The chi^2-test was chosen for simplicity and computational efficiency. While distance covariance or Chatterjee's coefficient could also be applied, they add potential complexity. We will explore these in future work.\n3. **Using p-Values Directly**  \n   Thresholding stabilized performance in preliminary experiments. Soft penalties (e.g., weighted p-values) may improve results but require careful tuning.\n4. **Algorithm Complexity**  \n  The order search stage involves O(d²) fitness function evaluations, each taking O(n*d) time, resulting in a total complexity of O(n*d3). The pruning phase has a complexity of O(d²) w.r.t independence tests. \n5. **Pruning Assumptions**  \nPlease refer to the discussion on pruning in the response to Reviewer XUn3 below\n6. **Additional Experimental Results**  \nIt is worthy to note that for problems with d=10, density=4 corresponds to a density proportion of 0.89, which is already quite dense. Unfortunately, due to the limited time available for rebuttal, we were unable to conduct additional experiments in this area. We sincerely apologize for any inconvenience this may cause.", "claims_and_evidence": "Generally, the claims seem reasonable and the proofs look correct. However, I found some aspects of the title, abstract, and intro to be somewhat vague/confusing/misleading:\n- I normally see \"identifiability\" described as a property of a model, while the corresponding property of an algorithm is rather called \"consistency\" or \"validity\"; While it doesn't make sense to talk about validity of an algorithm without assuming some indentifiable underlying model, these are nevertheless distinct concepts/claims and require different kinds of proofs. This becomes clear starting in Section 2 (and in Thm 3.3 vs 4.3), but it's a bit confused before that.\n- \"Causal Discovery\" in the title sounds quite general, but it seems the results are only for nonlinear ANMs (this is certainly less restrictive than other assumptions common in the field, but still not as general as the title implies).\n- I think the paper has nice theoretical identifiability results, and that the algorithm and experiments are a fine \"proof of concept\"; however the presentation leading up to the algorithm made me expect stronger experimental results as well as additional theoretical results about the pruning phase, both of which are lacking.", "methods_and_evaluation_criteria": "Both the methods compared against and the real dataset used are potentially lacking:\n- as far as I've seen, the Sachs et al. data is _only_ interventional; can the authors clarify exactly how they obtained observational data?\n- other SOTA methods should be compared against (e.g., O-MCMC and GRaSP, referenced later in the review), even if it requires comparing CPDAGs instead of fully oriented DAGs.", "theoretical_claims": "I checked all of the proofs. They look good.", "experimental_designs_or_analyses": "I looked through the experimental design and analysis, and found this shortcoming:\n- limited simulated models: only up to 20 nodes and somewhat sparse; should go at least up to 100 nodes (especially considering claims about the high-dimensional scalability of optimization-based methods and the claims about pareto optimality of efficiency vs effectiveness of the method, which I suspect doesn't hold has $d$ increases).", "relation_to_broader_scientific_literature": "The paper makes use of some classic analysis results for its identifiability results. I found this simple but quite interesting.", "essential_references_not_discussed": "There should be discussion of SOTA order-based methods, including:\n- O-MCMC: Kuipers, J., Suter, P., & Moffa, G. (2022). Efficient sampling and structure learning of Bayesian networks. Journal of Computational and Graphical Statistics, 31(3), 639-650.\n- GRaSP: Lam, W. Y., Andrews, B., & Ramsey, J. (2022, August). Greedy relaxations of the sparsest permutation algorithm. In Uncertainty in Artificial Intelligence (pp. 1052-1062). PMLR.\n\nI'm not as familiar with the ANM literature, but I'm a bit surprised these identifiab results are new (which I think works very much in the paper's favor, if they are new); I'd like to see more discussion of ANM identifiability results to support this claim of novelty.", "other_strengths_and_weaknesses": "The paper would benefit from some polishing/editing, but I found it generally quite easy to understand while still being insightful.\n\nI think the identifiability have more potential for impact than the algorithm (which isn't differentiable, doesn't seem to scale, and lacks theoretical gaurantees for the pruning phase).", "other_comments_or_suggestions": "- generally, use \\mathrm{} where appropriate, e.g., $\\mathrm{pa}$ vs $pa$ and $\\mathrm{MSE}$ vs $MSE$, as well as many other others like $Var$, $IT$, $fit$, $OP$, $Rev$, ...\n- the first paragraph of the intro calls RCTs the gold standard for casual discovery (which is defined in the first sentence of the abstraction to be from observational data), but RCTs use interventional data, and they're rather more for causal inference than causal discovery (in a general graphical setting, rather than the bivariate case).\n- many figures are too small; a good rule of thumb I've seen is that the smallest text in the figs should still be at least footnote size---in any case, check the ICML formatting instructions\n- first sentence after Def 2.1 is a run-on sentence\n- next sentence, it should be \"assumptions\", since it's two distinct ones; \"..recover _a_ graph...\"\n- Line 119: doubled \"Hoyer et al\"\n- Line 122: \"_Specifically_...\"; and rephrase last sentence of that paragraph to be less confusing\n- Line 132 and on: confusing using \"forward\" and \"backward\" in that way; maybe try something like \"preceding\" and \"subsequent\"\n- clarify $F_i$ in (3) and $g$ later in Defn 3.1\n- nice explanation on Line 200\n- Line 218: fix \"Next We...\"\n- after (4), should be \"..._preceding_...\"\n- a few sentences later, should be \"_In other words_...\"\n- I disagree with the sufficient vs necessary contrast in the last paragraph on page 4. Goodness of fit is sufficient for strongly identifiable models but _insufficient_ for weakly indentifiable ones, while leveraging residual independence _is sufficient_ for weakly identifable ones.\n- Line 294: \"mild assumptions\" here also includes infinite data? The method requires lots of independence tests, so even with a lot of data and a very low significance level, there will still be a nonnegligable probability of the IT making a mistake somewhere.\n\n__Questions not important enough to be in the next section__:\n1. In abstract and intro, the \"dimensionality\" of the effect variable is described as \"restricted\". What does this mean for a continuous random variable?\n2. What does the $pa(i)_k = ...$ mean in Def 3.1? The left side just the index of some parent of $i$, right? Why is the right side equal to this index? I understood the idea based on the description after and the Rudin reference, but I still don't understand the notation here in the Def.\n3. Why even do experiments on non-standard data?", "questions_for_authors": "These questions are all related to the algorithm/performance (which is the weakest part, in my opinion), so depending on the answers I would increase my overall score.\n\n_Complexity_\n\n1. The operation in Definition 4.1 looks to me like Cycle Sort. Can the authors clarify and if so, add a citation?\n2. Line 220: why use this test instead of something that can handle continuous data, like Chaterjee's coefficient or distance covariance?\n3. What about using the statistic or p-value directly in the penalty instead of thresholding it?\n4. Whats the complexity of the proposed algorithm? Scoring a single causal order seems to require $O(d^2)$ tests (and these have some complexity in terms of sample size $n$), and then the Cycle Sort used has a multiplicative $O(d^2)$, and then there's still the pruning phase.\n\n_Theory_\n\n5. Any results/assupmtions ensuring a $\\theta$ exists that makes the pruning phase valid?\n\n_Experiments_\n\n6. Are there any results over  larger and/or denser graphs (preferably with density given as a proportion between 0 and 1)? Or against more standard SOTA methods that learn a CPDAG?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yrp5VPeqs3", "reviewer": "Reviewer_XUn3", "summary": "The paper tackles the problem of causal discovery in additive noise models. It identifies different classes of ANMs, strongly identifiable or weakly identifiable, that pose different levels of difficulty for traditional discovery algorithms. It characterizes sufficient conditions for the different classes and proposes a novel algorithm (GENE) that has consistent performance across both classes of ANMs. The algorithm proposes to find a topological ordering that maximizes a goodness-of-fit measure based on R^2 values and residual independence via a greedy search approach; a novel edge pruning approach that leverages R^2 values (least pruning) is proposed to enable parent set identification. The authors validate GENE real and synthetic data, finding that their algorithm maintains performance on strongly identifiable datasets while having superior performance on both weakly identifiable ANMs and real-world data.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive feedback and insightful suggestions. Below, we address each point raised in the review.\n### **Claims and Evidence**\n1 and 3 **Claims about Simple Regression's Sufficiency for Strongly Identifiable Problems**  \n\nThe experiments in Fig. 4 show that continuous optimization-based methods like Noteras-MLP and Gran-DAG, which rely on simple regression, suffer more significant performance degradation after standardization on weakly identifiable problems compared to strongly identifiable ones (e.g., MIM, GP). Additionally, removing the independence penalty in GENE (Fig. 5) harms performance more on weakly identifiable tasks while maintaining similar results on strongly identifiable ones.\n\n2. **Issues of Least Pruning**  \n\nWe acknowledge that the \"least pruning\" strategy is somewhat heuristic, but our focus is on the strength of identifiability in ANMs, which is orthogonal to variable selection. Besides, existing methods assume additive SEMs (e.g., Group LASSO, CAM-pruning) or specific functional forms (e.g., kernel lasso), limiting their generality. In contrast, least pruning iteratively removes edges with minimal impact on $R^2$, aligning with ANM's non-additive nature while remaining intuitive and empirically effective. \n### **Essential References Not Discussed:**\n1. **Difference to Existing Methods**  \n\nGENE differs fundamentally from R2-Sort [1] and RESIT [2]. While R2-Sort relies on an empirical observation (monotonicity of $R^2$ along causal orderings) without theoretical guarantees, and RESIT depends solely on residual independence tests (sensitive to test accuracy), GENE is guided by the strong and weak identifiability theory, which explicitly unifies $R^2$ and residual independence into a single framework, ensuring robustness across both identifiable regimes. For pruning strategies, we have to say they indeed often share structural similarities (e.g., iteratively removing potential parent and refitting models). GENE's least pruning prioritizes $R^2$-based impact over residual independence, directly targeting ANM's goal of preserving predictive fidelity while promoting sparsity. We include comparative experiments below to demonstrate the performance of different pruning strategies\n\n### **Other Strengths And Weaknesses:**\n1. **Contribution**  \n\nWhile GENE integrates elements from existing methods, its core novelty lies in formalizing strong and weak identifiability for ANMs—a theoretical advancement that explains why prior methods succeed or fail under varying functional complexities (Section 3). This framework directly guides GENE’s design, unifying $R^2$-based and independence-based criteria adaptively, rather than as a heuristic combination. Experiments validate its necessity: GENE uniquely addresses weakly identifiable problems, where existing methods collapse. We agree that broader analysis of algorithm-class relationships is valuable, but our focus here is establishing the identifiability theory and its algorithmic implications.\n\n### **Questions For Authors:**\n1. **Intuition**\n\nIntuitively, the distinction between strongly and weakly identifiable ANMs arises from the existence of implicit functions. In strongly identifiable cases, causal directions cause asymmetric fitting, with good regression only in the correct direction. Weakly identifiable ANMs allow near-perfect fits in both directions, necessitating residual independence tests. Classic methods fail because they rely solely on regression or independence.This aligns with invertibility in 2-variable case.\n\n2. **correctness for Pruning**\n\nSee above Issues of Least Pruning part. We also add relevant experiments below.\n\n3. **Experiments**\n\n(1) We add experiments for GENE ordering with different pruning: Lasso, CAM pruning and Edge discovery on problems with d=20, density=2, function=MLP, report mean±std on 10 repeatitions.\n|Function|Metric|GENE|GENE+Lasso|GENE+CAM-pruning|GENE+Edge Discovery|\n|-|-|-|-|-|-|\n|MLP|F1|0.76±0.11|0.48±0.13|0.69±0.08|0.55±0.11|\n|MLP|SHD|18.8±5.6|47.2±12.3|26.7±9.5|33.9±10.1|\n\n(2) We add experiments for 2 mentioned SOTAs ([1] and [5]) on problems with d=20, density=2, report mean±std on 10 repeatitions.\n|Function|Metric|GENE|NHTS|CaPS|\n|-|-|-|-|-|\n|MLP|F1|0.76±0.11|0.34±0.09|0.42±0.10|\n|MLP|SHD|18.8±5.6|52.3±17.6|41.3±14.0|\n|MIM|F1|0.88±0.09|0.40±0.07|0.71±0.12|\n|MIM|SHD|7.7±2.1|31.6±5.4|15.9±7.1|\n|GP|F1|0.90±0.09|0.38±0.10|0.73±0.07|\n|GP|SHD|9.1±3.3|39.9±9.9|14.5±4.3|\n\n(3) We appreciate this insightful observation. However, Def. 3.1 explicitly states that any structural equation with an implicit function renders the entire SEM weakly identifiable. Thus, real-world scenarios with mixed mechanisms inherently fall under the weakly identifiable category.\n\n(4) As mentioned earlier in the discussion of R2-Sort, it relies on an empirical observation but does not provide sufficient theoretical justification. Of course, it is also possible that their method requires more careful tuning.", "claims_and_evidence": "1. On page 3, following Definition 3.1, the authors claim that if an implicit function does not exist, the SEM can be identified by simple regression - however, this is never shown formally. This is important, as the validity of the distinction between weak and strongly identifiable ANMs hinges on whether such a simplification can be made.\n\n2. In Section 4.3, the authors introduce \"least-pruning\" as a way to prune spurious edges, given a correct topological ordering. They suggest that Group LASSO is inappropriate given that the ANM may not have an additive contribution from each parent. However, it is unclear how their Least Pruning approach overcomes such a limitation, or in general, what the advantage is of this approach, obscuring the paper's contribution.\n\n3. On page 4, paragraph 4, the authors claim that \"For strongly identifiable SEMs, consider the goodness of fit in an order-based manner is sufficient for causal discovery\". However, this claim lacks substantiation, which casts doubt on whether the objective function proposed by the authors is well-motivated.", "methods_and_evaluation_criteria": "The evaluation criteria (F1 and SHD) as well as the synthetic benchmarks used make sense for the application of causal discovery. However, there are significant additional experiments to run in order to fully evaluate the proposed approach (see 'Questions for Authors' for more details).", "theoretical_claims": "I checked the proof of Theorem 4.3 and found no issues.", "experimental_designs_or_analyses": "The experimental designs presented are both sound and valid. However, there are significant additional experiments to run in order to fully evaluate the proposed approach (see 'Questions for Authors' for more details).", "relation_to_broader_scientific_literature": "Prior work ([1,2]) has highlighted how ANMs may be generated with different characteristics (var-sortability, R^2-sortability), and propose heuristic algorithms (Var-Sort, R^2 Sort) that can exploit these characteristics to recover the underlying DAG. This paper outlines a novel characteristic of ANMs, strong or weak identifiability, and constructs a heuristic algorithm to exploit recovery in these contexts.\n\n[1] Reisach, A. G., Seiler, C., & Weichwald, S. Beware of the simulated DAG! Causal discovery benchmarks may be easy to game. *Proceedings of Machine Learning Research*, vol TBD:1–24, 2021.\n\n[2] Reisach, A. G., Tami, M., Seiler, C., Chambaz, A., & Weichwald, S. A scale-invariant sorting criterion to find a causal order in additive noise models. *Proceedings of Machine Learning Research*, vol TBD:1–24, 2023.", "essential_references_not_discussed": "1. In the ordering stage of GENE, the authors propose to use a combination of R^2 and residual independence to define the fitness function, with greedy search as an optimization algorithm; however, this appears to be a fusion of the R^2-sortability approach discussed in [1], as well as the independence-based score approach discussed in Section 4.2 and 4.2.2 of [2] - how does the proposed approach differ from these concepts? \n\n2. In the edge pruning stage of GENE, the suggested least pruning algorithm is extremely similar to the pruning algorithm suggested by RESIT [2] (Section 4.1), with the main difference being that the R^2 measure replaces the residual independence measure. However, this remains undiscussed in the paper, and thus the novelty of this approach appears low.\n\n\n\n[1] Reisach, A. G., Tami, M., Seiler, C., Chambaz, A., & Weichwald, S. A scale-invariant sorting criterion to find a causal order in additive noise models. *Proceedings of Machine Learning Research*, vol TBD:1–24, 2023.\n\n[2] Peters et. al, Causal Discovery with Continuous Additive Noise Models, (2014).", "other_strengths_and_weaknesses": "Weakness:\n\n1. The paper's novel contribution can be considered relatively minor. The algorithm GENE simply combines existing ideas from RESIT, GES, and R^2-Sort to enable both its ordering and pruning algorithms. Although the identification of strong/weak identifiable ANMs is novel and interesting, it is underexplored in this work, with little formal reasoning about how different algorithms may succeed or fail in different types of ANMs.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. What is the intuition behind what makes strongly or weakly identifiable ANMs easier or harder to discover? Why is it that \"simple regression\" suffices in the strongly identifiable cases, whereas it does not in the weakly identifiable? Further, is it possible to prove how various classic methods might fail in each scenario? Without extensive explicit and formal characterization of the importance of identifiability type, the contribution of the paper remains unclear.\n   1. To this end, perhaps there is a connection between invertibility and strong/weak identifiability? \n2. Although the authors provide a correctness result for their ordering algorithm, there is no such correctness result for their edge pruning algorithm (least pruning). In fact, there is little discussion of the assumptions under which least pruning would be expected to be accurate, and it seems as if the approach simply leverages the R^2 heuristic. Without guarantees of correctness, it is unclear when we might expect least pruning to succeed, or outperform other approaches.\n3. The experimental results can be considered an incomplete evaluation, and raise a few questions that cast doubt on the validity of the author's approach:\n   1. To properly evaluate the effectiveness of the proposed edge pruning \"least pruning\", an ablation study must be conducted. In particular, given a correct topological ordering, the authors should compare the accuracy of the adjacency matrix yielded against other baseline methods (Lasso, CAM-pruning, Edge Discovery; see [1] for details on such an experimental setup).\n   2. To further understand the performance increase over baselines, GENE should be compared against classic baselines such as DirectLiNGAM [2], as well as newer state-of-the-art approaches such as NHTS, SCORE, NoGAM, CaPS, and NHTS [1, 3, 4, 5]. Additionally, experiments should be conducted with non-gaussian noise (laplacian, uniform) to demonstrate the robustness of GENE.\n   3. The causal mechanisms considered by the author contain mechanisms that either all have implicit functions, or all do not - this may not be representative of real-life scenarios, where one is likely to encounter a range of mechanisms for which an implicit function may or may not exist for each parent. The authors should design an experiment to test whether GENE still outperforms when some causal mechanisms have implicit functions, and some do not, in order to ensure their experimental results do not overstate the performance of GENE.\n   4. R2-Sort performs poorly for both MIM and GP, which are both strongly identifiable ANMs - however, the authors claim in Section 4 that for strongly identifiable ANMs, considering the good-of-fit measure yielded from R^2 is sufficient for accurate discovery. This seems contradictory and casts doubt on the authors' explanation for the overperformance of GENE.\n\n\n\n[1] Hiremath et. al, Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models, NeurIPS (2024).\n\n[2] Shimizu et. al, DirectLiNGAM: A Direct Method for Learning a Linear Non-Gaussian Structural Equation Model, (2011).\n\n[3] Montagna et. al, Scalable Causal Discovery with Score Matching, CLeaR 2023.\n\n[4] Montagna et. al Causal Discovery with Score Matching on Additive Noise Models with Arbitrary Noise. PMLR 2023.\n\n[5] Xu et. al, Ordering-Based Causal Discovery for Linear and Nonlinear Relations, NeurIPS 2024.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W8NiOL7e85", "reviewer": "Reviewer_isnT", "summary": "The manuscript introduces a criterion for strong vs. weak identifiability in causal graphs and explores the implications for optimization based structure discovery algorithms. Specifically, the authors propose a gradient-based approach whose objective combines a standard goodness of fit measure ($R^2$) with a residual independence test to score candidate orderings. Experiments demonstrate strong performance compared to additive noise model causal discovery algorithms on a range of synthetic and real-world benchmarks.\n\n## update after rebuttal\n\nI thank the authors for their rebuttal. After reading the discussion with other reviewers, I am inclined to agree that this manuscript is somewhat under-developed at present and could benefit from further experiments and/or theoretical analysis. I will be revising my score downward for consensus but encourage the authors to revise and resubmit in the near future. This paper is nearly there and will find a good home soon!", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive feedback and insightful suggestions. Below, we address each point raised in the review.\n### **Claims and Evidence**\n1. **confusion about the strength of identifiability**  \nThank you for raising this important point. Within the ANM framework—which is inherently identifiable—our distinction between strong and weak identifiability refines the classical notion of identifiability into subclasses based on practical difficulty:\n-Strong Identifiability: The causal direction is uniquely recoverable via regression alone (examples see Fig. 1), requiring no additional criteria.\n-Weak Identifiability: The causal direction is still uniquely identifiable but requires residual independence tests to resolve ambiguity.\n\nBoth classes are fully identifiable under ANM assumptions, differing only in the difficulty of identification. Weak cases do not imply partial identifiability but instead demand stricter criteria to isolate the true graph. This distinction guides algorithm design: GENE adaptively combines criteria to address both regimes, ensuring robustness. We will clarify these nuances in the revision.\n\n### **Theoretical Claims**\n1. **Questions about Lemma 3.2**  \n\nThank you for your careful reading. m and M have to be positive because this property is used in the process of constructing the inequality proof for the contraction. The positivity ensures strict monotonicity of F, guaranteeing a unique implicit function φ(x) over the domain E. Regarding the support range of E, it is necessary to understand it in conjunction with the role of this Lemma and Theorem 3.3. The purpose of providing this theorem is to move from a purely theoretical definition of strong and weak identifiability to providing a practically operational way to detect the strong and weak identifiability of SEMs (although in causal discovery, this is rarely done).  It bridges theoretical definitions to actionable insights: if F satisfies the lemma's criteria within any plausible domain E (e.g., observed data ranges), the SEM is deemed weakly identifiable. This aligns with causal discovery's practical focus, where identifiability is assessed within empirically relevant regimes. We will clarify this intent in the revision.\n\n2. **Confusion of Thm. 3.3** \n\nTheorem 3.3 focuses on weak identifiability because it represents the more challenging and nuanced regime where classical methods fail. Strong identifiability, by definition, arises when no implicit functions exist (Def. 3.1), making it straightforward to identify causal directions via regression alone. Thus, strong identifiability does not require separate conditions—it is the default when Theorem 3.3's criteria are unmet. Unidentifiable SEMs, fall outside our scope, as ANMs inherently assume identifibility. We will clarify this hierarchy in the revision.\n\n### **Other Comments Or Suggestions**\n1. **Issue of R^2 Formular** \n\nThank you for catching this important technical detail. You are absolutely correct that we miss a $1-$ in the formulation. We sincerely appreciate your careful reading, and we will make sure to correct this in the revised manuscript.\n\n2. **Time Limit** \n\nSince in our simulation experiments, for each setting (node_num, density, function form), we generate 10 graphs, which is equivalent to having 10 problems. Each algorithm is then repeated 10 times on each of these problems, meaning each algorithm has 10 * 10 = 100 runs for each setting. Therefore, setting the time limit to 2 hours is quite reasonable.\n\n3. **Choice of Independence Tests** \n\nWe appreciate this suggestion. While nonparametric tests (e.g., HSIC, Spearman) avoid discretization, they introduce computational bottlenecks—HSIC scales as O(n^2) per test, and Spearman requires rank calculations across O(d^2) variable pairs. The chi^2 test balances efficiency (O(n) per test) with empirical reliability. We validated binning choices (m=10) across synthetic datasets, observing stable performance. That said, we agree that discretization loses information and will explore hybrid strategies (e.g., kernel-based tests for critical nodes) in future work.\n\n### **Questions For Authors**\n1. **Meaning of Weak Identifiability** \n\nWeak identifiability does not imply unidentifiability. Under ANM assumptions, even weakly identifiable SEMs are uniquely identifiable in the infinite-sample limit. The distinction lies in the practical requirements: weakly identifiable cases demand residual independence tests to resolve directionality ambiguities that persist with finite data (e.g., symmetric regression fits). While strong identifiability allows causal discovery via regression alone, weak identifiability requires additional criteria—but both guarantee convergence to the true graph asymptotically. \n\n2. **Condition for Unidentifiability or Strong identifiability** \n\nPlease refers to above response for Confusion of Thm. 3.3.", "claims_and_evidence": "The main theoretical claim is the purported distinction between \"strong\" and \"weak\" identifiability of causal structures in additive noise models (ANMs). If I understand correctly, the structural equation for variable $V_i$ is \"strongly identifiable\" if we can uniquely solve for each of its parents by fixing the value of $V_i$ and all other parents (including an exogenous noise variable). So far so good. But I'm a bit confused about if/how these notions map onto classical distinctions between identifiable vs. partially identifiable structures. If an ANM is only \"weakly\" identifiable, does this mean that there is no unique solution (at least without further assumptions)? It's not obvious to me that this follows. If there is no unique solution, can we at least characterize the space of possible solutions (e.g., something akin to a Markov equivalence class in constraint-based approaches?) Also, the text appears to suggest that strong and weak identifiability form a partition on the space of ANMs. But surely some ANMs are simply _unidentifiable_? \n\nThe empirical results are impressive. The idea of adding a residual independence testing component to the standard objective for optimization-based causal discovery makes good sense and appears quite effective. I am unaware of any previous proposals along this line.", "methods_and_evaluation_criteria": "The experiments are convincing and well-designed. Synthetic and real-world results tell a similar story.", "theoretical_claims": "The proofs appear sound, though I did not check them closely. I have some questions about how to interpret Lemma 3.2. Why do the constants $m, M$ have to be positive? This seems like a very restrictive assumption. If I understand correctly, it means that $F$ is strictly monotone in each of its $n+1$ arguments, at least within the range $E$? Also, is $E$ meant to be the full support or just a subset? If the former, then the lemma should probably say so. If the latter, then what happens outside this range? \n\nI'm not entirely clear to me what to make of Thm. 3.3 on its own – do we not have any sufficient conditions for strong identifiability? Or for that matter unidentifiability? \n\nThm. 4.3 is a nifty result. Always nice when greedy methods are globally optimal!", "experimental_designs_or_analyses": "As noted above, the experiments are clear and compelling.", "relation_to_broader_scientific_literature": "The topic of optimization-based causal discovery is of great interest to the ICML community, and has broad scientific application. Leveraging neural networks and gradient-based learning for this difficult task, which has traditionally been formulated with discrete reasoning, is a promising direction. Early works in this area faced some challenges (var-sortability, etc.) but I believe there will continue to be more interesting developments in this space. The present work makes a small but meaningful contribution to this discourse.", "essential_references_not_discussed": "I am not aware of any essential references that were not discussed, but I confess I am not an expert in this domain.", "other_strengths_and_weaknesses": "The idea is clear. The results are compelling. I feel I might be missing some link between the theoretical and empirical results. Greater elaboration on the former could help readers better appreciate the latter.", "other_comments_or_suggestions": "-The $R^2$ formula is missing a $1–$ before the ratio\n\n-Is 2 hours a reasonable time limit for causal discovery algorithms? Seems a little conservative.\n\n-I understand the motivation for the residual independence test, but I was a bit baffled by the choice to implement this via a $\\chi^2$ test. Surely we lose information by discretizing? This also introduces hyperparameters that may influence results (how many bins to use?) There are plenty of nonparametric independence tests for continuous data that could be used instead, e.g. Spearman $\\rho$ or HSIC.", "questions_for_authors": "My main questions are:\n\n(1) What exactly does \"weak identifiability\" amount to? Is it just that we need more samples to get the right answer, or that even in the infinite limit we will not converge on a unique answer? \n\n(2) We have a sufficient condition for weak identifiability, but none for unidentifiability (or for that matter strong identifiability). Any idea what these might look like? How about necessary conditions for any of these?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: Reviewers have both pointed out interest and weaknesses of this submission. On the bright side, this work presents an original perspective on identifiability, with the distinction between strong and weak identifiability, and provide support for the empirical relevance of this distinction. At the same time, reviewers also pointed out the limited theoretical contribution and the weakness of the link between theoretical and empirical sections. During the rebuttal period, the authors did their best to thoroughly address the concerns raised by reviewers. Despite acknowledging these efforts, several reviewers still emphasized some limitations of the contribution, either from the theoretical or algorithmic side. 

While this contribution is indeed not perfect, I think it is a rare on to tackle the important question of the current limitations of classical theoretical identifiability results, which are not necessarily predictive of empirical successes. Such work, at the intersection of theory and practice, although not providing a definitive answer, can provide some stimulating ideas to the community. I am therefore advocating for a weak accept.
Decision: Accept (poster)