Source-linked AI summary
Causal Discovery in Equal Variance Linear Gaussian DAGs via SURE-Tuned Ridge Regression
Sambit Mishra, Urbashi Mitra
TL;DR
Recovering DAGs from observational data is challenging when samples are scarce or computation is constrained. SURE-Ridge uses SURE-tuned closed-form ridge regressions with adaptive thresholding, achieving the lowest SHD in sparse sample-limited settings and faster runtime than NOTEARS, DAGMA, and GBNSL across tested sample sizes.
Problem
Causal discovery requires recovering DAG structure in equal-variance linear Gaussian SEMs, including sparse sample-limited settings where existing approaches are less suited.
Method
SURE-Ridge combines parallel node-wise ridge regressions with SURE-tuned regularization and adaptive thresholding to extract a DAG without per-problem hyperparameter tuning.
Results
SURE-Ridge achieves the lowest SHD in sparse sample-limited regimes and substantially faster runtime than NOTEARS, DAGMA, and GBNSL across every tested sample size.
Takeaways & Limitations
SURE-Ridge offers an accuracy–compute tradeoff for causal discovery applications constrained by samples or computational resources.
Takeaways & Limitations
In rare fallback cases, the extracted graph may contain a small number of cycles.
Abstract
from arXiv · showhide
Recovering the directed acyclic graph (DAG) of a structural equation model (SEM) from observational data is a central problem in causal discovery. The iterative gradient descent and per-problem hyperparameter tuning of continuous-optimization methods are poorly suited to two practically important regimes: the sample-limited regime, where the number of samples is comparable to or smaller than the number of nodes in the DAG, and the compute-limited regime. This work proposes SURE-Ridge, a non-iterative, closed-form estimator for equal variance linear Gaussian SEM. The method performs parallel node-wise regressions with regularization parameters chosen adaptively by Stein's unbiased risk estimate (SURE), and applies an adaptive thresholding procedure to extract a DAG from the resulting soft adjacency matrix. Numerical results show that SURE-Ridge achieves the lowest structural Hamming distance in the small-sample regime and the lowest run time across all sample sizes tested, compared with NOTEARS, DAGMA, and GBNSL baselines.
I. INTRODUCTION · II. SYSTEM MODEL
The paper studies identifiable equal-noise linear Gaussian DAG recovery from observational data and proposes SURE-Ridge, a non-iterative closed-form estimator based on parallel node-wise ridge regressions. It models a d-node causal DAG through a weighted adjacency matrix and i.i.d. observations generated by an equal-variance linear Gaussian SEM.
- I. INTRODUCTION: Equal-noise linear Gaussian SEMs make the true DAG identifiable from the joint distribution alone.
- I. INTRODUCTION: Classical and continuous-optimization methods scale poorly or require thousands of gradient steps and per-problem hyperparameter tuning.
- I. INTRODUCTION: SURE-Ridge uses parallel node-wise ridge regressions with L2 regularization selected by minimizing Stein’s unbiased risk estimate.SURE estimates prediction error without held-out data or iterative search, which is advantageous when samples are scarce.
- I. INTRODUCTION: The method combines a closed-form estimator with adaptive thresholding that uses two scale-invariant constants and typically produces a valid DAG.
- I. INTRODUCTION: SURE-Ridge achieves the lowest structural Hamming distance in the small-sample regime and the lowest run time across all tested sample sizes against NOTEARS, DAGMA, and GBNSL.
- II. SYSTEM MODEL: The system model defines a d-node causal DAG G = (V, E), with V as the node set and E containing directed edges i → j.
- II. SYSTEM MODEL: The graph is represented by a weighted adjacency matrix W, while each node i has a causal-coefficient row-vector wi formed by removing Wii from row i.
- II. SYSTEM MODEL: For each node, xi contains n i.i.d. observations, and the full observation matrix X ∈ R^d×n concatenates the node-wise data under an equal-noise linear Gaussian SEM.
III. SURE-TUNED RIDGE REGRESSION
SURE-Ridge estimates each causal coefficient vector through node-wise ridge regression, selecting regularization by a per-node SURE risk objective. An eigendecomposition yields an efficient closed-form objective, and the resulting soft adjacency matrix is thresholded into a DAG estimate.
- Ridge estimation: Each causal coefficient vector w_i is estimated from noisy observations using ridge regression with a node-specific regularization parameter λ_i.The Gram matrix G_i is formed from the observations of the other nodes.
- SURE tuning: SURE provides a data-driven, principled criterion for selecting λ_i by estimating the expected squared-error risk of the ridge estimator.The resulting objective is optimized separately for each node i ∈ V.
- Efficient objective: Eigendecomposition of G_i transforms the SURE objective into scalar functions of λ_i that cost O(d −1) per grid point to evaluate.The transformation uses eigenvectors U_i, eigenvalues Γ_i, and projected observations z_i.
- DAG extraction: Concatenating the optimal node-wise estimates produces a soft adjacency matrix with zero diagonal, whose adaptive thresholding yields a DAG estimate.The estimator is described as capturing the population-level regression structure supporting identifiability under equal noise variance.
IV. ADAPTIVE THRESHOLDING
The method extracts a valid DAG from the generally non-DAG soft adjacency matrix using a three-stage adaptive thresholding procedure. It combines a signal-scaled floor, discrete bisection, and a fallback that preserves informative edges when bisection is too aggressive.
- The soft adjacency matrix is typically not a DAG, so the method applies thresholding to extract a valid DAG structure.
- It first sets an absolute floor threshold that scales with the signal magnitude.
- It then performs a discrete bisection search over magnitudes above the floor.
- Finally, it uses a fallback to preserve informative edges when bisection becomes too aggressive.
A. Acyclicity Test · B. Signal-Scaled Floor Filter
The method tests candidate thresholded graphs with a numerically stable polynomial acyclicity functional that vanishes exactly for DAGs. It complements this test with a signal-scaled floor filter that removes ridge-shrinkage noise while adapting to dimension and signal-to-noise conditions.
- A. Acyclicity Test: The polynomial acyclicity functional satisfies h(W) = 0 if and only if W represents a DAG.It is a numerically stable variant of the originally proposed matrix-exponential form.
- A. Acyclicity Test: The functional is evaluated on candidate thresholded graphs during DAG extraction.
- A. Acyclicity Test: Acyclicity evaluation vectorizes trivially across batches of candidate matrices.
- B. Signal-Scaled Floor Filter: The procedure introduces a scale-adaptive floor because zero thresholding retains ridge-shrinkage noise and zero-start bisection can return an empty graph.
- B. Signal-Scaled Floor Filter: The floor uses tunable hyperparameters η0 and β governed by node count d and expected signal-to-noise ratio.
- B. Signal-Scaled Floor Filter: In small-to-moderate-d or high-SNR settings, the β-scaled term tracks maximum signal magnitude and aggressively filters spurious correlations.
- B. Signal-Scaled Floor Filter: In large-d or low-SNR regimes, η0 provides an absolute safety bound when ridge regularization suppresses maximum edge weights toward the noise floor.
- B. Signal-Scaled Floor Filter: The first filtering stage zeroes out every entry below ηmin.
C. Bisection Over Above-Floor Magnitudes
When Wfloor remains cyclic, the method searches larger threshold candidates until acyclicity is restored. Because acyclicity is upward-closed on the sorted candidate list, discrete binary search finds the smallest acyclic candidate efficiently.
- The procedure searches for a larger threshold when Wfloor is still cyclic, aiming to restore acyclicity.
- The candidate set is formed from {ηmin} and n, then sorted in ascending order.
- At most ⌈2 log2 d⌉ acyclicity checks are required to locate the smallest acyclic candidate η∗ via discrete binary search.The resulting estimate is denoted Wbisect.
D. Fallback for Aggressive Cuts
The fallback prevents aggressive bisection from producing an uninformative near-empty DAG by prioritizing edge preservation over strict acyclicity. It returns the floor-thresholded matrix when bisection removes too many edges; otherwise, it returns the acyclic bisected matrix.
- Fallback motivation: Aggressive bisection can remove most floor-thresholded edges to break few cycles, producing a less-informative near-empty DAG.The fallback is designed to guard against this outcome.
- Fallback motivation: The fallback prioritizes edge preservation over strict acyclicity, so its output may contain a small number of cycles in rare cases.West is a valid DAG when the floor or bisection stage succeeds, as commonly occurred numerically.
- Fallback rule: If ||Wbisect||0 < 1/2||Wfloor||0, the algorithm returns Wfloor; otherwise, it returns Wbisect.The comparison determines whether bisection discarded too many edges relative to the floor-thresholded matrix.
V. NUMERICAL RESULTS AND DISCUSSION · A. Experimental Setup
The experiments evaluate SURE-Ridge on sparse equal-variance Gaussian SEMs with 20 or 50 nodes under repeated Monte Carlo trials. Comparisons include NOTEARS, DAGMA, and GBNSL using shared trial data and specified optimization settings.
- A. Experimental Setup: Synthetic graphs contain d ∈ {20, 50} nodes and ⌈2d/5⌉ edges, sampled from a sparse random-DAG distribution.This targets a sparse sub-Erdős–Rényi-1 average in-degree regime.
- A. Experimental Setup: Nonzero edge weights are sampled uniformly from [−2.0, −1.0] ∪ [1.0, 2.0], with noise variance fixed at σ^2 = 1.Each setting uses 100 Monte Carlo trials.
- A. Experimental Setup: Each method observes the same (W_true, X) in every trial, enabling fair comparisons against the ground-truth DAG adjacency matrix.W_true denotes the ground-truth DAG adjacency matrix.
- A. Experimental Setup: SURE-Ridge is compared with NOTEARS, DAGMA, and GBNSL.NOTEARS solves an ℓ1-regularized least-squares problem subject to h(W) = 0, while DAGMA uses a log-determinant acyclicity constraint.
- A. Experimental Setup: DAGMA uses better-behaved log-determinant gradients and replaces augmented-Lagrangian optimization with a central-path sequence of unconstrained subproblems.The constraint is h_ldet(W; s) = −log det(sI_d − W ⊙ W) + d log s.
- A. Experimental Setup: GBNSL uses successive node pruning based on sparse precision-matrix and Markov-blanket regression estimates, without gradient-based optimization.Under equal noise variance, it identifies leaf nodes iteratively and updates the precision estimate through a rank-1 Schur complement.
- A. Experimental Setup: NOTEARS and DAGMA start from zero with a matched budget of 32000 Adam steps, learning rate 3×10^−4, and L1 penalty 5×10^−2.NOTEARS uses 32 outer iterations of 1000 inner steps, whereas DAGMA uses four central-path stages of 8000 inner steps.
- A. Experimental Setup: Structural Hamming distance is defined as the minimum number of edge insertions, deletions, or reversals needed to transform one graph into another.The implementation code is provided in the cited repository.
B. Sample Efficiency
Sample efficiency is regime-dependent: SURE-Ridge has the lowest normalized SHD when n is on the order of d or smaller, while GBNSL improves fastest and eventually overtakes the iterative baselines and slightly surpasses SURE-Ridge.
- Sample Efficiency: In the sample-limited regime, SURE-Ridge attains the lowest normalized SHD by a substantial margin, with the gap widening as d grows.This advantage appears for both d = 20 and d = 50 and is not a small-d artifact.
- Sample Efficiency: At very small n, GBNSL performs worst, with normalized SHD close to 1 for d = 50.The passage relates this behavior to the high-dimensional regime, where GBNSL’s CLIME-based precision-estimate guarantees do not yet apply.
- Sample Efficiency: As n grows, GBNSL improves fastest, overtakes the iterative baselines near n ≈2d, 3d, and slightly surpasses SURE-Ridge near the sweep’s upper end.The ordering therefore changes with sample size, and GBNSL eventually reaches parity with SURE-Ridge.
C. Run Time Comparison · D. Discussion · VI. CONCLUSIONS
SURE-Ridge combines closed-form, SURE-tuned node-wise ridge regressions with adaptive DAG extraction, achieving strong small-sample accuracy and substantially faster runtimes than the evaluated baselines. Its speed derives from independent regressions that avoid gradient descent, while future work will study sample complexity and convergence.
- C. Run Time Comparison: At d = 50, SURE-Ridge is roughly two orders of magnitude faster than the iterative baselines.GBNSL is roughly one order of magnitude faster than the iterative methods, while SURE-Ridge is another magnitude below GBNSL.
- C. Run Time Comparison: All four runtimes are essentially flat in n.The comparison includes NOTEARS, DAGMA, GBNSL, and SURE-Ridge.
- D. Discussion: SURE-Ridge’s speed advantage comes from d independent closed-form regressions that eliminate gradient descent.Equal variance decouples the node-wise subproblems, while SURE adapts shrinkage without held-out data.
- D. Discussion: Sparse DAGs make shrinkage informative because most node-wise regression coefficients are zero.SURE adapts regularization strength without held-out data.
- VI. CONCLUSIONS: SURE-Ridge is a non-iterative, closed-form estimator combining d node-wise ridge regressions, SURE-tuned regularization, and adaptive thresholding for DAG extraction.The method requires no per-problem hyperparameter tuning.
- VI. CONCLUSIONS: SURE-Ridge achieves the lowest SHD in the sparse, sample-limited regime against NOTEARS, DAGMA, and GBNSL baselines.This result is reported on synthetic Gaussian SEMs.
- VI. CONCLUSIONS: SURE-Ridge has a substantially faster run time than NOTEARS, DAGMA, and GBNSL across every sample size tested.The authors describe this as an accuracy–compute tradeoff for constrained applications.
- VI. CONCLUSIONS: Future work will assess SURE-Ridge’s sample-complexity and convergence.These are identified as open directions in the conclusions.