Conditional Independence Tests as the Weak Link in Causal Discovery

Paper: 2608.11156 Authors: Pavel Averin, Theodoros Moysiadis, Ioannis Katakis Categories: stat.ML, cs.LG

The Gap

There are two large, well-developed literatures that rarely talk to each other.

On one side, constraint-based causal discovery. PC, FCI, and their variants (stable-PC, RFCI, PC-simple, and the anytime/conservative flavors) are studied as graph algorithms: correctness proofs assume an oracle that answers “is X independent of Y given Z?” perfectly. Consistency results are stated conditional on that oracle. Everything downstream, skeleton pruning and v-structure orientation, is treated as combinatorics.

On the other side, conditional independence testing as a statistics problem. Fisher’s z for partial correlation, G-square / chi-square on contingency tables, likelihood-ratio and residual-based regression tests, k-NN and mutual-information estimators (CMI, KCMI, mixed-KSG), kernel tests (KCIT, RCIT, RCoT, CDC), and the newer machine-learning constructions (CCIT, GCIT, CRT / holdout-randomization, classifier two-sample tests). Each comes with its own asymptotics, its own null calibration, and its own failure mode. And there is the uncomfortable theoretical result hanging over all of it: for continuous variables with no smoothness restrictions, there is no CI test that has both valid level and non-trivial power against every alternative. The oracle the graph algorithms assume cannot exist in general.

The gap this survey targets is the seam. Existing surveys either enumerate causal discovery algorithms (with a paragraph on “you need a CI test”) or enumerate CI tests as a standalone estimation problem (with a footnote on “these are used in causal discovery”). What is missing is a systematic mapping from test-level statistical properties to graph-level errors: power decay as the conditioning set grows, asymmetric consequences of type I versus type II error, and what happens when you run millions of correlated tests with no coherent multiplicity control. The biomedical framing sharpens it, because that is exactly where the assumptions break: mixed continuous/ordinal/binary variables, n in the hundreds, p in the thousands.

[Problem: PC / FCI correctness assumes a perfect CI oracle]
                        |
                        v
[Reality: every real test is biased in a specific direction]
                        |
        +---------------+---------------+
        |                               |
        v                               v
[Assumption layer]              [Six test families]
 faithfulness                    partial-corr
 i.i.d. sampling                 contingency-table
 correct null calibration        regression
 no hidden confounders           nearest-neighbor
 (PC only)                       kernel
        |                        ML-based
        |                               |
        +---------------+---------------+
                        v
        [Method: taxonomy + robustness layers
         + error-propagation mapping]
                        |
                        v
        [Evidence: literature synthesis +
         R / Python library adoption audit]
                        |
                        v
        [Conclusion: mixed-type CI without
         discretization, small-n error control,
         scalability = still open]

The Increment

One sentence: Before, choosing a CI test was a data-type lookup (“continuous, so use Fisher’s z”); after, it is an error-budget decision, because the survey makes explicit which graph structures each test’s specific weakness will destroy.

Core Mechanism

A survey’s “method” is its organizing scheme, so let’s be concrete about what the scheme does. Layer one is the taxonomy into six families, and the taxonomy axis is not “how the statistic is computed” but what the test actually assumes about the data-generating distribution. Partial correlation tests linearity plus (approximate) joint Gaussianity, and detects only linear dependence, so a monotone-but-nonlinear edge is silently deleted. Contingency-table tests are assumption-light on functional form but require discretization and blow up combinatorially: the cell count grows like the product of level counts across the conditioning set, so with three ternary conditioners you already have 27 strata to fill. Regression-based tests trade the distributional assumption for a model-specification assumption. Nearest-neighbor and mutual-information estimators are nonparametric but pay the curse of dimensionality in the conditioning set and typically need permutation or local-permutation schemes because their null distribution has no closed form. Kernel tests get near-universal consistency in exchange for kernel/bandwidth choices and, in the original form, cubic cost in n. ML-based tests recast CI as a prediction or generative-modeling problem and inherit whatever bias the learner has, plus a dependence on sample splitting.

