  In this paper we propose and study a class of simple, nonparametric, yet
interpretable measures of conditional dependence between two random variables
$Y$ and $Z$ given a third variable $X$, all taking values in general
topological spaces. The population version of any of these measures captures
the strength of conditional dependence and it is 0 if and only if $Y$ and $Z$
are conditionally independent given $X$, and 1 if and only if $Y$ is a
measurable function of $Z$ and $X$. Thus, our measure -- which we call kernel
partial correlation (KPC) coefficient -- can be thought of as a nonparametric
generalization of the partial correlation coefficient that possesses the above
properties when $(X,Y,Z)$ is jointly normal. We describe two consistent methods
of estimating KPC. Our first method utilizes the general framework of geometric
graphs, including $K$-nearest neighbor graphs and minimum spanning trees. A
sub-class of these estimators can be computed in near linear time and converges
at a rate that automatically adapts to the intrinsic dimension(s) of the
underlying distribution(s). Our second strategy involves direct estimation of
conditional mean embeddings using cross-covariance operators in the reproducing
kernel Hilbert spaces. Using these empirical measures we develop forward
stepwise (high-dimensional) nonlinear variable selection algorithms. We show
that our algorithm, using the graph-based estimator, yields a provably
consistent model-free variable selection procedure, even in the
high-dimensional regime when the number of covariates grows exponentially with
the sample size, under suitable sparsity assumptions. Extensive simulation and
real-data examples illustrate the superior performance of our methods compared
to existing procedures. The recent conditional dependence measure proposed by
Azadkia and Chatterjee (2019) can be viewed as a special case of our general
framework.
