PaperlayerView exact revision on arXiv

Source-linked AI summary

Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game

Alexander G. Reisach, Christof Seiler, Sebastian Weichwald

arXiv:2102.13647v3stat.MLcs.LGstat.ME

TL;DR

The paper asks whether generic simulated DAG benchmarks inadvertently make causal structure identifiable through data scale. It defines varsortability and analyzes how variance patterns affect structure-learning algorithms. High varsortability explains strong performance by some continuous methods and can be matched by a simple baseline, while standardization and real-world measurement scales limit the conclusion.

  • Problem

    Simulated DAG benchmarks may contain unintended scale and variance regularities that make causal structure easier to identify than expected.

  • Method

    The paper introduces varsortability, analyzes variance-driven optimization, and evaluates sortnregress alongside continuous and combinatorial methods on raw and standardized data.

  • Results

    High varsortability explains strong performance by some continuous methods and is matched by sortnregress, whereas standardization causes those methods to fail to recover the ground-truth DAG or its MEC.

  • Takeaways & Limitations

    Benchmark evaluations should report varsortability and distinguish performance obtained from marginal-variance patterns from performance that transfers across data scales.

  • Takeaways & Limitations

    Theoretical results are limited to linear additive noise models, and the conjectured causal role of first gradient steps remains unresolved.

Abstract

from arXiv · show

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.

1 Introduction

Causal discovery benchmarks can inadvertently encode causal direction in data scale, making simulated DAGs easier to identify than expected. The paper investigates this issue and shows that variance-related regularities can explain strong performance by continuous methods.

  • Motivation: Data scale and marginal variance can carry information about causal links and dominate benchmark outcomes.Prior results include ordinary regression-based methods on raw data outperforming causal discovery algorithms when regression-coefficient magnitude was informative.
  • Motivation: Existing identifiability results for additive noise models may require knowledge of the ground-truth data scale.The paper contrasts this scale dependence with scale-invariant methods developed for particular model classes.
  • Motivation: For a two-node additive noise model, inferring direction by MSE selects the lower-variance variable as the cause.This inference is correct under specified error-variance conditions but can reverse when measurement units rescale one variable.
  • Motivation: Continuous methods such as NOTEARS and GOLEM achieve remarkably close graph recovery on simulated data, motivating analysis under standardization.The paper examines how their performance changes when raw marginal variances no longer encode causal order.
  • Contributions: The paper introduces varsortability and a variance-sorting baseline to explain unexpectedly strong benchmark performance.It reports that standardization removes marginal-variance information and that the same algorithms fail to recover the ground-truth DAG in that setting.

2 Background

The paper formalizes acyclic linear additive noise models and contrasts combinatorial structure search with continuous optimization. NOTEARS and GOLEM optimize fit under acyclicity-related formulations using different score assumptions.

  • Model Class: The structural causal model is X = W^⊤X + N, with independent zero-centred noise components and graph edges corresponding to nonzero effects.The adjacency matrix encodes directed effects and parent sets.
  • Structure Learning: Combinatorial algorithms search over candidate structures while estimating parameters for each structure, often using restricted or heuristic traversal.Examples include constraint-based conditional-independence searches and greedy equivalence-class procedures.
  • Structure Learning: Continuous algorithms jointly optimize structures and parameters through differentiable objectives and acyclicity constraints.Differentiable acyclicity enables continuous optimization instead of explicit combinatorial traversal.
  • Continuous Methods: NOTEARS minimizes observational MSE subject to a hard acyclicity constraint.Its score is defined over observations X and weighted structure W.
  • Continuous Methods: GOLEM performs Gaussian maximum likelihood with equal- or non-equal-noise-variance models and soft acyclicity and sparsity constraints.Its objective uses likelihood terms based on MSE and omits a determinant term that vanishes for DAGs.

3 Varsortability

Varsortability measures how closely increasing marginal variance follows causal order and can make simulated structures identifiable. The paper connects this pattern to continuous optimization behavior and proposes sortnregress as a diagnostic baseline.

  • Definition and Identifiability: Varsortability is the agreement between increasing marginal variance and causal order, measured over directed paths.At maximal varsortability, the causal order is identifiable from marginal variances.
  • Benchmarking Scenarios: Marginal variance contributions combine direct noise with weighted ancestor effects, whose path products can cancel or be damped but are unlikely to do so under independent edge sampling.Common ancestors or mediators can either compound or partially cancel effects; empirically varsortability increases with graph density.
  • Definition and Identifiability: When varsortability v = 1, sorting nodes by increasing variance gives a valid causal order for sparse parent selection.Regressing each node on predecessors can then reconstruct the graph under mild assumptions in the sample limit.
  • Benchmarking Scenarios: Independent sampling of edge weights and noise variances commonly produces high varsortability in synthetic benchmarks.For W iid∼Unif((0.5, 2)), neighboring pairs are varsortable with probability at least 2/3, and empirically average varsortability exceeds 0.94 in simulated graphs and 0.71 in many nonlinear ANMs.
  • Optimization Effects: High varsortability produces larger initial gradient steps toward low-variance nodes, predominantly the anti-causal direction.The paper conjectures that these early steps can influence pruning and final structure, despite later optimizer, constraint, and penalty interactions.
  • sortnregress: sortnregress sorts nodes by marginal variance and performs parent selection, providing a reference for performance achievable from data scale alone.Its performance reflects varsortability and can be extended with nonlinear regression for nonlinear additive noise models.

