eCDANs: Efficient Temporal Causal Discovery from Autocorrelated and Non-stationary Data (Student Abstract)

Muhammad Hasan Ferdous, Uzma Hasan, Md. Osman GaniAAAI 2023 · DOI

Introduction

Causal Discovery (CD) is a fundamental task in data science, aimed at uncovering the underlying mechanisms that drive observed phenomena. In the context of time-series data, this involves identifying how variables influence each other over time. However, real-world time-series data often present two significant challenges: autocorrelation and non-stationarity. Autocorrelation occurs when a variable's current state is influenced by its own past, potentially masking true causal links. Non-stationarity refers to causal relationships that change over time due to external environmental shifts.

Problem Statement

Existing causal discovery algorithms often struggle with high-dimensional time-series data. As the number of variables and time lags increases, the computational complexity grows exponentially, often leading to a loss of statistical power or prohibitive runtimes. Furthermore, many methods fail to adequately account for the dynamic nature of non-stationary systems, leading to "ghost" relationships or missed detections. The eCDANs (Efficient Temporal Causal Discovery from Autocorrelated and Non-stationary Data) algorithm is designed to address these limitations by providing a robust and efficient framework for temporal causal discovery.

Methodology

The eCDANs approach utilizes a structured five-step pipeline to ensure both accuracy and efficiency:

  1. Initial Adjacency Detection: The algorithm begins by identifying potential lagged relationships using iterative "PC-stable" tests. It employs Momentary Conditional Independence (MCI) tests to prune the graph, keeping conditioning sets small to maintain computational efficiency.
  2. Skeleton Construction: A preliminary undirected graph is built, incorporating both lagged and contemporaneous (same-time) connections.
  3. Detecting Changing Modules: To handle non-stationarity, eCDANs introduces a surrogate variable ($C$) that acts as a proxy for time. By testing variables against $C$, the algorithm can pinpoint which causal mechanisms are shifting over time without requiring complex continuous optimization.
  4. Contemporaneous Refinement: The algorithm performs targeted independence tests to eliminate false positive edges between variables occurring at the same timestamp.
  5. Causal Direction Recovery: Finally, edges are oriented based on temporal flow and specific causal rules, ensuring that causes precede their effects.

Experimental Evaluation

The authors evaluated eCDANs using both synthetic and real-world datasets. Synthetic data with varying numbers of variables (4, 6, 8, and 10) allowed for precise measurement against a known ground truth. Additionally, a clinical dataset involving 12 time-series variables from ICU patients was used to demonstrate real-world applicability.

Key Results

The performance of eCDANs was benchmarked against three state-of-the-art methods: PCMCI+, Extended CD-NOD, and DYNOTEARS.

Performance comparison of eCDANs against state-of-the-art methods across TPR, FDR, SHD, and Runtime.

As shown in the results, eCDANs consistently demonstrates superior performance:

  • Accuracy: eCDANs outperformed PCMCI+ and CD-NOD across True Positive Rate (TPR), False Discovery Rate (FDR), and Structural Hamming Distance (SHD).
  • Reliability: While DYNOTEARS often achieved a high TPR, it suffered from excessively high FDR, indicating a tendency to over-predict causal links. eCDANs maintained a much better balance between precision and recall.
  • Efficiency: In terms of runtime, eCDANs was generally the fastest method, particularly as the number of variables increased, proving its scalability for modern datasets.

Conclusion and Future Work

eCDANs represents a significant step forward in temporal causal discovery, offering a balanced solution that handles both autocorrelation and non-stationarity efficiently. By leveraging surrogate variables and optimized independence tests, it achieves high accuracy without the computational burden of traditional methods.

Future research directions include the simultaneous detection of lagged and contemporaneous adjacencies to further streamline the pipeline. Additionally, the authors plan to extend eCDANs to handle latent confounders—unobserved variables that influence the system—by incorporating Partial Ancestral Graphs (PAGs) into the framework.

Summary updated

BibTeX
@inproceedings{ferdous2023ecdans,
  author = {Muhammad Hasan Ferdous and Uzma Hasan and Md. Osman Gani},
  title = {{eCDANs: Efficient Temporal Causal Discovery from Autocorrelated and Non-stationary Data (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i13.26964},
}
Figure