Rank-Limited Partial Correlation: Telling Real Edges from Mixture Artifacts

When a dataset secretly mixes several subpopulations, such as drug responders and non-responders or cells under different stimuli, two variables can look directly linked even though they are unrelated within every subgroup. The apparent link comes from the groups having different averages or different mechanisms, so it survives any amount of ordinary adjustment for other measured variables. Partial correlation (the correlation left after regressing both variables on a set of controls) cannot tell these "emergent" links from real ones. Its kernel generalizations cannot either. The causal-discovery methods that do separate them need roughly a hundred times more data. This proposal rests on a simple algebraic fact. If $X$ and $Y$ are independent within each of $K$ hidden groups, then all of their pooled dependence, measured through any collection of nonlinear features, has rank at most $K-1$. A genuine direct effect almost never has that property.

We propose a test built on this fact, which we call rank-limited partial correlation. It splits a conditional dependence into a low-rank part that $K$ hidden groups could explain and an "excess-rank" remainder that they cannot. The test flags an edge as real only when the excess-rank part is nonzero. The test is local, needs no clustering of samples, and plugs into any constraint-based search in place of the usual conditional independence test. The rank budget it estimates, shared across many variable pairs, also gives estimates of the number of groups and of the variables whose mechanisms change. Prior methods either assume these quantities are known or fit them with repeated mixture estimation.

Core Claim

Take a pair $X, Y$ and a conditioning set $Z$. Suppose $X \perp Y \mid Z, y$, where $y \in \{1,\dots,K\}$ is an unobserved group label. Choose feature maps $\phi(X)$ and $\psi(Y)$, for example polynomial or kernel features. For each value $z$, write $m_k(z) = E[\phi(X)\mid z, y=k]$ for the group-$k$ feature means of $X$ and $n_k(z) = E[\psi(Y)\mid z, y=k]$ for those of $Y$. Write $\pi_k(z)$ for the probability of group $k$ given $z$. The local cross-covariance is then

$$C(z) = \mathrm{Cov}\big(\phi(X), \psi(Y) \mid z\big) = \sum_{k=1}^{K} \pi_k(z)\,\big(m_k(z)-\bar m(z)\big)\big(n_k(z)-\bar n(z)\big)^{\top},$$

where $\bar m(z)$ and $\bar n(z)$ are the $\pi$-weighted averages of $m_k(z)$ and $n_k(z)$. The right-hand side has rank at most $K-1$ whatever the features are. This holds whether groups differ in means, in edge weights, or in nonlinear mechanisms. When there is a direct edge, $C(z)$ generically has unbounded rank. For a Gaussian pair with residual correlation $\rho$, its singular values in a Hermite basis decay as $|\rho|^j$. The proposed statistic is the excess-rank dependence

$$T_r = E_z\Big[\sum_{j>r} s_j\big(\tilde C(z)\big)^2\Big],$$

where $\tilde C(z)$ is $C(z)$ normalized by the feature variances, $s_j$ denotes its $j$-th singular value, and $r$ is the rank budget. Setting $r=0$ gives total conditional dependence, the quantity that kernel partial correlation and the Hilbert-Schmidt independence criterion (HSIC) measure. Setting $r=K-1$ removes exactly what $K$ hidden groups can produce.

The point is that an emergent edge and a real edge differ in the shape of the dependence, not only in its size. Testing shape is much cheaper than waiting until between-group variance is resolved well enough for ordinary separation tests to find the separating set.

Relation to Prior Work

Three papers establish that the problem exists and set its difficulty. Separability Analysis for Causal Discovery in Mixture of DAGs defines emergent edges and the set $\Delta$ of variables whose mechanisms vary. It runs a two-stage constraint-based algorithm with either partial correlation or the Generalized Covariance Measure (GCM, a regression-residual conditional independence test). It reports that union edges are recovered at $N=1{,}000$, while emergent edges need up to $N=100{,}000$. Its orientation stage also assumes $\Delta$ is known. Causal Structure Discovery from Distributions Arising from Mixtures of DAGs shows that the FCI algorithm (a constraint-based search that allows hidden confounders) applied to pooled data recovers the union of component graphs, with bidirected edges marking varying nodes. That result requires all components to share one causal ordering. A Causal Direction Test for Heterogeneous Populations shows that unadjusted HSIC on heterogeneous pairs has a Type I error of 0.796, and that conditioning on inferred partitions brings it to 0.048. All three motivate this proposal. None of them uses the structure of the dependence to separate the two edge types; they rely on separating sets, oracle $\Delta$, or explicit partitioning.

