Causal Discovery from Conditionally Stationary Time Series
Authors: Carles Balsells-Rodas
Xavier Sumba
Tanmayee Narendra
Ruibo Tu
Gabriele Schweikert
Hedvig Kjellstrom
Yingzhen Li
Venue: ICML 2025 poster (2025)
Keywords: causal discovery
graph neural network
time series
non-stationary
probabilistic modelling
identifiability
Primary area: probabilistic_methods->structure_learning
TL;DR: We tackle theoretical and algorithmic challenges for conditionally stationary time series.

Abstract: Causal discovery, i.e., inferring underlying causal relationships from observational data, is highly challenging for AI systems. In a time series modeling context, traditional causal discovery methods mainly consider constrained scenarios with fully observed variables and/or data from stationary time-series. We develop a causal discovery approach to handle a wide class of nonstationary time series that are _conditionally stationary_, where the nonstationary behaviour is modeled as stationarity conditioned on a set of latent state variables. Named State-Dependent Causal Inference (SDCI), our approach is able to recover the underlying causal dependencies, with provable identifiablity for the state-dependent causal structures. Empirical experiments on nonlinear particle interaction data and gene regulatory networks demonstrate SDCI's superior performance over baseline causal discovery methods. Improved results over non-causal RNNs on modeling NBA player movements demonstrate the potential of our method and motivate the use of causality-driven methods for forecasting.