Layer two is the robustness wrapper set, and this is the part I found most useful conceptually. The wrappers are largely orthogonal to the families: rank/copula transforms (making Fisher’s z work on ordinal and heavy-tailed data), shrinkage and regularized precision-matrix estimation (making partial correlation survive p > n), permutation and local permutation (getting a valid null without asymptotics), bootstrap and subsampling, stratification/pooling to fix sparse contingency cells, sample splitting and cross-fitting for the ML tests, and multiplicity control layered on top. A single “test” as used in practice is thus a family plus a stack of wrappers, and the survey’s point is that the wrappers change the error profile as much as the family does.

Layer three is the propagation account, and it is where the survey earns its keep. The critical asymmetry: in PC, the null hypothesis is independence, so a test with low power fails to reject and therefore declares independence and deletes the edge. Power decay with conditioning set size is thus not neutral noise, it is a systematic bias toward sparser skeletons at exactly the higher-order conditioning stages. Worse, deletion is not a local event: the conditioning set Z that produced the deletion is stored as Sepset(X,Y), and v-structure orientation asks whether the middle node sits in that sepset. So one under-powered test corrupts an edge and the record used to orient neighboring triples, and Meek’s rules then propagate the wrong arrowhead across the graph. Inflated type I error (falsely rejecting independence) has the opposite and more benign signature: a denser skeleton, more edges to test, and higher runtime, but fewer confidently wrong arrows.

   raw data: mixed types, n ~ 10^2, p ~ 10^3
                    |
                    v
   +--------------------------------------+
   | LAYER 1  family = assumption set     |
   |                                      |
   |  partial-corr .... linear + Gaussian |
   |  contingency ..... discrete, dense    |
   |  regression ...... model correct      |
   |  nearest-nbr ..... low-dim Z          |
   |  kernel .......... bandwidth + O(n^3) |
   |  ML-based ........ learner bias       |
   +--------------------------------------+
                    |
                    v
   +--------------------------------------+
   | LAYER 2  robustness wrappers         |
   |  rank / copula transform             |
   |  shrinkage precision matrix          |
   |  permutation, local permutation      |
   |  bootstrap, subsampling              |
   |  cell pooling, sample splitting      |
   |  FWER / FDR control                  |
   +--------------------------------------+
                    |
                    v
             p-value  vs  alpha
                    |
        +-----------+-----------+
        |                       |
     reject                  accept
   (dependent)            (independent)
        |                       |
   keep X - Y            delete X - Y
        |                 AND store Z as
        |                 Sepset(X, Y)
        |                       |
        +-----------+-----------+
                    v
   +--------------------------------------+
   | LAYER 3  graph-level consequence     |
   |                                      |
   |  low power  ==> too-sparse skeleton   |
   |  high type I ==> too-dense skeleton   |
   |  bad sepset ==> wrong v-structure     |
   |                    |                  |
   |                    v                  |
   |            Meek rules propagate       |
   |            the error outward          |
   +--------------------------------------+

Here is the metaphor that made it click for me, and it is the one the paper’s biomedical framing invites: the CI test is a clinical lab assay, and the causal graph is the diagnosis.

Each of the six families is a different assay technology. Partial correlation is a cheap colorimetric strip: fast, reliable, but only detects one analyte in one chemical form. Contingency tables are manual cell counting under a microscope: no assumptions about mechanism, but you need enough cells in each field of view, and if you slice the sample into 27 fields you are counting three cells per field and reporting noise. Kernel tests are mass spectrometry: will detect essentially anything, expensive, and the answer depends on how you tuned the instrument. ML-based tests are a machine-learned image classifier: excellent where it was trained, quietly wrong outside that distribution.

Conditioning set size is the number of covariates you insist on matching before comparing patients. Match on age, and you still have hundreds of comparable patients. Match on age, sex, BMI, three comorbidities, and two medications, and you are comparing one patient to one patient. The assay is unchanged; the effective sample has evaporated. That is power decay, and the reason it bites in causal discovery specifically is the direction of the default: an inconclusive assay is read as “no association,” and “no association” means the doctor crosses a suspected mechanism off the list. The robustness wrappers are the lab’s calibration and controls: run the sample in triplicate (bootstrap), shuffle the labels to see what a null slide looks like (permutation), convert absolute readings to ranks so a miscalibrated machine still gives a valid comparison (rank transform), correct for the fact that you ran ten thousand assays today (FDR).

