Hierarchical Topological Ordering with Conditional Independence Test for
  Limited Time Series
Anpeng Wu Haoxuan Li Kun Kuang Keli Zhang Fei Wu
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.