AdaPS-LiNGAM: Adaptive Predecessor Selection for Linear Non-Gaussian Acyclic Models under Small-Sample Settings

1 Introduction

• LiNGAM identifies causal structure from observational data under a linear acyclic model by exploiting non-Gaussian disturbances.DirectLiNGAM estimates a causal order by sequentially identifying exogenous variables and removing their linear effects.Source: §1 · p. 2
• When observations are scarce and the variable count approaches or exceeds the sample size, large regression predictor sets can destabilize causal discovery.The paper focuses on controlling the dimension of estimation problems in this regime.Source: §1 · p. 2
• When n < p, DirectLiNGAM’s cumulative residualization forces residual vectors to vanish before all variables are ordered.Each nonzero orthogonal-projection step removes one dimension, while centered observations provide at most n − 1 dimensions.Source: §1 · pp. 2–3
• The active boundary is the subset of previously ordered variables that can reach a target through the remaining graph without crossing another selected variable.Under localized non-cancellation, it is the support of the population reduced-form regression and the unique minimal predictor set for exact residual reconstruction.Source: §1 · p. 3
• AdaPS-LiNGAM reconstructs residuals from the original data using adaptively selected subsets of previously ordered variables, and applies the same principle in final pruning.The evaluation examines robustness as dimensionality increases in small samples and degradation as observations decrease.Source: §1 · pp. 3–4

Causal Discovery in Small-Sample Settings.

• Small-sample causal discovery studies include reliability methods, lower-order independence information, and approaches that divide structure learning into smaller problems.These lines of work share attention to limiting the statistical information used at each stage when data are scarce.Source: Causal Discovery in Small-Sample… · p. 4

LiNGAM in Small-Sample Settings.

• MiS-LiNGAM reduces the causal-discovery problem using skeleton estimation and minimal LiNGAM sets, whereas this work retains DirectLiNGAM and reduces residual-regression predictors.DirectLiNGAM constructs each residual using variables preceding the target in the estimated order.Source: LiNGAM in Small-Sample Settings · p. 5

Causal Discovery in High-Dimensional Settings.

• High-dimensional methods exploit structural sparsity or restrict candidate models, but high dimensionality and limited sample size are distinct settings.The paper focuses on the finite-sample effect of predictor count in each causal-ordering regression, including cases where n exceeds p.Source: Causal Discovery in High-Dimensional… · p. 5

3 Preliminaries

• The paper uses indexed subvectors and submatrices to express its variable-set operations.For a vector a and index set S, a_S denotes the subvector indexed by S; M_ST denotes a submatrix selected by row and column index sets.Source: §3 · p. 6

3.1 LiNGAM Model

• LiNGAM models variables with linear effects and mutually independent, continuous, non-Gaussian disturbances, with a directed acyclic graph encoding the effects.Under these assumptions, the causal structure is identifiable from the observed distribution, and a causal order places causes before effects.Source: §3.1 · pp. 6–7

3.2 DirectLiNGAM

• DirectLiNGAM sequentially identifies an exogenous variable using residual independence, then residualizes remaining variables and prunes unnecessary edges after ordering.Its sample dependence measure operationalizes the independence criterion, and each selected variable adds a successive least-squares projection to remaining residuals.Source: §3.2 · pp. 7–8

4.1 Projection Geometry of Sequential Residualization

• Each nonzero sequential projection reduces the residual-span dimension by one, so the nested residual subspaces have dimension r−t.Source: §4.1 · pp. 9–10

4.2 Vanishing Residuals under Cumulative Residualization

• When n < p, cumulative residualization leaves all remaining residuals zero while at least two variables remain unordered, preventing completion of the causal order.Source: §4.2 · pp. 10–11
• Only when r = p−1 does simultaneous vanishing occur after just one variable remains; n < p forces r < p−1.Source: §4.2 · p. 11

5 Proposed Method: AdaPS-LiNGAM

• AdaPS-LiNGAM reconstructs each residual from the original data using a sparse subset of previously selected variables, and applies subset selection to final edge pruning.The method estimates the predictor sets with adaptive best-subset selection.Source: §5 · p. 11, §5.1 · p. 15

5.1 Characterization of Sparse Residual Reconstruction

