Survey and Evaluation of Causal Discovery Methods for Time Series (Extended Abstract)

1 Introduction

Causality plays a central role in science and has been the subject of many debates among philosophers, biologists, mathematicians and physicists, to name but a few. Causality is implicit in the logic and structure of ordinary language and is embedded in our understanding mechanism that pushes humans to invoke questions. Why is it dark? Why is the sea salty? What is the effect of exercise on heart rate, of a vaccine on a particular disease? What is the effect of industrial pollution on the environment? And so, as already advocated by Spirtes, Glymour and Scheines, in attempting to answer such questions, both the baby and the scientist try to turn observations into causal knowledge [Spirtes et al., 2001]. Causality is indeed crucial for explanatory purposes since an effect can be explained by its causes, regardless of the correlations it may have with other variables.

∗The full paper is published in Journal of Artificial Intelligence Research, 73:767-820, August 2022.

The recent decades have seen the development, from philosophers, mathematicians, and computer scientists, of different models and methods to infer causal relations from data and to reason on the basis of these relations (to, e.g., predict the effect of changing a particular medication). If the first studies were dedicated to non temporal data, more and more studies now focus on time series. Indeed, time series arise as soon as observations, from sensors or experiments, for example, are collected over time. They are present in various forms in many different domains, as healthcare (through, e.g., monitoring systems), Industry 4.0 (through, e.g., predictive maintenance and industrial monitoring systems), surveillance systems (from images, acoustic signals, seismic waves, etc.) or energy management (through, e.g. energy consumption data). The number of scientific publications dedicated to causality in time series as well as the number of tools developed in this context have steadily increased to a point that it is difficult for non specialists to grasp the most important approaches proposed so far.

The goal of our survey is twofold: On the one hand, we want to introduce the major concepts, models, methods, and associated algorithms proposed so far to infer causal relations from observational time series, a task usually referred to as causal discovery; on the other hand, we want to assess how different methods for causal discovery in time series behave in practice. Several surveys on causal discovery have recently been proposed [Guo et al., 2020; Nogueira et al., 2021; Glymour et al., 2019; Vowels et al., 2021]. However, most of them do not discuss time series and when they do, they focus on Granger causality. In contrast, our survey is dedicated to causal discovery in time series and reviews all families of approaches proposed in this area.

The remainder of this extended abstract is organized as follows. After a brief description of the main concepts and assumptions in Section 2, we briefly present some of the different algorithms that we presented in our survey according to the family of approaches they belong to and summarize the main characteristics of these algorithms. Section 4 points out some aspect of causal discovery from time series that are not included in the survey. Lastly, Section 5 concludes this extended abstract.

2 Background

Causal discovery in time series aims at discovering, from observational data, causal relations within and between dvariate time series X where, for a fixed t, each Xt is a vector (X 1 t , · · · ,X d t ) in which each variable X p t represents a measurement of the p-th time series at time t. There are at least three ways to represent time series through a causal graph G = (V, E) with V the set of vertices and E the set of edges. The first is called a full time causal graph and represents a complete acyclic graph of the dynamic system, as illustrated in Figure 1a.

Definition 1 (Full Time Causal Graph). Let X be a multivariate discrete-time stochastic process and G = (V,E) the associated full time causal graph. The set of vertices in that graph consists of the set of components X 1 , . . . ,X d at each time t. The edges E of the graph are defined as follows: variables X p t-i and X q t are connected by a lag-specific directed link X p t-i → X q t in G pointing forward in time if and only if X p causes X q at time t with a time lag of i > 0 for p = q and with a time lag of i ≥ 0 for p ̸= q.

It is usually not possible to infer general full time causal graphs as there usually is a single observation for each time series at each time instant and it is common to rely on the so-called Consistency Throughout Time assumption.

Definition 2 (Consistency Throughout Time). A causal graph G = (V, E) for a multivariate time series X is said to be consistent throughout time if all the causal relationships remain constant in direction throughout time.

When assuming consistency throughout time, the full time causal graph can be contracted to give a finite graph which we call window causal graph. It is a representation of the causal graph through a time window, the size of which equals the maximum lag relating time series in the full time causal graph.

Definition 3 (Window Causal Graph). Let X be a multivariate discrete-time stochastic process and G = (V,E) the associated window causal graph for a window of size τ. The set of vertices in that graph consists of the set of components X 1 , . . . ,X d at each time t, . . . , t + τ. The edges E of the graph are defined as follows: variables X p t-i and X q t are connected by a lag-specific directed link X p t-i → X q t in G pointing forward in time if and only if X p causes X q at time t with a time lag of 0 ≤ i ≤ τ for p ̸= q and with a time lag of 0 < i ≤ τ for p = q.

