Efficient Differentiable Causal Discovery via Reliable Super-Structure Learning

Causal inference has evolved from classical constraint-based and score-based methods to modern differentiable approaches like NOTEARS, which reformulate structure learning as a continuous optimization problem. These methods excel in low-dimensional settings but face scalability issues as the number of variables grows, especially with latent confounders that induce dense, spurious correlations. Graphical Lasso and related super-structure learning techniques have been employed to constrain search spaces, yet they struggle with high-dimensionality and hidden variables, often leading to ill-conditioned matrices and unreliable super-structures. The need for robust, scalable super-structure learning methods that can handle confounding and high-dimensionality remains urgent, motivating the development of ALVGL.

Identifying causal structures in high-dimensional data with latent confounders is computationally intensive due to the exponential growth of possible graphs. Existing methods either lack robustness against confounders or fail to scale efficiently, often producing inaccurate or cyclic graphs. The core challenge is to develop a super-structure that reliably bounds the true causal graph, reduces search space, and remains stable under high-dimensional and confounded conditions, enabling downstream differentiable causal discovery methods to operate effectively.

ALVGL introduces a sparse+low-rank decomposition of the precision matrix, capturing direct causal links and shared confounding effects simultaneously. This decomposition is optimized via ADMM, ensuring scalability and convergence stability. The super-structure derived from this decomposition provably contains the true causal graph, providing a reliable initialization for existing differentiable methods like NOTEARS. This approach effectively addresses the limitations of graphical Lasso in high-dimensional, confounded settings, offering a unified, theoretically guaranteed framework for super-structure learning.

• �� Model the precision matrix as a sum of sparse and low-rank components, representing direct effects and confounding influences.
• �� Use ADMM to alternately optimize the sparse and low-rank parts, ensuring convergence and scalability.
• �� Derive a super-structure by thresholding the combined components, capturing potential causal edges.
• �� Integrate the super-structure into differentiable causal discovery algorithms, constraining their search space.
• �� Theoretically prove that the super-structure contains the true causal graph, providing guarantees for downstream inference.

Datasets include synthetic data with known causal structures and real-world datasets like Sachs. Baselines include NOTEARS, GLasso, and other super-structure methods. Metrics focus on F1 score, runtime, and robustness under confounding. Hyperparameters like regularization λ are tuned via cross-validation. Ablation studies analyze the impact of sparse vs. low-rank components. Results demonstrate superior accuracy and efficiency, especially in high-dimensional, confounded scenarios.

ALVGL achieves an average F1 increase of 3.3% over baselines, with runtime halved. It maintains stable performance in high dimensions (d≥100), avoiding matrix ill-conditioning. In confounded settings, it outperforms GLasso and other methods, with F1 scores improved by over 3%, and runtime reductions exceeding 75%. These results validate the effectiveness of the sparse+low-rank approach and the theoretical guarantees.

Applicable in genomics for gene network inference, economics for causal policy analysis, and social sciences for understanding complex social interactions. Its robustness to confounders makes it suitable for real-world datasets with hidden influences. The method can serve as a pre-processing step for large-scale causal inference pipelines, enabling more accurate and scalable analysis.

Limited to linear Gaussian models; extending to nonlinear or non-Gaussian cases is non-trivial. Computational costs remain high for ultra-high-dimensional data, requiring further optimization. Performance may degrade with extremely small sample sizes or very dense graphs, necessitating additional regularization or prior knowledge.