Certified Cheap Kernel Tests for Non-Linear Causal Search

Finding cause-and-effect structure among many variables from observational data means running thousands of statistical tests that ask whether two variables are independent, possibly given others. When relationships are non-linear, the tests that work are kernel tests. A kernel test compares variables through $n \times n$ similarity matrices built from the $n$ samples, and computing one exactly costs roughly $O(n^3)$. Search methods that avoid the traps of greedy edge-adding therefore tend to fall back to linear scores, or cap out at a few dozen variables. The usual remedy is to replace each similarity matrix with a low-rank sketch at some fixed rank. That makes tests cheap, but it quietly changes their answers, and nobody can say which search decisions were flipped.

We propose a different contract. Every test is a yes/no comparison of a statistic against a threshold. For positive semidefinite similarity matrices, the error introduced by a low-rank sketch can be bounded exactly and cheaply. So we run each test at a small rank, and we only spend more rank when the certified error interval still straddles the threshold. Decisions settled this way are, by construction, the decisions the exact test would have made. The search therefore returns the same graph as an exact-kernel search, at a fraction of the cost. Choosing how much rank to spend before knowing how much is needed is an online problem, and we analyze it the way online algorithms are analyzed. The compute paid is compared to an offline oracle that knows in advance the smallest rank that settles each test. The saved compute is then reinvested in non-greedy search with non-linear tests, a combination prior work called prohibitive.

Core Claim

The claim has three parts. First, a certified sketch can make kernel-test-driven causal search output-identical to its exact counterpart while cutting test cost by large factors on realistic data. Second, a simple rank-doubling policy has a constant competitive ratio on compute against the rank oracle. The open and interesting question is how much better one can do when sketches are shared across the many tests that reuse the same variable's similarity matrix. Third, the savings are large enough to run search procedures that escape greedy local optima, namely less greedy equivalence search and permutation search, with non-linear tests at sample sizes where they are currently out of reach.

The certificate is what makes the idea concrete. Take the HSIC statistic, a kernel measure of dependence equal to $\frac{1}{n^2}\mathrm{tr}(KHLH)$. Here $K$ and $L$ are the $n\times n$ similarity matrices of the two variables and $H$ is the centering matrix. Suppose we replace $K$ by a sketch $\hat K$ with $\hat K \preceq K$. Column-sampling (Nyström) sketches satisfy this, and so do projections of the form $QQ^\top K QQ^\top$. The residual $E = K - \hat K$ is then positive semidefinite, and

$$\left|\mathrm{HSIC}(K,L) - \mathrm{HSIC}(\hat K, L)\right| \le \frac{1}{n^2}\,\big(\mathrm{tr}(K) - \mathrm{tr}(\hat K)\big)\,\lambda_{\max}(HLH).$$

The bound follows from $\mathrm{tr}(EM) \le \mathrm{tr}(E)\,\|M\|_{op}$ for positive semidefinite $E$ and $M$. Both traces are cheap to compute: for a Gaussian kernel $\mathrm{tr}(K)=n$ exactly. The top eigenvalue of $HLH$ can be bounded from a sketch of $L$, and approximating $L$ as well adds a symmetric term. The bound is deterministic. It does not rely on the Gaussian sketch assumptions whose heavy-tailed limits Perturbation Analysis of Randomized SVD and its Applications to High-dimensional Statistics flags as unresolved. Randomization only affects how quickly the bound shrinks, not whether it holds.

Research Program

The first component extends the certificate from unconditional HSIC to the conditional tests that structure learning actually uses. These are kernel conditional independence tests built from residualized similarity matrices, as used in the PC-KCI skeleton step of OCDaf. The certificate also has to cover the test's threshold, since the standard gamma approximation to the null distribution is itself a function of traces of the same matrices. The conditional case is where we expect real technical work. Residualization introduces a regularized inverse, and its sensitivity to the sketch must be bounded without reintroducing cubic cost. We will use the a-priori analysis of Zhang and Tang, which shows that two or three power iterations recover exact-SVD statistical rates, to predict how fast the interval shrinks with rank. The trace certificate remains the thing that actually decides. Boullé and Townsend show that sketches drawn from an informed prior covariance beat white-noise sketches on operators with fast spectral decay. We will test whether such prior-informed sketches tighten our intervals on kernel matrices, which have exactly that decay; their paper only studied physics operators.

The second component is the online analysis. Each test $i$ has an unknown smallest settling rank $r_i^\*$. Running at rank $r$ costs $c(r)$, roughly linear in $r$ for column-sampling sketches at fixed $n$. The offline oracle pays $\sum_i c(r_i^\*)$. A doubling policy that recomputes from scratch pays at most four times the oracle, by the geometric-series argument familiar from search on a line. Nested sketches that reuse earlier columns should bring this toward two, and a randomized starting rank should improve further. The question we care about is the shared setting. One variable's similarity matrix enters hundreds of tests, so refining it once helps many pending decisions. Deciding which shared matrices to refine then resembles online covering problems more than independent ski-rental instances. We aim to prove an upper bound for a natural greedy refine-the-most-blocking-matrix policy, together with a lower bound, and to report the gap honestly if it does not close. This is the same kind of open gap catalogued for online matching and clustering in Closing the Optimality Gap in Online Algorithms. Note what is being bounded: compute relative to an oracle, not graph accuracy. Accuracy is pinned to the exact-test answer by the certificate.