• Under localized non-cancellation, the active boundary—earlier nodes whose effects reach a target through remaining nodes—equals the support of its regression coefficients and reconstructs its DirectLiNGAM residual.The condition excludes exact cancellation among the relevant directed-path contributions.Source: §5.1 · pp. 11–14
• The active boundary is the unique smallest support attaining minimum squared-error risk; reconstructing residuals from it preserves the next root-selection scores, while the pruning predictor set has the same minimal-support property for parents.The active-boundary regressions reproduce the residuals produced by DirectLiNGAM after the same ordering steps.Source: §5.1 · pp. 14–15

5.2 Active-Boundary Sparsity and Sample Size

• Active-boundary size depends on graph structure: it is one at every noninitial step in a directed chain, but grows linearly in p in expectation for the Wang–Drton random DAG with J = 3.Thus, bounded maximum in-degree alone does not guarantee bounded active-boundary sparsity.Source: §5.2 · pp. 15–16
• When Assumption 10 holds and smax(π) ≤ n −2, oracle active-boundary residuals remain nonzero even when n < p, but this condition does not guarantee recovery of the active boundary.Unlike cumulative residualization, oracle reconstruction can remain nondegenerate at ordering steps t ≥ n −1 because its predictor count is graph-controlled.Source: §5.2 · p. 17
• A node with in-degree at least n−1 rules out the sufficient sparsity condition, but does not alone imply that an oracle residual vanishes.The condition can therefore fail without proving residual degeneration in a particular graph.Source: §5.2 · p. 18
• For a layered graph of width at most w, active-boundary sparsity is at most 2w−1, so 2w−1 ≤ n−2 permits the sufficient condition independently of depth or p.The bound is exact for a directed chain with w = 1.Source: §5.2 · p. 19
• Under Assumption 10, active-boundary sparsity smax(π) ≤ n−2 is sufficient for all oracle active-boundary residuals during causal ordering to remain nonzero.This makes finite-sample feasibility depend on structural complexity along the causal order rather than total variable count.Source: §5.2 · p. 19

5.3 Algorithm and Implementation

• Because the required predictor sets are unknown in observed data, AdaPS-LiNGAM estimates them adaptively using best-subset selection.The method builds on the active-boundary sparsity condition for nonzero oracle residuals under Assumption 10.Source: §5.3 · p. 19

5.3.1 Adaptive best subset selection

• Adaptive BSS addresses combinatorial subset search and unknown cardinality by combining best-subset selection with information-criterion size selection via abess (Zhu et al., 2020).The information criterion selects the subset size.Source: §5.3.1 · p. 20

5.3.2 Use in causal ordering and pruning

• At each ordering step, AdaPS-LiNGAM reconstructs residuals from original observations using selected earlier variables, then applies adaptive BSS to candidate predecessors for pruning.When the estimated order is consistent with the causal structure, the pruning regression coefficient has support equal to the true parent set.Source: §5.3.2 · pp. 20–21

Data generation

• Synthetic data covered ER2, ER4, ER8, and RG-indeg3 graphs, with independent uniform or Laplace exogenous noises and edge coefficients sampled with random signs and magnitudes from [0.5, 2.0].The Erdős–Rényi families used target average degrees 2, 4, and 8; RG-indeg3 had maximum in-degree three.Source: Data generation · p. 22

Methods

• The comparison included DirectLiNGAM and HighDimDirectLiNGAM; AdaPS-LiNGAM used adaptive best-subset selection with GIC or EBIC for support-size selection.HighDimDirectLiNGAM used the fixed assumed in-degree bound J = 3, rather than a graph-specific oracle value.Source: Methods · pp. 22–23

Evaluation metrics

• Edge recovery was evaluated by precision, recall, F1, and directed SHD, while causal-order recovery used TOD; lower TOD and SHD indicate better results.Runtime was also recorded.Source: Evaluation metrics · pp. 23–24

Experimental environment

• Each experiment used 100 random seeds on a Linux server with 56 physical cores and 755 GiB RAM.Parallelization used 50 workers, with numerical libraries restricted to single-thread execution.Source: Experimental environment · p. 24

6.2 Small-sample Settings

