Observational data can often narrow the causal graph only down to a family of graphs that fit the data equally well, called a Markov equivalence class. Within that family, many edges have no determined direction. When the relationships are nonlinear with additive noise, there is a known way to break the tie. Regress each variable on the other, and in the true causal direction the leftover noise (the residual) is independent of the input. In the wrong direction it is not (Hoyer et al.). The independence check is usually a kernel test, the Hilbert-Schmidt Independence Criterion (HSIC). It costs time quadratic in the sample size, so practitioners compress it with a small set of "landmark" points (the Nyström approximation), chosen more or less uniformly.
This proposal targets a quieter failure. In the wrong direction, the residual dependence often sits in a small region: the tails of the input, or places where the noise spread changes. HSIC sums dependence over all directions, which is a Frobenius-type measure, and uniform landmarks under-sample exactly those regions. The compressed test can therefore throw away the one weak signal that orients the edge. We propose to pick landmarks by ridge leverage scores (a per-point measure of how much a point contributes to directions the kernel can resolve), computed in the joint space of input and residual. We pair this with a test statistic built on the worst-case, largest-singular-value (spectral) size of the dependence, and apply the combined test to orient the undirected edges of a learned equivalence class.
Core Claim
At a fixed compute budget, a Nyström independence test with two ingredients will orient more edges of a Markov equivalence class correctly than uniform-landmark Nyström HSIC, random Fourier feature HSIC, or autoencoder-compressed tests. The first ingredient is landmarks drawn from ridge leverage scores of the joint (input, residual) kernel. The second is a statistic based on the operator (spectral) norm of the compressed cross-covariance, rather than its Hilbert-Schmidt norm. The gain should be concentrated where the backward-direction dependence is confined to a low-mass region: heteroscedastic noise, heavy-tailed causes, and saturating mechanisms.
The theoretical target is an operator-norm guarantee. Let $\Sigma$ be the cross-covariance operator between input and residual features, and let $\tilde\Sigma$ be its Nyström-compressed version with $m$ landmarks drawn from $\lambda$-ridge leverage scores. We aim to show
$$\|\Sigma - \tilde\Sigma\|_{2} \le C\lambda \quad \text{with} \quad m = O\big(d_{\text{eff}}(\lambda)\log(1/\delta)\big),$$
where $d_{\text{eff}}(\lambda)$ is the sum of ridge leverage scores (the effective number of kernel directions above level $\lambda$) and $\delta$ the failure probability. This form mirrors the standard ridge-leverage sampling argument for kernel matrices, which bounds error in every direction via matrix concentration. The consequence is that any single dependence mode with singular value above $2C\lambda$ survives compression. A Hilbert-Schmidt bound alone cannot promise this: a dependence of fixed Hilbert-Schmidt size can be split across many small modes, or one small mode can be dwarfed by aggregate error.
Relation to Prior Work
The method builds on three lines of work.
- The test we modify. Nyström M-HSIC compresses multi-variable HSIC with Nyström landmarks, proves $O(n^{-1/2})$ consistency, and uses the test to orient causal pairs in weather data. It uses uniform-style landmarks and gives only scalar consistency guarantees, with no operator-norm control. Both omissions are what we change.
- Where the sampling rule comes from. Chatalic et al. show that approximate kernel ridge leverage scores for Nyström landmarks keep minimax power in two-sample testing. We move that sampling rule to independence testing of regression residuals. That setting differs in two ways: the relevant geometry is a joint space rather than a pooled sample, and the residuals are themselves estimated.
- Why uniform sampling should lose. Li et al. show uniform sampling can be minimax-suboptimal when the target lies outside the model's function space. Rudi et al. show data-independent random features need many more features than leverage-informed ones.
Two further papers motivate the spectral focus. Mangoubi et al. and d'Orsi et al. show, for private covariance estimation, that estimators optimal in Frobenius error can still misalign low-energy directions. We conjecture the same pathology for compressed dependence operators; we are not transferring a proof.
Two scaling efforts are our competitors rather than our tools:
- KIKO reduces the number of regressions with a shared denoising autoencoder and runs HSIC on its bottleneck. It has no distortion control.
- ReScore upweights hard-to-fit samples in differentiable DAG learning. It finds, and warns, that pure noise outliers also have high error, so it needs a manual cutoff.
ReScore's warning constrains our design. Leverage scores also push sampling probability toward isolated points, so heavy-tailed corruption could hijack the landmarks. This is why the ridge parameter $\lambda$, a cap on per-point probability, and a contamination experiment are part of the method rather than afterthoughts.
Research Program
The pipeline has three stages.
- Learn the equivalence class. Run PC or GES from causal-learn to obtain the partially directed graph (CPDAG).
- Test each undirected edge both ways. For each undirected edge, fit a nonlinear regression in both directions, using the parent set implied by the current partial orientation. Test residual-versus-input independence with the proposed test.
- Propagate. Accept an orientation only if one direction passes and the other fails. Then apply the standard orientation-propagation rules.
The proposed test works as follows. Compute approximate ridge leverage scores of the product kernel on (input, residual) pairs, using recursive approximation so the cost stays near-linear in $n$. Draw $m$ landmarks with capped probabilities and reweight. Form the $m$-dimensional compressed cross-covariance and take its largest singular value as the statistic. Calibrate by permutation, reusing the landmarks across permutations as in the two-sample setting of Chatalic et al..
The analysis has three parts. First, we will attempt the operator-norm bound above. Second, we will derive the consequence for edge orientation: a separation condition on the backward-direction top singular value under which orientation is correct with high probability. Third, we will state honestly the regime where the spectral statistic should lose to the Hilbert-Schmidt one, namely dependence spread evenly over many modes. That regime is where HSIC's summation helps rather than hurts.
Baselines
Uncompressed reference. The naive reference is exact HSIC with the same regressions, run on a uniform random subsample small enough to match our wall-clock budget. As a quality ceiling, exact HSIC is also run on full data wherever it fits in memory, which includes all Cause-Effect Pairs.
Uniform Nyström HSIC. This is Nyström M-HSIC with uniform landmarks (Kalinke & Szabó). It is the closest existing method and the strongest direct competitor, because it already matches exact-HSIC power at a fraction of the cost. We give it the same regressions, the same kernel bandwidth rule, and the same wall-clock budget. The last point means it may use more landmarks than we do, since we pay for leverage estimation. We sweep its landmark count on the same grid as ours. Beating it means strictly higher orientation accuracy at equal time, not at equal landmark count.
Random Fourier feature HSIC. This uses a feature count chosen to match time. It is the data-independent alternative that Chatalic et al. found to match leverage-Nyström power in two-sample testing, so it is a genuine threat.
Published systems. KIKO is run on the 100-pair Cause-Effect Pairs benchmark. Assaad et al. report 57% accuracy for ANM-pHSIC and 64.5% for their SKIKO-RT variant. The 64.5% figure is the strongest reported number we must exceed on that benchmark. For the 8-pair version, Mooij & Janzing report that additive noise models orient 6 of 8. For Nyström M-HSIC we found no reported result on Lacuna on Cause-Effect Pairs, so we will run it ourselves.
Ablations. Two cross ablations isolate the key ingredients:
- leverage landmarks with the Hilbert-Schmidt statistic, versus uniform landmarks with the spectral statistic;
- marginal leverage scores (input only), versus joint leverage scores.
The joint-versus-marginal comparison tests whether the joint geometry matters at all.
Why not just…?
Why not just use more uniform landmarks? This is the most serious threat. If the dependence region is not very small, doubling the uniform landmark count may recover it more cheaply than computing leverage scores. The equal-wall-clock comparison settles it. We also sweep how much of the sample carries the backward-direction dependence, from 50% down to 1%. We predict the two methods tie at 50% and the gap opens as the region shrinks. If no gap appears at any mass level, the leverage ingredient should be dropped.
Why not just use random Fourier features? They avoid kernel matrices entirely. However, Rudi et al. indicate that data-independent features need many more features to capture localized structure. Chatalic et al. found parity with leverage-Nyström in the two-sample setting, not dominance. We expect parity when the dependence is spread out and an advantage for our test only in the tail-concentrated regime. The mass sweep tests exactly this.
Why not just keep HSIC and skip the spectral statistic? HSIC is well calibrated and widely used, and it is the better statistic when dependence is diffuse. The ablation that swaps only the statistic will show whether the spectral statistic helps on concentrated dependence and how much it costs on diffuse dependence. If it only ever ties or loses, we report leverage-landmark HSIC as the method.
Why not just reweight hard samples as ReScore does? ReScore needs a differentiable DAG learner and a tuned cutoff. Its gains on Sachs were modest: structural Hamming distance fell from 16 to 13 with NOTEARS-MLP and from 15 to 14 with GOLEM (Zhang et al.). We run ReScore on the same Sachs data and on our synthetic graphs. Both it and our method are subjected to heavy-tailed contamination to see which one's weighting is hijacked by outliers.
Proposed Experiments
Synthetic graphs. We use Erdős-Rényi and scale-free DAGs with 20 to 200 nodes and sample sizes from $10^4$ to $10^6$, the regime where exact HSIC cannot be run. The nonlinear mechanisms are chosen so that backward dependence is either diffuse or tail-concentrated; the latter covers heteroscedastic noise, heavy-tailed causes, and saturating functions. The primary metrics are:
- fraction of equivalence-class-undirected edges correctly oriented;
- structural Hamming distance and structural intervention distance;
- permutation-calibrated Type-I error at nominal 0.05;
- wall-clock time.
Contamination. We inject 0.1% to 5% gross outliers. This tests whether capped ridge leverage sampling stays robust, which is the tension raised by ReScore's findings.
Real data. We use the 8-pair and 100-pair Cause-Effect Pairs benchmarks, where exact HSIC is feasible and serves as the ceiling. We also use the Sachs protein network, where published structural Hamming distances give reference points.
Decisive checks. The proposal succeeds on three conditions. First, at matched time, joint-leverage landmarks beat uniform Nyström HSIC on orientation accuracy, with a gap that grows as the dependence region shrinks. Second, Type-I error stays at nominal level. Third, the contamination experiment does not erase the gain. It fails if the gap vanishes once uniform Nyström is given the extra landmarks our overhead would have bought.
References
- Nonlinear causal discovery with additive noise models
- Nyström M-Hilbert-Schmidt independence criterion
- An Efficient Permutation-Based Kernel Two-Sample Test
- Optimal Convergence Rates for Agnostic Nyström Kernel Learning
- Generalization Properties of Learning with Random Features
- Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations
- On Purely Private Covariance Estimation
- Scaling Causal Inference in Additive Noise Models
- Boosting Causal Discovery via Adaptive Sample Reweighting
- Causal-learn: Causal Discovery in Python
- Distinguishing between cause and effect