The third component plugs the certified tests into two searches chosen because they are already designed against greedy traps. One is Less Greedy Equivalence Search. Its insertion rules check candidate edges against conditional independencies, but it was run with linear Gaussian tests and scores. We substitute certified kernel tests in the insertion checks. The other is permutation search in the style of IGSP. It searches over variable orderings and is consistent where graph-space greedy search provably is not. It already uses non-parametric tests but scaled to about 24 nodes. In both, test outcomes are cached by conditioning set, so the online refinement policy sees the true sharing structure of the search.

Baselines

The naive reference is standard greedy equivalence search with a linear Gaussian score, run through causal-learn. It shows how much non-linearity matters at all. It is the method whose false-positive accumulation and precision saturation are documented in Improving Causal Discovery By Optimal Bayesian Network Learning.

The most important competitor is the same search with fixed-rank sketched kernel tests: Nyström at a single rank $k$, tuned over a grid. Exact kernel tests are only run at sizes where they are affordable. Fixed-rank sketching is what a practitioner would do tomorrow, and it is the main threat to the proposal. We will give the fixed-rank variant the same wall-clock budget as our adaptive method and select its rank on held-out synthetic graphs, not test graphs. Beating it means one of two things. Either our method matches exact-test output at lower cost than the smallest fixed rank that also matches it, or, at equal cost, it gets lower structural Hamming distance (SHD, the number of edge additions, deletions, and reversals needed to fix the graph) because fixed-rank sketching flips decisions.

The exact-kernel version of each search is the accuracy ceiling, since our output should equal it wherever it can be run.

For overall accuracy among non-linear structure learners, the strongest reported number in the file is from OCDaf: OSLow reaches SHD 10.4 on Sachs, against 12.0 for CAM and 13.0 for GraN-DAG (Gradient-Based Neural DAG Learning). We rerun OSLow and CAM on our splits rather than copying these numbers. For less greedy equivalence search the file reports roughly halved SHD and a tenfold speedup over GES on graphs of 150+ variables, with no Sachs scalar; no reported result found on Lacuna for its Sachs SHD. For tree search, CD-UCT has no scalar results in the file; we include it with a linear score as a representative of compute-heavy non-greedy search.

The key ablation removes the certificate but keeps the adaptivity: refine rank on a heuristic (stop when the statistic changes by less than 5% between ranks). This separates the value of certification from the value of adaptivity.

Why not just…?

Why not just use a single well-chosen sketch rank? This is the real threat. If kernel spectra on these benchmarks decay fast enough that one modest rank settles nearly every test, the adaptive machinery buys little. We will measure the distribution of settling ranks $r_i^\*$ directly. A tight distribution means fixed rank wins, and we would report that and narrow the claim to the certificate as an audit tool. A heavy upper tail, with a few near-threshold tests needing high rank, means fixed rank either overpays everywhere or silently flips exactly the borderline decisions that shape the graph.

Why not just subsample the data so exact tests become affordable? Subsampling cuts $n$, which cuts power on precisely the weak dependencies that decide edges. Our method keeps all $n$ samples and spends compute only where decisions are close. The comparison at matched compute on the Perturb-seq data (about 30,000 cells) settles this. If subsampled exact tests match our SHD, the sketching contribution is moot at that scale.

Why not just stay linear, with linear Gaussian scores or linear non-Gaussian models? Linear models only see low-order moments and misorient non-linear mechanisms. The Sachs comparison above, where non-additive flows beat additive and linear-leaning baselines, is the file's evidence on real data. The bivariate evidence is LSIR, at a 0.77 identification rate versus 0.48 for HSIC regression on the 80 cause-effect pairs. The linear baseline stays in every table so the gap is measured, not assumed.

Why not just use exact search such as integer programming or A*? Integer programming methods need a precomputed cache of scores for every candidate parent set. With non-linear scores that cache is itself the cubic bottleneck multiplied many times over. Triplet A* tops out near 60 variables even with linear scores. Our certified tests could in principle fill such caches more cheaply, but we treat that as a follow-up, not a competitor.

Proposed Experiments

The first check is fidelity. On synthetic Erdős–Rényi graphs with non-linear additive and location-scale noise ($d$ from 10 to 100, $n$ from 1,000 to 20,000), we run each search with exact and certified tests wherever exact is feasible. We report the fraction of test decisions that differ, which should be zero. We also report wall-clock time and the empirical ratio of compute to the settling-rank oracle, computed after the fact from exact runs. The fixed-rank baseline is reported on the same graphs together with its decision-flip rate.

The second check is on the competitive analysis. We compare measured ratios of the doubling, nested, and shared-refinement policies against the proven bounds. We also construct adversarial sequences of near-threshold tests to probe whether the lower bound is approached.

The third check is downstream accuracy at scales currently out of reach. We run certified kernel versions of less greedy equivalence search and permutation search on Sachs and SynTReN, and report SHD against the rerun OSLow, CAM, GraN-DAG, and linear GES. We then use Perturb-seq, holding out one knockout as IGSP did, and score prediction of its downstream effects.

On the bivariate pairs and the nine E. coli regulatory links, we check that certified HSIC-based direction tests reproduce exact-kernel decisions. LSIR's reported 49 correct pairs and 7 of 9 forced-choice links serve as reference points, not targets.

The decisive outcome is whether certified adaptive tests beat the tuned fixed-rank sketch on compute at equal fidelity on Perturb-seq-scale data. If they do not, the proposal reduces to a useful audit certificate, and we will say so.