Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy to Game
Authors: Alexander Gilbert Reisach
Christof Seiler
Sebastian Weichwald
Venue: NeurIPS 2021 Poster (2021)
Keywords: Causality
Directed Acyclic Graphs
Structure Learning
Continuous Optimization

Abstract: Simulated DAG models may exhibit properties that, perhaps inadvertently, render their structure identifiable and unexpectedly affect structure learning algorithms. Here, we show that marginal variance tends to increase along the causal order for generically sampled additive noise models. We introduce varsortability as a measure of the agreement between the order of increasing marginal variance and the causal order. For commonly sampled graphs and model parameters, we show that the remarkable performance of some continuous structure learning algorithms can be explained by high varsortability and matched by a simple baseline method. Yet, this performance may not transfer to real-world data where varsortability may be moderate or dependent on the choice of measurement scales. On standardized data, the same algorithms fail to identify the ground-truth DAG or its Markov equivalence class. While standardization removes the pattern in marginal variance, we show that data generating processes that incur high varsortability also leave a distinct covariance pattern that may be exploited even after standardization. Our findings challenge the significance of generic benchmarks with independently drawn parameters. The code is available at https://github.com/Scriddie/Varsortability.

Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game
Alexander G. Reisach
Christof Seiler
Sebastian Weichwald'
'Department of Mathematical Sciences, University of Copenhagen, Denmark DDepartment of Data Science and Knowledge Engineering, Maastricht University, The Netherlands
3 Mathematics Centre Maastricht, Maastricht University, The Netherlands
Abstract
Simulated DAG models may exhibit properties that, perhaps inadvertently, render their structure identifiable and unexpectedly affect structure learning algorithms. Here, we show that marginal variance tends to increase along the causal order for generically sampled additive noise models. We introduce varsortability as a measure of the agreement between the order of increasing marginal variance and the causal order. For commonly sampled graphs and model parameters, we show that the remarkable performance of some continuous structure learning algorithms can be explained by high varsortability and matched by simple baseline method. Yet, this performance may not transfer to real-world data where varsortability may be moderate or dependent on the choice of measurement scales. On standardized data, the same algorithms fail to identify the ground-trun truun DAG or its Markov equivalence class. While standardization removes the pattern in marginal variance, we show that data generating processes that incur high varsortability also leave a distinct covariance pattern that may be exploited even after standardization. Our findings challenge the significance of generic benchmarks with independently drawn parameters. The code is available https: / htt///gtttuuu//.//////// com htt///criddde Varsortability.
Introduction
Causal structure learning aims to infer causal model from data. Academic disciplines anywhere from biology, medicine, finance, machine learning are interested causal models [Rothman et al., 2008, Imbens and Rubin, 2015, Sanford and Moosa, 2012, Schölkopf, 2019]. Causal models not only describe the observational joint distribution of variables but also formalize predictions under inter- ventions and counterfactuals [Spirtes et al., 2000, Pearl, 2009, Peters et al., 2017]. Directed acyclic graphs (DAGs) are common to represent causal structure: nodes represent variables and directed edges point from cause to effect representing the causal relationships. This graphical representation rests on assumptions which have been critically questioned, for example by Dawid [2010]. Inferring causal structure from observational data is difficult: Often we can only identify the DAG up to its Markov equivalence class (MEC) and finding high-scoring DAGs is NP-hard [Chickering, 1996, Chickering et al., 2004]. Here, focus learning the DAG of linear additive noise models (ANM).
Data scale and marginal variance may carry information about the data generating process. This information can dominate benchmarking results, such as, for example, the outcome the NeurlPS Causality 4 Climate competition [Runge et al., 2020]. Here, the magnitude of regression coefficients was informative about the existence of causal links such that ordinary regression- methods on raw data outperformed causal discovery algorithms [Weichwald et al., 2020J. Multiple prior works
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

state the importance of data scale for structure learning either implicitly or explicitly. Structure identification by ICA-LINGAM [Shimizu et al., 2006], for example, susceptible to rescaling of the variables. This motivated the development of Direcil [Shimizu et al., 2011], scale-invariant causal discovery algorithm for linear non-Gaussian models. The causal structure of ANMs is proven to be identifiable given the noise scale (cf. Section 2.2). Yet, such identifiability results require knowledge about the ground-truth data scale.
Simulated DAGs may be identifiable from marginal variances under generic parameter distributions. An instructive example is the causal graph A + B with structural equations A = NA and B = W.A + NB with A 0 and independent zero-centered noise variables NA, NB- The mean squared error (MSH) of a model X + Y is given by MSE (X - -Y) = Var (X) + (ar(Y))), It holds that MSE (A - B) < MSE (B - A) e Var(A) < Var(B) = (1 w²) Var(NN) Var (see Appendix A). Deciding the directionality of the edge between A and B based on the MSE amounts inferring an edge from the lower-variane, variable the higher-variance variable. For error variances Var( A)) S Var(NB) and any non-zero edge weight w. the MSE-based inference is correct. This resembles known scale-based identifiability results based on equal or monotonically increasing eтror variances [Peters and Bühlmann, 2014, Park, 2020]. However, if the observations of A were multiplied by a sufficiently large constant, the MSE-based inference would wrongfully conclude that A <- B. This is problematic since simply choosing our units of measurement differently may change the scale and variance of A. Arguably, this often the case for observations from systems: There is no canonical choice as to whether we should pick meters or yards for distances, gram or kilogram for weights, or yuan or dollar as currency. A researcher cannot rely on obtaining the same results for different measurement scales or after re-scaling the data when applying any method that leverages the data scale (examples include Peters and Bühlmann [2014], Park (2020), or Zheng et al. [2018 8], who employ the least squares loss studied by Loh and Bühlmann [2014)).
Continuous causal structure learning algorithms optimize model fit under a differentiable acyclicity constraint [Zheng al., 2018]. This allows for the use of continuous optimization and avoids the explicit combinatorial traversal of possible causal structures. This idea has found numerous applications and extensions [Lachapelle et al., 2019, Lee et al., 2019, Ng et al., 2020, Yu al., 2019, Brouillard et al.. 2020, Pamfil et al., 2020, Wei et al., 2020, Zheng et al., 2020, Bhattacharya et al., 2021]; Vowels al. [2021] provide review. NOTEARS [Zheng et al., 2018] uses the MSE with reference to Loh and Bühlmann [2014], while GOLEM [Ng et al., 2020] assesses model fit by the penalized likelihood assuming a jointly Gaussian model. On simulated data and across noise distributions, both methods recover graphs that are remarkably close to the ground-truth causal graph in structural intervention distance (SID) and structural hamming distance (SHD). We agree with the original authors that these empirical findings, especially under model misspecification and given the non-convex loss landscape, may seem surprising at first. Here, we investigate the performance under data standardization and explain how the causal order is (partially) identifiable from the raw data scale alone in common generically simulated benchmarking data.
Contribution. We show that causal structure drives the marginal variances of nodes in ANM and can lead to (partial) identifiability. The pattern in marginal variances dominant in ANM benchmark simulations with edge coefficients drawn identically and independently. We introduce varsortability as a measure of the information the data scale carries about the causal structure. We argue that high varsortability affects the optimization procedures of continuous structure learning algorithms. Our experiments demonstrate that varsortability dominates the optimization and helps achieve state-of- the-art performance provided the ground-truth data scale. Data standardization or an unknown data scale remove this information and the same algorithms fail to recover the ground-truth DAG. Even methods using a score-equivalent likelihood criterion (GOLEM) recover neither ground-truth DAG nor its MEC on standardized data. To illustrate that recent benchmark results depend heavily on high varsortability, we provide a simple baseline method that exploits increasing marginal variances to achieve state-of tfate-of-the-nn art results on these benchmarks. We thereby provide an explanation for the unexpected performance of recent continuous structure learning algorithms in identifying the true DAG. Neither algorithm dominates on raw or standardized observations of the analyzed rorl-world data. We show how, even data is standardized and even in non-linear ANMs, a causal discovery benchmark may be gamed due to covariance patterns. Consequently, recent benchmark results may not transfer to (real-world) settings where the correct data scale unknown or where edge weights not drawn independent and identically distributed (iid). We conclude that structure learning
2

