Learning a causal graph from observational data becomes possible when cause-effect relationships are non-linear. An effect written as a non-linear function of its causes plus independent noise leaves an asymmetry that a backward fit cannot reproduce. Methods that exploit this asymmetry, however, only scale when each variable's list of possible parents is first cut down to a small shortlist. That shortlist step is usually done with sparse regression and treated as plumbing. We argue it is a non-monotone subset-selection problem: the objective is a set function where adding an item can lower the total. Here, adding a weak or redundant candidate makes a finite-sample non-linear fit worse on held-out data. Algorithms built for this kind of objective, including recent fast "guided" methods with guarantees above the $1/e$ barrier, have never been tested on it.
The proposal has two parts. First, we build the shortlist with a guided randomized greedy algorithm applied to a held-out predictive score. Second, we analyze how its guarantee degrades when every score evaluation is a noisy statistical estimate rather than an exact oracle. We then measure whether better shortlists produce better final graphs. The bet is specific. Plain greedy forward selection grabs strongly predictive non-parents early, especially children and other descendants. A procedure that first steers away from a local-search solution should recover more true parents at the same shortlist size. That advantage should be largest in dense graphs with few samples.
Core Claim
In the Causal Additive Models pipeline (CAM), each variable $X_j$ is modeled as a sum of smooth functions of its parents plus Gaussian noise. The ordering search only considers edges inside a preliminary neighborhood of size at most $d \ll p$, where $p$ is the number of variables. Any true parent dropped at this stage can never be recovered.
We define the neighborhood objective for target $j$ and candidate set $S \subseteq V \setminus \{j\}$ as
$$f_j(S) = \widehat{\mathrm{LL}}_{\text{held-out}}\big(X_j \mid X_S\big) - \widehat{\mathrm{LL}}_{\text{held-out}}\big(X_j\big).$$
Here $\widehat{\mathrm{LL}}_{\text{held-out}}(X_j \mid X_S)$ is the cross-validated Gaussian log-likelihood of an additive spline regression of $X_j$ on the variables in $S$. The second term is the same quantity for an intercept-only model. We maximize $f_j$ subject to $|S| \le d$.
In the population, this gain is monotone and only mildly fails to be submodular. In finite samples, estimation variance grows with $|S|$, so $f_j$ is genuinely non-monotone: adding variables can lower it. This places $f_j$ in the setting of non-monotone, weakly submodular maximization. Weak submodularity means diminishing returns hold only up to a factor $\gamma \le 1$ (the submodularity ratio).
We make three claims. First, guided randomized greedy (GuidedRG) recovers more true parents than plain greedy or CAM's sparse-regression screening at equal $d$. Second, its guarantee survives noisy evaluations with an explicit additive loss. Third, the recall gain carries through to lower structural error in the final graph.
Relation to Prior Work
Three papers motivate the proposal and supply its methods.
Causal meets Submodular is the closest prior work. It selects sensors and covariates for time series by maximizing directed information, an information-theoretic causality measure. It proves the sensor problem is non-monotone submodular, handles the non-submodular covariate problem with a "submodularity index," and uses randomized greedy. Its authors leave open how finite-sample estimation error affects the greedy guarantee. We differ in three ways: our setting is static non-linear DAGs, the selected set feeds a downstream order search, and we answer their open question for our objective.
Weakly Submodular Function Maximization Using Local Submodularity Ratio supplies the theory. It shows that randomized greedy, after padding the ground set with $2k$ zero-gain dummy elements, achieves roughly $\gamma e^{-1/\gamma}$ on non-monotone $\gamma$-weakly submodular functions. It also notes that computing $\gamma$ is itself hard.
GuidedRG supplies the algorithm we test. It runs a fast local search to get a guidance set $Z$, then runs a randomized greedy that avoids $Z$ for a first stage before allowing all elements. It reaches $0.385$ under cardinality constraints. Its deterministic linear-time relatives (LinearCard and related) give a route to very large $p$.
Two papers constrain the design. OCDaf/OSLow shows that additive-noise assumptions break under heteroscedastic noise and learns orderings with normalizing flows. This warns us that a better shortlist under a misspecified CAM score may not matter, so we test downstream with both CAM and OSLow. ScoreLiNGAM reaches $p = 10{,}000$ only by assuming precomputed Markov blankets. This shows the shortlist step is the scaling bottleneck elsewhere too, although that method is linear.
Two adjacent papers use submodularity for causal experiment design rather than observational structure learning: Licence and Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models. They do not address our problem.
Research Program
Measure the objective's structure. On synthetic additive-noise graphs we know the true parents. We estimate local submodularity ratios of $f_j$ by sampling nested pairs $(A, B)$ and comparing marginal gains. We do this across sample size $n$, graph density, and nonlinearity strength, and we record how often $f_j$ has negative marginal gains. If $\gamma$ is near zero in practice, the weak-submodularity guarantees are vacuous. We would then report that and fall back to a purely empirical comparison.
Analyze noisy evaluations. Suppose every query to $f_j$ is off by at most $\eta$, with $\eta$ controlled by held-out sample size through standard concentration of cross-validated log-likelihood. Each greedy comparison then involves marginal gains wrong by at most $2\eta$. Over $d$ steps, the expected outcome should therefore satisfy
$$\mathbb{E}[f_j(S)] \ge \alpha(\gamma)\, f_j(S^*) - O(d\,\eta),$$
where $S^*$ is the best size-$d$ set and $\alpha(\gamma)$ is the noiseless ratio. We aim to prove this for randomized greedy with dummies and for GuidedRG. We will also check whether GuidedRG's local-search guidance stage amplifies the error, since local search makes many more comparisons. A finding that it does would be an informative negative result.
Build and plug in. The selector produces neighborhoods that replace CAM's preliminary neighborhood step. We then run CAM's order search and pruning unchanged, and separately feed the same neighborhoods to OSLow as an edge mask. For $p$ in the thousands, we use LinearCard with the same objective.
Baselines
The naive reference points come first. One feeds every variable to the order search with no shortlist, which is feasible only at small $p$ and gives an upper bound on recall. The other ranks candidates by marginal kernel dependence (HSIC) with $X_j$ and keeps the top $d$. Any method that cannot beat top-$d$ ranking on true-parent recall has no case.
The strongest existing competitor is CAM's own neighborhood selection, using component-wise boosting or group lasso with spline bases (CAM). It is the method this step was designed with, and it handles $p = 1000$ with $n = 200$ in the CAM paper. We run it with the authors' default tuning and give it the same cross-validation folds, the same spline basis, the same $d$, and a matched wall-clock budget. The relevant reported downstream number is from OCDaf: CAM reaches SHD 12.0 on Sachs, OSLow 10.4, and GraN-DAG 13.0. On SynTReN, that paper reports only that OSLow variants achieve lower SHD and SID than baselines, so no reported numeric result is available from the file for SynTReN.
The ablation that isolates our key ingredient is plain forward greedy on the identical $f_j$. It stops either at $d$ or when the best marginal gain turns negative. A second ablation is randomized greedy with dummy elements and no guidance set, which is the Santiago–Yoshida and Zhou–Spanos style. GuidedRG must beat both on true-parent recall at fixed $d$ by more than the seed-to-seed standard deviation over 20 graphs, in the dense, small-$n$ regime. Beating CAM's selector on recall and then on downstream SHD and SID is the bar for a practical claim.
Why not just…?
Why not just use CAM's group lasso or boosting screening? It is fast and it works on CAM's own benchmarks. Sparse additive regression, however, favors the variables that best predict $X_j$, and those include children. It also shrinks correlated true parents toward each other. We expect it to drop parents precisely when $X_j$ has several correlated causes and strong descendants. That is testable on synthetic graphs where we vary children's signal strength while holding parents fixed. If CAM's screening matches our recall there, the proposal reduces to a negative result.
Why not just run plain greedy with a stopping rule on the same objective? This is the most serious threat. If the non-monotonicity of $f_j$ is mostly a size penalty, greedy with stopping is close to optimal and the guided algorithms add nothing. Our ablation runs exactly this comparison on the same objective, folds, and query budget. We commit to reporting it as the headline result whichever way it comes out. The hypothesis we expect to support the proposal is narrower: greedy's early commitment to a dominant descendant is what guidance avoids. So we also log which variable each method picks first.
Why not skip shortlisting and let a flexible ordering learner like OSLow handle everything? At Sachs scale this may well be fine. Neural ordering methods are, however, heavy and prone to local optima as $p$ grows. ScoreLiNGAM's scaling to $p = 10{,}000$ relies on precomputed neighborhoods (ScoreLiNGAM). We test this directly by giving OSLow both full and shortlisted candidate sets at $p$ where it still runs, and comparing SHD per unit of compute.
Proposed Experiments
Synthetic study. We generate Erdős–Rényi DAGs with additive non-linear mechanisms using Gaussian-process and sigmoid functions. We vary $p$ over 50, 200, and 1000, expected degree over 2, 4, and 8, and $n$ over 200, 1000, and 5000. We include a heteroscedastic-noise variant to probe misspecification. The primary metric is true-parent recall at fixed $d$. Secondary metrics are shortlist size, number of oracle queries, and wall-clock time. The downstream metrics are SHD and SID (structural intervention distance) after CAM and after OSLow.
Real and semi-synthetic data. On SynTReN we report SHD and SID. On Sachs (11 nodes, 17 edges) we compare against the reported SHD of 12.0 for CAM and 10.4 for OSLow. We treat Sachs only as a sanity check, since shortlisting matters little at 11 nodes. On the 39-gene Arabidopsis isoprenoid data we examine agreement with known pathway directions, as CAM did. A scaling run of LinearCard on the mouse brain single-cell data ($p = 10{,}012$) reports held-out log-likelihood and runtime.
Decisive checks. There are two. First, in the dense, small-$n$ synthetic regime, GuidedRG must beat greedy-with-stopping on parent recall, and the gap must shrink as $n$ grows, as the noisy-oracle bound predicts. Second, any recall gain must reduce downstream SHD under at least one of CAM and OSLow. If the first check fails, the guided non-monotone machinery is unnecessary for this problem. If the first holds but the second fails, shortlist quality is not the bottleneck. Either outcome is a clear, reportable answer.
References
- CAM: Causal Additive Models, high-dimensional order search and penalized regression
- Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization
- Causal meets Submodular: Subset Selection with Directed Information
- Weakly Submodular Function Maximization Using Local Submodularity Ratio
- Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time
- OCDaf: Ordered Causal Discovery with Autoregressive Flows
- Sequentially learning the topological ordering of directed acyclic graphs with likelihood ratio scores
- Bayesian Active Causal Discovery with Multi-Fidelity Experiments
- Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models