Paper deep dive
Root cause analysis via difference graph discovery from linear time-series data
Anouk Ruer, Timothée Loranchet, Daria Bystrova, Charles K. Assaad
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/24/2026, 6:13:26 AM
Summary
This paper proposes a method for root cause analysis in linear time-series data by adapting difference graph discovery algorithms (specifically tsLDiffPC and tsDCI) to the time-series setting. The approach identifies 'effect-defying' root causes, defined as variables whose causal coefficients change between a normal and an anomalous regime, by comparing Full-Time Directed Acyclic Graphs (FT-DAGs) of these two regimes. The authors provide theoretical guarantees for these adaptations and validate them on simulated data and real-world datasets from IT monitoring and intensive care.
Entities (9)
Relation Signals (8)
tsLDiffPC → isextensionof → LDiffPC
confidence 95% · We begin with the extension of LDiffPC, which we denote by tsLDiffPC.
tsDCI → isextensionof → DCI
confidence 95% · We first evaluate the proposed approaches ... adapt several methods originally introduced ... DCI
Root cause analysis → uses → difference graph discovery
confidence 95% · In this paper, we study root cause analysis in linear time-series through the lens of difference graph discovery.
tsDCI → detects → effect-defying root cause
confidence 90% · We highlight that these methods are naturally suited to detecting certain types of root causes, in particular effect-defying root causes
tsLDiffPC → detects → effect-defying root cause
confidence 90% · We highlight that these methods are naturally suited to detecting certain types of root causes, in particular effect-defying root causes
DT-DSCM → induces → FT-DAG
confidence 90% · Within each regime, the DT-DSCM induces a full-time directed acyclic graph (FT-DAG)
FT-DFG → representsdifferencebetween → normal regime
confidence 90% · A Full-Time Difference Graph (FT-DFG) ... between M^N and M^N_bar
FT-DFG → representsdifferencebetween → anomalous regime
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Root cause analysis aims to identify the mechanisms responsible for anomalies in complex dynamical systems. In this paper, we study root cause analysis in linear time-series through the lens of difference graph discovery. We focus on effect-defying root causes, corresponding to variables whose causal coefficients change between a normal and an anomalous regime. We formalize this problem using linear discrete-time dynamic structural causal models and adapt several methods originally introduced for discovering difference graphs between two populations to the time-series setting, where the two populations are replaced by a normal and an anomalous regime. We first evaluate the proposed approaches on simulated data, and then demonstrate their practical relevance on real-world datasets from IT monitoring and intensive care monitoring. Our results show how difference graph discovery can help localize causal mechanisms responsible for anomalous behavior.
Tags
Links
- Source: https://arxiv.org/abs/2608.21117v1
- Canonical: https://arxiv.org/abs/2608.21117v1
Trouble viewing inline? Open PDF directly →
Full Text
87,516 characters extracted from source content.
Expand or collapse full text
Root cause analysis via difference graph discovery from linear time-series data Anouk Ruer Affiliation: Sorbonne Université, INSERM, Institut Pierre Louis d’Epidémiologie et de Santé Publique, F75012, Paris, France Timothée Loranchet Affiliation: Sorbonne Université, INSERM, Institut Pierre Louis d’Epidémiologie et de Santé Publique, F75012, Paris, France Daria Bystrova Affiliation: Sorbonne Université, INSERM, Institut Pierre Louis d’Epidémiologie et de Santé Publique, F75012, Paris, France Charles K. Assaad Affiliation: Sorbonne Université, INSERM, Institut Pierre Louis d’Epidémiologie et de Santé Publique, F75012, Paris, France Abstract Root cause analysis aims to identify the mechanisms responsible for anomalies in complex dynamical systems. In this paper, we study root cause analysis in linear time-series through the lens of difference graph discovery. We focus on effect-defying root causes, corresponding to variables whose causal coefficients change between a normal and an anomalous regime. We formalize this problem using linear discrete-time dynamic structural causal models and adapt several methods originally introduced for discovering difference graphs between two populations to the time-series setting, where the two populations are replaced by a normal and an anomalous regime. We first evaluate the proposed approaches on simulated data, and then demonstrate their practical relevance on real-world datasets from IT monitoring and intensive care monitoring. Our results show how difference graph discovery can help localize causal mechanisms responsible for anomalous behavior. Keywords difference graphs ⋅· root cause analysis ⋅· time-series. 1 Introduction Root cause analysis is a central task in many scientific and industrial domains, where the goal is to identify the mechanisms responsible for observed changes in a system. In climate science, for instance, understanding the drivers of extreme events or long-term shifts is crucial for prediction and policy-making [9]. In IT monitoring, root cause analysis supports the diagnosis of system failures and performance degradation, enabling faster and more reliable interventions [2]. Similarly, in healthcare, identifying the causes of adverse events or changes in patient trajectories can have important clinical implications, for example in intensive care or nephrology settings [14, 11, 17, 4]. In parallel, there has been growing interest in methods that learn differences between two environments [28, 10, 18, 7, 8]. These approaches, often referred to as difference graph discovery methods, aim to identify changes in dependency or causal structures across datasets. Although they have been studied in several settings, their potential for root cause analysis remains largely unexplored. In this paper, we investigate how difference graph discovery can be leveraged for root cause analysis in a linear setting. A key limitation of existing methods is that they are mostly designed for static data, whereas many real-world systems evolve over time. We therefore extend difference graph discovery methods to the time-series setting, allowing them to capture dynamic changes in causal or dependency structures between a normal and an anomalous regime. More specifically, we extend DCI [28] and LDiffPC [7, 8], and provide theoretical guarantees for their correctness in the time-series setting. We highlight that these methods are naturally suited to detecting certain types of root causes, in particular effect-defying root causes, corresponding to variables whose causal coefficients change between a normal and an anomalous regime [2, 4]. We then empirically evaluate the proposed extensions on both simulated and real-world datasets. For the real-world evaluation, we consider a dataset from IT monitoring as well as a dataset from intensive care monitoring. These experiments assess the practical relevance of difference graph discovery for root cause analysis and illustrate its potential across different application domains. The remainder of the paper is organized as follows. Section 2 introduces the necessary preliminaries. Section 3 reviews related work. Section 4 presents the time-series extensions of the considered difference graph discovery algorithms. Section 5 discusses how these algorithms can detect effect-defying root causes. Section 6 reports experiments on simulated data and apply the proposed methods to IT monitoring and intensive care monitoring data, respectively. Finally, Section 7 discusses the results and concludes the paper. All proofs are provided in Appendix. The implementation of the extended time-series difference graph methods, together with the code used for the experiments is available at https://github.com/CIPHOD/pyCIPHOD/tree/main/reproducibility/ecmlpkddcaesar2026. 2 Background We consider multivariate time-series VV evolving according to an unknown linear discrete-time dynamic structure causal model (DT-DSCM) [22, 2], denoted by ℳM, such that ∀Yt∈V,Yt=∑Xt−ℓ∈VαXt−ℓ,YtXt−ℓ+εYt,∀ Y_t ,Y_t= _X_t- _X_t- ,Y_tX_t- + _Y_t, where αXt−ℓ,Yt≠0 _X_t- ,Y_t≠ 0 only if Xt−ℓX_t- is a direct cause of YtY_t and εYt _Y_t is an exogenous noise term. Variables with a temporal subscript, such as YtY_t or Xt−ℓX_t- , denote time-indexed endogenous variables. When referring to an entire time-series, we omit the temporal subscript and write Y or X. The DT-DSCM governs the temporal and causal dependencies among the variables in VV. The model respects temporal ordering, meaning that a variable XtX_t cannot cause Yt−ℓY_t- for any ℓ>0 >0, while allowing instantaneous relations, so that XtX_t can directly cause YtY_t. In this paper we assume that there is no unmeasured confounding, an assumption known as causal sufficiency. Assumption 1 (Causal sufficiency). All noise terms are mutually independent and each noise term can affect only one observed variable. We consider the presence of two regimes N and ¯ N, corresponding to two different conditions of the system, namely, N represents the normal regime and ¯ N represents the anomalous regime. Throughout the paper, we assume that the observations have been assigned to either the normal or the anomalous regime before applying the difference graph discovery methods. This assumption is standard in both the difference graph discovery literature, where the generating regime is assumed to be known, and the root cause analysis literature, where anomalous observations are assumed to be identified beforehand, as is the case for all methods reviewed in Section 3. In the following, we use superscripts to indicate the regime associated with a given object. For example, ℳ¯M N, αXt−ℓ,Yt¯ _X_t- ,Y_t N, and εYt¯ _Y_t N denote, respectively, the DT-DSCM in the anomalous regime, the causal coefficient from Xt−ℓX_t- to YtY_t in the anomalous regime, and the exogenous noise of YtY_t in the anomalous regime. Within each regime the underlying DT-DSCM is assumed to be causally stationary. Xt−2X_t-2Yt−2Y_t-2Zt−2Z_t-2Xt−1X_t-1Yt−1Y_t-1Zt−1Z_t-1XtX_tYtY_tZtZ_tXt+1X_t+1Yt+1Y_t+1Zt+1Z_t+1Xt+2X_t+2Yt+2Y_t+2Zt+2Z_t+2Anomalous regime ¯ NNormal regime NYtY_tYt+1Y_t+1Yt+2Y_t+2 Figure 1: FT-DAG with a regime change at time t and ℓmax=1 _max=1. The vertices highlighted in orange are affected by a change in its causal mechanism; in this example, the time-series Y is an effect-defying root cause. We consider two settings depending on how the causal mechanism of Y changes: (i) Setting R, where only the red edges are changed, and (i) Setting RB, where both the red and blue edges are changed. Note that the causal mechanism can also be changed through a lagged mechanism, such as Yt−1→ZtY_t-1→ Z_t, where Z would be the root cause. Assumption 2 (Causal stationarity). Within each regime, for each variable YtY_t, the coefficients αXt−ℓ,Yt _X_t- ,Y_t do not depend on t and the noise εYt _Y_t is identically distributed over time. In addition, we assume the existence of a finite maximal lag between causes and their effects in the system, denoted by ℓmax _ , which is much smaller than the total number of observed time points. In practice, we assume that this maximal lag is provided by domain knowledge. More generally, the domain expert may specify an upper bound on the true maximal lag, so that the chosen ℓmax _ is greater than or equal to the actual maximal lag of the system. Within each regime, the DT-DSCM induces a full-time directed acyclic graph (FT-DAG), denoted by =(V,E)G^N=(V,E^N) and ¯=(V,E¯)G N=(V,E N), where vertices correspond to time-indexed variables and edges encode direct causal relationships both within a time step and across successive time steps. In this paper, we use several standard graphical notions. For instance, a vertex Xt−ℓX_t- is a parent of YtY_t in G if Xt−ℓ→YtX_t- → Y_t in G, equivalently if αXt−ℓ,Yt≠0 _X_t- ,Y_t≠ 0. The set of parents of YtY_t is denoted by Pa(Yt,)Pa(Y_t,G). Two vertices are adjacent if they are connected by an edge in G. The skeleton of G, denoted by Skel()Skel(G), is the undirected graph obtained from G by replacing every directed edge with an undirected edge while preserving the same set of adjacencies. For illustration, Figure 1 presents FT-DAGs corresponding to a normal and an anomalous regime. In the normal regime, the system is governed by a fixed stationary DT-DSCM, whereas in the anomalous regime it is governed by another stationary DT-DSCM in which changes, relative to the normal regime, occur in the direct effects on a specific variable YtY_t. Two settings are considered in this figure. In the first one, referred to as Setting R, only the red edge from XtX_t to YtY_t is modified across regimes. In the second one, referred to as Setting RB, both the red and blue edges, from XtX_t to YtY_t and from ZtZ_t to YtY_t, are modified. These settings will serve as running examples throughout the paper to clarify the behavior of the proposed methods. Under Assumption 2, the FT-DAG of each regime is fully characterized by the relationships between variables within a window of size ℓmax+1 _ +1, as it repeats this structure throughout the regime. Henceforth, VV refers solely to variables within this window; see Appendix for more details. The main objective of this paper is to identify root causes. To relate observed anomalies to changes in the causal system, we make the following assumption. Assumption 3 (Anomalies). All anomalies observed in the anomalous regime are induced by changes in the underlying DT-DSCM between the normal regime N and the anomalous regime ¯ N. Under the above assumption, root causes are defined as variables whose changes trigger and propagate anomalies throughout the system. At the finest level, such changes occur at the micro, or time-indexed, level of the system, for instance through a change in the mechanism of a variable YtY_t. However, under stationarity, a change affecting YtY_t at the beginning of the anomalous regime may propagate throughout the rest of the regime. Therefore, for simplicity and practical interpretability, we define root causes at the macro, or time-series, level. That is, we say that the time-series Y is a root cause, rather than referring to a specific time point YtY_t. This is also consistent with many applications, where domain experts are primarily interested in identifying which process is causing the malfunctioning, rather than the exact time at which the malfunctioning first appeared. In DT-DSCMs, two types of root causes are commonly considered [4]. A macro vertex Y is called an effect-defying root cause if there exist Yt∈Y_t∈ Y and Xt−ℓ∈Pa(Yt,)X_t- (Y_t,G^N) such that the corresponding causal coefficient changes across regimes, namely αXt−ℓ,Yt≠αXt−ℓ,Yt¯.α^N_X_t- ,Y_t≠α N_X_t- ,Y_t. Similarly, Y is called a noise-defying root cause if there exists Yt∈Y_t∈ Y such that the noise distribution of YtY_t differs between regimes, that is, εYt≠dε¯Yt ^N_Y_t _d N_Y_t. In this paper, we mainly focus on effect-defying root causes. Difference graphs provide a natural tool for this task, as they aim to identify direct relationships that differ between variables across two distributions or environments. While difference graph methods have received increasing attention in the independent and identical distributed (i.i.d.) setting, mostly to characterize differences between populations [28, 10, 18, 7, 3] rather than for root cause analysis, their role in time-series root cause analysis remains largely unexplored. Here, we investigate how such methods can be used to detect effect-defying root causes in linear dynamical systems by comparing normal and anomalous regimes. In the following, we introduce difference graphs adapted to time-series and linear DT-DSCMs. Definition 1 (Full-time Difference Graph). Consider two DT-DSCMs ℳM^N and ℳ¯M N. A Full-Time Difference Graph (FT-DFG) =(V,E|−¯|)D=(V,E^|N- N|) between ℳM^N and ℳ¯M N, is a directed graph such that the set of vertices is identical to the set of endogeneous variables in ℳM^N, ℳ¯M N and the set of edges is defined as: E|−¯|=Xt−ℓ→Yt|∀(Xt−ℓ,Yt)∈V2 such that αXt−ℓ,Yt≠αXt−ℓ,Yt¯.E^|N- N|=\X_t- → Y_t|∀(X_t- ,Y_t) ^2 such that α^N_X_t- ,Y_t≠α N_X_t- ,Y_t\. In general, FT-DFGs may contain cycles [3]. However, to simplify the problem, we assume in this paper that the FT-DFG is acyclic. This assumption is commonly adopted by algorithms [28, 10, 18, 7] that aim to fully or partially recover FT-DFGs from data. Xt−1X_t-1Yt−1Y_t-1Zt−1Z_t-1XtX_tYtY_tZtZ_t Figure 2: FT-DFGs corresponding to the FT-DAG in Figure 1. The left panel shows the FT-DFG for Setting R, where only the red edges in Figure 1 are changed. The right panel shows the FT-DFG for Setting RB, where both the red and blue edges in Figure 1 are changed. Xt−1X_t-1Yt−1Y_t-1Zt−1Z_t-1XtX_tYtY_tZtZ_t Assumption 4 (Common topological ordering). The graphs G^N and ¯G N share a common topological ordering. That is, there exists a mapping π:V→1,…,|V|π:V→\1,…,|V|\ such that π is a topological ordering of both G^N and ¯G N, i.e., for every directed edge Xt→YtX_t→ Y_t in either graph, π(Xt)<π(Yt)π(X_t)<π(Y_t). Figure 2 illustrates the FT-DFGs associated with the two settings, R and RB, from Figure 1. 3 Related Work Existing root-cause analysis methods either rely on a predefined causal graph [5, 16, 2, 4] or first estimate causal relations from data [27, 24, 25, 1, 23]. Among the latter, MicroCause [20] combines PCMCI [24] with a random-walk procedure, RCD [12] uses a regime indicator, and T-RCA [29] combines a learned graph with anomaly timing. There exists also approaches that focus on explaining one-point anomalies or outliers [6, 21, 26] bur we consider those to be beyond the scope of this paper. Here we focus on collective anomalies and assume having access to samples from normal and anomalous regimes. Our work builds on difference-graph discovery, which directly estimates how causal mechanisms vary across environments. In particular, we focus on methods that use equality tests to infer the FT-DFG. • LDiffPC [7, 8] is an algorithm for discovering a partially oriented graph in linear non-dynamic structural causal models. It recovers the skeleton of the graph by testing equality of regression coefficients across environments and then orients edges using collider detection and Meek [19] propagation rules. • DCI [28] is also designed to discover a partially oriented graph in linear non-dynamic structural causal models. It recovers the skeleton using the same procedure as LDiffPC. However, its orientation step differs: instead of relying on separation sets and orientation rules, DCI orients edges by exploiting changes in residual variances across environments. There exists also other approaches that do not use equality tests. For instance, MBGH [18] relies on covariance differences, while iSCAN [10] identifies changed mechanisms in nonlinear additive-noise models through distributional invariance. More details on related works is provided in Appendix. 4 Difference graph discovery: from static to time-series In this section, we adapt existing difference graph discovery methods to the time-series setting. The methods considered here do not return a fully oriented FT-DFG, but rather a partially oriented graph. We denote the output of such methods by ^=(V,E^,E^−) D=(V, E, E^-), where VV is the set of vertices, E E is the set of directed edges, and E^− E^- is the set of undirected edges. In the following, σYt _Y_t denotes the standard deviation of the noise term εYt _Y_t. For any conditioning set SS, βXt−ℓ,Yt|Sβ^N_X_t- ,Y_t denotes the coefficient of Xt−ℓX_t- , and σXt−ℓ,Yt|Sσ^N_X_t- ,Y_t denotes the residual standard deviation, in the regression of YtY_t on Xt−ℓ∪S\X_t- \ in the normal regime. Similarly, βXt−ℓ,Yt|S¯β N_X_t- ,Y_t and σXt−ℓ,Yt|S¯σ N_X_t- ,Y_t denote the corresponding coefficient and residual standard deviation in the anomalous regime. Xt−1X_t-1Yt−1Y_t-1Zt−1Z_t-1XtX_tYtY_tZtZ_t Xt−1X_t-1Yt−1Y_t-1Zt−1Z_t-1XtX_tYtY_tZtZ_t Figure 3: FT-DFGs recovered by the considered algorithms. The left panel shows the output of tsLDiffPC in Setting R. The middle panel shows the output of tsLDiffPC2 and tsDCIPC in Setting R. Under the variance-invariance condition required by DCI, tsDCI recovers the same graph. The right panel shows the output of tsLDiffPC, tsLDiffPC2, and tsDCIPC in Setting RB; under the same condition, tsDCI recovers an identical graph.Xt−1X_t-1Yt−1Y_t-1Zt−1Z_t-1XtX_tYtY_tZtZ_t 4.1 The tsLDiffPC algorithm We begin with the extension of LDiffPC, which we denote by tsLDiffPC. tsLDiffPC proceeds in two steps. First, it estimates the FT-DFG skeleton by testing equality of regression coefficients across regimes. More specifically, tsLDiffPC starts from a complete undirected graph over VV and iteratively removes edges between pairs of vertices Xt−ℓX_t- and YtY_t whenever it finds a conditioning set S⊆V∖Xt−ℓ,YtS \X_t- ,Y_t\ such that βXt−ℓ,Yt|S=βXt−ℓ,Yt|S¯ _X_t- ,Y_t ^N= _X_t- ,Y_t N. The size of the conditioning set is increased progressively, following the PC strategy [27]. For each removed edge, the corresponding separating set SS is stored. Second, tsLDiffPC starts the orientation phase by orienting lagged edges according to the temporal order. It then orients instantaneous edges using the standard LDiffPC collider-detection rule: for any triple Xt−ℓ−Zt−YtX_t- -Z_t-Y_t such that Xt−ℓX_t- and YtY_t are not adjacent, if ZtZ_t does not belong to the separating set stored for Xt−ℓX_t- and YtY_t, the triple is oriented as Xt−ℓ→Zt←YtX_t- → Z_t← Y_t. Finally, tsLDiffPC further orients edges by iteratively applying Meek’s orientation rules until no additional orientation is possible. The pseudocode is given in Appendix. To ensure correct detection, tsDiffPC relies on the following two assumptions. Assumption 5 (Diff-adjacency-faithfulness). Let =(V,E)D=(V,E) denote an FT-DFG. If Xt−ℓ→YtX_t- → Y_t in EE then for any subset S⊆V\Xt−ℓ,YtS \X_t- ,Y_t\, βXt−ℓ,Yt|S≠βXt−ℓ,Yt|S¯β^N_X_t- ,Y_t ≠β N_X_t- ,Y_t . Assumption 6 (Diff-orientation-faithfulness). Let =(V,E)D=(V,E) denote an FT-DFG. Let (Xt−ℓ,Zt,Yt)(X_t- ,Z_t,Y_t) be a triplet of vertices such that Xt−ℓX_t- and ZtZ_t are adjacent, ZtZ_t and YtY_t are adjacent, and Xt−ℓX_t- and YtY_t are not adjacent. The following holds: • If Xt−ℓ→Zt←YtX_t- → Z_t← Y_t in D then for any subset S⊆V\Xt−ℓ,YtS \X_t- ,Y_t\ that contains ZtZ_t, βXt−ℓ,Yt|S≠βXt−ℓ,Yt|S¯β^N_X_t- ,Y_t ≠β N_X_t- ,Y_t . • Otherwise, for any subset S⊆V\Xt−ℓ,YtS \X_t- ,Y_t\ that does not contain ZtZ_t, βXt−ℓ,Yt|S≠βXt−ℓ,Yt|S¯β^N_X_t- ,Y_t ≠β N_X_t- ,Y_t . The two assumptions introduced above differ from those originally used in the work introducing LDiffPC. In [8], the analysis relies on the stronger assumption of diff-faithfulness, which establishes an exact correspondence between the equality of regression coefficients and diff-separation (a tool similar to d-separation [22] but adapted to difference graphs). The analysis also requires an additional assumption ensuring the symmetry of regression invariance. It was shown that diff-adjacency-faithfulness and diff-orientation-faithfulness are jointly implied by diff-faithfulness and the symmetry of regression invariance [8]. Here, we argue that diff-adjacency-faithfulness and diff-orientation-faithfulness are sufficient on their own to establish the correctness of the tsLDiffPC algorithm, as well as its extension to the time series setting. Further details on how Assumptions 5 and 6 relate to the assumptions used in [8] are provided in Appendix. Theorem 1 establishes the correctness of tsLDiffPC under diff-adjacency-faithfulness and the diff-orientation-faithfulness introduced above. Theorem 1. Let =(V,E)D=(V,E) be the true FT-DFG and ^=(V,E^,E^−) D=(V, E, E^-) be the output of tsLDiffPC. If Assumptions 1,2,3,4, 5 and 6 are satisfied and we are given perfect conditional equality information about all pairs of variables then Skel(^)=Skel()Skel( D)=Skel(D) and E^⊆E E . Example 1. In Setting R, only a single edge entering YtY_t is modified across regimes. Consequently, the corresponding FT-DFG contains only one changed edge, Xt→YtX_t→ Y_t, as shown in Figure 2 (left). While LDiffPC correctly identifies the adjacency, it lacks sufficient information to orient the edge, as neither temporal ordering, collider detection, nor Meek’s orientation rules apply. As a result, the edge remains unoriented in the output, shown in Figure 3 (left). In contrast, in Setting RB, two incoming edges into YtY_t are modified across regimes. The resulting FT-DFG contains an unshielded collider structure of the form Xt→Yt←ZtX_t→ Y_t← Z_t, where YtY_t is the common endpoint of the changed edges. In this case, LDiffPC exploits its collider orientation rule to orient both edges toward YtY_t (Figure 3 right). 4.2 The tsDCI algorithm The second algorithm, denoted tsDCI is a time-series extension of DCI. The tsDCI algorithm proceeds in two steps. First, it estimates the FT-DFG skeleton using the same procedure as tsLDiffPC. Lagged edges are oriented directly according to temporal order, while instantaneous edges are oriented by testing the invariance of residual variances across regimes. More precisely, tsDCI searches for a conditioning set SS such that σXt|S=σXt|S¯σ^N_X_t S=σ N_X_t S. If such a set S S exists and Yt∉SY_t∉ S, the edge is oriented as Xt→YtX_t→ Y_t; if Yt∈SY_t∈ S, it is oriented as Yt→XtY_t→ X_t. The procedure is repeated until no further orientation is possible. The pseudocode is given in Appendix. To ensure correctness, tsDCI requires, similarly to tsLDiffPC, the diff-adjacency-faithfulness assumption. But for orientation, it relies on the following assumption on residual variances, which is the temporal analogue of Assumption 4.2 in [28]. Assumption 7 (Var-orientation-faithfulness). (temporal analogue of Assumption 4.2 [28]) For any node Xt−ℓ,Yt∈VX_t- ,Y_t it holds that: • If αXt−ℓ,Yt≠αXt−ℓ,Yt¯α^N_X_t- ,Y_t≠α N_X_t- ,Y_t then for every S⊆V∖YtS \Y_t\, σYt|S≠σYt|S¯σ^N_Y_t|S≠σ N_Y_t|S and σXt−ℓ|S∪Yt≠σXt−ℓ|S∪Yt¯σ^N_X_t- |S∪\Y_t\≠σ N_X_t- |S∪\Y_t\. • If σYt≠σYt¯σ^N_Y_t≠σ N_Y_t, then σYt|S≠σYt|S¯σ^N_Y_t|S≠σ N_Y_t|S for every S⊆V∖YtS \Y_t\. Theorem 2 establishes the correctness of tsDCI under diff-adjacency-faithfulness and the residual-variance assumption introduced above. Theorem 2. Let =(V,E)D=(V,E) be the true FT-DFG and ^=(V,E^,E^−) D=(V, E, E^-) be the output of tsDCI. If Assumptions 1,2,3,4,5 and 7 are satisfied and we are given perfect conditional equality information about all pairs of variables then Skel(^)=Skel()Skel( D)=Skel(D) and E^⊆E E . Example 2. Similarly to tsLDiffPC, tsDCI recovers the adjacencies in both settings R and RB. However, unlike tsLDiffPC, tsDCI can orient certain isolated changed edges. For example in Setting R, if σYt=σYt¯ _Y_t^N= _Y_t N, then Assumption 7 guarantees the existence of a conditioning set witnessing residual-variance invariance for YtY_t. Consequently, tsDCI orients the edge toward YtY_t, thereby recovering the true FT-DFG as shown in the middel panel of Figure 3. 4.3 The tsLDiffPC2 and the tsDCIPC algorithms We also consider two augmented variants, tsLDiffPC2 and tsDCIPC. The main idea behind these algorithms is to first apply a causal discovery method to the normal data, and then leverage the inferred orientations by projecting them onto the FT-DFG. To enable this step, we require the following additional assumption. Assumption 8 (Anomalous subgraph). Let =(V,E)G^N=(V,E^N) and ¯=(V,E¯)G N=(V,E N) denote the FT-DAGs associated with the normal and anomalous regimes, respectively. It is assumed that E¯⊆EE N ^N. This assumption is common in the root cause analysis literature and is notably adopted by EasyRCA and SGRCA. An alternative would be to assume that the normal graph is a subgraph of the anomalous graph and to apply tPC to the anomalous regime instead. We focus on the former setting because anomalies are more likely to modify existing mechanisms than to create entirely new ones, and because the normal regime typically contains more observations, leading to more reliable causal discovery. The tsLDiffPC2 and tsDCIPC algorithms first run tsLDiffPC and tsDCI, respectively, to obtain a partially oriented FT-DFG. Then apply tPC [27] to the normal regime and estimate a partially oriented FT-DAG. As in the standard PC algorithm [27], tPC removes edges by testing conditional independences and subsequently orients the remaining edges using temporal order, the collider-detection rule, and Meek rules. Finally, each undirected edge in D is oriented whenever tPC provides an orientation in G^N. Since both methods rely on tPC, they additionally require the assumptions underlying tPC. Assumption 9 (Faithfulness in the normal regime). Let ℳM^N be the DT-DSCM corresponding to the normal regime, with causal graph G^N and distribution PP^N. All conditional independences in PP^N are implied by the causal Markov property associated with G^N, which states that each variable is independent of its non-descendants given its parents. Table 1 summarizes all assumptions required by each of the algorithms introduced in this paper. The soundness of tsLDiffPC2 and tsDCIPC trivially follows from the soundness of tsLDiffPC, tsDCI and tPC. Corollary 1. Let =(V,E)D=(V,E) be the true FT-DFG, ∈tsLDiffPC2,tsDCIPCA∈\tsLDiffPC^2,tsDCIPC\ and ^=(V,E^,E^−) D=( V, E, E^-) be the output of A. Under the assumptions required by A in Table 1, and given perfect conditional equality information for all pairs of variables, Skel()=Skel(^)Skel(D)=Skel( D) and E^⊆E. E E. Example 3. In Setting R, tsLDiffPC cannot orient the edge in the FT-DFG. However, tsLDiffPC2 leverages orientations learned by tPC in the normal regime. Since the corresponding FT-DAG contains a collider with non-adjacent extremities, tPC correctly orients the edge, and this orientation is subsequently transferred to the difference graph. In Setting RB, tsLDiffPC2 produces the same output as tsLDiffPC. Similarly, tsDCIPC combines residual-variance-based orientations with orientations obtained from tPC. Consequently, it correctly orients the edge in both settings. The outputs of both algorithms are shown in Figure 3 (middle) for Setting R and in Figure 3 (right) for Setting RB. Assumption tsLDiffPC tsLDiffPC2 tsDCI tsDCIPC Linearity ✓ ✓ ✓ ✓ Sufficiency (As. 1) ✓ ✓ ✓ ✓ Stationarity (As. 2) ✓ ✓ ✓ ✓ Anomalies (As. 3) ✓ ✓ ✓ ✓ Order (As. 4) ✓ ✓ ✓ ✓ D. a. faithful. (As. 5) ✓ ✓ ✓ ✓ D. o. faithful. (Ass. 6) ✓ ✓ D. v. o. faithful. (As. 7) ✓ ✓ Subgraph (As. 8) ✓ ✓ Faithful. (As. 9) ✓ ✓ Table 1: Assumptions required by each algorithm for soundness. 5 Difference graph discovery for detecting root causes Up to this point, we have not directly addressed the detection of root causes. Once the FT-DFG has been estimated, root-cause detection follows naturally. Under the assumptions of Table 1, every directed edge returned by an algorithm A corresponds to a true changed edge in the FT-DFG. Hence, any variable targeted by such an edge is a confirmed effect-defying root cause. In contrast, an undirected edge Xt−YtX_t-Y_t only implies that at least one of X or Y is a root cause; we therefore refer to (X,Y)(X,Y) as a pair of potential root causes. To formalize these recovery guarantees, define the set of certain root causes and the set of pairs of potential root causes as ^:=Y:∃Xt−ℓ∈V,Xt−ℓ→Yt∈^, C:= \Y:∃\,X_t- ,\ X_t- → Y_t∈ D \, and ^P:=(X,Y):Xt−Yt∈^. C_P:= \(X,Y):X_t-Y_t∈ D \. Corollary 2 establishes the recovery guarantees for both sets. Corollary 2. Let C denote the set of effect-defying root causes, and let C and ^P C_P be as defined above, for an algorithm ∈tsLDiffPC,tsLDiffPC2,tsDCI,tsDCIPC.A∈\tsLDiffPC,\,tsLDiffPC^2,\,tsDCI,\,tsDCIPC\. Suppose that the assumptions required by A, as specified in Table 1, are satisfied, and we are given perfect conditional equality information for all pairs of variables. Then: ^⊆ C and ∀(X,Y)∈^P∀\,(X,Y)∈ C_P, [X∈]∨[Y∈][X ] [Y ]. Furthermore among all the possible ways of selecting one variable from each pair in ^P C_P, there exists a selection ^S C_S such that ^∪^S=. C∪ C_S=C. The corollary implies that every detected root cause is a true root cause, i.e., ^⊆ C . However, not all root causes are necessarily identified with certainty, since an undirected edge only indicates that only one of its endpoints is a root cause. The second item guarantees that all such unresolved root causes are contained in the set of potential root causes ^P C_P. Example 4. In both settings R and RB, =YC=\Y\. On the left panel, tsLDiffPC only identifies potential root causes : ^=∅ C= and ^P=(X,Y) C_P=\(X,Y)\ meaning that X or Y is the root cause. In the middle panel tsLDiffPC2 and tsDCIPC directly identifies the root cause, i.e. ^P=∅ C_P= so ^=Y= C=\Y\=C. For setting RB, all four methods correctly identify the root cause, i.e. ^P=∅ C_P= and ^=Y= C=\Y\=C for tsLDiffPC, tsLDiffPC2, and for tsDCIPC and tsDCI provided that σY=σY¯ _Y^N= _Y N. 6 Experiments In this section, we evaluate the proposed algorithms on both simulated and real-world datasets. We compare tsLDiffPC, tsLDiffPC2, tsDCI, and tsDCIPC against two root cause analysis methods, namely MicroCause and RCD. We also consider naive extensions of existing graph discovery algorithms, namely tsMBGH and tsiSCAN, derived from MBGH, iSCAN, and tPCUnion, which estimates a temporal graph separately in each regime and compares direct effects of the normal and anomalous regimes that are identified using the union graph. For tsLDiffPC, tsLDiffPC2, tsDCI, and tsDCIPC, the skeletons are estimated using a linear regression coefficient equality test across regimes. Edge orientations in tsDCI and tsDCIPC are obtained through an F-test for equality of residual variances across regimes. The tPC procedure used by tsLDiffPC2 and tsDCIPC employs Fisher’s Z test for conditional independence testing. All other methods are run with their default hyperparameters. All statistical tests are performed at significance level α=0.05α=0.05, and in all algorithms, ℓmax _max is set to one. A sensitivity analysis with respect to the significance level is provided in Appendix. 6.1 Simulated data We evaluate the algorithms on simulated multivariate time-series data generated from random finite-lag causal graphs. First, a random FT-DAG is sampled with a predefined number of time-series (d∈3,5,7,9d∈\3,5,7,9\), edge probability 0.30.3 and ℓmax=1 _ =1. Edge coefficients are sampled uniformly from [0.2,0.8][0.2,0.8] with random sign. To introduce anomalies, we consider three settings. In all cases, a target vertex is selected as an effect-defying root cause, and its incoming edge coefficients are modified while keeping the graph structure unchanged. In the first setting, only one incoming edge to the target vertex is modified; in the second setting, all incoming edges of the target vertex are modified; in the third setting, all incoming edges to the target vertex are modified, and we additionally impose that the target vertex has at least two parents. This last setting allows us to focus on cases where tsLDiffPC has sufficient information to orient edges. Time series are then simulated recursively from the corresponding linear DT-DSCM with Gaussian noise. For each setting, we simulate 10 datasets. To evaluate the different algorithms, we use the F1-score defined with respect to the set of true root causes C and a set of predicted positives P, i.e., F1(,)=2|∩|||+||,F1(C,P)= 2\,|C ||C|+|P|, where two choices are considered for the set of predicted positives P: =^P= C, where only confirmed root causes are considered; =^∪^PP= C∪ C_P where both confirmed and potential root causes are considered. Figure 4 shows that, when only confirmed root causes are considered, tsDCI and tsDCIPC achieve the best overall performance in the first and second settings. In contrast, tsLDiffPC often fails to orient the detected changed edges, although tsLDiffPC2 improves its performance. In the third setting, tsLDiffPC and especially tsLDiffPC2 become competitive with the DCI-based methods. This setting is particularly favorable to tsLDiffPC, as multiple changed parents are more likely to form unshielded colliders that facilitate edge orientation. When potential root causes are also taken into account, the performance of tsLDiffPC improves in all settings, confirming that its main limitation lies in the fact that it discovers a partially oriented graph. Among the remaining methods, RCD is the most competitive baseline, whereas tsMBGH, MicroCause, tPCUnion, and especially tsiSCAN generally obtain lower F1-scores. 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesF1 (C, C)One parenttsLDiffPCtsLDiffPC2tsDCItsDCIPCtsMBGHtsiSCANMicroCauseRCDtPCUnion 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesAll parents 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesAt least 2 parents 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesF1 (C, ^∪^P C∪ C_P) 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-series 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-series Figure 4: Mean F1-score for nine methods as a function of the number of vertices across three settings. 6.2 IT monitoring We evaluate the algorithms on IT monitoring data, namely, on the Ingestion dataset, introduced in [2]. The dataset was collected with a one-minute sampling rate and contains eight time-series measured over normal and anomalous operating periods. The time-series describe different activities of the ingestion pipeline, including message preprocessing (PMDB), message routing (MDB), metric extraction (CMB), database insertion (MB), updates of recent metric values (LMB), merging with check-message information (RTMB), insertion of historical status information (GSIB), and writing data to Elasticsearch (ESB). Each value is computed by multiplying the number of messages processed by the corresponding component during a 1010-minute window by the average execution latency in that window, and then normalizing by the window length. A visualization of the time series is provided in Appendix. The dataset contains 100100 anomalous observations and 10001000 normal observations preceding the anomalous period. It was highlighted in [2] that according to system experts two time-series were identified as root causes of the anomalies. The first corresponds to PMDB; however, based on the expert knowledge discussed in [2], this time-series is not caused by any other observed time-series, making it unlikely to be an effect-defying root cause. The second corresponds to ESB, which is more plausibly an effect-defying root cause, as it was detected as such by EasyRCA using data and the available background knowledge. On this dataset, all tsLDiffPC-based and tsDCI-based algorithms inferred the same graph, shown in Appendix. From this graph we can deduce that all these algorithms detected the effect-defying root cause ESB, along with three false positives. By contrast, tsMBGH did not detect any root cause, while tPCUnion and tsiSCAN identified all time-series as root causes (except RTMB for tsiSCAN). Among the other baseline methods, RCD identified LMB, MB and PMDB, whereas MicroCause detected CMB and PMDB. Overall, the tsLDiffPC-based and tsDCI-based methods are the only approaches that consistently recover ESB. 6.3 Intensive care monitoring We illustrate the algorithms on a patient record from the MIMIC-IV Waveform Database [13], a publicly available critical care database of high-resolution physiological signals from ICU patients. Nine variables are retained: mean arterial blood pressure (ABPm), mean pulmonary arterial pressure (PAPm), mean umbilical arterial pressure (UAPm), heart rate (HR), ST-segment deviation on leads V and I (ST-V, ST-I), central venous pressure (CVPm), respiratory rate (R), and oxygen saturation (SpO2). Since the raw signals are irregularly sampled with missing values, all variables are first aligned onto a common time grid via linear interpolation. Regime change detection is performed on ST-V using the PELT algorithm [15] with an MBIC penalty, yielding a single changepoint. A symmetric window of 10 00010\,000 observations around this changepoint defines two temporal segments. For consistency with our notation, we refer to the earlier segment as the normal regime and to the later segment as the anomalous regime; these labels indicate temporal order only, not clinical status. A visualization of the time series is provided in Appendix. The estimated FT-DFGs are shown in Appendix. The tsLDiffPC-based methods identify the same set of candidate root causes, namely R, HR, PAPm, ABPm and CVPm. The tsDCI-based methods yield a similar result, but leave an ambiguity between PAPm and CVPm due to an unresolved edge orientation. The tsiSCAN algorithm identifies R as the sole root cause. In contrast, tPCUnion detects all variables as root causes except SpO2. MicroCause identifies PAPm and CVPm as root causes, partially overlapping with the variables detected by the difference graph methods. And RCD identifies ST-V, which is not selected by any other method. Although no ground truth is available, there is an agreement among most algorithms on PAPm, CVP, and R. 7 Conclusion In this paper, we investigated how difference-graph discovery methods can be leveraged for root-cause analysis in time-series data. Our results demonstrate the potential of these methods for identifying structural changes associated with observed anomalies. The proposed approaches nevertheless rely on several assumptions regarding the underlying causal structure and data-generating processes. Moreover, their computational cost increases rapidly with both the number of variables and the maximum time lag considered, which may limit their applicability to large-scale systems. Acknowledgment This work was supported by the CIPHOD project (ANR-23-CPJ1-0212-01). References [1] C. K. Assaad, E. Devijver, and E. Gaussier (2022) Survey and evaluation of causal discovery methods for time series. J. Artif. Int. Res. 73. External Links: ISSN 1076-9757, Document Cited by: Appendix A, §G.1, §3. [2] C. K. Assaad, I. Ez-Zejjari, and L. Zan (2023) Root cause identification for collective anomalies in time series given an acyclic summary causal graph with loops. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, F. Ruiz, J. Dy, and J. van de Meent (Eds.), Proceedings of Machine Learning Research, Vol. 206, p. 8395–8404. Cited by: §G.1, §1, §1, §2, §3, §6.2, §6.2. [3] C. K. Assaad (2025) Causal reasoning in difference graphs. In Proceedings of the Fourth Conference on Causal Learning and Reasoning, M. Drton and B. Huang (Eds.), Proceedings of Machine Learning Research. Cited by: §2, §2. [4] C. Assaad (2026) Contributions to causal reasoning and root cause analysis. Habilitation à diriger des recherches, Sorbonne Université. Cited by: §G.1, §1, §1, §2, §3. [5] K. Budhathoki, D. Janzing, P. Bloebaum, and H. Ng (2021) Why did the distribution change?. In International Conference on Artificial Intelligence and Statistics, p. 1666–1674. Cited by: §G.1, §3. [6] K. Budhathoki, L. Minorics, P. Blöbaum, and D. Janzing (2022) Causal structure-based root cause analysis of outliers. In International Conference on Machine Learning, p. 2357–2369. Cited by: §G.1, §3. [7] D. Bystrova, E. Devijver, V. Manucharian, J. Mondet, and P. Mossuz (2024) Difference graph over two populations: implicit difference inference algorithm. In 9th Causal Inference Workshop at UAI 2024, Cited by: 1st item, §1, §1, §2, §2, 1st item. [8] D. Bystrova and E. Devijver (2026) Constraint-based difference graph discovery in a linear setting. Cited by: §B.1, §B.1, §B.1, §B.1, §B.2, 1st item, §1, §1, 1st item, §4.1, Proposition 1. [9] G. Camps-Valls, M. Fernández-Torres, K. Cohrs, A. Höhl, A. Castelletti, A. Pacal, C. Robin, F. Martinuzzi, I. Papoutsis, I. Prapas, J. Pérez-Aracil, K. Weigel, M. Gonzalez-Calabuig, M. Reichstein, M. Rabel, M. Giuliani, M. D. Mahecha, O. Popescu, O. J. Pellicer-Valero, S. Ouala, S. Salcedo-Sanz, S. Sippel, S. Kondylatos, T. Happé, and T. Williams (2025) Artificial intelligence for modeling and understanding extreme weather and climate events. Nature Communications 16 (1) (en). External Links: ISSN 2041-1723, Document Cited by: §1. [10] T. Chen, K. Bello, B. Aragam, and P. Ravikumar (2023) ISCAN: identifying causal mechanism shifts among nonlinear additive noise models. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36, p. 44671–44706. Cited by: §G.2, §1, §2, §2, §3. [11] A. Connell and C. Laing (2015) Acute kidney injury. Clinical medicine 15 (6), p. 581–584. Cited by: §1. [12] A. Ikram, S. Chakraborty, S. Mitra, S. Saini, S. Bagchi, and M. Kocaoglu (2022) Root cause analysis of failures in microservices through causal discovery. In Advances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Vol. 35, p. 31158–31170. Cited by: §G.1, §3. [13] A. E. W. Johnson, L. Bulgarelli, L. Shen, A. Gayles, A. Shammout, L. Lehman, T. J. Pollard, S. Horng, L. A. Celi, and R. G. Mark (2023) MIMIC-IV, a freely accessible electronic health record dataset. Scientific Data 10 (1), p. 1. External Links: Document Cited by: §6.3. [14] Kidney Disease: Improving Global Outcomes (KDIGO) Acute Kidney Injury Work Group (2012) KDIGO Clinical Practice Guideline for Acute Kidney Injury. Kidney International Supplements 2 (1), p. 1–138. External Links: Document Cited by: §1. [15] R. Killick and I. A. Eckley (2014) changepoint: an R package for changepoint analysis. Journal of Statistical Software 58 (3), p. 1–19. External Links: Document Cited by: §6.3. [16] M. Li, Z. Li, K. Yin, X. Nie, W. Zhang, K. Sui, and D. Pei (2022) Causal inference-based root cause analysis for online service systems with intervention recognition. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’22, New York, NY, USA, p. 3230–3240. External Links: ISBN 9781450393850, Document Cited by: §G.1, §3. [17] N. A. Mahmood, F. A. Chaudry, H. Azam, M. I. Ali, and M. A. Khan (2013) Frequency of hypoxic events in patients on a mechanical ventilator. International journal of critical illness and injury science 3 (2), p. 124–129. Cited by: §1. [18] V. Malik, K. Bello, A. Ghoshal, and J. Honorio (2024) Identifying causal changes between linear structural equation models. In Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, UAI ’24. Cited by: §G.2, §1, §2, §2, §3. [19] C. Meek (1995) Causal inference and causal explanation with background knowledge. In Conference on Uncertainty in Artificial Intelligence, External Links: Link Cited by: §B.2, 1st item, 1st item. [20] Y. Meng, S. Zhang, Y. Sun, R. Zhang, Z. Hu, Y. Zhang, C. Jia, Z. Wang, and D. Pei (2020) Localizing failure root causes in a microservice through causality inference. In 2020 IEEE/ACM 28th International Symposium on Quality of Service (IWQoS), Vol. , p. 1–10. External Links: Document Cited by: §G.1, §3. [21] W. R. Orchard, N. Okati, S. Garrido Mejia, P. Blöbaum, and D. Janzing (2026) Root cause analysis of outliers with missing structural knowledge. Advances in Neural Information Processing Systems 38, p. 161634–161671. Cited by: §G.1, §3. [22] J. Pearl (2009) Causality: models, reasoning and inference. 2nd edition, Cambridge University Press, USA. External Links: ISBN 052189560X Cited by: §2, §4.1. [23] N. Reiter, J. Wahl, A. Gerhardus, and J. Runge (2026) Causal inference on process graphs: Causal structure and effect identification. Bernoulli 32 (2), p. 1356 – 1382. External Links: Document Cited by: §G.1, §3. [24] J. Runge, S. Bathiany, E. Bollt, G. Camps-Valls, D. Coumou, E. Deyle, C. Glymour, M. Kretschmer, M. D. Mahecha, J. Muñoz-Marí, E. H. van Nes, J. Peters, R. Quax, M. Reichstein, M. Scheffer, B. Schölkopf, P. Spirtes, G. Sugihara, J. Sun, K. Zhang, and J. Zscheischler (2019) Inferring causation from time series in earth system sciences. Nature Communications 10 (2553). External Links: Document Cited by: §G.1, §3. [25] J. Runge (2020) Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets. In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), J. Peters and D. Sontag (Eds.), Proceedings of Machine Learning Research, Vol. 124, p. 1388–1397. Cited by: §G.1, §3. [26] D. Schkoda and D. Janzing (2026) Root cause analysis of outliers in unknown cyclic graphs. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), Note: Poster External Links: Link Cited by: §G.1, §3. [27] P. Spirtes, C. Glymour, and R. Scheines (2000) Causation, prediction, and search. 2nd edition, MIT press. External Links: Review PC algorithm Cited by: §G.1, §3, §4.1, §4.3. [28] Y. Wang, C. Squires, A. Belyaeva, and C. Uhler (2018) Direct estimation of differences in causal graphs. In Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31, p. . Cited by: §B.3, 2nd item, §1, §1, §2, §2, 2nd item, §4.2, Assumption 7, Lemma 1, Lemma 2. [29] L. Zan, C. K. Assaad, E. Devijver, E. Gaussier, and A. Aït-Bachir (2024) On the fly detection of root causes from observed data with application to it systems. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, CIKM ’24, New York, NY, USA, p. 5062–5069. External Links: ISBN 9798400704369, Document Cited by: §G.1, §3. Appendix A Details on window graphs Given causal stationarity (Assumption 2) and the existence of a maximum lag ℓmax _ , the (potentially infinite) FT-DAG can be compressed into a finite representation called a window graph [1]. For each regime, it suffices to represent only the variables between time t and time t−ℓmaxt- _ , since the FT-DAG of the regime is obtained by replicating this window in a block-wise manner throughout the entire regime. Figure 5 shows the window graph corresponding to the full-time DAG of Figure 1. It contains only time steps t and t−1t-1, since ℓmax=1 _ =1 in this case. Here, the window graph is identical across both regimes as the FT-DAG is the same, but it may in general differ between regimes. Xt−1X_t-1Yt−1Y_t-1Zt−1Z_t-1XtX_tYtY_tZtZ_t Figure 5: window graph corresponding to the FT-DAG of Figure 1, with ℓmax=1 _ =1. Only time steps t−1t-1 and t are represented. In this case, the window graph is identical across both regimes. Appendix B Proofs B.1 Diff-faithfulness vs diff-adjacency-faithfulness and diff-orientation-faithfulness This subsection assumes that the reader is familiar with the concepts introduced in [8]. Proposition 1. Assumptions in [8] ⟹ diff-adjacency-faithfulness ++ diff-orientation-faithfulness but the reverse is not true. Proof. The forward implications are proven in [8]. In the following, we prove that the reverse is not true, through two examples. First consider the underlying graphs in Figure 6, where a≠a′a≠ a . XXYYZZWWaa−a-abbbbG^NXXYYZZWWa′a −a′-a b¯G NXXYYZZWWD Figure 6: The two causal graphs and the corresponding difference graph such that b,a,a′>0b,a,a >0, and a≠a′a≠ a . Diff-adjacency faithfulness is satisfied by construction of the graph and the conditions on the coefficients. The difference graph contains an unshielded non-collider, and for both conditioning sets that do not contain X, meaning ∅ and W\W\, the coefficients differ across regimes because a2≠(a′)2a^2≠(a )^2. Thus diff-orientation-faithfulness is also satisfied. However, in both regimes, the two causal effects of X on W cancel. Consequently βX,W=βX,W¯=0 _X,W^N= _X,W N=0. Nevertheless, the paths X→Y→WX→ Y→ W and X→Z→WX→ Z→ W are active given the empty set and both contain an edge of the difference graph. Hence, the empty set does not diff-separate X from W [8]. Therefore, the assumption of diff-faithfulness [8] is violated although diff-adjacency-faithfulness and diff-orientation-faithfulness are satisfied. Now let us consider a second example, X→Y→Z→WX aY bZ cW for the normal regime, X→Y→Z→WX cY bZ aW for the anomalous regime and the resulting difference graph X→YX→ Y, Z→WZ→ W where a,b,c>0a,b,c>0 and a≠ca≠ c. Diff-orientation-faithfulness is automatically satisfied, as the 2 edges of the difference graph are disjoint. Diff-adjacency-faithfulness is also satisfied, the coefficient associated to both changed edges are different across regimes for every admissible conditioning set. But diff-faithfulness [8] fails. As the total effect of X on W in the normal and anomalous regime is βX,W=βX,W¯=abc _X,W^N= _X,W N=abc but the empty set does not diff-separate X and W, as the path X→Y→Z→WX→ Y→ Z→ W is active and has two edges in the difference graph. ∎ B.2 Proofs for tsLDiffPC In the following we present the proof of Theorem 1. Theorem 1. We start by proving the skeleton construction phase then we proceed to proving the orientation phase. Skeleton. The algorithm starts from the complete graph and removes an edge Xt−ℓ−YtX_t- -Y_t, for ℓ≥0 ≥ 0, if and only if it finds a set SS such that βXt−ℓ,Yt|S=βXt−ℓ,Yt|S¯.β^N_X_t- ,Y_t =β N_X_t- ,Y_t . (1) Every true difference edge is preserved. Suppose that Xt−ℓ−Yt∈Skel().X_t- -Y_t (D). If Xt−ℓ−Yt∈Skel()X_t- -Y_t (D) then by Assumption 5 for any subset S⊆V\Xt−ℓ,YtS \X_t- ,Y_t\, βXt−ℓ,Yt|S≠βXt−ℓ,Yt|S¯β^N_X_t- ,Y_t ≠β N_X_t- ,Y_t . Thus, given perfect conditional equality information for the pair Xt−ℓX_t- ,YtY_t tsLDiffPC would not remove an edge Xt−ℓ−YtX_t- -Y_t. Thus, Skel()⊆Skel(^).Skel(D) ( D). (2) Every non-edge is removed. Suppose that Xt−ℓ−Yt∉Skel()X_t- -Y_t (D), so Xt−ℓX_t- and YtY_t are not adjacent in D. Thus, by Assumption 5, there exists such set S⊆V\Xt−ℓ,YtS \X_t- ,Y_t\, such that βXt−ℓ,Yt|S=βXt−ℓ,Yt|S¯β^N_X_t- ,Y_t =β N_X_t- ,Y_t . If such set SS does not exist, then again, under Assumption 5, Xt−ℓX_t- and YtY_t are adjacent in D which contradicts that Xt−ℓ−Yt∉Skel()X_t- -Y_t (D). Thus, as βXt−ℓ,Yt|S=βXt−ℓ,Yt|S¯β^N_X_t- ,Y_t =β N_X_t- ,Y_t and given perfect conditional equality information about the pair Xt−ℓX_t- ,YtY_t, tsLDiffPC would remove an edge Xt−ℓ−YtX_t- -Y_t in Skel(^)Skel( D). Thus, Skel(^)⊆Skel().Skel( D) (D). Orientations. Let us now prove the correctness of the orientations. For the edges Xt−ℓ−YtX_t- -Y_t where ℓ>0 >0, the orientation is defined using temporal order Xt−ℓ→YtX_t- → Y_t. Next, we prove that tsLDiffPC correctly orients all unshielded colliders. Let us consider the following triple Xt−ℓ→Zt←YtX_t- → Z_t← Y_t with ℓ≥0 ≥ 0 in D, where Xt−ℓX_t- and YtY_t are not adjacent. As the skeleton of D coincides with the skeleton of D, then Xt−ℓX_t- and YtY_t are not adjacent, and pairs Xt−ℓX_t- , ZtZ_t and YtY_t, ZtZ_t are adjacent in D. As Xt−ℓX_t- and YtY_t are not adjacent in D, there exists set SS such that βXt−ℓ,Yt|S=βXt−ℓ,Yt|S¯β^N_X_t- ,Y_t =β N_X_t- ,Y_t . By Assumption 6 the set SS does not contain ZtZ_t. Thus, Xt−ℓ→Zt←YtX_t- → Z_t← Y_t is oriented as an unshielded collider in D by tsLDiffPC. Once all unshielded colliders and all edges that can be oriented using temporal order have been oriented, the Meek orientation rules[19] are applied, as in LDiffPC. The correctness of the application of Meek rules in D follows from Lemma 3 in [8]. ∎ B.3 Proofs for tsDCI The proof follows the same structure as the proof of Theorem 4.4 in [28], and relies on two lemmas which we now state and prove. The first lemma characterizes the nodes whose internal noise variance is invariant across regimes. Lemma 1 (temporal analogue of C.6 [28]). For any node YtY_t incident to at least one edge in D, σYt=σYt¯⟺∃S⊆V∖Yt such that σYt|S=σYt|S¯.σ^N_Y_t=σ N_Y_t V \Y_t\ such that σ^N_Y_t =σ N_Y_t . Proof. Proving the ”⇐ ” direction comes directly from the Var-Orientation Faithfulness assumption (Assumption 7). To prove the ”⇒ ”, suppose σYt=σYt¯σ^N_Y_t=σ N_Y_t and let S=Pa(Yt,)∪Pa(Yt,¯)S=Pa(Y_t,N)∪ Pa(Y_t, N). By Assumption 2, S⊆V∖YtS \Y_t\. By definition of the DT-DSCM: Yt Y_t^N =∑Xt−ℓ∈Pa(Yt,)αXt−ℓ,YtXt−ℓ+εYt = _X_t- ∈ Pa(Y_t,N)α^N_X_t- ,Y_tX_t- + ^N_Y_t =∑Xt−ℓ∈Pa(Yt,)αXt−ℓ,YtXt−ℓ+∑Xt−ℓ∈S∖Pa(Yt,)αXt−ℓ,Yt⏟=0Xt−ℓ+εYt = _X_t- ∈ Pa(Y_t,N)α^N_X_t- ,Y_tX_t- + _X_t- Pa(Y_t,N) α^N_X_t- ,Y_t_=0X_t- + ^N_Y_t =∑Xt−ℓ∈SαXt−ℓ,YtXt−ℓ+εYt, = _X_t- α^N_X_t- ,Y_tX_t- + ^N_Y_t, so the residuals of the regression of YtY_t^N on SS are εYt ^N_Y_t, and σYt|S=Var(εYt)=σYt _Y_t ^N= Var( ^N_Y_t)= _Y_t^N. The same holds for ¯ N: Yt¯ Y_t N =∑Xt−ℓ∈Pa(Yt,¯)αXt−ℓ,Yt¯Xt−ℓ+εYt¯ = _X_t- ∈ Pa(Y_t, N)α N_X_t- ,Y_tX_t- + N_Y_t =∑Xt−ℓ∈Pa(Yt,¯)αXt−ℓ,Yt¯Xt−ℓ+∑Xt−ℓ∈S∖Pa(Yt,¯)αXt−ℓ,Yt¯⏟=0Xt−ℓ+εYt¯ = _X_t- ∈ Pa(Y_t, N)α N_X_t- ,Y_tX_t- + _X_t- Pa(Y_t, N) α N_X_t- ,Y_t_=0X_t- + N_Y_t =∑Xt−ℓ∈SαXt−ℓ,Yt¯Xt−ℓ+εYt¯, = _X_t- α N_X_t- ,Y_tX_t- + N_Y_t, so σYt|S¯=Var(εYt¯)=σYt¯ _Y_t N= Var( N_Y_t)= _Y_t N. Since σYt=σYt¯σ^N_Y_t=σ N_Y_t by assumption, we conclude σYt|S=σYt|S¯ _Y_t ^N= _Y_t N. ∎ The second lemma shows that the conditioning set SS witnessing the variance invariance of YtY_t correctly encodes the edge orientations adjacent to YtY_t in D. Lemma 2 (temporal analogue of C.7 [28]). For every instantaneous edge Xt−Yt∈X_t-Y_t such that σYt=σYt¯.σ^N_Y_t\ =σ N_Y_t. it holds that, • if Xt→Yt∈X_t→ Y_t , then Xt∈SX_t for all SS s.t. σYt|S=σYt|S¯.σ^N_Y_t =σ N_Y_t . • if Yt→Xt∈Y_t→ X_t , then Xt∉SX_t for all SS s.t. σYt|S=σYt|S¯.σ^N_Y_t =σ N_Y_t . Proof. We prove both items by contradiction. Item 1: Suppose Xt→Yt∈X_t→ Y_t , then αXt,Yt≠αXt,Yt¯α^N_X_t,Y_t≠α N_X_t,Y_t. Suppose further that there exists a SS with Xt∉SX_t such that σYt|S=σYt|S¯σ^N_Y_t =σ N_Y_t . This directly contradicts the first part of Assumption 7. Item 2: Suppose Yt→Xt∈Y_t→ X_t , then αYt,Xt≠αYt,Xt¯α^N_Y_t,X_t≠α N_Y_t,X_t. Since αYt,Xt≠αYt,Xt¯α^N_Y_t,X_t≠α N_Y_t,X_t then under the Assumption 7 for S′=S∖XtS =S \X_t\, S′⊆VS , σYt|S′∪Xt≠σYt|S′∪Xt¯σ^N_Y_t ∪\X_t\≠σ N_Y_t ∪\X_t\, which contradicts the assumed equality. ∎ Theorem 2. The correctness of the skeleton construction follows directly from Theorem 1. The orientation step of the tsDCI proceeds in two stages. First, for all the edges Xt−ℓ−YtX_t- -Y_t where ℓ>0 >0, the orientation is defined using temporal order Xt−ℓ→YtX_t- → Y_t. Once all the lagged edges have been oriented, the remaining contemporaneous edges Xt−YtX_t-Y_t are oriented using the variance equality criterion introduced in DCI. We prove that these orientations are correct. By lemma 1, there exists SS such that σYt|S=σYt|S¯σ^N_Y_t =σ N_Y_t if and only if σYt=σYt¯σ^N_Y_t=σ N_Y_t. Therefore, all the nodes where the internal noise variance is unchanged will be choosen by tsDCI. In addition, it also follows from lemma 2 that for any Xt→Yt∈X_t→ Y_t , Xt∈SX_t and Yt→Xt∈Y_t→ X_t , Xt∉SX_t . Consequently, whenever the internal noise variance of a node XtX_t is invariant across regimes, tsDCI correctly orients all edges adjacent to XtX_t. It remains to show that all edges oriented in the last step are correct. This easely follows from the acyclic property of the underlying graphs. ∎ B.4 Proofs for tsLDiffPC2 and tsDCIPC Proof. (Corrolary 1) By the soundness of tsLDiffPC or tsDCI, the skeleton of the estimated difference graph is correct and every previously oriented edge is correctly oriented. It remains to prove that the additional orientations obtained from tPC are sound. Consider an edge Xt−YtX_t-Y_t that remains undirected in D and suppose that tPC orients it as Xt→YtX_t→ Y_t in G^N. By the correctness of tPC, this implies that XtX_t precedes YtY_t in the causal order of G^N. Since the two regimes share the same topological ordering by Assumption 4, the reverse orientation Yt→XtY_t→ X_t is not admissible in either regime. Hence it is also impossible in the true difference graph D. Moreover, since the skeleton of D is correct, the edge Xt−YtX_t-Y_t corresponds to a true changed edge in D. Therefore, the only admissible orientation is Xt→YtX_t→ Y_t. Thus, all additional orientations introduced by tsLDiffPC2 or tsDCIPC are sound, and the result follows. ∎ B.5 Proof for effect-defying root cause detection Proof. (Corrolary 2) By the correctness guarantees of A under the assumptions of Table 1, we have Skel(^)=Skel()andE^⊆E.Skel( D)=Skel(D) E E. Hence every directed edge returned by A is a true changed edge with the correct orientation. Let X∈^X∈ C. Then there exists Y such that Y→XY→ X is in the output of A. Since this edge is correctly oriented, Y→XY→ X is also in the true difference graph D. Therefore X is the target of a changed causal mechanism, so X∈X . Thus, ^⊆. C . Now let (X,Y)∈^P(X,Y)∈ C_P. Then X−YX-Y is an undirected edge in the output. Since the skeleton is correct, this edge corresponds to a true changed edge in D. Therefore, in the true difference graph, either X→YX→ Y or Y→XY→ X. Hence either Y or X is the target of a changed causal mechanism, and so [X∈]∨[Y∈].[X ] [Y ]. Finally, because the skeleton is fully recovered, every true changed edge is either returned as a directed edge or as an undirected edge. For each undirected edge in ^P C_P, choose the endpoint that is the target of the corresponding true directed edge in D. Let ^S C_S be the set of selected endpoints. Then all root causes not already contained in C are selected in ^S C_S, while no non-root cause is selected. Therefore, ^∪^S=. C∪ C_S=C. ∎ Appendix C Pseudocodes This section presents the pseudocode of tsLDiffPC (Algorithm 1), tsLDiffPC2 (Algorithm 3), tsDCI (Algorithm 2), tsDCIPC (Algorithm 4) and tPCUnion (Algorithm 5). In Algorithm 5, PossPa^U(Yt)PossPa_ G^U(Y_t) denotes the set of possible parents of YtY_t in the union graph, including both nodes with an incoming directed edge into YtY_t and nodes connected to YtY_t by an undirected edge. Algorithm 1 tsLDiffPC algorithm 1: Input ,¯,VP^N,P N,V 2: Initialize a fully connected undirected graph D on VV. 3: Orient every lagged edge by temporal order: if Xt−ℓ−YtX_t- -Y_t with ℓ>0 >0, orient Xt−ℓ→YtX_t- → Y_t. 4: s←0s← 0 5: while s≤|V|s≤|V| do 6: for each YtY_t in VV do 7: for each Xt−ℓ∈Adj^(Yt)X_t- ∈ Adj_ D(Y_t) do 8: ←V∖Xt−ℓ,YtP \X_t- ,Y_t\ 9: for each S⊆S such that |S|=s|S|=s do 10: if βXt−ℓ,Yt|S=βXt−ℓ,Yt|S¯β^N_X_t- ,Y_t =β N_X_t- ,Y_t then 11: Remove Xt−ℓ−YtX_t- -Y_t from D. 12: By stationarity remove all Xt−ℓ−i−Yt−iX_t- -i-Y_t-i from D 13: S=Sep(Xt−ℓ,Yt)=Sep(Yt,Xt−ℓ)S=Sep(X_t- ,Y_t)=Sep(Y_t,X_t- ). 14: break 15: end if 16: end for 17: end for 18: end for 19: s←s+1s← s+1 20: end while 21: For each triple Xt−ℓ−Yt−ZtX_t- -Y_t-Z_t, if Xt−ℓX_t- and ZtZ_t are nonadjacent and Yt∉Sep(Xt−ℓ,Zt)Y_t∉ Sep(X_t- ,Z_t) or Yt∉Sep(Zt,Xt−ℓ)Y_t∉ Sep(Z_t,X_t- ), orient Xt−ℓ→Yt←ZtX_t- → Y_t← Z_t. 22: By stationarity orient all Xt−ℓ−i→Yt−i←Zt−iX_t- -i→ Y_t-i← Z_t-i 23: repeat 24: Apply Meek rules, only when the resulting orientation respects temporal order. 25: until no additional edge can be oriented 26: return D. Algorithm 2 tsDCI algorithm 1: Input ,¯,VP^N,P N,V 2: Initialize a fully connected undirected graph D on VV. 3: Orient every lagged edge by temporal order: if Xt−ℓ−YtX_t- -Y_t with ℓ>0 >0, orient Xt−ℓ→YtX_t- → Y_t. 4: for each adjacent pair Xt−ℓ,YtX_t- ,Y_t in D do 5: for each S⊆V∖Xt−ℓ,YtS \X_t- ,Y_t\ such that S∉Descendant(Yt)S∉ Descendant(Y_t) do 6: if βXt−ℓ,Yt|S=βXt−ℓ,Yt|S¯β^N_X_t- ,Y_t =β N_X_t- ,Y_t or βYt,Xt−ℓ|S=βYt,Xt−ℓ|S¯β^N_Y_t,X_t- =β N_Y_t,X_t- then 7: Remove Xt−ℓ−YtX_t- -Y_t from D. 8: By stationarity remove all Xt−ℓ−i−Yt−iX_t- -i-Y_t-i from D 9: S=Sep(Xt−ℓ,Yt)=Sep(Yt,Xt−ℓ)S=Sep(X_t- ,Y_t)=Sep(Y_t,X_t- ). 10: break 11: end if 12: end for 13: end for 14: for each remaining undirected edge Xt−YtX_t-Y_t do 15: for S⊆V∖YtS \Y_t\ such that S∉Descendant(Yt)S∉ Descendant(Y_t) do 16: if σYt|S=σYt|S¯σ^N_Y_t =σ N_Y_t then 17: if Xt∈SX_t then 18: Orient Xt→YtX_t→ Y_t. 19: By stationarity orient all Xt−i→Yt−iX_t-i→ Y_t-i 20: else 21: Orient Yt→XtY_t→ X_t. 22: By stationarity orient all Yt−i→Xt−iY_t-i→ X_t-i 23: end if 24: break 25: end if 26: end for 27: end for 28: Orient remaining undirected edges by graph traversal: orient Xt−ℓ−YtX_t- -Y_t as Xt−ℓ→YtX_t- → Y_t whenever there exists a directed path Xt−ℓ→Z1→⋯→Zm→YtX_t- → Z_1→·s→ Z_m→ Y_t. 29: return D. Algorithm 3 tsLDiffPC2 algorithm 1: Input ,¯,VP^N,P N,V 2: Run tsLDiffPC. 3: Run tPC on P^N. 4: for each remaining undirected edge Xt−YtX_t-Y_t in D do 5: if tPC orients Xt→YtX_t→ Y_t then 6: Orient Xt−YtX_t-Y_t as Xt→YtX_t→ Y_t in D. 7: end if 8: end for 9: return D. Algorithm 4 tsDCIPC algorithm 1: Input ,¯,VP^N,P N,V 2: Run tsDCI. 3: Run tPC on P^N. 4: for each remaining undirected edge Xt−YtX_t-Y_t in D do 5: if tPC orients Xt→YtX_t→ Y_t then 6: Orient Xt−YtX_t-Y_t as Xt→YtX_t→ Y_t in D. 7: end if 8: end for 9: return D. Algorithm 5 tPCUnion algorithm 1: Input ,¯,VP^N,P N,V 2: Estimate separately the temporal graphs G^N and ^¯ G N using tPC. 3: Initialize an empty union graph ^U G^U and an empty difference graph D. 4: for each pair Xt−ℓ,YtX_t- ,Y_t adjacent in G^N or ^¯ G N do 5: if Xt−ℓX_t- and YtY_t are adjacent in only one regime then 6: if the orientation is Xt−ℓ→YtX_t- → Y_t then 7: Add Xt−ℓ→YtX_t- → Y_t to ^U G^U and D. 8: else 9: Add Xt−YtX_t-Y_t to ^U G^U and D. 10: end if 11: else 12: if both regimes imply opposite orientations then 13: Record an orientation conflict between XtX_t and YtY_t. 14: else if at least one regime orients Xt−ℓ→YtX_t- → Y_t then 15: Add Xt−ℓ→YtX_t- → Y_t to ^U G^U. 16: else 17: Add Xt−YtX_t-Y_t to ^U G^U. 18: end if 19: end if 20: end for 21: for each directed edge Xt−ℓ→YtX_t- → Y_t in ^U G^U not already in D do 22: if YtY_t is involved in an orientation conflict then 23: continue 24: end if 25: S←PossPa^U(Yt)∖Xt−ℓS← PossPa_ G^U(Y_t) \X_t- \. 26: if βXt−ℓ,Yt|S≠βXt−ℓ,Yt|S¯β^N_X_t- ,Y_t ≠β N_X_t- ,Y_t then 27: Add Xt−ℓ→YtX_t- → Y_t to D. 28: end if 29: end for 30: for each undirected edge Xt−YtX_t-Y_t in ^U G^U not already in D do 31: SY←PossPa^U(Yt)∖XtS_Y← PossPa_ G^U(Y_t) \X_t\. 32: SX←PossPa^U(Xt)∖YtS_X← PossPa_ G^U(X_t) \Y_t\. 33: if βXt,Yt|SY≠βXt,Yt|SY¯β^N_X_t,Y_t _Y≠β N_X_t,Y_t _Y or βYt,Xt|SX≠βYt,Xt|SX¯β^N_Y_t,X_t _X≠β N_Y_t,X_t _X then 34: Add Xt−YtX_t-Y_t to D. 35: end if 36: end for 37: return D. Appendix D Sensitivity analysis To assess the sensitivity of the results to the significance level, we repeat the simulations using α=0.01α=0.01 and α=0.1α=0.1. The corresponding results are reported in Figures 7 and 8, and can be compared with the main results obtained for α=0.05α=0.05 in Figure 4. Across α∈0.01,0.05,0.1α∈\0.01,0.05,0.1\, the relative ranking of the proposed methods remain largely unchanged. 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesF1 (C, C)One parenttsLDiffPCtsLDiffPC2tsDCItsDCIPCtsMBGHtsiSCANMicroCauseRCDtPCUnion 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesAll parents 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesAt least 2 parents 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesF1 (C, ^∪^P C∪ C_P) 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-series 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-series Figure 7: Mean F1-score for eight methods as a function of the number of vertices across three settings, for α=0.01α=0.01. 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesF1 (C, C)One parenttsLDiffPCtsLDiffPC2tsDCItsDCIPCtsMBGHtsiSCANMicroCauseRCDtPCUnion 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesAll parents 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesAt least 2 parents 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-seriesF1 (C, ^∪^P C∪ C_P) 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-series 222.52.5333.53.5444.54.5555.55.5666.56.5777.57.5888.58.5999.59.5000.20.20.40.40.60.60.80.811Number of time-series Figure 8: Mean F1-score for eight methods as a function of the number of vertices across three settings, for α=0.1α=0.1. Appendix E Real Data Visualization This appendix presents a visualization of the real data used for the evaluation of the algorithms. Figure 9 shows the IT monitoring time series and Figure 10 shows the ICU monitoring time series. For each figure, each time series corresponds to a variable, the normal regime is shown in blue and the abnormal regime is shown in red, and the dashed orange line represents the presumed regime change point. Figure 9: Time series of the eight bolt-level capacity metrics recorded in the IT monitoring system. The blue and red segments correspond to the Normal and Anomalous regimes respectively, as defined by the known changepoint at t=46683t=46683 (dashed orange line). Each metric is displayed on its own scale. Figure 10: Time series of the nine physiological variables recorded for the selected MIMIC-IV patient. The blue and red segments correspond to the Normal and Anomalous regimes respectively, as defined by the changepoint detected on ST-V via PELT (dashed orange line). Each variable is displayed on its own scale. Appendix F Inferred graph using real data We report here the FT-DFGs inferred by the different difference-graph-based methods on the two real-world applications. These graphical representations complement the results discussed in the main text and provide a direct comparison of the structural changes identified by each method. Figure 11 shows the graphs recovered from the IT monitoring data, while Figure 12 reports those obtained from the MIMIC-IV patient data. Isolated vertices are omitted for readability. CMBt−1CMB_t-1CMBtCMB_tPMDBt−1PMDB_t-1PMDBtPMDB_tESBtESB_tRTMBtRTMB_t Figure 11: FT-DFG discovered by tsLDiffPC/tsLDiffPC2/tsDCI/tsDCIPC on the IT monitoring data. Vertices that are not linked to anything are omitted. The graph inferred by tsiSCAN and tPCUnion is not shown because it contains many edges, while the graph inferred by tsMBGH is not shown because it is an empty graph. CVPt−1CVP_t-1RRt−1R_t-1HRt−1HR_t-1ABPt−1ABP_t-1CVPtCVP_tPAPmtPAPm_tRRtR_tHRtHR_tABPtABP_t CVPt−1CVP_t-1RRt−1R_t-1HRt−1HR_t-1ABPt−1ABP_t-1CVPtCVP_tPAPmtPAPm_tRRtR_tHRtHR_tABPtABP_t ST-Vt−1ST -V_t-1ST-IIIt−1ST -I_t-1ST-VtST -V_tST-IIItST -I_tRRtR_t Figure 12: FT-DFGs discovered by tsLDiffPC and tsLDiffPC2 (left), by tsDCI and tsDCIPC (middle) and tsISCAN (right) on the MIMIC-IV patient. Isolated vertices are omitted. The graph inferred by tPCUnion is not shown because it contains many edges, while the graph inferred by tsMBGH is not shown because it is an empty graph. Appendix G Related Work G.1 Root cause analysis Several methods have been proposed for root cause analysis in dynamical systems. Many of them require background knowledge to perform the analysis. One such method [5] attributes the change in the joint or marginal distribution across two regimes to changes in specific causal mechanisms (whether effect or noise defying) given a predefined causal graph. CIRCA [16] relies on a graph constructed from system architecture knowledge and performs regression-based hypothesis testing on anomalous data to identify deviations. It mainly focuses on noise-defying root causes. Closer to our setting, EasyRCA [2] and SGRCA [4] provide frameworks that combine data with an abstraction of the FT-DAG, called a summary causal graph. They explicitly distinguish between changes in causal effects and changes in noise distributions. EasyRCA focuses on effect-defying root causes, whereas SGRCA addresses both effect-defying and noise-defying root causes. However, these methods require a graph as input, which may not always be available. To relax this requirement, several approaches incorporate causal discovery, i.e., learning the FT-DAG or a partially oriented version from data [27, 24, 25, 1, 23]. MicroCause [20] uses PCMCI [24] (restricted version of PCMCI+ that does not allow for instantaneous relations) to learn causal relations among anomalous time series and identifies root causes via a random walk strategy based on partial correlations. However, its ability to detect the types of root causes considered here remains unclear. RCD [12] introduces a regime indicator variable and applies hierarchical causal discovery to identify variables whose distributions change across regimes. It does not distinguish between changes in causal effects and noise, assumes a fixed causal graph, and requires discrete data. Finally, T-RCA [29] defines root causes as the first variables to cross a threshold and trigger subsequent anomalies. It learns a graph from offline data using PCMCI+ and combines it with anomaly timing information to identify root causes. In a different view, several works have addressed root cause analysis of outliers [6, 21, 26]. These methods differ from those evaluated in this paper in several key aspects. First, the anomalies considered in these works are provoked by noise-defying root causes rather than as effect-defying root causes, as we focus in this paper. Second, all three methods are designed to identify the root causes from single anomalous observation, whereas our approach operates on samples from two regimes (normal and anomalous) to detect changes in causal mechanisms. G.2 Difference graph discovery Since many causal discovery methods exist to recover the causal graph from observational data, a naive approach to identifying the difference graph would consist in running a causal discovery algorithm separately on each regime and comparing the outputs to detect discrepancies. However, such an approach would only capture structural changes, i.e., edges that appear or disappear across regimes, corresponding to coefficients transitioning from zero to nonzero or vice versa. Yet the difference graph should also encode edges whose coefficients change in magnitude without inducing any structural modification. A possible solution is therefore to estimate the causal graph in each regime, construct their union graph, and compare the corresponding edge coefficients across regimes. However, this strategy can be computationally costly. To address this problem, several dedicated methods have been proposed. While they rely on different assumptions and identification strategies, they all aim to estimate a graph encoding which causal mechanisms differ across environments. In this paper, we mainly focus on methods that use equality tests to infer the FT-DFG. • LDiffPC [7, 8] is an algorithm for discovering a partially oriented graph in linear non-dynamic structural causal models. It recovers the skeleton of the graph by testing equality of regression coefficients across environments and then orients edges using collider detection and Meek [19] propagation rules. • DCI [28] is also designed to discover a partially oriented graph in linear non-dynamic structural causal models. It recovers the skeleton using the same procedure as LDiffPC. However, its orientation step differs: instead of relying on separation sets and orientation rules, DCI orients edges by exploiting changes in residual variances across environments. There exists also other approaches that do not use equality tests. For instance, MBGH [18] formulates difference graph discovery as a covariance-based estimation problem and recovers the graph through a recursive peeling procedure, while iSCAN [10] targets nonlinear additive noise models and identifies changed mechanisms through distributional invariance arguments.