Writing “these two variables are independent” into causal search: NOTREKS improves both structure recovery and effect identification for DAGMA and FLOP on synthetic benchmarks
Synopsis
In causal discovery, known marginal independencies were previously handled only indirectly: score-based search does not explicitly enforce them, so with finite samples the estimated graph can contradict what is known. Under a faithfulness assumption, NOTREKS translates marginal-independence pairs into a graphical constraint that no trek, a pair of directed paths sharing a common source, connects the two nodes, and plugs it into the gradient-based DAGMA as a differentiable PSTrek penalty and into the order-based FLOP as a trek-aware parent search. On linear-Gaussian synthetic benchmarks with oracle NOTREKS information, both variants improve CPDAG structural distance and the Ancestor-AID effect-identification distance over their vanilla counterparts, with no significant worsening.
Interpretation
Score-based causal discovery can now use “these two variables are marginally independent” as a hard graphical constraint inside the search rather than only as a post-hoc check. Such methods did not explicitly enforce independence constraints; the independencies implied by an estimated graph emerged only indirectly from score optimization and, with finite samples or model misspecification, could contradict what is known. In a linear-Gaussian setting with d=10 and n=100, globally minimizing BIC over all DAGs subject to correct marginal-independence constraints recovered the true Markov equivalence class more often than without the constraints.
The constraint is realized through a no-trek condition: if no two directed paths sharing a common source connect two variables, then under faithfulness those variables are marginally independent. Gradient-based methods had used independence information only locally, through support masks derived from the PC algorithm or by masking individual edges, and generally did not enforce all implied no-trek constraints. For gradient methods, the PSTrek penalty writes the no-trek condition as a smooth function of the weight matrix and reuses the matrix inverse already present in DAGMA's feasible region, at O(d3) cost; for order-based search, FLOP's grow-shrink parent procedure rejects any edge addition that would violate the constraints.
On synthetic benchmarks, both variants with correct NOTREKS information outperform their vanilla counterparts and are never significantly worse. Vanilla DAGMA barely beat the diagnostic baselines that order variables by marginal variance or by predictability, while FLOP already performed very well without prior information. DAGMA+NOTREKS improves significantly in every setting and on both metrics, with gains growing with sample size; FLOP+NOTREKS improves significantly in all sparse settings at n=100, for example reducing Ancestor-AID by a mean of 286 at k=4 and d=100.
Perspective
Experiments focus on linear-Gaussian structural equation models with heteroskedastic noise, with graphs drawn from Erdős–Rényi and Watts–Strogatz families; FLOP covers d of 20, 50 and 100, DAGMA covers d of 20 and 50. Priors are oracle NOTREKS information derived from the true graph, taken at fractions q of 0, one quarter and all available trek-free pairs.
Priors are assumed correct and complete, whereas practical priors may be incomplete or partly wrong; a false hard constraint excludes the true graph, while a soft penalty can trade violations against data fit. On the semi-synthetic manufacturing benchmarks CausalMan and CausalAssembly, data-generating mechanisms depart strongly from the assumed models, structural recovery is difficult for all methods, and NOTREKS information yields no consistent improvement. Constrained searches show a larger BIC gap to the ground truth, indicating they do not always find the best feasible graph.
