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:
- Exogeneity via Projection: A variable becomes "exogenous" (acting like a source node) once its projection onto a set containing all its parents is subtracted.
- 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.
- 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).
- 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.
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}})$.
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