Causal Discovery from Time Series with Hybrids of Constraint-Based and Noise-Based Algorithms
Authors: Daria Bystrova
Charles K. Assaad
Julyan Arbel
Emilie Devijver
Eric Gaussier
Wilfried Thuiller
Venue: Accepted by TMLR ()

Abstract: Constraint-based methods and noise-based methods are two distinct families of methods proposed for uncovering causal graphs from observational data. However, both operate under strong assumptions that may be challenging to validate or could be violated in real-world scenarios. In response to these challenges, there is a growing interest in hybrid methods that amalgamate principles from both methods, showing robustness to assumption violations. This paper introduces a novel comprehensive framework for hybridizing constraint-based and noise-based methods designed to uncover causal graphs from observational time series. The framework is structured into two classes. The first class employs a noise-based strategy to identify a super graph, containing the true graph, followed by a constraint-based strategy to eliminate unnecessary edges. In the second class, a constraint-based strategy is applied to identify a skeleton, which is then oriented using a noise-based strategy. The paper provides theoretical guarantees for each class under the condition that all assumptions are satisfied, and it outlines some properties when assumptions are violated. To validate the efficacy of the framework, two algorithms from each class are experimentally tested on simulated data, realistic ecological data, and real datasets sourced from diverse applications. Notably, two novel datasets related to Information Technology monitoring are introduced within the set of considered real datasets. The experimental results underscore the robustness and effectiveness of the hybrid approaches across a broad spectrum of datasets.

Published in Transactions on Machine Learning Research (05/2024)
Causal Discovery from Time Series with Hybrids of constriitt-Based and Noise-Based Algorithms
Daria Bystrova"
Unio. Grenoble Alpes, CNRS, Inria, Grenoble INP, LECA, LJK, LIG, F38000, Grenoble, France
charles.assuad @insemm. Sorbonne Université, INSERM, Institut Pierre Louis d' d'Epidémiologie et de Santé Publique, F75012, Paris, France EasyVistar Vista, F38000, Grenoble, France
Charles K. Assaad
Julyan Arbel
Unio. Grenoble Alpes, CNRS, Inria, CNRS, Grenoble INP, LJK, F38000, Grenoble, France
Emilic Devijver
Eric Gaussier
Univ Grenoble Alpes, CNRS, Grenoble INP, LIG, F38000, Grenoble, France
Wilfried Thuiller
Univ. Grenoble Alpes, Univ. Savoie Mont Blane, CNRS, LECA, F38000, Grenoble, Prance
Reviewed on OpenReview: https: openreview. net/ forun? id= PGLbZpVk22
Abstract
Constraint-based methods and noise-based methods are two distinct families of methods pro- posed for uncovering causal graphs from observational data. However, both operate under strong assumptions that may be challenging to validate could be violated real-world sco- narios. In response to these challenges, there growing interest in hybrid methods that amalgamate principles from both methods, showing robustness to assumption violations. This paper introduces novel comprehensive framework for hybridizing constraint-base and voise-based methods designed to uncover causal graphs from observational time series. The framework is structured into two classes. The first class employs a noise-based strategy to identify super graph, containing the true graph, followed by a constraint- based strategy to eliminate unnecessary edges. In the second class, a constraint-based strategy applied to identify a skeleton, which is then oriented using a noise-based strategy. The paper provides theoretical guarantees for each class under the condition that all assumptions are satisfied, and it outlines some properties when assumptions of the framework, two algorithms from each class are experimentally lested on simulated data, realistic ecological data, and real datasets sourced from diverse applications. Notably, two novel datasets related to Information Technology monitoring are introduced within the set of considered real datasets. The experimental results underscore the robustness and effectiveness of the hybrid approaches across a broad spectrum of datasets.
violated. To validate the efficacy
1 Introduction
Recent technological advances allow collecting observational time series on complex dynamical systems in various fields, such as biodiversity monitoring in ecology (Dornelas et al., 2018), epidemiology (Meci et al., 2022, Arlegui et al., 2023, Bales et al., 2023, Morean et al., 2023), healtheare (Morid et al., 2023) and Information Technology (IT) monitoring systems (Tamburri et al., 2020, Assaad et al., 2023). One of the
*These authors contributed equally this work.

---