---

benchmarks on ANMs with generically sampled parameters may be distorted due to unexpected and perhaps unintended regularity patterns in the data.
2 Background
2.1
Model Class
We consider acyclic linear additive noise models. Single observations denoted by x(1) R where =r) denotes the jth dimension of the 1th iid observation of random vector [X1:.., Xz)T.
All observations are stacked as X = -,. _! E IRaxd and zj IR" refers to the juh column of X. Analogously, n denotes the corresponding jt iid observation of the random noise variable N = [Ni.... Nel with independent zero-centred components. The linear effect of variable Xx on X, is denoted by Wk-rj Wkj. The causal structure corresponding
the adjacency matrix W [_kg]kk.=........ with columns w, [uk=,]k==I...dd E R can be represented by directed acyclic graph G = (Va, FG) with vertices Va = {1,-.., d} and edges Fig = {(k,)) j) wk-+j # 0}. Edges can be represented by an adjacency matrix such that the (k entry of E is non-zero and only if directed path of length from & to exists in G. For a given graph, the parents of j are denoted by PA (j). The structural causal model is X = W + N.
2.2 Identifiability of Additive Noise Models
Identifiability of the causal structure or its MEC requires causal assumptions. Under causal faithful- ness and Markov assumptions, the causal graph can be recovered up its MEC [Chickering, 1995, Spirtes et al., 2000]. Faithfulness, however, is untestable [Zhang and Spirtes, 2008]. Shimizu et al. [2006] show that under the assumptions of no unobserved confounders, faithfulness, linearity, and non-Gaussian additive noise, the causal graph can be recovered from data. Hoyer et al. [2009] show that this holds for any noise distribution under the assumption of strict non-linearity. This finding is generalized to post-nonlinear functions by Zhang and Hyvarinen [2009]. Peters and Bühlmann [2014] prove that the causal structure of a linear causal model with Gaussian noise is identifiable the eπrrr variances
equal or known. Any unknown re-scaling of the data breaks this condition. For the case of linear structural causal models, Loh and Bühlmann [2014] provide a framework for DAG function. For ANMs, they give
estimation based on a noise variance- aariance-weighhed weighted least squares conditions under which the general Gaussian case can be identified via approximating it by the equal noise- variance case given knowledge of the (approximate) noise scale. Finally, subsuming further prior results on (linear) ANMs [Hoyer et al., 2009, Ghoshal and Honorio, 2017, 1, 2018, Chen et al., 2019], Park [2020] shows that the causal structure is identifiable under regularity conditions on the conditional variances along the causal order. In particular, identifiability holds if the error variances of nodes weakly monotonically increasing along the causal order.
2.3 Structure Learning Algorithms
Combinatorial structure learning algorithms (such as PC, FGES, DirectLiNGAM) separately solve the combinatorial problem of searching over structures and finding the optimal parameters for each structure. To remain computationally feasible, the search space of potential structures is often restricted or traversed according to heuristic. One can, for example, carefully choose which algorithms, or employ greedy
conditional independence statements to evaluate constraint- (equivalence class) search in score-based algorithms. In our experiments, we consider PC [Spirtes and Glymour, 1991]. FGES [Meek, 1997, Chickering, 2002b], DirectLiNGAM [Shimizu et al., 201 1], and greedy DAG search (GDS) algorithm MSE-GDS that greedily includes those edges that reduce the MSE the most. For details see Appendix D.
Continuous structure learning algorithms (such as NOTEARS and GOLEM) employ continuous optimization to simultaneously optimize over structures and parameters. As a first step towards expressing causal structure learning as a continuous optimization problem, Aragam and Zhou [2015] propose ["rregllarization instead of the conventional (" ("-penalty for model selection. Zheng al. [2018 8] propose differentiable acyclicity constraint, allowing for end-to-end optimization of score functions over graph adjacency matrices. We examine and compare the continuous structure learning algorithms NOTEARS [Zheng et al., 2018] and GOLEM [Ng et al., 2020]. For details see Appendix D.
3

---

NOTEARS [Zheng et al., 2018] minimizes the MSE between observations and model predictions subject to hard acyclicity constraint. The MSE with respect W on observations X defined as MSFx (W) X XWI where || 1|2
|r denotes the Frobenius norm.
GOLEM [Ng et al., 2020] performs maximum likelihood estimation (MLE) under the assumption of a Gaussian distribution with equal (EV) or non-equal (NV) noise variances. There are soft acyclicity and sparsity constraints. The unnormalized negative likelihood-parts of the objective function are
LEV (W, X) = log MSEx (W)) and Lv ( = Σラ=1 log ( |ay - Xw, Ile). respectively, omitting a - log( dot(T - ) term that vanishes when W represents a DAG [Ng et al., 2020).
To ease notation, we sometimes drop the explicit reference to X when referring to MSE, LEV, LNV.
3 Varsortability
The data generating process may leave information about the causal order in the data scale. We introduce varsortability as a measure of such information. When varsortability is maximal, the causal order is identifiable. Varsortability high in common simulation schemes used for benchmarking causal structure learning algorithms. We describe how continuous structure learning algorithms affected by marginal variances and how they may leverage high varsortability. This elucidates the results of continuous methods reported by Zheng al. [2018], Ng et al. [2020], and others on raw data and predicts impaired performance on standardized data as confirmed in Section 4. We introduce sortnregress simple baseline method that sorts variables by marginal variance followed by parent selection. The performance of sortnregress reflects the degree of varsortability in a given setting and establishes a reference baseline to benchmark structure learning algorithms against.
3.1 Definition of Varsortability
We propose varsortability as a measure of agreement between the order of increasing marginal variance and the causal order. For any causal model over variables (X1...., Xa} with (non-degenerate) DAG adjacency matrix E we define varsortability as the fraction directed paths that start from a node with strictly lower variance than the node they end in, that is,
1
< b 1/2
d Einsegt (xerossing(Var(x)))))) Var(X))) [0, 1] where increasing(a, b)
b
E.jeet 1
b
For example, we calculate the varsortability as v 1+1+1+1 4 given the causal graph below.
1+1+1 3
Varsortability equals one if the marginal variance of each node is strictly greater than that of its causal ancestors. Varsortability equals zero if the marginal variance of each node is strictly greater than that of its descendants. Var- sortability does not depend choosing one of the possibly multiple causal orders and captures the overall agreement between the partial order induced by the marginal vari- ances and all pathwise descendant relations implied by the causal structure. In the two-node introductory example (cf. Section 1), varsortability v = is equivalent to
Var(C) =3
(A) = 2
C
A
B
Var(B)
Var(A) < Var(B) = Var(Na) < 2² Var(NA) + +Vr(NB)
where A and B are nodes in the causal graph A " B with noise variances Var(NA) and Var(NB).
We can also understand varsortability we sample from for benchmarks on synthetic data. The distribution of weights and noise variances determines whether the causal order of any two connected nodes in the graph agrees with the order of increasing marginal variance and in turn determines the varsortability of the simulated causal models. We observe that even for modest probabilities of any two neighboring nodes being correctly ordered by their marginal variances, the variance of connected nodes tends to increase quickly along the causal order for many ANM instantiations (cf. Appendix G.3). For a heuristic explanation, recall that we obtain the marginal variance of a node by adding the variance contribution of all its ancestors to the
property of the distribution of graphs and parameters that