4 Simulations

The simulations compare causal discovery algorithms on raw and standardized synthetic data across graph, noise, and size settings. High raw-data varsortability coincides with strong performance from variance-based and continuous methods, while standardization substantially harms several algorithms.

  • Experimental setup: Synthetic experiments vary noise distributions, graph types, and graph sizes, using raw data and de-meaned, unit-variance standardized versions.ER and scale-free graphs are sampled, with performance evaluated over repeated instances.
  • Raw-data performance: In ER-2 Gaussian-NV experiments, sortnregress matches NOTEARS and GOLEM despite exploiting only varsortability.Figure 1 reports SID and SHD for graph and Markov-equivalence-class recovery across 50- and 10-node settings.
  • Evaluation: SID and SHD are measured against ground-truth graphs and, additionally, against ground-truth Markov equivalence classes.The latter separates DAG-recovery failures from losses beyond identifiability expectations.
  • Raw versus standardized data: NOTEARS, MSE-GDS, and GOLEM-EV perform excellently on raw data but far worse after standardization, revealing strong scale sensitivity.GOLEM-NV is also scale-sensitive but improves upon standardization.
  • Raw versus standardized data: Sortnregress is competitive on raw data and reaches baseline performance on standardized data, making it a diagnostic for variance-driven task difficulty.Its standardized version is equivalent to random ordering followed by regression on predecessors.

5 Gaming Further Benchmarks

The paper tests whether benchmark artifacts persist beyond raw marginal variances. Standardization and scale harmonization can remove variance ordering, yet high-varsortability generators retain covariance or nonlinear patterns that support above-chance or competitive naive baselines.

  • Scale-harmonized data: Scale harmonization equalizes variable scales under independently standard-normal direct parents but does not eliminate inadvertent patterns in simulated additive noise models.Previously high-varsortability DAGs can still generate distinct covariance patterns after standardization or harmonization.
  • Orienting causal chains: A decision rule orients a causal chain above 50% accuracy from raw, standardized, and scale-harmonized data when edge weights and noise terms are iid.The comparison is between two Markov-equivalent chain orientations.
  • Orienting causal chains: Downstream nodes can retain stronger parent-variance contributions relative to noise, producing correlations that reveal chain orientation after standardization.This is the stated intuition for residual orientation information beyond marginal variance.
  • Nonlinear settings: Variance sorting in nonlinear additive Gaussian-process ANMs performs substantially better than random sorting, although its fully connected output precludes SHD evaluation.Table 2 reports SID on 1000 observations with ten repetitions and average varsortability by graph type.
  • Nonlinear settings: The results indicate that exploiting varsortability can deliver competitive results in nonlinear settings, where similarly high varsortability occurs across many functional relationships and graph parameters.The authors recommend testing variance-based baselines in future benchmarks while noting open comparisons with other nonlinear methods.

6 Discussion and Conclusion

The discussion argues that scaling properties can make simulated DAGs unexpectedly identifiable and inflate apparent algorithmic performance. It recommends treating varsortability as a benchmark property while delimiting the theory and empirical scope.

  • Discussion and conclusion: Scale-variant structure-learning methods are highly susceptible to rescaling and should be benchmarked cautiously when variables lack a shared or attainable measurement scale.The paper also stresses declaring whether input data were standardized.
  • Discussion and conclusion: Simulated DAGs can become identifiable through increasing marginal variances, including settings where identifiability may not ordinarily be expected.The paper frames varsortability as a benchmark property that can distort algorithm comparisons.
  • Discussion and conclusion: The paper concludes that varsortability should inform future benchmarking, while real-world algorithms may perform within the range of naive baselines.This consequence is stated as a motivation for more representative benchmarks.
  • Limitations: The theoretical results are limited to linear additive noise models, while causal explanations involving initial gradient steps remain unresolved.The authors also state that broader algorithmic effects and claims about standardized or nonlinear benchmarks need further research.
  • Discussion and conclusion: For a two-node linear model, MSE-based orientation is correct for every nonzero edge weight when the parent noise variance does not exceed the child noise variance.This links variance-based orientation to scale-based identifiability results with equal or increasing error variances.

