Causal discovery becomes particularly challenging when the available sample size is small relative to the number of variables. This challenge also arises in the linear non-Gaussian acyclic model (LiNGAM), an identifiable framework for causal discovery from observational data. DirectLiNGAM estimates a causal order, which arranges variables so that causes precede their effects, by sequentially identifying an exogenous variable and removing its linear effect from the remaining variables. We establish a structural limitation of this procedure: when the number of variables exceeds the sample size, repeated residualization necessarily becomes degenerate before the full causal order can be determined. Our analysis further reveals that each residual can be reconstructed using only a graph-determined subset of variables already placed earlier in the causal order, termed the active boundary. This result motivates AdaPS-LiNGAM (Adaptive Predecessor Selection LiNGAM), which reconstructs each residual directly from the original observations using an adaptively chosen sparse subset of those earlier variables. The same subset-selection principle is also applied to the final pruning step for edge estimation. Experiments on synthetic data demonstrate that AdaPS-LiNGAM provides accurate causal-structure recovery in sample-limited settings and degrades more gradually as the sample size decreases.
Figures & tables
Figure 1 : Results for the small-sample experiment with n=100 under uniform noise, with p∈{10,25,50,75,100,125,150,175,200} . Markers show the mean over 100 trials and error bars ±1 standard deviation. The SHD axis is truncated at 1000 .
Figure 2 : Results for the small-sample experiment with n=100 under Laplace noise, with p∈{10,25,50,75,100,125,150,175,200} . Markers show the mean over 100 trials and error bars ±1 standard deviation. The SHD axis is truncated at 1000 .
Figure 3 : Results for the reduced-sample experiment with p=100 under uniform noise, with n∈{100,500,1000,1500,2000} . Markers show the mean over 100 trials and error bars ±1 standard deviation. The SHD axis is truncated at 1000 .
Figure 4 : Results for the reduced-sample experiment with p=100 under Laplace noise, with n∈{100,500,1000,1500,2000} . Markers show the mean over 100 trials and error bars ±1 standard deviation. The SHD axis is truncated at 1000 .
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5 : Empirical mean active-boundary sparsity of the RG-indeg3 graphs under the fixed true causal order π(i)=i , together with the theoretical lower bound on E[smax(π)] from Example 2 . Error bars indicate one standard deviation across graph realizations.
Figure 6 : Active-boundary sparsity across the four graph families used in Section 6 . For each true graph realization, ten valid causal orders were sampled. Curves show the median across graph realizations and sampled orders, and shaded regions indicate the interquartile range.
Causal discovery methods such as LiNGAM identify causal structure from observational data by assuming mutually independent disturbances. This assumption is fragile: shared volatility, common scale effects, or other forms of dependence can cause the methods to recover the wrong causal order, even with infinite data. We introduce the Linear Mean-Independent Acyclic Model (LiMIAM), which replaces full independence with weaker one-sided mean-independence restrictions on the disturbances. Under finite-order consequences of these restrictions, source nodes are generically identifiable, and hence a compatible causal order can be recovered recursively. Our proof is constructive and leads to DirectLiMIAM, a sequential residual-based algorithm for causal discovery under dependent noise. In simulations with mean-independent but dependent disturbances, DirectLiMIAM outperforms LiNGAM methods. A large-scale empirical application to the oil market highlights the implausibility of the independence assumption and the ability of DirectLiMIAM to recover a realistic causal ordering, from policy to production and from prices to inflation.
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
Recovering the exact directed acyclic graph (DAG) in linear non-Gaussian acyclic models with latent confounders (LvLiNGAM) remains a challenging problem. Although LvLiNGAM is identifiable only up to an observational equivalence class, each equivalence class is characterized by a unique sparsest DAG. Recovering the sparsest DAG from finite samples, however, remains difficult. Although existing methods are asymptotically consistent, they do not provide an explicit finite-sample procedure for recovering the unique sparsest DAG, nor do they handle models with an arbitrary number of latent confounders. In this paper, we propose a finite-sample method for recovering the sparsest DAG without imposing any restriction on the number of latent confounders. Simulation studies and real-data analyses demonstrate that the proposed method achieves superior finite-sample performance compared with existing approaches.
Ming Cai, Hisayuki Hara
Graduate School of Informatics, Kyoto University, Kyoto, Japan · Institute for Liberal Arts and Sciences, Kyoto University, Kyoto, Japan