---

node's own noise variance; to obtain the variance contribution of an ancestor, we take the product of the edge weights along each directed path from ancestor to node, sum these path coefficient products, square, and multiply with the ancestor's noise variance. While the sum of path coefficient products may vanish or be small such that the variance contribution of an ancestor cancels out or is damped across the different connecting paths, we find it is unlikely if edge weights are drawn independently (cf. Meek [1995] for why exact cancellation and faithfulness violations are unlikely). Furthermore, the further apart connected pair of nodes, the more variance may be accumulated in the descendant node along all incoming paths in addition to one ancestor's (possibly damped) variance contribution further fueling the tendency for descendant nodes to have higher variance than their ancestors. In practice we indeed find that an ordering of nodes by increasing marginal variance closely aligns with the causal order for commonly simulated linear and non-linear ANMs (ef. Appendix G).
3.2 Varsortability and Identifiability
If varsortabilityy v= 1, the causal structure is identifiable. It can be recovered by ordering the nodes by increasing marginal variance and regressing each node onto its predecessors using conventional sparse regression approaches. The causal structure learning problem is commonly decoupled into causal order estimation and parent selection [Shimizu et al., 2006, Shojaie and Michailidis, 2010, Bühlmann et al., 2014, Chen et al., 2019, Park, 2020]. This decoupling is further warranted, since we only need the causal ordering to consistently estimate interventional distributions [Bühlmann et al., 2014, Section 2.6]. At Given a causal ordering, one can construct fully connected DAG and use parent selection to prune edges and reconstruct the graph in the sample limit under mild assumptions. Bühlmann et al. [2014, Section 2.5] discuss parent selection and Shojaie and Michailidis [2010] establish the consistency of an adaptive lasso approach for edge selection given valid causal order. The identifiability conditions by Park [2020] are closely related to varsortability, though not equivalent as we prove in Appendix C. 1, though, this shares severe
1, an ordering by marginal variance is valid causal ordering.
Identifiability of the causal order is immediate if varsortability drawbacks with other identifiability conditions that rely on data scale by Peters and Bühlmann [2014], Loh and Bühlmann [2014], and Park [2020]. First, it is difficult to verify or assess the plausibility of assumptions about the correctness or suitability of the data scale for any given dataset. Second, any unknown rescaling may break previously met identifiability conditions. Third, even if variables are on the same measurement scale the units may not correctly capture the ground-truth causal scale. For example, dartist's distance from the dartboard may affect the precision of their throw measured by the distance between hit and target. Here, the effect variable's 's marginal variance may be smaller than that of the cause (even) both distances are measured in centimetres. Nonetheless, may be possible to exploit varsortability if one can establish that certain assumptions on the data scale be met.
3.3 Varsortability in Benchmarking Scenarios
For real-world data we cannot readily assess nor presume varsortability as we do not know the parameters and data scale of the data generating process. When benchmarking causal structure learning algorithms, however, we can evaluate varsortability for the simulated DAGs and parameter settings. We may acquire an intuition about the probability of varsortable cause-effect pairs in our simulation settings by considering two neighboring nodes A 3 B in the sampled graph without common ancestors and no other directed path from A to B. Under these assumptions, Var( [) w² Var(A) + Var(ECCrA(()) (Λ) C²-
(ar(N)) such that |w]] > implies that the variable pair is varsortable. To simulate an ANM, we need to sample a DAG, decide on the noise distributions, and then sample edge weights and noise variances. Across simulation instances in given benchmark set-up, the edge weights W and noise variances o are iid instantiations of independent random variables W and S The distributions of W and 52 induce a distribution of the marginal variance Vy of node Y in the resulting ANM. The probability for the variable pair A - B to be varsortable in simulated ANM is then bounded from below by P[(1 - VA < S%a (cf. Appendix B). If A is a root node, VA- = 5 In the experimental settings used by, for example, Zheng et al. [2018, 2020]. Lachapelle et al. [2019], Ng et al. [2020], edge weights from a uniform distribution and noise standard deviations or variances are either fixed or also drawn independently from a uniform distribution. For our parameters W id Unif( -0.5) U (0.5, 2)) and S jid (nif( 2)), which resemble common choices in the literature, any pair is varsortable with probability at least 2/3 due to P||W| > 1] = 2/3, and with probability p > 0.93 provided A is
independently drawn
5

---

