Methods that learn cause-and-effect graphs from non-linear data at scale start by shrinking the problem. For each variable they keep a short list of plausible neighbors and discard everything else, and only then search for a causal ordering. This shortlisting step is permanent: if a true parent is cut, no later stage can restore it. Today the list length is a fixed hyperparameter, and the list is filled by a heuristic that has no guarantee of keeping the variables that matter. This note proposes to use the submodularity ratio, a number between 0 and 1 that measures how far a set-selection objective departs from diminishing returns, to answer two questions directly. How long must each variable's shortlist be so that it contains that variable's true Markov blanket (its parents, children, and children's other parents)? And when does adding one candidate at a time fail outright, so that candidates must be added in pairs?
The core idea fits in two sentences. Greedy forward selection of regressors captures a known fraction of the best achievable explained variance, and that fraction is controlled by the submodularity ratio $\gamma$. If every true neighbor contributes at least some minimum unique variance, then a shortlist of size roughly $(k/\gamma)\log(\text{total signal}/\text{minimum signal})$ provably contains the whole Markov blanket. Estimating $\gamma$ per variable therefore lets us size each shortlist individually, and a near-zero estimate is a diagnostic: it flags interaction mechanisms such as $X_1 X_2$, where neither parent helps alone, and calls for pairwise selection there.
Why this, and not the obvious version
The obvious bridge between these two literatures would be to prove that greedy topological-order search, as in CAM or GENE from Strong and Weak Identifiability, achieves a $(1-e^{-\gamma})$ fraction of the optimal score. The research file finds no paper that does this, but a guarantee of that kind would be close to meaningless for causal discovery. The weak-identifiability paper shows that in non-linear additive noise models a reverse "implicit function" can fit the data almost as well as the true mechanism. A near-optimal goodness-of-fit score can therefore come from a graph with wrong edge directions. A multiplicative bound on the score says nothing about whether the edges are correct.
We avoid this trap by applying the submodularity ratio only where a score guarantee does translate into a structural one. That place is neighborhood screening. Its target, the Markov blanket, is the minimal set that achieves the population optimum of the regression objective, and it does not depend on edge orientation.
The closest existing work comes in two groups. Approximate Submodularity and its Applications and Restricted Strong Convexity Implies Weak Submodularity supply the method: the $(1-e^{-\gamma})$ greedy bound and the lower bound $\gamma \ge m/M$, where $m$ and $M$ are the restricted strong convexity and restricted smoothness constants of the loss. Both papers study prediction of a single target from linear or generalized linear models, and neither asks whether the selected set contains a specific structural subset. ProtoDash shows that a kernel objective can be weakly submodular, which suggests non-linear regression gains may be as well, but it never touches graph recovery. On the causal side, ABCD-Strategy and Licence use exact or $\epsilon$-submodularity, but only to choose interventions. Our setting is purely observational, and we use a multiplicative ratio rather than an additive error term.
Core Claim
Fix a variable $X_j$. Let $f_j(S)$ be the in-sample variance of $X_j$ explained by a grouped-basis regression on the candidate set $S$, for example a spline basis per candidate as in CAM. Explained variance in-sample is monotone, which is what the greedy theory requires. The non-monotone pruning step is left downstream, which sidesteps the monotonicity tension noted in the file.
Das and Kempe's bound extends to running greedy for $\ell$ steps against the best $k$-set:
$$f_j(S_\ell) \ge \left(1 - e^{-\gamma \ell / k}\right) f_j(\mathrm{OPT}_k).$$
Here $S_\ell$ is the greedy set after $\ell$ additions, $k$ is the Markov blanket size, and $\gamma$ is the ratio restricted to greedy prefixes and the optimal set. In the population, $\mathrm{OPT}_k$ is the Markov blanket and has value $V_j^*$.
Now assume a "minimum signal" condition. Every blanket member $x$ adds at least $\beta_j$ explained variance on top of any candidate set that lacks it. This is the selection analogue of the usual beta-min assumption. Under it, any set missing $x$ has value at most $V_j^* - \beta_j$. Combining the two statements, greedy contains the full blanket once
$$\ell > \frac{k}{\gamma}\,\log\frac{V_j^*}{\beta_j}.$$
That inequality is the sizing rule. As $\gamma \to 0$ it requires an unbounded list, and exactly then we switch to selecting pairs of candidates. Pair blocks have their own submodularity ratio, which stays bounded away from zero for pairwise interaction mechanisms.
We claim three things. First, a conservative computable lower bound on $\gamma$ follows from a grouped version of $\gamma \ge m/M$, using restricted eigenvalues of the basis covariance. Second, an empirical estimate along the greedy path is much tighter. The "alignment effect" in Approximate Submodularity predicts this gap: spectral bounds there implied about 33% of optimal $R^2$ while greedy achieved 90–95%. Third, sizing each variable's list by the estimated $\gamma$, and switching to pair blocks when the estimate is small, recovers Markov blankets at higher recall per candidate kept than fixed-size screening. That recall gain should then show up as better downstream structure.
Research Program
The theory step adapts the restricted strong convexity argument to group sparsity, so that one group equals one candidate's spline or tensor-product basis. We will state the bound for regression on a fixed basis with a fixed ridge penalty and be explicit that it is conservative. We will also prove the sizing rule above, with a finite-sample version. In that version, $V_j^*$, $\beta_j$, and $\gamma$ are replaced by estimates, and the slack is controlled by a uniform concentration bound over groups.
Because computing $\gamma$ exactly is NP-hard (Is submodularity testable?), the estimation step does not try to certify it. Instead it computes the ratio only on the sets the proof actually uses: greedy prefixes paired with small sampled candidate sets. This gives an estimate, not a certificate. We will report how often the estimate falls below the true $\gamma$ on synthetic graphs, where exhaustive computation is feasible for small $k$.
The algorithm, called γ-sized screening, runs greedy forward selection per variable. It stops at the length the sizing rule gives, using $\beta_j$ from a held-out significance threshold. It promotes to pair blocks whenever the estimated $\gamma$ drops below a threshold. The output feeds unchanged into CAM's order search and pruning, and separately into GENE, so that every downstream difference is attributable to screening.
Baselines
The naive reference point is no screening at all: CAM's order search with every other variable as a candidate. This is an upper bound on recall and a lower bound on efficiency. It is feasible only at moderate $p$, and we run it up to the largest $p$ that fits the shared compute budget.
The default competitor is CAM's own preliminary neighborhood selection, which uses boosting with a fixed neighborhood size, from CAM. We run it with its published default size and also with a size tuned on held-out synthetic graphs under the same tuning budget we give our threshold. CAM reports scaling to $p=1000$ with $n=200$ and beating PC, GES, and LiNGAM in SHD and SID. However, no reported result was found on Lacuna for CAM's exact SHD or SID numbers on its Gaussian-process DAGs, so we will rerun it ourselves.
The strongest end-to-end method on real data in the file is GENE (Strong and Weak Identifiability). It reports an F1 of 0.65 on Sachs, against 0.38 for CAM and 0.24 for NOTEARS-MLP. OCDaf reports SHD 10.4 for its flow-based OSLow on Sachs, against 12.0 for CAM. REX reports F1 0.629 for ReX.
Sachs has only 11 variables, so screening barely matters there. Matching GENE's 0.65 when our screening is placed in front of GENE counts as "no harm," not as a win. A win means two things on synthetic graphs with $p \ge 100$. First, GENE or CAM with γ-sized screening must reach lower SHD and SID than with their default screening, at equal or lower wall-clock time. Second, Markov blanket recall must be strictly higher at matched average shortlist length.
Two ablations isolate the key ingredients. The first applies the sizing rule but never promotes to pairs, which tests the pair-block diagnostic. The second promotes to pairs but uses a fixed list length, which tests the sizing rule. A third variant replaces the empirical $\gamma$ with the spectral lower bound, which measures how much the alignment effect matters in practice.
Why not just…?
Why not just use Group Lasso for screening? In linear settings the file's evidence favors greedy selection. Approximate Submodularity, Restricted Strong Convexity, and Scalable Greedy Feature Selection each report greedy methods matching or beating the Lasso and Lasso-then-refit, citing shrinkage bias. That evidence is linear or GLM-only, so we include Group Lasso over the same spline groups as a baseline and do not treat the question as settled.
Why not just make the fixed neighborhood larger? If enough compute is available, a larger list or no screening will trivially match our recall. The claim is about efficiency and adaptivity. Most variables need short lists and a few need long ones, and a single global size either wastes computation on the many or truncates the few. Plotting recall against shortlist length, per variable, tests this directly. If a single tuned global size matches the per-variable rule at equal total length, the sizing contribution fails.
Why not just use interaction-capable boosted trees, as in REX? This is the real threat. Depth-two trees can pick up an $X_1 X_2$ parent pair that additive screening misses, and REX already uses gradient boosted trees with SHAP values to find parents. We will run tree-based screening at matched compute, in fitted models and wall-clock time, on mechanisms with planted interactions. If trees match our blanket recall, the pair-block component adds nothing as a selector. What would survive is the per-variable $\gamma$ estimate, as a diagnostic of where screening is unreliable, together with the sizing rule. We would report it that way rather than claim a better selector.
Why not just use continuous optimization and skip combinatorial search? On Sachs, NOTEARS-MLP reaches an F1 of 0.24 against GENE's 0.65, and it degrades under rescaling (Strong and Weak Identifiability). Relaxed permutation learning can also cheat with soft cycles (OCDaf). We include NOTEARS-MLP only as a reference point.
Proposed Experiments
The synthetic suite has three parts. The first is CAM-style Gaussian-process additive DAGs, on Erdős–Rényi and scale-free graphs with $p \in \{50, 200, 1000\}$ and $n \in \{200, 1000\}$. The second is the strongly identifiable MIM and GP generators and the weakly identifiable MLP generator from the GENE paper. The third is a new family that plants a controlled fraction of multiplicative pairwise mechanisms, so that the true $\gamma$ can be driven toward zero.
On all of these we measure Markov blanket recall against shortlist length, the gap between estimated and exact $\gamma$ (exact $\gamma$ is computed exhaustively only for small $k$), and downstream SHD, SID, and F1 after CAM and after GENE.
Semi-synthetic SynTReN data, used in OCDaf, tests realistic gene-network structure. Sachs is the real-data sanity check against the reported numbers above.
Three checks decide the project. First, on the interaction family, the recall of fixed-size screening must collapse as the planted interaction fraction rises, while γ-sized screening holds steady. The estimated $\gamma$ must also fall exactly on the variables with planted interactions; if it does not, the diagnostic claim fails. Second, at $p=1000$, $n=200$, γ-sized screening must beat CAM's tuned default in downstream SID at no greater total compute. Third, in the head-to-head with boosted trees, the method must either win on recall at matched compute or be recast honestly as a diagnostic plus sizing rule.
A negative result is also informative. If the empirical $\gamma$ concentrates near 1 on all additive generators and fixed-size screening already hits near-perfect recall, then the screening stage is not the bottleneck for these pipelines. Errors would instead come from order search under weak identifiability, which would redirect effort there.
References
- CAM: Causal Additive Models, high-dimensional order search and penalized regression
- Strong and Weak Identifiability of Optimization-based Causal Discovery in Non-linear Additive Noise Models
- Approximate Submodularity and its Applications: Subset Selection, Sparse Approximation and Dictionary Selection
- Restricted Strong Convexity Implies Weak Submodularity
- ProtoDash: Fast Interpretable Prototype Selection
- ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery
- Bayesian Active Causal Discovery with Multi-Fidelity Experiments
- Is Submodularity Testable?
- OCDaf: Ordered Causal Discovery with Autoregressive Flows
- ReX: Causal discovery based on machine learning and explainability techniques
- Scalable Greedy Feature Selection via Weak Submodularity