Figure 1b illustrates a window causal graph corresponding to the full time causal graph given in Figure 1a. In practice, it is often sufficient to know the causal relations between time series as a whole, without knowing precisely the relations between time instants, in addition, in some applications, an expert would like to validate a causal graph before using it, but validating a window causal graph can be difficult as it is difficult to determine the temporal lag between a cause and an effect. In these cases, one one can use a summary causal graph. An example of such a graph is given in Figure 1c. Note that since a summary causal graph is a abstraction of the full time causal graph, it can contain cycles.

Definition 4 (Summary Causal Graph). Let X be a multivariate discrete-time stochastic process and G = (V,E) the associated summary causal graph. The set of vertices in that graph consists of the set of time series X 1 , . . . , X d . The edges E of the graph are defined as follows: variables X p and X q are connected if and only if there exists some time t and some time lag i such that X p t-i causes X q t at time t with a time lag of 0 ≤ i for p ̸= q and with a time lag of 0 < i for p = q.

The relations between a probability distribution and its causal graph are central to the construction of the graph. It is however not always possible to infer a causal graph solely from observational data on which one can only compute correlations and statistical independencies. For this reason, in addition to the acyclicity of the full time causal graph and consistency throughout time, all methods rely on at least two of the following assumptions:

• Stationarity, which states that the generative process does not change with respect to time;
• Causal Markov condition [Spirtes et al., 2001; Pearl, 2000], which states that every variable is independent of all its nondescendants in the graph conditional on its parents;
• Causal sufficiency [Spirtes et al., 2001; Pearl, 2000], which states that all common causes, i.e., confounders, of all observed variables are observed;

• Minimality [Spirtes et al., 2001], which requires that all adjacent nodes are dependent;
• Faithfulness [Spirtes et al., 2001; Pearl, 2000], which states that all conditional independencies are entailed from the causal Markov condition;
• Semi-parametric models [Peters et al., 2017], which stipulates a general form for the underlying model, as linear models or nonlinear additive noise models;
• Temporal priority [Hume, 1738], which makes the process of causality asymmetric in time and is useful for orienting a causal relation when one knows that two variables are causally related, as well as its relaxed version which allows for instantaneous relations as the difference in time between two values of two time series may not be observed if the sampling frequencies of the time series are small.

3 Diffferent Families of Approaches for Causal Discovery

We now turn to the most widely used approaches used to infer causal graphs between time series. Additional approaches can be found in the complete survey.

Granger causality is one of the oldest concepts in causal inference, based on a statistical version of Hume's regularity theory [Hume, 1738] which states that causal relations can be inferred by the experience of constant conjunctions between causes and effects, a cause preceding its effects. Assuming stationary linear systems, one can assess whether X p Granger-causes X q by considering two autoregression models: an autoregressive restricted model that uses only past values of X q to predict its current value and an augmented version of the autoregressive model that uses both past values of X q and X p to predict the current value of X q . If the augmented version is significantly more accurate than the restricted model, one can conclude that X p Granger-causes X q . In a multivariate setting, a pairwise analysis can be performed using the bivariate approach denoted as PWGC. This approach does however not fully capture Granger's original ideas which assume that all relevant information is included in the analysis [Eichler, 2008]. To include all relevant information in the analysis, the multivariate Granger causality denoted as MVGC [Geweke, 1982; Chen et al., 2004; Barrett et al., 2010] was introduced. InMVGC, the restricted and augmented models are both based on a vector autoregressive instead of a simple autoregressive model, where the augmented model uses all observational time series whereas the restricted model uses all time series except X p . Analogously to the bivariate case, if the augmented model is significantly more accurate than the restricted model, one concludes that X p Granger-causes X q . Note that several extensions of the above approach have been proposed, as the temporal causal discovery model, denoted as TCDF [Nauta et al., 2019], which dispenses with the linear assumption made in the original proposal.

Constraint-based approaches exploit conditional independencies to build a skeleton between variables. This skeleton is then oriented either according to temporal priority or according to a set of rules that define constraints on admissible orientations while assuming faithfulness. oCSE [Sun et al., 2015] algorithm uses the causation entropy to find these conditional independencies under the assumption that all causal relations have a time-lag of size 1. Due to this assumption, temporal priority is sufficient to orient all edges and the summuary causal graph gives the same information as the window causal graph. However, time-lag of size 1 is not always satisfied in real world scenarios, so the PCMCI algorithm [Runge et al., 2019] was introduced to detect time lagged causal relations in the form of a window causal graph. Note that PCMCI can be flexibly combined with any kind of conditional independence tests. Instantaneous causal relations, which were not supported in the initial algorithm, have been integrated to PCMCI [Runge, 2020] by conducting separately the edge removal for lagged conditioning sets and instantaneous conditioning sets. Lagged relations are treated as in PCMCI and instantaneous relations are oriented using the known PC-rules [Spirtes et al., 2001] which were introduced for non temporal graphs. Both of the above algorithms assume causal sufficiency, however, there exists constraintbased algorithms, such as tsFCI [Entner and Hoyer, 2010], that do not need this assumption.