And the diagnosis logic is PC/FCI. A single false negative does not just remove one line from the chart. It gets written into the record as “we ruled this out while controlling for W,” and the next inference step reads that record to decide the direction of a neighboring relationship. One bad assay, propagated through the diagnostic protocol, yields a confidently stated causal claim that is backwards. That asymmetry, false negatives are structurally more damaging than false positives, is the survey’s central practical message.

Key Concepts

• Conditional independence, and why the “conditional” part is brutal: Plain independence asks whether knowing X tells you anything about Y. Conditional independence asks a harder question: among people who are *identical on Z, does knowing X still tell you anything about Y? Ice cream sales and drowning deaths are dependent; among days with the same temperature, they are not. The computational cruelty is that “identical on Z” is a slicing operation. Each variable you add to Z multiplies the number of slices and divides your data among them. With continuous Z there are no exact matches at all, so every method has to fake it: assume a functional form (regression), assume linearity (partial correlation), find approximate neighbors (k-NN), or embed the conditional distribution in a function space (kernel). Every CI test is a different answer to “how do I pretend I have matched samples when I do not.”

• Power decay with conditioning set size: Statistical power is the chance of catching a real dependence. It falls as Z grows, for reasons that differ by family but all reduce to shrinking effective sample size or growing degrees of freedom. Concretely: a genuine but modest dependence between two genes might be detected with an empty conditioning set at n = 200, survive conditioning on two variables, and become undetectable conditioning on five. PC tests conditioning sets in increasing order of size, so the tests it runs *late are the weak ones, and those are the ones deciding the subtle edges. If you have ever noticed that PC output gets suspiciously sparse as you raise the maximum conditioning-set depth, this is the mechanism.

• Asymmetric error consequences (sepset poisoning): PC finds a v-structure X to Z back-from Y when X and Y are non-adjacent and Z is *not in the separating set that removed the X-Y edge. So the sepset is not bookkeeping, it is the evidence for orientation. Suppose the true separating set for X and Y is {Z, W}, but an under-powered test accepts independence given {W} alone. The edge is correctly removed, but the stored sepset omits Z, and the algorithm now sees a v-structure that does not exist and orients two arrowheads into Z. Meek’s rules then propagate those arrowheads. A single missing element in a single sepset can flip the causal direction of a whole neighborhood, which is why a test being “slightly conservative” is not a slightly worse outcome.

Framework Shift