B Derivation of Lower Bound on Pairwise Varsortability

For randomly sampled additive noise models, marginal variances across simulations depend on sampled noise variances and edge weights, allowing lower bounds on pairwise varsortability. Varsortability is related to, but distinct from, Park’s sufficient identifiability conditions.

  • Lower-bound setup: Marginal variances of nodes are random transformations of sampled noise variances and edge weights across simulated additive noise models.A node’s variance depends on its noise variance and variance contributions from predecessor nodes.
  • Lower-bound setup: The marginal variance of a node includes its noise variance plus additional variance contributed by predecessor nodes.For a node Y, predecessor contributions are represented through terms involving P_X→Y V_X.
  • Pairwise bound: For a two-node edge, pairwise varsortability can be bounded from below using the distributions of the two nodes’ marginal variances.Equality holds when A is the only parent contributing to B’s marginal variance.
  • Benchmark sampling: Common benchmarks independently sample edge weights from Unif((−2, −.5)∪(.5, 2)) and noise standard deviations from Unif(.5, 2).These sampling choices induce distributions over simulated marginal variances.
  • Relation to identifiability: Varsortability is not equivalent to Park’s Theorem 4 conditions: either condition can hold without the other.The supplied examples include one satisfying part A without varsortability and another with varsortability but neither part A nor part B.

C.2 Varsortability without Park, 2020, Theorem 4 conditions satisfied

A constructed three-node model has increasing marginal variances despite violating Park’s sufficient conditions, illustrating that varsortability can identify causal order independently of those conditions. The section also connects variance ordering to optimization behavior in several structure-learning algorithms.

  • C.2 Varsortability without Theorem 4: The model has causal order A, B, C and marginal variances Var(A) = 4 < Var(B) = 7 < Var(C) = 10.5.At least one inequality in each of Park’s criteria A) and B) is violated.
  • C.2 Varsortability without Theorem 4: Varsortability may identify causal order even when neither of Park’s sufficient criteria is satisfied.The example verifies that at least one inequality fails in both criteria A) and B).
  • D Algorithms: DirectLiNGAM iteratively selects the node whose residuals are least dependent on predecessor nodes and returns a DAG.In strictly non-Gaussian settings, it is guaranteed to converge asymptotically to the optimal solution within a small fixed number of steps.
  • D Algorithms: MSE-GDS greedily inserts edges using mean squared error as its score criterion and estimates edge weights by regression.The implementation searches a smaller space of forward edge insertions and returns a DAG.
  • D Algorithms: NOTEARS jointly learns structure and parameters by minimizing MSE with a sparsity penalty and differentiable acyclicity constraint.The supplied formulation includes λ∥W∥1 and tr(exp(W ⊙W)) − d = 0.
  • E.3 Increasing Marginal and Residual Variances: For small step sizes, marginal-variance ordering and residual-variance ordering remain aligned during the first optimization steps of MSE- or likelihood-based gradient descent.This alignment is observed for objectives optimized by gradient descent, including GOLEM-EV/-NV.
  • E.4 Gradient Asymmetry: GOLEM-NV’s first gradient step tends to favor anti-causal directions under high varsortability because incoming gradients are inversely scaled by marginal variance.For opposing edges, the larger first step favors the direction whose endpoint has lower variance.
  • E.5 NOTEARS: NOTEARS line-search can produce residual-variance orderings that differ from marginal-variance orderings after the first step, while later acyclicity pressure tends to remove edges into lower-variance nodes.The optimized step targets overall MSE, making changes to edges into high-variance nodes more costly in MSE terms.

F.1 Infinite Sample

For iid-sampled linear ANMs, a regression-based rule identifies the orientation of causal chains above chance across raw, standardized, and scale-harmonized data. Variance ordering is highly informative in common benchmark settings, including nonlinear ANMs and larger graphs.

  • Chain orientation: The chain-orientation task distinguishes two Markov-equivalent directions using pairwise regression-coefficient magnitudes.The rule compares whether absolute coefficients tend to increase from left to right or right to left, otherwise guessing.
  • Chain orientation: The orientation rule achieves above-chance accuracy for raw, standardized, and scale-harmonized data under iid parameter sampling.The empirical setup uses 1000 observations and varies chain lengths and edge distributions.
  • Chain orientation: Variance-sorting is the only evaluated setting without above-chance orientation accuracy after standardization.Standardization makes variance sorting equivalent to random sorting because nodes no longer differ in marginal variance.
  • Varsortability: Varsortability is close to 1 across graph and noise types in the linear experiments and is higher in denser graphs.The linear setup samples 1000 observations of ten 50-node graphs for each graph/noise combination.
  • Varsortability: All nonlinear experimental settings also exhibit high average varsortability, indicating that the concern extends beyond linear ANMs.The nonlinear setup uses 1000 observations of ten 20-node graphs for each graph and ANM type.
  • Causal order and variance: Marginal variance tends to increase rapidly along the causal order, making high varsortability difficult to avoid on larger graphs.This pattern is observed empirically even when parameter settings do not guarantee high pairwise varsortability.