Noise-based approaches do not consider that statistical noise is as a nuisance that one has to live with. Instead, they consider it as a valuable source of insight to identify causal relations [Hoyer et al., 2009; Climenhaga et al., 2019]. Even though it has been shown that, in a non parametric setting, the noise does not help to distinguish between a cause and its effects [Peters et al., 2017], this is no longer the case when using specific semi-parametric models as a a linear model with non-Gaussian noise [Shimizu et al., 2006], or a nonlinear additive noise model [Hoyer et al., 2009]. Therefore, the VarLiNGAM [Hyv¨arinen et al., 2010] algorithm was proposed for uniquely identifying causal structures based on purely observational time series assuming a linear model with nonGaussian noise. Similarly, TiMINo [Peters et al., 2013] was introduced for nonlinear additive noise models. Both algorithms assume causal sufficiency and the minimality condition, which is a weaker version of faithfulness.

Score-based approaches aim to find the graph that best matches the data based on a score that typically strikes a balance between the likelihood of the data given the network and a penalty term related to the complexity of the network. Assuming causal sufficiency as well as linearity, the DYNOTEARS [Pamfil et al., 2020] algorithm was proposed to simultaneously estimate instantaneous and time-lagged relationships between time series. This algorithm relies on minimizing a penalized loss based on the Frobenius norm of the residuals of a linear model.

Summary Table 1 displays the main characteristics of representative algorithms in the above families. As one can note, 4 algorithms infer a summary causal graph and 5 infer a window causal graph. It is of course possible to deduce the summary causal graph from a window causal graph and, in the case of oCSE, the summary causal graph is equivalent to the window causal graph. Roughly only half of the algorithms address the problem of discovering instantaneous relations. Most algorithms can detect confounders. However, only TCDF can detect instantaneous hidden confounders and only tsFCI can detect lagged hidden confounders. More generally, very few algorithms can deal with hidden variables, which violates the causal sufficiency assumption. Regarding the type of underlying models, almost all algorithms rely on a particular model (except PCMCI and oCSE). Among the algorithms relying on a model, roughly half of them rely on a linear model. Relying on a specific model can be an advantage when the data considered arises from a similar model. It can be of course a disadvantage when this is not the case and when the model family considered is not a universal approximator. Lastly, as one can note, most algorithms have few (less than 5) hyper-parameters, with the exception of TCDF which is based on deep neural networks.

4 Elaboration

Our survey reviews different causal discovery algorithms in the setting where consistency throughout time as well as other technical conditions are satisfied. However, it is important to note that there exists algorithms that relax these conditions: [Huang et al., 2015; Huang et al., 2020; Saggioro et al., 2020] relax the consistency throughout time constraint, [Danks and Plis, 2013; Gong et al., 2015] allow for temporal aggregation or subsampling, and [Kleinberg and Mishra, 2009; Kleinberg, 2011; Kleinberg, 2015] consider qualitative and mixed data. In addition, in each family of approaches, we presented what we think are the most known algorithms but one should bear in mind that there exists many extensions of these algorithms. For example, in the constraint-based family, the idea behind the oCSE algorithm was extended to handle lags of size different from 1, instantaneous relations as well as a method to directly infer the summary causal graph without going through a window causal graph [Assaad et al., 2022a; Assaad et al., 2022b]. In the noise based-family, identifiability was shown to be also possible under a post nonlinear additive noise model [Zhang and Hyv¨arinen, 2009]. Finally, it is worth noting that we did not include hybrid methods [Malinsky and Spirtes, 2018; Sanchez-Romero et al., 2019; Assaad et al., 2021] which sometimes yield better results than purebred methods.

5 Conclusion

Our survey presents different algorithms, pertaining to different families of approaches, for causal discovery in time series. The families we have retained here correspond to approaches `a la Granger, constraint-based approaches, noisebased approaches and score-based approaches. Further details on those algorithms and their evaluation, as well as on other families of approaches (namely, logic-based approaches, topology-based approaches, and difference-based approaches) and associated algorithms can be found in the full paper [Assaad et al., 2022c]. In a nutshell, one can draw from our survey that causal discovery in times series is an active research field in which new methods (in every family of approaches) are regularly proposed, and that no family or algorithm stands out in all situations. Indeed, they all rely on assumptions that may or may not be appropriate for a particular dataset.