Causal Layering via Conditional Entropy

One important task in causal discovery is the recovery of a topological ordering of the underlying graph, which in the context of causality is an ordering of the nodes which places causes before effects. Other than the importance of such ordering in its own right, it is also highly useful for discovering the full graph [Teyssier and Koller, 2005]. A topological ordering which doesn't unnecessarily break all ties is called a layering [Tamassia, 2013]. Given a graph, repeated removal of sources or sinks yields a layering: we denote these algorithms as repeated-SOUrceRemoval (SOUR) and repeatedSInkRemoval (SIR), both are simple and probably known variants of Kahn's Algorithm [Kahn, 1962]. Of course, in causal discovery, we are not given the graph, so implementing SOUR/SIR is not straightforward. In this paper, we propose a new method for causal discovery of layerings of discrete random variables, which implements SOUR/SIR without direct access to the graph, but with access to a conditional entropy oracle for the data instead. We show that, under some assumptions, we can separate sources from non-sources and sinks from non-sinks by comparing their conditional entropy (with appropriate conditioning) to their unconditional noise entropy. Specifically, when repeatedly removing sources and conditioning on all removed variables, we show that the conditional entropy of new sources equals the conditional entropy of their noise, while the conditional entropy of non-sources is larger than the entropy of their noise.