Differentiable Structure Learning for Cyclic Linear Gaussian Models with Latent Confounders

Sadegh Khorasani; Ali Najar; Saber Salehkaleybar; Negar Kiyavash

cs.LGSep 29, 2026

Differentiable Structure Learning for Cyclic Linear Gaussian Models with Latent Confounders

Authors: Sadegh Khorasani, Ali Najar, Saber Salehkaleybar, Negar Kiyavash

Organizations: School of Computer and Communication Sciences, EPFL, Lausanne, Switzerland · Leiden Institute of Advanced Computer Science (LIACS), Leiden University, Leiden, The Netherlands · College of Management of Technology, EPFL, Lausanne, Switzerland

Abstract

We study causal structure learning from observational data in linear Gaussian structural causal models in the presence of directed cycles and an unknown number of exogenous latent confounders, bounded by a given maximum. We derive the covariance of the observed variables and introduce marginal quasi-equivalence, which characterizes when different causal models share a full-dimensional subset of the observational distributions they can generate. We formulate structure learning as minimization of the Gaussian negative log-likelihood with a logarithmically scaled complexity penalty that counts directed edges and latent variables. For a fixed number of observed variables and a fixed upper bound on latent variables, we establish consistency of global score minimizers up to marginal quasi-equivalence under algebraic faithfulness, structural minimality, and model-overlap assumptions. We parameterize the inclusion of directed edges and candidate latent variables using Bernoulli gates, whose continuous probabilities are optimized jointly with the structural coefficients. Averaging the penalized negative log-likelihood over these gates yields an objective with a closed-form differentiable complexity penalty. We prove that this expected objective has the same global infimum as the corresponding discrete structure-learning objective. Experimental results show that our approach achieves lower recovery error than previous methods in several experimental settings.

Figures & tables

Panel of Figure 1 — Figure 1: Synthetic results across 10 trials. Compatibility error for varying number of observed variables, the maximum observed degree, and the latent-to-observed ratio.

Latents	Method	$d_{\mathrm{fwd}}\downarrow$	$d_{\mathrm{rev}}\downarrow$	$(d_{\mathrm{fwd}}+d_{\mathrm{rev}})\downarrow$	Time (s) $\downarrow$
20	Ghassami et al. (2020)	$16.57\pm 0.23$	$22.78\pm 2.87$	$39.35\pm 2.71$	$615.40\pm 45.48$
	DCCD-CONF	$28.01\pm 1.67$	$10.03\pm 0.43$	$38.05\pm 1.91$	$1334.86\pm 0.55$
	Amendola et al. (2020)	$22.97\pm 0.24$	$93.54\pm 7.43$	$116.51\pm 7.65$	$1464.31\pm 166.35$
	Ours	$\mathbf{16.33\pm 0.25}$	$\mathbf{3.31\pm 0.13}$	$\mathbf{19.63\pm 0.24}$	$\mathbf{47.92\pm 0.07}$
30	Ghassami et al. (2020)	$\mathbf{16.28\pm 0.59}$	$24.75\pm 1.59$	$41.03\pm 1.80$	${743.09\pm 58.81}$
	DCCD-CONF	$36.61\pm 4.93$	$11.12\pm 0.93$	$47.73\pm 5.08$	$1352.79\pm 8.69$

Table 1: GeneNetWeaver results with 100 observed variables. Values are mean

\pm

SEM across 10 trials.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Structure optimization
Setting	Value
Mask samples per update	$256$
Adam learning rate	$10^{-2}$
Binary Concrete temperature	$\tau=1$ (fixed)
Structure-search initializations	$1$ per trial
Initial observed-edge probability	$0.01$

Appendix

Table 2: Principal numerical settings used in the experiments.

Panel of Figure 3 — Figure 3: Sensitivity to graph density and latent confounding. Rows correspond to latent ratios $\ell/p$ of $10\%$ , $20\%$ , and $30\%$ , and columns to maximum observed degrees of $1$ , $2$ , and $4$ . Points show mean $d_{\mathrm{fwd}}+d_{\mathrm{rev}}$ with SEM across trials; lower is better.

Explore similar work

Sep 16, 2026cs.LG