The method draws on Kernel Partial Correlation Coefficient - a Measure of Conditional Dependence. That paper defines kernel partial correlation (KPC) and gives near-linear-time nearest-neighbor-graph estimators of conditional dependence. We reuse its local-neighborhood estimation, but replace its scalar summary of $C(z)$ with a spectral tail. In the mixture setting KPC is exactly the $r=0$ case, and it inherits the false-positive problem the file documents for pooled tests.

Two lines of work constrain the design. Causal Mixture Models: Characterization and Discovery fits mixtures of linear regressions with a latent-aware BIC inside greedy search, running EM at every edge operation. It also shows that two or more components make linear Gaussian directions identifiable. It is the strongest joint-modeling competitor. Its cost and its restriction to linear models are the gap we target, not its accuracy. The mechanism-clustering papers, Causal Inference and Mechanism Clustering of A Mixture of Additive Noise Models and Specific and Shared Causal Relation Modeling and Mechanism-Based Clustering, show that clustering by feature location fails when groups differ in mechanism. That rules out a naive cluster-then-test design, and it is why our test never assigns samples to groups.

Research Program

The first component is theory. We will make precise when a direct edge produces excess rank. Within-group independence implies rank at most $K-1$ unconditionally. The converse fails in one known case: when $Y$ depends on $X$ only through a $K$-valued function of $X$, such as a hard threshold. That case is observationally identical to a mixture, and we will state it as an identifiability limit rather than hide it. For linear Gaussian components with residual correlation $\rho$, the leading excess singular value scales as $\rho^2$. We therefore expect the sample size needed for detection to grow like $\rho^{-4}$, because estimating a second-order moment to precision $\epsilon$ costs $\epsilon^{-2}$ samples. We will check this scaling directly, since it defines where the method should beat separation-based tests and where it should not.

The second component is estimation and calibration. Following KPC, we form local neighborhoods in $Z$ using nearest-neighbor graphs. Within each neighborhood we compute the cross-covariance of truncated feature bases: low-order Hermite polynomials, or random Fourier features. We then take its tail singular values and average them. Permutation calibration is invalid here because it destroys the rank-$(K-1)$ null structure. We will instead calibrate by bootstrapping from a fitted rank-$(K-1)$ factorization, and we will compare this against a sample-split variant that estimates the factors on one half and tests the remaining dependence on the other.

The third component exploits sharing across pairs. A single hidden label shifts the feature means of every variable in $\Delta$, so the left factors $m_k - \bar m$ for variable $X$ are the same across all partners $Y$. Stacking local cross-covariances of $X$ against many partners gives a pooled estimate of $K$, taken as the shared rank. It also gives a per-variable score for membership in $\Delta$, namely whether a variable carries any shared low-rank component. This is the upstream $\Delta$ estimator that the separability work assumes.

The fourth component is integration into search. We will plug the test into the PC skeleton search (constraint-based search that deletes edges whose endpoints test independent), passing it the estimated rank budget. We will also feed the estimated $\Delta$ into the orientation stage of the separability algorithm. The test itself is local and does not need a shared ordering across groups. Whether the full pipeline tolerates groups with reversed edges is an empirical question we will test, not a claim we make in advance.

Baselines

The naive reference is pooled partial correlation inside the PC skeleton search, run on the same samples with the same significance level and conditioning-set limits. This is the test used in Separability Analysis for Causal Discovery in Mixture of DAGs. It treats emergent and union edges identically and sets the floor any proposal must clear.

The strongest constraint-based competitor is the full separability algorithm with GCM tests. We run it twice. Once it has the oracle $\Delta$, which is the setting in which the paper reports skeleton precision above 0.9 at $N=1{,}000$ and emergent-edge resolution needing up to $N=100{,}000$. Once it uses our estimated $\Delta$. Beating it means reaching comparable emergent-edge precision and recall at $N \le 2{,}000$ without oracle $\Delta$. A practical reading is that our method at $N=2{,}000$ should match what the oracle-$\Delta$ GCM version achieves at $N \ge 20{,}000$.

