Optimal estimation of linear non-Gaussian structure equation models

Sunmin Oh, Seungsu Han, Gunwoong ParkAISTATS 2025 · OpenReview

Abstract

This paper establishes the first sample-optimal complexity for learning the structure of Linear Non-Gaussian Acyclic Models (LiNGAMs) in high-dimensional settings. The authors introduce OptLiNGAM, an algorithm that achieves a sample complexity of $n = \Theta(d_{in} \log \frac{p}{d_{in}})$—matching information-theoretic lower bounds—without requiring restrictive assumptions like faithfulness or a known maximum indegree.

Introduction

Causal discovery aims to uncover the "who-causes-whom" relationships in data, typically represented as a Directed Acyclic Graph (DAG). While Gaussian models are common, they are often unidentifiable without strict assumptions such as equal error variances. LiNGAMs are powerful because the non-Gaussian nature of the noise makes the causal directions mathematically identifiable.

However, a major gap has persisted regarding sample efficiency. In high-dimensional regimes where the number of variables $p$ significantly exceeds the number of samples $n$, existing LiNGAM algorithms require far more data than the theoretical minimum. This paper bridges that gap, proving the exact data requirements for causal graph recovery and providing an algorithm that achieves this limit.

Methodology: The OptLiNGAM Algorithm

OptLiNGAM recovers graph structure in a top-down, layer-wise fashion. Its core innovation lies in a new conditional independence property:

  1. Exogeneity via Projection: A variable becomes "exogenous" (acting like a source node) once its projection onto a set containing all its parents is subtracted.
  2. Reduced Search Space: Unlike previous methods that project onto all preceding variables in an ordering, OptLiNGAM shows that projecting onto a subset of size $d_{in} + 1$ is sufficient.
  3. Distance Covariance: The algorithm uses distance covariance as a robust, non-parametric measure of independence, allowing it to handle various sub-Gaussian error distributions (e.g., Uniform or Beta).
  4. Iterative Layering: It identifies source nodes (Layer 0), then uses those to find subsequent layers, incrementally constructing the DAG.

Crucially, OptLiNGAM does not require faithfulness or parental faithfulness, common assumptions that are often violated in practice.

Empirical Evaluation

The authors evaluated OptLiNGAM using synthetic hub graphs with varying maximum indegrees ($d_{in}$) and the real-world General Social Survey (GSS) dataset.

Performance of OptLiNGAM and baselines across different sample sizes and maximum indegrees.

As illustrated in Figure 2, OptLiNGAM (labeled 'Opt') demonstrates superior sample efficiency. It reaches near-perfect recovery significantly faster than competing methods, particularly as the graph complexity ($d_{in}$) increases. The algorithm's performance aligns with the theoretical optimal scaling of $n = \Theta(d_{in} \log \frac{p}{d_{in}})$.

Comparison of MCC and Hamming distance (HM) for various methods in high-dimensional settings.

Quantitative results in Table 1 (Figure 3) further highlight the performance gap. In a high-dimensional scenario with $p=200$ variables and $n=200$ samples, OptLiNGAM achieves a Matthews Correlation Coefficient (MCC) of 0.8592, significantly outperforming ICA-LiNGAM (~0.47) and DirectLiNGAM (~0.44). On real-world GSS data, OptLiNGAM recovered the ground-truth causal graph with a Hamming distance of only 2, compared to a distance of 6 for DirectLiNGAM.

Conclusion and Future Work

OptLiNGAM represents a significant advancement in causal discovery, providing the first sample-optimal approach for high-dimensional LiNGAMs. While the algorithm involves a subset search that presents a statistical-computational trade-off, its efficiency in data-constrained environments is unparalleled. Future research directions include extending these optimal bounds to models with latent confounders and adapting the method for heavy-tailed noise distributions.

Summary updated

Abstract

Much of science involves discovering and modeling causal relationships in nature. Significant progress has been made in developing statistical methods for representing and identifying causal knowledge from data using Linear Non-Gaussian Acyclic Models (LiNGAMs). Despite successes in learning LiNGAMs across various sample settings, the optimal sample complexity for high-dimensional LiNGAMs remains unexplored. This study establishes the optimal sample complexity for learning the structure of LiNGAMs under a sub-Gaussianity assumption. Specifically, it introduces a structure recovery algorithm using distance covariance that achieves the optimal sample complexity, $n = \Theta(d_{in} \log \frac{p}{d_{in}})$, without assuming faithfulness or a known indegree. The theoretical findings and superiority of the proposed algorithm compared to existing algorithms are validated through numerical experiments and real data analysis.
BibTeX
@inproceedings{oh2025optimal,
  author = {Sunmin Oh and Seungsu Han and Gunwoong Park},
  title = {{Optimal estimation of linear non-Gaussian structure equation models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=lblYg0GoCe},
}
Figure