Hierarchical Topological Ordering with Conditional Independence Test for Limited Time Series
This work addresses a bottleneck in causal discovery for researchers, offering an incremental improvement to topology-based methods by incorporating limited time series data.
The paper tackles the problem of learning directed acyclic graphs (DAGs) from observational data by proposing a hierarchical topological ordering algorithm with conditional independence test (HT-CIT) that reduces spurious edges, resulting in more efficient and sparse DAG learning with a smaller search space.
Learning directed acyclic graphs (DAGs) to identify causal relations underlying observational data is crucial but also poses significant challenges. Recently, topology-based methods have emerged as a two-step approach to discovering DAGs by first learning the topological ordering of variables and then eliminating redundant edges, while ensuring that the graph remains acyclic. However, one limitation is that these methods would generate numerous spurious edges that require subsequent pruning. To overcome this limitation, in this paper, we propose an improvement to topology-based methods by introducing limited time series data, consisting of only two cross-sectional records that need not be adjacent in time and are subject to flexible timing. By incorporating conditional instrumental variables as exogenous interventions, we aim to identify descendant nodes for each variable. Following this line, we propose a hierarchical topological ordering algorithm with conditional independence test (HT-CIT), which enables the efficient learning of sparse DAGs with a smaller search space compared to other popular approaches. The HT-CIT algorithm greatly reduces the number of edges that need to be pruned. Empirical results from synthetic and real-world datasets demonstrate the superiority of the proposed HT-CIT algorithm.