Before (mainstream practice):        After (this survey's framing):

  pick algorithm: PC                  target: which graph
        |                              features must be right?
        v                                     |
  pick test by data type                      v
  (continuous -> fisherz               error budget:
   discrete   -> gsq                   FN cost vs FP cost
   mixed      -> discretize)                  |
        |                                     v
        v                              choose family by
  run, get a graph                     assumption match
        |                                     |
        v                                     v
  worry about alpha                    add wrappers to patch
  and nothing else                     the specific weakness
                                              |
  test = interchangeable                      v
         black box                      run; read skeleton
                                        density + sepsets as
  CI test <--> graph                    diagnostics
  connection: unexamined                      |
                                              v
                                        test = calibrated
                                        instrument with a
                                        known bias direction

                                        CI test ==> graph
                                        error: traced

From “which test matches my data type” to “which graph errors can I afford,” the core shift is treating the CI test as an instrument with a known bias direction rather than an interchangeable subroutine.

Expert Assessment

A caveat up front: I am working from the abstract and framing, so my read on how deeply the error-propagation analysis is developed versus merely asserted is provisional. That distinction is exactly what determines whether this is a good survey or a very good one.

Problem choice: Real gap, not manufactured. The disconnect between causal-discovery theory (oracle assumed) and practice (whichever test the library defaulted to) is genuine, and practitioners feel it as unexplained instability across CI-test choices. The biomedical scoping is honest rather than decorative, because mixed-type, small-n, high-p is precisely the regime where the standard advice fails. Where it sits in the trajectory: this is consolidation work arriving after a decade of test proliferation (kernel tests circa 2011 onward, ML-based tests circa 2017 onward) and after the theoretical bad news about the impossibility of a universally valid and powerful CI test. That is the right moment for a survey. The risk is that the field has partly moved on to score-based and continuous-optimization methods (GES, NOTEARS-family) and to differentiable or amortized causal discovery, where the CI test is not the bottleneck. The survey should say why constraint-based methods still matter, and the honest answer, that FCI handles latent confounders in a way score-based methods largely do not, deserves to be made loudly.

Method maturity: The six-family taxonomy is conventional and mostly matches what you would draw yourself. The genuinely valuable contribution is the separation of “family” from “robustness layer,” because that is not how the literature usually presents it, and it explains a lot of practical confusion, e.g. that rank-transformed Fisher’s z is a meaningfully different test from Fisher’s z but appears under the same name in software. The test-property to graph-error mapping is the other real contribution. My concern is depth: this mapping can be done rigorously (finite-sample bounds relating test error rates to expected structural Hamming distance, or an analysis of sepset error propagation through Meek’s rules), or it can be done as narrative. Narrative is still useful, but it is not a result. A simpler alternative the field keeps overlooking, and which a survey is well placed to advocate: instead of chasing better tests, use stability across resamples as the primary edge criterion, i.e. stability selection at the edge level. That sidesteps calibration problems entirely and is criminally under-adopted.

Experimental integrity: A survey with no unified benchmark inherits every incomparability in its sources. Reported power and runtime numbers across CI-test papers use different simulators, different graph densities, different noise, and different alpha, so a synthesis of them is a synthesis of apples and oranges. If the paper includes even a modest common-protocol experiment, say six families times the same simulated mixed-type graphs at n = 100/500/2000, that would be the single highest-value addition. The R/Python library-adoption audit is the most verifiable and most immediately useful part, and it also functions as a quiet critique: the gap between what the literature recommends and what pcalg, bnlearn, causal-learn, and friends actually expose by default is where practitioner behavior is really determined. Red flag to watch for: survey tables that report each method’s strengths from that method’s own paper. Self-reported performance in a comparison table is a systematic optimism bias.

Writing quality: The predictable corner-cutting in this genre is the “open challenges” section, which tends to be a list of things nobody solved, stated at a level of generality that generates no research. The three named challenges (mixed-type CI without discretization, small-sample error control, scalability) are the right three, but they are only useful if each comes with a concrete formulation and a proposed evaluation. The section I would most want rewritten is the propagation analysis: turn it from prose into a small set of worked micro-examples, three or four nodes, showing exactly which test error yields which wrong graph, with the sepset contents printed. That single change would move the paper from “well-organized reference” to “thing people cite when they explain why their PC output is wrong.” Also, the mixed-type problem deserves more than a challenge bullet, because discretization is the most common silent methodological failure in applied causal discovery, and copula/rank and mixed-KSG approaches are mature enough to be given a proper treatment rather than a mention.

Verdict: weak accept — the family-versus-wrapper decomposition and the test-error to graph-error framing are genuinely useful and under-served, but without a common-protocol benchmark it remains a well-organized reading list rather than a source of new evidence.

Takeaways

Things you can actually take and use:

• The direction of the default matters more than the significance level. In any pipeline where “not significant” triggers a deletion or a rejection, low power is not conservatism, it is a systematic bias toward whatever the null implies. This generalizes far past causal discovery: feature-selection loops, automated data-quality gates, A/B test kill-switches. Ask “which way does an inconclusive test push my artifact?” before tuning alpha.

• Separate the estimator from its robustness wrappers when naming things. “Fisher’s z” and “rank-transformed shrinkage Fisher’s z” have different assumption sets and different failure modes. Any codebase that logs only the test name is losing the information that explains its own results. Log the wrapper stack.

• Effective sample size, not nominal sample size, is the quantity to track. In CI testing it is roughly n divided by the number of strata induced by Z. Compute it and refuse to run tests below a threshold, rather than letting the test silently return a meaningless p-value. Several PC implementations expose a maximum conditioning-set depth; the principled way to set it is from effective sample size, not from a round number.

• Intermediate artifacts are diagnostics. The separating sets PC produces are usually discarded, but they are the evidence trail for every orientation. Dumping them and checking whether they look plausible, right size, sensible membership, is cheap and catches the sepset-poisoning failure mode. The general lesson: when an algorithm makes a decision based on internal bookkeeping, expose the bookkeeping.

• Use library-adoption gaps as a research map. If the literature recommends a method and no mainstream library implements it, that is either a signal the method is impractical or a low-hanging contribution. Both are worth knowing before you start a project.

What is not here: no new test, no new bounds, no benchmark you can run. If you already know the CI-test landscape, read the taxonomy table and the library-adoption section and skip the rest.