Causal Layering via Conditional Entropy
Itai Feigenbaum Devansh Arpit Huan Wang Shelby Heinecke Juan Carlos Niebles Weiran Yao Caiming Xiong Silvio Savarese
Causal discovery aims to recover information about an unobserved causal graph
from the observable data it generates. Layerings are orderings of the variables
which place causes before effects. In this paper, we provide ways to recover
layerings of a graph by accessing the data via a conditional entropy oracle,
when distributions are discrete. Our algorithms work by repeatedly removing
sources or sinks from the graph. Under appropriate assumptions and
conditioning, we can separate the sources or sinks from the remainder of the
nodes by comparing their conditional entropy to the unconditional entropy of
their noise. Our algorithms are provably correct and run in worst-case
quadratic time. The main assumptions are faithfulness and injective noise, and
either known noise entropies or weakly monotonically increasing noise entropies
along directed paths. In addition, we require one of either a very mild
extension of faithfulness, or strictly monotonically increasing noise
entropies, or expanding noise injectivity to include an additional single
argument in the structural functions.