Published in Transactions on Machine Learning Research (05/2024)
key objectives in studying such dynamical systems is to understand the causal relationships between the system's 's components. To find these causal relations, experts can employ causal discovery methods for time series, which aim to build a causal graph from observational data. These methods can be categorized into several familics, including Granger- (Granger, 1969), constraint- 2020, Assaad et al., 2022c), score-based (Chickering, 2002b), contimuous pptimization-benn 2018) and noise-based families (Hyvärinen et al., 2008, Peters et al., 2013) -for more details see Assaad et al. (2022a), Hasan et al. (2023), Gong et al. (2023). Each family has its own set of assumptions, which may may not be suitable for specific dataset. Therefore, single method stands out in all situations (Assaad et al., 2022a).
(Spirtes et al., 2000, Runge,
(Zheng et al.,
Hybrid frameworks combine several methods from different families to enhance graph inference (Hasan et al., 2023). For non-temporal data, several authors propose to combine ideas from constraint based and score-based methods to improve scalability (Tsamardinos et al., 2006) or robustness to small sample size (Ogarrio et al., 2016). For temporal data, SVAR-GFCI, proposed by Malinsky & Spirtes (2018), is a time- series generalization of the hybrid method GFCI which is based on the score-based and constraint-based algorithms.
Another type of hybrid framework, which is our main focus in this work, is based on the combination of constraint-based and noise-based families. The advantage of constraint-based methods is that they are pur-parmmttric (i.e., no assumption is made on the form of the underlying causal relationships), while the limitation is that they require strong non-testable assumptions and can only recover the causal graph up to its Markov equivalence class, i... orientation of some edges could be unknown in the inferred graph as several graphs represent the same conditional dependence structure. On the other hand, noise-based methods are capable of recovering true graphs. So, by combining methods from both families, although we require assumptions of both families of methods, some assumptions can be weakened and we can recover the true causal graph. There exist several methods of this type for non-temporal data, such as PClingam (Hoyer et al., 2008) or FRITL (Chen et al., 2021). Assnad et al. (2021) introduced NBCBacyclic for temporal data assuming that there are no cyelic causal relations between different time series.
This paper presents a hybrid framework for temporal data using noise- based and constraint-basee algorithms. In this framework, we consider two different classes of methods, which we denote NBCB and CBNB. Both classes can infer different lypes of causal graphs that differentiate wet instantaneous relations and lagged relations. To construct these types of causal graphs, NBCB and CBNB orient edges using a noise-based strategy and prune edges using a constraint-based strategy. The main difference between NBCB and CBNB is that the former starts by orienting the graph and then proceeds to pruning, while the latter starts by pruning and then proceeds to orientation. Most, importantly, NBCB and CBNB combine the parts from corresponding methods in an efficient way, such that information in the first part improves the efficiency of the second part. At the core of CBNB lies the notion of an undirected cycle group, which we introduce to optimize the search for orientation. The advantage of the proposed hybrid framework is that, in practice, it has a tradc-off performance between the constraint-based and noise-based algorithms. In comparison to the constrained- based family, the proposed methods do not require the so-called faithfulness assumption (but require a weaker assumption named adjacency faithfulness) and can recover the true causal graph instead of restricting only to the markov equivalence class. In comparison to noise-based methods, the proposed methods provide a better pruning of odges when the sample size is small (Malinsky & Danks, 2018). In this paper; we also show the distinct responses of NBCB and CBNB when assumptions are violated. This demonstration highlights the expected results across various scenarios and aids in determining the most suitable methodological approach for given problem.
In summary, our main contributions are the following:
We propose hybrid framework for the causal discovery of time series that combines parts of noise- based and constraint-based algorithms. Within this framework, we derive two classes of algorithms, NBCB and CBNB, which we optimize to infer the causal graph from time series.
In Assaad et al. (2021), this method was called NBCB but in this work, we denote it as NBCBacydlic explicitly point out that assumes that the summary causal graph acyelic. For more details about summary causal graphs see Section
2

---

Published in Transactions on Machine Learning Research (05/2024)
x= = ===a,x-- X--1 + Oya V + Ozn 7 + St
= :===----11 + Xe1 + Oyz Y + Owz W 1-1
== ayYo-1 --1 + any 1-1 + awy Wr t-2 1-2 + &t
(1)
W. = aw (-1 + Ayw Y, + azw Ze + 5t.
U+
U2 1-11-1 + awn We + 52.
Figure 1: Running example. Left: Dynamic structural causal model (dynamic SCM). Right: Associated full-time causal graph g (FTCG).
We study theoretically to which extent each class of algorithms is robust against assumption viola- tion.
We provide extensive simulation studies and real data applications to illustrate the applicability of our approach and their enhanced capabilities against assumption violation comparod to original methods.
We introduce two novel datasets about IT monitoring within the set of considered real datasets.
The remainder of the paper is organized as follows: Section 2 describes the different types of causal graphs that can be used to represent causal relations between time series and the different assumptions related those graphs. Section discusses related work and particularly details the steps that compose noise-based and constraint-based algorithms. Section 4 introduces consists of two classes NBCB and CBNB, each of which is detailed in dedicated subsections. In Section 5, NBCB and CBNB are compared to different causal discovery algorithms on simulated, realistic, and real datasets. Finally, Sections and discuss and conclude the paper.
main contribution, the hybrid framework, which
2 Background
In this section, we first introduce some terminology, tools, and assumptions which are standard for the major part. We use upper case letters denote observed random variables, lower case letters to represent deterministic constants, blackboard bold for sets, and Greek letter & to denote noise. A directed graph is denoted as and parents and descendants of X in are respectively denoted as Pag(X) and (es, We denote (X....,Y) Y) path in graph which starts at node X and ends at node Y and we denote 2 W T--Y) Y) walk in a graph which starts at node X and ends at node Y (nodes are used for paths and edges are used for walks). The skeleton of a directed graph, is graph that consists only of undirected edges that represent the same adjacencies as in the directed graph (Hasan et al., 2023).
Causal relations in a dynamical system can be represented by dynamic structural causal model, an extension of structural causal model (SCM, Pearl, 2000) to time scrics. In such dynamic SCM, each point a time series is defined by the function of its parents and some unobserved noise. Without loss of generality, we will use the linear dynamic SCM represented in Equation (1) running example.
Such dynamic SCM can be represented graphically using full-time causal graph (FTCG, Assaad et al. (2022a)), as represented in Figure and denoted as g = (E', vt). The FTCG represents an infinite graph of the dynamical system through infinite nodes Vf, representing observational random variables, and infinite odges EF, representing causal relationships. In this paper, we only consider FTCGGs that are directed acyclic graphs (DAGs), i.e., all edges are directed and there exists no directed path in gf that starts and ends the same node.
3

---

Published in Transactions on Machine Learning Research (05/2024)
2.1 Assumptions
We assumne that there are no hidden common causes, assumption known as causal sulliciency. Assumption (Causal sufficiency, Spirtes et al., 2000). Let G (E', wt) be an FTCG. There exist no hidden common couses of any two observed nodes in the V i.e., the noise terms in the underlying dynamic SCM are jointly independent.
One of the most common assumptions is the causal Markov condition, which is assumed by most of the methods, and connects the causal graphs that correspond to the given SCM with the compatible probability distribution.
Asuumption& 2 (Causal Markov condition, Spirtes et al., 2000). Let g = (B', be an FTCG and P be a probability distribution over the nodes in yf generated by the caasal structure represented by G Every X E V is independent of (DDecgrr U Page(X)) conditional on Pag:
In general, inferring causal graphs from data is possible under additional assumptions on the data-generating process. For the constraint-based family of methods, the necessary assumption for the correspondence between the graph and the distribution is the faithfulness assumption (Spirtes et al., 2000), which states that all the conditional independence relations that are true in the probability distribution are entailed by the causal Markov condition applied to G However, we consider in this work the following weaker version of the faithfulness assumption, called adjaceney faithfulness.
A ssumption 3 (Adjacency Faithfulness, Ramsey et al., 2006). Let G = = V be an FTCG. Tf two modes X and Y in yf are adjacent in G then they are dependent conditionally on any subset of Y...
We provide an example of the violation of the adjacency faithfulness and faithfulness assumptions in Figure 2. Let us consider variables We and U, and their past ..- in the causal graph in Figure 2a. Let assume that the corresponding linear SCM is composed of two equations:
W. = aw W 55
t-1
U, au a-U1-1 + awn We+ + Et
which leads to
U,= - + (auawu + Ww W + awust + +a55t + 5H-
If the coefficients are such that a, = -aw, then the coefficient before W.-1 is 0 and thus W,- | U,-2 (the noise terms are jointly independent and independent of U--2 and Wi-1). If there exists such combination of coefficients, we say that the path (W (1, We, e U,) is canceled by the path WW-1, U--, U,) (or vice versa). The independence WL,, U2-2 is not entailed by the the causal Markov condition, so the faithfulness assumption is violated, while adjacency faithfulness is not violated as W,-1 and U, are not adjacent. Let now consider the graph with an extra edge as designed in Figure 2b. If the path by the two paths (W,-1, U,) and (W U-,, then W W.LlUU, {Ut-2, (Ur2,,W,22) and the adjacency faithfulness assumption is violated. Notice that U, | (U,-2, Markov condition, which means that the faithfulness assumption is also violated.
U2} is canceled out
W Wr-2) ) is not entailed by the the causal
Note that adjacency faithfulness is proven to be equivalent to the minimality condition (Peters et al., 2017) introduced in Spirtes et al. (2000), which states that every proper subgraph of g does not satisfy causal Markov condition.
In addition, the following assumption is required by the noise-based family to guarantee identifiability Assumption 4 (Identifiable Functional Model, Peters et al., 2011). The SCM belongs to on identifiable functional model class, as defined in Peters et al. (2011).
For example, the linear dynamic SCM in Equation (1) satisfies Assumption if the noise terms are non- Gaussian.
2.2 Causal graphs for time series
Using time series data has a particular advantage for discovering causal relationships between temporal vari- ables since we can employ temporal priority, which states that the causal relationship between two variables
4

---

Published in Transactions on Machine Learning Research (05/2024)
0.5
W
W
W.
0.9
0.9
0.9
0.9
0.9
Vt-1
U
(a) Unfaithful
(b) Adjacency Unfaithful
Figure Illustration of the violation of the laithfulness and the adjaceney faithfulness assumption. (a) violates the faithfulness assumption but satisfies the adjacency faithfulness assumption and (b) violates the adjacency faithfulness which implics that it violates the faithfulness assumption.
X²
X
7
Z
W
U
(a) WCG
(b) ECG
(c) SCG
Figure 3: Different causal graphs to represent the dynamic SCM in Equation (1): (a) window causal graph
(WCG) with maximal temporal lag equal to 2, (b) extended summary causal graph (ECG), and (c)
summary causal graph (SCG).
is oriented such that the effect cannot happen before its cause. However, despite this advantage, working with full-time causal graphs (which introduced before) is impractical due to their infinite dimension, which has led to the adoption of simpler causal graphs, assuming that causal relations between time scries hold throughout time. This is formalized in the following assumption, in which yf (V......., Vt,..,,W... where V denotes a vector of d time series.
Assumption 5 (Consistency Throughout Time). Let G = (E', vt) be a full-time causal graph. There cxists in N \ (0} such that the causal structure of the graph consisting of the nodes (We-....., V.) is the same for every L.
We call the minimum value of for which consistency throughout time holds the maximal temporal lag of the graph. For example, the maximal temporal lag of the graph of Figure 7
Under Assumption 5, the full-time causal graph is equivalent to the so-called window causal graph (Hyvärinen et al., 2008, Runge, 2020, Figure 3a).
Definition (Window Causal Graph, WCG). Let gf (B',V) be a full-time causal graph satisfying Assumplion 5 with & the maximal lemporul lag in gf. A window causal graph (WCG) g" = (E", V*) is the subgraph of gf consisting of the nodes V/ = =V,- V.) and E contains all related edges.
Unfortunately, causal discovery methods still suffer in practice of the strong assumptions they rely on which are not always satisfied. Thus, in many applications, experts have to validate those graphs before using them. However, validating WCGs is challenging: if experts can usually identify causes and related effects, they do not know, in general, the exact temporal lags between them. Morcover, in some applications, exports are not interested in understanding exact causal relations with the temporal lags between them but rather opt for an abstract representation of the causal relationships between variables. An extended summary causal graph
5

---

Published in Transactions on Machine Learning Research (05/2024)
(Assaad et al., 2022c, Figure 3b) is one type of abstraction that can differentiate between instantaneous relations and lagged relations without giving precise information about the lag.
Definition 2 (Extended Summary Causal Graph, ECG). Let G (E*% (L") be WCG with mazimal temporal lag ς and nodes (Vi-qy.... Wt). The underlying extended summary causal graph (ECG) G (E", v.) consists of the nodes V/- = (Vi-.V) and the set of directed edges E' is defined as follows: for all X1, E Vt, X + Yt, there erists a directed edge from X2 to Y, (denoted as X, 4+ Y2) if and only if the same directed edge erists in 9"; for all Xt- E VV_,YY, Yy E V1, there exists directed edge from Xt- to Ye (denoted as (.-+Y) if and only if there erists at least one temporal lag f > 0 such that there exists directed edge between Xi-e and Yt in g".
The ECG presents several interesting characteristics: similarly to the WCG, inherits the acyclicity of the FTCG; it is possible to infer it from data without passing a WCG without any additional assumption (it only needs the assumptions that are needed to infer a WCG); the ECG and the WCG are equivalent when the maximal temporal lag 7 is 1.
Another more abstract graphical representation is the summary causal graph (Arnold et al., 2007, Peters et al., 2013, Assaad et al., 2022a, Figure 3c), which provides an overview of the causal relationships between time series without any information about the temporal lag (it does not differentiate between instantaneous relations and lagged relations).
Definition 3 (Summary Causal Graph, SCG). Let = = VV) be a WCG with mazimal temporal log 7
The underlying summary causal graph (SCG) of G" is G (F),V) where Va contains one node for each time series and the set of directed edges E are defined as follows: for all X, E v2, X + Y, there erists directed edge from X to Y (denoted X + Y) if and only if there crists at least one temporal lag E 2 0 such that there erists directed edge belween X,-e and Y, in G".
Note that, unlike the FTCG, the WCG and the ECG, the SCG may contain cycles and in particular self- loops, and two edges in opposite directions, as illustrated in the rumning example in Figure 3. Unlike the ECG, it is not possible to infer the SCG directly from data without additional assumptions. For example, NBCBasyclie (Assaad et al., 2021) can discover the summary causal graph assuming it is acyclic, which limits the range of potential WCGs and ECGs.
In this paper, we focus on methods that infer the WCG or the ECG from observational data.
We use throughout for clarity the notation 9- (V*, to refer to either ge (EE, Vo) or G" (E", V"). Moreover, we use the notation l* wildcard that represents time step t i, where i E {0..... .0......)) 7 in the context of WCG, and that represents either t- or t in the context of ECG.
Another important notion that we will use in this paper is the notion of a cansal order (Peters et al., 2017) which we define, in the following, only for instantaneous nodes.
Definition 4 (Causal Order of Instantaneous Nodes). Given a causal graph G*, we call a bijective mapping a Ve + {l....,dh d}, a causal order of instantaneous nodes if it sotisfies
T (X.) < (Ya)
if Yr E Descg- (Xx), Y.V.
Because of the acyelicity assumption of the WCG (resp. ECG), there is always a causal order between instantaneous nodes (and fortiori between all nodes) but it is not necessarily unique (Peters et al., 2017). For example, in Figure 3a, there exists a causal order कi such that (X,) = and क. (W.) = and there exists another causal order π2 such that (W) (Z() T2( = 2 and (U,) = T2(U)) = Note that the number of possible causal orders is not limited to two, for example, we obtain new causal order from л2, by inverting the positions of U₁ and X,.
and (x(,)) 4, while ग. (Y,) T2 = 1,
3 Related works
In this section, we start by giving a general literature review and then we give additional details on the steps that compose nosse and constraint-bbasel algorithms.
6

---

Published in Transactions on Machine Learning Research (05/2024)
3.1 Literature review
In this section, describe several methods from the main causal discovery families related to our work. More details can be found in thorough reviews such as Assaad et al. (2022a), Hasan et al. (2023), Gong et al. (2023). All those methods rely on consistency throughout time (Assumption 5) to reduce the infinite dimension of the full-time causal graph. Moreover, to consider meaningful graphs, causal sufficiency and causal Markov condition (Assumptions and 2) ) are assumed.
Gronger Causality, introduced by Granger in 1969 and improved in subsequent works (Granger, 2004, Arnold et al., 2007), stands as one of the earliest methods designed for identifying causal relationships among time scries. This approach primarily considers lincar relationships and temporal priorities, operating under the assumption that the past of a cause is both necessary and sufficient for optimally forecasting its effect. It is important to note that Granger causality, by relying on temporal priority, is limited in its ability to infer instantaneous causal relations. Furthermore, Granger causality methods typically utilize the past of one time series, up to a defined maximal temporal lag, to predict the present value of another time series without explicitly distinguishing between the importance of different lags. Consequently, these methods can be employed in constructing an ECG if we assume that there are no instantancous relations.
Constraint- based approaches (Spirtes et al., 2000) are certainly the most popular approaches for discovering causal graphs. These methods are based on conditional independence tests, do not depend on any specific distribution form, and require the faithfulness assumption. In the case of causal sufficiency ( (Assumption 1), they are usually based on the PC-algorithm (Spirtes et al., 2000), initially introduced for non-temporal data. In theory, a constraint-based algorithm can only infer a representative (known as a CPDAG, Chickering, 2002a) of the Markov equivalence class (Verma Pearl, 1990). Fast Causal Inference (FCT) algorithm can be used when Assumption 1 is not satisfied and infers a Partially Ancestral Graph (PAG), which is a representative of class of equivalent Maximal ancestral graphs (MAG) and allows representing the existence of hidden confounders in the causal graph. For time series, several algorithms infer WCGs, such PCMCI (Runge et al., 2019) and PCMCI* (Runge, 2020), extensions of the PC-algorithm, and tsFCI (Entner & Hoyer, 2010) or SVAR-FCI (Malinsky & Spirtes, 2018), extensions of the FCI almorithm. PCGCE proposed by Assaad et al. (2022c), is based on the adaptation of the PC-algorithm and infers directly an ECG.
Score-based approaches (Chickering, 2002a) search over the space of possible graphs, trying to maximize a score that reflects how well the graph fits the data. Greedy Equivalence Search (GES, Chickering, 2002a) is one of the first scoro-based methods that, under the faithfulness assumption, finds the CPDAG similarly to the PC-algorithm. There have been several recent modifications of GESS, such as the more efficient Fast Greedy Search (FGS, Ramsey, 2015) and Selective Greedy Equivalence Search (Chickering & Meek, 2015).
Continuous optimization-basel approches Unlike score-based methods, this category of algorithms avoids the combinatorial greedy search over DAGs by employing gradient-based optimization. Notears (Zheng et al., 2018) is considered as the first approach to reformulate the greedy search as continuous optimization problem within this category. This method assumes linearity and considers only DAGs whose topological order follows increasing marginal variance (rescaling data can change or reverse their inferences) (Kaiser & Sipos, 2021). Recently, new extension of Notears called Dynotears (Pamfil et al., 2020) was presented to infer a WCG from time series.
Noise-based approaches discover causal relations using footprints produced by the causal asymmetry in the data, namely the noise. They assume an identifiable functional model, as introduced in Assumption For time series, one of the most popular algorithms in this family is VarLiNGAM (Hyvärinen et al., 2008), which can discover the WCG assuming linear autoregressive models with non-Gaussian noise. TiMINo (Peters et al., 2013) discovers the SCG assuming nonlinear additive noise model. Note that TiMINo only assumes non-Gaussian noise when causal relations are lincar. These approaches also require the minimality condition (Assumption 3).
Hybrid frameworks integrate methods from different families to improve the inference the graph by mitigat- ing the limitations of one algorithm through its combination with another algorithm. For nontemporal data, one group of methods combines constraint-based and score-basod methods. Greedy Fast Causal inference (GFCI, Ogarrio et al., 2016) is combination of the constraint-based FCT algorithm and the GES algorithm.
7

---

Published in Transactions on Machine Learning Research (05/2024)
which allows addressing FCI limited applicability small sample size data and correcting the graph inferred by GFS in the presence of latent confounders (removing causal sufficiency, stated in Assumption 1). HCM hybrid (Li et al., 2022) aims to discover the causal structure from mixed nontemporal data and combines part of the constraint-base based method and greody search adapted for mixed data. SVAR-GFCI introducod by Malinsky & Spirtes (2018) extends GFCT for temporal data. Another type of hybrid method is a com- bination of constraint-based and noise-based methods. Hoyer et al. (2008) presented a hybrid approach for nontemporal called PClingam that starts with constraint-based procedure find the pattern of the graph and then uses noise-based procedure to orient some of the non-oriented edges (depending on the noise distribution), which allows obtaining a more informative causal graph. Another algorithm called FRITL (Chen et al., 2021) aims to infer more informative causal graphs with the presence of hidden confounders using the noise-based LiNGAM methods to refine the output of the FCI algorithm. For time series, a combi- nation of noise- based and constraint- based methods was proposed by Assaad et al. (2021) to infer an SCG assuming there are no cycles between different time scrics-which starts with inferring causal order using an additive noise model and pruning unnecessary edges using conditional independence tests. The combination of methods from different families generally relies on the assumptions required by employed methods (as for example in the case of GFCI or FRTIL), while sometimes hybridization allows for relaxation of some assumptions, c.g., faithfulness in the case of NBCBacyelie or non-Gaussian noise in the case of PClingam.
3.2 Details on noise-based and constraint-based methods
Let us first describe the basic steps of noise-based methods. A noise-based algorithun that infers causal graph relies on the fact that, under an identifiable functional model (Assumption 4), prediction model of a target node Y where the predictors are the true causes of Y should yicld residuals (that represent the noise) that are independent of the causes. The procedure of such an algorithm can be divided into two main steps:
NB1. Find the causal order between instantaneous nodes V, by recursively performing regression and independence tests between the predictors and residuals (noise). But note that even if only instan- taneous nodes V, are accounted for, lagged nodes used in the regression means to account for confounder bias. For example, assuming lincarity, we use the following regression model to compute the residuals of each Y, E Vz:
Y,= Σ X.EVAYY))
Xey +
Σ Zsye 2E-
(2)
NB2. Find which set of predictors is not needed to keep the independence between other predictors and residuals. The former set of predictors is considered not causally related to the node that is predicted and the latter set of predictors is considered as the causes of this node.
In general, step NB1 requires only Assumptions 1, 2, 4 and 5. Note that it has been shown that the causal order can be identified even if Assumption 3 is violated (Peters et al., 2014)². However, Peters et al. (2014) only considered the identifiabliity of the causal order in case of violation of Assumption 3 up to the additive noise model case. However, Assumption is required for step NB2. The output of step NBI is a causal order 4. For step NB1 one can use, for example, TiMINo (Peters et al., 2013) or VarLiNGAM (Hyvärinen et al., 2008) algorithms.
Turning to constraint-based methods, we focus in this paper on the methods that are based the PC- algorithm, which requires causal sufficiency (Assumption 1). It follows that most constraint-based algorithms for WCGs or ECGs can be divided into two main steps:
CB1. Initialize fully connected graph such that lagged relations are oriented using temporal priority (if X₁- is adjacent to Y, and t < t then X₃- + Y)) and instantaneous relations are unoriented, and then prune unnecessary edges using the following procedure:
Note that Peters et al. (2014) considered the case where the minimality assumption violated which is equivalent to the rase where Assumption is violated (Peters al., 2017).
8

---

Published in Transactions on Machine Learning Research (05/2024)
(a) Eliminate edges between nodes (Xe+, Y)) if X,-JLY,
(b) For each pair of nodes (Xxr, Y2) having an edge between them, and for each subset of nodes S S (Xx,, Yi) of size between X₁- and Y, if X1- S.
1 such that AZp E S, Zy is adjacent to Yt, climinate the edge
(c) Iteratively repeat step (b) while increasing the size of the conditioning set n by 1 until there are no more adjacent pairs (Xo+, such that there is a subset S S V (XX,, Yi) of size n that was not tested.
CB2. Orient instantancous relations using some rules (in case of causal sufficiency, see Spirtes et al., 2000, Meek, 1995).
Note that for step CBI, we only need Assumptions 1, 2, 3 and 5, while steps CB1 and CB2 together require the faithfulness assumption, which is stronger than Assumptions 3 (Ramsey et al., 2006). The output of the CB1 step is a partially oriented graph 9 that shares the same skeleton as the true graph G* and where all lagged relations are oriented and all instantancous relations are non-oriented.
In our work, we consider two algorithums from this family. The first one, PCMCI+ (Runge, 2020), is an adaptation of the PC-algorithm to time series that can discover WCGs, and the second one, PCGCE (Assaad et al., 2022c), is an adaptation of the PC-algorithm that can discover ECGs.
4 Hybrids of constraint-based and noise-based algorithms
Here, we present a hybrid framework for discovering causal graphs from observational temporal data, which contains two classes of methods:
(NBCB) and constraint-based-ther noise-based (CBNB). Both classes of methods operate under identical assumptions. They both necessitate the standard Assumptions 1 and 2 addition to Assumption for stationary time series. Moreover, both classes require Assumption 4 which is essential for noise- based methods. As both classes use only part of the algorithms from the constraint- baast family, they do not require the faithfulness assumption but only the weaker adjacency faithfulness, stated in Assumption 3. In the rest of the paper, assume that methods from CBNB or NBCB classes are built using the algorithms from constraint-based and noisc-based families that are correct under the given assumptions.
Note that we do not need an acyclicity assumption of the true SCG, as in NBCBaeyelic, since we primarily focus on inferring a WCG or an ECG. If needed, we can then deduce the SCG from the inferred WCG or the inferred ECG.
In the following sections, we provide a detailed description of the NBCB and CBNB classes of methods.
4.1 NBCB class of algorithms
Each of the methods in the NBCB class has two major steps. The first part of NBCB constructs fully connected graph such that lagged relations are oriented using temporal priority, on which the NB1 step is applied in order to find the causal order between all instantaneous nodes.
In the second part, we aim to use CB1 to prune the edges. This step can be optimized by using additional information on the causal order. We modify CB1 step CB1', by taking into account the causal order of the nodes in the following way:
CB1'. Start with the initialization of the fully connected oriented graph as instantaneous relations can be oriented using the causal order ा.
(a) Eliminate edges between nodes 3 (Xe,, Yi) if Xy-
(b) For each pair of nodes (Xe,, Y2) having an edge between them, and for each subset of nodes
S C V*\(Xr. Yd) of size n = 1 such that VZy E S, Zr is parent of Y,, eliminate the edge between X,, and Y; if 1LY S.
We recall that 1* a wildcard that represent time step where E ('....., in the context of WCG and represent. either t- or in context of RCG.
9

---

Published in Transactions on Machine Learning Research (05/2024)
X1
2.
Y
W.-
U.
Ux
Ut
(a) Step NB1
(b) Graph based on
(c) Step CB1'
Figure 4: Illustration of the NBCB algorithm for the running example. (a) Output of the NB1 step (b) Output of the CB1.
(c) Iteratively repeat step (b) while increasing the size the conditioning set n by 1 until there are no more adjacent pairs (X,,, Y2), such that there is a subset (X,,, Yd) of size n that was not tested.
Note that in CB1' step (a) and (c) are the same in step CB1. The NBCB class of methods can be presented combination of the NB1 and CB1', for which provide schematic illustration in Figure 4. Theorem 1. Let G (Vf, Bf) be FTCG. Under Assumptions 1, 2, 4, 5 and given perfect conditional independence information about all pairs of variables in VI, any algorithm in the NBCB class returns the correct WCG or the correct ECG compatible with g5.
The proof of Theorem 1 is available in Appendix A. It is important to note that after having obtained the WCG or the ECG, we can deduce the correct SCG using Definition
The NBCB class robust to the violation of Assumption 3. This mcans that even if Assumption is violated, NBCB is still capable of providing valuable information on causal relationships, as demonstrated in the following proposition. We restrict ourselves to class of functional identifiable models known restrictive additive noise models class (Peters et al., 2014), which is stronger than Assumption 4.
Proposition (Violation of Assumption 3). Under Assumptions 1, 5, given that the SCM is restrictive additive noise model (Peters et al., 2014), and given a correct causal order between instantaneous nodes, the NBCB class would give a WCG or an ECG such that, for each pair of nodes X₃, and Yt, one of the following possibilities holds true:
(1) The causal relationship between N,- and V, is correctly identified.
(2) X₁- and Yt ave not adjacent in the inferred graph, but they are adjacent in the true graph.
(3) X and Y, adjacent in the inferred graph, but they are not adjacent in the true graph.
The proof of Proposition 1 is presented in Appendix A. Proposition states that if there an oriented edge in graph G inferred by NBCB, then it can not have opposite orientation in the true graph. In the following, we illustrate cases (2) and (3) of the Proposition 1. Let consider that there exists lincar dynamic SCM with the corresponding true WCG g" presented in Figure 5a. As long as adjacency faithfulness is violated, we can assume that there exists a path (Zz-2, Zt-1, Z,, Xx) which is canceled by the path (2,-2, (see example faithfulness violation in Section 2.1), such that in the observed data Z,-2lXX, | X,-I- Thus, the edge Z,-2 X, would be removed, so we obtain case (2) Proposition 1. A similar argument works for the edge Zt-2 Y.. Further, these two errors would propagate in the next step for the pair of nodes Y, and Xt. As in the inferred graph G", edges Z X, and Z,-2 Y, absent.
10

---

Published in Transactions on Machine Learning Research (05/2024)
X
Xi
Z
( WCG of an SCM violating adjacency faithfulness
(b) Output of NBCB
Figure 5: Illustration of items (2) and (3) in Proposition 1.
(see Figure 5b), then 44 Y2 Pag- (Pa) (Y)), as Z is the common confounder in the true graph, thus the edge X,-Y, Y, would not be removed and we obtain the case (3) in Proposition 1.
We want to highlight that Proposition 1 holds when the CB1' step of NBCB is implemented using PC- style algorithm. Other constraint- based algorithms could be envisioned, such as greedy approach where the iterative process of finding conditional independence while progressively expanding the conditioning set (steps (b) and (c) of CB1') is replaced by a single step of conditioning on all parents. With such a greedy algorithm, the concerns outlined in case (3) of the proposition could be alleviated.
Note that NBCB would perform poorly when the SCM is not an identifiable functional model (Assumption 4 is violated). Tn this case, NB1 would give incorrect causal order, and the errors would propagate in the second step.
Algorithm 1: Boise-Based--oe
Based (NBCB)
Input: A multivariate time series, maximal temporal lag y and a significance threshold a, NB1, CB1', independence measure 10), and conditional independence test C1() Result: 9" (WCG or ECG) and ga (SCG)
Find the causal order & between all instantaneous nodes using NB1 which lakes and I() as hyper- prper-parameters;
Discover G" using CB1' which takes y, a, CI(), and as pyper-parameters:
Deduce the SCG ga from 9 using Definition 3.
The pseudo-code of NBCB is given in Algorithm 1, which involves the abstract steps NB1 and CB1'. Step NB1 can be directly obtained from any existing noise- based algorithm. In the experimental section of this paper, step NB1 is directly based on the VarLiNGAM algorithm, while step CB1' is either based on the modification of the PCTMI+ algorithm or on the modification of the PCGCE algorithm. More details on specific versions of NB1 and CBI' is given Appendix B.
4.2 CBNB class of algorithms
As far as we know, there exists no previous work that investigated the case where the constraint-based part a hybrid method is executed before the noise-based part in causal discovery from time series (for non-temporal data, see PClingam, Hoyer et al., 2008). theory, there no clear argument as to why one part should be executed before the other. So here, we present new class of methods called CBNB, where the constraint- based part is before the noise-based part.
In the first step of CBNB, CB1 is used to infer g'. Then, we are going to orient edges between instantancous nodes V, by finding the causal order between them.
A vanilla approach would be to apply NB1 over all instantaneous nodes (while taking into account lagged common confounders), as it was done NBCB, to get the causal order and then orient the instantancous relations accordingly. However, we argue that this vanilla approach, despite being correct, is not optimal since it does not take into account the knowledge that has already been acquired through the construction
11

---

Published in Transactions on Machine Learning Research (05/2024)
X--2
Wa
1/
Ux
Ut
(a) Step CB1
(b) Undirected cycle group
(c) Step NB1'
Figure Illustration of the CBNB algorithm for the running example. (a) Output of the CB1 step (b) Detection of the undirected cycle group, where red and blue colours denote two different cycle groups of instantancous nodes (c) Output of the NB1' on each of the cycle groups.
of the outpul graph in step CB1. Therefore, we modily the NB1 step to NB1' by finding the causal order within different groups of instantaneous nodes separately in the following way:
NB1. Find the causal order within instantaneous groups of nodes Tr S V. by recursively performing regression and independence tests between the predictors and residuals (noise). But note that even only the instanlaneous group of nodes Il, are accounted for, the lagged parents Pag. (Il) are used in the regression as a means to account for confounder bias.
Not any groups of instantaneous nodes T, would yield correct causal order since, in general, for any X1, Y E 4, Ie U Pag. (I+) does not necessarily contain any subset that remove confounding bias between X, and Y, Therefore, these groups should be selected carefully. To find these groups, we first need to define an undirected cycle walk.
Definition 5 (Undirected Cycle Walk). Let 9' be the output of the CB1 step. A sequence of edges u (et....,,,,) en), for n 2 2, is an undirected cycle walk iff
Ve, E u, G₁ is an undirected edge in O";
Ve,,e E u, such that < j, no node in e; coincides with any node in ej, except if where the right-hand side node in 6 always coincide with the left-hand side node in e.41, if i = 1, n, where the left-hand side node in e1 and the right-hand side node in en always coincide.
Note that in our definition an undirected edge can form an undirected cycle walk. We provide schematic illustration in Figure for the running example. In Figure 6b, (X,-Y, Ye-YceZa Ze, Z.-X,) and (Z,-Y,, Y.- Wt, W, Ze) are two undirocted cycle walks. Notice that Z, Y,, is in both undirected eycle walks and would be considered twice, which is not only compulational problem but might also induce bias in practice. Thus, defining undirected cycle walk alone is not sufficient. So, we combine all undirected cycle walks that share at least one edge in a undirected cycle group" which is defined as follows:
Definition 6 (Undirected Cycle Group). Let 9* be the output of the CB1 step. C is an undirocted cycle group of g iff C is sel of undirected cycle walks and Vus, u2 E C, un O u2 + 0.
We assume that two undirected cycle walks and up do not intersect (i.e., n u2 0) if there is no common edge between these two walks. For simplicity, we consider two undirected cycle walks that are reversed versions of one another as equivalent and so only one of these two undirected cycle walks will be
NNoe that definition cycle group is different than the introduced Spirtes (1995).
12

---

Published in Transactions on Machine Learning Research (05/2024)
accounted for. In Figure 6b, for the WCG, there are two undirected cycle groups, C1 = - The same example applies
7t - Xt), (Z+ Y,, We, Wt 7.),.... ........). and C2 = [(U, Wt, to the corresponding ECG, Given an undirected cycle group C, we are interested in the set of its nodes, mcaning the set of nodes that belong to undirected cycle walks described by the undirected cycle group. Similarly, we say that an edge X, Yy belongs to ifl Bu such that Yx), E u.
Having brought out the concept of undivected cycle group, we can now describe the second Quoise-based part of CBNB. Given the output of the CB1 step, CBNB scarches for all undirected cycle groups. Note that cach edge is member of exactly one undirected eycle group. Then for each undirected cycle group C, CBNB uses NB1' to find the causal order ı between all the nodes belonging to undirected cycle group C. Finally, using this causal order, CBNB orient all edges belonging to C.
Note that the CBNB step where NB1' applied for different undirected cycle groups can be parallelized, which can significantly improve the computational time for high dimensional problems.
Theorem 2. Let G = E/) an FTCG. Under Assumptions 1, 2, 3, 4, and given perfect conditional independence information about all pairs of variables in VI, any algorithm in the CBNB class returns the correct WCG or the correct FCG compatible with GJ.
The proof of Theorem 2 is available in Appendix A. It is also important to note that as in the case of NBCB, after having obtained the WCG or the ECG, we can deduce the correct SCG using Definition 3.
The CBNB class is robust to the violation of Assumption 4. This means that even if Assumption 4 is violated, CBNB is still capable of providing valuable information on causal relationships, as demonstrated in the following proposition.
Proposition 2 (Violation of Assumption 4). Under Assumplions 1, 2, 3, 5 and given perfect conditional independence information about all pairs of variables, CBNB is guaranteed to find the correct skeleton of the WCG or the ECG.
The proof of Proposition 2 is available in Appendix A. Note that since CBNB gives the correct skeleton of WCGs and ECGs, the correct skeleton of SCG can also be deduced. If Assumption is violated, then the skeleton obtained in the CB1 step of CBNB is not reliable, thereby affecting the reliability of the CBNB algorithm's 's results.
The pseudo-code of CBNB is given in Algorithm 2, which involves the abstract steps CB1 and NB1. In the experimental section of this paper, step CB1 is directly based either on the PCMC1+ algorithm or on the PCGCE algorithm, while step NB1' is based on the modification of the VarLiNGAM algorithm. More details on specilic versions of CB1 and NB1' given in Appendix B.
Algorithm 2: whwerrattt--aaee------------
(CBNB)
Input: A multivariate time series, a maximal temporal lag y and a significance threshold CB1, NB1', an independence measure I(), and a conditional independence test CT() Result: Ó+ (WCG or ECG) and 9a (SCG)
Initialize & as the output of CB1 which takes 7, a, and CI() as aaper-parameters: for each undirected cycle group C in 9- do
Ie: set of nodes that belong to C;
Find the causal order á between nodes in I4 using NB1' which takes y, 10, and 9 as hyper-parameters;
Orient instantaneous edges between T, in 9 using the order म;
Deduce the SCG g from 9' using Definition
4.3 Complexity analysis for NBCB and CBNB classes of methods
When considering d time series, finding the causal order is of complexity di f(n, d) where f(n, is the complexity of the user-specific regression method with time series length n. Then, pruning the graph by
13

---

Published in Transactions on Machine Learning Research (05/2024)
X
X
X
Or
Opz
Gya - a are@a
Z
Y
O you
dayegge
a you
W
W
W
W
Cyclic Diamond
Unfaithful Diamond
Adjacency Unfaithful
Diamond
Diamond
Figure 7: Summary causal graphs corresponding to the data simulated in Section 5.2. The last two models correspond to unfaithful distribution.
conditional independence tests is of complexity (dg)) 1)=1 where represents the maximal degree of any (k-1))
node, is equal to t when considering a WCG and @ is equal to 2 when considering an FCG, and each operation consists conducting significance test to a conditional independence measure. Both CBNB and
NBCB have the same complexity in the worst case, d [R,(n, d) + (do)"dd-1))+= which corresponds for CBNB the case where there is only one undirected cycle group.
(K-13
5
Experiments
In this section, we propose first an extensive analysis both on simulated data, generated from basic causal structures, and on simulated but realistic benchmarks. We then perform an analysis on different real datasets.
5.1
Experimental setup
Baselines and hyper-parameterrs
We compare NBCB and CBNB with five state-of-the-ar methods:
the multivariate version of Granger Causality denoted GCMVL (Arnold et al., 2007);
the constraint-based methods PCMCT* (Runge, 2020) for which we use the Python code available
https://github. http:://ggithbb.co///ooorrrggeee ccmm//akkbrrggeetirraatttte and PCGCE (Assaad al., 2022c) for which the main Python code available at https: h/tp::///gtthbl com/ ckassad/PCGCE For PCGCE, the authors suggested, we reduce the dimensionality of V.- in the ECG to 1 using PCA;
the continuous optimization-based method Dynotears (Pamfil et al., 2020), for which the Python http://ww...cccaaaaaaaaaaeeeeeee For this method, we set
code is available at the hyperparameters to their recommended values (Aw XA 0.05 and aw a 0.01);
the based method VarLINGAM (Hyvärinen et al., 2008) for which we use the Python code available al https:// http//gttbtb..t//////////eeeee wttp/oottm/mingaaaaaeeeaeeeee where the regularization parameter the adaptive Lasso is selected using BIC.
For all the methods, the maximal temporal lag is set to 7 = and the significant threshold for hypothesis testing to a = 0.05. We test two versions of each of our classes which we denote NBCB-w, NBCB-e, CBNB- w, and CBNB-e. Methods with '-w" suffix are based on the algorithms that infer a WCG, while methods
AA Python code all methods and of every experimentation is available https://github. con/ ccaee//caaeaaaae/ttttri.... of_CB_ _f____and___ NB. for Series.
14

---

Published in Transactions on Machine Learning Research (05/2024)
with "-e' are based on the algorithms that infer an ECG. In NBCB-w and NBCB-e, the NB1 step is based on the VarI.NGAM algorithm and the CBI' step is respectively based on the PCMCT+ algorithm and the PCGCE algorithm. In CBNB-w and CBNB-e, the CB1 step is respectively based on the PCMCI+ algorithm and the PCGCE algorithm and the NB1' step is based on the VarLiNGAM algorithm. The pscudo-code of each version of the NB1, CB1, NB1', CB1' steps are given Appendix B. To find undirected cycle walks CBNB-w and CBNB-e, we use an adapted version of Paton's algorithm (Paton, 1969). For all methods that require conditional independence test, we use a test based on partial correlation, which assumes Gaussian distributions but which has been successfully used non-iid data (Peters et al., 2013).
For real data, we also use nonlinear versions of our hybrid algorithms as well of the PCMCI and the PCGCE algorithrns. We use kernel-based conditional independence test which combines Gaussian process regression with a distance correlation test on the residuals (Runge et al., 2019), and a Gaussian process regression in the noise-based part. All nonlinear versions are denoted by the suffix "-nl".
Evaluation. In the different experimental settings, we compared the results concerning the F1 score of the orientations in the SCG obtained without considering self causes, as it is treated differently depending the methods. When there are three datasets or more, report the mean and the variance for the Fl score.
5.2 Simulated data with Gaussian and non- non-Gaussian noise
The simulated datasets correspond to four causally sulficient SCGs presented in Figure 7, extracted from WCGs 9", among which three are acyelic, two correspond to an unfaithful distribution, and one is cyclic. The generating process of all datasots is the following: for all Y, for all t 0,
Yi = a
Σ
X + 0.1g".
XI- (V.
where ay: Gzy E U([-1, (0.1, and for each parent X we randomly choose if X causes Y instanta- neously or with a lag of 1, i.e., l E 13. Regarding the noise, we consider two different settings, in the first the noise is drawn from a uniform distribution, i.e, zx ~ U([-1, from a Gaussian distribution, i.c., 5" N(.. 1). For cach setting and each structure in Figure 7 we generate 100 datasets of 1000 timestamps.
-U[[,, I]), and in the second the noise is drawn
For the unfaithful diamond structure in Figure 7, following Zhalama et al. (2016), set axy ay: O2y aw to zero, and azw = -Ury Aaz.- All relationships are considered instantaneous. Consequently, in the distribution consistent with this model, we observe X_LW, which violates the faithfulness assumption as this indopendence is not entailed by the causal Markov condition. However, it docs not violate the adjacency faithfulness assumption since is not adjacent to W in the graph. Similarly, for the adjacency unfaithful diamond structure, we set anw = -yw - O2z4lzw which violates the adjacency faithfulness assumption since in addition to X being adjacent to W in the graph, in the distribution, we observe X_I. W, and this independence is not entailed by the causal Markov condition.
In Table 1, we report the results for the setting with non-Gaussian noise (top panel), and with Gaussian noise (bottom panel).
Let us start with the case of non-Gaussian noise, which is easier to handle for most methods. For the first two structures, diamond and cyclic diamond, all assumptions required by both families of methods are satisfied, as well as by competitors. In this case, VarLiNGAM has the best performance for diamond, followed by CBNB-w and NBCB-w, while CBNB-w and NBCB-w have the best performance for cyclic diamond, followed by VarLiNGAM. PCMCI+ comes closest to these methods. As expected from these results, CBNB-w and NBCB-w perform better than both original noise-based and constraint- basod methods or as a trade-off between them. We can note that the same conclusion can be made for NBCB-e and CBNB-e. For the unfaithful structures, constraint- due to faithfulness violation. VarLiNGAM has the best results, which makes sense as it does not rely on faithfulness, followed by CBNB-c, with close results by NBCB-c. We can also note that our methods experience noticeable drop in performance only for adjacency unfaithful structures, confirming that they
see that
methods PCMCI+ and PCGCE have a drop in performance
15

---

Published in Transactions on Machine Learning Research (05/2024)
Table 1: Results obtained on the simulated data of Section 5.2 for the different structures with 1000 obser- vations with non-Gaussian noise (top panel) and with Gaussian noise (bottom panel). We report the mean and the variance of the F1 score of the orientations in the SCG. The best results are in blue bold and the second best results in green bold.
Diamond
Cyclic Diamond
Unf. Diamond Adj. unf. Diamond
Non-Gaussian noise
NBCB-w
1.9400011
0.81 = 0.01
0.86 = 0.01
0.8 = 0.01
CBNB-w
0.94 +094+000 0.01
0.8 + 0.01
0.9 + 0.01
0.84 + 0.01
NBCB-e
0.74
0.01
0.95 = 0.01
0.86 = 0.01
CBNB-c
0.02
0.02
0.96 + 0.01
0.86 = 0.01
GCMVL
0.86+0001
0.01
0.04 + 0.01
0
PCMCT*
0.01
0.75
0.47 0.04
0.44 0.03
PCGCE
0.00
0.60
0.01
0.45 0.01
Dynotears
0.00
0.0
0.0 0.0
0.0 0.0
VarLiNGAM
0.99 0.01
0.79
0.98 0.01
0.87 = 0.01
Gaussian noise
NBCB-w
0.08
0.77
0.52 + 0.05
0.48 0.01
CBNB-w
0.84
0.75
0.52 + 0.05
0.48 0.06
NBCB-e
0.02
0.02
0.52 + 0.07
0.44 0.06
CBNB-e
0.03
0.02
0.53 + 0.07
0.44 0.05
GCMVL
0.87 0.01
0.7
0.03 + 0.01
0.01 0.01
PCMCI+
0.93 0.01
0.75
0.42 + 0.05
0.4
PCGCE
0.02
0.65
0.02
0.44
Dynotears
0.02
0.0
0.0 0.0
0.0
VarLiNGAM
0.08
0.74
0.42
do not require a full faithfulness assumption but are surprisingly still competitive for adjacency unfaithful structure, illustrating some robustness.
Considering Gaussian noise is more challenging, the SCM is not an identifiable functional model (As- sumption 4 is violated), which is needed for VarLiNGAM (and its use within the proposed methods). For the first diamond structure, as expected, POMCI performs best, closely followed by GCMVL and CBNB- w, NBCB-w, and VarLiNGAM. NBCB-e and CBNB-c demonstrate lower performance than VarLiNGAM, due lower results of PCCGE. For the cyclic diamond structure, NBCB-w has the best results, followed by CBNB-w and PCMCI+ For unfaithful structures with Gaussian noise, the constraint-based methods PCMCI- and PCGCE again experience drop in performance due to faithfulness violation. Our methods yield the best results. Specifically, CBNB-e performs best for the unfaithful diamond, with the rest of our methods being the second-best. NBCB-w and CBNB-w work best for the adjacency unfaithful diamond, followed by NBCB-e, CBNB-e algorithms, and PCGCE.
We highlight the consistently poor performance Dynotears in Table 1, where this method has the lowest result in all scenarios. This can be attributed the fact that our simulated data, the variances do not increase in accordance with the topological order of the WCG.
Comparing PCMCI+ and PCGCE, we the unfaithful cases for both types of noise distribution. This empirical observation suggests that PCGCE is more robust to assumption violation. This behavior is also inherited by CBNB-e and NBCB-e methods.
that PCGCE has lower performance in general, except for
We can conclude that when necessary assumptions are satisfied, CBNB-w and NBCB-w w are either trade-offis between the PCMCI+ and VarLiNGAM or perform better, and NBCB-c and CBNB-e, are tradc-offs between PCGCE and VarLiNGAM. For the unfaithful structures under assumption violation, all our methods are more robust compared to constraint and noise-based families.
16

---

Published in Transactions on Machine Learning Research (05/2024)
Table 2: Results for realistic datasets of Section 5.3 generated using the Lotka Volterra model with five species (left column) and ten species (right column). We report the mean and the variance of the F1 score of the orientations in the SCG, The best results are in blue bold and the second best results are in bold green.
Lotka (olterra(5)
Lotka Volterra (10)
NBCB-w
0.41 + 0.03
0.28 + 0.01
CBNB-w
0.38 = 0.03
0.24 = 0.01
NBCB-e
0.47 + 0.02
0.24 + 0.01
CBNB-e
0.44 0.02
0.23 + 0.01
GCMVL
0.19 + 0.03
0.11 + 0.01
PCMCT+
0.36 + 0.03
0.22 0.01
PCGCE
0.44 0.02
0.20
Dynotears
0.18 + 0.05
0.15 0.01
VarLiNGAM
0.43 + 0.06
0.23 + 0.02
Table presents the F1 score of the orientations in the SCG, which is not suitable to illustrate the Propo- sition 2. Thus, Table 6 Appendix E. we present the F1 score on the adjacencies, which illustrate the robustness of CBNB class to Assumption 4. More precisely, CBNB-w has the same performance PCMCI and better than the results of NBCB-w, in the case of Gaussian noise, for all structures, except the adjacency unfaithful diamond. We also see similar results for CBNB-e. Proposition is difficult to see from Table 1, as we do not evaluate separately orientations and adjacencies, due to the specific structure of the inferred graph.
5.3 Realistic ecological data from the Lotka-Voltere model
We consider the simulation with multi-species generalization of the Ricker model introduced by Poggiato et al. (2022), which is analogous to the generalized the same paper and commonly used in ecological studies. Ricker model with abiotic control in discrete time for abundance of species Y at time step t has the following form:
model with abiotic control presented in
Y exp exp
AA Ex Exc-iEPAgu(YY.O (Ys,0-) axy X + V(-dy) exp (-(0=--)))) + <t (preys) 20
Ye
Y, exp A
(Y. aay X1-1 - 11) + +
(predators)
where Y, is the abundance of species Y at time t, the upper equation is related to preys and the lower to predator species, Y is the abundance of species Y in the stationary state, ary is the strength of the effect of species X on species Y and ag is strength of the effect of species Y on itself, & is an i.i.d Gaussian random variable with variance or, Oy is a niche optimum for species Y, is the environmental variable, i is the extinction rate of the predator. We run this simulation for the number of species $ {5, 10) with the following fixed parameters: fixed environment
0.5, number of time steps T = 1000, μ =0.05, o, 0.2, for each species 0y randomly sampled from U(0.005, 0, (,)5)), the interaction matrix related to coefficients Ozy and a, is obtained through a randomly generated WCG G which is compatible with an SCG ga. The SCG is constrained to contain only bi-directed edges and to encompass precisely trophic levels, representing the hierarchical positions species in the food chain. Specifically, these levels include basal species or prey (Ir), their predators (L2); and the predators of prodators (Lz). The second constraint ensures that VX E L, and VY Lj, if X = in Go then - (for more details see Poggiato et al., 2022). The interaction strength is randomly sampled for all interactions. We generate 100 graphs and thus we obtain 100 datasets.
For the Lotka (otka-Volterra(5) datascts, NBCB-e performs better than the other methods followed by CBNB-c and PCGCE as shown in Table 2. Close to them perform VarLiNGAM, NBCB-w and CBNB-w. Dynolears and GCMVL have the lowest results. For the Lotka- Volterra(10) datasets, all results saw a significant decrease, with NBCB-w performing the best, followed by CBNB-w and NBCB-c. It is worth noting that for all datasets, NBCB-c and CBNB-e perform either better or equally as well as PCGCE and VarLiNGAM, while NBCB-w and CBNB-w outperform PCMCI.
17

---

Published in Transactions on Machine Learning Research (05/2024)
Table 3: Results for real datasets of Section 5.4 using linear methods. We report the mean and the variance (when meaningful, see data description) of the F1 score of the orientations in the SCG. The best results are in blue bold and the second best results are in green bold.
Temp.
Veil1
Veil2
Dairy
Ingest.
Webl
Web2
Antivirust
Antivirus2
NBCB-w
1
1
0
0.4
0.47 + 0.03
0.2
0.23
0.13
0.3
CBNB-W 1
1
0
0.4
0.46 = 0.11
0.24
0.29
0.18
0.18
NBCB-e
1
1
1
0.4
0.5 + 0.05
0.24
0.42
0.29
0.38
CBNB-e
1
1
0.4
0.52
0.15
0.38
0.33
0.27
GCMVL
0.67
1
0.33
0.503.0.3
0.19
0.0
0.08
0.0
PCMCI*
1
0
0.4
0.3 0.3 0.08
0.17
0.32
0.04
0.11
PCGCE
1
1
0.4
0.55
0.21
0.34
0.29
0.36
Dynotears
0.67
1
1
0.33
0.25 0.06
0.22
0.3
0.18
0.17
VarLiNGAM 1
1
1
0.5
0.49 + 0.05
0.23
0.2
0.18
0.18
5.4 Real data
Nine different real datasets considered in this study. Taking into account the limitations of certain meth- ods in handling nonlinearity, we start by evaluating our algorithms using linear tests and linear regressions, alongside linear tests for constraint-basee methods. Then, we proceed to compare the nonlinear counterparts of our mothods with those of the constraint-ban based methods while providing a computational time analysis.
5.4.1 The linear case
We detail the performance of each method in the following paragraphs, while the results are summarized in Table 3. See Appendix D for URL links to the considered datasets.
Temperature. This a bivariate time series of length 168 about indoor and outdoor O measurements. As noted by Assaad al. (2021), it expected that O causes I.
NBCB-w, CBNB-w, NBCB-e, CBNB-e, PCMCI+, PCGCE, and VarLiNGAM correctly infer O I. GCMVL and Dynotears infer bidirected causal relation.
Veilleux. We considered two datasets for Figure 11(a) and 12(a) (Jost & Ellner, 2000) from Veilleux (1979)
which study interactions between predatory ciliate Dinidum nasutum and its prey Paramecium aurelia with different values of Cerophyl concentrations (CC): 0.375 and 0.5. The lengths the time series are 71 and 65. These data were previously analyzed with causal discovery algorithms (Barraquand et al., 2021, Sugihara al., 2012), which showed bidirectional relationships in both cases.
Here, NBCB-e, CBNB-c, GCMVL, PCGCE, Dynotears and VarLiNGAM discover bidirected relationships Paramecium = Didinium in both datasets, which is consistent with Sugihara et al. (2012), Barraquand et al. (2021). CBNB-w, NBCB-w, PCMCI+ have detected bidirected relationships between Paramecium and Didinium only in the first datasot.
Diary. This dataset provides ten years (from 09/2008 to 12/2018) monthly prices for milk M, butter B, and cheddar cheese C, so the three time series are of length 124. We expect that the price of milk is common cause of the price of butter and the price of cheddar cheese: B M C.
NBCB-w, CBNB-w, NBCB-e, CBNB-e, PCMCT+, PCGCE and VarLiNGAM correctly inferred that M - B. But NBCB-w and CBNB-w wrongly inferred that M + C + B, NBCB-e, CBNB-e, wrongly inferred that M - B + C, PCMCI+ and PCGCE wrongly inferred that M +- C + B and VarLiNGAM wrongly inferred that C + B. GCMVL wrongly infers B = + C and Dynotears wrongly infers M BSC.
Ingestion mini. This benchmark provided by Easy consists of datasets each containing three time series with 1000 timestamps collected from IT monitoring system with one-minute sampling rate. Half
18

---

Published in Transactions on Machine Learning Research (05/2024)
the datasets are compatible with the graph C.M.I <- M.E - G.H.I (Assaad et al., 2022b) where M.E is the metric extraction which represents the activity of the extraction of the metrics from the messages; G. G. is the group history insertion, which represents the activity of the insertion of the historical status in the database; and C.M.I is the collector monitoring information, which represents the activity of the updates in given database. The second half of the datasets are compatible with the graph M.D - M.E. + M.J where M.D is the metric dispatcher which represents the activity of a process that orients messages to other processes with respect to different types of messages; and M.I is the metric insertion which represents the activity of insertion of data in database. Lags between time series are unknown, well as the existence of self-causes.
From Table 3, we can see that PCGCE has the best results followed by CBNB-e then by NBCB-e and GCMVL. After that comes VarLiNGAM and NBCB-w and CBNB-w and PCMCI+.
Finally, Dynotears has the worst result. This might suggest that the lags between causes and effects are not consistent over time, in the sense that if the lags between two-time series vary (while respecting the maximal temporal lag), the extended summary causal graph might remain the same however this is not true for the window causal graph. In this case, we might expect that methods inferring window causal graphs (such as PCMCI-) would perform worse than methods inferring extended summary causal graphs (such as PCGCE).
Web. We consider a datasct that reflects the activity in a web server which is provided by Easy This dataset contains ten time series collected with one-minute sampling rate. The raw data of this case study were initially misaligned. In order to align them, we use the two pre-processing strategies described in Appendix C. We denote the dataset pre-processed using Strategy 1 as Web 1 and the dataset pre-processed using Strategy 2 as Web 2. The two processed datascts contain 3000 timestamps. The corresponding summary causal graph for Web dataset is presented in Figure 8a where Nethn represents the data received by the network interface card in Kbytes/socond; NetOut represents the data transmitted out by the network interface card in Kbytes/seconds
NPH represents the number of HTTP processes; NPP represents the number of PHP processes; NCM represents the number of open MySql connections which are started by PHP processes; CpuHf represents the percentage of CPU used by all HTTP processes; RamH represents the percentage of RAM used by all HTTP processes; CpuP represents the percentage of CPU used by all PHP processes; W represents the Disk write in Kbyles/second; CpuG represents the percentage of global CPU usage.
From Table 3, for the Webl dataset, we can see that NBCB-c and CBNB-w demonstrate the highest perfor- mance, followed by VarLiNGAM. Next are Dynotears and PCGCE. CBNB-e exhibits the lowest score. For the Web2 dataset, NBCB-e attains the highest F1 score, with CBNB-e closely following. The subsequent competitive results are observed with PCGCE and PCMCI*. This could imply that the data is noisy and the time lags are inconsistent throughout time, making the inference of the extended summary graph more robust.
Antivirus. Lastly, we consider a dataset which depicts the impacts of antivirus activity in servers which is again provided by Vista This dataset contains 13 time series such that 3 of them are collected with a one-minute sampling rate and the rest with a five-minute sampling rate. The raw data of this case study were initially misaligned. To align them, we use the two pre-procsssing strategies described in Appendix C, leading to the dataset Antivirus 1 for Strategy and Antivirus for Strategy 2. The two processed datasets consist of 1321 timestamps. The corresponding summary causal graph for Antivirus dataset is presented in Figure 8b where CUV represents the percentage of CPU usage of antivirus processes in server V; CUGV represents the percentage of CPU usage of the global server V; MUV represents the percentage of memory usage of antivirus process; MUGV represents the percentage of global memory usage of the server; RV represents the Disk 10 read in Kbyles/second; ChIE refers to the required duration in seconds to open an IE browser on server V; CUP represents the percentage of CPU usage of antivirus processes in server P; CUGP represents the percentage of CPU usage of the global server P: MUP represents the percentage of memory usage of antivirus process; MUGP represents the percentage of global memory usage of the server; RP represents the Disk TO read in Kbyyte//ecoodd ChP represents refers to the required duration in seconds
19

---

Published in Transactions on Machine Learning Research (05/2024)
NPH
RamH
CpuHt
CUV
CUGV
ChP
CUGP
CUP
Netln
NPP
CpuP
CpuG
RV
RP
NetOut
NCM
DiskW
MUV
MUGV
ChiE
MUGP
MUP
(a) Web-Activity.
(b) Antivirus-Activee
Figure 8: Summary causal graphs for (a) the Web activity datasets and (b) the Antivirus activity datasets. Those summary causal graphs are constructed by an IT monitoring system's experts.
Table 4: Results for real datasets of Section 5.4 using nonlinear methods. We report the mean and the variance (when meaningful, see data description) of the F1 score of the orientations the SCG. The best results are in blue bold and the second best results are in green bold.
Temp.
Veill
Veil2
Dairy
Ingest.
NBCB-w-nl
1
0.4
0.52 + 0.02
CBNB-w-nl
1
1
0.4
0.54 + 0.06
NBCB-e-nl
1
1
0.4
0.43 + 0.04
CBNB-e-nl
1
0.4
0.49 = 0.07
PCMCI+-1
1
0.0
0.38 + 0.09
PCGCE-nl 0.67
0.4
0.43 + 0.03
to open CITRIX Portal on server P; T represents the global time in seconds required to open CITRIX portal and open the IE browser.
From Table for Antivirus 1, we can see that CBNB-e achieves the best result followed by PCGCE and NBCB-e and then by CBNB-w, VarLiNGAM and Dynotears. GCMVT, and PCMCT+ have low performance, with PCMCI+ being the worst. For Antivirus 2, we can see that NBCB-e performs best followed by PCGCE and then by CBNB-e. The remaining methods have substantial drop in performance. As in the case of Web datasets, improved performance of the PCGCE over PCMCI+ suggests that inference of the extended summary graph is more robust in this case. We can also note that NBCB-e and NBCB-w perform well, while VarLiNGAM does not, which could suggest that VarLiNGAM infers a more dense graph.
5.4.2 The nonlinear case
The results of the nonlinear counterparts of our hybrid methods and of PCMCT+ and PCGCE on real data are presented Table 4. In this scenario, we excluded the Web and Antivirus datascts due computational constraints (running the noulinear counterparts of the algorithms on these datasets is prohibitively expensive due to their size).
In the temperature dataset, the Veilleux datascts and the Dairy datasct, all considered methods produced consistent results compared to their linear counterparts, except for PCGCE, which exhibited decrease in performance the temperature dataset. In the Ingestion mini datasets, we can clearly see that all methods that infer a WCG has slight increase performance and all methods that infer an ECG has a slight decrease in performance. In terms of ranking, in the nonlinear case, NBCB-w-nl demonstrates the best performance, followed by CBNB-w-nl, while PCMCT+ performs the worst despite its performance increase.
20

---

Published in Transactions on Machine Learning Research (05/2024)
800
NBCB w CBNB----l NBCBael
600
time (
CHNB---al
X PCMCIT-al POGCE-al
400
200
Temp-
Veil.
Dairy
Ingest.
Figure 9: Time computation (in second) for NBCB-w, CBNB-w, NBCB-e, CBNB-e, POMCI+, and PCGCE for real datasets of Section 5.4. We report the mean and the standard deviation.
The performance improvement observed in methods inferring a WCG can suggest that the dataset Ingestion mini contains nonlinear causal relations. Conversely, the decline seen in methods inferring ECG could be attributed to the combination of the complexity of nonlinear tests and the necessity for these methods to conduct conditional independence tests with larger conditional sets compared to those considered by other methods.
We also conduct a computation time analysis of the nonlinear counterparts of the methods, as shown in Figure 9. Notably, the computation times for all methods are comparable across the temperature dataset, the Veilleux datasets, and the Dairy dataset, which are relatively small in size. However, in the Ingestion mini datasets, variations in computation time are evident: PCMCI+ exhibits the longest computation time, followed by CBNB-w then by PCGCE and NBCB-w. Our hybrid methods for inferring an ECG (NBCB-e and CBNB-e) exhibit the shortest computation time, with NBCB-e showing a lower computation time compared to CBNB-c. The NBCB methods achieve better time computation because the nonlincar conditional tests they employ are significantly more computationally expensive than learning Gaussian process regression. This implies that the constraint-based step is more costly than the noise-based step. Hence, providing additional knowledge to the constraint-based step, in the form of causal order, results in much greater reduction in computation time compared to when the additional knowledge is given to the noise- base- step, in the form of the skeleton.
6 Discussion
Experiments on simulated data, realistic ecological data, and real data from various applications, show that our hybrid approaches are robust and yield overall good results over all datasets. Notice that for all results on real data, NBCB-w and CBNB-w (which are based on PCMCT+ and VarLiNGAM) never perform simultaneously worse than PCMCI+ and VarLiNGAM. Similarly, NBCB-e and CBNB-e (which are based PCGCE and VarLiNGAM) never perform simultancously worse than PCGCE and VarLiNGAM, except for the Web dataset where CBNB-e has the lowest F1-score (but NBCB-e has the best F1-score). In general, NBCB-e and CBCB-e seem to be more reliable than NBCB-w and CBCB-w for the real data we considered, especially when assuming linearity. As mentioned before, the possible explanation is noisy data and inconsistent time lags. In summary, results on simulated data, realistic ecological data, and real data are coherent with the theoretical findings, showing that algorithms from CBNB and NBCB classes are trade- off' between the original methods, potentially exhibiting enhanced performance compared to the original methods when certain assumptions are violated.
In Table 5, provide various theoretical and experimental criteria to distinguish between the algorithms within the NBCB and CBNB classes. In the second and third rows of Table 5, we present which algorithms infer a WCG and which ones infer an ECG. In the forth and fifth rows, we detail the sleps of the NBCB and CBNB classes of methods. The sixth row indicates that NBCB-w and NBCB-e can still be applied even guaranteod
violated. In such cases, the true graph may not be fully retrieved, but that if the algorithms infer X Y, then in the true graph, we can be certain that Y does not cause (see Proposition 1). Similarly, the seventh shows that CBNB-w and CBNB-e can be utilized even when
when Assumption
21

---

Published in Transactions on Machine Learning Research (05/2024)
Class
NBCB
CBNB
Version
NBCB-c
NBCB-W
CBNB-c ECG
CBNB-W
Output
ECG
WCG
WCG
Step 1
NB1 (VLINGAM)
CB1 (PCGCE - PCMGI+)
Step 2
CB1' (PCGCE PCMCI+)
NB1' (VLINGAM)
Violation of Assump. 3
(X, Y
(Y A X. E
X
X
Violation of Assump.
(X,- EE = (X - E(gg))
Simulated data (Sec. 5.2)
Realistic sim. data (Sec. 5.3)
Real data (Sec. 5.4)
X
x
Table 5: Summary of the two proposed classes of methods, NBCB and CBNB. Rows respectively indicate: their versions NBCB-e, NBCB-w, CBNB-e, CBNB-w; outputs; the algorithms used in each step; their theoretical guarantees, or lack thereof (x), under violation of some assumption; and their advantageous (V) or limited (x) performances on the different data scenarios considered in Section 5. 9 represents the inferred WCG or ECG and G* representes the true WCG or ECG.
Assumption 4 is violated. In this scenario, algorithms are capable of inferring accurate skeleton of the graph, but not the orientations. The last three rows highlight the scenarios where each algorithm outperformed others. Interestingly, in the experimental section, we observed that methods inferring a WCG perform better with simulated data, while methods inferring an ECG excel with real data, assuming linearity.
One of the key limitations of the CBNB and NBCB classes for real-world applications is their reliance on the restrictive assumption that there are no hidden confounders (Assumption 1), which could be often violated. For CBNB, could consider extension of the FRITL algorithm (Chen et al., 2021) for time-series, which is based on building the skeleton using FCI extension and refining after using noisc-based methods. However, it is not clear how to adapt the necessary conditions for undirected cycle groups For NBCB it could be more complicated to relax the no hidden confounders assumption.
Additionally, it would be interesting adapt the CBNB and NBCB classes to the cases when there is a violation of consistency over time or stationarily. One potential direction could be to integrate our mot in the strategy proposed by Saggioro et al. (2020) which combines causal discovery with regime learning optimisation approach. However, this direction might require additional assumptions and while it appears promising for CBNB, it is less obvious for NBCB. Another direction could be to assume the presence of an observed contextual variable that explains the non-stationarity (Mooij et al., 2020, Günther et al., 2023).
Finally, adapting these methods for mixed data can be important in many applications. This can be straight- forward for the constraint-basse part of our algorithms, given the availability of conditional independence tests for mixed data (Zan et al., 2022). However, the adaptation is more challenging for the noise-based part..
7 Conclusion
In this paper, we introduced a framework for hybrids of noise-based and constraint-based methods that can discover causal graphs from temporal data. Algorithms in the first class, denoted NBCB, start with ordering instantaneous relations, and then prune edges of the fully oriented graph. On the other hand, the algorithms from the second class, denoted CBNB, start by finding the skeleton and the orientation of lagged relations using a constraint-based method and temporal priority, then orient instantaneous relations by ordering nodes in each cycle group of instantaneous relations. Overall, the performance of our algorithms is a trade-off between the performance of caint-aint and noise-based algorithms when all assumptions are satisfied, and they outperform other methods in the cases where some of the assumptions are violated.
For future works, it would be interesting to extend these approaches cases involving hidden confounders, non-stationarity, and mixed data.
22

---

Published in Transactions on Machine Learning Research (05/2024)
Acknowledgments
We thank Ali Ait-Bachir, Christophe de Bignicourt and Rachid Mokhtari from EasyVista for providing the IT monitoring data along with the underlying causal graphs. We also thank Giovanni Poggiato for several discussions about the realistie ecological simulated data. Finally, we thank the anonymous reviewers for their helpful comments. This work was partially supported by the CIPHOD project by the Horizon Europe Obsgession project (No: 101134954) and the FRB-CESAB through the IMPACT working group.
by
Grenoble Alpes PER-19-PP38 LANR-19-P3IA-
References
Hugo Arlegui, Emmanuel Mahé, M.-A Richard, Yann Rycke, M. Viguier, Maric Beylot-Barry, A. Dupuy, N. Beneton, P. Joly, Denis Jullien, H. Bachelez, É Sbidian, O. Chosidow, Carle Paul, and F. Tubach. Impact of the first wave of the covid-19 pandemic on the treatment of psoriasis with systemic therapies in france: Results from the psobioteq cohort. Annales de Dermatologie et de Vénéréologie, 150, 02 2023. doi: 10.1016/j.annder 2023.01.0000
Andrew Arnold, Yan Liu, and Naoki Abe. Temporal causal modeling with graphical granger methods. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '07, pp. 66-75, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595936097, doi: 10.1145/1281192, 11155/1281112.22122222
Charles K. Assaad, Emilie Devijver, Eric Gaussier, and Ali Ait-Bachir. A mixed noise and manstriint-based approach to causal inference in time series. In Machine Learning and Knowledge Discovery in Datalases. Research Track, pp. 453 468, Cham, 2021. Springer International Publishing. ISBN 978-3-030-864886-
Charles K. Assaad, Emilic Devijver, and Eric Gaussier. Survey and evaluation of causal discovery methods for time series. Artif. Inl. Res., 73, may 2022a. doi: 10.1613/jair.1.133 1.13422
Charles K. Assaad, Emilie Devijver, and Eric Gaussier. Entropy- based discovery of summary causal graphs in time series. Entropy, 24(8), 2022b. ISSN 1099-4300. doi: 10.3390/c240811156
Charles K. Assaad, Emilie Devijver, and Eric Gaussier. Discovery of extended summary graphs in time series. In James Cussens and Kun Zhang (eds.), Proceedings of the Thirty- Eighth Conference on Uncertainty in Arlificial Intelligence, volume 180 of Proceedings of Machine Learning Research, pp. 106. PMLR, 01-05 Aug 2022c.
Charles K. Assaad, Imad Ez-Zejjari, and Lei Zan. Root cause identification for collective anomalies time series given an acyelic summary causal graph with loops. In Francisco Ruiz, Jennifer Dy, and Jan- Willem van de Meent (eds.), Proceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 8395 8404. PMLR, 25 27 Apr 2023.
Mélanic Bales, Elodic Pambrun, Charlotte Maguct, Judith van der Wacrden, Nine Glangeaud-Frendde Freudenthal,, Marie-Aline Charles, Corinne Bois, Maria Melchior, Jeannette Milgrom, Bruno Falissard, Helene Verdoux, and Anne Laure Sutter. Pathways between risk poootttcteivve factors and maternal postnatal depressive symptoms: The elfe cohort. Journal of Clinical Medicine, 12:3204, 04 2023. doi: 1.3390//jem12093200
Frédéric Barraquand, Coralic Picoche, Matteo Detto, and Florian Hartig. Inferring species interactions using granger causality and convergent cross mapping. Theorelical Ecology. 14(1):87-105, 2021.
Wei Chen, Kun Zhang, Ruichu Cai, Biwei Huang, Joseph Ramsey, Zhifeng Hao, and Clark Glymour. Fritl: A hybrid method for causal discovery the presence of latent confounders. arXiv preprint orXiv:2103. 14238, 2021.
David Maxwell Chickering. Learning equivalence classes of bayesian network structures. Mach. Learn. Res., 2:445-499 498, mar 2002a. ISSN 1532-4435. doi: 10.1162/1532244400700000
23

---

Published in Transactions on Machine Learning Research (05/2024)
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-555 154000 2002b.
David Maxwell Chickering and Christopher Meek. Selective greedy equivalence search: Finding optimal bayesian networks using a polynomial number of score evaluations. arXiv preprint (rXiv:1506.021 02113, 2015.
Maria Dornelas, Laura H Antao, Faye Moyes, Amanda E Bates, Anne E Magurran, Dušan Adam, Asem A Akhmetzhanova, Ward Appeltans, Jose Manuel Arcos, Haley Arnold, et al. Biotime: A database of biodiversity time scries for the anthropocene. Global Ecology and Biogeography, 27(7):760-786, 2018.
Doris Entner and Patrik O Hoyer. On causal discovery from time series data using fci. Probabilistic graphical models, pp. 121-128, 2010.
Chang Gong, Di Yao, Chuzhe Zhang, Wenbin Li, Jingping Bi, Lun Du, and Jin Wang. Causal discovery from temporal data. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, pp. 5803 5804, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701030. doi:
Clive Granger. Investigating causal relations by econometric models and cross-spectral methods. Economel- ricn, 37(3):424-38 38, 1969.
Clive W. J. Granger. Time series analysis, cointegration, and applications. The American Economic Review, 94(3):421 425, 2004. ISSN 00028282.
Wiebke Günther, Urmi Ninad, and Jakob Runge. Causal discovery for time series from multiple datasets with latent contexts. In Robin J. Evans and Nya Shpitser (eds.), Proceedings of the Thirly-Ninth Conference on Uncertainty in Artificial Intelligence, volume 216 of Proceedings of Machine Learning Research, pp. 766-776. PMLR, 31 Jul-04 Aug 2023.
Uzma Hasan, Emam Hossain, and Md Osman Gani. A survey on causal discovery methods for iid and time series data. Transactions on Machine Learning Reseorch, 2023.
Patrik O. Hoyer, Aapo Hyvärinen, Richard Scheines, Peter L. Spirtes, Joseph Ramsey, Gustavo Lacerda, and Shohei Shimizu. Causal discovery of linear acyclic models with arbitrary distributions. In Conference on Uncertainty in Artificial Intelligence, 2008.
Aapo Hyvärinon, Shohei Shimizu, and Patrik O. Hoyer. Causal modelling combining instantancons and lagged ellects: An identifiable model based on non-gaussianity. In Proceedings of the 25th International Conference on Machine Learning, ICML '08, pp. 424 431, New York, NY, USA, 2008. ACM. ISBN 978-1-60558-205--
Christian Jost and Stephen P Ellner. Testing for predator dependence in predator-prey dynamics: non- parametric approach. Proceedings of the Royal Society of London. Series B; Biological Sciences, 267(34)3): 1611-1620, 2000.
Marcus Kaiser and Maksim Sipos. Unsuitability of notears for causal graph discovery when dealing with dimensional quantitics. Neural Processing Letters, 54:1587 1595, 2021.
Yan Li, Rui Xia, Chunchen Liu, and Liang Sun. A hybrid causal structure learning algorithm for mixed-type data. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7435-7443, 2022.
Daniel Malinsky and David Danks. Causal discovery algorithms: A practical guide. Philosophy Compass 13(1)se12470, 2018. doi: https://dh..rr//0.111//// 12470. c12470 10.1111/phc3.12770
Daniel Malinsky and Peter Spirtes. Causal structure learning from multivariate time series settings with unmeasured confounding. In Proceedings of 2018 ACM SIGKDD workshop on causal discovery, pp. 23-47. PMI.R, 2018.
24

---

Published in Transactions on Machine Learning Research (05/2024)
Andrew Meci, Florence Breuil, Ana-Maria Vileu, Thiband Pitel, Caroline Guerrisi, Quentin Robard, Clément Turbelin, Thomas Hanslik, Rossignol Louise, Cécile Souty, and Thierry Blanchon. The sentiworld project: Global mapping of sentinel surveillance networks in general practice. BMC Primary Care, 23, 07 2022. doi: 011/8///11877722--0000
Christopher Meek. Causal inference and causal explanation with background knowledge. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UA195, pp. 403-410, 410, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. ISBN 1558603859.
Joris M. Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. Journal of Machine Learning Research, 21(99):1 108, 2020.
Clémence Moreau, Marine Roux, Jérémie Riou, Clémence M. Canivet, Etienne Audureau, Clovis Lusivika- Nzinga, Pierre Nahon, Fabrice Carrat, Jéröme Boursier, and the ANRS CO12 CirVir group and the ANRS CO22 HEPATHER group Dynamic personalized prediction of the individual liver-related risk after sustained viral response in hev patients. Journal of Viral Hepatitis, 30(6):567-57, 2023. doi: https://doi.orr//0.1111//
Mohammad Amin Morid, Olivia R Liu Sheng, and Joseph Dunbar. Time series prediction using deep learning methods in hearth ACM Transaction on Management Information Systems, 14(1):1 29, 2023.
Juan Miguel Ogarrio, Peter Spirtes, and Joe Ramsey. A hybrid causal search algorithm for latent variable models. In Conference on probabilistic graphical models, pp. 368 379-379. PMLR, 2016.
Roxana Pamfil, Nisara Srivattanaworachai,, Shaan Desai, Philip Pilgerstorfer, Konstantinos Georgatzis, Paul Beaumont, and Bryon Aragam. Dynotears: Structure learning from time-series data. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial In- lelligence and Slatistics, volume 108 of Proceedings of Machine Learning Research, pp. 1595 1605. PMLR, 26 28 Aug 2020.
Keith Paton. An algorithm for finding a fundamental set of cycles of a graph. Commun. ACM, 12(9): 514-518, sep 1969. ISSN 0001-0782. doi: 10.1145/3633219333332.
Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, NY, USA, 2000. ISBN 0-521-77362-8.
Jonas Peters, Joris M. Mooij, Dominík Janzing, and Bernhard Schölkopf. Identifiability of causal graphs using functional models. In Proceedings of the SeeenlySeverdh Conference on Uncerlainly in Arlificial Intelligence, UAr'11, pp. 589-598, Arlington, Virginia, USA, 2011. AUAI Press. ISBN 9780974903972.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Causal inference on time series using restricted structural equation models. In Advances in Neural Information Processing Systems 26, pp. 154 112,162,2 2013.
Jonas Peters, Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 15(68):2009-2053 2014.
Jonas Peters, Dominik Janzing, and Bernhard SchIkopf. Elements of Causal Inference: Foundations and Learning Algorithoss. The MIT Press, 2017. ISBN 0262037319.
Giovanni Poggiato, Jérémy Andréoletti, Laura Shirley, and Wilfried Thuiller. Integrating food webs in species distribution models improves ecological niche estimation and predictions. nov 2022. doi: 10.22541/am / (66853339445823333/
Joseph Ramsey, Peter Spirtes, and Jiji Zhang. adjaacenc-faitthuune and conservative causal inference. In Proceedings of the Twenty-Second Second Conference on Uncertainty in Artificial Intelligence, UAr06, pp. 401-408, Arlington, Virginia, USA, 2006. AUAI Press. ISBN 0974903922.
Joseph D Ramsey. Scaling up greedy causal search for continuous variables. arXiv preprint orXiw:1507.07749 2015.
25

---

Published in Transactions on Machine Learning Research (05/2024)
Jakob Runge. Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets. In Jonas Peters and David Sontag (eds.), Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), volume 124 of Proceedings of Machine Learning Research, pp. 1388 1397. PMLR, 03-06 Aug 2020.
Jakob Runge, Peer Nowack, Marlene Kretschmer, Scth Flaxman, and Dino Sejdinovic. Detecting and quan- tilying causal associalions in large nonlinear time series datasets. Science advances, 5(1 )eaau4999, 2019.
Elena Saggioro, Jana de Wiljes, Marlene Kretschmer, and Jakob Runge. Reconstructing regime-dependent causal relationships from observational time series. Chaos: An Intendisciplinary Journal of Nonlinear Science, 30(11):113115, 11 2020. ISSN 1054-1500. doi: 10.1063/5.0020655
Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(72):2003-25)) -0300 2006.
Shohei Shimizu, Takanori Inazumi, Yasuhiro Sogawa, Aapo Hyvärinen, Yoshinobu Kawahara, Takashi Washio, Patrik O. Hoyer, and Kenneth Bollen. Directlingam: A direct method for learning a linear non-gaussian structural equation model. Journal of Machine Learning Research, 12(33))1225-122) 1248, 2011.
Peter Spirtes. Directed cyclic graphical representations of leedback models. In Proceedings of the Eleventh Conference on Uncertointy in Artificial Intelligence, UAI995, pp. 491-498, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. ISBN 1558603859.
Peter Spirtes, Clark Glymour, and Richard Scheines. Cousation, Prediction, and Search. MIT press, 2nd edition, 2000.
George Sugihara, Robert May, Hao Ye, Chih hao Hsieh, Ethan Deyle, Michael Fogarty, and Stephan Munch. Detecting causality in complex ecosystems. Science, 438(606))4496-500, 2012. doi: 10.1126 1227079.
Damian A. Tamburri, Marco Miglierina, and Elisabetta Di Nitto. Cloud applications monitoring: An industrial study. Information and Software Technology, 127:106376, 2020. ISSN 0950-5849. doi: https: //ddo..or/10..nn (1t...011......ooo.2200. 2020..067.....
loannis Tsamardinos, Laura E Brown, and Constantin F Aliferis. The max-min hill-climiing bayesian
network structure learning algorithm. Machine learning, 65:31-78, 2006.
Brendan G. Veilleux. An analysis of the prodatory interaction between paramccium and didinium. The Jowrnal of Ansmal Ecology, pp. 787 803, 1979.
Thomas Verma and Judea Pearl. Equivalence and synthesis of causal models. Proceedings of the Sizth Annual Conference on Uncerlainly in Artificial Intelligence, UAI '90, pp. 255 260, USA, 1990. Elsevier Science Inc. ISBN 0444892648.
Lei Zan, Anouar Meynaoui, Charles K. Assaad, Emilie Devijver, and Eric Gaussier. A conditional mutual information estimator for mixed data and an associated conditional independence test. Entropy, 24(9). 2022. ISSN 1099-4300. doi: 0..3390/e2409125.
Zhalama, Jiji Zhang, and Wolfgang Mayer. Weakening laithfulness: some heuristic causal discovery algo- rithms. International Journal of Data Science and Analytics, 3:93-104, 2016.
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with no tears: Continuous optimization for structure learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
26

---

Published in Transactions on Machine Learning Research (05/2024)
A Proofs
We recall the definition of blocked paths, backdoor paths, and the backdoor criterion.
Definition 7 (Blocked path, Pearl, 2000). A path is said to be blocked by a set of nodes & C V if it contains an intermediate cause or a common cause such that X E S and if it contains a collider X such that X $ S and no descendant of X is in S.
Note that a path that is not blocked said to be active. Definition 8 (Backdoor path, Pearl, 2000). path between an ordered pair (X,Y) is said to be a backdoor path between X and Y if contains an arrow into X.
Note that blocking all backdoor paths between two nodes eliminates confounding bias (Pearl, 2000).
Theorem 1. Let G = (VI,E)) be an FTCG. Under Assumptions 1, 2, 3, 4, and given perfect conditional independence information aboul all pairs of variables in Vi, any algorithm in the NBCB class relurns the correct WCG or the correct ECG compatible with GS.
Proof. This proof is similar to the proof of Theorem 4 in Assaad et al. (2021) for NBCBacyclic Given the Assumption 4 and causal sufficiency and assuming NB1 is consistent with Assumption 4, NB1 would infer the correct causal order â. Given the causal order átt and temporal priority, we can orient all edges in a fully connected graph, which represents a super graph that contains the true graph. Given Assumptions 1, 2, 3, 5 and assuming that the constraint- based algorithm on which CB1' is based on is sound and complete, we do not consider the causal order, CB1 would prune all unncccssary edges by removing edges between two nodes that are conditionally independent given a subset. S adjacent to one of these two nodes and yield the correct skeleton. Given the causal order At the subset S can be reduced by containing only parents (instead of adjacencies). Thus, again by Assumptions 1,2, 3, removing all edges between the conditionally independent nodes, the only edges that will be left with are causal, and so the graph would be correct.
]
Proposition 1 (Violation of Assumption 3). Under Assumptions 1, 2, 5, given that the SCM is restrictive additive noise model (Peters et al., 2014), and given a correct causal order between instantaneous nodes, the NBCB class would give a WCG or an ECG such that, for each pair of nodes X₁, and Yt, one of the following possibilities holds true:
(1) The causal relationship between N., and Y, is correctly identified.
(2) X and Yt are not adjacent in the inferred groph, but they are adjacent in the true graph.
(3) X and Y, are adjacent in the inferred graph, but they are not adjacent in the true graph.
Proof. Given that the noise-based algorithm on which the NB1 step is based is correct, the NB1 step would give the correct causal order. Thus, having correct causal order for the instantaneous nodes and using orientation by time, the NB1 step would give the fully connected oriented graph, such that each edge that is present in the true graph is correctly oriented. The second step involves the CB1' step for pruning the edges. Since we consider that adjacency laithfulness is violated, we can have one of the following cases:
If a pair of nodes X,- and Y, is adjacent in the true graph there are two possible cases: (a) there exist set S such that X,-JLY, S. In this case, CB1' would erroneously remove the edge between X,, and Y, in the inferred graph and we obtain case (2) in the proposition
(b) there exists no set S such that X S, in this case, the CB1' would keep this edge and orientation of this edge is correct (given step NB1), this edge corresponds to correctly inferred causal relationship case (1)
If a pair of nodes X₃* and Y, is not adjacent in the true graph but they are connected by an active path u = (Xe,, Viz... . .V,_l Yi) of size n > 2. Suppose that due to violation of adjacency
faithfulness, the step CB1' removes the edge X₁- - V and the edge ve_ - Y,- If n = 3, then
27

---

Published in Transactions on Machine Learning Research (05/2024)
CB1' will never test if LY, S, such that V2 E & therefore it will not remove the edge between Xş. and Y the inferred graph. If n > 3 and CB1' removes all possible edges between X₁- and each node in (Vg..... ) and all possible edges between Y, and each node in (V2,,... V in the inferred graph (due to some specific configuration of the parameters that violates faithfulness but not adjacency faithfulness). Then, in this case, CB1' will never test if 1L, S, such that (V2 VV ns = graph.
n
therefore it will not remove the edge between X₁, and Y in the inferred
Theorem 2. Let G -VI, be an FTCG. Under Assumptions 1, 2, 4, and given perfect conditional independence information aboul all pairs of variables in V!, any algorithm in the CBNB class relurns the correct WCG or the correct ECG compatible with GS.
Proof. Without any given causal order, CB1 uses the first two steps of the constraint-based algorithm (omitting the orientation step). Using the full constraint-base algorithm under Assumptions 1, 2 and 3, we obtain correct partially complete partially oriented WCG or ECG 9 i.e. correct skeleton, all instantaneous relations are not oriented and all laggod relations are oriented. So, having 9*, what is left prove is that applying NB1' the nodes that belong to each of undirected cycle group C given the past parents Pag. (L.)We Ve is free of confounding bias.
To obtain the correct causal order between nodes 4, we need to verify that the subgraph of ÿ containing the nodes Il, U Paç. (Ie) (which is by definition acyclic) for every two adjacent nodes X,, Y, E 1l, there exists C [Xx, Y2] U Pag. (I,, such that blocks all backdoor paths between X, and Y, (if there is no edge between nodes X, and Yz, then there is no orientation to be determined by NB1).. Suppose X, Y, in the true graph (but in the output of CB1 this edge is unoriented) and there exists some active backdoor path u between X, and Y,, we consider two cases:
(a) Suppose all nodes in path belong to Ve By definition of an undirected cycle group C, all nodes in also in L,, which means that the common cause (common ancestor) the path is also in I, i.e., causal sufficiency is satisfied. This means, that u can be blocked by a node in L. Thus there exists $ C (T,,,, Y1 such that all backdoor paths between X, and Y, are blocked.
(b) Suppose that some nodes in u belong to V. In this case, conditioning on Pag. (It) blocks since Pag. (Te) are the parents of Tr and none of the nodes in Pag. (Te) are colliders of any two nodes in It. Thus all backdoor paths between X, and Y, passing by V/,W,, can blocked by Pag. (Il) and all the backdoor paths that are left are the ones discussed in (a).
Proposition 2 (Violation of Assumption 4). Under Assumptions 1, 2, 3, 5 and given perfect conditional independence informalion about all pairs of variables, CBNB is guaranleed to find the correct skeleton of the WCG the ECG.
Proof. Given that the CB algorithm used for the CBNB method is correct under Assumptions 1 and 2, the result of the first step CB1 would give the correct skeleton under the Assumption 3.
For example, the PCMCI+ method is used for the CBNB method, then the correctness of the skeleton comes from Theorem in Runge (2020). In case when CB1 is based on PCGCE algorithm, the correctness of the skeleton shown in Theorem in Assaad al. (2022c).
28

---

Published in Transactions on Machine Learning Research (05/2024)
B Pseudo-code algorithms
In our experimental section, we used an NB1 and an NB1' steps based on the VarLiNGAM algorithm (NB1 in NBCB-w w and NBCB-e and NB1' in CBNB-w w and CBNB-e) and we used respectively CB1 and CB1' steps based on the PCMCT+ algorithm (CB1 in CBNB-w and CB1' in NBCB-w) and on the PCGCE algorithm (CB1 in CBNB-c and CB1' in NBCB-e). Since NB1' and CB' steps require more modifications compared to NB1 and CB1 steps starting from the initial methods, in the following, we provide the pseudo-codes of each NB' and CB' steps that we used. But first, we start by briefly recalling VarLiNGAM, PCMCI+, and PCGCE algorithms which all assume causal sufficiency (Assumption 1) while pointing out either their NB1 or CB1 step.
VarLiNGAM (Hyvärinen et al., 2008) is noise-based causal discovery algorithm for time series data that constructs a WCG. First, it estimates a classic autoregressive model for the data using any conventional implementation of a least-squares method. It then computes the residuals and then performs the LINGAM analysis (Shimizu et al., 2006; 2011) on the residuals. Note that the LINGAM analysis can be either done using the ICALiNGAM (Shimizu et al., 2006) or DirectLiNGAM (Shimizu et al., 2011), in this work, we use DiMM This step, which we refer to as NB1, gives the causal order and the estimate of the instantaneous causal effects. After that, computes the estimates of lagged causal effects. Finally, it estimates redundant directed edges to find the underlying WCG.
PCMCI (Runge, 2020) is constraint-based causal discovery algorithm for time series data that constructs WCG. First, the PC1 lagged phase infers a superset of the lagged parents together with the parents of instantancous ancestors. Next, the MCI instantancous phase starts with links found in the previous stop and all possible instantaneous links, then il conducts momentary conditional independence (MCT) with a modified conditioning set learned in the previous step to increase detection power. This step, which we refer to as CB1, gives partially oriented graph where lagged relations are oriented and where instantaneous are non-oriented. Finally, it orients edges using the same rules used in the PC-algorithm (Spirtes et al., 2000, Meek, 1995).
Similarly, PCGCE (Assaad et al., 2022c) is also a constraint-based causal discovery algorithm for time series data, but that constructs an ECG without passing by a WCG. It also consists of two steps. First, it searches for the skeleton of the FCG using procedure similar to the PC-algorithm that is order-independent by using conditional independence test between either two nodes in the present slice or one node in the present slice and one node in the past slice, which can be muliidinensional. Similarly to the case of PCMCI+, this step, which we refer to CBI, gives partially oriented graph where lagged relations are oriented and where instantancous are non-oriented. Then it orients edges using the same rules used in the PC-algorithm (Spirtes et al., 2000, Meek, 1995).
In the following, we present the pseudo-codes of NB1' based on VarLiNGAM, CB1' based on PCMCI+ and CB1' basod on PCGCE. We colour in orange the parts that are different from the initial algorithms. Remark that the orange colour indicates that the correspouding parts are added or modified compared to the initial algorithms, but they do not indicate parts of the initial algorithms that were deleted.
B.1 NB1' based on VarLiNGAM (Algorithm 3)
The NB1' step based VarLiNGAM is almost identical to the NB1 step based on VarLINGAM. As NB1, NB1' starts by computing the residuals of all instantaneous nodes by regressing them on their past. However, unlike NB1, NB1' focuses only on subset of instantaneous nodes 1, S V,, Note that also unlike NB1, NB1 takes as input a partially oriented graph 9" (the output of CB1 step which has the correct skeleton) and that I, J Pag. (I,) should satisfy causal sufficiency. By construction, causal sufficiency satisfied when I, is an undirocted cycle group as defined in Definition 6. The pseudo-code of NB1' is provided Algorithm 3.
B.2 CB1' based on PCMCI+ (Algorithm 4)
CB1 and CB1' based on the PCMCI algorithm use conditional independence test CI() that returns at the same time the p-value and the statistic of the test. The main differences between the CB1' and the CB1 step
29

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm 3: NB1' based on VarLiNGAM (parts in orange are different from the initial algorithms) Input: A multivariate time scries, a maximal temporal lag 7 significance threshold a, an independence measure 10, the output of the CB1 step O (partially oriented), and instantancous nodes of interest C Ve
Result: G (fully oriented)
if G is an ECG then
Construct WCG 9= (IE V (Ve-7 V.)) s.t. VX2-
- E then AA E {I,-.,, ,7, Xx- E E and VX,, Y v, if X, + Y, Xx Y E then X₁ Yn,
X + Y2 E E";
else
9" ;
for Y, E 1, do Estimate a classic autoregrossive model for the data
Y Σ
anyt Xt + C/
X1 Xi-zEPaga (1)
using any conventional implementation of a least-squares method. Note that here é 0, so is really a classic AR model; Compute the residuals, that is, estimates of c/'
eV = Yv
Σ
DzgeXi-t
X. (EPagu((e)
Initialize a bijective mapping function m
= 1;
Initialize a list. S containing all nodes in ll;
while size(3) > 1 do Initialize an empty list H:;
for X2 E S do for Y, (X,) do Perform least squares regressions of En on E and compute the residuals:
e = Cy cov(Er E var(E?)
Estimate the dependence between the total residuals and X
e(
Append to the end of H;
Find the node X, corresponding éे that most independent of its residuals in H:: =(x,) = i;
i=i+l;
Remove X₂ from S;
T (X,)) = i where X, is the remaining instantaneous node in 8;
Orient 8 s.t. VX, Et, X. + Y e E+ if =(X)) +(Y);;
30

---

Published in Transactions on Machine Learning Research (05/2024)
based PCMCI* is that CB1' takes causal order as imput, and therefore, it starts with fully-oriented graph, in addition in the MCT instantaneous phase, it conditions only using parents (PCMCT+ condition also on instantaneous adjacencies).
Algorithm 4: CB1' based on PCMCI* (parts in orange are different from the initial algorithms) Input: A multivariate time scries, a maximal temporal lag y and a significance threshold o, a conditional independence test CI(), and a causal order
Result: 9 (WCG)
Construct an fully-connected WCG 9" = (EE", V (Ve-yy' v.)) s.t.
VX2- E (Ve-) Ve-1h,Y V Xe- Y E" and VX,, Y2 Ve s.t. X * X - Y E" if
T(x)) < <Y));
for Y, V, do
Initialize BY) V
Initialize m / (Xi- X,) oa VX, & Be(Y));
n ==
while _x2_ E (Y,) s.t. size (Y)) 2 do
for Xt- E y V. s.t. size (Y.)) 2 do
= first n nodes in BY))):
p, = Cr(X,-1, Y, $);
1 (X, Yi) min(h), uii (X._;, Ki);
if p> then
I mark Xe-e for removal
vX,-e marked for removal, remove X Y₁ from E"; Sort (Y,) by puin (X.-(X Yy) from largest to smallest; n= 1;
Initialize Tuin Txin(X, V,) = x VX B((Y.);
n = 0:
while 3X - Y, E E" V
s.l. size Page (Yr VA(X-))) 2 n do
for X Y4 E E" V s.t. Paz- (Yr) n (ONA 2 do
while -x,- Y, E E and not all'S E Page (Vi ( with size(S) = n have been
considered do for $ E Page VV)X-XX s.t. size = do
h= CI X,-el (x( (X.
m (X,-,, Yi) min(m/) m (Xe-e, Y.));
if p a then Remove X + Y, from Ey or X Y, from E";
n= n n==+1 11;
Sort Page N)nV, by 7min (X,-e, Yg) from largest smallest;
B.3 CB1' based on PCGCE (Algorithm 5)
CB1 and CB1' based on the PCGCE algorithu use conditional independence test CI() that returns either the v-vuuue the test or the statistic without computing the p-value. The main difference between the CB1' and the CB1 stop based on the PCGCE algorithim is that CB1' takes causal order as input, and therefore, it starts with a fully-oriented graph and in addition, conditions only using parents (PCGCE condition on adjacencies).
31

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm 5: CB1' based PCGCE (parts in orange different from the initial algorithms) Input: A multivariate time series, a maximal temporal lag y and a significance threshold a; a conditional independence test CT(, and a causal order π
Result: 9e (ECG)
Construct an fully-connected ECG g E V (V-,, s.t. VXI_ Vo, X, - +YEB and vX,, Y, e Ve s.t. X + Y,, X2 Y1 E if (Xi) <X)) n= 0;
while =x2- V2 E E. vl+ E [1,1-} s.1. size( Page (Vi))(X4,)) 2 n do
Initialize I'' and III as empty lists;
for X1. - Y E ES vi* E {1,1-} s.l. size( PPge (Xx)
do while _.,. - E and not all S E Pag. (X) (XX,} with size(S) = n have been considered do
for $ c Pag. (Y)) (X,+} s.t. size(S) = n do
-, (X,,, Ye 18)
Save (X Y, S) in D and in H
Sort ID and H by Hi from smallest to largest; for X Yr, E DD s.t. S Pag. (Y) do
P. - CI(X,., |S);
if p>p< a then Remove X Y, from E Xx, Yt from E";
n 1;
C
Experimental setup
Time series in monitoring systems are not always exactly aligned together and come in different sampling rates as the timestamps depond on when the data was collected. the following, we present two pre- processing strategies that we considered for aligning time series:
Time series are analyzed in terms of sampling rates and the lowest one is chosen. Afterwards, all the time series are re-sampled according to this lowest sampling rate with the closest value to the timestamp taken as the new value. Upon re-sampling, missing values can be clearly observed. If missing values are detected, they are filled using simple linear interpolation of Pandas data frames
Strategy 1:
Strategy 2: Each raw value 2; couverted into integral value 8; at each point as follows: 8: = + s;-1. Then all time series are re-sampled such that each re-sampled value 2y at every n (the lowest sampling rate) steps is calculated as follows: T3 = 9-- is the time that is after the corresponding time to Zz.
4-44 The time tę (of value si)
Links to datasets
Temperature. Available at http://wbbdar.uuuuiiee... mpg aegebigggnngggee/ccuueeeeeee///
Veilleux. Available at
Diary. Available at http://future.att eds.
Ingestion mini. Available at http:///eew.s.l00o....hhhhh//hth
easyvista httpp/aaa.aaeeaaaatt//////aeeeee ETDommantts///aa/y/PP..ooooggogr
32

---

Published in Transactions on Machine Learning Research (05/2024)
Web. Available
Antivirus. Available
at
E
Additional experiments
In Table we provide F1 score on the adjacencies. In contrast to Table the main texl, this Table shows the performance of the algorithms on skeleton recovery which allows to illustrate the robustness of CBNB class to Assumption 4.
Table 6: Results obtained on the simulated data of Section 5.2 for the different structures with 1000 obser- vations with non-Gaussian noise (top panel) and with Gaussian noise (bottom panel). We report the mean and the standard deviation of the F1 score adjacencies. The best results are in bluc bold and the second best results are in green bold.
Diamond
Cyclic Diamond
Unf. Diamond
Adj. Unf. Diamond
Non-Gaussian noise
NBCB-w w
0.95 + 0.01
0.95 + 0.01
0.94 + 0.01
0.88 0.01
CBNB-w
0.95 1.01
0.96 0.01
0.95 + 0.01
0.88 = 0.01
NBCB-e
0.00
0.85 0.01
0.97 + 0.01
0.87 = 0.01
CBNB-e
0.01
0.86
0.97 0.01
0.87 = 0.01
GCMVL
0.01
0.00
0.07
0.06 + 0.02
PCMCI+
0.95
0.00
0.88 = 0.01
PCGCE
0.85
0.00
0.97
0.87 0.01
Dynotears
0.00
0.0
0.0
0.0
VarLiNGAM
0.99 0.01
0.97 + 0.01
0.98 0.01
0.87 0.01
Gaussian noise
NBCB-w
0.93
0.93 + 0.01
0.90 + 0.01
0.87 0.01
CBNB-w
0.96
0.96 0.01
0.94 + 0.01
0.87 = 0.01
NBCB-e
0.00
0.00
0.93 + 0.01
0.85 = 0.01
CBNB-e
0.85 0.01
0.01
0.97 + 0.01
0.87 = 0.01
GCMVL
0.00
0.00
0.02
0.03 0.01
PCMCI+
0.96
0.01
0.94
0.87 0.01
PCGCE
0.85
0.01
0.97
0.87 0.01
Dynotears
0.05
0.0
0.0
0.0
VarLiNGAM
0.91 0.01
0.92
0.00
0.84+00.0
33


Reviews:
[{"review_id": "nMf2z8PxTL", "reviewer": "Reviewer_FAfh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "---Strengths\n\nThe paper is well written. It contains a good literature review. I appreciate the authors’effort to discuss all\nthe necessary theoretical points that made it easy to understand their approach. Also, the plots are quite useful to\nunderstand the results.\n\nWhen Assumption 3 (Adjacency Faithfulness) is violated, the NBCB class of algorithms can still obtain valid\ncausal information. \n\nWhen Assumption 4 (Identifiable Functional Model) is violated, the CBNB class of algorithms\ncan guarantee that the learned skeleton of the WCG or the ECG is accurate. \n\nExperiments show that this algorithm has a certain degree of robustness.\n\n---Weaknesses\n\nWhen Assumptions 3 (Adjacency Faithfulness) and 4 (Identifiable Functional Model) are violated at the\nsame time, the method proposed in this paper is not reliable. The algorithm’s robustness in this paper is limited,\nand it would be meaningful if it could be expanded to be stronger.\n\nIf the authors give an example of a situation where the faithfulness assumption is violated but the adjacency\nfaithfulness is satisfied, then explain the situation where adjacency faithfulness is violated. It will help readers\nbetter understand the content of the paper.\n\nIn CBNB, the adjacency faithfulness assumption was used when learning the skeleton, and the V-structure\nwas learned. Why can’t it be used for orientation?\n\n- When the noise is Gaussian, the experimental results in Table 1 are not as good as in the non-Gaussian case.\nCan the author explain the reason for this phenomenon?\n\nWhy in the case of Gaussian noise in Table 1, in Diamond’s learning results, NBCB and CBNB are far behind\nPCMCI+ and GCMVL? What is the specific reason?\n\nWhat is the reason for the poor experimental results in Table 2?\n\nIf the author can add experiments comparing learning ECG and WCG, it will increase the completeness of\nthe theory in the article.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a hybrid framework for the causal of time series that combines parts of noise-based and\nconstraint-based algorithms. Within this framework, they derive two classes of algorithms, NBCB and CBNB,\nwhich they optimized to infer the causal graph from time series. The authors study theoretically to which extent\neach class of algorithms is robust against assumption violation. The authors provide extensive simulation studies\nand real data applications to illustrate the applicability of their approach and their method’s enhanced capabilities\nagainst assumption violation compared to original methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "-[Figure 4] Give more detailed reasons for Zt−1 ⊥⊥ Xt|{Xt−2, Zt−2} so that readers can better understand.\n\n-[Undirected Cycle Group] How to understand the undirected cycle group based on Wt and Ut, which is\nWt − Ut in Figure 5. This path only contains two nodes, and this path does not meet the conditions in Definition\n5 (Undirected Cycle Path): size(u) ≥ 3, so it is also The conditions in Definition 6 (Undirected Cycle Group)\nobtained based on Definition 5 are not met, that is: according to my understanding, the undirected path Wt − Ut\ndoes not belong to an undirected cycle group. In other words, is this a special undirected cycle group?\n\n-[NB$1^{\\prime}$] \"Find the causal order between instantaneous groups of nodes\n$\\mathbb{I}_t \\subseteq \\mathbb{V}_t $ \nby recursively performing regression and independence tests between the predictors and residuals (noise).\" \" Given the output of the CB1 step, CBNB searches for all undirected cyclic groups. Then for each undirected cyclic group $\\mathbb{C}$, CBNB uses NB$1^{\\prime}$ to find the causal order $\\pi$ between all the nodes belonging to undirected cyclic group $\\mathbb{C}$.\" The first sentence describes using NB$1^{\\prime}$ to find the causal order between instantaneous groups, and the second sentence describes using NB$1^{\\prime}$ to find the causal order $\\pi$ between all the nodes belonging to undirected cyclic group $\\mathbb{C}$. This is very different, and the author needs to check these descriptions.\n\n-The network in the experiment of Table 1 has too few instantaneous nodes.\n\n-It is necessary to explain the complexity of the algorithm.\n\n-  Discussion: \"In such cases, the true graph may not be fully retrieved, but it is guaranteed that if the algorithms infer\n$X \\rightarrow Y$, then in the true graph, we can be certain that \\underline{$Y \\rightarrow X$}.\"  This should be $Y \\not\\rightarrow X$, not \\underline{$Y \\rightarrow X$}.", "broader_impact_concerns": "This paper does not cover sensitive topics.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3nuN3CPlnC", "reviewer": "Reviewer_NiR4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The paper is well-structured and easy to follow. The writing is good overall, except in some sections (see below). The extensive background section helps make the work accessible even to researchers without much prior exposure to causal discovery in temporal settings. \n- The presented hybrid framework is conceptually simple and clean. The paper does a good job at keeping things simple, and not overcomplicating things. The figures are nicely made, and together with the running example, are very helpful to communicate the different steps of the method, and the newly introduced concepts. \n- Some theoretical results show the soundness of the proposed methods. The misspecification results, while limited in scope, are an interesting first step (that could be expanded).\n- The experimental section is rather extensive, considering both simulated and real data, and several well-established baselines. \n- The paper does a good job at adopting a sober scientific tone, and not overclaiming on the results, clearly emphasising that there are trade-offs and highlighting both benefits and downsides of the proposed methods. \n\n### Main Weaknesses\n- The paper does not succeed at clearly and convincingly presenting a strong argument for when and why the proposed hybrid framework is beneficial compared to pure CB or NB methods. The misspecification results are a step in this direction, but they are quite limited in scope and appear relatively straight-forward: Prop. 1 seems to follow more-or-less directly from the assumption of a given correct causal order, and similarly Prop. 2 from the assumption of a conditional independence oracle. Wouldn't the same results also hold for purely NB or CB methods? \n- In Sec. 4.2, there is an inconsistency in the definition and use of undirected cycle paths/groups: according to Defn. 5, an undirected cycle path must have length at least 3, and according to Defn. 6 an undirected cycle group consists of one or more undirected cycle paths. However, below Defn. 6, $(U_t, W_t)$ is referred to as an undirected cycle group, despite being of size 2. This inconsistency needs to be resolved. In particular, it needs to be guaranteed that each edge is a member of at least one undirected cycle group, so that all edges can be oriented by Algorithm 2. With the current Defns., it is not clear that this should be the case. \n- The literature review in Sec. 3.1 and the description of results in Sec. 5 are somewhat disorganized and not very well-written. The former should be better structured and connected to the material in Section 2, and the latter should focus more on high-level takeaways and which results are expected or surprising. Generally, the paper would benefit from grammar checking/proofreading by a native speaker as throughout, indefinite and definite articles are often missing, which hurts the flow/readability.\n- Only linear methods are considered in the experiments. While this is justified for the synthetic data which has linear ground-truth, linearity is violated for the semi-synthetic data, and most-likely for many of the real datasets. As a result, it is unclear to what extent the results on these data sets reflect differences between the methods, rather than misspecification effects. To address this, it would be good to also try a nonlinear (e.g., kernel) regression approach, or to run an ablation for linear methods applied to nonlinearly generated synthetic data (or both).\n\n### Other comments, suggestions, and more minor points\n- after Assumption 3, it would be nice to give an example or some intuition for why adjacency faithfulness is weaker than faithfulness; an example is given later in the paper that could potentially already be mentioned here.\n-  After Defn. 3: \"Remark that\" --> \"Note that\" / \"We remark that\" \n- I strongly suggest using paragraphs (empty line in latex) rather than lineskips to make the manuscript more readable. \n- In the example after Defn. 4, it may be worth noting that the order among $(U_t,X_t)$ is not determined: i.e., one could also have an order in which $\\pi(U_t)=4$ and $\\pi(X_t)=5$. The current presentation may be slightly misleading in this regard, particularly the last phrase.\n- According to  Defn. 1, the graph in Fig. 4(a) is not a WCG since the lag is only 1, is it? \n- I like the clearly stated and references assumptions. However, when referring to Assumptions at various parts throughout the paper, it would be helpful to also give the name of the assumption: e.g., \"when the *Identifiability* Assumption 4 is violated ...\" as opposed to \"when the Assumption 4 is violated ...\" --- doing this would save the reader a lot of flicking back and forth through the manuscript to look up which assumption is meant.\n-  The paper often refers to \"WCG or ECG\", but it is not entirely clear to what extent the two can be considered equivalent for all intents and purposes in the studied setting; could you perhaps add some elaboration on this to the manuscript?\n- at the bottom of page 12, penultimate line, there appears to be a typo: \"adjacent to $Y$\" --> \"adjacent to $W$\" \n- when introducing the -w and -e versions of NBCB and CBNB, it is not clear what \"w\" and \"e\" stand for; later it becomes clear that this indicates whether a WCG or ECG is learnt, but it would be helpful to clarify this directly when introducing the variants\n- What is going on with Dynotears in Table 1? How can the catastrophic performance be explained? Might this be an implementation error? (the numbers really stand out from all others)\n- in 5.3, please specify the distribution from which $o_y$ is \"randomly assigned between 0 and 1\", is it uniform? also, please explain what trophic levels are (or avoid the term altogether) \n- In the third line of p.18 there appears to be a typo: \"we can be certain that $Y\\to X$\" should probably read \"we can be certain that $Y\\not\\to X$\"\n\n\n### Summary:\n*Overall, a solid submission with somewhat limited contributions or novelty, but sound claims and no major flaws that cannot easily be fixed. Subject to minor revisions (see below), I see no objections to acceptance. However, I think that expanding on the theoretical comparison and benefits compared to non-hybrid methods, would help substantially strengthen the work.*", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents two new hybrid methods for causal discovery from time series with instantaneous effects. Both methods combine noise-based (NB) and constraint-based approache. They differ mainly in the order in which the two are applied: \n- NBCB first uses NB to learn a causal order of instantaneous effects, resulting in a fully connected and fully oriented graph; CB is then used to prune edges.\n- CBNB first uses CB to learn a partially directed graph in which only lagged edges are directed and instantaneous ones undirected; NB is then used to orient the instantaneous edges.\n\nBoth methods rely on combining standard approaches for CB and NB in the respective order, subject to minor refinements to reduce unnecessary computations:\n- In NBCB, the CB step is refined by only searching for conditioning sets among parents, rather than all adjacent nodes.\n- In CBNB, the NB step is refined by applying NB not to the set of all nodes, but separately to a partition thereof into appropriately chosen subsets (so-called \"undirected cycle groups\").\n\nIt is shown that both methods return the correct graph if all required assumptions are satisfied (Thms. 1 and 2). Further, some results are presented for partially misspecified settings:\n- For NBCB, if adjacency faithfulness is violated, then it can still be guaranteed that if $X\\to Y$ in the inferred graph, then $Y\\not\\to X$ in the true graph (Prop. 1).\n- For CBNB, if the SCM is not identifiable, adjacency in the inferred graph still implies adjacency in the true graph (Prop. 2).\n\nEmpirically, linear versions of the proposed hybrid methods are compared against Granger-, constraint-, score-, and noise-based baselines on synthetic, semi-synthetic, and real datasets. The results show that CBNB and NBCB are trade-offs between CB and NB, which may exhibit increases robustness to violations of some assumptions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the points listed under main weaknesses above. \n\nI would also appreciate adressing/responding to the more minor points (most of which are easily fixed), though these are less critical in nature for the overall evaluation.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "l2bBy9ZrVc", "reviewer": "Reviewer_AuBy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\n- generally clearly written paper, with helpful explanation and examples\n- explicit statement and discussion of assumptions\n- sufficient experimental results that show the algorithms perform well\n\n*Weaknesses:*\n- assumptions are a bit confusing\n- some imprecision/ambiguity in the technical details\n- lacking discussion on runtime", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a flexible framework for hybrid (noise- and constraint-based) causal discovery algorithms for time series, successfully combining existing methods to achieve improved performance.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "*Critical:* (in order of appearance)\n- 3rd sentence, Section 2: be more specific here and later about \"graph\"---sometimes it's important that you're talking about a simple DAG, other times it's important to have bidirected edges and self loops, etc. Clarify when you're talking about which classes of graphs.\n- It seems like Assumptions 1 and 2 are implicitly about DAGs? This should be mentioned explicitly here too instead of as a seemlingly independent assumption 5.\n- Doesn't Assumption 1 for DAGs imply Causal Sufficency?\n- The statement of Assumption 5 only mentions (uni)directed cycles, but for example Fig 2c is described as having a cycle even though it's a bidirected cycle.\n- $\\mathbb{N}^*$ in Assumption 6 is undefined?\n- Definition 2 implies you can have multigraphs with directed 2-cycles, but the example summary graphs seem to use bidirected edges instead?\n- Second sentence after Definition 2 about inferring summary graphs should be clarified---can the summary graph be directly deduced from the window causal graph, or not? Are additional assumptions only sometimes required?\n- 4th line of page 7: can you justify why you expect this? otherwise better to avoid speculation.\n- Doesn't possiblity (3) in Proposition 1 violate Assumption 1?\n- In Definition 6, what does it mean to take the intersection of two paths?\n- Why not use the cycle $Z_t$ -- $X_t$ -- $Y_t$ -- $W_t$ -- $Z_t$ instead of the the two 3-cycles over those vertices?\n- Discussion after Table 4:\n  - \"n such cases, the true graph may not be fully retrieved, but it is guaranteed that if the algorithms infer\nX → Y , then in the true graph, we can be certain that Y → X\"; But this is trivial when assuming the correct causal order as in Proposition 1.\n  - \"the true graph may not be completely retrieved, but the inferred graph’s skeleton\nwill be accurate\"; This sentence indicates $\\iff$ but the corresponding entry in Table 4 uses $\\implies$.\n\n*Suggested:* (in order of appearance)\n- paragraph spacing seems to disappear after Assumption 3 and for the rest of the paper?\n- just before Section 3.2: \"conditional independence\" instead of \"conditionally independent\"?\n- Show experimental results using nonparamteric CI tests; should only require substituting 1 or 2 lines of code and should improve performance. Maybe using nonlinear regression is similarly easy? Doing one or both of these on the real data would already be quite compelling, even if you don't generate nonlinear simulated data to apply it to.\n- After Definition 6, you use \"cycle group\" and \"cyclic group\". Is there supposed to be a distinction?\n- Second paragraph in Section 5.2: are these supposed to be superscripts or subscripts?\n- Discuss runtime of CBNB and NBCB compared to just PCMCI+ or VLiNGAM", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a novel framework that merges constraint-based and noise-based methods to learn causal graphs from observational time series comprehensively. Based on which type of method is used firstly, two classes of methods are proposed in the paper. The paper furnishes theoretical assurances for each class, contingent upon the satisfaction of all assumptions, and delineates certain properties when assumptions are violated. To substantiate the effectiveness of the framework, two algorithms from each class are rigorously tested on simulated data, realistic ecological data, and datasets sourced from various real-world applications.

The reviewers raised several concerns on the the technical details and presentation, and these concerns were well addressed in the rebuttal. The updated manuscript was recommended for acceptance by all reviewers. After reviewing the paper and tracking the review process, I am in full agreement with the recommendation made by the reviewers.
Decision: Accept (poster)