Causal structure learning, also known as causal discovery, aims to estimate causal relationships between variables as a form of a causal directed acyclic graph (DAG) from observational data. One of the major frameworks is the order-based approach that first estimates a topological order of the underlying DAG and then prunes spurious edges from the fully-connected DAG induced by the estimated topological order. Previous studies often focus on the former ordering step because it can dramatically reduce the search space of DAGs. In practice, the latter pruning step is equally crucial for ensuring both computational efficiency and estimation accuracy. Most existing methods employ a pruning technique based on generalized additive models and hypothesis testing, commonly known as CAM-pruning. However, this approach can be a computational bottleneck as it requires repeatedly fitting additive models for all variables. Furthermore, it may harm estimation quality due to multiple testing. To address these issues, we introduce a new pruning method based on sparse additive models, which enables direct pruning of redundant edges without relying on hypothesis testing. We propose an efficient algorithm for learning sparse additive models by combining the randomized tree embedding technique with group-wise sparse regression. Experimental results on both synthetic and real datasets demonstrated that our method is significantly faster than existing pruning methods while maintaining comparable or superior accuracy.
Figures & tables
Figure 1: An overview of the order-based causal structure learning algorithm. Given an observational dataset, it first estimates a topological order of the underlying causal DAG. Then, it prunes spurious edges from the fully-connected DAG induced by the estimated topological order. This paper focuses on the latter step and aims to propose an efficient and accurate pruning method.
Figure 2: An example of our SARTRE framework. We consider the same example as in Figure 1 , where the estimated topological order π^=(2,3,1,4) is given and we consider to identify the parents of the variable X4 from its candidate parents pa^(4)={2,3,1} . (a) Our method first generates binary representation vectors (ϕ2(X2),ϕ3(X3),ϕ1(X1)) by randomized tree embedding. Then, it learns an additive model f^4(Xpa^(4))=g4,2(X2)+g4,3(X3)+g4,1(X1) , where each shape function is defined by g4,j(Xj)=β4,j⊤ϕj(Xj) . By optimizing the coefficient vectors (β4,2,β4,3,β4,1) through group lasso regression, we can obtain a sparse additive model f^4 . (b) For each shape function g4,j , if β4,j=0 holds, we have g4,j(Xj)=0 for any Xj , which enables us to prune the corresponding candidate parent Xj . In this example, β4,3=0 holds and thus we can prune X3 .
Figure 3: An example of the tree embedding technique. Given an ensemble of decision trees that takes Xj as input, each leaf k of a tree corresponds to an interval rj,k of Xj . Thus, we can obtain a set of intervals Rj by collecting intervals corresponding to the leaves in a given tree ensemble.
Figure 4: Experimental results of baseline comparison on the synthetic datasets. For all the metrics, smaller values are better. The shaded areas indicate the standard deviations over 10 trials. We varied the number of variables d from 10 to 50 . Our SARTRE was significantly faster than the baselines while maintaining comparable or superior SHD and SID.
Figure 5: Experimental results of baseline comparison by varying the number of samples n from 1000 to 5000 on ER1 and ER4 datasets. Our SARTRE was faster than the baselines without significantly degrading SHD and SID.
Figure 6: Experimental results of the high-dimensional cases on ER1 and ER4 datasets. We varied the number of variables by d∈{64,128,256,512} . We observed that our SARTRE was faster and attained better SHD and SID than DAS.
Sachs
fMRI
Method
SHD
SID
Time
SHD
SID
Time
SCORE
43.2
102.4
14.7
19.6
71.8
11.4
DAS
27.6
70.3
6.42
11.6
58.6
4.75
SARTRE
22.7
58.0
3.62
12.9
60.0
3.18
Table 1: Experimental results on real datasets. We sampled each dataset by bootstrap sampling, and repeated this procedure for 10 trials. We can see that our SARTRE was faster than the baselines while maintaining comparable accuracy.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 7: Experimental results of baseline comparison on the synthetic datasets. The shaded areas indicate the standard deviations over 10 trials. We varied the number of variables d from 10 to 50 and fixed the number of samples n to 2000 .
Figure 8: Experimental results of baseline comparison on the synthetic datasets. The shaded areas indicate the standard deviations over 10 trials. We varied the number of samples n from 1000 to 5000 and fixed the number of variables d to 20 .
Figure 9: Experimental results of the high-dimensional cases on ER1 and ER4 datasets. The shaded areas indicate the standard deviations over 10 trials. We varied the number of variables d∈{64,128,256,512} and fixed the number of samples n to 2000 .
Figure 10: Experimental results of the mixed cases. We generated each link function fi as either a linear function or a nonlinear function with probability 0.5 . The shaded areas indicate the standard deviations over 10 trials. While we varied the number of variables d from 10 to 50 and fixed the number of samples n to 2000 in (a), we varied the number of samples n from 1000 to 5000 and fixed the number of variables d to 20 in (b). We observed that our SARTRE performed well even when the link functions are a mixture of linear and nonlinear functions.
Figure 11: Experimental results of the sensitivity analysis on the regularization parameter λ . The shaded areas indicate the standard deviations over 10 trials. We varied the number of variables d from 10 to 50 and fixed the number of samples n to 2000 .
Figure 12: Experimental results of the sensitivity analysis on the regularization parameter λ . The shaded areas indicate the standard deviations over 10 trials. We varied the number of samples n from 1000 to 5000 and fixed the number of variables d to 20 .
Learning causal relations from observational data is challenging because the graph search space grows super-exponentially with the number of variables. Ordering-based methods reduce this space by first identifying the topological ordering, whereas continuous optimization methods explore most likely regions of the space by casting DAG learning as a differentiable objective with an acyclicity constraint. Despite their conceptual appeal, both paradigms face significant scalability limitations in high-dimensional settings, restricting their practical applicability. In this work, we introduce a new formulation for linear causal discovery that tightly integrates these two paradigms to achieve substantial gains in scalability without sacrificing accuracy. Our approach, TriOpt, decomposes the problem into two efficient stages. First, it recovers the topological ordering by exploiting the Sherman-Morrison rank-1 downdate together with the additive structure of linear kernels, enabling fast and scalable ordering estimation. Second, given this ordering, we reformulate structure learning as a convex continuous optimization problem that entirely avoids the need for enforcing costly acyclicity constraints. We theoretically show that, under the true ordering, TriOpt exactly recovers the underlying linear DAG. Empirically, across synthetic, semi-synthetic, and real-world datasets, TriOpt achieves orders-of-magnitude speedups over state-of-the-art linear causal discovery methods in high-dimensional regimes, while maintaining comparable or superior accuracy.
Despite the growing availability of large datasets, causal structure learning remains computationally prohibitive at scale. We revisit sparsest-permutation learning for linear structural equation models and show that exact Cholesky factorization is unnecessary for structure recovery. This observation motivates a support-level relaxation that searches for sparse triangular factors over a precision-support screening graph. The relaxed formulation can be efficiently evaluated via masked zero-fill incomplete Cholesky factorization, enabling scalable comparison of candidate orderings. At the population level, we establish soundness for Markov equivalence class (MEC) recovery under no-cancellation and sparsest Markov representation assumptions, as well as robustness to ordering misspecification. Motivated by these guarantees, we introduce SCOPE, a sparse-Cholesky pipeline that provides a scalable implementation of the relaxed formulation. Experiments on synthetic and real datasets demonstrate that SCOPE matches the MEC recovery accuracy of substantially slower baselines, while achieving significantly reduced runtime and scaling to 10k variables.
Sunmin Oh, Sang-Yun Oh, Gunwoong Park
Department of Statistics, Seoul National University, South Korea · Department of Statistics and Applied Probability, University of California Santa Barbara, CA, USA · Scientific Data Division, Lawrence Berkeley National Laboratory, CA, USA +2
Understanding causal dependencies in observational data is critical for informing decision-making. These relationships are often modeled as Bayesian Networks (BNs) and Directed Acyclic Graphs (DAGs). Existing methods, such as NOTEARS and DAG-GNN, often face issues with scalability and stability in high-dimensional data, especially when there is a feature-sample imbalance. Here, we show that the denoising score matching objective of diffusion models could smooth the gradients for faster, more stable convergence. We also propose an adaptive k-hop acyclicity constraint that improves runtime over existing solutions that require matrix inversion. We name this framework Denoising Diffusion Causal Discovery (DDCD). Unlike generative diffusion models, DDCD utilizes the reverse denoising process to infer a parameterized causal structure rather than to generate data. We demonstrate the competitive performance of DDCDs on synthetic benchmarking data. We also show that our methods are practically useful by conducting qualitative analyses on two real-world examples. Code is available at this url: https://github.com/haozhu233/ddcd.
Hao Zhu, Di Zhou, Donna Slonim
Beth Israel Deaconess Medical Center Harvard Medical School Boston, MA, USA · Department of Computer Science Tufts University Medford, MA, USA