root node. Empirically, we find that varsortability averages above 0.94 in our simulated graphs and above 0.71 in commonly considered non-linear ANMs (cf. Appendix G). This result indicates that in benchmark simulations the marginal variance of any two nodes in graph tends to increase along the causal order and that we may game these benchmarks and perform well by exploiting this pattern.
If A and B have a common ancestor or mediator C, the effect of C' on B may either compound or partially cancel out the effect of on B. In practice, the effect commonly increases the variance of the effect node B, which may be attributed to the independent sampling of path coefficients which also renders faithfulness violations improbable [Meek, 1995]. We find varsortability to increase with graph density and the lower bound presented above to be loose. Motivated by the strong impact of different levels of varsortability on some structure learning algorithms as reported in Section 4 and Appendix H.2, we advocate an empirical evaluation and reporting of varsortability (cf. Appendix G.4 for the implementation) when simulating ANMs. We emphasize that even for varsortability < 1, where the order of increasing variance does not perfectly agree with the causal order, experimental results may still be largely driven by the overall agreement between increasing marginal variance and causal order. The extent to which varsortability may distort experimental comparisons of structure learning algorithms on linear ANMs is demonstrated in Section 4.
3.4 Marginal Variance yields Asymmetric Gradients for Causal and Anti-Causal Edges
We explain how varsortability may dominate the performance of continuous structure learning al- gorithms. We do not expect combinatorial structure learning algorithms that use score-equivalent (see e.g. Yang and Chang [2002], Chickering [2002a]) criterion or indeeeenddnn (conditional) independence tests to be dependent the data scale. This includes PC, local constraint based algorithm. FGES as locally greedy score-based search using a score-equivalent criterion, and Di- .NGAA,, procedure minimizing residual dependence. By contrast, combinatorial algorithms with a criterion that is not score-equivalent (such as the MSE) depend on the data scale. Due to the optimization procedure, continuous structure learning algorithms may depend the data scale irrespective of whether the employed score is score-oquivalent (as, for example, GOLEM for Gaussian models) or not (as, for example, GOLEM under likelihood misspecification NOTEARS).
We first establish how varsortability affects the gradients of MSE-based score functions (which akin to assuming equal noise variances in the Gaussian setting) and when initialising with the empty graph Oaxd (as is done in NOTEARS and GOLEM). Full statements of objective functions and respective gradients are found in Appendix E. Since V MSE (W) x X (X XW) we have that V MSE (Oaxa) X
X X and V (LEvv(Oxxee x !/IXXX X. The initial gradient step of both NOTEARS and GOLEM-EV is symmetric. We have MSS((W) x [XT(x> (z1 Xwa)] where the j"h column X (x; Xmy) reflects the vector of empirical covariances of the jth residual vector Ty- Xwy with each x; Provided a small identical step size is used across all entries of W in the first step (as, for example, in GOLEM-EV), we empirically find the residual variance after the first gradient step to be larger in those components that have higher marginal variance (see Appendix E.3 for a heuristic argument). We observe that during the next optimization steps V MSE(W) tends to be larger magnitude for edges pointing in the direction of nodes with high-variance residuals (which tends to be those with high marginal variance) than for those pointing in the direction of nodes with low-variance residuals (which tends to be those with low marginal variance). Intuitively, when cycles are penalized, the insertion of edges pointing to nodes with high residuals is favored as a larger reduction in MSE may be achieved than by including the opposing edge. Given high varsortability, this corresponds to favoring edges in the causal direction. This way, the global information about the causal order in case of high varsortability is effectively exploited.
Xwz),... X T(za-
Once allow for unequal noise variances in GOLEM-NV, the marginal variances lead the gradients differently, Letting MSE, (w,) = 11 - Xwy 12 we have
X (xz Xw,)
VLNV(W) x
MSE, (wy)
j=m.....d
such that the logarithmic derivative breaks the symmetry of the first step for the non-equal vari- ance formulation of GOLEM and we have VLNv
X X diag(l|xall?.... ||xali²)) While Vw MSE(W) & [X [xx Xww)li=t,.... I...,, tends to favor edges in causal direction (see above), the column-wise inverse MSE scaling of X (xz Xww) by MSE, (wy) (the residual variance in

---

the 5thh component) leads to larger magnitude gradient steps for edges pointing in the direction of low-variance nodes rather than high-variame nodes. Given high varsortability, this corresponds predominantly to the anti-causal direction.
We conjecture that the first gradient steps have dominant role in determining the causal structure, even though afterwards the optimization is governed by a non-trivial interplay of optimizer. model fit, constraints, and penalties. For this reason we focus on the first optimization steps explain a) why continuous structure learning algorithms that assume equal noise variance work remarkably well in the presence of high varsortability and b) why performance changes once data is standardized and the marginal variances no longer hold information about the causal order. Because of the acyclicity constraint, may be enough for weight wi-sj to be greater magnitude than its counterpart o wy-+ early on in the optimization for the smaller edge to be pruned from there on. For discussion of the interplay between sparsity penalties and data scale see Appendix J, which indicates that the nodes need to be on comparable data scale for L' pe-penalizttion to be well calibrated. Ng et al. [2020] provide further discussion on sparsity and acyclicity constraints continuous DAG learning.
3.5 sortnregress: A Diagnostic Tool to Reveal Varsortability
We propose an algorithm sortnregress performing the following two steps:
order search Sort nodes by increasing marginal variance.
parent search Regress each node on all of its predecessors in that order, using a sparse regression technique to prune edges [Shojaie and Michailidis, 2010]. We employ Lasso regression [Tibshhraai, 1996] using the Bayesian Information Criterion [Schwarz, 1978] for model selection.
As baseline, sorthregress is easy implement (cf. Appendix H.1) and highlights and evaluates to which extent the data scale is informative of the causal structure in different benchmark scenarios. An extension for non-linear additive noise models is obtained by using an appropriate non-linear regression technique in the parent search step, possibly paired with cross-validated recursive feature elimination. It facilitates a clear and contextualized assessment of different structure learning algo- rithms in different benchmark scenarios. The relationship between varsortability and the performance of sortnregress in a linear setting is shown Appendix H.2. Varying degrees of varsortability and performance of sorinregress add an important dimension which current benchmarks do not consider.
4 Simulations
We compare the performance of the algorithms introduced in Section 2.3 on raw and standardized synthetic data. In our comparison, we distinguish between settings with different noise distributions, graph types, and graph sizes. Our experimental set-up follows those in Zheng et al. [2018), Ng Appendix K. We
et al. [2020] and we contribute results obtained repeating their experiments complement and previous DAG-recovery results by additionally evaluating how well the DAG output by continous structure learning algorithms identifies the MEC of the ground-truth DAG.
4.1 Data Generation
We sample Erdös-Réne (ER) [Erdös and Rényi, 1960] and Scale-Free (SF) [Barabási and Albert, 1999] graphs and the parameters for ANMs according to the simulation details in Table 1. For a graph specified as ER-k or SF-k with d nodes, we simulate dk edges. For every combination of parameters, we create a raw data instance and a standardized version that is de-meaned and re-scaled to unit variance. On standardized data, we have varsortability e = 1/ and the marginal variances hold no information about the causal ordering of the nodes. In all our experimental settings, varsortability averages above 0.94 on the raw data scale (cf. Appendix G.I).
Table 1: Parameters for synthetic data generation.
Repetitions
10
Edge weights
iid Unif(( -5) (.5, 2))
Graphs
ER-2, SF-2, SF-4
Noise distributions
Exponential, Gaussian, Gumbel
Nodes
d (10, 30)
Noise standard deviations
1 GGaussian--VV; iid Unif(.5, 2) (others)
Samples
n 1000
7

---

Recovery of ground-truth DAG
D'eeCuNGAN
stam sandarddzee
PC
PC
Aigorihi
Algontbin
INTTERR
NOTEARS
GOLDR DK-VV
GOL IN-VV
sorthregress
500
1000
1590
300 Structural Hamming Distance
Structural intervention Distance
Recovery of ground-trth DAG's Markov equivalence class
DIOCCUNNAA
DiectuNGAN
stander convinutut
saanerrticed continuuu
PC
PC
randeme
Aigonthim
Algentan
NOTEARS
NOTEARS
NVL
GOLEM-NV
sorthragress
MEC Structural Intervention Distance tupper bound)
MEC Structural Hamming Distance
Figure I: SID (left, lower is better) and SHD (right, lower is better) between recovered and ground- truth graphs (top) or Markov equivalence classes (bottom) for ER-2 graphs with 50 (top) or 10 (bottom) nodes and Gaussian-NV noise. The performance of sortnregress, which only exploits varsortability, matches that of the continuous methods NOTEARS and GOLEM.
4.2 Evaluation
We evaluate performance using structural intervention distance (SID) [Peters and Bühlmann, 2015] and structural Hamming distance (SHD) between the recovered graph and ground truth. Additionally, we contribute a performance assessments of continuous structure learning algorithms in terms of the SID and SHD between the ground-truth MEC and the recovered MEC (PC, FGES) or the MEC identified by the recovered graph (NOTEARS, GOLEM). SID assesses in how far the recovered structure enables to correctly predict the effect of interventions. SHD measures the distance between the true and recovered graph by counting how many edge insertions, deletions, and reversals are required to turn the former into the latter. Since interventional distributions can consistently be estimated given only the causal ordering [Bühlmann et al., 2014), SID is less susceptible arbitrary choices of edge pruning procedures and thresholds than SHD. Intuitively, SID prioritizes the causal order, while SHD prioritizes the correctness of individual edges. We follow common practices for edge thresholding and scoring (see Appendix K).
4.3 Performance on Raw Versus Standardized Data
We group algorithms into combinatorial and continuous algorithms. We propose novel baseline algorithm termed sortnregress which serves as reference marking the performance achievable by directly exploiting marginal variances. We indicate its performance on standardized data as random- regress, since it amounts to choosing a random order and regressing each node on its predecessors. We use boxplots aggregating the performance achieved in the 10 repetitions data by each algorithm and create separate plots per noise type to account for identifiability and MLE specification differences. We show the results obtained for ER-2 graphs and Gaussian noise with non-equal variances in Figure 1. These results are representative of the results obtained for different graphs and noise distributions (cf. Appendix K). For the simulated settings, varsortability is high (> 0.94) on the raw data scale (ef. Appendix G.1).
raw and standardized
We observe that some algorithms are highly scale-sensitive and perform vastly different raw and standardized data. The algorithms NOTEARS, MSF-GDS, GOLEM-EV are most affected their performance is excellent data but far worse standardized data. Note that all of these rely

---

a loss function that revolves around the MSE. The performance of GOLEM-NV is also seale-sensitive but improves upon standardization. The direction of the effect of standardization is in line with the predictions by our gradient analysis in Section 3.4. Note that we initialize all algorithms with the empty graph since we are primarily interested in comparing the impact of standardization given equal starting conditions. On standardized data, an initialization of GOLEM-NV with the results of GOLEM-EV, as recommended by Ng et al. [2020], does not improve performance and may fail to converge. sortnregress achieves competitive performance on raw, and baseline performance on standardized data. It thus qualifies as diagnostic tool to highlight how much of a given causal structure learning task can be resolved by exploiting data scale and sorting nodes by their marginal variance.
In summary, the evidence corroborates our claim that the remarkable performance on raw data and the overall behavior upon standardization of the continuous structure learning algorithms may be driven primarily by high varsortability. On a real-worle causal protein signaling dataset [Sachs et al., 2005] we measure a mean varsortability of 0.57 (which is close to chance level at 0.5) with a standard deviation of 0.01 across our bootstrapped samples and do not observe the consistent performance pattern described for synthetic data with high varsortability (cf. Appendix I).
5
Gaming Further Benchmarks
5.1 Orienting Causal Chains on Standardized Data
In order to design a causal discovery benchmark that does not favor methods that explicitly exploit marginal variances we may standardize the data or employ coefficient re-scaling schemes. Mooij et al. [2020], for example, propose a scale-harmonizztion by dividing each column wi - [wx=>slj=t,...d E Rd of the drawn adjacency matrices by Vllwi] || + 1 such that each variable would have comparable scale if all its direct parents were independently standard-normally distributed. However, this does not avoid the problem of potentially inadvertent patterns in simulated ANMs. Even after standardization or ocale-harmonization, DAGs with previously high varsortability generate data with distinct covariance patterns that may be exploited.
In Appendix F we present instructive example of a decision rule that can infer the orientation of a causal chain from raw, standardized, and scale- harmonized data with accuracy strictly greater than 50%. For a causal chain X1 + X2 - ... + Xa where edge weights and noise terms drawn iid we can decide between the two Markov-cquivallnn graphs X1 + X₂ + ... + Xa and X1 < X₂ ... f- X whith above-chance accuracy. The empirical results for varying chain-lengths and various adge-weight distribution are deferred to the appendix where we discuss the 3-variable chain in detail and illustrate that the phenomenon extends from finite- sample to the population setting.
The intuition is as follows. Consider data generated by X1 + + - - + Xa and the aim is to infer from standardized data whether X, + ... Xa or X1 + f- X.. For data with high varsortability and comparable noise variance on the raw data scale it holds that the further downstream node X; is in the causal chain, the stronger the variance of its parent Var(X;-1) contributes to its marginal variance (X, = Var(X;-1) + Var(N,) relative to its noise variance Var(NV), and the stronger is it correlated with its parent. Thus, the sequence of regression coefficients, which tends to increase in magnitude
in the standardized case amounts to (Corr(X; (X,, X=+1))==I....dd along the causal order and decrease in the anti-causal direction. The proposed decision rule predicts the causal direction as the one in which the absolute values of the regression coefficients tend to increase. This chain orientation rule achieves above-chance performance on raw, standardized, and scale-harmonized data (cf. Appendix F).
5.2 Sorting by Variance in Non-Linear Settings
Varsortability may also be exploited in non-linear settings. Table 2 shows the results of sorting by marginal variance and filling in all edges from lower-variance nodes to hiriacev nodes in a non-linear setting. This variance sorting strategy is more naive than sortnregress and places no assumption on the functional form. The results are substantially better than random sorting and may therefore be a more informative baseline than commonly used random graphs. We not show performance in terms of SHD, as our variance sorting baseline always yields a fully connected graph. Although the data generating process not identical, we note that the improvement of our crude variance sorting over random sorting compares favorably to some of the improvements gained by

---

more involved methods over random graphs as shown in Lachapelle et al. [2019, Table I]. Our results indicate that exploiting varsortability may also deliver competitive results in non-linear settings.
Table 2: SID of naive baselines on non-linear data. Results on 1000 observations of additive Gaussian process ANMs with noise variance I simulated as by Zheng et al. [2020] (10 repetitions each; average varsortability v per graph type shown in parentheses).
Algorithm
Graph (average v)
ER-1
ER-4 (0.95)
SF-1 (0.95)
SF.4 (0.98)
(0.87)
variance sorting random sorting
7.7 5.72
25.2 + 12.36
1.9 + 2.28
7.6 + 3.37
27.9 = 11.44
63.1 + 8.10
22.3 + 13.14
59.5 = 7.32
We find similarly high levels of varsortability for many non-linear functional relationships and graph parameters (cf. Appendix G.2). This begs the question how much other successful methods exploit varsortability, how they compare to non-linear nonparametric methods that leverage assumptions on the residual variances [Gao et al., 2020]. and how they perform under data standardization. We encourage such an exploration in future work and suggest that varsortability and sortnregress or variance sorting should always be included in future benchmarks.
6 Discussion and Conclusion
We find that continuous structure learning methods are highly susceptible to data rescaling and some do not perform well without access the true data scale. Therefore, scale-variant causal structure learning methods should be applied and benchmarked with caution, especially if the variables do not share measurement scale or when the true scale of the data is unattainable. It is important to declare whether data is standardized prior to being fed to various structure learning algorithms.
Following the first release of the present paper, Kaiser and Sipos [2021] also independently reported the drop in performance of NOTEARS upon standardizing the data and presented low-dimensional exemplary case. Beyond reporting of impaired NOTEARS performance, we also analyze score- cquivalent methods, provide exhaustive simulation experiments, and explain the phenomenon.
Our aim is to raise awareness of the severity with which scaling properties in data from simulated DAGs and causal additive models may distort algorithm performance. Increasing marginal variances can render scenarios identifiable, which may commonly not be expected to be so for example the Gaussian case with non-equas variances. We therefore argue that varsortability should be taken into account for future benchmarking. Yet, with any synthetic benchmark there remains risk that the results are not indicative of algorithm performance on real data. Our results indicate that current structure learning algorithms may perform within the range of naive baselines on real-world datasets.
The theoretical results of our paper are limited to the setting of linear ANMs. Additionally, our conjecture regarding the importance of the first gradient steps, and with it a rigorous causal explanation for the learning behavior of different continuous algorithms and corresponding score functions remain open and require further research to be settled. Our empirical findings indicate that causal discovery benchmarks can be similarly gamed on standardized data and in non -onelinear settings, but further research is needed to confirm this. We focus on specific subset of algrorithms, the impact of patterns in benchmarking data on a wider class of algorithms and score functions remains to be explored.
Varsortability arises in many ANMs and the marginal variances increase drastically along the causal order, at least in common simulation settings. This begs the question what degree of varsortability can be observed or assumed in real-world data. If the marginal variances carry information about the causal order, our results suggest that it can and should be leveraged for structure learning. Otherwise, our contribution motivates future research into representative benchmarks and may put the practical applicability of the additive noise assumption into question.
Acknowledgements
We thank Jonas M. Kübler, Jonas Peters, and Sorawit Saengkyongam for helpful discussions and comments. SW was supported by the Carlsberg Foundation.
10

---

References
Bryon Aragam and Qing Zhou, Concave penalized estimation of sparse Gaussian Bayesian networks. Journal of Machine Learning Research, 16(69)):273-23533 -3228, 2015.
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439): 509-512, 1999.
Rohit Bhattacharya, Tushar Nagarajan, Daniel Malinsky, and Ilya Shpitser. Differentialee causal discovery under unmeasured confounding. In International Conference Artificial Intelligence and Statistics, 2021.
Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. In Advances Neural Information Processing Systems, 2020.
Peter Bühlmann, Jonas Peters, and Jan Ernest. CAM: Causal additive models, high-dimensional order search and penalized regression. The Annals of Statistics, 42(6):2526 (55565652--,56, 2014.
Wenyu Chen, Mathias Drton, and Y Samuel Wang. On causal discovery with an equal-variance assumption. Biometrika, 106(4):973-98)) 09 2019.
David M. Chickering. A Transformational Characterization of Equivalent Bayesian Network Structures. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (UAI), 1995.
David M. Chickering. Learning Bayesian Networks is NP-complete. In Learning From Data, pages 121-130. Springer, 1996.
David M. Chickering. Learning equivalence classes of Bayesian- network structures. Journal of Machine Learning Research, 2:445 498, 2002a.
David M. Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3(11):507-554, 2002b.
David M. Chickering, David Heckerman, and Chris Meek. Large-sample learning of Bayesian networks is NP-hard. Journal of Machine Learning Research, 5:1287-1330 2004.
Philip Dawid. Beware the DAG! Proceedings of Workshop on Causality: Objectives and Assessment at NIPS 2008, volume 6 Proceedings of Machine Learning Research, pages 59-86. PMLR, 2010.
Paul Erdös and Alfred Rényi. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 5(1):17 60, 1960.
Ming Gao. Yi Ding, and Bryon Aragam. A polynomial-time algorithm for learning nonparametric causal graphs. In Advances in Neural Information Processing Systems, 2020.
Asish Ghoshal and Jean Honorio. Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity. Advances Neural Information Processing Systems, 2017.
Asish Ghoshal Jean Honorio. Learning linear structural equation models in polynomial time and sample complexity. International Conference on Artificial Intelligence and Statistics, 2018.
Patrik Hoyer, Dominik Janzing, Joris M. Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. In Advances in Neural Information Processing Systems, 2009.
Guido W. Imbens and Donald B. Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge University Press, 2015.
Marcus Kaiser and Maksim Sipos. Unsuitability of NOTEARS for Causal Graph Discovery. arXiv preprint arXiv:2104.04411, 2021.
Sébastien Lachapelle. Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien Gradient-bass neural DAG learning. arXiv preprint /tti::/996.022222 2019.
Hao-Chih Lec, Mattco Danicletto, Riccardo Miotto, Sarah T. Cherng, and Joel T. Dudley, Scaling structural learning with NO- BEARS to infer causal transcriptome networks. arXiv preprint arXiv: 191.0008,, 2019.
Po-Ling Loh and Peter Bühlmann. High-dimensions learning of linear causal networks via inverse covariance estimation. Journal of Machine Learning Research, 15:3065-31 3105, 2014.