• At p = 200 under uniform noise, AdaPS-LiNGAM (EBIC) F1 scores were 0.905, 0.785, and 0.557 on ER2, ER4, and ER8, versus DirectLiNGAM's 0.315, 0.319, and 0.263.On ER2, TOD was 11.14 versus 77.00, and SHD was 34.39 versus 430.20, respectively.Source: §6.2 · pp. 24–25
• At p = 200 under uniform noise, AdaPS-LiNGAM (EBIC) F1 fell from 0.905 on ER2 to 0.557 on ER8 (drop 0.348), while DirectLiNGAM fell from 0.315 to 0.263 (drop 0.052).Source: §6.2 · p. 25

6.3 Performance under Reduced Sample Sizes

• As sample size fell from 2,000 to 100, AdaPS-LiNGAM (EBIC) F1 fell from 0.997 to 0.914 on uniform-noise ER2, while DirectLiNGAM fell from 0.978 to 0.267.For uniform-noise ER8, the corresponding values were 0.982 to 0.536 for AdaPS-LiNGAM (EBIC) and 0.993 to 0.229 for DirectLiNGAM.Source: §6.3 · p. 26
• For uniform-noise ER2, AdaPS-LiNGAM runtime rose from approximately 75 seconds at n = 100 to 792 seconds at n = 2,000, while DirectLiNGAM rose from approximately 87 to 129 seconds.HighDimDirectLiNGAM had the lowest TOD on RG-indeg3 at n = 100, 69.01 versus 73.13 for AdaPS-LiNGAM (EBIC), but its F1 was 0.144; additional observations did not close the edge-recovery gap in RG-indeg3 or ER8.Source: §6.3 · pp. 26, 29

7 Conclusion and Future Work

• AdaPS-LiNGAM reconstructs residuals from a subset of previously selected variables, and its EBIC variant achieved more accurate causal-order and graph recovery than DirectLiNGAM in sample-limited settings.It also degraded more gradually as sample size decreased.Source: §7 · p. 29
• Future work includes finite-sample guarantees for active-boundary recovery and estimation, separate analysis of root-selection reliability, and more practical conditions on active-boundary sparsity.The paper also calls for explicit guarantees on the minimum sample size permitting reliable causal discovery.Source: §7 · pp. 29, 32
• Figures 3 and 4 report reduced-sample experiments at p = 100 for n = 100, 500, 1,000, 1,500, and 2,000, under uniform and Laplace noise, respectively.Markers show means over 100 trials with ±1 standard-deviation error bars; the SHD axis is truncated at 1,000.Source: Figure 3 · p. 30, Figure 4 · p. 31

A.1 RG-indeg3 Graphs

• RG-indeg3 uses the Wang–Drton construction with in-degree bound J = 3 and fixed causal order π(i) = i.Its active-boundary sparsity can nevertheless grow linearly with p.Source: §A.1 · p. 32
• A bounded maximum in-degree does not prevent active-boundary sparsity from increasing linearly with p in this graph family.The generated DAGs have 1, . . . , p as a true causal order.Source: §A.1 · p. 32
• Empirical means of smax(π) follow an approximately linear trend and remain above the theoretical lower bound over the range considered.Figure A1 compares the empirical mean with the lower bound on E[smax(π)].Source: §A.1 · p. 32

• ER2 has the smallest active-boundary sparsity, followed by ER4 and ER8, while maximum in-degree alone does not characterize sparsity.Source: §A.2 · p. 32
• RG-indeg3 active-boundary sparsity increases substantially with p despite maximum in-degree being bounded by three.Source: §A.2 · p. 32
• Fig. A1 compares empirical mean active-boundary sparsity under the fixed order π(i) = i with the theoretical lower bound on E[smax(π)].Error bars show one standard deviation across graph realizations.Source: Figure A1 · p. 33

• Greater active-boundary sparsity in RG-indeg3 is consistent with its relatively difficult edge-recovery performance at large p.Source: §A.3 · p. 33
• ER8 has larger active-boundary sparsity and greater edge-recovery degradation than ER2, suggesting sparsity captures difficulty beyond maximum in-degree alone.Source: §A.3 · p. 33
• These comparisons are structural interpretations, not finite-sample guarantees; the oracle condition smax(π) ≤ n − 2 guarantees nonvanishing residuals, not support or order recovery.The guarantee also requires the stated sample nondegeneracy condition.Source: §A.3 · p. 33