---
name: 20261023-andrey-0-8-0
description: "In Andrey 0.8.0, PC, FCI, GFCI, and CD-NOD test independence with KCI, RCoT, CMIknn,
  and GPDC to detect nonlinear effects that partial correlation misses."
meta:
  type: post
blogpost: true
date: 2026-10-23
author: Shu Wan
tags: [Release, Nonlinear data, Constraint-based]
version: 0.8.0
cover: harmonograph
---

# Nonlinear dependence

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.

```{raw} html
:file: 0.8.0/dependence.html
```

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.

```{literalinclude} 0.8.0/example.py
:language: python
:caption: example.py
```

```{literalinclude} 0.8.0/example-output.txt
:language: text
:caption: example.py
```

```{raw} html
:file: 0.8.0/graphs.html
```

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](https://arxiv.org/abs/1202.3775)) | 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](https://arxiv.org/abs/1702.03877)) | 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](https://proceedings.mlr.press/v84/runge18a.html)) | 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](https://doi.org/10.1126/sciadv.aau4996)) | 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.

```{raw} html
:file: 0.8.0/comparison.html
```

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](../docs/benchmarks/0.8.0.md) 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](../docs/benchmarks/0.8.0.md) and the
[changelog](../docs/changelog.md) give the details.

## Try it

```{code-block} shell
:class: window

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](https://github.com/Abel-ai-lab/andrey/issues/new) or which method you need.
We also welcome pull requests. The
[contributing guide](https://github.com/Abel-ai-lab/andrey/blob/main/CONTRIBUTING.md) explains how
you can set up the development environment.

---

- [Getting started](../docs/guides/getting-started.md)
- [Examples](../docs/examples/index.md)
- [Release cards](../docs/benchmarks.md)
- [Changelog](../docs/changelog.md)
- [GitHub](https://github.com/Abel-ai-lab/andrey)