---

Christopher Meek. Strong Completeness And Faithfulness In Bayesian Networks, In Proceedings of Eleventh Conference on Uncertainty in Artificial Intelligence (UAI), 1995.
Christopher Meek. Graphical Models: Selecting causal and statistical models. PhD thesis, Carnegie Mellon University, 1997.
Joris M. Mooij, Sara Magliacane, and Tom Claassen. Joint Causal Inference from Multiple Contexts. Journal of Machine Learning Research, 21999);1-108, 2020.
Ignavier Ng, AmirEmad Ghassami, and Kun Zhang, On the role of sparsity and DAG constraints for learning linear DAGs. In Advances in Neural Information Processing Systems, 2020.
Roxana Pamfil, Nisara Sriwattanaworuchai, Shaan Desai, Philip Pilgerstorfer, Konstantinos Georgatzis, Paul Beaumont, and Bryon Aragam. DYNOTEARS: Structure Learning from Time-Series Data. In International Conference on Artificial Intelligence and Statistics, 2020.
Gunwoong Park. Identifiability of additive noise models using conditional variances. Journal of Machine Learning Research, 21(75):1-34, 2020.
Judea Pearl. Causal inference statistics: An overview. Staristics surveys, 3:96-146, 2009.
Jonas Peters and Peter Bühlmann. Identifiability of Gaussian structural equation models with equal emror variances. Biometrika, 101(1):219-228, 2014.
Jonas Peters and Peter Bühlmann. Structural intervention distance for evaluating causal graphs. Neural Computation, 27(3)771-7799, 2015.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of Causal Inference. MIT Press, 2017.
Joseph D. Ramsey, Kun Zhang, Madelyn Glymour, Ruben S. Romero, Biwei Huang, Imme Ehert- Sthor-,Uphoff, Savini Samarasinghe, Elizabeth A. Barnes, and Clark Glymour. TETRAD A toolbox for causal discovery. In 8th International Workshop on Climate Informatics (CI 2018). 2018.
Kenneth Rothman, Sander Greenland, and Timothy L. Lash. Modern Epidemiology. Lippincott Williams Wilkins, 2008.
Jakob Runge, Xavier-Andess Tibau, Matthias Bruhns, Jordi Muñoz-Mari and Gustau Camps-Vall Valls. The causality for climate competition. In NeurlPS 2019 Comperition and Demonstration Track, pages 1 110-120, PMLR, 2020.
Karen Sachs, Omar Perez, Dana Pe'er, Douglas A. Lauffenburger, and Garry P. Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science, 308(5721) 2005.
Andrew D. Sanford and Imad A. Moosa. A Bayesian network structure for operational risk modelling in structured finance operations. Journal of the Operational Research Society, 63(4):431-444, 2012.
Bernhard Schölkopf. Causality for machine learning. arXiv preprint 1rXiv:1911.1050000 2019.
Gideon Schwarz. Estimating dimension of model. The Annals of Statistics, 6(2) 1978.
Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti Kerminen. lincar non Gaussian acyelic model for causal discovery. Journal of Machine Learning Research, 7:2003-2030, 2006.
Shohei Shimizu, Takanori Inazumi, Yasuhiro Sogawa, Aapo Hyvärinen, Yoshinobu Kawahara, Takashi Washio, Patrik O. Hoyer, and Kenneth Bollen. DirectL.NGGAN A direct method for learning linear non-Gaussian structural equation model. Journal of Machine Learning Research, 12: 12:1225-122 1248, 2011.
Ali Shojaie and George Michailidis. Penalized likelihood methods for estimation of sparse high-dinennsonnll directed acyclic graphs. Biometrika, 97(3)519-5338 2010.
Peter Spirtes and Clark Glymour. algorithm fast recovery of sparse causal graphs. Social Science Computer Review, 91):62-72, 1991.
Peter Spirtes, Clark N. Glymour, Richard Scheines, and David Heckerman. Causation, Prediction, and Search. MIT press, 2000.
Robert Tibshirani.
Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-286 1996.
12