Causal Discovery from Conditionally Stationary Time Series
Carles Balsells-Rodas'
Xavier Sumba' Tanmayee Narendra² Ruibo Tu
Gabriele Schweikert?
Hedvig Kjellström Yingzhen Li"
Abstract
et al., 2017). Practically, better algorithms are needed to accurately extract the causal structure from data.
Causal discovery, i.c.. inferring underlying causal relationships from observational data, is highly challenging for Al systems. a time series mod- eling context, traditional causal discovery meth- ods mainly consider constrained scenarios with fully observed variables and/or data from station- ary time-series. We develop causal discov- ery approach to handle a wide class of nonsta- tionary time series that are conditionally station- ary, where the nonstationary behaviour is mod- eled as stationarity conditioned on a set of latent state variables. Named State- Mate--eeenddet Causal Inference (SDCI), our approach is able recover the underlying causal dependencies, with prov- able identifiablity for the state-dependent causal structures. Empirical experiments on nonlinear particle interaction data and gene regulatory net- works demonstrate SDCI's superior performance over baseline causal discovery methods. Im- proved results over non-causal RNNs mod- cling NBA player movements demonstrate the potential of our method and motivate the use of causality-driven methods for forecasting.
In time series analysis, causal discovery identifies the under- lying temporal causal structure of the observed sequences. Historical approaches rely on restrictive assumption: sta- tionarity (Granger. 1969; Peters et al., 2017; Tank al., 2021; Löwe al., 2022), while real-world data is often nonstationary with potential hidden confounders. To ad- dress this issue, three major strategies have been recently proposed: (1) modelling nonstationary noise (Huang et al., 2020; Gong et al., 2023); (2) introducing time-dependent ef- feets with fixed causal structure (Huang et al., 2015; 2019); and (3) using discrete latent variables to capture structural changes over time (Saggioro al., 2020). Despite these ad- vances, causal discovery in nonstationary time series under realistic assumptions remains an open challenge.
This work addresses causal discovery for nonstationary time series based on a much relaxed assumption, conditionally stationary time series, where the dynamies of the observed system change depending on set of discrete "state" vari- ables. These causal structures can change not only during time, but also across samples (Löwe al., 2022). This assumption holds for many real-world scenarios, such as individuals whose different decisions depend on mood, past experiences, or interactions with others. The causal discov- cry task for such conditionally stationary time series poses different challenges depending on the observability and de- pendency of the states, which classify into scenarios:
1. Introduction
Deep learning has achieved profound success in vision and language modelling (Brown et al., 2020; Nichol et al., 2022). Still, it remains grand challenge for deep neural networks to perform causal discovery (Yi et al., 2020; Girdhar & Ra- manan, 2020; Sauer & Geiger, 2021), 1), which critical for interpretabilityy generalization, and robustness (Lake al., 2017; Schölkopf al., 2021). Theoretically, structure iden- tifiability is key to ensure a unique correspondence between observations and the underlying causal structures (Peters
States observed/independennt The states are observed and/or independent on observations (Fig. la). Structure identifiability can be established for both cases by Peters et al. (2013), and Balsells-Rodas et al. (2024), respectively.
States determined: The states are hidden but depend on observations directly. In Fig. 1b, the states are determined by the balls' positions (pink vs purple regions).
The states depend on historical events. E.g., in Fig. 1c, particles have state changes upon collision. Also in a football game player acts differently based on earlier actions of the others.
States recurrent:
'Imperial College London University of Dundee 'KTH Royal Institute of Technology. Correspondence to: Carles Balsells-Rodas <cb221 @imperial.ac.uk.
Proceedings of the 4rnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
We propose a novel framework to tackle both the theoretical and algorithmic challenges for causal discovery from condi-

---

Causal Discovery from Conditionally Stationary Time Scries
f
Bt+1
Independent fro an
collides
2 2 D 1 1 1 O 1
0 1 2 2
10 a 2 11 0
2 2 1 O 2 2
A1
#1
(a) States observed.
(b) States determined.
(c) States recurrent.
Figure 1: Graphical representations of the data generation processes. 2t represents the observations of time series, and 8: denotes the state variables. The states affect observations by changing the causal structure ft for different state values.
tionally stationary time series in states determined and re- current cases. Our contributions are summarised as follows, providing advances in both identifiability and estimation:
stantancous effects, and a first-order Markov property. In stationary time series, the full time graph is static across time steps. This allows us to define the summary graph g = -V, (VVE$), where V {l,..., ",....,N, N and an edge + exists in g if there an edge from æ; to x in 9 for some t < t'. The identifiability of both G and g is guaranteed under Time Series Models with Independent Noise (TiMINo; (Peters et al., 2013)). By further assuming an additive noise model (ANM), the SCM becomes:
We introduce conditional summary graph as a compact representation of the underlying causal graph structure for conditionally stationary time series. This efficiently addresses the exponential complexity of full-time graph in summarising the causal structure of time series data with nonstationary interactions between variables.
We establish identifiability for the conditional summary graph and related structural properties for conditionally stationary time series satisfying "state determined" (Fig. 1b) or "state recurrent" (Fig. Ic) assumptions.
(J) = م(: #
a 2 12 ( + E (1)
where PA (t- (t-1) 1) denotes the parents' of xz and (,1)
Pe represents independent noise. In this setting, PA (t (t-1) is constant in time and aligns with the summary graph GS.
We propose State- State-Dependen Causal Inference (SDCI) practical algorithm extract the conditional summary graphs and model state dependencies, based discrete latent variable models and graph neural networks.
2.2. Markov Switching Models
We validate SDCI on semi-synthetic data based physi- cal and biological systems, and real-world datasets. Com- pared to baselines including GNN and RNN based ap- proaches, SDCI achieves superior performance in iden- tifying the underlying nonstationary structures in gene regulatory networks; and forecasting future trajectories from observations on NBA player movements.
Markov Switching Models (MSMs; (Hamilton, 1989)) ex- tend time series modeling by introducing discrete latent variables ue E {1,... U} that condition the autoregres- sive process at each time step I. For regime-dependent time series (Saggioro et al., 2020), the full-time graph F is time-dependent, but causally stationary (Assaad et al., 2022) given the discrete latent variables uy, t {1, T). This leads defining the regime-dependent graph, which is set of graphs G P
......I
2. Background
S U} where G.I.D encodes the causal effects of æ. for ut = u. Our work utilises MSMs under the following key assumptions (ml-m3):
2.1. Causal Discovery in Stationary Time Series
Causally-driven time series often modelled using struc- tural causal models (SCM; (Pearl, 2009; Peters et al., 2017)) for describing data generation processes. Consider N se- quences of length T. denoted by æ1.r, where x; Rd denotes the features of the i-th sequence at time I; which can incorporate high-order moments, e.g velocity, acceleration. The data dependencies in a temporal SCM are structured via a causal graph, known as the full time graph, 9
(m1) Conditional first-order Markov transitions, con- trolled by u only: for any E (2....T)).
p at @1 U1tt-1)
p( ( we-1). (2)
(m2) Conditional stationarity: the transition distributions do not change during time: for any E (1,..., U} we have
'The notation (t 1) indicates that the parents of variable j are considered the previous time step.
For simplicity, we assume no hidden confounders, no in-
2

---

Causal Discovery from Conditionally Stationary Time Scries
t=
2
2
+ (9)
x (9)
2
2
(c) Conditional sum- mary graph
(a) Full time graph
(b) Regime-ddeentee graph
Figure (a) Full time graph 9 of sample considering our problem setting, (b) regime-dependerr graph, and (c) conditional summary graph g.k of the corresponding sample for K 2. We denote states using numbers (1,2) inside each element. Different colors (red and blue) denote effects caused by different states.
for any t + t', any B,y E Rdd such that
of K graphs, 9 = 1 S k I K}. where is the number of possible state values. Each summary graph 9 : {V,E E has the same vertices V = = fI....,NY N). exists in ECS if there exists such that (i) = k and x;" connects to (j) in 9
p(a, = B x- = 14-1 = u)
p(æ. B B1 = ",, 41 u).
(3)
An edge
(m3) Factorisation based on Gaussian ANM:
For simplicity, omit self-connections in Fig. 2c (black edges in Fig. 2a), where show the conditional summary graph extracted from the full time graph. For k = 1 we observe s 1, and "red edge" connects a1 and az!") placing red edge in ECS, Similar reasoning applies for GCS. Compared to summary or regime-dependent graphs (Fig. 2b). the conditional summary graph offers a compact and informative representation of state- nate-dependent causal structures. summary, the SEM for conditionally station- ary time series can be formalised as follows:
p(a,/a:-11 10-1))-,, III (a
(1) (m 12 E G) He-1 (1 1)) (4)
for any .,,... T}. where PA (t - 1) denotes the parents of variable j at time - 1, as described by G
3. State-Dependent Causal Inference (SDCI)
3.1. Conditionally Stationary Time Series
(3) JS
PA PA() (i) (t (t-1))+EE) +E( (5)
a
We focus on nonstationary time series where each time step is associated with N latent variables s; = {
(N)
This introduces the following assumption:
Each ( E {1...., K} controls the causal effects of x to future observations 11+1. In other words, the causal influences of at are dynamically modified by the state st This can be viewed as a general MSM under assumptions (m1-m3) by setting u, = (sx)) with global states KN, for some injective yp (1....,K) KJN + [I,...,U}, U). Fig. 2a exemplifies the full time graph illustrating these assumptions. Here, the causal effects vary across time as S1 # S2 * $z, leading to nonstationarity. From MSM view, we can extract a regime-dependent graph with K regimes (Fig 2b).
(m4) Multi-state dependence: The parents PA (5) (t 1) of variable j at time t are defined by gCS as:
PA (A (1- 1): { [0
j c k= 10 k
- (6)
ch CV denotes the children of variable in state k speci-
fied by gCs. To illustrate, in Fig. 2a the parents of a!
{Ø 2 2 x1
} as 2 E (c) and 2 E (3) (9)
Although the segime-dependent graph captures the general structure, it becomes inefficient it scales exponentially with N. Furthermore, summary graph (aggregating all the regimes) can be non-informative, due to inability to distinguish state-dependent effects. Instead, we define the conditional summary graph.
3.2. Amortisation of Conditional Effectss.
The conditional summary graph introduces linear scaling with K. However, indexing the SEM in Eq. (5) by 8:-1 requires KN functions. Taking inspiration from interac- tive systems (Kipf et al., 2018; Löwe et al., 2022), we pro- pose a two-stage interaction and aggregation framework, formalised as the following assumption:
Definition 3.1 (Conditional summary graph, first-order Markov setting). The conditional summary graph is a set
3

---

Causal Discovery from Conditionally Stationary Time Scries
(tw the Ve)- For observed states, define:
(0(81r(221))
1:: k.
Pel (xIrT, W[s1:T) = Pos (11T W)Pv (W), (9)
State State
xe (3)
with factorised prior on the edge labels Pe. (W)
(1)
T
I II. Pe.. (wist)) We can guide Vu through domain knowledge (e-g. sparsity). Given W Po..(W and 81:7, sequence .1. is generated as
(2)
W121
(2)
T-1 N Pe. (BLTSSIT W) = II
II Pv_ (2 20, St. W). t= j=1
(2)
(2)
( [ 82, W)
2++1 E+11 2+1
(1) (2) (3)
(1) To compute pv. (x [,,, 8t, W). the model queries edge-
types el Wifks for s k', retrieves pairwise interac- tions fa (8) xz()), and aggregates them:
Figure 3: SDCI extracts the labels of conditional effects that describe state-dependent interactions in a sample.
h (1)) =
(m5) Global function-type dependence:
The effect be- tween any pair of variables is determined by n, functional effects F = (Jo...., _/,_-1, where fo(.) = O represents the absence of an edge. Each functional effect is state- dependent, i.e., the effects from variable at time are determined by its state o;") These effects are collected in the labels of conditional effects:
c20
.(1ه
Li+1 = x( +g
>E> it
h )T) (10)
where F = [f) and g are parametrisable functions, similar to Eq. (8). 20 denotes the mean of Tt+1 which is
(z)
Gaussian distributed with covariance I² For latent states with influence from æ1,7 (determined and recurrent cases; Figs. lb, Ic), the joint distribution extends to:
W = Wi.jk E {0.................. nr 11/1
1 1 WIJK = + j i }
(7)
Pe (TI.TT S1.T, W) = Pow (W)
where Wi.i.A specifies the edge-type i + j at state k, associ- ated to variable i. In the aggregation stage, the interactions are combined using a permutation invariant function g:
II 1=1
Po. (2 W| W)pb, (s: (s S1-1a-L,).
f/2, (IL-1) = 9 x x
(
where Lg and Lg are the maximum lags. The determined case fixes I., = 0 and L,, O: and we assume the states are autonomous with shared parameters vh:
1 { fee (2 i + +1))
where -.,.400 The function 9 aggregates interac- tions to variable j. capturing complex state-dependent dy- namics. This formulation effectively reduces the exponen- tial complexity of conditionally stationary time series, and can be efficiently implemented with graph neural networks (GNNs) (Kipf et al., 2018). Furthermore, it aligns with well-established mechanisms in physical systems, such as aggregating forces from pair-wise interactions.
Ps. LL $t-
II Pv. (s)"
(x L, 8 (8)
(2) 1
1 (1I)
Inference. Building on VAE-based approaches (Kingma & Welling, 2014; Löwe et al., 2022), we introduce a vari-
ational posterior parametrised by Φ == [&w. Φz); which approximates the posterior over W, and $1. as follows:
3.3. Implementation
g (W, s1.1 (1:)) Tow (W(a (11r)(21:) (12)
We propose State- Depeedeepndd Causal Inference (SDCI), probabilistic approach infer the underlying causal struc- ture from time series. Given dataset D, each sample I1.T ~ D is driven by W, which may differ across samples. SDCI models the joint dynamics of states, edge-types, and observations (Fig. 3), and builds on graph neural networks (GNNs) and interactive systems (Kipf et al., 2018).
where Toh is factorised across edges
9au (wijk (1r)) = softmax (finnaaxx()j))))...)
Φij fo.. (mir)) E Kx", (13)
The function Φij extracts embeddings for any pair i + j that represents the dete-deeenddnt causal interaction, and the architecture of (x1.)) ) is based on (Chen et al., 2021).
Generative model. joint distribution for conditionally stationary time series is dependent on 81.7, W, and 1a: ==
See Appendix B.3 for details. In the determined case, exact
4

---

Causal Discovery from Conditionally Stationary Time Scries
inference on the states is tractable (see Appendix B.2), and set 20. ($1r((1r:)) = Pv. (S1:T/21:))
This partial identifiability definition excludes the state distri- bution, as restrictions on the state dynamics are imposed. It cannot generally be achieved under (ml-m5) without fur- ther assumptions. However, our main focus in this work is to recover state-dependent structures, and we leave state distribution identifiability for future work. Below, we list sufficient conditions for identifiability.
To. (0) ( [aa softmax($! /T), 86 = (2) ) (14)
In the recurrent case, go. (81:T (1:T) =Ii'=1 9o, (8t (21:))
is implemented via bidirectional RNN-GNN that approxi- mates smoothing (details in Appendix B.3).
(a1) Unique indexing of outgoing structure. For each state 8/-1 E [1....,K} the graph representing the direct causes of i is unique. That is, for any i (1,....N):
Objective. SDCI optimises the ELBO (Kingma & Welling, 2014) (see Appendix B.I for derivation):
logPo(#1:r) 2 -KI -KI( qo... (W|z1:))
Po... (W))
mk, k' E (1,-..,
+
c + C (19)
Σ KL qs. (51 (51(211:7) Pe. LL
81- 81-
This is stronger than the typical unique indexing assumption for mixture models (Balsells-Rodee et al., 2024), where:
+ +B (.ooWW.Lrrloos) log (21: ( w)]. (15)
s1:7,
p( 81-1 (Ki, (KI,..... ................................ kN)) #
where reparametrisation tricks (Jang et al., 2017) en- sure backpropagation for discrete samples W, 81:7 (WW, (1r((21:)) To reduce variance, we use straight- through Gumbel-softmax and fix gradients to pass through unperturbed marginals (Ahmed et al., 2023). During train- ing, Eq. (10) becomes:
p(z, -1,, = Ky].
for (k1,..... KN) + (i......''!
(a2) Unique indexing of function types. Given (ml-m5):
(a2.1): For any j E {1...., and given g(x(1) (h:--))) * j}), where h(d) = (x(()() ax(1)) for some E (O..... :Ne - 1}, the partial derivative andii is non-zero almost everywhere for any i E [I....,N]
K
(0)
(ewate)))l ( (16)
0g
k=1
c30
and we optimise & and & using mini-bate match gradient ascent.
(a2.2): Edge-types differ almost everywhere: fo == 0, and for e # d' E {0, nee - 1}, the following set has zero measure:
4. Theoretical Considerations
We provide identifiability guarantees for the labels of con- ditional effects W, driving conditionally stationary time series under assumptions (ml-m5). A detailed analysis of identifiability for regime-dependent graphs under (ml-m3) and conditional summary graphs under (ml-m4) is provided in Appendix A. We first define partial identifiability for W.
Xe,e == I E Rdd
Ba0 E IRd
(21, 22)
(20)
dx
dzi
These assumptions ensure pairwise interactions are not can- celled during aggregation, and the edge-types remain suffi- ciently distinct. For example, SDCI, naturally satisfies (a2. I) through GNN message passing. Additionally, implementing edge-type functions as analytic functions guarantees (a2.2). We now state the following identifiability result:
Definition 4.1 (Partial identifiability of conditional ef- fects). Given observations I..T and a family of models M satisfying (ml-m5), we say M is partially identifi- able with respect to the labels of conditional effects if for any P. E M, with corresponding W and W such that p(æ1T)) = p(xx1T); K = K and there exist permutations T E Sn, and g( E SK such that for any i,j E (1....,N) NN} and k E [1,...,K] K):
Theorem 4.3. Conditionally stationary time series satisfy- ing (ml-m5) are partially identifiable with respect to condi- tional effects (Def. 4.1), if they meet assumptions of unique indexing of (al) outgoing structure and (a2) function types.
WiJjk i (R)
Wiih = 0,
(17)
Wiijk = ( (k)) + W.J.k + O. Remark 4.2. Mixture models can only be identified up to permutations (Yakowitz Spragins, 1968). Contrary to previous work (Gassiat et al., 2016; Hälvä Hyvarinen, 2020; Song et al., 2024), our results do not require knowl- edge of the number of components K. Eq. (17) establishes equivalences of G.S. up to element-wise permutations (+) for outgoing edges {C() mutation equivalence in edge labels 1, 1,..., ncc.
(18)
Proof sketch. The full proof is depicted in Appendix A.5, and it can be divided into 3 major steps.
(i) Write p(a,, (.1-))) 1) as a mixture model. Under (ml- m3) and (al-a2), the regime-dependene graph is iden- tifiable up to permutation E Sx~ (Theorem A.6). Under state dependencies on I1.t-1, the key is to show that the permutation equivalence of the transi- tion distribution is preserved almost everywhere due to (al-a2), no matter the overlap on Tt-1-
((ú ). Eq. (18) ensures per-
5

---

Causal Discovery from Conditionally Stationary Time Scries
(ii) Using (m4) and (al), regime-dependent graph iden- tifiability transfers to conditional summary graph identifiability (Theorem A.7).
include constraint-based methods (Entner & Hoyer, 2010; Runge, 2018), score-based methods such DYNOTEARS (Pamfil et al., 2020) based on Dynamic Bayesian Networks (Murphy et al., 2002), and functional causal model- based methods (Shimizu et al., 2006; Zhang & Hyvärinen, 2009; Peters et al., 2014) with constrained dynamics assumptions (Peters et al., 2013). The functional causal model-based approaches also motivate the use of deep generative models for causal discovery in high-dimensions (Yu et al., 2019).
(iii) By (m5) and (al-a2), partial derivatives in the aggre- gation step reveal permutation equivalence on the edge-types (Corollary A.8).
While several prior works (Hälvä & Hyvarinen, 2020; Song et al., 2024; Balsells-Rodas et al., 2024) introduce nonsta- tionarity via regime switching, our approach offers three key advantages:
Our work focuses on modelling nonstationary time series with discrete latent variables that condition the underlying structure. It is related to Amortized Causal Discovery (ACD; Löwe et al. (2022)), which assumes stationarity and amor- tizes summary graph discovery across samples with different graphs but shared dynamics. We extend ACD by allowing the causal structure to vary according to latent state vari- ables, thus enabling conditional stationarity. When observed auxiliary variables are present, Monti et al. (2020) uses time contrastive learning (Hyvarinen & Morioka, 2016) and non- linear ICA for causal discovery; while Yao et al. (2022) establishes identifiability conditions in the presence of piece- wise stationary disturbances. Regime-dependent dynamies assume no access states Saggioro al. (2020), where Balsells-Rodas et al. (2024) proves identifiability through Markov Switching Models; and Rahmani & Frossard (2025) via a score-based approach. Varambally et al. (2024) also proves identifiability when the discrete latents represent global states. Our "states determined" model is similar to Song et al. (2024), where identifiability is established by assuming mechanism sparsity and knowledge of the num- ber of regimes. Other works focus on fixed causal struc- tures, modelling nonstationarity through noise distributions (Huang et al., 2020; Gong et al., 2023) or time-varying ef- fects (Huang et al., 2015; Zhang et al., 2017; Ghassami et al., 2018; Huang et al., 2019); such as Huang et al. (2020) with distribution shifts; Gong et al. (2023) with history- dependent noise: or Huang et al. (2015) with time-varying functional causal models.
Unknown number of state values K: Most prior work, including HMM-ICA (Hälvä & Hyvarinen, 2020) and CtrINS (Song et al., 2024), assumes that the number of la- tent regimes is known. Our approach leverages Yakowitz & Spragins (1968), which enables identifiability without knowing the true number of regimes. This allows iden- tification of K by model selection (MeLachlan & Peel, 2000) (assuming convergence to the MLE), which is not theoretically supported when K requires to be known.
No assumption on state dependency: Prior works typi- cally assume either the "states independent" case (Hälvä & Hyvarinen, 2020; Balsells- Rodaas et al., 2024; Rahmani & Frossard, 2025); or the "states determined" case under strong structural constraints (Song et al., 2024). Our identifiability results make no assumptions about state dependencies, allowing feedback from observations.
Regine-dependent identifiability: Our theoretical re- sults (Thms. A.6-A.7; Cor. A.8) build from general Markov Switching Models to our specific implemen- tation, SDCI. Theorem A.6 introduces a novel proof strategy that extends from Yakowitz & Spragins (1968), providing a general theoretical foundation for regime- dependent causal discovery (Saggioro et al., 2020).
As mentioned, SDCI considers samples u1.T ~ D, each generated under different structures. The presented results remain valid, as identifiability holds even when considering the distribution of a single sample. However, the consis- tency of SDCI, along with other approaches within the same family. such as ACD (Löwe et al., 2022), remains an open challenge. Recent works (Gong et al., 2023; Geffner et al., 2024) have shown that the validity of variational objectives for causal discovery relies on strong assumptions; including universal approximation properties of g, absence of model misspecification, and the infinite data limit. These works assume fixed structures across samples, where SDCI can be adapted by setting To... (W|x1r)= = 46w (W).
6. Experiments
6.1. Springs and Magnets
We evaluate SCDI on spring data adapted from Kipf et al. (2018); Löwe et al. (2022), consisting of particles in a box, connected by springs with directed impact - meaning that e.g. particle could affect particle j with a force through a connecting spring, but leaving partiele i unaffected by this spring force. We further modify the dataset to introduce repulsive magnetic interactions, resulting in 3 edge-types: none, spring, and magnetic. We assess SDCI across de- termined and recurrent states. In the determined case, the state is modeled as a function of particles' positions, while the recurrent case involves state transitions when particles
5. Related Work
Causal discovery for time series traditionally extends from non-temporal data (Assaad et al., 2022). These approaches
6

---

Causal Discovery from Conditionally Stationary Time Scries
1.0
1.0
0.8
0.8
007
5 vars
0.7
5 vars
F. S.core
0.8
10 vars
10 vars vars
0.6
20 vars
0.6
0.6
19
States
19
States
SDCI
(a) States determined.
(b) States recurrent.
ACD
0.4
Rhino
Figure 4: Fj Score of the edge labels W and states for samples with shared underlying structure with K = 2.
N-GC
5
10
20
10
20
Fixed Graph
Variable Graph
1.0
Summary graph (g Fi score on determined states data, with fixed and variable structures across samples.
Figure 6:
5 vars
0.8
0.8
10 vars
0.77
10 vars
5 vars
0.7
Reconstruction MSE
10
20 vars
0.6
10
States
1
States
(a) States determined.
(b) States recurrent.
Ground truth
Figure 5: Fj Score of the edge labels W and states with structures varying across samples with K = 2.
2 States
States
10
3
6 8
Number of states K
collide with walls. Details on data generation, model hyper- parameters, and additional results (including observed case) are provided in Appendices C.I, B.4, and E. respectively.
Figure 7: Test reconstruction MSE vs number of states K for data with ground truth = 2 (red) and = 4 (blue).
To empirically verify the consistency SDCI in estimating state-dependent structures, we begin with a fixed-graph set- ting, where the graph remains constant across samples, and use amortised posterior fe... (W)rrr) inference. Fig. 4 demonstrates that SDCI achieves perfect structure estimation on both state settings. However, accu- rately estimating the states in the recurrent case is more chal- lenging, likely due the exponential computational cost of exact inference. Our formulation considers graphs that vary across samples, and we present results again in both state cases in Fig. 5. In this case, recovering state-dependent structures is significantly more challenging. While SDCI successfully captures the state dynamics the determined case, the increased complexity from variable graph struc- tures makes recovering state-dependent structures the recurrent notably difficult, even with only 3 variables.
ever, N-GC particularly achieves strong results for vari- able graphs, surpassing ACD despite its simplicity. Overall, SDCI decomposes the nonstationary dynamics into con- ditional stationary components while accurately capturing state transition dynamics.
tew. (W) for
Selecting the number of states. Determining the number of states K, or the number of regimes in regime-switching dynamics, a fundamental challenge in real-world data, As discussed in Section 4, SDCI is also identifiable in terms of K. Assuming the consistency of SDCI, K can be theo- retically recovered by maximising the data lig-likelihood, which we approach by model selection (McLachlan & Peel, 2000). However, in practice, overestimating K may lead to overfitting or redundant regimes. To overcome this is- sue, standard selection heuristics such the elbow method (Thorndike, 1953) can be applied. Figure 7 shows the recon- struction error for two settings: states recurrent with N 5 and K = 2 (in red); and states determined with N = 10 and K = 4 (in blue). In both cases, the MSE plateaus when K reaches its ground truth value, thus providing a principled heuristic to identify the true number of states.
We compare SDCI with causal discovery baselines in ex- tracting graphs from conditionally stationary time series. Specifically, we measure the Fi score for summary graph identification determined states data with fixed and vari- able graph structures, benchmarking against ACD (Löwe al., 2022). Rhino (Gong al., 2023), and Neural Granger Causality (N-GC; (Tank al., 2021)). For variable graph datasets, Rhino and N-GC require re- re-training for each sam- ple, adding computational overhead. Results in Fig. 6 show a clear advantage of SDCI in terms of summary graph es- timation. We observe that approaches assuming causal sta- tionarity struggle to aggregate the full structure into a co- herent summary graph, limiting their performance. How-
6.2. Gene Regulatory Networks
We extend our evaluation to the inference of Gene Reg- ulatory Networks (GRNs) during cellular differentiation, reprogramming and development, which are defined by dy- namically changing gene interactions with nonstationary,
7

---

Causal Discovery from Conditionally Stationary Time Scries
==
Table I: AUROC and Fi score of the GRN structure.
METHOD
AUROC
Fj SCORE
R-PCMCI (Saggioro al., 2020)
0.887
0.062
N-GC (Tank et al., 2022)
0.556
0.093
ACD (Löwe et al., 2022)
0.714
0.187
State
Rhino (Gong et al., 2023)
0.933
0.081
SDCI Observed
0.805
0.182
SDCI Determined
0.936
0.347
SDCI Recurrent
0.855
0.276
State
(a)
(b) 1=
Figure 8: Example of a bifurcating network (b) from Dyn- Gen, where in (a) gray nodes denote target genes, and other colors indicate genes activated by their corresponding states.
SDCI Obs (Km4)
0.3
ACD
SDCI Unobs (Km4)
MSE
0.2
SDCI Unobs (K=2)
VRNN
NRI-NPM
20
40
60
80
100
Time
Figure 10: Test error on forecasts. The dashed line repre-
sents the mean value.
Figure 9: Conditional summary graphs extracted by SDCI. Genes are grouped by states, and gray nodes denote targets.
gene deactivation is typically gradual rather than abrupt. The recurrent case suffers from the underlying exponential of exact inference (approximated by go). which is criti- cal in high variable scenarios. In contrast, the determined case proves to be simple yet effective approach that adapts to the time-varying dynamics in GRNs. We visualise the estimated strucutre in Fig. 9, where genes are grouped by their associated states. SDCI successfully detects deacti- vated gene interactions, except for gene groups B and C: and thus provides robust framework for realistic GRNs with direct applications to tasks such as cell type specific regulatory network inference.
and nonlinear dynamics (Schiebinger et al., 2019; Yeo et al., 2021; Kamimoto et al., 2023; Bhaskar et al., 2024). We simulate gene expression data using DynGen (Cannoodt et al., 2021), a semi-synthetic simulation engine that models dynamic regulatory interactions. ? In DynGen, an underly- ing state network introduces nonstationarity by activating deactivating groups of genes, leading to time-varying structures. Fig. 8 illustrates example of bifurcating net- work, where the system transitions through different states: activating genes A, then transitioning to B, and ending by activating genes from C' or D. See App. C.2 for details.
6.3. NBA Player Trajectories
We simulate 1000 cells with N 49 genes for T 50 time steps; under bifurcating state network with 4 regimes. We find SDCI is tailored to GRN setups, since the state variables (K~ = 2) naturally activate or deactivate gene ex- pressions. We evaluate SDCI in the 3 scenario classes, and we leverage ground-trutt information to manually activate or deactivate genes the observed case. In Table we report results in comparison to causal discovery baselines in terms of estimating the underlying GRN structure, where observe SDCI shows superior performance in terms of Fi score. In the observed case, we find that state auxiliary information does not provide significant advantage, as
We consider NBA player movements (Linou, 2016), real- world multi-agent trajectory dataset with highly nonlinear & nonstationary dynamics. See Appendix C.3 for details of the dataset, including our design for auxiliary states (as ground- truth is unavailable). We evaluate SDCI under observed and determined states. To simplify the task, we model the tra- jectories of the players (position and velocity) conditioned on the ball's position and velocity. This achieved by mod- ifying Eq. (10) include the ball features in the message passing aggregation of the decoder. In addition ACD, we compare against non-causal baselines VRNN (Chung et al., 2015) and NRI-NPM (Chen et al., 2021) (Appendix B.4). All the models are trained on sequences of length T = 100.
We do not the widely-used DREAM3 benchmark (Mar- bach al., 2010) since it limited by only simulating steady-state individual gene perturbation conditions.
Fig. 10 shows the average forecast error (MSE) of the player
8

---

Causal Discovery from Conditionally Stationary Time Scries
to diverse modelling choices while extracting interpretable patterns in complex, nonstationary systems.
30
7. Conclusions
We have developed SDCI for causal discovery in condition- ally stationary time series. The key innovation is the new concept of conditional summary graphs that are identifi- able under broad class of underlying state dependencies Evaluations on semi-synthetic data show SDCI's superior performance in extracting the underlying causal graph and its potential for biology applications. Importantly, the im- provement of SDCI over VRNN and NRI on modeling NBA player movements demonstrate the promise of causality- driven methods for forecasting and data interpretability.
(a)
bb)
Figure 11: Illustration of learned structures on SDCI (K 4) given sample (a), where (b), (c) correspond to g and Ges respectively.
Impact Statement
(a) K = 2 state values.
(b) K = 4 state values.
Figure 12: Learned regimes from SDCI on the NBA dataset. The colour maps refer to the state posterior distribution (s (lx(")) k [1, .1..... K).
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential socictal consequences our work, none which we feel must be specifically highlighted here.
References
positions on a held-out dataset. Overall GNN-based meth- ods outperform VRNN. Moreover, ACD and SDCI achieve better long-term forecasts, despite using first-order Markov transitions. This is likely due to the "no-edge" interaction for reducing error accumulation through time. The hidden state setting allows SDCI to have slight advantage over ACD thanks to adapting player interactions through time.
Ahmed, K., Zeng, Z., Niepert, M., and den Broeck, G. V. SIMPLE: A gradient estimator for k-subset sampling. In The Eleventh International Conference on Learning Representations, 2023.
Ansari, A. F., Benidis, K., Kurle, R., Turkmen, A. C., Soh, H., Smola, A. J., Wang, B., and Januschowski, T. Deep explicit duration switching models for time series. Ad- vances in Neural Information Processing Systems, 34: 29949-29966 2021.
Fig. 11 visualizes the extracted conditional summary graphs from SDCI for sample trajectory (additional visualiza- tions in Appendix E.2). We observe that SDCI extracts interpretable structures relevant basketball plays: Players 2 and 5 receive the majority of interactions (Fig. 11b) as Player 2 passes the ball to Player 5. Also interactions from the read team (defense) to the blue team (offense) are more prominent. Notably, SDCI adapts to nonstationary dynam- ies by controlling interaction sparsity and switching regimes throughout sequences.
Assaad, C. K., Devijver, E., and Gaussier, F. Survey and evaluation of causal discovery methods for time series. Journal of Artificial Intelligence Research, 73:767-819, 2022.
Balsells-RRdas, C., Wang, Y., and Li, Y. On the identifi- ability of switching dynamical systems. In Forty-first International Conference on Machine Learning, 2024.
While our identifiability theory does not require pre- determined number of states values K, in practice accurate estimation of K remains a challenge, where different K may return different results. For instance, Fig. 12 shows the state posterior as a function of player positions on the court. For K 2. states change near the mid-court line, reflecting common basketball play strategies where players transition between "defense" and "offense". The K 4 case turns more fine-grained result by further partitioning the court, with boundaries positioned near the three-poine line. Notably these insights arise despite model simplifications, where the states are made dependent solely on positions, excluding velocities. This highlights how SDCI can adapt
Bhaskar, D., Magruder, D. S., Morales, M., De Brouwer, E., Venkat, A., Wenkel, F., Wolf, G., and Krishnaswamy. Inferring dynamic regulatory interaction graphs from time series data with perturbations. In Learning on Graphs Conference, pp. 22-1. PMLR, 2024.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877-1901, 2020.

---

Causal Discovery from Conditionally Stationary Time Scries
Cannoodt, R., Saelens, W., Deconinck, L., and Saeys, Y. Spearheading future omics analyses using dyngen, multi-modal simulator of single cells. Nature Communi- cations, 12(1):3942, 2021.
Conference on Uncertainty in Artificial Intelligence, pp.
939-948. PMLR, 2020.
Hamilton, J. D. A new approach the economic analy- sis of nonstationary time series and the business cycle. Econometrica: Journal of the econometric society, pp. 357 357-384, 1989.
Chen, S., Wang. J., and Li, G. Neural relational inference with efficient message passing mechanisms. In Proceed- ings of the AAAI Conference Artificial Intelligence, volume 35, pp. 7055-7063. 2021.
Huang, B., Zhang, K., and Schölkopf, B. Identification of dime-dependent causal model: A gaussian process treat- ment. In Twenty-Four international joint conference on artificial intelligence, 2015.
Chung. J., Kastner, K., Dinh, L., Goel, K., Courville, A. C.,, and Bengio, Y. A recurrent latent variable model for se- quential data. Advances in neural information processing systems, 28, 2015.
Huang, B., Zhang, K., Gong, M., and Glymour, C. Causal discovery and forecasting in nonstationary environments with state-space models. In International Conference on Machine Learning, pp. 2901-2910. PMLR, 2019.
Clevert, D., Unterthiner, T., and Hochreiter, Fast and ac- curate deep network learning by exponential linear units (clus). In Bengio, Y. and LeCun, Y. (eds.), 4th Interna- tional Conference on Learning Representations, ICI. 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Truck Proceedings, 2016.
Huang, B., Zhang, K., Zhang. J., Ramsey, J. D., Sanchez- Romero, R., Glymour, C., and Schölkopf, B. Causal dis- covery from leterogeneou//nossatioonyy data. J. Mach. Learn. Res., 21(89): 1-53, 2020.
Entner, D. and Hoyer, P. O. On causal discovery from time series data using fci. Probabilistic graphicul models, pp. 121-128, 2010.
Hyvarinen, A. and Morioka, H. Unsupervised feature ex- traction by time-contrastive learning and nonlinear ica. Advances in neural information processing systems, 29, 2016.
Gassiat, É., Cleynen, A., and Robin, S. Inference in fi- nite state space non parametric hidden markov models and applications. Statistics and Computing, 26(1):61-71, 2016.
Jang, E., Gu, S., and Poole, B. Categorical reparameteriza- tion with gumbel-softmat In International Conference on Learning Representations, 2017.
Geffner, T., Antoran, J., Foster, A., Gong, W., Ma, C., Kici- man, E., Sharma, A., Lamb, A., Kukla, M., Pawlowski, N., Hilmkil, A., Jennings, J., Scetbon, M., Allamanis, M., and Zhang, C. Deep end-to-end causal inference. Trans- actions on Machine Learning Research, 2024. ISSN 2835-8856.
Kamimoto, K., Stringa, B., Hoffmann, C. M., Jindal, K., Solnica-Krezel, L., and Morris, S. A. Dissecting cell iden- tity via network inference and in silico gene perturbation. Nature, 614(7949):742-757 2023.
Ghassami, A., Kiyavash, N., Huang, B., and Zhang, K. Multi-domain causal structure learning in linear systems. Advances in neural information processing systems. 31, 2018.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In Bengio, Y. and LeCun, (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Confer- ence Track Proceedings, 2015.
Girdhar, R. and Ramanan, D. CATER: diagnostic dataset for Compositional Actions and TEmporal Reasoning. In ICLR, 2020.
Kingma, D. P. and Welling, M. Auto-Encoding Variational Bayes. In 2nd International Conference Learning Representations, ICLR 2014, Banff, AB, Canuda, April 14-16, 2014, Conference Track Proceedings, 2014.
Gong, W., Jennings, J., Zhang, C., and Pawlowski, N. Rhino: Deep causal temporal relationship learning with history- dependent noise. In The Eleventh International Confer- ence on Learning Representations, 2023.
Kipf, T., Fetaya, E., Wang, K.-C., Welling, M., and Zemel, R. Neural relational inference for interacting systems. In International Conference on Machine Learning, pp. 2888-2697. PMLR, 2018
Granger, C. W. Investigating causal relations by economet- ric models and cross-spectral methods. Econometrica: journal of the Econometric Society, pp. 424-438, 1969.
Lake, B. M., Ullman, T. D., Tenenbaum, J. B., and Gersh- man, S. J. Building machines that learn and think like people. Behavioral and brain sciences, 40, 2017.
Hälvä, H. and Hyvarinen, A. Hidden markov nonlinear ica: Unsupervised learning from nonstationary time series. In
10

---

Causal Discovery from Conditionally Stationary Time Scries
Linou, K. NBA player movements. https: htttps://gtthbs com/linouk22 /w////BAAPPaaa waye---aayr---oeeeeeeette 2016. Last accessed: 2022-08-06.
Peters, J., Mooij, M., Janzing, D., and Schölkopf, B. Causal discovery with continuous additive noise mod- els. Journal of Machine Learning Research, 15(58)20099- 2053, 2014.
Löwe, S., Madras, D., Zemel, R., and Welling, M. Amor- tized causal discovery: Learning to infer causal graphs from time-series data. Conference on Causal Learning and Reasoning, pp. 509-525. PMLR, 2022.
Peters, J., Janzing, D., and Schölkopf, B. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
Marbach, D., Prill, R. J., Schaffter, T., Mattiussi, C., Flo- reano, D., and Stolovitzky, G. Revealing strengths and weaknesses of methods for gene network inference. Pro- ceedings of the national academy of sciences, 107()4); 6286-6291, 2010.
Rahmani, A. and Frossard, P. Causal temporal regime struc- ture learning. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
Runge, J.
Causal network reconstruction from time se- ries: From theoretical assumptions to practical estimation. Chaos: An Interdisciplinary Journal of Nonlinear Sci- ence. 28(7):075310, 2018.
McLachlan, G. J. and Peel, D. Finite mixture models. John Wiley & Sons, 2000.
Monti, R. P., Zhang, K., and Hyvärinen, A. Causal discovery with general non-linear relationships using non-linear ica. Uncertuinty in artificial intelligence, pp. 186-195. PMLR. 2020.
Saggioro, E., de Wiljes, J., Kretschmer, M., and Runge, J. Reconstructing regime-dependent causal relationships from observational time series. Chaos: An Interdisci- plinary Journal of Nonlinear Science, 30(1 30(11):113115, 2020.
Murphy, K. P. et al. Dynamic bayesian networks. Proba- bilistic Graphical Models, M. Jordan, 7:431, 2002.
Sauer, A. and Geiger, A. Counterfactual generative net- works. In International Conference on Learning Repre- sentations, 2021.
Nichol, A. Q., Dhariwal, P. Ramesh, A., Shyam, P., Mishkin, P., Megrew, B., Sutskever, I. and Chen, M. GLIDE: Towards photorealistic image generation and editing with text-guided diffusion models. In Chaud- huri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th Interna- tional Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 16784 16804. PMLR, 17-23 Jul 2022.
Schiebinger, G., Shu, J., Tabaka, M., Cleary, B., Subrama- nian, V., Solomon, A., Gould, J., Liu, S., Lin, S., Berube, P., et al. expression identifies developmental trajectories in repro- gramming. Cell, 176(4):928-943, 2019.
analysis single-cell gene
Schölkopf, B., Locatello, F., Bauer, S., Ke, N. R., Kalch- brenner, N., Goyal, A., and Bengio, Y. Toward causal representation learning. Proceedings of the IEEE, 109(5):
Pamfil, R., Sriwattanaworachaii, N., Desai, S., Pilgerstor- fer, P., Georgatzis, K., Beaumont, P., and Aragam, B. Dynotears: Structure learning from time-series data. In International Conference on Artificial Intelligence and Statistics, pp. 1595-1605. PMLR, 2020.
612-634, 2021.
Shimizu, S., Hoyer, O., Hyvärinen, A., Kerminen, A., and Jordan, M. A linear non- ganssiaa acyelic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, I.., Bai, J., and Chintala, S. Pytorch: An imperative style, high- gigh-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024- 8035. Curran Associates, Inc., 2019.
Song, X., Li, Z., Chen, G., Zheng, Y., Fan, Y., Dong, X., and Zhang, K. Causal temporal representation learning with nonstationary sparse transition. In The Thirtt-eighth Annual Conference on Neural Information Processing Systems, 2024.
Tank, A., Covert, I., Foti, N., Shojaie, A., and Fox, E. B. Neural granger causality. IEEE Transactions Pattern Analysis and Machine Intelligence, pp- 1-1, 2021. doi: 10.1 109/TPAMM.001 30056601.
Pearl, J. Causality, Cambridge university press, 2009.
Peters, J., Janzing, D., and Schölkopf, B. Causal inference on time series using restricted structural equation models. Advances in Neural Information Processing Systems, 26, 2013.
Thorddik, R. L. Who belongs in the family? Psychome- trika, 18(4):267-276, 1953.

---

Causal Discovery from Conditionally Stationary Time Scries
Varambally, S., Ma, Y., and Yu, R. Discovering mixtures of structural causal models from time series data. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.). Pro- ceedings of the st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learn- ing Research, pp. 49171 49202. PMLR, 21-27 Jul 2024.
Yakowitz, S. J. and Spragins, J. D. On the identiiaaiiltyy of finite mixtures. The Annals of Mathmatical Statistics, 39(1):209-2 201,, 1968.
Yao, W. Sun, Y., Ho, A., Sun, C., and Zhang, K. Learning temporally causal latent processes from general temporal data. In International Conference on Learning Represen- tations, 2022.
Yeo, H. T., Saksena, S. D., and Gifford, D. K. Generative modeling of single-cell time series with prescient enables prediction of cell trajectories with interventions. Nature communications, 12(1):3222, 2021.
Yi, K., Gan, C., Li, Y., Kohli, P., Wu, J., Torralba, A., and Tenenbaum, J. B. CLEVRER: collision events for video representation and reasoning, In ICLR, 2020.
Yu. Y., Chen, J., Gao, T., and Yu, M. Dag-gnn: Dag structure learning with graph neural networks. In International conference machine learning, pp. 7154-7163. PMLR, 2019.
Zhang, K. and Hyvärimen. A. On the identifiability of the post-nonlinear causal model. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial In- telligence, UAI '09, pp. 647-655, Arlington, Virginia, USA, 2009. AUAI Press. ISBN 9780974903958.
Zhang, K. Huang, B., Zhang. J., Glymour, C., and Schölkopf, B. Causal discovery from nonstation- ary/heterogeneous data: Skeleton estimation and orienta- tion determination. IJCAI: Proceedings of the Confer- ence, volume 2017, pp. 1347. NIH Public Access, 2017.
12

---

Causal Discovery from Conditionally Stationary Time Scries
A. Identifiability Proofs
We have introduced conditionally stationary time series Section 3. Here, we will revise the model assumptions introduced in the main text, and present of our identifiability theory; starting from general Markov Switching Models (ml-m3), following with conditional summary graph identification under (m4), and finishing with identifiability of the labels of conditional effects (m5) utilised in SDCI.
A.1. Preliminaries
We review the main model assumptions that characterise SDCI. We start with the assumptions that apply to general MSMs, where have single global state each time step t. In this we denote the global state ut =: (p(s))) E (1,--., U} for some injective yp: (1....,K)* + {I....,U] U} (we use 8, when referring to multiple states in SDCI).
(m1) Conditional first-order Markov transitions controlled by u only:
Vt E TT.
(21)
(m2) Conditional stationarity: the conditional transition distribution does not change during time: for any { U} we have for any t * t', any B, E R Nd
pla, = 3|x,-1 = Y 1 = u) = p(æ: = 3| = 7, 41 = u).
(22)
(m3) Factorisation structure based the ANM model with Gaussian noise:
N
p(ar 11 2-11) = N 2
II
()
(l) f02
(2 (2
(t- ( (t- .09), (.)).. Vt E T3.
PAG)
(23)
Again, we formalise assumptions specific to conditionally stationary data, where the total state configuration is denoted by grouping all the individual states 8, = {s) ..... (N) E E (I,..., Note that this defines a specific structure in a general MSM with U == KN global states.
(m4) Multi-state dependence: For each variable i E [1....,N]
NN at time t E f1,..., T): x0 there exists a state variable
St E [1....,K] such that 8:11 = (8 8/-1) E fl,.... KJN. For any variable j E (1,...,,N) N). PA PAU) 8c (t 1),
defined as follows:
PA (t - (t- (2 h k (8) 1
(24)
where c( C denotes the outgoing edge structure (children) of variable E {I,..., KJ. corresponding to state KY.
(m5) Global function-type dependence: We allow n. functional effects (including the no-edge effect). We define the labels of conditional effects as
W: = Wiijk (O.....,4.. -). (I.,, (I...., K}, Wigh =0 - j j c cli
(25)
where each & denotes an edge-type from variable i to at state k. associated to variable i. Each edge-type corresponds to different function over the total function interactions F =
where fo(-) = 0 from Eq. (25). Given a
state configuration 8: إنع Rd pd in Eq. (23) is defined follows for any # R.Vd.
1T-1 (Jes (0) 20) 12 * s)). where ea
162,(0 (x)-1)
W $
(0....,ne), (26)
where e,, i E {l,..., N} denotes the interactions between variables and j, which are aggregated by a permutation invariant function g.
13

---

Causal Discovery from Conditionally Stationary Time Scries
A.2. Partial Identifiability
We wish analyse the identifiability of the labels W for SDCI (ml-m5) in the case of unobserved states. However, we first require developing identifiability for regime-dependen and dete-dependent structures, ie 9 and g respecitvely. We define identifiability of the
structures for a general MSM (ml-m3).
Definition A.1 (Partial identifiability of regime-dependent graph). Given observations ærr and family of models M satisfying (ml-m3), say M is partially identifiable with respect its regime-dependent graph if for any p, E M, (8) with corresponding PA ( (t 1) and PA (t (t-1) 1) for any E [N). u E {l...., UJ. and û E (I,...,ū)) U,), such that p((11:) = p(xI.T); = 0 and there exists a permutation T E Sy such that PA! - 1) = PA P 1) for i [I....,N] N. and Ul.....U).
We also define the identifiability of the outgoing edges c in terms of 9 given model with N state variables and multi-state dependence (m1-m4).
Definition A.2 (Partial identifiability of outgoing edge structure). Given observations æı. and family of models M satisfying (ml-m4), we say M is partially identifiable with respect to the ouigoing edge structure if for any p.P M, with corresponding c and 2 for any E [L.....N}: k E {L...., K},, and k E "h....,K), such that p(x1.T) ((x1:)); K = K and there exist permutations (00) E Sx such that ch (()) for i E [L....,N] and E (1...., (k)
Finally, we further define identifiability of the labels of conditional effects under global function-type dependence (m5).
Definition A.3 (Partial identifiability of conditional effects). Given observations F1.T and family of models M satisfying (ml-m5), we say M is partially identifiable with respect the labels of conditional effects if for any p.p M, with corresponding W and W such that p(æ).T) = ((xI.:);; K K and there exist permutations π E Sn, and ((0) Sx such that for any i.j E {I....,N] and k E {l.....K} K.::
Wijjk = úū (1) Wiikk = π (1i))(()))
= Wi.jkk O,
(27)
Wiihk A O.
(28)
As mentioned in the main text, these definition consider identifiability is partial since it does not cover the structure capturing interaction between Ø1.7 and 81:7 as well as those within 81:7-
A.3. Sufficiency Conditions for Identifiability
The defined partial graph identifiability cannot be achieved without further assumptions for (m1-m5). Below we list the sufficient conditions for such identifiability, some of them which we already introduced in the main text.
(al) Unique indexing of outgoing structure. Here we assume that for each state ( underlying graph representing the direct causes from variable i the rest of the variables is unique.
(L, K.,,K,,, i [I,...,NN the
vk, k' E (l,...,KKKKk K}
c + (()) C
Vi (1,
(29)
This assumption has equivalences to MSMs, i.e. when considering all state variables, 8.-1 E (l,...,K, KJN as a global state, M--1 E (1....,K*) KN).
(b1) Unique indexing of regime-dependent graph structure. For each possible state u4-1 E f1,..., , U} the underlying graph representing the direct causes between variables is unique, In other words, the resulting U graphs are different. This implies that the following holds:
Yu, u' E (1,
UJ,uuu UI,
+> Ej (1,..,, N) s.t. PAG 1= (t 1) PA 4 1- (t-
(30)
Assume an invertible injective mapping ş [I,...,K''' KJN + {l.... KND such that we can map a specific state configura- tion (k,...., to an assigned value kINN E (1,..., KN that is, kINN = ((k),..., kx). With this view, we can write the state variables in terms of one global state variable with KN regimes. We connect assumption (al) 1) to assumption (b1) defined for MSMs as follows.
14

---

Causal Discovery from Conditionally Stationary Time Scries
Proposition A.4. Assumption (al) implies ussumption (bl).
Proof. Recall the definition of PA (
PA 1 (t-1) = {-,-1 c(0) k= - -issss
(31)
Given two state configurations (k,,..., kN), (K)...., kx) E (l....,Rr K) that differ in at least one k E (I,...,N)
under (al), we have c(i) + C Again from (al), Ej E (1...., N) such that j E cli and j & c(.. From Eq. (31), and by
writing PA ()) S6-1 (t - 1), as a MSM with one global state (u4 == st) we have
Ej E (1....,,, N) s.t. 2/ E PA (1) Mi p-p( ((.......NN AN) - 1), and ( & PA (3)
ui 1=0 1 (M (t-
Aj E (1, ..... , s.t. PA (i)
pfk pxx) (t 1) + PA (i)
1 ( - (K My) (6-11 -) (32)
(t-1)
Therefore, assumption (bl) also holds.
We now revisit the functional assumptions introduced in the main text, and establish connections to MSMs.
(a2) Unique indexing of function types. Under the model assumptions (ml-m5), we assume the following:
(a2.1): For any j E (L...., N.. and given g(x(1), (12))) * j}), where h (+.J) fe (x( xx()) for some E {O...., 1}. the partial derivative Thee non-zero almost everywhere for any E [1......7) N).
(a2.2): Edge-types differ almost everywhere: Jn 0, and for e + fé,E (0, nee 1}, the following set has zero measure:
Ne,e' == 2i ERR: 30e E R (21, (f1
(33)
Ox
On
(b2) Functional faithfulness. This condition considers the functional properties of 142 in terms of its faithfulness the graph structure. We require the following sense of faithfulness in terms of the functional behaviour for all s {1..... K)K:
(b2.1) |() is differentiable w.r.t. PA(1) 8 (t 1) almost everywhere. Also all the entries of the Jacobian matrix 4rim
when well defined, are non-zero almost everywhere w.r.t. PA (f) (t - 1). 86-1
1P (c-1)"
(b2.2) If x & PAU) 1 1), then flf, is constant w.r.t. 2;-1-
(8)
Intuitively, this faithfulness condition requires the output of the function slا", to vary if and only if PA () S.-1 (t 1) varies. We also connect (a2) to (b2).
Proposition A.5. (a2) implies (b2).
To see this, note that (a2.1) and (a2.2) force the derivatives w.r.t PA (1)
(t-1) to be non-zero almost everywhere (which implies (b2.1). 1). Furthermore, this is only violated in a zero measure set of points, or when variable interacts with j via fu. (8) but this only is possible when 2 & ())
8. (t_,(t-
8 (t - 1), which implies (b2.2).
(3)
A.4. Identifiability of Markov Switching Models
With the above assumptions can now state the following identifiability results:
Theorem A.6. A Markov Switching Model (ml-m3) under assumptions (bl) and (b2) is partially identifiable with respect to its regime-dependent graph (Def. A.I)
15

---

Causal Discovery from Conditionally Stationary Time Scries
Proof. Assume there exist two MSMs satisfying p(#1r) (((1r)) Since wlog. p(æ1,:) - p(0n the fact that p(æ1r)) = ((x11:), and p(a,, #1:t-1) is a probability distribution imply that
p( 11)+1) = ((
Vt = 22....
(34)
Now since the model assumes (m1) a conditional first-order Markov structure controlled by the previous state 8:-1 (Eq. (21)), we can show that the conditional distribution is a finite mixture distribution:
(11-1) = Σ p =
10 u4-1 = u)-
(35)
==1
U-11 We assume (b1) and functional faithfulness (b2). Since (m3) p( 2,- = u) is Gaussian (Eq. (23)), using the identifiability result of Gaussian finite mixture (Yakowitz & Spragins, 1968) we have U U, and for almost any given 2t-1 a RNd (modulo some zero-measure sets) we have the following result: for any { UJ,, there exists u(a,u)= E {I....UU such that
p(u-11 = D1 -t a) = p(u,1 = ú(a, u) 21 2, = a);
(36)
p(a, = a, u1-1 = u) - /( = a, Uz 1 -
To clarify, Proposition 2 in Yakowitz & Spragins (1968) establishes multivariate Gaussian distributions are identifiable if and only if the means or covariances are distinct. Our assumptions (b1) and (b2) ensure distinct means for almost any xt-1 = E RNd
The (m3) factorised Gaussian structure (Eq. (23)) and the above identification result further indicate that
p(z
(1) x1 a, u = u) p(x= (i) xt-1 a. 2 = ū((x,))))))) Vj 1, L...., N.
(37)
4 = u) p()) for 1,..., N and 1,.... K, Again wlog., let us denote the mean function of p(z, (7) [x,-1 a, 24-1
and we also use a short notation PA ()) (t. - 1) to denote the input variables for f(3) Under (b2.1) of the (b2) functional faithfulness assumption, and given that U,N < +oo, there exist an open set X RR such that vxx) = ((R where y(+)) denotes the Lebesgue measure of a Euclidean space, and both Eq. (37) and the following condition hold (note that (t 1) C 1)-)):
dr(0)
all the entries of dPA
(3) 11-1=a non-zero, Va X, Vj N).
(38)
To see this: under (b2.1) have for each {L,..., U} there exists open set X, PA 1) with {((x))
((PA (i) 1)) such that the partial derivatives computed within this set are non-zero. Then we can construct X' follows:
0 (0 10 & (t 1))),
x= x&, x= nx, (Xh,
(1)
U
2 = n2, x (a E R & PA ((-1))). (39)
u=1
We can show wlog. that p(X,, x {z(21 product measure. Therefore using the union bound we also have m²²²) = (u Nd).
P - 1)}) (u Nd)
Nd) since the Lebesgue measure of Nd is
Now we show that a((e, u) is a constant for a E X' almost everywhere, and those a values satisfy ú(a, u) = ū(u) and PA()) (t -
(j) PA ((w) (t- 1) for all j E (1.
(i) By model definition (m3) (Eq. (23)) and assumption (b2.1), within .;-1 a X' have p(xr (1)
(1-11 u2-1
u) = p(= (5) PPA ( (t- - 1), u = u). Similarly for P we have (
(1) [0-11 4:11 = ū(a, u)) = =p(x) PA (t-
(1) (j)
1), 14 i(0,10 u)).
16

---

Causal Discovery from Conditionally Stationary Time Scries
Then from Eq. (37) and assumption (b2.2), there exist most zero-measure set Xy C X of a values such that
PA ala (1 - 1)) # ( - 1). Otherwise, we can show that there exist two a + a' E 2o with PA (3)
a(a.u) - 1)) =
Paala' u) (t ( 1)) PA (t 1), which contradicts with Eq. (37) and (b2.2). This means, by Eq. (23) again, and notice that (b) = (())::
6) PA a) (t - PA 1). Va E X No. Vj E [},
(ii) Under (b1) unique indexing of causal graph structure, we have ú(a, u) as a constant w.r.t a E 22 To see this, if there exist a, a' 2o such that ú(ax u) A ú(a', u), then from (bl), there exists j E {I, N such that
PA (f)
())
1)) ((- o PA ((ar - 1)), a contradiction to point (i) above. We now write a(ce, u) = ((u) w.l.o.g., then a(a,w))
we have
PA - 1) = PA (( 1), Vo X Vj E (I,,,N,
In summary, we have shown that there exists permutation 7 Sy such that ū r(u) and the following equivalence holds for all j E (1....,N) N) and almost everywhere for 2;-1 E Rd:
(x( x u4-1 = -u) = -p(x()) [ 4-1 4-1 r(u)), PA - 1t- PA -) 1); Vj Ny VIL-1 E N' m(d'((o)) M(BNNg)
(40)
A.5. Identifiability of Conditionally Stationary Time Series
We start by introducing assumption (m4) and establish identifiability of the conditional summary graph under unique indexing of outgoing edges (al) and functional faithfulness (bl).
Theorem A.7. The multi-state dependent model (ml-m4) is partially identifable w.ra. the outgoing edge structure (Def. A.2) up to permatation equivalence of the states, if satisfies the assumptions of (al) unique indexing of causal graph structure and (b2) functional faithfulness.
Proof. Assume there exist two models under (ml-m4), satisfying p(x1.)) = ((().)) For simplicity, we first want to view the above as mixture model of KN regimes with one global state. Assume again an invertible injective mapping : fl, KNN N >> {1..... KN} such that we can map a specific state configuration (k1,..., ,x) to an assigned value kINN E (l...., K KN that is, k1NN = = kx). Therefore, for any L E (1,...,, ,T,, we can obtain u, = (((s)) to reduce the multi-state model into a general MSM. Given that assumption (al) implies (b1), from Theorem A.6 there exists a permutation permutation 5 Sgx such that KINN = T(k.N) and the following equivalence holds for all j E {1, and almost everywhere for æ;-1 E I Nd:
pl 4-1 = kI:N) = p(x( 10-1, u-1 = (kkiN))
( -
PA KiN (1 (1-1) PA (A 1),
(41)
Vj E [L...,NN; Vx,-1 E X', ((X( ((
We can revert the above back to the multi-state model notation (ml-m4), obtaining the following equivalence for the causal effects:
(i)
PA kk) (t 1) PA (porop- (x),.... 1),
(42)
where the permutation 7 is general and can permute both state indices and values. From (m4), recall the definition of (i)
PA (KI kww) (t- 1) for some (k1,..., kx) (1...., K}N, and consider the equivalence on PA (J)
(k)....w)(t 1) for some
(ki,..., .x) E (1...., KYN:
N U i=1
PAC ( 11-11((1, kN) (t (t-
af 1s
(
Uf 1=1
1i E
200) k.
(R
PA
-- ( Rx) (t-1).
(43)
17

---

Causal Discovery from Conditionally Stationary Time Scries
.....,,, K). we can recover the outgoing edge structure c Then for given i E (I,... N and by fixing = k; E (1...., from PA (i)
(w) 1) for j E NJ....;N.. Equivalently, by fixing k k (1....,KK) recover (00 from ())
PA (k AN) -0-)11 1) for all j (1,...,NN)
c = U j=1
N
j E PA
N hh.... kx) (t (1--1)3 U ==1
1)}
j E ( Rh dwn 11}
2
Given the unique indexing assumption (al), every k necessarily needs to map to different k. Therefore, k is obtained from permutation of k, which might differ among variables. Therefore, there exists a Sx such that C/2 200 (k)) for all
i E f1...., N and & E (1...., }.. This implies that the multi-state dependent model (ml-m4) is partially identifiable with respect to its outgoing edge structure.
Corollary A.8. Conditionally stationary time series (ml-m5) are partially identifiable w.r.t. the labels of conditional effects (Def. A.3) up to permutations, if they satisfy: (al) unique indexing of outgoing structure, and (a2) unique indexing of function types.
Proof. Under mml-m4) and assuming (al-a2), from Theorem A.6 the following equivalence holds for all j E {l,.... N} and almost everywhere for xT-1 Nd.
(1) p 2 [1-1, SC-1 (A1,.... kw)...,,)) 1 (z) 11-1 81-1 (-00)))))--1(00)))))))))))))))))
(44)
Vj [I,,..,,,, Vx,-1 X' (() - (()
From Gaussian identifiability (Yakowitz & Spragins, 1968), we have p((i (II-1) flll, (2x-1), for each j {l,...,NN and any 1t- E No. From (m5), we have
(1) 10--1.2111 (F{pp (2)-)) = (Foup)
(N) (2) faxp
(
9 (fea
( ( [01 2 ,..,, Sapep (,(M. = f(i) (a)-1), (45)
(1-) = w ( where e
We can directly establish a relation from (1,) [
(i.f) e using the partial derivative on the mean of
a with respect to 0;-1
054 (I1-1)
0g of
0g 0f
o (xx-1)
(46)
0x
(8)
(h.)
dx--1
ah(
dx,
(1)
0x,-1
where the derivative of g is independent of 81-1, and also notably (which will be of great importance later). Under assumption (a2.2), the set
Xfune
U (Ne. U )e Ege!
is zero measured. & denote the in (a2.2) for another model ý under (ml-m5) that satisfies (al-a2). Assume Xy contains the points where the partial derivative of g with respect (6.)) is zero, where we know it has measure from 1a2.1). Therefore, for any Do X' (2% U ( Xfume)),
0g
0 (5))
0g
of
(
(47)
dx
dx (1)
=
20
=
Note X') X')(XUU(X** X Xfune)) )) is full measured. Given that (1-)) E (0...... - 1}, from (=2.1))).2) we know that if (1-) = 0
we have e(t,)) = 0 due to having non-zero derivatives on fa for any e * 0. Furthermore from (a2.2), for any e * e' the (1.))
derivatives of fa and for are not equal, Then, any e * must map uniquely to another (1.3) * 0, otherwise under
18

---

Causal Discovery from Conditionally Stationary Time Scries
assumption (a2.1-a2.2) we have contradiction with Eq. (47), it will imply repetition of edge-types. Therefore for each i and each j, there exists a permutation ((ii) E Sn,-1 such that for any a!ha) = (1a2) (e) (1)))
for Gt-l E f1,.... Tr - 1/.
This does not imply any direct identifiability on the set of functions "..........- but the labels of conditional effects W. Due to permutation invariance of the aggregation g, the partial derivative terms 3ht55 are equal across i and j for fixed
0g
(1.f) 20 E ( (x N Xfane)). This forces the permutations x(1-) to be equal, as otherwise, edge-types where et- *
mapping to different e/"r]) will violate Eq. (47) under assumptions (22.1....2). Therefore, there exists E Sn,-1 such that for any ((-)) é-1 = T (((
(id) (4d)) for e-1 E {I,...,,e, 1}. Now, recall the definition of W:
W = Wiijk E {O,...,,,, ne - 1) ú,j
N), k E (1....,
K).....,,, K), W.iik = = j $ c
(48)
From Theorem A.7, indexing w.r.t k in the above equation is equivalent up to permutation x()) on W. Considering (6.5)
6z-1
W. (..50
we have the following equivalence for W when Wiihk # O, for any i,j E NJ, and ls E {I,...,,K} K}.
Wiiik = π (1)1),00))) Wiii E (1,...,, nhe 1}.
(49)
This implies partial identifiability with respect to the labels of conditional effects W (Def. A.3).
B. Implementation Details
B.1. ELBO Derivation
Below we derive the ELBO objective for SDCI, which is expressed in Eq. (15). We start with the likelihood term pa(2 and write it in terms the joint distribution pv (11.1, $1:T. W).
log (xI = log Σ
Σ W
(I(TT S1.7, W)
(50)
BUT
log Pe (T1:T 81:7, W) (WW 81:7 (1:T))
> E ra)))))))))
(51)
Pe (21ITT 81.7 W) log (51r (1:T)
Pv (W)
Egg (W
log Tow (W]))1))..
(52)
log (2n 11:T, W)] KL gow (W/z11:)
per (W))
(53)
T Pv, (s (el/ -1: 81-1:0-L.)
Bos. (ALT
log
(54)
go. (1.T((11:T)
w)] KL (L(() (po
Bgo(W.en ((1)))
(55)
T
KL KL (0(091100
Ps. (s 81-11--L))
(56)
B.2. Exact Inference on State Variables
Exact inference on state variables based on sum- sum-product implementations require computing the posterior for all combinations of states at each time step, thus introducing O(K~) complexity. However, in the determined states case, the state variable is
directly determined by observations, which implies p(s (x1:-1) p p(s [x, )) To compute the reconstruction term in Eq. (15), consider the likelihood distribution p(æ1:r| (V) = I p [ W), where we assume the states have heen marginalised. Following our implementation, consider the likelihood term p(æ, 1 W) and assume the message (9)
follows delta distributed variable. Expanding the marginalisation equation of the state variables results in the following:
(ax W) II Pv. (a (a. (1
h. (N3)
II 5
Σ
Pv. (h., (22 22, W. 8 1.pp. 1
(2(())
(57)
19

---

Causal Discovery from Conditionally Stationary Time Scries
(o(mnyo2211) go (wwy #1r))
Painwise Embedding
Input
MLP
MLP Aggr
Embedding
Pairwise concatenation
Aggregate
Edge type
distribution
Figure 13: Illustration of the implementation of the SDCI encoder which adapted from ACD (Löwe et al., 2022) and allow for conditioning on states. In the example, we consider states.
Note that we can marginalise the states element-wise, thus reducing the exponential cost to O(NK). Given the above equation equivalent to Eq. (16), we can set qo. = Pv. for exact inference on state variables.
For the recurrent state here results in exponential cost, compute pv (xt (1.-.)), where can also try marginalising the states.
cannot simplify the forward state posterior ps (s (1==1)). To why exact inference
Py (x 11 W) II Ps. (x. (1) b h (ND)
II
Σ
Pos (2 ( w, 60
(58)
Where the state posterior obtained using the forward algorithm:
( (1) (1
Σ (0 22
Σ
pv. Cos (0-111822 -t-1: (
(59)
2--
where Pv. 2 - )s) is given from the state decoder, and 2 (21==1)) is computed as follows:
Py 220 pu(s x x1.-- 2) (2 1 x1-2)
(0 1|s xt x2-2)
p 2112-2) Py: (1 (2
(60)
Pe 111.. Pay x.,1 x1.--2)
and we find recursive terms Pa (x 21:-22 and P (5, (1) Unfortumately, computing Py (z x(-2) requires
marginalising (1. 2s..,..... (N) and involves all possible tuple combinations, thus introducing computational cost of O(KN).
(0 81-1 = 1, 81-11,
Σ p(8:-1188 ki x. ()(1: =, 212 2t-2
(61)
B.3. Encoder Architecture
Below provide details our encoder architecture (WW, 81.7 æ1r) go.. (W(anar))s, (Sur)) (1:r)
Fixed graph encoder. As mentioned, we consider an amortised encoder on for fixed state-dependent structures across samples: Io... (W[x q æ...
xn, independently of qo... (W). We modify Eq. (13) and directly parametrise the logits Φiq E R K'n,
Variable graph encoder Our architecture extends directly from ACD (Löwe et al., 2022), and we incorporate additional edge-edge layers proposed in Chen et al. (2021) only for SDCI under the recurrent state case. The logits Φi5 for the
20

---

Causal Discovery from Conditionally Stationary Time Scries
distribution yo... (W.r) are obtained as follows. First, the model computes a latent embedding 2 for each node using the whole sequence:
S (T177 I:T
(62)
Then each embedding is updated using a graph neural network (GNN) that captures the correlations between nodes. Specifically the message passing procedure follows the two equations below:
z1 = f0z )
(63)
2111 = Sos (15))
(64)
itj
For the recurrent state case, we incorporate edge-to-edge message passing operations proposed by Chen et al. (2021) after computing the edge embeddings Eq. (63). The edge-to-edge message passing treats the set of edges as a sequence, and we implement the mapping using self-attention. See Chen et al. (2021) for additional details. Finally, we obtain the softmax logits Bi E Rx* for every pair i ++ j and every state value S k S K:
Φ = Far x2 )
(65)
The above network architecture design is visualised in Figure 13. according to equation 13. The details of the architecture settings follows the designs in Löwe et al. (2022) and Chen al. (2021). Each embedding step Sa., including the self- attention network in the edge-to-edge message passing, uses two-layers of 256 dimensions and ELU (Clevert al., 2016) activations followed by a batch normalization. for uses skip connections and modify its output size to generate pairwise embedding for each of the K states. For fully-observed state case, the architecture for qe. (W| $1:1) follows similar
structure, except that for the first layer we use z = for (concat( (2 1.7: 8(() ((rr)). where $({) is a one-hot encoded version of the states {s( (4) It=1-
State encoder. For determined states, use the state decoder explained in the next paragraph. For recurrent states, combine edge embeddings and the state posterior approximation from Ansari et al. (2021) to implement GNN-RNN network. First, we generate edge embeddings with temporal components. This is equivalent to Eq. (62) where we use æ; to obtain 1,,-- Then, we obtain edge embeddings z ziij),, similarly as in Eq. (63) using the same implemntation design. The temporal edge are forwarded to a 3-layer bi-directional RNN with GRU cells and 256 dimensions, followed by a 1-layer forward RNN with GRU cells and 256 dimensions. Finally, the resulting embeddings are aggregated following Eq. (65)
(i)
(f)
with similar implementation designs.
State Decoder. The state decoder implemented as a two-layer MLP with 256 dimensions, where the input dependent on the requirements for each state dependency case: xi (1) in the determined case, and (xr at-1: s 1) in the recurrent case.
Observation Decoder. We implement the set of functions F = (/I,..,, }} using two-layer MLPs of 256 dimensions and Ieaky-ReLD activations with slope 0.1. The mapping uses skip-connections and the same design and the edge-type functions above. For gene regulatory networks, we use incorporate node embeddings into the aggregator g following Gong al. (2023), resulting increased network expressivity. The node embeddings have 16 dimensions. For NBA data, we instead incorporate the ball's 's features each time step b, TR., denoting 3D position and velocity.
B.4. Training Specifications
Our method has been implemented with Pytorch (Paszke et al., 2019), and the experiments have been performed on NVIDIA RTX 2080 Ti GPUs. Code for our experiments is available at https: / /gi thub. com/ ch/ar 2/23//DDC.
SDCI and ACD. All SDCI and ACD (Löwe et al., 2022) models have been trained using the following training scheme. Following Kipf et al. (2018), the models are trained using ADAM optimizer (Kingma & Ba, 2015). In all datasets, the learning rate of the edge labels encoder is 5- 10-4 for variable graphs, and 5 10-3 for fixed graphs. The learning rate of the decoder is 5- 10-4. Learning rate decay is in use with factor of 0.5 every 200 epochs. The duration of the training phase differs between datasets and state dependence considerations. We monitor the reconstruction error on validation data and use early-stopping. We list additional specifications which depend on each dataset.
21

---

Causal Discovery from Conditionally Stationary Time Scries
In springs and magnets data with determined states we train for 1000 epochs using batch sizes of 100, 50, and 20 for N being 5, 10, and 20 respectively. For recurrent states, the GNN-RNN network restricts GPU capacity, and we adapt the number of epochs and batch size to perform 200k iterations, and decaying the learning rate every 60k iterations.
In gene regulatory network data, in the determined state setting we reduce the batch size to 10 meet GPU capacity and train for 1000 epochs. For recurrent states, we lower the batch size to I due to the increased number of variables, and train for 200 epochs (200k iterations), similarly to the springs and magnet case. In all settings, we use 2 edge-types and a sparsity regularisation of 0.9 using Pew.
In NBA data, we train for a total of 450k iterations due to the large number of samples, with batch size of 100 and decaying the learning rate every 200k iterations. We find both SDC and ACD perform best using 2 edge-types and a sparsity regularisation of 0.8 using Pv...
The decoder is trained with teacher foreing every 10 time-steps, i.e., it receives the ground-truth as input every 10 time-steps.
The variance of the decoder Gaussian distribution is o² = 5 10-5 The temperature term of the edge label encoder is set to 0.5. The state encoder temperature y follows a schedule similar to Ansari et al. (2021) which prevents state collapse, i.e. the model ignoring states. We first set ry = 5, and decrease temperature every epoch by factor of 0.8 until we have y = 0.5.
VRNN. The experiments with NBA player trajectories consider VRNN as a non-causal baseline to compare forecasting performance. Below we specify the network architecture and training scheme. To allow a fair comparison between SDCI, ACD, NRI, and VRNN, we modify the decoder defined in Chung et al. (2015) to condition the player positions on the ball features, similarly as we did for the previous models: pe (xre Zgr, b,), where b; E IR represents the ball features at time (3D position and velocity). The architecture of the model follows the original work: 3-layer LSTM networks with 256 dimensions and latent space size of 128 dimensions. The encoder and decoder architectures use two-layer MLPs of 256 dimensions. The models are trained using ADAM (Kingma & Ba, 2015) for 350K iterations with a learning rate of 10 and batch size 32.
NRI-MPM. We train our NBA player trajectory model by using the first 100 time steps of player and ball trajectories as input and predicting the next 100 time steps. Our experimental setup follows the settings outlined in (Chen et al., 2021). The NRT model trained with both the encoder and decoder using GRU- and Attention- based architectures for edge type [2, 4). Training is conducted over 500 epochs with batch size of 128. The initial learning rate is set to 2.5 10-5 and is decayed by a factor of 0.5 every 200 epochs. We use a temperature parameter 7 0.5, and all hidden layers across the model have a dimension of 256. During training, the model predicts M 20 future time steps at each iteration.
Rhino. For GRN and springs, we tune the hyperparameters of Rhino based on the validation RMSE error. Our experimental setup follows a similar configuration to (Gong et al., 2023), with the key difference that we use single MLP layer with 15 hidden units for the function f.. We train the model using a batch size of 128 and an initial learning rate of 0.001, optimized with Adam. The node embedding dimensions are set to 32 and 16 for each respective dataset. Additionally, we use lag = 1, auglag = 60, and apply sparsity penalty X of 19 and 25 for the two datasets, respectively.
N-GC. For Neural Granger causality (Tank et al., 2021), we use the official implementation based on MLPs. We set the default hyperparameter settings, which include large training runs with early stopping; and used MLPs with 256 hidden units.
R-PCMCI. Regime-PCMCI does not support batch mode. This implies the algorithm needs to be re-trained for each sample, and we take the average summary graph across all the samples. Given available official code implementation (Saggioro et al., 2020), exploring hyperparameter settings resulted into errors from training with short sequences (T = 50). We use the predefined hyprraarameters and select regimes to align with the number of components in the backbone state network used in GRN data.
C. Datasets
In this section we provide detailed information about the datasets used in this work. For spring data, we generate 10000 samples of each setting for training the models. Regarding testing, we compute all the metrics using 100 samples, and we note that Rhino and Neural Granger Causality require retraining for data with variable graphs across samples.
22

---

Causal Discovery from Conditionally Stationary Time Scries
C.I. Springs and Magnets
When considering springs and magnets with directed connections, we follow the generation procedure described Kipf et al. (2018) with a small modification where the spring interaction between pair of particles can change over time (depending on state variables), and the addition of magnetic interactions. This assumes setup with n. = 3, describing no-edge, and spring or magnetic effects.
In this dataset, N particles are simulated inside a 2D box where they can collide elastically with its walls. Each pair of variables is connected by a spring with uniform probability. To allow for identification of causal connections (directed edges), the connection is made unidirectional. The spring interaction follows the Hooke's law, and the magnetic interaction follows a standard repulsive magnetic pole model. These interactions are captured in terms of third order moments and aggregated following the second Newton's law by summation of forces:
fu = - (wwx=1)) - -r²) + 1 (w)ea=
(r. rr
Byg. Di = (r. (x), r E
(8) 86
(66)
4m
where edge-types I and 2 are associated to spring and magnetic effects respectively. C, is the unidirectional interaction from particle j to particle i, and it denote the 2D position and velocity of each particle. The continuous variable x; is constructed by concatenating the position and the velocity measuremenss. Notice that the above equation defines the evolution of the continuous variable for single time-step. In setting, have that k .(ب) Thus, fly will change over time, contrary to Kipf et al. (2018).
To generate samples, we first generate random labels of conditional effects W and the initial location and velocity. The sparsity of the structure is set to 0.5, 0.7, and 0.8 when considering 5, 10, and 20 variables respectively. Then, trajectories are simulated by solving the previous differential equations using leapfrog integration. The step size used is 0.001 and the trajectories are obtained by sub-sampling each 100 steps. In our experiments, we set T = 80. When considering determined, for 4 states, where yp injectively assigns integers to tuples. For recurrent states, we consider K 2 and alternate states on wall collision.
we set sf 1, (n [0)
for 2 states; and of sp(( (r())=0) ( >of
C.2. Gene Regulatory Networks
Gene expression data was generated with DynGen (Cannoodt et al., 2021). The simulation engine includes different types of backbone state networks, namely bifurcation, eyclic, or single line networks. We choose a bifurcating network with 4 state modules and 2 bifurcations; with total of 49 genes, including 16 target genes and no housekeeping genes. Target genes are characterised by not taking part of the activation/deacciiationn regimes and only receive interactions from genes associated to states. A synchronised experiment was simulated with 50 time steps and for 1000 cells. Real sequencing experiments cannot measure the same cell over time and simulation engines typically sample different populations of cells at every time step. However, facilitating causal discovery require that the gene expression of the same cell is measured over time. To obtain this, the model's i simulated mRNA counts were used directly. As mentioned, used meta-data from the backhone state transitions as auxiliary information to SDCI in the observed case.
C.3. NBA Data
The NBA dataset (Linou, 2016) consists of recordings from 632 NBA games played during Winter 2015-2016. Each game is composed by approximately 400 to 600 events, which represents sequences of plays. In each trajectory, we find information about the ball location and 5 players of the 2 different teams (10 in total). The coordinates of the ball and players are represented in 3D and the length of each sequence can vary from 100 to 600. In our experiments, we consider a sequence up to 200 time-steps (T = 100 for reconstruction and the rest 100 steps for prediction), which gives us a total training dataset of 150K samples and a test set of 6380 samples. Data inspection shows that the court size is 100 x 50, and we use this information to standardise the data. For experiments with SDCI with observed states, design some ground-truth states which depend on different locations of the court. We set K 4 and our choice is shown in figure 14.
Data extracted from the following cade repository https: httpppp:////ttttbbb com www.o/mmmnook2...mm / Plyyer--aaa Moveer--- last accessed 2022-09-28.
23

---

Causal Discovery from Conditionally Stationary Time Scries
1.0
1.0
5 Variables Variables
Variables
1.0
Variables
0.9
20 Variables
Edge accuracy
ACD
Edge accuracy
Variables
ACD
0.9
0.8
0.7
Edge
0.7
0.6
0.5
0.6
0.5
2
1 5 10
20
50
100
5
10
20
State values (K)
Train data percentage (%)
Num. variables (data)
(a) Increasing variables and states.
(b) Data efficiency.
(c) Generalisation.
Figure 15: Spring data with observed states for (a) increasing variables and state values, (b) data efficiency, and (c)
generalisation, where the x-axis indicates the test data and the legend indicates the model used. SDCI results are shown with solid lines.
D. Comments on Evaluation Metrics
D.1. Summary Graph Estimation
For multi-dimensions. data such as springs, estimate the summary graph of Rhino and N-GC by grouping elements together, and for each element we include an edge any of its dimensions has interactions with other elements.
50
D.2. Fi Scores
20
To clarify, the evaluation of the summary graph considers the micro averaged F1 score, to account for increased sparsity on increasing variables. For edge labels W and states 81:7, we use macro averaged Fi score, no restrictions on proportion of labels are made.
10
20
100
D.3. Computing the Summary Graphs
Figure 14: Hand-crafted ground-truth state map on NBA data which is forwarded to SDCI with observed states. Colours indicate different states.
Notice that SDCI can extract the conditional summary graph (CSG) whereas the baselines we compare with only consider the summary graph (SG). Consequently, the only immediate way compare the performance in capturing the causal structure among the methods we consider is to evaluate the latter. From the definition of summary graph, we deduce that one can estimate it by taking the union of the graphs in the CSG. This is used to compute the summary graphs of both SDCI and the ground truth structure the generative process.
E. Additional Results
In this section report additional experiments and qualitative visualisations, which can be helpful to complement the main results from Section 6 in the main text..
E.1. Springs and Magnets
Observed In this experiment the states are known and independent from the observations. For the ground truth dynamics, the state transitions incrementally into the next one every 10 time-steps. We report accuracy with respect to the edge lables W, and consider 2 edge-types. Figure 15a shows results with increasing variables and increasing states, where we compare with ACD (dashed lines) as a stationary baseline. Although performance drops as K increases, SDCI able to maintain reasonable accuracy in edge-type identification in comparison to the stationary baseline. With increasing number of variables both approaches see accuracy drops; our hypothesis that this can be addressed by increasing model capacity. The next test
24

---

Causal Discovery from Conditionally Stationary Time Scries
considers data efficiency of SDCI with results reported in Figure 15b. We that both SDCI and ACD are data efficient in this scenario, where training 10% of the data returns good performance already. Finally, also report in Figure 15c generalisation unseen data with different number of variables. Here both methods generalise better to settings where the number of variables is similar to the ones they were trained.
Determined states of both SDCI and ACD as well as the corresponding conditional summary graphs and summary graphs extracted by both methods respectively. We observe SDCI produces accurate causal graph estimates. Regarding time series forecasting, our method is able make reasonable predictions. Notice that to train the models, we use teacher foreing every 10 time-steps, which means that the learned models less suited for long-term dynamics modelling. However, one can expect obtain more accurate predictions by progressively reducing the teacher forcing frequency during training. Considering ACD, despite being restricted by assuming stationary time series, it still infers graph structures that allow the model to produce adequate forecasts.
We provide visualisations for the determined states case in Figure 17, where we show the predictions
E.2. NBA Data
To further analyse the representations learned by SDCI, visualise additional examples in Figure 16. The extracted graphs exhibit similar patterns to those presented in the main text. In the first example, the blue team is on offense, and we observe a higher presence of edges from the defending team. A similar pattern can be seen in the second example, where the red team takes the offensive role instead. Overall, SDCI assigns regimes with distinct sparsity patterns, effectively adapting to the nonstationary nature of the data.
25

---

Causal Discovery from Conditionally Stationary Time Scries
5
2
Figure Examples of extracted conditional summary graphs from SDCI for K 4, with states determined by the position and velocity the players. Each row describes different sample.
26

---

Causal Discovery from Conditionally Stationary Time Scries
Predictions
Conditional summary graph
Summary graph
Grouhd-truth
SDCI
ACD
State
AC33
SOCI
State 9
State
ACD
SOCI
State
State
GT AC3
State
State
ACO
SOCI
Figure 17: time series forecasting (left, dotted lines) of SDCI and ACD for 50 time-steps along with the ground-truth. We use solid lines denote the input the models and the background color represents the state value. We show the associated conditional summary graph (center) and summary graph (right) of SCDI (red) and ACD (blue) respectively along with the ground-truth (GT, black) for each sample. Each row represents different sample.
27


Reviews:
[{"review_id": "vD4mvbsJPk", "reviewer": "Reviewer_qXnG", "summary": "This paper presents a new framework for solving the causal discovery problem in non-stationary sequences. This paper makes certain assumptions under the non-stationary condition, and then proposes the new method Conditional summary graph for representing causality, and the method for conducting causal discovery state-Dependent Causal Inference. The paper provides identifiability analysis for the key steps of its approach, validating SDCI methods on semisynthetic data based on physical and biological systems and real-world datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s time and thoughtful feedback. We are glad they find our framework innovative and acknowledge its significance in handling nonstationary time series. Below, we address the key concerns raised in the review.\n> ... if the actual data cannot meet the premise, may lead to model failure.\n\nSDCI is explicitly designed for conditionally stationary time series, with applications in interactive systems (e.g., sports) and Gene Regulatory Networks (GRNs). However, our theoretical results are **broader**, covering:\n- Markov Switching Models (m1-m3): Theorem A.6.\n- Conditionally stationary time series (m1-m4): Theorem A.7.\n- SDCI (m1-m5): Corollary A.8.\n\nWe develop theoretical results starting from a very general case to our specific implementation, SDCI. These results, A.6 and A.7, provide a **general foundation** for regime-dependent causal discovery.\n\nWe would like to note that identifiability in regime-dependent time series is a **very challenging** problem with only recent contributions [1]. Importantly, our results make no assumptions on state dependencies, and introduce a **novel proof technique** based on classic finite mixture model theory (Thm. A.6). We will incorporate a discussion emphasizing our theoretical scope in contrast with related work (see Reviewer Fbj4 for additional details).\n\n[1] Balsells-Rodas, et al. \"On the identifiability of switching dynamical systems.\" ICML 2024.\n\n\n> … scalability of experimental validation is not fully demonstrated.\n\nWe acknowledge this concern and will include additional runtime analysis in the appendix to illustrate SDCI’s linear scaling with respect to $K$. We will also compare state inference times across “determined” and “recurrent” scenarios.\n\n\n> NBA data are only mentioned in context, lacking detailed experimental design and outcome analysis\n\nWe provide details on training in Appendix B.4 (lines 1097-1099) and dataset preprocessing in Appendix C.3. These details were deferred to the appendix to focus on the interpretability of learned structures.\n\n> … this paper does not need to know the number of K mentioned in Remark 4.2, but in experiment 3, the movement trajectory needs to do two groups …\n\nOur identifiability results do not require knowledge of $K$, which implies we can determine $K$ via model selection (assuming convergence to MLE). This is a significant contribution, as other related works require knowledge of $K$ (with exception of [1]) and cannot rely on this idea.\n\nHowever, selecting $K$ in practice is a well-known challenge even in non-temporal settings. We can use the “elbow method” (as in K-means), or similar heuristics. Below we show results for synthetic springs and magnets with $K=2$ where reconstruction MSE plateaus for $K=2$.\n\nhttps://postimg.cc/k2rFZkBp\n\nOur discussion regarding results on $K=2$ and $K=4$ aimed to show that both values provide meaningful interpretations. Figure 9 (forecasting results) shows similar performance for $K=2$ and $K=4$, suggesting $K=4$ overfits the data in this scenario. \n\nWe acknowledge selecting $K$ is an important challenge, and will \n- include a discussion on how to select $K$ in practice, showing figures similar to the above, including a setting with $K=4$.\n- discuss how this applies to NBA data.\n\n> the targeted validation is not designed in the experiment (such as the convergence test under different data quantities) …\n\nFigure 4 shows that SDCI achieves 100% $F_1$ score when the graphs are fixed, demonstrating consistency empirically. For samples with different graphs, the challenge relies on the approximate posterior design $q(W|x_{1:T})$. The identifiability results support structure learning from purely unsupervised data, which for this setup is very challenging.\n\nWe provide dataset size variation results for observed states in Appendix E.1, Figure 14. Below, we show similar results for fixed graphs on \"Recurrent states\" with $N=5$ and $K=2$, which will be included in the appendix:\n\n| $\\|\\mathcal{D}\\|$              | $\\mathcal{W}$ $F_1$ score | State $F_1$ score |\n| ---------------- | :---------: | :-------: |\n| 10        |   0.65   | 0.524 |\n| 100           |   0.875   | 0.543 |\n| 500    |  1.00   | 0.857 |\n| 1000 |  1.00   | 0.884 |\n| 5000 |  1.00   | 0.891 |\n\n**Actions**\n\nTo improve our manuscript (see other Rebuttals for details), we aim to:\n- Clarify notation and revise typos.\n- Provide intuitions from [2] in our Proof for Theorem A.6.\n- Contrast our method assumptions with prior works, emphasizing our broader theoretical scope.\n- Expand the discussion on assumptions and implications to real-world data.\n- Provide details for $K$ selection, and clarify NBA data.\n- Clarify scalability and include runtime analysis in Appendix.\n- Include figures for increasing data sizes on fixed graph data in Appendix.\n- Modify Figure 5b to include additional variables.\n\nWe appreciate the reviewer’s constructive feedback and believe these revisions will further improve the paper.", "claims_and_evidence": "The paper mainly focuses on the causal discovery problems under new and more lenient conditions. The feasibility of the proposed method is tested through theoretical identifiability analysis and experimental testing.", "methods_and_evaluation_criteria": "The conditions assumed in this paper are mainly that the dependence of the state dependence can be decomposed into the superposition of the dependence of various features. This assumption can indeed be satisfied by prior knowledge in certain realistic scenarios. Therefore, the proposed method expands the application scope of causal discovery in the time series, which has significance.", "theoretical_claims": "No", "experimental_designs_or_analyses": "The experimental design of this paper revolves around the causal discovery of conditional stationary time series, and mainly verifies the proposed SDCI framework from the simulation system (spring-magnet), gene regulation network (GRN) and real data (NBA). Covering the simulation, synthesis and real data scenarios, the physical mechanism is verified by the spring system, and the applicability of the biological network is verified by GRN, reflecting the universality of the method. The comparison methods include traditional methods (R-PCMCI, Neural Granger Causality) and leading hidden variable causal models (ACD, Rhino), covering different methodological systems. However, NBA data are only mentioned in context, lacking detailed experimental design and outcome analysis, which may weaken the credibility of the method in real scenarios. In addition, the paper mentioned that the consistency (consistency) of SDCI is still an open problem, but the targeted validation is not designed in the experiment (such as the convergence test under different data quantities), and the theoretical advantages are not fully translated into empirical results.", "relation_to_broader_scientific_literature": "All causal discovery papers require assuming certain conditions, which are often too strict for realistic scenarios to make the method inapplicable, and so many studies are devoted to relaxing these conditions. Starting from this goal, this paper studies the causal discovery problem under new and more relaxed conditions.", "essential_references_not_discussed": "As far as I known, it's no problem.", "other_strengths_and_weaknesses": "The main advantage of this paper is the method of causal discovery from conditional stable time series, which provides new ideas for solving the limitations of traditional causal inference in handling non-stable data, especially in handling causal relationships in complex systems or dynamic environment. The method is innovative in theoretical framework or algorithm design to capture more hidden causal patterns. However, the disadvantage of the paper is the strong dependence on the \"conditional stability\" assumption, which, if the actual data cannot meet the premise, may lead to model failure. Moreover, the computational complexity or scalability of experimental validation is not fully demonstrated.", "other_comments_or_suggestions": "No", "questions_for_authors": "Why is it that the work of this paper does not need to know the number of K mentioned in Remark 4.2, but in experiment 3, the movement trajectory needs to do two groups: K=2 and K=4, and the results of the two groups are different?", "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": "", "extra_scores": {}}, {"review_id": "5kAqCHpve7", "reviewer": "Reviewer_Fbj4", "summary": "This paper introduces State-Dependent Causal Inference (SDCI), an approach for causal discovery building on VAE-based approaches in nonstationary time series characterized. SDCI leverages a \"conditional summary graph\" to compactly represent state-dependent causal structures and establishes identifiability guarantees under specific state-dependency assumptions.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's thoughtful comments. Below, we address the key concerns raised in the review.\n\n> It is unclear how the proposed method is different from existing methods...\n\nWhile prior works [1-3] also consider discrete latent variables for modeling nonstationary time series, our method has **three key advantages:**\n\n- **No assumption of known number of states:**\n  - Most previous works, including HMM-ICA [1] and CtrlNS [2], assume the **number of states is known**.\n  - Our work leverages Yakowitz & Spragins (1968) [4], which enables identifiability **without** knowing the number of states. This allows for model selection to determine $K$, an aspect theoretically impossible in prior approaches.\n- **No assumptions on state dependency:**\n  - Prior works often assume that **state transitions independent of observations** (e.g., HMM-ICA [1], [3]).\n  - Recently, NCRTL [2] models **direct observation-to-state dependencies**, but requires **stronger assumptions** (e.g., mechanism sparsity, known $K$).\n  - Our proof technique requires no assumptions in terms of state dependencies, allowing feedback from observations.\n- **Regime-dependent identifiability**\n  - While we provide identifiability for SDCI in the main text (m1-m5), our results provide a **broader scope** with general identifiability results for regime-dependent time series (m1-m3) in Theorem A.6. \n  - In Thm. A.6 we present a **novel proof technique** leveraging Yakowitz and Spragins (1968) [4]. This result can be of independent interest.\n  - Strategies based on [1] **cannot solve this problem**, as their proof strategy prohibits explicit autoregressive dependencies from $x_{t-1}$ to $x_t$.\n\nWe will explicitly incorporate this discussion in the revised manuscript.\n\n[1] Hälvä, Hermanni, and Aapo Hyvarinen. \"Hidden markov nonlinear ica: Unsupervised learning from nonstationary time series.\" UAI 2020.\n\n[2] Song, Xiangchen, et al. \"Causal temporal representation learning with nonstationary sparse transition.\" NeurIPS 2024.\n\n[3] Balsells-Rodas, Carles, Yixin Wang, and Yingzhen Li. \"On the identifiability of switching dynamical systems.\" ICML 2024.\n\n[4] Yakowitz, Sidney J., and John D. Spragins. \"On the identifiability of finite mixtures.\" AMS 1968.\n\n> it is still unclear how to ensure the assumptions hold?\n\nAligning data with assumptions is a key challenge in causal discovery and ICA. Our assumptions are as follows:\n- (m1-m5): Our model design is inspired by interactive systems, and physical models (e.g. sum of forces). \n- (a1) Unique Causal Structures Across States: Each variable must have distinct causal interactions per state.\n- (a2) Functional Faithfulness: Discussed in lines 248–253. It can be achieved by using smooth functions (e.g. analytic functions), which are commonly assumed in EEG or Gene expression data.\n\nFor semi-synthetic datasets, the assumptions are simple to verify due to access to the groundtruth dynamics. In real-world data, expert knowledge is required. Assumption violations can break identifiability, which would invalidate interpretability. We discuss these issues in Section 6.3 and will expand on them in revision.\n\n> does the proposed algorithm satisfy all the required assumptions  \n\nYes, SDCI is designed to incorporate these assumptions:\n- (m1-m5) & (a2.1): Enforced via a GNN architecture and the no-edge effect (i.e. $w_{ijk}=0 \\to f_0:= 0$).\n- (a1): Date-dependent, independent of algorithm design.\n- (a2.2): Ensured via analytic activation functions (e.g., Softplus, Cosine) in the edge-type mechanisms.\n\nWe will enhance the discussion on how SDCI aligns with these assumptions in the final version.\n\n> The number of variables (N=3, 5) is too small \n\nSee the figure below for an additional column with $N=10$ in Figure 5b. Increasing $N$ in time series causal discovery is challenging due to the temporal component.  In our setting, the total data dimensionality is $N \\cdot d$ ($N\\cdot 4$ in springs and magnets), but complexity also increases with $K$ and $T$.\n\nhttps://postimg.cc/mzznGYhz\n\n**Actions**\n\n\nTo improve our manuscript (see other Rebuttals for details), we aim to:\n- Clarify notation and revise typos.\n- Provide intuitions from [2] in our Proof for Theorem A.6.\n- Contrast our method assumptions with prior works, emphasizing our broader theoretical scope.\n- Expand the discussion on assumptions and implications to real-world data.\n- Provide details for $K$ selection, and clarify NBA data.\n- Clarify scalability and include runtime analysis in Appendix.\n- Include figures for increasing data sizes on fixed graph data in Appendix.\n- Modify Figure 5b to include additional variables.\n\nWe believe these revisions will strengthen the paper and appreciate the reviewer’s constructive feedback.", "claims_and_evidence": "Yes, the claims are generally supported by experiment, though there are some gaps. In particular, the paper claims that it relaxes the assumptions of causal discovery for nonstationary time series, but it lacks a clear discussion on it.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria are well-suited for the problem of causal discovery from nonstationary time series.", "theoretical_claims": "The theoretical claims in this paper seems correct. However, the proposed results seem not much related to the proposed algorithm.", "experimental_designs_or_analyses": "Yes, the experimental designs and analyses are partial sound. Howeve, experiments are somewhat weak, e.g., the number of variables (N=3, 5) is too small in the recurrent states and varying structures experiment.", "relation_to_broader_scientific_literature": "This paper related to the causal discovery literature.", "essential_references_not_discussed": "Most enssential references are discussed.", "other_strengths_and_weaknesses": "Strengths:\n\n- It developed a novel VAE and GNN-based framework to build the proposed method.\n\nWeaknesses:\n- The main issue is that the setting of introducing discrete latent variables to modeling nonstationary time series is not new [1]. This work claims that it relaxing assumption under such setting, but does not provide a clear discussion on how it relax the assumption. It is unclear how the proposed method is different from existing methods under the same setting.\n- Although some theoretical results are developed, it is still unclear how to ensure the assumptions hold? \n- Moreover, does the proposed algorithm satisfy all the requreied assumptions since there are some assumption on the function.\n\n[1] Hälvä, Hermanni, and Aapo Hyvarinen. \"Hidden markov nonlinear ica: Unsupervised learning from nonstationary time series.\" Conference on Uncertainty in Artificial Intelligence. PMLR, 2020.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See the weaknesses above.", "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": "", "extra_scores": {}}, {"review_id": "IIiadbzDJA", "reviewer": "Reviewer_5FGR", "summary": "This paper extends the existing work in time series causal discovery from stationary data to conditionally stationary time series data, which is stationary if conditioned on the latent states. The authors propose a conditional summary graph to represent the causal structure and give the identifiability results. Empirical experiments on semi-synthetic and real-world data show the superior performance over the baselines.\n\n## update after rebuttal\nI will keep my score after reading the response and the other reviews.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s feedback. Below, we address key concerns.\n>  There is room for the clarity/simplification of the notations.\n\nWe appreciate this point and will revise the manuscript for clarity.\n- Subscripts $\\psi$ and $\\phi$ denote parameters of the generative model and variational approximation, respectively. The generative model should always be indexed by $p_{\\psi}$\n- The outgoing structure $C_k^{i}$ contains variable indices, $1, \\dots, N$, while $PA_{s_{t-1}}(t-1)$ refers to function arguments (e.g. $x_{t-1}^{(i)}$). For time series, we consider the time index when computing densities at each time step $t$, and this is why we use $t-1$ as an argument to $PA$.\n\nWe will make sure the above is revised and address all noted typos.\n> but I am concerned with the contributions.\n\nOur theoretical results encompass three levels of generality. \n- Markov Switching Models (m1-m3): Thm. A.6\n- Conditionally stationary time series (m1-m4): Thm A.7\n- SDCI (m1-m5): Cor. A.8. \n\nOur paper explicitly studies the applications of SDCI to address nonstationarity. However, our scope in terms of theoretical results is **broader**, and our results from Thms. A.6 and A.7 could be of independent interest. Identifiability in regime-dependent time series is a very challenging problem with only very recent contributions [1], and importantly, our work makes no assumptions on state dependence.\n\nRegarding empirical contributions, Gene Regulatory Network (GRN) inference methods are typically validated with semi-synthetic data that mimics the underlying biological system, as validation through real-world cell systems is very expensive. SDCI design agrees with GRN literature and its ability to model gene activation/deactivation could be impactful in this domain. \n\n[1] Balsells-Rodas et al., \"On the identifiability of switching dynamical systems.\" ICML 2024.\n\n**Theoretical Claims and Q1**\n\nAll proofs are original. Theorem A.6, leverages Yakowitz & Spragins (1968) [2], also used in [1]. We note **key differences**:\n- We allow dependencies from $x_{1:t}$ to $s_t$, strictly prohibited in [1]. \n- Our weaker assumptions require a **novel proof strategy** resolving permutation equivalence issues from Yakowitz & Spragins (1968) result.\n- Our strategy addresses identifiability from **conditional distributions** $p(x_t| x_{1:t-1})$, while [1] considers the **joint distribution** $p(x_{1:T})$.\n\nIdentifiability in finite mixtures relies on function linear independence [2]. For Gaussian families, this holds if means or covariances are distinct. We ensure this by assumption (a1). We will clarify the above in the appendix, and plan to include a discussion comparing other works in the main document (see Reviewer Fbj4).\n\n[2] Yakowitz and Spragins. \"On the identifiability of finite mixtures.\" AMS 1968.\n\n\n\n**Reviewer’s questions:**\n\nQ2: Conditional effect labels improve scalability in conditionally stationary time series. SDCI, inspired by interactive systems (e.g. NRI, ACD), learns diverse graphs from limited types of interaction types $n_{\\epsilon}$. Example: in sports data, different samples may have distinct graphs, but all interactions could be categorized as \"no interaction,\" \"aggressive,\" or \"defensive.\"\n\nQ3: \n- Eq. (5): $f_{s_{t-1}}^{(j)}$ in is indexed by $s_{t-1}$ leading to $K^N$ functions definitions, which is prohibitively expensive.\n- Eq. (8): We use GNNs with pairwise interactions and an aggregator function, reducing complexity, and we prove identifiability of the labels under this setting.\n- SDCI considers (m1-m5), but we also prove identifiability considering weaker cases (m1-m4), allowing alternative solutions.\n\nQ4:\n- We require no knowledge of $K$, unlike most mixture model results on time series. \n- This allows finding $K$ via model selection (assuming convergence to MLE), which is theoretically impossible if $K$ requires to be known. \n- In practice, standard techniques such as the “elbow method” (used in K-means) can be applied. See the figure below for model selection with true $K=2$ in the springs and magnet data, where reconstruction MSE plateaus at $K=2$.\n\nhttps://postimg.cc/k2rFZkBp \n\nWe plan to expand on selecting $K$ in the Experiments section, showcasing also $K=4$ in the springs and magnets data.\n\n**Actions**\n\nTo improve our manuscript (see other Rebuttals for details), we aim to:\n- Clarify notation and revise typos.\n- Provide intuitions from [2] in our Proof for Thm. A.6.\n- Contrast our method assumptions with prior works, emphasizing our broader theoretical scope.\n- Expand the discussion on assumptions and implications to real-world data.\n- Provide details for $K$ selection, and clarify for NBA data.\n- Clarify scalability and include runtime analysis in Appendix.\n- Include figures for increasing data sizes on fixed graph data in Appendix.\n- Modify Figure 5b to include additional variables.\n\nWe sincerely appreciate the reviewer’s insights and believe these revisions will significantly improve the paper.", "claims_and_evidence": "The claims made in the submission (e.g. establishing the identifiability for the conditional summary graph and related structural properties) are supported by the clear definition (Def. 4.1), reasonable assumptions, and rigorous theoretical results (Thm. 4.3). The experimental results, conducted under the authors’ specified settings, provide convincing empirical validation. However, providing more real-world examples for the three classified scenarios of states would improve the paper’s practical relevance.", "methods_and_evaluation_criteria": "Overall, the proposed State-Dependent Causal Inference (SDCI) framework makes sense for the problem of causal discovery in conditionally stationary time-series data. The probabilistic formulation, graph-based modeling, and variational inference provide a compelling approach. However, the clarity of the notations and the derivations of the formulations could be further improved.", "theoretical_claims": "Overall, the proofs provided for the Thm. A.6, Thm. A.7, and Corollary A.8 seem correct. The reasoning effectively utilizes key assumptions to establish partial identifiability up to permutation equivalence. Some minor refinements could further enhance accessibility and readability. \n\n1.\tThe theorem appears to rely on several existing results. Providing clearer references or explanations in the appendix regarding the specific works used would enhance clarity and attribution. \n\n2.\tAdditionally, for the identifiability of finite Gaussian mixture, does it need any regularity assumptions? Please clarify these assumptions if you are going to use the results.", "experimental_designs_or_analyses": "The experimental design is well-structured and appropriate, leveraging both semi-synthetic and real-world data. Careful modifications and adjustments have been applied to the datasets to ensure smooth comparisons. However, the evaluation criteria could be clarified further. For example, in Fig. 6, does the fixed graph correspond to the summary graph for the full-time graph, while the variable graph represents the conditional summary graph? Explicit clarification of these evaluation targets would enhance the interpretability of the results.", "relation_to_broader_scientific_literature": "This work is related to causal discovery for nonstationary time-series and multi-domain data (Yao, 2022; Varambally, 2024; Song, 2024; Huang, 2015, 2019, 2020; Gong, 2022; Zhang, 2017; Ghassami, 2018). The conditional summary graph proposed by the authors provides a more compact representation than the full-time and regime-dependent graphs. The identifiability results over hidden latent states are novel.\n\nReferences:  \n1. Yao, W., Sun, Y., Ho, A., Sun, C., and Zhang, K. Learning temporally causal latent processes from general temporal data. In International Conference on Learning Representations, 2022.   \n2. Varambally, S., Ma, Y., and Yu, R. Discovering mixtures of structural causal models from time series data. Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 49171–49202. PMLR.  \n3. Huang, B., Zhang, K., and Scholkopf, B. Identification of time-dependent causal model: A gaussian process treatment. In Twenty-Fourth international joint conference on artificial intelligence, 2015.  \n4. Huang, B., Zhang, K., Gong, M., and Glymour, C. Causal discovery and forecasting in nonstationary environments with state-space models. In International Conference on Machine Learning, pp. 2901–2910. PMLR, 2019.  \n5. Huang, B., Zhang, K., Zhang, J., Ramsey, J. D., SanchezRomero, R., Glymour, C., and Scholkopf, B. Causal discovery from heterogeneous/nonstationary data. J. Mach. Learn. Res., 21(89):1–53, 2020.  \n6. Gong, W., Jennings, J., Zhang, C., and Pawlowski, N. Rhino: Deep causal temporal relationship learning with history-dependent noise. In NeurIPS 2022 Workshop on Causality for Real-world Impact, 2022.  \n7. Zhang, K., Huang, B., Zhang, J., Glymour, C., and Scholkopf, B. Causal discovery from nonstationary/heterogeneous data: Skeleton estimation and orientation determination. In IJCAI: Proceedings of the Conference, volume 2017, pp. 1347. NIH Public Access, 2017.  \n8. Ghassami, A., Kiyavash, N., Huang, B., and Zhang, K. Multi-domain causal structure learning in linear systems. Advances in neural information processing systems, 31, 2018.", "essential_references_not_discussed": "I did not identify any missing essential references, though further discussion on related work in causal identifiability for time series data could be beneficial.", "other_strengths_and_weaknesses": "Strengths:  \n1.\tThis paper is original for its proposed setting (stationary time-series when conditioned on states). Based on the identifiability of Markov switching models, the identifiability of this model is also guaranteed.  \n2.\tThis work is significant since it extends the stationary time-series to a broader setting.  \n\nWeaknesses:  \n1.\tThere is room for the clarity/simplification of the notations. For example,  it is hard to differentiate a real probability density from an estimated one. Especially in Section 3.3, $p$, $p_{\\psi}$, and $q_{\\phi}$ confused me.  \n2.\tThe work seems like a compact version of the regime-dependent graph, which also considers the time-series data in a conditional stationary setting. The identifiability results are impressive, but I am concerned with the contributions.", "other_comments_or_suggestions": "Some typos:  \n1.\tLine 146\\~147, right side, “the parent of $x^{(2)}\\_2$ are …” lost a “{“.  \n2.\tLine 217, left side,  “we can guide $\\psi_\\omega$ though” -> through.  \n3.\tLine 738 (a2.2), “, the following set has zero measure:”, where is the following set?  \n4.\tLine 1022~1023, what’s behind “=”?  \n5.\tThe citation format is inconsistent in the Related Work part.  \nI found the notations not that clear, e.g., an explicit footnote about $j\\in C_k^{(i)} \\iff x_{t-1}^{(i)}\\in PA_{s_{t-1}}^{(j)}(t-1), s_{t-1}=k$ and the reason why PA should take t-1 as input but $C$ should not, might be rather helpful.", "questions_for_authors": "1.\tIs the proof of Thm. A.6 originally derived by the authors, or is it adapted from existing work?  \n2.\tWhy do you propose labels of conditional effects? It seems just to work as a compact representation of the existence of edges. Could you please give a more intuitive explanation for $f_{e_i}$ in Eq. (8)?  \n3.\tWhat’s the difference between two $f_{s_{t-1}}^{(j)}$s in Eq. (5) and Eq. (8)? The authors claim Eq. (8) reduces the exponential complexity of Eq. (5), but it’s bearly clear to me.  \n4.\tHow did you learn the $K$ in your implementation?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: **Summary**: The paper shows identifiability results and GNN based VAE architecture that learns multiple causal graphs one for each latent state conditioned on which the observed time series is stationar, i.e. fixed Granger causal functional relationships. Authors prove identifiability results for Markov Switching models which are mixtures of stationary time series (with sparse Granger causal relations between previous discrete time and the current time) and many other generalizations even when the unobserved latent variable support is not known.

Authors propose a GNN based VAE framework that extends the previous amortized causal discovery work of Lowe et al..2022 where some extra assumptions of functional relationships are made to make it suitable for an edge-edge message passing framework on an GNN. Authors prove identifiability results for that specific modeling assumption.

**Concerns**: Concerns that were raised is that even in time series, non linear ICA results resolving the mixture of stationary time series were proven. So why is the current work different ? Authors responded by saying that their identifiability results do not require the support of the latent states to be known and relies on a 1968 result about finite mixtures of multi variate gaussians. Further, authors show empirically they outperform or match ACD which has lots of overlap in terms of architecture in many datasets. 

Further, evaluations were not one sided with only comparisons with neural granger methods line of work alone but rather also includes R-PCMCI which is a constrained based Grange causal discovery method that does handle regime dependent time series. 

**Overall**:  (I read the paper in some detail before coming to this conclusion) Authors very general identifiability results without knowing latent support and adaptation of GNN based VAE from prior work to solve for Granger causal relationships with conditionally stationary time series is noteworthy. Experimental evaluation (during rebuttal and in the paper) also look comprehensive. I encourage the authors to release their code base for future works to compare to theirs. I recommend accept
Decision: Accept (poster)