H.2 Varsortabiltiy and Score Attainable by Variance Ordering

Variance ordering is a strong baseline when varsortability is high: its score improves linearly with varsortability and can nearly recover the structure in the benchmark regime.

  • Score versus varsortability: Sortnregress improves linearly with varsortability and recovers the structure near-perfectly at varsortability 0.93.Randomregress uses a random ordering while otherwise matching sortnregress.
  • Score versus varsortability: Below 0.33 varsortability, sortnregress performs significantly worse than randomregress (p<1e-4).Variance ordering is disadvantageous in the low-varsortability regime.
  • Score versus varsortability: Between 0.33 and 0.66 varsortability, sortnregress and randomregress do not differ significantly (p=0.40).The two ordering strategies are statistically indistinguishable in this intermediate regime.
  • Score versus varsortability: Above 0.66 varsortability, sortnregress significantly outperforms randomregress (p<1e-4).This identifies the high-varsortability regime in which variance ordering provides a substantial advantage.
  • Score versus varsortability: Most models under standard simulation settings have high varsortability, requiring rejection of many models to populate low-varsortability bins.Figure 3 uses ten simulated 10-node ER-1 graphs in each of ten equally spaced bins.

I Evaluation on Real-World Data

On protein-signaling data, no algorithm dominates, and most methods perform similarly to random regression or the empty-graph baseline.

  • Protein-signaling evaluation: On ten bootstrap samples of the Sachs protein-signaling dataset, no evaluated algorithm dominates.The observational data contain 853 observations, 11 nodes, and 17 edges.
  • Protein-signaling evaluation: Most algorithms achieve average performance similar to randomregress or the empty graph.The reported SHD results are sensitive to thresholding choices and the empty-graph baseline.
  • Protein-signaling evaluation: Figure 4 reports SID and SHD performance for combinatorial and continuous methods on real-world data.The figure presents the two structural-recovery metrics side by side.

J Model Selection in Continuous Optimization

Continuous optimization is affected by data scale: standardization changes the loss landscape and improves Lasso calibration, yet performance drops extend beyond choosing the correct DAG within a Markov equivalence class.

  • Loss landscape: With Lasso penalty 0.1, the optimal loss is achieved by the true structure more frequently after standardization.The result is described through the accumulation of true-structure points in the loss-landscape plot.
  • Loss landscape: Lasso sparsity penalization is influenced by data scale and is better calibrated on standardized data.The authors identify scale dependence as a property of penalization.
  • Loss landscape: The standardized Gaussian MLE loss landscape compares 25 candidate graphs against 25 possible three-node ground-truth structures using loss scaled to [0, 1].The analysis compares vanilla MLE with Lasso regularization on raw and standardized data.
  • MEC recovery: MEC recovery is evaluated separately because only the ground-truth MEC, not the exact DAG, is identifiable under non-equal Gaussian noise.This analysis isolates whether performance drops are compatible with DAG non-identifiability within an MEC.
  • MEC recovery: The performance drop extends from DAG recovery to MEC recovery, beyond difficulty identifying the correct DAG within an MEC.Thus, the decline is not explained solely by ambiguity among Markov-equivalent DAGs.

K.2 Results Across Thresholding Regimes

Across thresholding regimes, relative algorithm performance remains nearly unchanged for both SID and SHD. The effects associated with varsortability therefore persist across favorable and fixed thresholds and across raw versus standardized comparisons.

  • Thresholding setup: Thresholding was evaluated across different regimes because standardization can alter edge weights and affect pruning.The experiments include thresholding for continuous structure learning algorithms and prune edges based on edge weight.
  • SID: SID relative performances are nearly identical even when thresholds differ by orders of magnitude.Figure 7a and Figure 7b compare different threshold choices.
  • SHD: SHD relative performances are nearly identical under both instance-specific favorable thresholds and a fixed threshold of 0.3.The favorable threshold is selected separately for each instance, whereas the fixed-threshold regime uses 0.3.
  • Robustness: Varsortability effects remain present with the most favorable SHD threshold and across a wide SID threshold range.Computing a favorable SID threshold for each instance is described as computationally infeasible.
  • Cross-setting comparison: Raw-versus-standardized differences are qualitatively similar across noise distributions, while DirectLiNGAM performs well only in non-Gaussian cases.The comparison includes different graph types in the non-Gaussian setting; DirectLiNGAM’s behavior matches its identifiability assumptions.
Loading 2102.13647v3…