---

Matthew J. Vowels, Necati Cihan Camgoz, and Richard Bowden. ya like DAGs? A Survey on Structure Learning and Causal Discovery. arXiv preprint urXi:22003.02882, 2021.
Dennis Wei, Tian Gao, and Yue Yu. DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks. arXiv preprint arXiv:2010.09133, 2020.
Sebastian Weichwald, Martin E. Jakobsen, Phillip B. Mogensen, Lasse Petersen, Nikolaj Thams, and Gherardo Varando. Causal structure learning from time series: Large regression coefficients may predict causal links better in practice than small p-values. In NeurfPS 2019 Competition and Demonstration Track, pages 27- 36. PMLR, 2020.
Shulin Yang and Kuo-Chu Chang. Comparison of score metrics Bayesian network learning. IEEE Transuc- lions on Systems, Man, and Cyberneticx-Parl A: Systems and Humuns, 32(3):419-433 2002.
Yue Yu, Chen, Tian Gao, and Mo DAG-GNN: DAG structure learning with graph neural networks. arXiv preprint arXiv:1904. 2019.
Jiji Zhang and Peter Spirtes. Detection unfaithfulness robust causal inference. Minds and Machines, 18 (2):239-271, 2008
Kun Zhang Aapo Hyvarinen. On identifiability of post-nonlinear causal model. In Proceedings of the Twenty-Fifte Conference on Uncertainty in Artificial Intelligence (UAI), 2009.
Xun Zheng, Bryon Aragam, Pradeep Ravikumar, and Eric P. Xing- DAGs with NO TEARS: Continuous optimization for structure learning. In Advances in Neural Information Processing Systems, 2018.
Xun Zheng, Chen Dan, Bryon Aragam, Pradeep K. Ravikumar, and Eric Xing. Learning sparse nonparametric DAGs. In International Conference on Artificial Intelligence and Statistics, 2020.
13


