Nonlinear dependence#

Cover: a harmonograph tracing a figure of cosine curves, one curve amber, drawn in navy lines
Shu Wan · · Andrey 0.8.0

A constraint-based method learns a graph from independence tests. Its result depends on the test. The default test, partial correlation, detects only linear dependence. When an effect is nonlinear, it can miss an edge or add a false one. In 0.8.0, you can use PC, FCI, GFCI, and CD-NOD with four supported tests that detect nonlinear dependence: KCI, RCoT, CMIknn, and GPDC. Each runs faster than the package we measured it against at every size we timed, at the same level of accuracy: PC with RCoT runs more than 5x faster than causal-learn and more than 9x faster than pcalg.

TL;DR#

  • Four supported nonlinear tests: indep_test="kci", "rcot", "cmiknn", and "gpdc", in pc, fci, gfci, and cdnod.

  • Faster than the reference package at every size we timed, at the same level of accuracy: PC with RCoT runs 5.9x to 36x faster than causal-learn and 9.5x to 29x faster than pcalg.

  • KCI and CMIknn also run on a CUDA GPU, with the same graphs as on the CPU.

What partial correlation misses#

Partial correlation asks whether y rises or falls with x in a straight line. Many effects do not: a dose helps up to a point and then harms, a signal repeats, a cost grows with the square of a size. Each panel below has 400 points with the same noise.

Partial correlationKCIRCoTCMIknnGPDC
y = x✓p < 0.001✓p < 0.001✓p < 0.001✓p = 0.002✓p < 0.001
y = cos(x)✗p = 0.17✓p < 0.001✓p < 0.001✓p = 0.002✓p < 0.001
y = x²✗p = 0.23✓p < 0.001✓p < 0.001✓p = 0.002✓p < 0.001
Three ways y depends on x, each with the same noise; ✓ finds the dependence at alpha 0.05. Partial correlation measures only a straight-line trend, so it misses the cos and the square; KCI, RCoT, CMIknn, and GPDC find all three.

All the tests detect the linear dependence. For the cosine and the square, y depends on x, but the straight-line trend is flat, so partial correlation misses the dependence. KCI uses kernels to compare the two variables and detects all three relationships.

An example#

We simulate 500 rows of 8 variables, each a weighted sum of the cosines of its causes plus noise. We fit PC with partial correlation and with each nonlinear test, then count the true edges each finds.

example.py#
import andrey
from andrey.data import sample_scm

data = sample_scm(d=8, n=500, functional="nonmonotone", density=2.0, scale="standardize", seed=0)
true = data.graph.adjacency != 0
true |= true.T

for test in ("fisherz", "kci", "rcot", "cmiknn", "gpdc"):
    fit = andrey.pc(data.data, alpha=0.05, indep_test=test)
    found = fit.structure.adjacency != 0
    found |= found.T
    hits, extra = (found & true).sum() // 2, (found & ~true).sum() // 2
    print(f"{test:>7}: {hits} of {true.sum() // 2} true edges, {extra} extra")
example.py#
fisherz: 3 of 8 true edges, 4 extra
    kci: 8 of 8 true edges, 0 extra
   rcot: 8 of 8 true edges, 0 extra
 cmiknn: 8 of 8 true edges, 0 extra
   gpdc: 7 of 8 true edges, 0 extra

True graph

ABCDEFGH

8 links

Partial correlation

ABCDEFGH

3 of 8 found, 4 extra

KCI

ABCDEFGH

8 of 8 found, 0 extra

RCoT

ABCDEFGH

8 of 8 found, 0 extra

CMIknn

ABCDEFGH

8 of 8 found, 0 extra

GPDC

ABCDEFGH

7 of 8 found, 0 extra

The example's true graph, and the graph PC finds on its 500 rows with each test.

Partial correlation finds 3 of the 8 edges and adds 4 false edges. KCI, RCoT, and CMIknn find all 8, and GPDC finds 7. None of the nonlinear tests adds a false edge.

Four tests#

Each test asks whether x and y are independent given a set of variables z. They differ in how they measure dependence and how much computation they need.

indep_test

Test

How it decides

Cost

"kci"

Kernel conditional independence (Zhang et al., 2011)

Compares x and y in a Gaussian-kernel feature space after removing z

Grows with the square of the rows or faster; rank=k caps each kernel at k columns

"rcot"

Randomized conditional correlation (Strobl, Zhang, and Visweswaran, 2019)

Approximates the kernel test with quasi-Monte Carlo random Fourier features, sampled for each conditioning set

Linear in the rows; warns below 500 rows

"cmiknn"

Nearest-neighbor conditional mutual information (Runge, 2018)

Estimates conditional mutual information and builds its null by shuffling x among neighbors in z

500 shuffles per test by default

"gpdc"

Gaussian-process distance correlation (Runge et al., 2019)

Regresses x and y on z with Gaussian processes, then tests the residuals with distance correlation

Grows with the cube of the rows per regression

Your choice depends on the size of your data:

  • RCoT takes time linear in the number of rows. Every fit we ran finished, up to 50 variables and 5,000 rows. It warns below 500 rows.

  • KCI reached 20 variables at 2,000 rows in our runs. For more rows, KCI(rank=...) caps its cost, and a GPU runs it faster.

  • CMIknn is the slowest of the four: 10 variables at 500 rows takes minutes.

  • GPDC reached 20 variables at 1,000 rows in our runs. Its cost grows with the cube of the rows.

How fast#

We compared PC and FCI with each test against the package that implements it: causal-learn for KCI and RCoT, pcalg with RCIT for RCoT, and tigramite for CMIknn and GPDC. We ran each on additive data and on nonmonotone data generated with cos, using 20 datasets per size, and timed 5 of them.

Each test against its reference package

Faster by
PC and FCIKCIvs causal-learn2.7-5.6x
RCoTvs causal-learn5.9-36x
RCoTvs pcalg9.5-29x
CMIknnvs tigramite2.3-10x
GPDCvs tigramite1.3-1.9x
The range over sizes of the reference's median fit time over Andrey's.

Each test runs at the same level of accuracy as its reference package. The release card gives the errors at every size. On nonmonotone data, partial correlation makes more errors than the empty graph from 10 variables onward, while every nonlinear test makes fewer errors than the empty graph.

KCI and CMIknn also run on a CUDA GPU (ANDREY_BACKEND=cuda) and return the same graph as on the CPU; the 0.8.0 release card lists the speedups and the hardware.

Limits#

  • Measured sizes. PC up to 20 variables at 2,000 rows with KCI, 50 variables at 5,000 rows with RCoT, 20 variables at 500 rows with CMIknn, and 20 variables at 1,000 rows with GPDC. FCI with KCI and RCoT at 5 and 10 variables. The release card lists every size and the hardware.

  • Cost. KCI and GPDC costs grow quickly with the number of rows; KCI(rank=...) caps KCI’s cost. CMIknn grows with the number of variables and rows.

0.8.0 also brings background knowledge for every search, score defaults that follow the data, and faster categorical tests. The 0.8.0 release card and the changelog give the details.

Try it#

pip install -U andrey-core

Help us build it#

Andrey is in alpha. The API may change between releases. When you try it on your own data, tell us what breaks or which method you need. We also welcome pull requests. The contributing guide explains how you can set up the development environment.

Acceleration