Reframed GES with a Neural Conditional Dependence Measure
In a nonparametric setting, the causal structure is often identifiable only
up to Markov equivalence, and for the purpose of causal inference, it is useful
to learn a graphical representation of the Markov equivalence class (MEC). In
this paper, we revisit the Greedy Equivalence Search (GES) algorithm, which is
widely cited as a score-based algorithm for learning the MEC of the underlying
causal structure. We observe that in order to make the GES algorithm consistent
in a nonparametric setting, it is not necessary to design a scoring metric that
evaluates graphs. Instead, it suffices to plug in a consistent estimator of a
measure of conditional dependence to guide the search. We therefore present a
reframing of the GES algorithm, which is more flexible than the standard
score-based version and readily lends itself to the nonparametric setting with
a general measure of conditional dependence. In addition, we propose a neural
conditional dependence (NCD) measure, which utilizes the expressive power of
deep neural networks to characterize conditional independence in a
nonparametric manner. We establish the optimality of the reframed GES algorithm
under standard assumptions and the consistency of using our NCD estimator to
decide conditional independence. Together these results justify the proposed
approach. Experimental results demonstrate the effectiveness of our method in
causal discovery, as well as the advantages of using our NCD measure over
kernel-based measures.