Provable Guarantees and Efficient Learning of Structural Equation Models with Latent Confounders

Causal discovery aims to recover causal relationships from observed data. In various fields, exploring causal relationships among variables remains an important topic, but this task becomes challenging due to the existence of latent confounders. Ignoring such confounders can lead to false associations and incorrect edge directions. In this paper, we study the linear structural equation model with latent confounders. We propose an algorithm that iteratively identifies terminal (observed) nodes and reconstructs the directed acyclic graph of the observed variables. To do this, we recover the precision matrix of the observed variables as a sparse plus low-rank matrix: a sparse matrix captures the conditional dependencies among observed variables, while a low-rank matrix captures the combined influence of a few latent confounders. We establish that for

p

observed variables,

r

latent confounders and

s

edges, our procedure correctly identifies the directed causal relationship among observed variables, for

n \gtrsim \max\{s\log p,\ r p\}

samples. Experimental results validate our theoretical contributions.

Weijian Yu, Jean Honorio

CIS, The University of Melbourne

Linear Structural Equation Models Latent Confounders Causal Provable Guarantees

Ask PDF

May 11, 2026stat.ML

Coarsening Linear Non-Gaussian Causal Models with Cycles

Recent work on causal abstraction, in particular graphical approaches focusing on causal structure between clusters of variables, aims to summarize a high-dimensional causal structure in terms of a low-dimensional one. Existing methods for learning such summaries from data assume that both the high- and low-dimensional structures are acyclic, which is helpful for causal effect identification and reasoning but excludes many high-dimensional models and thus limits applicability. We show that in the linear non-Gaussian (LiNG) setting, the high-dimensional acyclicity assumption can be relaxed while still allowing recovery of a low-dimensional causal directed acyclic graph (DAG). We further connect identifiability of this low-dimensional DAG to existing results: LiNG models with cycles are observationally identifiable only up to an equivalence class whose members differ by reversals of directed cycles; our low-dimensional DAG, which is invariant across all members of a given equivalence class, thus forms a natural representative of the class. While existing approaches for learning this observational equivalence class over high-dimensional variables have exponential time complexity, our low-dimensional summary is learned in worst-case cubic time and comes with explicit bounds on the sample complexity. We provide open source code and experiments on synthetic data to corroborate our theoretical results.

Francisco Madaleno, Francisco C Pereira, Alex Markham

Department of Technology, Management and Economics, Technical University of Denmark · Department of Mathematical Sciences,11 University of Copenhagen

Causal Modeling Causal Representation Learning Acyclic Graphs Equivalence Chronos

Ask PDF

Sep 28, 2026stat.ML

The Statistical Cost of Causal Discovery with Feedback

What determines the unavoidable sample cost of learning cyclic causal structure? For cyclic linear non-Gaussian models, we study exact condensation recovery from observational data: identifying the strongly connected component (SCC) partition and all edges between components. We establish the first information-theoretic lower bounds on sample complexity for this target. For

p

variables, maximum SCC size

s_{\max}

, and maximum external-parent count

d_B

, any estimator requires order

s_{\max}\log(ep/s_{\max})+d_B\log(ep/d_B)

samples in the worst case over a regular model class. These bounds distinguish the costs of SCC membership and external-parent selection. Under principal invertibility and without correlation faithfulness, we establish a population block-exogeneity principle that identifies unknown root SCCs through residual independence and inclusion minimality. A sparse-adjustment characterization shows that small adjustment sets suffice to identify SCCs and their direct external parents, without regressing on all previously recovered variables. These characterizations yield BlockExo, which attains a structurally matching sample bound without knowing

s_{\max}

d_B

under suitable conditions. Simulations support the structural dependence of our sample bound and demonstrate BlockExo's sample-efficient recovery in comparisons with other methods for cyclic causal discovery.

Sunmin Oh, Seungsu Han, Gunwoong Park

Department of Statistics; Institute for Data Innovation in Science, Seoul National University, Korea · Department of Operations Research and Financial Engineering, Princeton University, USA · Department of Statistics; Interdisciplinary Program in Artificial Intelligence; Institute for Data Innovation in Science, Seoul National University, Korea.

Causal Discovery Methods Causal Latent Confounders Discovery Feedback

Ask PDF