Reviews:
[{"review_id": "xWd2uHmIRu", "reviewer": "Reviewer_BrkD", "summary": "This submission is about causal structure learning and how some simulated directed acyclic graphs (that are used for benchmarking structure learning approaches, and that are generally used for causal representations) can have properties (in particular, marginal variances and also covariance patterns) that could render some structure learning algorithms more efficient, even though that might be not necessarily replicable for real-world data; that is highlighted a concern.\n\nThe authors describe a measure, varsortability, that relates to a relationship between marginal variances and the causal structure in a causal graph. They discuss how identifiability might be affected by that. The submission shows how, and explains potentially why, the varsortability of causal graphs and the data simulated/generated from them might interplay with the performance of some structure learning algorithms (in particular, continuous structure learning methods), and how that performance might be explained and depend (potentially, inadvertently) up to some significant extent by the varsortability (in particular, for simulated DAGs). The submission covers that through some theoretical analysis and empirical studies. Because marginal variances and varsortability depend on the choice of the scales of variables, the submission raises concerns about the usefulness/interpretation of existing benchmarks (particularly if no experiments with data standardisation are performed) and their results for existing structure learning algorithms. The submission also presents a baseline structure learning method that relies on marginal variances; that method can be used as a baseline for benchmarking. The theoretical results in the submission is for linear additive noise models; the empirical experiments cover both some linear and non-linear settings. The empirical experiments (and results) cover simulated and also some real-world data. In addition to discussing the points that relate to marginal variances, the submission also has a part that relates to covariance patterns and how those might influence the benchmarking in a similar way. The paper finishes with a conclusion and discussion, including some recommendations/comments as part of that.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is written very well. I believe it is a very important paper. The paper is significant because it raises valid concerns about existing benchmarking (and results received with them) in a constructive way (see the summary section of the review for more details on the contribution). Thanks extremely much to the authors for their work on this.\n\nMany related work papers are referred to in the submission. The submission naturally relies on previous work. Based on that coverage, it is assumed that the idea and implementation, as a whole, are original.\n\nSome clarity points:\n\n* The sentence on lines 53-56: it might be helpful to clarify for a reader whether this statement (“... cannot rely …”) is covered in those references or it is a finding/point of this submission.\n\n* Line 90: “inadvertent” (also similarly in line 319 and “inadvertently” in line 1) - are they inadvertent or potentially “advertent”/natural (and the submission also refers to this question in lines 375-377)? (As far as the variables have the same meaning and it is natural for them to have the same scale?)\n\n* Some clarification/more details might be helpful for lines 169-177:\n** Line 172: “... obtaining varsortability for each individual …” - is something like “a varsortability component/part” meant? (since a pair of nodes is just a part of a graph)\n** Regarding sentences “Even … quickly” and “The further … to the causal order” - I assume the authors might be (partially) relying on the Appendix B regarding those statements. However, those statements are not trivial, to the best of my understanding, and a proof (or at least a sketch) might be essential for them. (For example, can there be some cancellation of noise on a causal path along a causal order? (As the authors mention as well in lines 212-214.))\n** Philosophically, how can we be certain that those properties are not replicated in the real world (for at least some data)?\n\n* Line 179: “If varsortability v = 1, the causal structure is identifiable” - this is a strong statement. I see how it could be potentially (sometimes?) identifiable (from a “partial” causal order), but I don’t see why the causal structure would be necessarily identifiable in general, especially from noisy data. A proof, a sketch and/or a reference would be very helpful.\n\n* Lines 193-194: if we don’t know the true data scale (and maybe there is no _true_ scale) but variables have the same meaning (e.g. seconds or meters), would a scale matter (at least for ANMs) as far as the scale that is used the same (e.g. seconds and seconds but not hours)?\n\n* Figure 1: “The performance of _sortnregress_ … matches that of …” - it is not an exact match. (And someone could argue NOTEARS performs somewhat better than sortnregress in some cases, although it is not clear whether there are significant differences.) It might be worth highlighting that.\n\n* Line 358: “later” - just to check, later to this submission’s first publication (e.g. on arXiv)?\n\nSome other/minor points:\n\n* It might be helpful to define “DAG” in the abstract.\n\n* Line 9: “where varsortability may be absent” - can a measure be absent? (Is it meant that varsortability is low or equal to 0?)\n\n* Line 10: “no longer identify” - do they rather just (sometimes) identify it, generally, much worse? (They still might perform somewhat better than the “randomregress”, e.g. see Figure 1, top-right. Before, they also did not identify it perfectly.)\n\n* Lines 14-15: “[existing?] generic benchmarks”\n\n* Line 43: it might be helpful to define the “MSE”. (It is appreciated that there is some definition after the line 139.)\n\n* Line 94: “i.i.d.” presumably refer to any x^(i) overall (i can be any from 1 to n) and not to dimensions - it might be not clear from the first read although that is probably obvious in this context.\n\n* Line 101: “if and only if” - a reference to a proof might be helpful, even if trivial.\n\n* The equation after line 159: it might be helpful (although probably trivial) to describe what does “i -> j \\in E^k” mean.\n\n* It might be helpful to cover what happens with the varsortability if e.g. a graph does not have any edges.\n\n* More derivation details for section 3.4 might be helpful (e.g. in an appendix section).\n\n* Can varsortability be measured (approximately, using empirical variances) for the real dataset (as in the appendix G)?\n\n* Line 328, “from finite-sample to the population setting” - just to check, is it a reference to sections “D.1 Infinite Sample” and “D.2 Finite Sample” in the appendix (or to some other section(s))?\n\n* Line 360: “score-equivalend” -> “score-equivalent” ?\n\n* Line 371: “is needed to .” - potentially, some missing (or extra) words?\n\n* Note that the appendix was looked at (for some parts) but was not carefully checked.\n\n*\n\nGiven some of the clarity points, although I think this work is very important, I am sorry, sadly I don’t feel comfortable at this point to recommend its acceptance. There is a chance though that: (a) I did misunderstand some points; (b) some points are obvious and they just were not mentioned by the authors; (c) or/and some points are valid and they can be addressed by the camera-ready version submission if the paper is accepted. Given the authors’ rebuttal, to which I am looking forward, there is a chance that the score will be adjusted. Given the importance of the paper, it probably would be very beneficial for the field if it is accepted to facilitate the discussion on this important topic.\n\nAll parts of the review are provided to the best of my understanding and knowledge. Mistakes/misunderstandings in the review are possible. I kindly ask to point me to them, if any, if possible, please.\n\n*\n\n* A discussion point (of the review): The paper topic relates to an important question on whether scales are important for structure learning tasks (and how should benchmarks be constructed; and what should metrics be). If some variables have the same meaning, does it make sense (and is it essential for full possible “identifiability”) to use their scales? (For example, if two variables concern time, is it natural to use seconds and seconds (without any standardisation)? And also, potentially, generally to use a consistent metric system, assuming there are some natural connections between different base units, or/and they can be naturally expressed through one another?)\n** (It also brings an interesting question on how a structure learning algorithm can try to incorporate information about different units that can’t be necessarily naturally expressed through each other (e.g. numbers of people and currency (money) units) using some meaningful statistical information that describes some relationships between them (e.g. an average income or some average expense per a person); but it is out of the scope of this review.)\n\n*\n\n**For the update, please, see my message dated the 2nd of September 2021 (GMT).**\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "* There is a question: to what extent is high varsortability natural in the real world? Is it generally natural? (E.g. for variables where scales can be chosen.) Authors acknowledge this question too (e.g. in lines 375-378). I wonder whether it should be covered a bit more earlier in the paper as well (e.g. in the abstract or on the first pages)?\n** If that is the case (that it is natural), then would it be appropriate to use algorithms that rely on scales in practice (as far as scales are (somewhat) consistent)? Even though (some of) their performance is explained by varsortability, is it fine (and desired?)?\n\n* (I assume it is a general issue in the field, and that is not trivial to resolve:) There seems to be a limited set of real-world, expert-annotated datasets.\n** It is also interesting to note, based on the authors’ note about that, that on the one real-world dataset that was used in the paper, for SID the algorithms perform generally quite similarly (the appendix, line 761) and, if I understand correctly, not very well (although NOTEARS on the raw data seems to be performing relatively well on SID, and sortnregress too).\n\n*\n\nSocietal impact:\n\nThere are generally potential huge positive impacts of the paper, and that is really appreciated: the submission raises questions and contains work that are important for the field and its applications (and that is expected to lead to positive social impact). The authors make a statement regarding that in the paper checklist.\n\n(Further study is required to understand better e.g. whether high varsortability is natural for some real-world data (given some assumptions about scale relationships); the authors make a similar statement in lines 375-378 regarding additive noise models. Note that those further studies would affect further evaluation of different (existing and new) structure learning algorithms (and development of new ones), and further analysis and development of benchmarks and metrics. An obvious potential negative social impact might be if e.g. (a hypothetical scenario) varsortability of real-world datasets would be for some reason generally originally underestimated and if that would for some reason lead to bias towards some algorithms (e.g. if they don’t perform well on standardised data) until later it would be established that high varsortability is actually a natural property (for some real-world data) and identifiability significantly depends on it (again, that is just a hypothetical scenario).)\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "I have not tracked time. I generally conduct a review in a few sub-iterations, to be able to reflect (between them) on a submission/material under review for some time."}, "extra_text": {}}, {"review_id": "n-KxnUDOp8H", "reviewer": "Reviewer_ciTV", "summary": "This paper shows that one needs to be cautious when rescaling your data prior to using a causal structure learning algorithms. The authors introduce the concept of varsortability that measures the agreement in how much the marginal variance tends to increase along the causal order. They show that standardization of your data can hurt performance in identifying the DAG (or its equivalence class) which can be explained by varsortability. The authors claim that this concept of varsortability also explains why even after standardization certain continuous structure learning algorithm perform well. The authors focuses on additive noise models and perform an extensive benchmark.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well written and a pleasure to read. The authors shed some new light on current causal structure learning algorithms by introducing the intuitive concept of varsortability. They show that varsortability is high in common simulation schemes used for benchmarking causal structure learning algorithms. Interestingly, they show that high varsortability may still be exploited after data standardization and may explain why certain continuous structure learning algorithms work so well. They motivate this possible explanation by matching the performance of their algorithm sortnregres to other algorithms. These results, however, do not imply, or proof, that varsortability is a \"causal\" explanation of why other continuous learning algorithms work so well in the presence of high varsortability. In Section 3.4 the authors give a heuristic argument why this is the case, but the paper would be much stronger if the authors could actually proof this, and state precisely under which circumstances this would hold. Part of the arguments of this section could I think be improved upon. For example, the authors state that:\n- line 239: \"We expect the residuals after the first gradient step ... to be larger ...\"\n- line 254: \"b) why performance changes once data is standardized ... causal order.\"\nwithout further explanation. It would be helpful if the authors could elaborate more on this. Nevertheless, the concept of varsortability and the benchmarking results will still be a valuable contribution to NeurIPS.\n\nMinor comments:\n- line 217-221 \"In general, ... causal order.\": What motivates these claims? I think a reference would be appropriate.\n- line 226-229: \"We do not expect combinatorial ... to be dependent on data scale.\"  Why is that?\n- line 310 \"are driven by\": Really? Or should this read as \"may be driven by\"?\n- line 292 \"sortnregress\": Why not emphasize more that this is a novel contribution?\n- Why Figure 1 only for ER-2 graphs and Table 2 only for ER-4 and SF-4 graphs?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One of the limitations of this work was already mentioned in the main review section. Moreover, the authors discuss the further limitations, such as examining the role of varsortability in non-linear and empirical settings in detail in Section 6. The authors aim to raise awareness of the severity by which scaling properties in data may distort structure learning algorithm performance makes this paper a valuable contribution to NeurIPS.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5h"}, "extra_text": {}}, {"review_id": "CDICEjYnfx", "reviewer": "Reviewer_b4Yx", "summary": "The paper considers common DAG simulation schemes and and defines and studies a property that results, which does occur in real data, but which may be specifically exploited by continuous causal structure learning algorithms like NOTEARS and GOLEM which case causal structure learning as a differentiable optimization problem, essentially allowing them to game common benchmarks.\n\nThe key property that results from common DAG simulation schemes is downstream nodes in the causal graph having higher variance. The paper defines \"varsortability\" as the fraction of directed paths of any length which start from a node with strictly lower variance than the node they end in. The paper finds that forward sampling in the linear and additive noise model settings result in varsortability of ~ .7 and ~.9, respectively. \n\nThe paper then goes on to show how varsortability guides the gradient-based steps when continuous causal structure learning algorithms like NOTEARS and GOLEM are used. \n\nNext, the paper caries out simulations which compare combinatorial vs. continuous causal structure learning algorithms (and a baseline that relies only on varsortability to obtain the causal order) in settings where the simulated data is standardized and not standardized. The results show that continuous causal structure learning algorithms show significantly higher performance due to varsortability whereas combinatorial algorithms are roughly unaffected.\n\nThe paper further elaborates that even standardized data where prior to standardization there was high varsortability may still allow allow gaming due to distinct covariance patterns.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presents a very clear and thoughtful analysis of current methods for benchmarking causal discovery algorithms and identifies an important problem, which I don't think has previously been addressed rigorously. \n\nSince the paper also addresses the core question of how we should be benchmarking causal discovery algorithms I think the significance and novelty are both high. \n\nFinally the paper is well written and organized, reviews existing literature thoroughly and the main observations regarding varsortability and continuous causal discovery algorithms are well supported with experiments. \n\nI don't have any significant concerns. My main criticism would be the claims in section 5 remain unclear - this may be more clear in the appendix (which I am unable to review given the overload of papers this NeurIPS cycle), but I still support accepting this paper based on the content in the other sections. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not really discussed - but I don't foresee negative impacts", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: A summary from one of the reviews:

"This paper shows that one needs to be cautious when rescaling your data prior to using a causal structure learning algorithms. The authors introduce the concept of varsortability that measures the agreement in how much the marginal variance tends to increase along the causal order. They show that standardization of your data can hurt performance in identifying the DAG (or its equivalence class) which can be explained by varsortability. The authors claim that this concept of varsortability also explains why even after standardization certain continuous structure learning algorithm perform well. The authors focuses on additive noise models and perform an extensive benchmark."

While the initial reviewer opinions were split, the eventual consensus on this paper is that it brings a valuable message of caution regarding developing and benchmarking causal inference methods with simulated data.
Decision: Accept (Poster)