The strongest joint-modeling competitor is Causal Mixture Models: Characterization and Discovery, run with its released settings and given the same wall-clock budget, with unlimited time reported separately. Its summary reports that it outperforms PC, GES, and LiNGAM in true positive rate and separation distance, and that it beats MixUTIGSP on Sachs. No reported numerical result was found on Lacuna for its structural accuracy. On linear mixtures we would count it a win to match CMM's structural error within its variance at a fraction of its runtime. On nonlinear mixtures, where CMM is misspecified, we expect to beat it outright.

We also run FCI on pooled data from Causal Structure Discovery from Distributions Arising from Mixtures of DAGs as the reference for $\Delta$ detection through bidirected edges. A two-step pipeline that fits a Gaussian mixture and then runs per-cluster PC serves as the cluster-first reference.

The ablation that isolates the key ingredient is the same estimator with rank budget $r=0$, which is essentially pooled KPC. Any gain over this ablation comes from the rank-limited idea alone, not from the features or the neighborhood construction. An oracle that stratifies on the true label $y$ and runs within-group partial correlation gives the upper bound.

Why not just…?

Why not just cluster the samples first and run partial correlation within each cluster? On mechanism-shift data the clusters are wrong. Mechanism-aware clustering reached an Adjusted Rand Index of 0.503 on the BAFU air-quality data, while k-means and Gaussian mixtures were near zero (Causal Inference and Mechanism Clustering of A Mixture of Additive Noise Models). On Sachs, k-means failed where SSCM reached 0.92 (Specific and Shared Causal Relation Modeling and Mechanism-Based Clustering). This alternative is a real threat when groups are well separated in their means. Our synthetic sweep therefore varies mean separation from large to zero, so the regime where clustering suffices is reported, not assumed away.

Why not just use a nonparametric conditional dependence measure such as KPC on the pooled data? Emergent dependence is real dependence in the pooled distribution, so any consistent test detects it. The file reports unadjusted HSIC Type I error of 0.796 on heterogeneous Tübingen pairs (A Causal Direction Test for Heterogeneous Populations). Our $r=0$ ablation is exactly this alternative, and the comparison isolates what the rank budget adds.

Why not just model the pooled precision matrix as sparse plus low-rank? For mixtures that differ only in means, the pooled covariance is the shared within-group covariance plus a rank-$(K-1)$ term. Its inverse is then the within-group precision minus a low-rank correction, which is exactly the structure latent-variable graphical models estimate. This is a genuine threat in that regime. We include such an estimator as a baseline, though no reported result for it was found on Lacuna. The decomposition breaks down when groups differ in edge weights, because the within-group covariances then differ and no single sparse precision exists. The rank-limited test still applies in that case. The synthetic grid contrasts mean-only shifts with weight shifts to settle the question. If the sparse-plus-low-rank estimator matches us on weight shifts, the proposal's scope shrinks to the nonlinear setting.

Why not just run the joint mixture model? CMM is likely as accurate on linear data. Its cost is EM at every search step, and it is linear by construction. The runtime-matched comparison and the nonlinear additive-noise mixtures decide whether our method's advantage is speed only or also accuracy.

Proposed Experiments

The synthetic core follows the Erdős–Rényi linear SEM mixtures of the separability paper. We use $K \in \{2,3,4\}$, mixing ratios up to 90/10, and $N \in \{500, 1{,}000, 2{,}000, 5{,}000, 20{,}000\}$, with shifts in means only, weights only, and both. A nonlinear arm uses additive-noise mixtures in the style of the mechanism-clustering paper. A third arm includes edge reversals across groups to probe the shared-ordering requirement. We report precision and recall separately for union and emergent edges, the accuracy of estimated $K$, $\Delta$ recovery, structural Hamming distance, runtime, and Type I error at nominal 0.05.

On real data, Sachs flow cytometry treats the intervention condition as the hidden label. Here we report the clustering ARI obtained from samples projected onto estimated $\Delta$ variables, against SSCM's 0.92, and the graph error against CMM. The 41 heterogeneous Tübingen pairs test calibration against the adjusted HSIC Type I error of 0.048. The ovarian cancer expression data serve as a qualitative check of whether BIRC3 emerges as a high-scoring $\Delta$ node, as FCI on the pooled data found.

The decisive check is emergent-edge F1 at $N=2{,}000$ on the weight-shift arm. If rank-limited partial correlation without oracle $\Delta$ does not clearly exceed the $r=0$ ablation and pooled GCM there, the core claim fails. A second check is the measured sample requirement for detecting true edges as a function of $\rho$. If it is far worse than the predicted $\rho^{-4}$, the method's useful range is narrower than claimed, and we will report that boundary.