Signature Kernel Conditional Independence Tests in Causal Discovery for Stochastic Processes
Authors: Georg Manten
Cecilia Casolo
Emilio Ferrucci
Søren Wengel Mogensen
Cristopher Salvi
Niki Kilbertus
Venue: ICLR 2025 Spotlight (2025)
Keywords: causality
dynamical systems
stochastic processes
causal discovery
signature kernel
Primary area: causal reasoning
TL;DR: We develop a kernel-based conditional independence test on ‘path-space’ and constraint-based causal discovery algorithms for SDE solutions that make use of the test for robust causal discovery.

Abstract: Inferring the causal structure underlying stochastic dynamical systems from observational data holds great promise in domains ranging from science and health to finance. Such processes can often be accurately modeled via stochastic differential equations (SDEs), which naturally imply causal relationships via `which variables enter the differential of which other variables'. In this paper, we develop conditional independence (CI) constraints on coordinate processes over selected intervals that are Markov with respect to the acyclic dependence graph (allowing self-loops) induced by a general SDE model. We then provide a sound and complete causal discovery algorithm, capable of handling both fully and partially observed data, and uniquely recovering the underlying or induced ancestral graph by exploiting time directionality assuming a CI oracle. Finally, to make our algorithm practically usable, we also propose a flexible, consistent signature kernel-based CI test to infer these constraints from data. We extensively benchmark the CI test in isolation and as part of our causal discovery algorithms, outperforming existing approaches in SDE models and beyond.

Published as a conference paper at ICLR 2025
SIGNATURE KERNEL CONDITIONAL INDEPENDENCE TESTs IN CAUSAL DISCOVERY FOR STOCHASTIC PROCESSES
Georg Manten" & Cecilia Casolo"
Technical University of Munich
Helmholtz Munich
Munich Center for Machine Learning (georg manten, cecilis secilia.c casolo) @tum.
Emilio Ferrucci
Søren Wengel Mogensen
Mathematical Institute
Department of Automatic Control Lund University swm fi cbs dk
University of Oxford
emilio. emilio.rossifi www..orrerreecciittttttttte ox. ac uk
Cristopher Salvi
Niki Kilbertus
Department of Mathematics
Technical University of Munich
Imperial College London
Helmholtz Munich
sasalvi aeviiiimperiii ac uk
Munich Center for Machine Learning niki. ki kilbertus us t.m. de
ABSTRACT
Inferring the causal structure underlying stochastic dynamical systems from obser- vational data holds great promise domains ranging from science and health finance. Such processes can often be accurately modeled via stochastic differential equations (SDEs), which naturally imply causal relationships via 'which variables enter the differential of which other variables'. In this paper, we develop condi- tional independence (CI) constraints on coordinate processes over selected intervals that Markov with respect the acyelic dependence graph (allowing self-loops) induced by a general SDE model. We then provide a sound and complete causal discovery algorithm, capable of handling both fully and partially observed data, and uniquely recovering the underlying or induced ancestral graph by exploiting time directionality assuming CI oracle. Finally, to make our algorithm practically usable, we also propose flexible, consistent signature kernel-basse CI test to infer these constraints from data. We extensively benchmark the CI test in isolation and part of our causal discovery algorithms, outperforming existing approaches in SDE models and beyond.
INTRODUCTION
Understanding cause-effect relationships from observational data can help identify causal drivers for disease progression in longitudinal data and aid the development of new treatments, act upon the underlying influences of stock prices to support lucrative trading strategies, or speed up scientific discovery by uncovering interactions complex biological systems such as gene regulatory pathways. Causal discovery (or causal structure learning) has received continued attention from the scientific community for at least two decades (Glymour et al., 2019; Spirtes et al., 2000; Vowels et al., 2022) with notable uptick in previous years particularly regarding differentiable score-based methods (Zheng et al., 2018; Brouillard et al., 2020; Charpentier et al., 2022; Hägele et al., 2023; Lorch et al., 2021; Annadani al., 2023; Zheng et al., 2020), building score matching algorithms (Rolland
Equual contribution

---

Published as a conference paper at ICLR 2025
et al., 2022; Montagna et al., 2023b;a), and other deep-learning based approaches (Chen et al., 2022; Ke et al., 2023; Yu et al., 2019; Ke et al., 2020). Many of these approaches aim at improving the scalability of causal discovery in the number of variables and observations well as incorporating uncertainty or efficiently making use of interventional data.
However, causal discovery from time series data has received much less attention and been mostly neglected in these recent advances. At a fundamental level, causal effects in dynamical systems can only 'point into the future', which should make causal discovery in time resolved data intuitively sim- pler. Nevertheless, except for restricted settings, this promise has not been realized methodologically and causal discovery in time series, especially for systems evolving in continuous time, remains a major challenge (Singer, 1992; Runge et al., 2019; Lawrence et al., 2021; Runge et al., 2023).
Data generating process. We assume data to follow a stochastic process X == (x) ..... X
with X taking values in Th (næ 2 1), and X satisfying the following system of stationary, path-dependent SDEs
xx = (X (. X =b for k [c] (1.....d) d)
+ - o.
We call this the SDE model. The subscript [0, at X means that n² (the 'drift') and o² (the 'diffusion') ) are functions of the entire solution up to time 6, i.e. they are defined on C([O, +20), R") (or some suitable subspace thereof), where n := my + ... + nd. Each W* is an ma-dimensional Brownian motion, and o maps to nu X ma-dimensional matrices. The noises W together with the (possibly random) initial conditions x1j are jointly independent. Therefore, the diffusion a of the entire system is block-diagonal (see equation 8). We refer to Rogers & Williams (2000) for details, Evans (2006) for a concise introduction, and Appendix A.2 for more intuition and discussion of the assumptions made here. Hence, the SDE together with distribution over initial conditions defines our data generating process. Individual observations are paths, which in practice translate to stochastic, potentially irregularly sampled time series observations for X [ú.2] with maximum observation time T, see Figure 1. Appendix A. contains an overview table of the notations used.
Induced causal graph. Eq. (1) naturally implies cause-effect relationships: we call E [d] parent of j E = [d] (i E paf) when either jet or σā is not constant in the i-th argument. These parental relationships define directed graph G (V. E), which we call dependence graph of the SDE model. The goal of causal discovery to infer the graph g induced by the SDE model from a sample of observed solution paths, depicted in Figure 1. Here, we only consider data generating processes leading to directed graphs without cycles of length greater than one (i.e., only 'loops' X + X are allowed). We still call these directed acyclic graphs (DAGs) for simplicity.
dxt = == of (Xpahlit
a (1x1,,9), ). )
Reteratio
Inhices
B
causal discovery
Limitations and requirements. The key limitation of our setting is the assumption of acyclicity (ex- cept for self-loops). We discuss fundamental issues arising from dropping the acyclicity constraint in Ap- pendix A.3. Further, we focus on stationary SDE models, i.e., the coefficients in eq. (1) are not explicitly time-dependent, motivated by the requirement that causal relationships do not change over time. Despite these limitations. our setting the first to simultancously satisfy the following criteria for causal discovery in continuous time systems: (a) It does not rely on the 'discrete-time" assumption, i.e., that all variables are observed at the same, typically homogeneously spaced, time points (neither in the underlying model nor the actual observations). Instead, different variables can be observed at different, irregularly spaced time points in our setting. (b) We can handle partially observed systems with unobserved confounders. (c) aath-dependence (1L", l may depend on the entire previous history X of paths), including delayed SDEs, is typically not captured in existing approaches (Peters et al., 2022). (d) Beyond "additive observation noise' it incorporates 'driving noise', where causal dependence may stem from the diffusion, not captured by the means of observed paths.
Figure 1: Illustration of causal discovery in the SDE model (A), leveraging conditional independencies in the observed samples (B) to infer the dependence graph of the SDE (C).
2

---

Published as a conference paper at ICLR 2025
Contributions. Our main contributions include (a) developing CI constraints on coordinate processes over selected intervals that we prove to be Markov with respect to the acyclic dependence graph (with self-loops) induced by general SDE model. (b) We then propose an efficient constraint based causal discovery algorithm and prove it to be sound and complete, assuming a Cl-oracle, for both fully and partially observed data. Unlike existing constraint based methods in static settings, our algorithm uniquely recovers the full underlying graph or induced ancestral graph by exploiting the direction of time. (c) Finally, we propose a flexible, practical CI test on path space, rendering our method highly practicable. (d) We extensively demonstrate the test's 's efficacy and achieve superior performance in causal discovery compared existing methods.
BACKGROUND AND RELATED WORK
Causal discovery on time series. While virtually all causal discovery methods on time series exploit that the direction of time constrains edges to point forward, except for Laumann et al. (2023), most existing work assumes observations be sampled on a regular time grid with discrete (auto-regressive) law. where past observations (Xt-7 ( determine the present X; = f(x Xx) for some fixed lag т, which can be seen as static structural causal model (SCM) over 'unrolled graph' with variables at different time steps considered as distinct nodes (Assaad et al., 2022; Hasan et al., 2023; Peters al., 2017). Based on the seminal work (Granger, 1969), various Granger-type approaches leverage the assumption that past values of a variable can help predict future values to detect lagged causal influences both for linear (Diks & Panchenko, 2006; Granger, 1980) and non-linear (Marinazzo et al., 2008; Shojaie & Fox, 2022; Runge, 2020; Pamfil et al., 2020) functional relationships. While non- parapaamettiic constraint- based methods for such discrete-time models (Runge al., 2019; 2020; 2023) can handle partial observations, they also fundamentally limited by the 'discrete-time assumption making them unfit for irregularly sampled observations of continuous time systems, path-dependence, or diffusion dependence. Furthermore, they require numerous tests across all time points and rely on the correct estimation of a fixed 'lookback window' т. The fundamental problems of the "discrete-time" assumption have also been discussed in Runge (2018).
Other work focuses on the (static) equilibrium behavior of differential equations (Mooij et al., 2013; Bongers et al., 2018; Bongers & Mooij, 2018), exploiting invariance in mass-action kinetics (Peters et al., 2022), or attempts to directly learn the full dynamical law via non-convex optimization of heavily overparameterized neural network models (Aliee et al., 2021; 2022; Bellot et al., 2022; Wang et al., 2024). The latter are fundamentally limited by the fixed functional modeling structures and therefore also unable to model partially observed settings. Albeit its limited applicability to fully-observed, Markovian SDE models, SCOTCH (Wang et al., 2024), which uses a variational formulation to infer posterior distributions over possible graphs, is the current state-of state-of-the-ant ofettheart baseline.
Constraint basedd methods for continuous-time stochastic processes mostly rely on (conditional) local independence, an asymmetric independence relation (Schweder, 1970; Mogensen et al., 2018), which can be used to infer a (partial) causal graph in, e.g., point process models (Didelez, 2008; Meek, 2014; Mogensen al., 2018; Mogensen & Hansen, 2020). However, besides the limitation to drift-dependencies, there exists no practical test of local independence for diffusions. The only work that actually tests local independence from data is (Christgau al., 2023), which is heavily restricted to counting processes.
In this work, we overcome the challenges of irregular and partial observations, path- and diffusion dependence, and practical applicability by transforming CI statements of the form
X
x
for disjoint J,J,K K S [d] between subsets of proocessssssssssesssseeee X1, XJ, X- over intervals I,J,K C [0. into practical hypothesis test using the signature kernel and the arrow of time.
Conditional independence tests. As a key building block of graphical models, there is a large literature conditional independence tests, i.e., testing the null hypothesis Ho X JLL Y Z. When Z is discrete, CI testing reduces to a series of unconditional tests for each value of Z (Tsamardinos & Borboudakis, 2010). For continuous Z, nonparametric kernel-based methods often either check independence of residuals after kernel (ridge) regressing X and Y on (Shah & Peters, 2020; Lundborg et al., 2022; Zhang al., 201 I; Daudin, 1980; Strobl et al., 2019 9), or measure the distance
3

---

Published as a conference paper at ICLR 2025
between joint and marginal kernel mean embeddings (Muandet et al., 2017; Park & Muandet, 2020). For example, KCIPT (Doran et al., 2014) phrases it as a two-sample test of the null Ho P(X,Y. P(X P) ()) and simulates samples from P(X PY ()) via a permutation of the data that approximately preserves Z. Lee & Honavar (2017) improve on KCIPT with unbiased estimate of Maximum Mean Discrepancy (MMD) (Gretton et al., 2006). Other permutation-basee approaches require large sample sizes (Sen et al., 2017) or rely on densities (Kim et al., 2022), unfit for our setting.
Laumann et al. (2023) develop CI test for functional data using the Hilbert-Schnite conditional independence criterion (HSCIC) (Park & Muandet, 2020) and a permutation test (Berrett et al., 2019), which they use as part of the PC-algorithm (Glymour et al., 2019) for causal discovery. Even though their approach assumes Pxiz to be known (not the case in our setting). it is inapplicable under partial observations, and does not exploit the arrow of time (to identify graphs beyond the Markov equivalence class), we benchmark the work by Laumann et al. (2023) against our method in the experiments. CI testing faces funddamental practical challenges, such as the exponential growth in the number of values to condition on as dimensionality of increases, and theoretical limits, as any CI test's power is bounded by its size (Shah & Peters, 2020; Lundborg et al., 2022). This 'no free lunch' statement underscores the need for carefully selecting the right test. Most existing approaches assume Euclidean spaces and do not generalize to path-valued random variables without densities, gap we fill by combining kernel-based permutation tests (KCIPT, SDCIT) with the signature kernel for a tailored CI test on path space and proving its consistency.
Signature kernels. Signature kernels (Király & Oberhauser, 2019; Salvi et al., 2021a), a universal class for sequential data, have received attention recently for their efficiency in handling path- dependent problems (Lemercier et al., 2021; Salvi et al., 2021c; Cochrane et al., 2021; Salvi et al., 2021b; Cirone et al., 2023; Issa et al., 2023; Pannier & Salvi, 2024). The definition of the signature kernel requires an initial algebraic setup, which we keep as concise as possible- yet self self-contained here and refer the reader to Cass Salvi (2024, Chapter 2) for more details. We provide some more informal intuition of signatures in Appendix A.4. Let (1:)) be the Euclidean inner product on 12d. Denote by @ the standard outer product of vector spaces. For any n E N, we denote by -n on (RR))n @n the canonical Hilbert-Schmidt inner product defined for any and b = (b)..... b,) in (Re)) as (a, b),, = Ih= (a,, bi)1- Define the direct sum of vector spaces T(R := ( where it is understood that the direct sum runs over finitely many non-zero levels. The inner product () on (Rd)@n can then be extended by linearity to an inner product (.--) on T(Ra) defined for any a (ao: .1....) and b = (by, b1, ...) in T(R as (a, b) = >>m (an; bn).. Other choices of linear extensions have been studied in Cass et al. (2023). We denote by T(Rs) the Hilbert space obtained by completing T(Rdd) with respect to (s-))
(a1...., an)
The signature transform is classical aoth-transform from stochastic analysis. For any sub-interval [s, :] C [0, and any continuous path X E (O, of finite p-variation, with 1 S p < 3, it (canonically) defined as S(X),, = (L)) (1)
()))()))).... ",, S(x)..) .......... E T(Rd), where S(X)
(edy@n is the n-fold iterated integral S(X) 2.t -seure..eunee dXu, 8 dXxu2 8 ... 8 dX u... Given two arbitrary sub-intervals [a, 6), [c, d] C [o, the signature kernel Ks : Cp 4), R-) x Cps (1) + R is positive definite kernel on continuous paths of bounded variation defined as
Ks(X,Y) = (S(X) a.,, s(Y),,e))
(3)
Salvi et al. (2021a, Thm. 2.5) shows that Kx(X,Y) f(t, t'), where f [ t) x 1 + R is the solution of the following path-dependent integral equation:
((,,)) - [[' [.
dYo),, with f(0,-) =
-(.-)) f(:0) 1
(4)
This 'kernel trick' allows us to evaluate the signature kernel without explicit computation of the signature transform by solving the partial differential equation (PDE) in eq. (4). We refer to Salvi et al. (2021a) for a numerical approximation scheme to solve this hyperbolic PDE and its error rates and to Appendix A.4 for more mathematical details the applicability in our setting. In our experiments, we use the JAX library sigkerax to efficiently solve eq. (4).
In summary, the signature kernel is universal kernel that takes vauiii- continuous paths potentially on different intervals- as input, is efficiently computable, and performs well in capturing characteristics of sequential data (Lee & Oberhauser, 2023).
4

---

Published as a conference paper at ICLR 2025
3 METHODOLOGY
We start with our constraint-basee causal discovery algorithms, where we assume an oracle for CI testing path space for eq. (2) in Section 3.1. In Section 3.2 then introduce the signature kernel CI test and state its consistency, which requires new proof that does not rely on densities. Our test, applicable arbitrary stochastic processes, time series, or functional data, performs well empirically in our extensive experiments in Section 4 making it a contribution of independent interest.
3.1 CAUSAL DISCOVERY IN THE ACYCLIC SDE MODEL
Throughout this section, we assume access to a CI oracle for eq. (2), where [ denotes the C(aa, b), such an oracle can be replaced in practice by consistent finite-aample CI test for path-valued test the independence of increments, not the independence of the processes on consecutive intervals, meaning that we consider path- valued random variables + ([a, b] l (X((w) X (a)) effectively decoupling initial conditions from subsequent increments. For simplicity and since this minor subtlety is naturally handled by the signature kernel as the signature transform is translation invariant (meaning ((X (1),,,b ((X(t)- Xa)))a,b denote these paths by X
random variable ([a, b] a t (X](w) (w))het) Asymptotically.
random variables (see Section 3.2). More specifically,
In Appendix A.3, we prove that when allowing for cycles in the SDE model, constraint-basee causal discovery of the full graph is impossible using arbitrary expressions of the form in eq. (2) despite the flexibility of these conditional independencies. This impossibility result is a key motivation to study the acyclic setting still allowing for loops, which are crucial in dynamic settings variables should be allowed to depend on themselves infinitesimally into the past.
We will use the oracle in the following ways for intervals [0, s) and [s, s h] with 0:
X' is symmetrically CI of X given X on [0, I) if X (oo., IL X
X- 10.71
(0,71
we then write X Lyym X X
X' is future-extended h-locally CI of X given x s if X %o.) X
Il X
X 10.o] X (o..++aai
we then write X 1 X
X' is conditionally h-locally selffindependent given X at s (o.1) 11 X we then write X 11 C x
X
[0,++A]
The key idea to leverage the unidirectional flow of time is to split the observed paths into 'past' and 'fu- ture' at some time / E [0, T). Therefore, we define the lifted dependence graph 9 (V,E) by setting V : Vo L V1, where LJ denotes disjoint union and Vo, Vi are two copies of V. whose elements we sub- script with 0 and 1; we include an edge (No - i1) i1) É if and only if there
Xi
X7
x
X²
X
X!
loop (i > i) E E, and for each edge (i + j) E E with i * j. include edges (io - jo), (i1 + +i). (in +i) E É, see Fig- ure Conversely, we say that the graph with edges E obtained by collapsing the graph with edges Intuitively, Vo contains all 'past' and V1 all 'future"
X
The lifted dependence graph ğ (right) for DAG (left) with colors high- lighting the correspondence of selected edges. variables with the same edges among them (causal relations) with additional edges from 'past' to 'future'. We can
Figure 2:
establish the following Markov property.
Proposition 3.1 (Markov property). Assume the dependence graph of the SDE model is acyclic except for loops and associate Xjo.)) with in E Vo and X(e,tt)) with i E V1. Then & is acyclic and the independence relation 1 satisfies the global Markov property w.r.. d-separation in ÿ.
Our proof (see Appendix A.6) leverages the structure of the SDE-generating mechanism, which factorizes according to the dependence graph, thereby allowing us to formally establish the global
'he '4' denotes conditioning the future of X common the literature (Florens & Fougere, 1996).
5

---

Published as a conference paper at ICLR 2025
Markov property using arguments from stochastic analysis. With an oracle for eq. (2) and a faithful- ness type assumption (for more details see Appendix A.8), we now develop new constraint based causal discovery algorithms that infer the full dependence graph instead of just equivalence classes.
Algorithm 1: Causal discovery for acyclic SDEs.
Discovering the full DAG G. To discover the full graph including loops we propose Algorithm that makes use of the time- ordering via our h-local independence mod- arbitrary but fixed).
1: - (ig Jo: 4 + lij (ijEViijj
[k. ki k V}
Ufio -
i,j |
els (consider s,
2: for c= c=....,dd-2 d-...d-200 2220 do
edge recovery wo loops
3:
for i.j V.
Theorem 3.2. Algorithm is sound and complete for the SDE model, assuming acyclicity except for loops and faithfulness: its output is the true dependence graph G.
4:
for K C V [i,5] [ =|
s.t. (Ko + +i1) E F. for E K do
5:
if -,,,, X2 x then
6:
E + E {io ju, i + j1, to 51}
7: G = (V, F3) + collapse( V FF)
The proof (see Appendix A.7) establishes completeness by identifying separating set and leveraging the global Markov property in Proposition 3.1; soundness is shown via the faithfulness assumption. In particular, our proof does not require the "strong faith- fulness' assumption, but a weaker version, 'parent faithfulness', suffices see Appendix A.8 for detailed discussion of faithfulness in our setting.
8: for k E V do
D removing loops
9:
if x 1
4.h
X x then
10:
E 4- EV (k k}
11: return g
the CPDAG. In Algorithm I, we leverage our Markov property with respect to the lifted graph that also incorporates time directionality to infer the full graph. We now show that we can also use the symmetric criterion aym to recover the 'Markov equivalence class' -all graphs that are Markov equivalent to G-via the completed partially directed acyclic graph (CPDAG) of G (Peters et al., 2017, Def. 6.24). Loosely speaking, the CPDAG has the same adjacencies G. but some edges may remain undirected. Due to space limitations, present the required global Markov property with respect to yym in Appendix A.9. This Markov property allows us apply the sound and complete PC algorithm to infer the CPDAG assuming an CI oracle for Jaym and faithfulness (Spirtes et al., 2000). While Algorithm is strictly more informative (returns G instead of just its CPDAG), the reliability of 1 in practice might be negatively affected compared to Laym by (a) conditioning on larger sets, (b) shorter time segments (potentially losing information), and (c) the additional choice of parameters s, h. Hence, real-world applications inferring the CPDAG using Jyy may be more robust than inferring G fully using I A. Building on these potential benefits, we also develop a prot-procsssing procedure for the CPDAG that again leverages the directionality of time to provably also orient all remaining unoriented edges.
Discovering and
Corollary 3.3 (post-processt) processing). Let G EV, be the dependence graph of the acyclic (except for loops) SDE model and & (V, E3) its CPDAG. Then we have X3 X1.17 J. X3 but (o.1 X3 for all (1,5) E E with (J, i) E and j.
The proof in Appendix A0 relies on the joint independence of Brownian motions dW and initial conditions X8. Corollary 3.3 directly motivates an alternative algorithm for causal discovery of G, written out as Algorithm 2 in Appendix 10, by first constructing the CPDAG (PC algorithm with Laym) followed by testing unconditionally the yet unoriented edges as in Corollary 3.3.
Partially observed setting. Finally, we consider the partially observed setting, where only (X JoLeVes.. of the process (X;" Je.ev...UVV..eep. from the model in eq. (1) with DAG G = (Vobs V2, EE) are observed. Asymmetric local independence based methods for causal dis- covery are challenged by requiring exponentially many oracle calls in the partially observed setting (Mogensen & Hansen, 2022; Mogensen, 2025). However, since our symmetric conditional indepen- dence constraint satisfies the global Markov property with respect to the induced acyelic directed mixed graph (ADMG) Gor. = (Vore, E') (also known as latent projection, with potentially arbitrary unobserved processes) over the observed variables, we can take inspiration from the Fast Causal Inference (FCI) algorithm (Zhang, 2008) by first rumning its skeleton-discoven -part and then again leveraging the direction of time to uniquely infer the edge-type (+, -, {+} for found adjacencies. This reduces the typical partial ancestral graph output of FCI (representing an equivalence class of

---

Published as a conference paper at ICLR 2025
ancestral graphs) to single, maximally informative graph (as informative ancestral graph can be). We provide all details in Appendix D.
3.2 SIGNATURE KERNEL CONDITIONAL INDEPENDENCE TEST
Our theoretical results in Section 3.1 assume a CI oracle. To make our algorithms usable in practice, we now propose flexible CI test for path-values random variables on different time intervals for expressions of the form eq. (2). Recent work using the signature kernel is limited to unconditional hypothesis tests (Chevyrev & Oberhauser, 2022) or only use as heuristic measure of conditional independence (not developing hypothesis test) (Salvi et al., 2021c), and both do not use the time order. Using terms of the signature to detect causality (not specifically with hypothesis testing) was also proposed by Giusti & Lee (2020); Glad & Woolf (2021). Hence, we are the first to combine ideas from kernel-based CI tests and the signature kernel for a practically usable, consistent CI SDCIT)
test path space. While the existing consistency proof for KCIPT (also applying (Doran et al., 2014) relies on the existence of densities, we prove consistency for testing on path- valued random variables in Appendix A.14 requiring novel arguments. We discuss the sensitivity of constraint-basee causal discovery on errors in the CI test in Appendix A. Given n samples of path segments X/O,, y z intervals I, J,K. [0, T] for i [n]. we compute the Gram matrices lxx x, k,,,kyy,k kzz E Rxx using the signature kernel Ks and run a kernel-based permutation CI test like KCIPT (Doran et al., 2014) or SDCIT (Lee & Honavar, 2017) to test Xy IL Ys Zx. The theoretical foundation combined with the strong empirical performance of our CI test suggest that it may be of independent interest outside of causal discovery applications.
4 EXPERIMENTS
In this section, after introducing the baselines and implementation details, empirically evaluate our CI test in a variety of settings. We then demonstrate strong performance in various causal discovery tasks and also outperform traditional methods in real-world finance case study.
Baselines. We compare against CCM (Sugihara et al., 2012), PCMCI (Runge et al., 2019), Granger causality (Granger, 1969), a kernel-based approach (Lau) (Laumann et al., 2023), and SCOTCH (Wang et al., 2024), a variational neural SDE method. CCM, Granger, and PCMCI are well-established methods for time series, while Lau and SCOTCH represent the latest advances in causal discovery for functional data and SDE models, respectively. CCM and Granger are limited to bivariate cases, while Lau is only applicable to unconditional tests here. Details are in Appendix C.
Implementation details and metrics. We use sigkerax for the signature kernel with an RBF kernel with length scale selected via median heuristic (see Appendix B. For bivariate cases, the causal structure is X + X2, for d >>> 2, we draw Erdös-Rényi DAGs. Performance is measured by Structural Hamming Distance (SHD, Appendix B.8). For 1 1 0.1 T (and fixed T 1) performed best (Table 5). The SDE model is
d.X; = (AX, + c)dt + DDaa(BXX + d)dW,, with A, Rdxd c. e Rd.
(5)
except for the 2-dimensional non-linear SDE, which is given by
X X
-rw sin(wt) ) rw tanh((?)) dt + Diag(d Diag(dT)dW,,
(6)
Computational complexity. Due to space constraints, we defer the computational complexity analysis of our CI test, the causal discovery algorithm, and the signature kernel evaluations in Appendix B.9. The overall computation is dominated by finding the permutation that leaves Z (approximately) invariant in the permutation based CI tests (KCIPT, SDCIT).
Choosing (conditional) independence tests. In initial experiments on two- and three-dimensional structures (c.g., forks, colliders, chains) detailed in Appendix B.2, we found bootstrapped SDCIT and HSIC to be the best performing variants of kernel-based (C)I tests (see Figure 6 and Tables 6 to 8 for details) and use them for all subsequent experiments
Whiile time observations within process not i.i.d., the process samples are i.i.d. realizations of the SDE model, see Appendix 1.13 for details.
7

---

Published as a conference paper at ICLR 2025
Table 1: SHD (x (x1 comparison of SigKer to the baselines in four bivariate SDE settings: linear, path-dependence, non-linear, and diffusion dependence. We ran SCOTCH for different sparsity parameters À and numbers of epochs ne; there is no clear trend in either parameter, but À 100, The 2000 performed best overall. Different learning rates performed worse across the board.
lincar
path-dependecce
non-lincar
diffusion dependence
x10
(A,
CCM
176 7
166 + 8
186
194
120::00 10
106: 10
100 10
10
Granger
92 5
87 1: 5
85 1:5
95 6
103 1.
103 1:5
105 1
111 1
PCMCI
89 = 9
100::00 10
91
125 15
11
55 + 15
98 - 13
75 = 23
SCOTCH
100.
17
SCOTCH
50, 2k
79 4: 18
44 14.1100 17
23 4 12
73 23
83:
73 13
25 1 13
44 1 28
SCOTCH
100,
50
36
64
55
8
91
9
Sigker
14:4 4
7 3
5
6
28
5
7 6
63
Power analysis of the unconditional test. We first demonstrate consistently superior performance of our conditional independence test (HSIC) SigKer (ours) over the only existing baseline for this setting from Laumann et al. (2023) (Lau) in the linear SDE-setting eq. (5) (with
1,00
0.75
test power
B = 0, d; 0.4), reaching test power near already for n 2 40 when the causal interaction 021 (strength of
0.50
0.25
X + X²) is comparable X2's self self-dependence (az2)
in Figure 3.
0.00
0.5
1.0
1.5
2.0
Figure further highlights SigKer's robustness even with high data missingness, and Figure 8 demonstrates its ef- fectiveness on fractional Brownian motions outside the semi- martingale framework. We are not aware of other CI tests that apply to such settings-establishngg establishing it as state- of-the-art art CI test for stochastic processes.
ratio
Figure 3: Test power for X 1L X 1o.4
over #21, Lines (shades) means (stan- a22
dard errors) over 1000 SDE instances.
Next, we leverage time to orient the edge in the much-studied bivariate causal-discovery setting (X1 - X²) via our II 2. constraint with K 0 for variety of settings: (i) linear SDEs with dependence in the drift, (ii) diffusion, (iii) or path-dependent, as well as (iv) nonlinear interactions. Table shows that SigKer decisively dominates all baselines in all settings for different sample sizes except diffusion dependence. In this setting, SCOTCH is better for specific hyperparameter settings, while performing worse for others. Crucially, one cannot cross-validate' or otherwise select such hyperparameters for the causal- qussa-yiscoverry task in data-driven fashion without ground-truth knowledge. The lack of robustness (different optimal hyperparameters for different sample sizes) renders SCOTCH unreliable in practice even for diffusion dependence.
Leveraging the direction of time.
Specifically, we draw the settings for these experiments as follows: for linear drift interactions we sample 021 ~ (1, 2.5)), 411, A22 (1.[-0.5, 0.5)), 412 = 0, B = 0, d; ~ (((0011, 0.2]) in two- dimensional linear SDE model eq. (5). For linear diffusion interactions we draw d11, 022 ~ ((0,5,, 1)) and 621 ~ U[[1, 4.5))), the rest set to zero in a two-dimensional linear SDE model eq. (5). For path- dependence, we simulate dx, = 1² (x [0.4] dt + d2dW? via a dimensiinai SDE eq. (5) with B 0, c 0, 423; 031 ~ [d[[[33, 1]] U 3.5)) and = (di, d2, 0)T, T, de ( 0.2)), the rest set to zero. For the nonlinear SDES we use eq. (6) with w ~ U(TT, 8T]), r ~ u ((0.55, 5, I]), de u(22,2.5) 2.5)..
Causal discovery. causal discovery, we sample 40 linear SDEs from eq. (5)
For
Table 2: SHD (x 1x2) comparison of SigKer to PCMCI and SCOTCH (different À and n..) in causal discovery. Means and standard errors are over 40 SDE instances.
(with Dij 2([-2,-1) -1] [1,2) for j A and a; (([-0.5, 0.5])) with random DAG adjacency structures for d {3, 5, 10, 20, 50) and use 200 sample paths from each SDE as input for the al- gorithms. Table 2 shows that
50
PCMCI
29 = 16
243 + 37
793 + 84
3530 = 159
19.6k = 857
SCOTCH 100,
28
+
86
250
1525
1160
10275
6176
SCOTCH 200, 2k
110 = 21
270
1
48
530
223
370 :: 174
538 1 70
SCOTCH 200,
:: 17
1370
1:
6425
1
705 77
7863 2670
1026
1916
ay Ppp.
18 +:
38
7
157
725 = 439
4593 = 93
Maam only
57 = 84
1477 + 11
436 + 19
1294 = 48
6005 = 98
8

---

Published as a conference paper at ICLR 2025
A
D
D
B
B
ground truth
FCI
SCOTCH
ours
Figure An example graph demonstrating the advantage our approach under partial observations.
our Algorithm (denoted by 1. and Algorithm 2 (Jll sym +pp and sym the result before post- processing) clearly outperform PCMCI and SCOTCH up to d = 10. SCOTCH's heavy dependence on hyperparameter choices for X (graph sparsity) and (the number of epochs), can sometimes render superior when charitably picking the best setting. However, since good values particularly for À cannot be known up front nor selected in data-driven fashion, one must interpret SCOTCH's in terms of its worst case performance over a set of
performance more reasonable hyperparameter settings. Hence, SigKer-firee of any hyperparameter choices- broadly outperforms the state-of-the-ars such as SCOTCH even in the setting SCOTCH was specifically tailored (SDE models). Unlike such methods, approach continues work well for other data generating mechanisms as our CI test handles stochastic processes beyond the SDE model.
Summary and discussion of results. Our CI test for J reliably detects the direction of time and outperforms strong baselines (CCM, Granger, PCMCI), consistently improving with larger sample sizes (Table 1). SigKer also dominates PCMCI in causal discovery across dimensions and consistently beats most hyperparameter settings of SCOTCH. While isolated hyperparameter settings for SCOTCH perform better than SigKer in diffusion dependence and high-dimensional causal discovery, its strong dependence on hyperparameters, particularly the sparsity parameter X, renders it unreliable in practice. Finally, SCOTCH and PCMCI are tailored to Markovian SDEs (or SDEs with fixed lag). Instead, our CI test is broadly applicable and effective across data modalities which further demonstrate empirically in a functional data example where both PCMCI and SCOTCH fail Table 10.
to detect maath-dependecce,
The partially observed setting. One of the main benefits of constraint causal discovery (especially with non parammemctiicc test) is the ability to handle partial observations. Score-based methods like SCOTCH are fundamentally challenged in this setting, since there could in principle be infinitely many unobserved variables, impossible to model, e.g., with neural-network based approaches. We showcase this advantage on the challenging example graph in Figure 4, where SCOTCH falsely infers an adjacency A- D in 88 out of 100 runs, whereas our algorithm correctly handles the unobserved confounder and only (falsely) predicts this adjacency in 8 instances.
Real-world pairs trading example. To demon- strate the applicability of our developed meth- ods on real-data, we evaluate pairs trading strategies on ten stocks from the VBR Small- Cap ETF over a three-year period (2010/01/01- 2012/12/31). We only provide concise sum- mary our results here and refer to Ap- pendix B.7 for more details on this proof-of- concept study. We assess our method's effective- ness by quantifying the profit-and-loss (P&L) profile of the generated pairs trading strategy substitution for ground truth. Pairs were selected based on pairwise p-values from different hypothesis tests: 1) cointegration via the Augmented Dickey-Fuller (ADF) test, 2) Granger causality, and 3) our method. Table 3 shows that our strategy's 's P&L substantially outperforms the baselines in total return, APR, Sharpe ratio, and maxDDD while being almost on par with ADF Granger in the fifth relevant metric maxDD. This case-study highlights the broad applicability and potential downstream impact of the findings in this work.
Table 3: SigKer outperforms baselines in most pairs trading performance metrics. 1 indicates 'higher/lower is better'.
return APR 1 Sharpe + maxDD maxDDD
ADF
0.004
0.004
0.090
0.087
230
Granger
-0.010
-0.230
0.056
ADF & Granger
0.008
0.008
0.242
0.022
153
SigKer
0.076
0.077
1,500
0.027
5 CONCLUSION AND FUTURE WORK
We introduce constraint based causal discovery algorithms for both fully and partially observed data in the form of stochastic processes, proving them to be sound and complete assuming CI oracle.

---

Published as a conference paper at ICLR 2025
These are based novel Markov properties corresponding the developed CI constraints with respect to the induced dependence graph. Our algorithms critically leverage the directionality of time to uniquely identifying the full underlying graph or induced ancestral graph, critically improving over existing constraint-hased algorithms in the static case that only output equivalence classes. Our framework also efficiently captures path- or diffusion-depeeddnce. Finally, we propose practical and consistent kernel-based CI test on path-space leveraging recent advances in signature kernels that empirically outperforms existing alternatives across wide range of settings also beyond the SDE model such as functional data and fractional Brownian motions.
Due to the identified fundamental limitations in the eyclic setting, we limit ourselves to acyclic (except for self-loops) dependence graphs and assume causal relationships to not change over time. Relaxing both of these assumptions and assessing how much of the causal structure can in principle be learned in the cyclic settings are immediate interesting directions for future work. We highlight that the field of causality represents just one of the many potential applications of our conditional independence test for path-valued random variables. Exploring applications in different domains is worthwhile direction for future work that could also catalyze new methodological developments.
REPRODUCIBILITY STATEMENT
Significant effort was made to ensure reproducibilityy both for the theoretical and experimental results. The complete proofs of Proposition 3.1, Theorem 3.2, Corollary 3.3 can be found in Appendix A.6 Appendix A.7, Appendix A. respectively. Additionally, we discuss the limitations and requirements in Section 1, which outlines the assumptions made throughout the paper. Details regarding implementation and metrics can be found in Section 4, along with further information on mechanism and results evaluation throughout Section 4. The implementation of baselines is described in Appendix C. and details on the real- world pairs trading example can be found in Appendix 1. We will also make all code used to produce the results in this paper openly available.
the
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
This work is supported by the DAAD programme Konrad Zuse Schools of Excellence in Artificial Intelligence, sponsored by the Federal Ministry of Education and Research. This work was supported by the Helmholtz Association's 's Initiative and Networking Fund on the HAICORE@IZZ FZJ partition. Emilio Ferrucci is supported by UKRI EPSRC Programme Grant EP/S026347/1. Søren Wengel Mogensen is supported by Independent Research Fund Denmark Dnte-nnteratiinnll Postdoctoral Grant 0164-00023B) and member of the ELLIIT Strategic Research Area at Lund University.
REFERENCES
Hananeh Aliee, Fabian J Theis, and Niki Kilbertus. Beyond predictions in neural odes: Identification and interventions. arXiv preprint 2tt:::100..24030 2021. 3
Hananeh Aliee, Till Richter, Mikhail Solonin, Ignacio Ibarra, Fabian Theis, and Niki Kilbertus. Sparsity in continuous-depth neural networks. Advances Neural Information Processing Systems, 35:901-914, 2022. 3
Holly Andersen. When to expect violations of causal faithfulness and why it matters, Philosophy of Science, 80(5))672-683, 6833, 2013, doi: 10. 10.1086/673937. 23
Yashas Annadani, Nick Pawlowski, Joel Jennings, Stefan Bauer, Cheng Zhang, and Wenbo Gong. Bayesdag: Gradient-based posterior sampling for causal discovery. arXiv preprint 11Xiv:2307.13917, 2023.
Charles K Assaad, Emilie Devijver, and Eric Gaussier. Discovery of extended summary graphs in time series. In Uncertainty Artificial Intelligence, pp. 106106. PMLR, 2022. 3
Alexis Bellot, Kim Branson, and Mihaela der Schaar. Neural graphical modelling in continuous- time: consistency guarantees and algorithms. In International Conference on Learning Represen- fations, 2022. URL htttps://operreiiee htteeeewwwweeeeeeeeeeeeeeeeeeeee
10

---

Published as a conference paper at ICLR 2025
Thomas Berrett, Yi Wang, Rina Barber, and Richard Samworth. The conditional permutation test for independence while controlling for confounders. Journal of the Royal Statistical Society: Series (Statistical Methodology), 82, 10 2019. doi: 10.11 https/ss..124... 4
Stephan Bongers and Joris M Mooij. From random differential equations structural causal models: The stochastic case. arXiv preprint 1rXiv:1803.08777 2018. 3
Stephan Bongers, Tincke Blom, and Joris M Mooij. Causal modeling dynamical systems. arXiv preprint arxiv:8033 08784, 2018. 3
Stephan Bongers, Patrick Forré, Jonas Peters, and Joris M. Mooij. Foundations of structural causal models with cycles and latent variables. The Anmals of Statistics, 49(5):2885 2915, 2021. doi: 10.1214/11-AS2206 URL https::tpp/.o.. :ttttp:://oo org /
19
Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. Advances in Neural Information Processing Systems, 33:21865-21877, 2020. 1
T Cass, T Lyons, and X Xu. Weighted signature kernels. Annals of Applied Probability, 2023. 4, 20, 28
Thomas Cass and Cristopher Salvi. Lecture notes on rough paths and applications to machine learning. arXiv preprint arXiv:2404.065883 2024. 4
Thomas Cass and William F Turner. Topologies unparameterised path space. Journal of Functional
Analysis, 286(4): 110661, 2024. 20
Bertrand Charpentier, Simon Kibler, and Stephan Günnemann. Differentiable DAG sampling. In International Conference Learning Representations, 2022. URL httpps://openreele.r
net/ fet//fozee forum? i id= 9w0
Hang Chen, Keqing Du, Xinyu Yang. and Chenguang Li. review and roadmap deep learning causal discovery in different variable paradigms. arXiv preprint arXiv:2209.06533 2022. 2
Ilya Chevyrev and Andrey Kormilitzin. primer the signature method in machine learning, 2016.
URL https:://// / aarriiivivvv///.i///aaa//aaaavva org/ abs/1603 03788. 21
Ilya Chevyrev and Harald Oberhauser. Signature moments characterize laws of stochastic processes.
J. Mach. Learn. Res., 23(1), jan 2022. ISSN 1532-4435. 7, 20
Alexander Mangulad Christgau, Lasse Petersen, and Niels Richard Hansen. Nonparametric con- ditional local independence testing. The Annals of Statistics, 51(5):2116 2144, 2023, doi: 10.1214/33-AS2232, URL https:://// /tpp:://do.. www.ooog///.......o. 121 2 3,20
Nicola Muça Cirone, Maud Lemercier, and Cristopher Salvi. Neural signature kernels infinite- width-depth-limits of controlled resnets. In Proceedings of the 40th International Conference on Machine Learning, ICML'22. 23. JMLR.org, 2023.
Thomas Cochrane, Peter Foster, Varun Chhabra, Maud Lemercier, Terry Lyons, and Cristopher Salvi. Sk-tree: a systematic malware detection algorithm on streaming trees via the signature kernel. In 2021 IEEE international conference cyber security and resilience (CSR), pp. 35-40. IEEE, 2021. 4
Christa Cuchiero, Philipp Schmocker, and Josef Teichmann. Global universal approximation of functional input maps weighted spaces. arXiv preprint wwXiv:2366.03333, 2023. 20
JJ Daudin. Partial association measures and application to qualitative regression. Biometrika, 67 (3):581-590, 1980.
Vanessa Didelez. Graphical models for marked point processes based on local independence. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(1):245-266 2008.
Cees Diks and Valentyn Panchenko. A new statistic and practical guidelines for nonparametric granger causality testing. Journal of Economic Dynamics and Control, 301--10):1477-166, 2006.
11

---

Published as a conference paper at ICLR 2025
Gary Doran, Krikamol Muandet, Kun Zhang, and Bernhard Schölkopf. A permutation-based kernel conditional independence test. In UAI, pp. 132-141, 2014. 4, 7, 28, 29, 30
Lawrence C Evans. An introduction stochastic differential equations version 1.2. Lecture Notes, UC Berkeley, 2006.
Jean-Piere Florens and Denis Fougere. Noncausality in continuous time. Econometrica: Journal of the Econometric Society, pp. 1195-1212, 1996. 5,
Anne Gégout-Petic and Daniel Commenges, A general definition of influence between stochastic processes. Lifetime data analysis, 16(1):33 2010. 20
Chad Giusti and Darrick Lee. Iterated integrals and population time series analysis. In Nils A. Baas, Gunnar E. Carlsson, Gereon Quick, Markus Szymik, and Marius Thaule (eds.). Topological Data Analysis, pp. 219-246, Cham, 2020. Springer International Publishing. ISBN 978-3-030-43408--3 7
Will Glad and Tom Woolf. Path signature area-based causal discovery in coupled time series. In Sisi Ma and Erich Kummerfeld (eds.), Proceedings The 2021 Causal Analysis Workshop Series, volume 160 of Proceedings of Machine Learning Research, pp. 21-38. PMLR, 16 Jul 2021. URL attps::/eet httpss//ppoceeddieee
milrppress / v1 60 glad2la wet.aallaahmll..........
Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical models. Frontiers in genetics, 10:524, 2019. 1,
Clive WJ Granger. Investigating causal relations by econometric models and cross-spectral methods. Econometrica: journal of the Econometric Society, pp. 424-438, 1969. 3,7
Clive WJ Granger. Testing for causality: A personal viewpoint. Journal of Economic Dynamics and control, 2:329-352, -522 1980. 3
Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf. and Alex Smola. A kernel method for the ce-ssample-probleen Advances in neural information processing systems, 19, 2006.
Arthur Gretton, Kenji Fukumizu, Choon Teo, Le Song, Bernhard Schölkopf, and Alex Smola. A kernel statistical test of independence. Advances in neural information processing systems, 20, 2007. 30
Alexander Hägele, Jonas Rothfuss, Lars Lorch, Vignesh Ram Somnath, Bernhard Schölkopf, and Andreas Krause. Bacadi: Bayesian causal discovery with unknown interventions. International Conference on Artificial Intelligence and Statistics, pp. 141 1411-1436. PMLR, 2023.
Uzma Hasan, Emam Hossain, and Md Osman Gani. A survey on causal discovery methods for iid and time series data. Transactions on Machine Learning Research, 2023. 3
Zacharia Issa, Blanka Horvath, Maud Lemercier, and Cristopher Salvi. Non-adversarial training of neural sdes with signature kernel scores. Advances in Neural Information Processing Systems, 2023.
Dominik Janzing, David Balduzzi, Moritz Grosse-Wentrup and Bernhard Schölkopf. Quantifying causal influences. The Annals of Statistics, pp. 2324-2358, 2013. 29
Prince Joseph Erneszer Javier. causal-cem Python implementation of Convergent Cross Mapping, 6 2021. 36
Markus Kalisch and Peter Bühlman. Estimating digh-dimmesional directed acyclic graphs with the pe-algorithm. Journal of Machine Learning Research, 8(3), 2007. 27
Nan Rosemary Ke, Olexa Bilaniuk, Anirudh Goyal, Stephan Bauer, Hugol Larochelle, Chris Pal, and Yoshua Bengio. Learning neural causal models from unknown interventions, 2020. URL https:// https://cppnreviie net forum? d1 gN6ksFws. 1o 2
12

---

Published as a conference paper at ICLR 2025
Nan Rosemary Ke, Silvia Chiappa, Jane X Wang, Jorg Bornschein, Anirudh Goyal, Melanie Rey, Theophane Weber, Matthew Botvinick, Michael Curtis Mozer, and Danilo Jimenez Rezende. Learning to induce causal structure. In International Conference Learning Representations, 2023. URL https::/p/........... / www.oppeevvveoooe wwwrreeieeweeeeeee.eeeee... net/ www.:e/foeommeeeeeeeeeeee httpemmmiddhpp_hhhh_ae 2
Ilmun Kim, Matey Neykov, Sivaraman Balakrishnan, and Larry Wasserman. Local permutation tests for conditional independence. The Annals of Statisticx, 50(6):3388-3414, 2022.
Franz J Király and Harald Oberhauser. Kemnlls for sequentially ordered data. Journal of Machine Learning Research, 20, 2019.
Felix Laumann, Julius Von Kügelgen, Junhyung Park, Bernhard Schölkopf, and Mauricio Barahona. Kernel-based independence tests for causal structure learning functional data. Entropy, 25(12): 1597, 2023. 3, 4, 7, 8, 29, 31, 34, 36
Steffen Lauritzen and Kayvan Sadeghi. Unifying Markov properties for graphical models. The Annals of Statistics,, 46(5):2251 - 2278, 2018. doi: 10.121411-A0S1618, URL https://dol. org/10 11111111111111 110-114/7771116666 24
Steffen L Lauritzen, Philip Dawid, Birgitte Larsen, and H-G Leimer. Independence properties of directed markov fields. Networks, 20(5):91-5505 1990. 25
Andrew R Lawrence, Marcus Kaiser, Rui Sampaio, and Maksim Sipos. Data generating process to evaluate causal discovery techniques for time series data. arXiv preprint arXiv:2104.08044 2021.
Darrick Lee and Harald Oberhauser. The signature kernel. arXiv preprint arXiv:2305.04625, 2023. 2,
Sanghack Lee and Vasant Honavar. Self ceff-discrepaccy conditional independence test. In Uncertainty in artificial intelligence, volume 33, 2017. 4, 30
Maud Lemercier and Terry Lyons. A high order solver for signature kernels. arXiv preprint arXiv:2404.02996, 2024. 20
Maud Lemercier, Cristopher Salvi, Theodoros Damoulas, Edwin Bonilla, and Terry Lyons. Distri- bution regression for sequential data. In International Conference on Artificial Intelligence and Statistics, pp. 3754-3762. PMLR, 2021. 4
Lars Lorch, Jonas Rothfuss, Bernhard Schölkopf, and Andreas Krause. Dibs: Differentiable bayesian structure learning. Advances in Neural Information Processing Systems, 34:24111-24111 2021. I
Anton Rask Lundborg, Rajen D Shah, and Jonas Peters. Conditional independence testing in hilbert spaces with applications to functional data analysis. Journal of the Royal Statistical Society Series B: Statistical Methodology, 14(5):1821-88 -1500 2022. 3, 4
Daniele Marinazzo, Mario Pellicoro, and Sebastiano Stramaglia. Kernel method for nonlinear granger causality. Physical review letters, 100(14):14410: 2008.
Christopher Meek. Toward learning graphical and causal process models. In CI@ UAI, pp. 43-48, 2014. 3
Søren W. Mogensen. Faithful graphical representations of local independence. In Sanjoy Dasgupta, Stephan Mandt. and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. PMLR, 02-04 May 2024. URL htt.s: /pwccedr ngs m1 mlr. wwr.rppres/eee v238//
mogensen24a. html. 23
Søren Wengel Mogensen. Weak equivalence of local independence graphs. Bernoulli, 2025. (to appear). 6
Søren Wengel Mogensen and Niels Richard Hansen. Markov equivalence of marginalized local independence graphs. The Annals Statistics, 48(1):539 559, 2020. 3
13

---

Published as a conference paper at ICLR 2025
Søren Wengel Mogensen and Niels Richard Hansen. Graphical modeling of stochastic processes driven by correlated noise. Berouuli, 28(4):3023 - 3050, 2022.
Søren Wengel Mogensen, Daniel Malinsky, and Niels Richard Hansen. Causal learning for partially observed stochastic dynamical systems. In Conference Uncertainty in Artificial Intelligence. pp. 350-360, 2018.
Francesco Montagna, Atalanti A. Mastakouri, Elias Fulig, Nicoletta Noceti, Lorenzo Rosasco, Dominik Janzing, Bryon Aragam, and Francesco Locatello. Assumption violations in causal dis- covery and the robustness score matching. In seirth-seventh Conference on Neural Information Processing Systems, 2023a. URL httt:p:://penneviiiee n EowummoddlyyTrtteaaoroo
Francesco Montagna, Nicoletta Noceti, Lorenzo Rosasco, Kun Zhang, and Francesco Locatello. Scalable causal discovery with score matching. In Mihacla van der Schaar, Cheng Zhang, and Dominik Janzing (eds.), Proceedings of the Second Conference on Causal Learning and Reasoning, volume 213 of Proceedings of Machine Learning Research, pp. 752-771. PMLR, 11-14 Apr 2023b. URL https:tt////omc httptpp:://proceednnng.
ml presss./eeee...................e /vwps//21133 htt11//mmntgggga2200 html. 2
Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. From ordinary differential equations to structural causal models: the deterministic case. In Proceedings of the Twenty-Ning Conference on Uncertainty in Artificial Intelligence, UAI'3,, 13, pp. 440 448, Arlington, Virginia, USA, 2013.
AUAI Press.
James Morrill, Adeline Fermanian, Patrick Kidger, and Terry Lyons. A generalised signature method for multivariate time series feature extraction. arXiv preprint (XXi:20006000873. 2020. 21
Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, Bernhard Schölkopf, et al. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends@ in Machine Learning, 10111)) 2017. 4, 20
Roxana Pamfil, Nisara Sriwattanaworachai Shaan Desai, Philip Pilgerstorfer, Konstantinos Geor- gatzis, Paul Beaumont, and Bryon Aragam. Dynotears: Structure learning from time-series data. In International Conference on Artificial Intelligence and Statistics, pp. 1595-1605. PMLR, 2020.
Alexandre Pannier and Cristopher Salvi, A path-dependent pde solver based on signature kernels. arXiv preprint arXiv:2403. 1738, 2024.
Junhyung Park and Krikamol Muandet. measure-theoretic approach kernel conditional mean embeddings. Advances in neural information processing systems, 33:21247-212555 2020. 4, 28, 29
Judea Pearl. Causality. Cambridge university press, 2009. 25
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017. 3, 6, 21, 22
Jonas Peters, Stefan Bauer, and Niklas Pfister. Causal models for dynamical systems. In Probabilistic and Causal Inference: The Works of Judea Pearl, pp. 671-699 Association for Computing Machinery, 2022, 2, 2,3,17
Thomas Richardson and Peter Spirtes. Ancestral graph Markov models. The Annals of Statistics, 30 (4):962 1030, 2002. doi: (0.1214/0s/10331669055 URL https: //ooi. ottpoooog/0...111111 aos 0os/1031669015.01 37
L. C. G. Rogers and David Williams. Diffusions, Markov processes, and martingales. Vol. 2. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 2000. ISBN 0- 521-77593-0. doi: 10. 11000///097811177500000
URL https: //tp::////ooooo/oo//////ooo /ttp:/oooo......o////o///////o/t or1/10.1017/ CR097811075901 Itô calculus, Reprint of the second (1994) edition. 2, 18, 22, 24
14

---

Published as a conference paper at ICLR 2025
Paul Rolland, Volkan Cevher, Matthäus Kleindessner, Chris Russell, Dominik Janzing, Bernhard Schölkopf, and Francesco Locatello. Score matching enables causal discovery of nonlinear additive noise models. In International Conference Machine Learning, pp. 18741-18753. PMLR, 2022.
Jakob Runge. Causal network reconstruction from time series: From theoretical assumptions to practical estimation. Chaos: An Interdisciplinary Journal of Nonlinear Science, 28(7):075310, 2018. 3
Jakob Runge. Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets. In Conference Uncertainty in Artificial Intelligence, pp. 1388-1397, PMLR,
2020. 3
Jakob Runge, Peer Nowack, Marlene Kretschmer, Seth Flaxman, and Dino Sejdinovic. Detecting and quantifying causal associations in large nonlinear time series datasets. Science advances, :eaau4999, 2019. 2, 3, 36
Jakob Runge, Xavier-Andoni Tibau, Matthias Bruhns, Jordi Muñoz-Marí, and Gustau Camps- Valls. The causality for climate competition. In NeurlPS 2019 Competition and Demonstration Track, pp. 110-120. PMLR, 2020. 3
Camps-Valls.
Jakob Runge, Andreas Gerhardus, Gherardo Varando, Veronika Eyring, and Gustau Camps- Calps-Valls. Valls. Causal inference for time series. Nature Reviews Earth & Environment, 4(7):487-505, 2023. 2,
Cristopher Salvi, Thomas Cass, James Foster, Terry Lyons, and W. Y. The signature kernel is the solution of a Goursat PDE. SIAM Journal on Mathematics of Data Science, 3(3) 899, 2021a. 4, 20
Cristopher Salvi, Maud Lemercier, Thomas Cass, Edwin V Bonilla, Thcodoros Damoulas, and Terry Lyons. Siggpde: Scaling sparse gaussian processes sequential data. In International Conference on Machine Learning, pp.
PMLR, 2021b.
Cristopher Salvi, Maud Lemercier, Chong Liu, Blanka Horvath, Theodoros Damoulas, and Terry Lyons. Higher order kernel mean embeddings to capture filtrations of stochastic processes. Advances in Neural Information Processing Systems, 34:16635- 14416655-16677,, 2021c. 4.7
Tore Schweder. Composable markov processes. Journal of applied probability, ((2):400-410 1970.
3, 20
Skipper Seabold and Josef Perktold. statsmodels: Econometric and statistical modeling with python. In 9th Python in Science Conference, 2010. 36
Rajat Sen, Ananda Theertha Suresh, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkottai. Model-powered conditional independence test. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https: httte/////ccceeeeooeeeeeeeo B wwwp:edddddPaa.pppeeee .df. 4
http://ceeeeiiinnn.eeeereeeeeeee neurips cc/paper_fili taapper_ffleseeeeeeeeeeee wetllessppppree ppsp/p///////////////
Rajen D Shah and Jonas Peters. The hardness of conditional independence testing and the generalised
covariance measure. The Annals of Statistics, 48(3): 2020. 3,
Ali Shojaie and Emily B Fox. Granger causality: A review and recent advances. Annual Review of Statistics and Its Application, 9:289-319, 2022.
Carl-Johann Simon-Gabriel
Gabriel and Bernhard Schölkopf. Kernel distribution embeddings: Universal kernels, characteristic kernels and kernel metries on distributions. The Journal of Machine Learning Research, 19(1):1708 700-1736, 2018. 20
Hermann Singer. Dynamic structural equations in discrete and continuous time. In Economic Evolution and Demographic Change: Formal Models in Social Sciences, pp. 306-320. Springer, 1992. 2
15

---

Published as a conference paper at ICLR 2025
Alexander Sokol and Niels Hansen. Causal interpretation of stochastic differential equations. Elec- tronic Journal of Probability, 19, 03 2013. doi: 10.1214/EJR.19-28991 20
Peter Spirtes and Christopher Meek. Learning bayesian networks with discrete variables from data. In KDD, volume 1, pp. 294-299, 1995. 27
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, prediction, and search. MIT press, 2000. 1, 6, 23, 27
Eric V Strobl, Kun Zhang, and Shyam Visweswaran. Approximate kernel-based conditional inde- pendence tests for fast non-parametric causal discovery. Journal of Causal Inference, 7(1), 2019.
George Sugihara, Robert May, Hao Ye, Chih-hao Hsieh, Ethan Deyle, Michael Fogarty, and Stephan Munch. Detecting causality in complex ecosystems. science, 338(6 (886610))49965000 2012. 7
Gábor Székely, Maria L Rizzo, and Nail K Bakirov. Measuring and testing dependence by correlation of distances. Ann. Statist. 35 (6) 2769 2794, 2007. 36
Ioannis Tsamardinos and Giorgos Borboudakis. Permutation testing improves bayesian network learning. In Joint European conference machine learning and knowledge discovery in databases, pp. 322-337. Springer, 2010. 3
Caroline Uhler, Garvesh Raskutti, Peter Bühlmann, and Bin Yu. Geometry of the faithfulness assumption in causal inference. The Annals of Statistics, 41(2), April 2013. ISSN 0090-5364. doi: 10.1214/12-a0s1066 URL http: / /ttpxxxxoiio//////oooo//////.dot www.oooi.ooooooooooooooooooo.... wwt.///...0 111.1111111110111111111110000111 A001000000000.. 23
Thomas Verma and Judea Pearl. Equivalence and synthesis of causal models. In Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, UAI '90, pp. 255-270, USA, 1990. Elsevier Science Inc, ISBN 0444892648. 21, 23
Matthew J Vowels, Necati Cihan Camgoz, and Richard Bowden. D'ya like dags? survey structure learning and causal discovery. ACM Computing Surveys, 1- 2022.
Benjie Wang. Joel Jemnings, and Wenbo Gong. Neural structure learning with stochastic differential equations. In The Twelfth International Conference on Learning Representations, 2024. URL
htttp:///cpenreveww net wttpenrreeeeeeeeteooooraaaaaaaa
3, 7, 36
Naftali Weinberger. Faithfulness, coordination and causal coincidences. Erkenninis, 83(2):113-333, April 2018. ISSN 1572-8420. doi: 10010077/1100000-07-99962 URL htt.t:tts///ee /ttp:://ddooo//////
10.7/00/s// 00..007/1116000000 017- 9882-66 6. 23
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gnn: Dag structure learning with graph neural networks.
In International Conference on Machine Learning, pp. 7154-7163. PMLR, 2019.
Jiji Zhang, On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16):183--188 1896, 2008. ISSN 3704-3702. doi: https://doi.oom http://doooorg//// 10. a000 00000..1.110000100000000....000. URL https: / www.wwwwkk.... /tw.s/cienneiieee.....c 6,37
com/ hcmm://cceenccatttllleees/p////s
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. In Proceedings of the Twenty-Sevntth Conference on Uncertainty in Artificial Intelligence, UAI'1, 11, pp. 804-813, Arlington, Virginia, USA, 2011. AUAI Press. ISBN 9780974903972.1 3, 30
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric Xing. Dags with optimization for structure learning. Advances in neural information processing systems, 2018.
Continuous
Xun Zheng, Chen Dan, Bryon Aragam, Pradeep Ravikumar, and Eric Xing. Learning sparse nonparametric dags. In International Conference Artificial Intelligence and Statistics, pp. 3414-3425 PMLR, 2020.
16

---

Published as a conference paper at ICLR 2025
APPENDIX
TABLE OF CONTENTS
Proofs and Theoretical Digressions
18
A.1 Summary of Notations
18
A.2 Intuition and Details for the SDE Model
18
A.3
Counterexample for Cyclic Causal Discovery in the SDE Model
19
A.4 Signature Kernel Details
20
A.5 Testing on Time Points
21
A.6 Proof of Proposition 3.1
21
A.7 Proof of Theorem 3.2
22
A.8 Faithfulness and Causal Minimality
23
A.9 Global Markov Property for the Symmetric Independence Criterion
24
A.10 Proof of Corollary 3.3 and Algorithm for Robust Causal Discovery
26
A.11 Post-Processing Without Jointly Independent Initial Values
26
A. Sensitivity of Constraint-Basee Methods to Errors in Conditional Independence Testing
27
A.13 Li.d. Assumption of the Conditional Independence Test
28
A. 14 Consistency of the Conditional Independence Test
28
Experiments and Evaluation
29
B.1 Kernel Heuristic and Interval Choice
30
B.2
Empirical Comparison of Different Tests
30
B.3
Additional Experimental Results for the Bivariate Case
................................
31
B.4
Building Blocks for Causal Discovery
B.5
Causal Discovery
32
B.6
Conditional Independence Testing Beyond the SDE Model
................................
32
B.7
Real-World Pairs Trading Example
35
B.8
Evaluation Metrics
35
B.9
Computational Complexity
36
Baselines
36
Details on the Partially Observed Setting
37
17

---

Published as a conference paper at ICLR 2025
A PROOFS AND THEORETICAL DIGRESSIONS
A.1 SUMMARY OF NOTATIONS
A summary of notation is provided in Table 4.
Table 4: Summary of notations
Symbol
Meaning
m
short for { m. E N
X
stochastic process X = (X1 X C, T) R Ruit...ddd
d
number of coordinate processes X = (X X or nodes in graph
X
k-th coordinate process of X (X1, ,..., X X E R
dimension of the k-th coordinate process X
T2k
W
k-th Brownian motion, W E 1
dimension of the k-th Brownian motion W
mg
n
total dimension of the stochastic process X, n2 n1 + nd
k-th drift component n²x IR" R
o²
k-th diffusion component o² R" + 1M xm:
T' Rs0
maximum observation time time points within the observation time dependence graph with nodes V and edges E
8,8 [0,
g= (V,
V = [d]
set of vertices in the dependence graph
FCV V
set directed edges between nodes V
pag
parents of node in graph (omitted if clear from context)
g= (V, B)
lifted dependence graph of graph G (V, E))
Vo, Vi
disjoint copies of V. with 0/1 indicating past/future
V Vo LV
node set in lifted dependence graph
ECV V
edge set in lifted dependence graph
S(X),,, E T(R")
signature transform of path X over interval [s,
Y)
signature kernel of paths X,
T(R4)
the direct sum n= (Rdy@n
{a (an)neN II IenN (RR))))))) max(n a, # < oo)
T(RR)
the completion of ((Rd) w.r.t. (a, b) Σn= a, (well-defined)
0(-)
Landau asymptotic notation ("Big-O notation")
A.2 INTUITION AND DETAILS FOR THE SDE MODEL
Making the actual dependence of n* and ṭ² on their arguments in eq. (1) explicit, we can rewrite it as
dxx 11² (X
[o.1) (o. )at + o a (Xp.))
(7)
X = x k E [d].
Then u² k are functions defined on C((O, +oo), (pan.) (or some suitable subspace thereof): Lipschitz conditions the coefficients that guarantee existence and uniqueness for this type of SDE can be found Rogers & Williams (2000), which we assume to hold throughout, Each W an ma-dimensional Brownian motion (a collection of m4 independent 1-dimensional Brownian motions, that is), * maps to the space rı X my-dimennioon matrices, and the noises 4 together with the (possibly random) initial conditions z jointly independent. In other words, the system be written as an n = n4 + ne dimeenmnsil SDE driven by an m == mi .... ma-dimensional Brownian motion, with a block-diagonal diffusion coefficient (since the noise is unobserved, this structure has to be imposed if we wish not to deal with unobserved confounding). This means the SDE can be written the matrix-form
x7
n1' (x
Pa
W
10,8
d
dt +
(8)
dd
(X
(
pad [0.4]
We
18

---

Published as a conference paper at ICLR 2025
The superscript påg refers to the parents of the hthh node in G, which may (and most often does) contain & itself. Intuitively, all of this means that, for all times t and small increments At, the increment of the solution X (+at XI is random with distribution that is well-approximated by [o.t] ) At, and independent of the history of the system up to time I. This interpretation can actually be made precise by showing that these piecewise constant paths converge in law to the true solution (usually known as the weak solution, when viewed in this way).
multivariate normal with mean μ (X [o.:] At and covariance function ( (o.9) (Xfo.)
We will refer to G as the dependence graph of the eq. (I), which we refer to as the SDE model for brevity. Compared to that of Peters et al. (2022), this model is slightly more general in that (i) allows for path-dependence and (ii) for each node to represent multidinensional process: the special case of state-dependent SDE-i.e., in which μ and a only depend on X., the value of X at time I-continues to be important special case, although our model also accommodates delayed SDEs (the coefficients depend on the value of X at prior instant in time, c.g. X,-r for fixed or possibly pondom/time-depenee
7 > 0), and SDEs that depend on quantities involving the whole past of X, such as the average 1 - X,ds. We note that the choice not to make the coefficients explicitly time-dependent is deliberate and motivated by the requirement that the system be causally stationary (the causal relations between the variables do not change over time).
Given that we considering the dynamic setting, it is generally natural to allow for G to have cycles. This comes at no additional requirement of consistency constraints as does in the static case (see for example Bongers et al. (2021)), since the causal arrows in the model eq. (I) should be thought of as 'pointing towards the infinitesimal future, with infinitesimal magnitude', integrated over the whole time interval considered. Indeed, the system of SDEs does not require any global consistency to be well-posed, other than the regularity and growth conditions that guarantee global-in-time existence and uniqueness. On the other hand, we will be interested in the potential for constraint-bia based causal discovery of such systems, qualified by the following assumption on the types of conditional independencies that we allow be tested in continuous time:
A.3 COUNTEREXAMPLE FOR CYCLIC CAUSAL DISCOVERY IN THE SDE MODEL
The following example demonstrates that constraint- baasd causal discovery of the full graph is impossible using expressions of the form eq. (2) when allowing for cycles.
Example A.1. An oracle for eq. (2) is not powerful enough to rule out a directed edge X + X3 for an SDE model with the following dependence graph:
x1
X2
X33
We now go through this example and describe a different type of oracle that would be required for causal discovery in cyclic SDE models. Concretely, we claim that an oracle for eq. (2) is not powerful enough to rule out directed edge X1 - X for an SDE model with the graph Example A.1.
Testing X [0.+] X% [e,oth]
22.3 will not remove the edge, due to the open path [0.a].
x [b.) + x ( + X2 [.,++]] X [s,++)]
Testing X1..] IL X3
X3 [0
X2 (0,0+N) on the other hand, runs into the collider
X Xb.a)
X (1,0tH
X2 (...tt -x -X2.
There is no other way of splitting up the time interval (even allowing for more than 2 subintervals) that overcomes both these problems: when testing X (o..) IL x x (as is necessary in order to rely
on time to obtain direction of the arrow), if X² is not conditioned on over [s, s + h] it will be a mediator, and if it is, it will be a collider.
What would be needed to detect the edge in the above example (and to perform causal discovery more generally in the cyclic case), is the availability of tests of strong instantaneous non-causality
19

---

Published as a conference paper at ICLR 2025
x1
X2
X²
Figure 5: The blue highlighter for intervals over which the path is being tested for independence. while orange is for conditioning. The first figure illustrates the path opened by the unconditioned-on mediator X [.)++ while the second illustrates the path opened by the same variable acting as a conditioned-on collider. While not quite possible to draw extra/figures this way, it is helpful to think of the arrows as pointing from values to increments X₁ + (Yi+de Yt), infinitesimally, with the total causal effect accrued over time.
in the Granger sense as defined in Florens & Fougere (1996). This reflects the fact that the SDE model is 'acyclic at infinitesimal scales'. Unfortunately, such a property- has to do with the Doob-Meyer decompositions of functions of the process w.r.t. two different filtrations- iss much more difficult to test for, it is infinitesimal in nature. Recent progress in this direction was made in Christgau et al. (2023) for the case of SDEs driven by jump processes; this local independence criterion, which goes back to Schweder (1970), is however weak in the sense that it only takes into account the Doob-Meyer decomposition of X and not functions of it, and is not therefore able, for example, to detect dependence in the diffusion coefficient (Gégout-Pethe & Commenges, 2010). Here we take the view that a continuously-indes observational distribution (ef. the discussion in Sokol & Hansen (2013) on whether the infinitesimal generator can be considered "observational))
path, queried over an interval, can be considered as an
A.4 SIGNATURE KERNEL DETAILS
Additional mathematical details. For any E [1,2), let C C,( T). be a compact subset such that the signature transform is a continuous injection from K. to T(R An example of compact set K. satisfying such conditions is the set of time-augmented paths started at common origin, where ((O, 7], (Rd) is endowed with the p-variation topology. Further examples of compact sets and choices of topologies on path-space are discussed by Cass & Turner (2024). Then, the signature kernel is universal over K. in the sense that the associated RKHS, whose elements are restricted to act on KC, dense in C(K). the space of continuous real-valued functions on K,, endowed in the topology of uniform convergence. See Cass et al. (2023, Proposition 3.3) for a proof. The compactness assumption can be relaxed by either renormalizing the signature transform so that range is always guaranteed to be bounded (Chevyrev & Oberhauser, 2022) or by operating weighted path-spaces with a different choice of topology Cuchiero et al. (2023).
The signature kernel is well-defined and can be shown, under similar compactness conditions, to be universal also when p 2 (Salvi et al., 2021a; Lemercier Lyons, 2024). In the specific setting of stochastic differential equations (SDEs) considered in this paper, i.c. when p E [2, (), one can use classical limiting procedure from rough analysis to show that the integral equation in eq. (4) takes
the Stratonovich form ftt, (') + f [u, (odX,, odY.) We refer the interested reader Salvi et al. (2021a, la, Section 4.3) for further details.
Another important property that a kernel should possess order ensure theoretical guarantees of most kernel methods, including tests for conditional independence (Muandet et al., 2017), is that of being characteristic. Loosely speaking, kernel & is said characteristic to a topological space if for any (Borel) probability measure on that space, the μ-expectation of the feature map k((,,) uniquely characterises jr. An important result from the theory of kernels relates to the equivalence between the notions of universality and characteristicness. In particular, these three notions can be shown to be equivalent for kernels defined over general locally convex topological vector spaces -Sirin-Gabriel & Schölkopf, 2018, Theorem 6).
Intuition.
The signature transform of a (potentially multidimensional) continuous path (or time series) is sequence of iterated integrals, static features, which form expressive representation
20

---

Published as a conference paper at ICLR 2025
of the path. An analogy is often drawn to monomials in (multiple) indeterminants, with which one can express continuous functions. Another useful analogy is the Fourier transform. While Fourier transforms (or wavelet transforms) capture the frequency content of different modes (over different times), the signature captures information about order, area, and so forth (due to the iterated integrals). For example, the depth 1 (or order 1) iterated integral describes the changes of each variable throughout the time interval; depth 2 describes the signed area that is swept by the curve (an illustration of depth I and 2 of a path can be found in Morrill al. (2020)); higher depths capture properties of the volume, and so on, but those can be hard to grasp visually. We refer the reader to Chevyrev & Kormilitzin (2016); Lee Oberhauser (2023) as introductory texts on the signature (kernel) method that contain more visualizations and examples for building intuitions about these mathematical objects.
A.5 TESTING ON TIME POINTS
It is also possible to replace any of the path- random variables in eq. (2) by random variable at a single time-point (as for example done in the post-processing by testing on Xo) using a regular rbf-kernel. Note, that in addition, if we knew in advance that there is path-dependence, the unconditional independence X 11 A.A. X is equivalent to the conditional independence X JL + x! X depends on X/,,1) via X3. Testing on entire (segments of) paths is always required when allowing for path-dependence.
(at fixed times 8, 8 + h): this is because without aath-dependence X for u E [s, t| only
A.6 PROOF OF PROPOSITION 3.1
Proof of Proposition 3. Since 9 is acyelic, a directed cycle in ② that is not a loop must contain nodes both in Vo. V1. But there can be no such directed cycles, since edges only travel in the direction Vi V1, by construction of G. Since & also free of loops, it is DAG. We now show that there exists a structural causal model (SCM) over & with the path-valued random variables of the statement: Markovianity will then follow from Peters et al. (2017, Proposition 6.31), original to Verma & Pearl (1990). In other words, we must show there exist measurbee functions
Rdim(paa) C((0, s), RTM) C((O, s], RRiimpe ((43)) Fb:
C((0, R*))
( Wh Wh. [0.4]
X [0.4]
and
F#: [C((s,s + h1, Rm²) x C(10, s), Rddimpaat) C((s, 8 + h), Redimppa ({4)))))))))))))))))))))))))))) (( a+1 - Wh) )oseens X-pa x-pa ((A))
~C[s 8 + MJ, R
".app [s,0th]
[s.0+1]
for each & E [d] where the initial conditions To and the Brownian path segments W 1o.. (W W Josesn jointly independent and X [*.,++))== == X[t..+ X This independence follows from the definition of the SDE model and from independence of Brownian increments over disjoint or consecutive intervals. These functions are partial in that they are not defined on the whole space of continuous functions on the interval: we only need to show them to be defined on a measurable set of paths that contains all solutions of SDEs on the required interval. F can be defined as follows, with care to make explicit the dependence on the solution on the two intervals via the operation of path-concatenation *;
x [3,++A] = solution of X = X. + I" nd 4x
Pop(E (11 (1k) (k))ppa (k)
[..)]
xpui _
[o.s]
* (s.0]
jdt (9)
+ ot (xppaa patk rpa) 10k) x (agrrpaa
(K3ripa Jaw?
* *x (s.00)
(0,0]
[o.u) (o.e]
(10)
21

---

Published as a conference paper at ICLR 2025
for [s, s hl, we obtain Ff by removing the initial condition X3 in front of the integrals in equation
We have also separated out the k-th component of the solution from the rest of the arguments which o², n² are dependent, which we consider part of the measurable adapted dependence on WP))(R) needed in the existence and uniqueness theorem. F is defined similarly (with no dependence on past path-segments and with =f replacing X in equation 9). Such functions are well-known to be well-defined and measurable (Rogers & Williams, 2000, Theorem 10.4).
Remark A.2. In testing, using the symmetric criterion Maym has proven to be more reliable than the asymmetric one used in the test above. procedure, which a little redundant, but which makes good use of the superior performance of sym would work as follows:
1. Run the PC algorithm to discover the CPDAG corresponding to the variables X (0.T))
2. Pass this CPDAG as input to Algorithm 1: by this we mean that V is the same and the input E is given by
(in + jo, j1, f1 ji E. (i 5) or (i - U kn k
where (i j) denotes undirected arrow and E' is the CPDAG output by the classical PC algorithm.
3. The loop-recovery step is identical as before.
The algorithm would run very similarly as before, but performing fewer CI tests in the first phase, since it can make of the information contained in the partially-directed skeleton.
Remark A.3. we knew advance that there no path-dependence, the test X II a.A X (with no additional conditioning set) is equivalent to the test on values of the process X 1l X x X this is because X for E [ss t] only depends on X [e..) via X However, this kind of statement no longer works in the conditional case (by arguments similar to Example A. and testing on whole paths is strictly necessary when allowing for path-dependence
Remark A.4. CI testing of SDEs conceptually similar to static CI on discretely sampled data, is lower than the actual frequency which causal effects propagate. This
when the sampling is because, in continuous time and for any > O, there are going to be causal effects that occur at time scales less than h. Whenever we just discretely sample time series with no instantaneous effects, Peters et al. (2017, Thm. 10.3) provides full causal discovery, even in the presence of cycles in the MiJ). {dd)) Potentially absent loops could [0.+]
summary graph, by performing d² tests X JL X i then be removed as Algorithm Ignoring that this might suffer from the conditioning being
too large, our signature method can be of help in this setting too, if there is path-dependence: the conditioning variable can be taken to be S(X [44 (4)
A.7 PROOF OF THBOREM 3.2
Proof of Theorem 3.2. We have to show that E E (where E the edges detected by Algo- rithm 1).
"C:" This direction can be shown by finding an appropriate separation set in ğ by exploiting the global Markov property Proposition 3.1. We begin by proving correctness of the recovery of the skeleton modulo loops. This will follow if we show that for (i (ا>)) j) & E. for i,j E V distinct
_ sep (oo} U [Ko, k & paf (()).
where - sep denotes d-separation the graph ő. Indeed, eventually, the set K in the algorithm will take the value (Ku, k A E pa? \ {i)}, at which point the three edges (iu, ju). (11,1)), (io. j1) (which are either all present or all absent, inductively, by construction Æ) are deleted. (Of course may be that these edges are deleted before this, if smaller or different d-separating set found, but note that edges are never added.) All undirected paths between in and ji factor as ig ... ho + 4 -.. where the dots stand for possibly empty undirected path. All such paths with l j are blocked by {oo} U. (ko l paς \ (i)), so we focus our attention the in which l . f1 is non-empty.
22

---

Published as a conference paper at ICLR 2025
Here we follow similar argument to that of Verma & Pearl (1990, Lemma 1). If ..... is of the form 1 ........ 17 > ji (with 1 = 11) it is blocked by (ki k E pağ \ {i)}. Assume instead it is of the form 11 ...... + ji and let S q S r be such that { is the first collider on the entire path in ......1 -Ji- starting from ji and travelling back: certainly this exists (and belongs to Vi), thanks to the arrows ho - and [ + j1. For the path in ....... -i to be open given the conditioning set, it must be the case that 14 must be an ancestor (in 9) or member of {k1 h E paf (i)) (l) cannot be an ancestor of nodes in Vo): this would yield directed cycle, which is impossible.
We argue similarly for the loop-removal phase. If Ei () + (do, (1) & E, we must show
G io 11 eeeep" in (ko, k1 | h E E \ {i}}
Consider path ig- f....-hy ho + 1 ....1 11 in G. If the segment 1 ..... .. non-emply we conclude that the path is blocked by the same argument as above (with i1 replacing ji). Assume that the path is of the form iu... ho - i1 (with io * ho since (ou, 11) & E): in this case h E pa \ {i) and the path is again blocked. Thus all paths are blocked and the implication follows.
2: Assume (i. E E. thus (1a: E E. Hence as a DAG by construction, # S C V {i,j} s.t.
(5o) (11 So U (1o) U.S. By the faithfulness assumption Definition A.5 one therefore has x (eott V S C V \ (i.5}. Hence (i,j) EAAg,
Xio.i KL X [b..tt] Xosop X (u.s
A.8 FAITHFULNESS AND CAUSAL MINIMALITY
In the above proof, we have used the following notion of faithfulness:
Definition A.5 ((Global) Faithfulness of _ s.h in 9). Let {Xiheed be the coordinate processes of a solution of eq. (1) for t E [o, 1], 9 = (V z [d]. E') the dependence graph defined by eq. (1). The independence relation 1 is called (lobally) w.r.t. the DAG G, if
X t. x" x Ao 1 B1 Bo; Co Ci
(11)
for all B, C V pairwise disjoint.
Faithfulness is a standard assumption in the causal discovery literature. Some type of faithfulness-like assumption is strictly necessary to do causal discovery since, otherwise, it would be impossible to make any inference about adjacencies in the underlying graph from the observed distribution. While we used the strong faithfulness assumption Definition A.5 for the proof above, various weaker faithfulness-like assumptions in the case of DAG-based causal discovery could be used, e.g., the strictly weaker assumption known as 'parent faithfulness' (Mogensen (2024) gives a definition of parent faithfulness in the context of stochastic processes). This assumption suffices in our algorithm without making any changes to it (or the respective proofs) in the acyclic case.
The strength of the faithfulness assumption in real-world data is heavily debated. Besides Weinberger (2018), who states that 'proposed counterexamples to the causal faithfulness condition are not genuine'. Spirtes et al. (2000) argues that for parametric models, 'the measure of the set of free parameter values for any DAG that lead to such cancellations is zero for any smooth prior probability density, such as the Gaussian or exponential one, over the free parameters'. What is meant in our case is, that when allowing the diffusion coefficients in eq. (1) to range in some 'reasonable' finite- dimensional family (such as linear or affine functions) and drawing the parameters of such family from a distribution which has positive density w.r.t. the Lebesgue measure (and independently of the noise), the resulting distribution on path-space, split over [0, s) and [s, t]. will almost surely be faithful for any 0 < < w.r.t. the lifted dependence graph. We do not attempt a proof of this statement here, as it may require considerable effort and technique. On the other side, Andersen (2013) or Uhler et al. (2013) (among others) caution against making the strong faithfulness assumption easily. Many of their concerns are ameliorated by only assuming the weaker parent faithfulness.
Causal minimality, the other hand, is generally easier to understand and can be expected hold for the arrow X3 [f.00 X((..) whenever the following condition is satisfied: the conditional distribution X (1 = x admits a positive density on some submanifold M of R. and for all u there exist 21. 2/ M. of # sty, s.t. (w', (x) =1) # (n² ad) (xr,
23

---

Published as a conference paper at ICLR 2025
Example A.6 (Causal minimality).. The fact that allowing for variables to have than one dimension means the causal minimality condition is not a trivial one, as the following examples demonstrate. Let X (W,0) where W is 1-dimensional Brownian motion (so that n, 2), and let 1² and/or o² depend on X only through its second coordinate. Then, even though this dependence may be non-trivial, causal minimality does not hold. This may lead one believe that one can generically only expect causal minimality to hold if m = but this is not the case. Take, for example, d = 4 n and assume o² = i.c., X has driving Brownian motion, that m is only 3. Assume, furthermore, that pa = {4}. Then, by Hörmander's 's Lie bracket-generatine condition (see for example $V.38 in Rogers & Williams (2000)), (X _X² xx3 has density in R² for any choice of an initial condition, if (a (ar), 0, 0), (0, (z),, 0) span I for all x E IR² and (x)), 0, 0); /d] = f1 0, or [(o²(x) (x), O, 0), [u] span the third direction. Arrows going from the first three nodes to the fourth will be necessary for Markovianity
long as the coefficients of x depend on the respective variables on the support of such density. The point is that even though
(X), x)) is only driven by wooddimensional Brownian motion, the coefficients of the SDE (at the initial condition) impart a 'twist' to the solution, making causal minimality trivial condition on (ort, ,,") which is verified as there is any dependence.
A.9 GLOBAL MARKOV PROPERTY FOR THE SYMMETRIC INDEPENDENCE CRITERION
In this section, we provide proof for the global Markov property of the symmetric independence criterion in order for the PC-algorithm to be applicable. is based on the notion of independence models:
Definition A.7. Let V = [d] be a set. An independence model J(V) over V is ternary relation over disjoint subsets of
J(V) [(A, B,C, |,B,BC))ABBBCCCCCCCCCCC, A,B,C disjoint}
When (A, C) is triple in J(V), (A, C) E J(V), we also use (A, B C)) to denote (A, B, C). This notation highlights the fact that a conditioning set. An independence model J(V) is called semigraphoid if 1.-4. hold for all disjoint A, B, C C.
(symmetry) (A, B C) E J(V) = (B, A AIC) E J(V)
2. (decomposition) (4, B C) E J(V) and D C B + (A, J(V)
(weak union) (A, B D C) E J(V) = (A, CUD) E J(V)
4. (contraction) (A, B C) E J(V) and (A, D BUC) J(V) = ()BUDIC)EJTI
semigraphoid J(V) called graphoid 5. holds.
5. (intersection) (4, B CUD) E TVV) and (A BUC) E J(V) = (A,BUD) J(V)
An independence model (VV) called compositional if 6. holds.
(composition) (A, B C) (VV and (A, D C)) e J(V) = (ABBUDIC)
The graphical criterion of d-separation defines independence model on DAG G (V,E)
(g) = ((A, A,B,C c disjoint, A I sep B |C}
(12)
Theorem A.8 (Lauritzen & Sadeghi (2018)). For any DAG g (V,E), the independence model Ja-sen (g) is a compositional graphoid.
Let V = id. Given random variables X : (9, (X', A.), i i E and B, C V disjoint, conditional independence
X X : o (x (x 1((9)
defines the probabilistic independence model
A, A,B.C V disjoint, XA L X Xc).
(13)
24

---

Published as a conference paper at ICLR 2025
We will use this symmetric conditional independence relation. Note that X' may take values in path-space in which case is a stochastic process. The independence model J ((P) P) is a semigraphoid which is immediate consequence of sub-o-algebra properties.
For E V. we let ndę denote the set of nondescendants of v, i.e., the set of nodes i such that there is no directed path from v to i.
Definition A.9 (Directed global and local Markov properties). Let G = (V,&) be DAG and J(V) be an independence model over V. The independence model I (V) satisfies the global Markov property w.E.t G :
(A, B C) Jd-sep(9)
( VA,B,C V disjoint
(14)
The independence model JVV) satisfies the directed local Markov property w.r.t. G :44
pag) E JVV for all VEV ((v), End spa?)
(15)
Theorem A.10 (Lauritzen et al. (1990)). Let G = (V,E) be a DAG, let and J(V) a semigraphoid over V. The directed global and local Markov properties are equivalent, that is.
J(V) satisfies eq. (14) w.r.t G + J(V) satisfies eq. (15) W.E.t. g
(16)
We therefore only have to establish the local Markov property for the symmetric independence model sym
Proposition A.11. Let be set of variables induces by the model in eq. (7) with a constant and diagonal diffusion matrix such that it induces the DAG g (V,E). Then the system satisfies the directed local Markov property w.r.f. G.
X sym nd \ pas x
pa X
Wi [d]
(17)
Proof. The idea the proof is that all information about node X is contained in its parents pa; == pay.. the Brownian motion W and the initial condition Xj. A similar idea can be used to show the result in the case of SCM Pearl (2009). We let (P) denote the semigraphoid induced by Laym the variable set V [X]_ ..... X") u [W1 ..... W (X). X and we let (P) denote the semigraphoid induced by Lyym on the variable set V = (X) "x.....""" X"}. We define the DAG
= ( (x (x....., (W!. (W!,..,, U X²). E - + x(i)
(18)
By construction, F.(X+) C FF(W")) V (X(Pa V (Xx)), and therefore
Fi(X') Fx lpa, w v | V(W"")
where the parent and nondescendant sets are be read in the graph G, W-i (W1,... W (W.). and X, (X) ..... X²} \ (X,). The above statement corresponds to eq. (15) when (X1, Xn). When W. or v Xg. has no parents in I and eq. (15) also holds. Therefore, the independence model J(P) satisfies the local directed Markov property w.r.t. to J.
The independence model J ((P) is semigraphoid, and by Theorem A.10 satisfies eq. (14) w.r.t. G. We have X a ndd \pa, XPa, in G. and one therefore has
F((X)) P (x F((XPa')
establishing eq. (15) for J(P) w.r.t. g.
25

---

Published as a conference paper at ICLR 2025
A.10 PROOF OF COROLLARY 3.3 AND ALGORITHM FOR ROBUST CAUSAL DISCOVERY
Proof. This is clear from the data generating mechanism in eq. (1) where all Brownian motions dW; and initial conditions X are jointly independent. Since X (o.r) is fully determined by ?
where anj are the ancestors of in G, it follows that i E an, if and only if X + X Since already know from the CPDAG that and j adjacent and the graph is acyclie, E anj implies i +
The full written out algorithm then looks like Algorithm 2 and is sound and complete by Corollary 3.3.
Algorithm 2 Robust Causal discovery for acyclic SDE models leveraging the initial values
1: pre [k V) Epre t- [i + J. -iliijeei j}
for c = O.....d
do
Adjacency detection
3: for i,j E V. viiis # do
4:
for K C VV {1,5), |K| c
S.L. (k 1) Epre for k K do
5:
if x IL X2 x then
6:
Epre + Epre {i j.j +
Siy t
7:
for each triple i, k E with i-j jj and i do
D Collider Orientation
8:
i & Six then
9:
Epre + Epre ((..), (},
10: Apply the Meek Rules
joji V.iz j s.t. (i,j), (). do
12:
X 1L X 0.11 then
13:
E < ( j}
14:
else
< Aii i)
16:
for
l
E do
b removing loops
17:
x
1
1x ((A)) then
E s.h
18:
[k- k}
19:
return G
A.11 POST-PROCESSING WITHOUT JOINTLY INDEPENDENT INITIAL VALUES
In real-world settings where there is natural 'starting point' of the processes, can typically not assume joint independence of initial values X1 as 'the process also happened before'. In this subsection extend Algorithm 2 version that is applicable in scenarios where cannot assume the initial values (xj) to be jointly independent. The algorithm works similar as to Algorithm 2, except for the fact that for each pair i,j E V with unoriented edge, we have to condition on the parents of j when testing for the existence of edge + to prevent information flowing from i to j. As it can happen that j connected ls f with another undirected edge, the set K;,ag required:
Opace XC,+j : pa knnon x PVVy,un))
where pa, Knooum := Vifin}} (1) Epost: (Jo. k1) & Epoct), Vg,en == (k ( (1) E Epost, (jo, ki) Epost]. Ki-aj is required to implement the procedure of conditioning on all known parents jf (pa (pa Spont (nnwn and case there are unspecified other neighbors Vj,un of j, loops through the options of either condition on them or don't condition on them. case j has no other undirected adjacencies, this set only contains one element, the parents of except i.
Proposition A.12. Algorithm is sound and complete assuming faithfulness, meaning if we denote the output graph of Algorithm by Gezt = (V, Eest), the output edges East coincide with the edges of the true DAG G = (V, F.).
26

---

Published as a conference paper at ICLR 2025
Algorithm 3 Robust causal discovery for acyclic SDE models.
1: Vpre [A EV Epre 1 +ilijje V, V, ド}
for e O...., d- do
Adjacency detection
3: for i,j E V. + do
4:
for K C V j). |K] = c
s.t. (k [-=1 j)
Fir for & K do
5:
X IL X X then
6:
Epre t Epre {i - j.j + i}
Siy +-1 V
7: for each triple i, E V with i-j- and i do
Collider Orientation
i Six then
9:
Epre + Epro ((.,),, ki.
10: Apply the Melk-Rules
V +V
Pepeet f tso + jo, in + h +1 (f,5) E Eprc]
U {io + liEvi
b Lifted Graph
12:
fori, jri,j V. v.
(io.j),, () do
for E K,->,
14:
x 1 X²
X then
15:
E+ E\ {&o + ju
h is 513
Break the loop
16: = (V. E) < collapse( V,
17: for k V do
removing loops
18:
if X 1
X1 ((k) then
19:
E E [k b}
20: return
G
Proof.
"5": We have show (i,j) = (i.j) Fest. This direction is clear but will still be stated here. Since the original PC algorithm (see e.g. Spirtes et al. (2000)) sound, (i,j) Epost Since (f,j) E E, in and jı cannot be separated in the lifted graph AK C V( Thus by the faithfulness assumption X a X X AK c cV which holds especially for K Ki-+j, hence (i,j) E Eezt-
"C": Proof by contraposition: (i.j) Eext = (i.j) E is equivalent to (i.j) & = (i,j) & East. Since the PC result Spre = =V, Epre) has the correct skeleton and v-structures, the only option would be that wlog jjjs j.t.j - E G, (io. 51), (Ja, i1) E Epost meaning the original PC was to detect an adjacency but unable to discard (i,j). But then jo is separated from é by the parents paς of i, which do not contain j. Therefore, they are contained in Kj-+s as single element and by the global Markov property, obtain X 3.1 X XPa thus (i,j) East.
A. 12 SENSITIVITY OF CONSTRAINT-BASED METHODS TO ERRORS IN CONDITIONAL. INDEPENDENCE TESTING
Constraint- based causal discovery methods such as PC or FCI heavily rely on conditional indepen- dence tests to infer the causal structure. However, the adaptive nature of these tests, where the results of subsequent tests are contingent upon the outcomes of earlier ones, complicates the error analysis of these approaches. While this is a widely acknowledged challenge faced by all constraint-bact methods, how the final graph depends on type I and II errors remains an important open problem in the field. Already early work by Spirtes & Meek (1995) presented a simulation study showing the sensitivity of different methods the different types of errors, underscoring variable trade-off between sensitivity and specificity across different sample sizes in skeleton and edge orientation detection depending the size of the graph and number of samples. Instead, Kalisch & Bühlman
27

---

Published as a conference paper at ICLR 2025
(2007) provide theoretical results showing that the PC algorithm is uniformly consistent for high- dimensional settings under a mild sparsity assumption on the DAGs, where the number of nodes can grow quickly with the sample size. However, they critically rely the restrictive assumption that the observational distribution a multi-variate Gaussian for their finite sample results, where a strong theory for testing CI with partial correlations is available.
The performance of conditional independence tests is critical for the robustness of constraint- based methods and consistency (as demonstrated for our test in Appendix A.14) a critical first step. prac- tice, extensive simulation studies are another useful approach to benchmark the actual performance of the final causal discovery method.
A.13 L.I.D ASSUMPTION OF THE CONDITIONAL INDEPENDENCE TEST
KCIPT and SDCIT both require i..dd samples as input. In our analysis, solution path of all variables in is treated as a single example originating from the SDE model. By generating n solution paths independent realizations of stochastic process (e.g., independent initial conditions and independent Brownian motions in the SDE), we obtain n i.i.d. samples. is important to note that while multiple observations from each path different time points are considered part of a single sample, these within-path observations are not assumed to be i.i.d. However, as each path is an independent realization, the collection of different paths meets the i.i.d. requirement necessary for the effective application of KCIPT and SDCIT in our setting.
A. CONSISTENCY OF THE CONDITIONAL INDEPENDENCE TEST
In this section, we argue, that under certain assumptions on our system, Theorem of Doran et al. (2014) still holds even without assuming the existence of a density. At first, it is to be noted that the signature kernel eq. (3) is bounded on compact sets C' C (V(CC R<)) of BV paths, an assumption that can be made we evaluate our SDEs over finite, discrete time steps. Satisfying this boundedness, it defines an RKHS over these compact sets. addition, the signature kernel is characteristic
these bounded sets (see Proposition 3.3 Cass et al. (2023)). We use the notation X (R, P) - Ax), Y: A2 P) - (y, Ay). Z (2.A, P) + (2, Az) with X,Y, 2 being compact subsets in BV(C(T, R==)), )), (C R )) (V(C R²=)) and denote the RKHS's defined by the signature kernel as (Hx, kx): (Hy, ky), (H2,kz))
Our measure-theoretical argumentation now follows the definitions in Park & Muandet (2020) and the original proof in Doran et al. (2014). Let H be a Banach space, A', Ah a sub-o-algebra of the Bolee-r--ageebr.
Definition A.13. Let F: (2,,,, P) + AH, a Bochner P-integrable random variable. The conditional expectation of H w.r.t. E is Bochner P-integrable RV F (Ω, A. P) + A'n) s.t.
[ Fap = F'aP
VA A'H
Due the existence and (almost sure) uniqueness, such an F' is denoted E[F A'g]] with the notation E[F 2] := E[F oZ)] for a general Z : (22, A. P) + AZ, which in turn can be used define the conditional expectation P(A A'r)) E a A'r and can be used to define the conditional kernel mean embedding
px| = MXXI == Exjzz (xx Z
As proven Theorem 5.8 of Park Muandet (2020) under the assumption, that Pxiz := E(- 1 Z admits a regular version (meaning its can be written transition kernel, see Park & Muandet (2020)) and kx @ ky is characteristic, holds that
X X Y Z < ||ихл|д px]2 @ 2Y|2 2 Hy 0 <> ||yхл| @ pz pxiz @ pyiz @ pz H2 =
where the second equivalence is trivial. Let now o E S, be permutation such that its permutation matrix M, (m))
if o(i), 0
1
my
j (
28

---

Published as a conference paper at ICLR 2025
satisfies (M 0.
The empirical estimates for the given sample {(r,, Vs. (e) and its permuted version under a
PPx,Y Ax(a)))) @ (y .) @ (2(
(19)
Prxyz
(x,, @ ky -) @ (z1,
(20)
Similar to Laumann al. (2023), can now write the distance between test statistic and the approx- imated test statistic in terms of the sum of the distance between the empirical estimates and its respective counterparts by using the inverse and the regular triangle inequality
|XX22 2 fz - px|z @ PYIZ Pz HZIlHeHHyon 1l Pr Inxenoon
||xX|| @ Fz - 1x|2 X JYIZ & pzz pXxx + (.pk.nellHxx
PXY|2 & Pz PPX.x. N
||xxz
@ fYI2 @ pz - AP IHNSHYSKE
By Park & Muandet (2020), the first term tends to zero for n + co. With a similar line of argumentation as in Doran et al. (2014) can establish majorant for the estimated HSCIC, namely
1!pxX PP HH8HH8Hz
(x :) @ (y())))) (z(2))) n
kx( @ ky(yo()))) kz(z,,
Hx
1 hx (zi, :) @ ky(2s))) & (2(2))))
kx (x(xx-1(1)))) @ ky(Ui, @ k2(20-1()))))
==0
Hy
(kx((z)))) - -x(xx-1()))))
(()) @ ky(w,)) -) & (kz(2z,)) - (z((2-2(00) Hll
71
(xx :) - kx(#o 1(0) :)
[ky Many (kz((z)))) kz(zz 10) 1)
Hx
S2Ma
SM,
< 2M ( TY(DDRKHS)
where the assumptions can be made due to the boundedness of the kernels. Hence, under the assumption that
((2) + Pxiz 8 Priz @ Pz
(21)
a statement that holds true in the case of densities (see supplementary material of Janzing al. (2013)), since P/ is regular, j Mx|z @ Jy|z & uzz
Hence under the assumptions that P. admits regular version (an assumption also made by Laumann et al. (2023)), the considered random variables operate on compact sets of BV-paths and eq. (21) holds, the test is consistent and only if n Tr(PDDKHS) 0. This is the exact same statement as in Theorem 1 of Doran et al. (2014).
B EXPERIMENTS AND EVALUATION
This section provides details about the experimental framework, elaborating on the data generation process, the parameters and architectures employed, and presents additional results.
29

---

Published as a conference paper at ICLR 2025
Table 5: Performance of fittree-extende h-locally conditionally independence criterion in the bivariate setting for the two heuristic and d2 for different sample sizes. The SHD is measured for different values of in 1 with defining different lengths of intervals in the past and future. Overall the performance is best of shorter values of the past intervals compared to the future (s < 2
01
02
(x10²)
= 400
600
400
600
0.1
76.2 = 2.5
58.4 = 2.7
14.9 = 2.0
15.8 = 2.0
8 = 0.2
77.3
72.2 + 2.8
12.9 + 1.7
1..
0.3
80.2 + 2.3
76.2 + 2.6
21.8 2.2
17.8
8 = 0.4
$9.1 2.0
92.0 + 2.1
31.7 2.4
25.7
S 0.5
8.0
98.1
38.6
27.7
8 = 0.6
82.4 1.9
96.0 2.1
60.0
48.5 2.9
8 0.7
102.0 1.2
104.0 2.0
80.2
61.4
8 0.8
104.0 1.4
95.0 + 1.5
81.1 + 2.0
87.1 + 2.4
S 0.9
95.0 1.6
104.4 = 1.8
102.0 1.2
101.0 = 2.1
B. KERNEL HEURISTIC AND INTERVAL CHOICE
In kernel methods, besides selecting the right kernel function, the correct choice of its parameters is vital. A reasonable choice for radially symmetric kernels & (g) -x, /l/ f: R. + R. is to choose to lie in the same order of magnitude as the pairwise distances (12z, Iz [I) Choosing the bandwidth for the RBF kernel in our setting with samples (Z4)) x; E C C (I, Rd) is not straight forward, as the RBF kernel ultimately acts on signatures and there no immediate way obtaining a 'typical scale' of pairwise distances of signatures. To still set the bandwidth purely based on observed data, there are two natural ways implement a median heuristic based on two different collections of pairwise distances. The first option is to choose
Median || - 1 i.j E [n]]
where || Ia is the is the 2 norm of entire paths, i.e., integrated over the time interval I. Given that in practice we observe the paths 2; still at fixed time points t <... tm within the interval I, we can also consider the heuristic
02 Median (1| a. ji E [n], ke [m]]
where || ll2 is the Euclidean norm in IRd and we consider pairwise distances of all observations across all paths and time points. In early benchmarks, have empirically found 02 to yield better heuristic by comparing the performance of both heuristics by evaluation of the SHD in causal discovery task in the linear bivariate setting X X2 without diffusion interaction with a21 ~ ~ ((-2.5, -1] [1, 2.5)). Q11, ~ ~u ((-0.5, 0.5)) and ~ l (10, 0.5)). The experiment performed for different choices of intervals [0, x). [s, 8 8+h] the future-extended h-local conditional independence. As can be seen from Table 5, and the intervals [0. 0.1], 10.1, 1] seem to perform best on average and are therefore used in the rest of the experiments. In all the experiments of the paper, in the implementation of the signature kernel we use depth parameter of 4, the RBF kernel and we add time as an extra dimension to the signature kernel.
B.2 EMPIRICAL COMPARISON OF DIFFERENT TESTS
Different kernel-based conditional and unconditional tests are compared. HSIC with bootstrap (HSIC;) and with 7-distribution approximation (HSIC,) (Gretton et al., 2007) were implemented for the unconditional setting, while KCIPT (Doran et al., 2014), KCIT with bootstrap (KCIT,), KCIT with 7 approximation (KCIT,)) (Zhang et al., 201 1) and SDCIT for the conditional setting (Lee & Honavar, 2017). Figure 6 shows that SDCIT and HSIC, are overall the best performing ones in terms of type I and type II error. In this experiment, sample 400 different trajectories within time interval [0,1]. The number of bootstrap samples over permutation test is set 100, the number of permutations for single permutation test to 20000, the
sampled 100 different linear SDEs and
30

---

Published as a conference paper at ICLR 2025
1.0
1.0
0.8
0.8
0.6
0.6
type 1
0.4
0.4
0.2
0.2
0.0
0.0
HSIC, HSIC, KCIPT KCIT, KCIT, SDCIT
HSIC, HSIC, KCIPT KCIT, KCIT, SDCIT
Figure 6: Performance in terms of type and type II errors of different unconditional (HSIC, and HSIC,) and conditional tests (KCIPT, KCIT, KCTT,, SDCTT). Among the conditional tests, SDCTT outperforms KCIPT in terms of type error, while performig in a similar range in terms of type error. Among the unconditional tests, HSIC, outperforms HSIC,
0.8
test power
0.4
SigKer n-60
.....
Lau n-6 c=100
0.0
0.2
0.4 missingness
0.6
0.8
Figure 7: Test power over the missingness level (percentage observations that is being dropped at random). While both our method as well Laumann et al. (2023) maintain their power up to high levels of missingness, our test still consistently outperforms the baseline. Lines show means over 1000 settings in the power analysis in Section and shaded regions show standard errors.
number of null samples via Monte Carlo from all values permutation HSIC, the number of null samples for KCrT-bootstrap to 20000 and the number of null samples for SDCIT to 1000. These are the tests parameters also used in the rest of the experiments.
20000 and 1000 for
B.3 ADDITIONAL EXPERIMENTAL RESULTS FOR THE BIVARIATE CASE
Figure shows that in the simple unconditional bivariate setting of the power analysis in Section our test maintains high power up substantial levels of missingness and only starts degrading once more than 80% of observations are dropped at random starting from 64 time steps over the interval [0, 1] for 1000 different SDEs.
B.4 BUILDING BLOCKS FOR CAUSAL DISCOVERY
The performance of the conditional and unconditional independence tests evaluated using widely recognized causal structures that are at the foundation of causal discovery. Specifically, we examined scenarios involving two variables, both connected and unconnected, and three-variable configurations comprising chain, fork. and collider structures. The analysis type and type II errors, as shown in Table 6, indicates robust performance for both conditional SDCIT and unconditional HSIC tests.
31

---

Published as a conference paper at ICLR 2025
Table Test performance on the key building blocks for causal discovery. Here, IL refers Laym except for X, IL ; which means X [0.1/2] JL [t/2..] We use SDCIT for CI tests and bootstrapped HSIC unconditional independence. We simulate 40 samples of 512 trajectories for 10 different SDEs (400 tests column) with 25% of the 128 original observations dropped uniformly at random. The error represent type or type error when the null hypothesis Hg should be rejected (X) or accepted (V), respectively.
graph
He
x x|
X I. px2
x
X
|
X Il X
x
X 2
X Lxx X x2
should
X
x
reject
error
0.0000
0.0075
0.0000
0.0000
0.9600
0.0000
0.0450
0.0000
Table Test performance on the key building blocks for causal discovery. Here, JL refers to Maym in a setting where the dependence only comes except for x IL X which means (o.1/2) IL X from the diffusion. We use SDCIT for CI tests and bootstrapped HSIC unconditional independence. We simulate 40 samples of 512 trajectories for 10 different SDEs (400 tests per column) with 25% of the 128 original observations dropped uniformly at random. The error represent type or type II error when the null hypothesis Ho should be rejected (X) accepted (V), respectively.
grapb
No
x
x
x
x
3
x
x
x
x
x
x
x il x
x Il x
X 1x
should
reject
error
0.0000
0.0072
0.0000
0.0000
0,9600
0.00
0.07
0.01
These results refer to the symmetric conditional independence Leym. while future-extended h-local conditional independence presented in Table 8. The tables show that the test is able to reconstruct the presence and the directionality of the edges overall all building blocks of causal structure learning. We also perform the same experiments for the setting in which the causal dependence only comes from the diffusion. Referring to the linear SDE in eq. (5), ai = O3f O, a11, Q22 ~ U[_0.5, 0.5), 012, 02 ( 2.5,- 1.0) U (1.0, 2.5)] and 1 022 2[.005, 0.5). b, and d, are sampled from u[-0.1, and U 0.2,, 0.2]. Table includes the results for all the different causal structures.
B.5 CAUSAL DISCOVERY
We tested SCOTCH using various sparsity parameters and epochs to identify the optimal configuration. Table confirms that the configuration with À 200 and n. 2000 outperforms others in the tested settings, and hence is chosen for the comparison with our method in Table 2. The table also reveals that SCOTCH's performance is not robust. to changes in A, showing substantial variations under the same number of epochs, optimizer, and learning rate with different À values. These results demonstrate that the SCOTCH's performance can significantly deteriorate with changes the parameter X, while keeping the number of epochs constant. For example, when À is adjusted from 200 to 100, the Structural Hamming Distance (SHD, scaled by 10²) increases from an average of 538 to 10.275 for ne 2000.
B.6 CONDITIONAL INDEPENDENCE TESTING BEYOND THE SDE MODEL
In this section, aim to demonstrate that proposed non-parametric conditional independence (CI) test extends beyond the setting of SDEs and even beyond semi- mami-martingalss, rendering it more broadly applicable than most existing methods, which usually assume independent (additive) noise.
32

---

Table 8: Test performance on the chain, fork and collider causal structures for the future-extended h-locally conditionally independence criterion. Here, refers to IL + and we use SDCIT. We simulate 10 samples of 512 trajectories for 10 different SDEs (100 tests per column). The error Published as a conference paper at ICLR 2025
represent type I or type II error when the null hypothesis Hu should be rejected (X) or accepted (V), respectively.
graph
Ho
xxx
x"xx**
should reject
X
X
X
error
0.07
0.33
0.04
0.04
0.03
0.00
X1
X3
graph
Ho
x xx
x"xX'Xx"
x px
X"XX'XX²
XX
should reject
X
X
X
X
0.12
0.02
0.04
0.02
0.04
0.06
graph
Ho
x2xx
x²xx'|X"
x [x
x2xX''X²
should reject
error
0.08
0.4
0.56
0.46
0.36
0.16
33

---

Published as a conference paper at ICLR 2025
Table SHD (x10') of discovered graphs, for 200 samples and nodes in the SDE model. The mean and standard error of SCOTCH for different values of À and ne for 20 different SDEs is presented. The best performing setting for higher dimensional graphs
200 and ng = 2k.
x10
(e,
d=3
d=5
d= 10
d = 20
50
SCOTCH 100, 2k 188 + 28
417 + 86
250 1 61
1525 - 1160
10275 + 6176
SCOTCH 200, 2k 110 +
270 +
530 223
370 174
538 + 70
SCOTCH I, 1k
20
11
85 + 20
375 + 28
1455 + 103
6095 + 153
SCOTCH 50, lk
330 2
1255
=
5895 107
1340 243
2994 + 941
SCOTCH 200, lk
400 17
1370
+ 29
6425 = 80
705 + 77
7863 + 2670
Fractional Brownian Motion. illustrate this, we start by applying our test to stochastic process driven by fractional Brownian motions (fBMs). Fractional Brownian motion is a generalization of standard Brownian motion, a continuous time Gaussian process Bμ (t) with zero mean and E By [+)] = (14|2 + |s|2H - |t - (2H) that incorporates parameter E (0, 1), the so called Hurst parameter, which governs long range dependencies. For
0.5 it reduces to the regular Brownian Motion.
H > 0.5 increments are positively correlated.
H < 0.5 increments are negatively correlated.
Specifically, we consider the following system of stochastic differential equations driven by fractional Brownian motions
dXx, dY,
0 a2
0
X1 Ye
d1 0
0 d2
dw! dw?
dt
(22)
with WT. W independent fBMs with Hurst parameter H and 021, d1, d2 ~ (((((12) 2)). quantify the effectiveness of our test in this context, we measure the test power for different strengths of interaction for different Hurst parameters. Figure shows this power analysis for 500 random settings of eq. (22). The power of our test steadily approaches I the interaction strength increases to 1 regardless H. We note that since the above example does not have independent increments, Algorithm is not applicable anymore for causal discovery in such settings. Instead, the fractional Brownian motion example merely highlights the usefulness of our CI test independently from its application in causal discovery in the SDE model.
Functional data. For further corroboration of our claims, we turn to the following example from functional data analysis (FDA), taken from Laumann et (2023), test causal discovery in a non SDE setting. After drawing DAG G (V, E), processes for source vertices, i.e., vertices i ;; without parents in G, are generated according to
M
(t = Σ
c mm (t) + c
m=1
cos with Fourier basis functions (t) (1) 2 sin (2ml), @3(() v2 cos (2mtt) and on, the
weights ein ~ [(0, 1), and the additive noise of ~ No0,, 1). For all vertices with at least one parent,
we set
/ (s.
x'(t)= =a Σ
kEPu?
with 3+ (*(ss)) 8(s ot2² 8(t 2t))), of ~ Up.1 and 1.
We draw 40 DAGS with 40 distinct FD generating mechanisms for each dimension d E {3. 5, 10, 20, 50}. Table 10 shows that SCOTCH cannot capture the underlying dependencies, as it is tailored specifically to the SDE model. is thus misspecified for such a function generating mechanism. Under such (arguably mild) misspecification, SCOTCH is even outperformed by PCMCI, whereas our method still performs much better than both baselines.
34

---

Published as a conference paper at ICLR 2025
SigKer H=0.3
SigKer H=0.5
SigKer H=0.7
SigKer H=0.4
Sigker H=0.6
1.
0.5
test
0.0
0.0
0.2
0.8 1.0
interaction strength
(22) for different H. The CI test picks up dependence for as little as 100 samples given certain amount of interaction-strength. Lines show means over 500 settings and shaded regions show standard errors.
Figure 8: Test power over for different fBMM-diven processes eq.
Table 10: SHD (x 10²) comparison of SigKer to the baselines PCMCI and SCOTCH (with À 200 and n2 = 2000) in the functional data setting. We report mean and standard errors over 40 instances.
x10²
d=3
d= 5
d= 10
= 20
50
I sym
40
22
+ 10
509 + 25
1542 + 60
6786 = 223
sym+
42
141
+ 13
489 +
1498 56
6529
250
PCMCI
110 + 30
320
+ 42
1150 + 121
6518 + 293
7799
250
SCOTCH
558 +
1861
+ 43
8567 = 63
35467 + 833
105165 = 10934
B.7 REAL-WORLD PAIRS TRADING EXAMPLE
In the pairs trading experiment, stock price data is downloaded from Yahoo Finance for predefined list of stocks over a specific period, divided into training (Ist January 2010 to 31st December 2011) and trading intervals (Ist January 2012 to 31st December 2012). The chose stocks are Trinity Industries (TRN), Brandywine Realty Trust (BDN), Commercial Metals Company (CMC), The New York Times Company (NYT), New York Community Bancorp (NYCB), The Wendy's 's Company (WEN), CNX Resources Corporation (CNX). Logarithms of the stock prices are computed to stabilize variance and normalize the prices. During the training period, pairs of stocks selected based on various statistical tests: Cointegration Test Sangle-Grangery to determine if a pair of stocks is cointegrated, suggesting long-term equilibrium relationship; Augmented Dickey-Fuller (ADF) Test to assess the stationarity of the spread (ratio) of a pair's prices; and Granger Causality Test to check the price of one stock in the pair can predict the price of the other. Pairs selected based the p-values from these tests, with threshold of 0.05 determining significance. In the trading phase, rolling window used continuously recalculate the mean and standard deviation of the spread between the selected pairs. Trades are initiated based on the z-score of the spread, where a high z-score indicates short position and low z-score indicates long position. Positions are managed and closed when the spread returns to predefined 7-score threshold. The strategy's 's performance is evaluated based on total return, annual percentage rate (APR), Sharpe ratio, maximum drawdown (maxDD), and maximum drawdown duration (maxDDD).
B.8 EVALUATION METRICS
Following common conventions in the causal discovery literature, we evaluate our algorithms using the following metries.
Structural Hamming Distance (SHD). Given two directed graphs G1 (V, (V. over the same nodes with different sets of edges and let A₁, A2 E {0, 1]mxX be their adjacency matrices. Then define the structural hamming distance (SHD)
SHD Σ
((A))s (A2)igl
i.j
35

---

Published as a conference paper at ICLR 2025
Normalized SHD. In order to compare the recovery performance of our algorithms for different types of graph-sizes, the normalized SHD is defined as
SHD
SHD Dorm d(d-1)
B.9 COMPUTATIONAL COMPLEXITY
Conditional Independence Test. For KCIPT, we denote by B the number of outer bootstraps. by the number of inner bootstraps, by n the number of i.i.d. samples, and by NMc the number of Monte-Carlo samples. We spell out the computational complexity of all steps in performing single conditional independence test.
computing B permutations of the n-samples: (nn)
the loop over the B outer bootstrap contains in each iteration:
permuting matrices: R ( (assuming fast matrix multiplication algorithms, otherwise
(n²)))
splitting matrices using indexing: O(n²)
computing RKHS distances: (
solving the linear program to find the best permutation (this depends on the solver, but for primal-dual interior point methods is ((v log(1/e) + m²)), where the number of constraints, n the number of variables, and the accuracy tolerance for the solution. Overall, in our case with m n(n 1) constraints, we obtain: which becomes On 4.5 (og((/c))
+
n2- (n (n)-)33)
permuting matrices: (nn²*)
computing the original statistic: (nn)
loop over b inner permutations
permuting matrices: (n²2.)
computing the permuted statistic: Onn?)
computing the p-value: (())
computing the original statistic: O(B)
for nmc Monte Carlo samples computing the null sample: O(B computing the final v-value: (nnac)
Causal discovery. The computational complexity of our causal discovery algorithm is in the worst case Oddeaux d²), where is the number nodes and dmax is the maximal degree the graph, meaning the maximal number of adjacencies of any node. For sparse graphs (e.g., graphs with low maximal degree), the complexity can reduce to being polynomial in the number of nodes.
Signature kernel.
The computational complexity of evaluating the signature kernel scales quadrati- cally in the number of time points within a process using the s sigkerax Python package with an RBF lifting kernel and again quadratically in the number of samples when computing the full Gram matrix. The is another package, iis siiintuurr,, that allows for linear scaling in the number of time points when using linear lifting kernel. Both implementation support highly parallelized execution on GPU accelerators.
C BASELINES
In Section 4, we benchmark our method against other baselines, including Granger causality, CCM, PCMCI, and Laumann (Laumann et al., 2023). For the latter, we used their implementation provided in the causal- l-fa package. For the Granger-inplemennttion for two variables (d = 2), we used Seabold Perktold (2010), for CCM we used Javier (2021), and for PCMCI we used the tigramite package (Runge et al., 2019). In PCMCI, tests for edges are conducted by applying distance correlation based independence tests (Székely et al., 2007) between the variables' residuals after regressing out other nodes using Gaussian processes. For SCOTCH implementation (Wang et al., 2024), we use the package causica. For SCOTCH. we always use a learning rate of 0.001 and keep the same default parameters for the learning algorithm.
36

---

Published as a conference paper at ICLR 2025
D DETAILS ON THE PARTIALLY OBSERVED SETTING
Since in the partially observed setting there could in principle be infinitely many unobserved variables, special tools are required. Usually, the graphical framework of maximal ancestral graphs (MAGs) (loosely speaking DAGs with also bidirected edges) is used, which encodes ancestral relations in the DAG G and aims at graphically representing conditional independencies implied by ç involving only the (marginal of the) observed variables. The unique MAG M corresponding to the partially observed DAG 9 can be constructed via Zhang (2008) the following rules.
For v1 02 E Vobs: 1/ U22 in M if and only if there exists an inducing path relative to Vz. between "1, 02 in g.
For each pair of adjacent vertices v1 222 in M we orient the edge between them as follows:
2/2
- + 02 21 E ang, and v2 & an
-1 + 02 if u2 E ang, and 01 E ang
- + 02 if 22 & ang and vn g an
An inducing path is path with all colliders on the path being in an (e1,0)) n Vote and all other nodes on the path in Vz. The obtained MAG M9 therefore preserves causal ancestral relations with respect G. The Fast Causal Inference (FCI) algorithm (Zhang, 2008) on the observed marginal outputs an equivalence class of MAGs, known as Partial Ancestral Graph (PAG), which captures the same adjacencies but leaves some endpoints unoriented as there are multiple MAGs with the same conditional independence relations. For example, in Figure 4 FCI cannot rule out an additional latent confounder between A and C' such that the induced MAG has the same m-separation properties. Unlike FCI, by leveraging the direction of time, we can recover the full underlying MAG M which substantially more informative than FCI's PAG. First, we establish adjacencies analogous to the first part of Algorithm 2 (or simply by running FCI with our symmetric criterion) and then follow the steps in the construction of the MAG from a DAG to orient these adjacent edges v; Ugy 2/4 # Vj E Vobs:
Uj if X sym X 10,71 and X3 sym X [0.T]
o < By if X sym X/.7 and X sym (ooT] 0 ++ By if X Maym X (o.r and X Xaym X
We note that these criteria precisely encode the (non-)ancestraal relationships in the MAG construction rules. Uniqueness of the obtained result follows from Richardson & Spirtes (2002, Corollary 3.10) as two ancestral graphs Gi. G2 are equal, if they share the same adjacencies and ancestral relations.
We have thus constructed a sound and complete algorithm (assuming access to a CI oracle) to recover the unique MAG MS for the ground truth DAG G in the partially observed SDE model. To illustrate our causal discovery algorithm in practice, we conduct experiments on an SDE model with a graph G depicted in Figure 4 where Vois {A, B, D, VL {U}. E = {(A, C), (B, C), (U.C), (U, D)}. While FCI run on data coming from a Markov model with this DAG is able to detect the adjacency structure, it is unable to decide whether A truly an ancestor of C. It will correctly infer the arrow-head into C, but cannot rule out an arrow-head at A, see Figure 4. Neural network approaches like SCOTCH that directly infer the functional relationships by model fitting are not able to deal with such partially observed settings and are typically expected to predict edges that do not exists in the ground truth graph, since they can not model potentially infinitely many unobserved processes. To demonstrate this concretely, ran SCOTCH as well as our FCI-inspired algorithm on 100 SDEs with the adjacency from our example graph & and compare how often A and D are (falsely) adjacent in the output. SCOTCH predicted an edge between A and D in 88% and ours algorithm in only 8% of all settings, see also Figure 4.
37


Reviews:
[{"review_id": "XHKzASE4ek", "reviewer": "Reviewer_mqsA", "summary": "This paper introduces an innovative approach to uncovering causal relationships in stochastic processes, using conditional independence (CI) tests based on signature kernels to detect causal links within stochastic differential equation (SDE) models. It presents a comprehensive algorithm to reconstruct causal graphs, even with partially observed data and irregular sampling patterns. Benchmark tests show this method outperforms existing causal discovery techniques (in small graphs) in continuous-time settings, showing particular strength in cases with incomplete data and path-dependence (without need for hyper parameter tuning)", "questions": "- The  Oracle used for this algorithm, how likely it is to be wrong? How much it would affect the performance?\n- What happens if the underlying causal graph has a cycle? How does the algorithm handle this situation?\n- How does the algorithm handles the case where the observation in time is limited (subsampled) ?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Provides a solid framework for causal inference in continuous-time SDEs, going beyond the limitations of traditional discrete-time models.\n- Introduces a practical CI test using signature kernels, suited for handling path-dependent random variables.\n- Shows strong performance with incomplete data and irregularly sampled time series.\n- Empirical tests and real-world examples, like pairs trading, demonstrate the algorithm’s practical effectiveness and accuracy.\n- Method is not heavily dependent on hyper parameters.", "weaknesses": "- The paper assumes stationarity and acyclicity, which may restrict its use in scenarios where causal relationships change over time.\n- Limited discussion on performance of the algorithm if the IC Oracle is wrong.\n- While I appreciate the rigor in the paper, the length of the paper, considering the appendix is more than $2 /3$ of the page limit. Might be more suitable for a journal setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QUSBc6khE5", "reviewer": "Reviewer_Fppw", "summary": "The authors propose a sound and complete causal discovery algorithm for stochastic processes, incorporating a consistent signature kernel conditional independence test. The stochastic process is modeled using a stochastic differential equation (SDE), and the entire process is segmented into intervals that exhibit the Markov property with respect to an acyclic dependence graph.", "questions": "1. Could you briefly explain how to incorporate or partially incorporate PC and FCI into the proposed algorithm, given that both assume IID samples? Is any adjustment needed for non-IID samples?\n\n2. Do KCIPT and SDCIT require IID samples as well? If so, a similar question arises as in item 1.\n\n3. Are the simulated datasets used in the experiments 'continuous-time'? If so, how do you choose the discretization interval for PCMCI and other baselines that assume 'discrete-time'? Does using different discretization intervals influence their performance? How do you compare the output of PCMCI and the proposed algorithm, given that PCMCI includes time lags and may cause 'cycles' according to the definitions in this context?\n\n4. Are you considering using more baselines designed for time series, particularly non-stationary time series? The number of baselines included is limited. Is there a specific reason for not using metrics such as F1 score, precision, and recall but just SHD?\n\n5. Is there a power analysis for the conditional test, and how does it perform with different conditioning sets?\n\n6. Could you explain how to obtain bi-directed edges as shown in Figure 4?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The effect working on the 'continuous-time' path sequence is impressive.\n\n2. The signature kernel conditional independence test is a novel CI test for path sequences.\n\n3. The paper is well written, and the framework of the paper is straightforward.\n\n4. The proposed algorithm has been applied to a series of simulations and one real-world dataset.", "weaknesses": "1. There seems to be no assumption sections. The acyclic assumption seems like a common assumption used in many causal discovery methods; however, it is more restricted in this paper as a cycle could be easily created if the causal relations exist for both $X^i_{0,s}$ to $X^j_{s,s+h}$ and $X^j_{s+h,s+2h}$ to $X^i_{s+2h,s+3h}$. Such pairs of causal relations are allowed in many causal discovery methods for time series, such as PCMCI. Therefore, though the authors claim that the proposed algorithm will not rely on the 'discrete-time' assumption, they did not discuss the impact of not assuming a time lag based on the 'discrete-time' assumption and the additional limitations from the acyclic assumption in this paper, compared to many previous causal discovery algorithms. Hence, the limitation discussion and comparison is not comprehensive. The acyclic assumption in this context is not very practical.\n\n2. Does the proposed CI test only work in the specific setting of this paper? Could it be utilized outside of this setting, for more general time series?\n\n3. In the limitations and requirements section, it is stated that the proposed algorithm far exceeds other existing causal discovery methods for time series data, which may not be the best way to frame the discussion. For instance, in part (b), it is mentioned that the proposed algorithm can handle confounders; however, there are already many algorithms that allow for confounders in time series, such as LPCMCI [1] and tsFCI [2]. Additionally, there are algorithms for non-stationary time series, such as CD-NOD [3], and those with special periodic patterns, such as PCMCI$_{\\Omega}$ [4]. Therefore, it is difficult to conclude that the proposed algorithm far exceeds other related work, given different settings and assumptions.\n\n4. The number of baselines in the experiment results is limited for both causal discovery and the CI test. Please refer to the questions section for more details.\n\n5. Please correct me if I am mistaken, but it seems there is no computational complexity analysis or running time results provided.\n\n6. I may have misunderstood, but does the first selected interval of $[0, s], [s, h]$ have to start at the beginning? Based on line 233, there are two copies of vertex $V$. Does this imply $h = T$? If not, how many intervals are possible? If multiple intervals are allowed, can the acyclic assumption be relaxed since different time-ordered intervals resemble the concept of \"time lag\" in a 'discrete-time' setting?\n\n7. By intuition, is having $V_0$ and $V_1$ essentially a sub-sampling technique, where samples in $[0,s]$ and samples in $[s,h]$ are considered? The full causal graph that the algorithm aims to discover is restricted to this $V_0$ and $V_1$, and the estimated causal graph will be influenced by the intervals selected. Again, the full causal graph discussed here is different from the one in many causal discovery algorithms, referred to as the full time causal graph, which does not require sub-sampling and is more comprehensive. Therefore, this discussion needs to be handled with care.\n\n[1]Gerhardus, Andreas, and Jakob Runge. \"High-recall causal discovery for autocorrelated time series with latent confounders.\" Advances in Neural Information Processing Systems 33 (2020): 12615-12625.\n\n[2]Entner, Doris, and Patrik O. Hoyer. \"On causal discovery from time series data using FCI.\" Probabilistic graphical models 16 (2010).\n\n[3]Huang, Biwei, et al. \"Causal discovery from heterogeneous/nonstationary data.\" Journal of Machine Learning Research 21.89 (2020): 1-53.\n\n[4]Gao, Shanyun, et al. \"Causal discovery in semi-stationary time series.\" Advances in Neural Information Processing Systems 36 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "J0uLvKra3r", "reviewer": "Reviewer_BsMU", "summary": "The paper makes contributions to causal discovery in stochastic dynamical systems. In particular, it introduces a novel framework of conditional independence constraints in SDE processes, which are then leveraged to provide a causal discovery (CD) algorithm. The authors also provide a conditional independence (CI) test to evaluate these constraints from data. The authors evaluate the CD algorithm on synthetic data and compare it to other state-of-the-art baselines. They also evaluate their CI test on synthetic data and in a small case study on stock trading pairs.", "questions": "Some minor typos and unclear sentences:\n\n- Line 421: “even in the settings it was tailored to” -> what was tailored to these settings, SigKer or the state of the art?\n- For figure 2, maybe explicitly say which graph is the lifted graph (right) and which is G (left)\n- Line 157: “is inapplicable” -> “it is inapplicable”?\n- Some pedantic styling comments:\n- Line 105: you have double parenthesis with the citation to Laumaann et al.\n- Lines 170,200,420:  you appear to be using hyphens (-) instead of em dashes (---) for interjections. See the JMLR formatting guide (under dashes): https://www.jmlr.org/format/format.html", "limitations": "", "rating": 10, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and a pleasure to read. All theoretical claims are backed by careful proofs, and care is taken to ensure reproducibility of their experimental results. The authors openly address the limitations of their methodology,  and additional interesting results and discussions are provided in a well-organized and comprehensive appendix.\n\nI believe the paper earns its place in the suite of tools for causal inference with time-series data from dynamical systems. In my opinion, this is a high-quality paper that deserves acceptance.", "weaknesses": "The only major weakness is the lack of real-world experiments for the causal discovery algorithm, which I understand to be the main contribution of the paper. Only the CI test has a real-world data experiment on a downstream task, which I found creative and is well-documented in the appendix.\n\nNaturally, because we are in causal inference, real-world data with a ground truth can be difficult to find. However, I would like to point the authors to two recent papers that provide real-world data with a causal ground truth and whose settings appear to be a good fit for the method in this paper:\n\n**“[Causal discovery in a complex industrial system: A time series benchmark](https://arxiv.org/abs/2310.18654)” by Mogensen et al. (2023).**\n\nThe paper presents a real-world dataset from a dynamical system with partially observed data. The authors provide a ground-truth causal graph (section 2.4). The paper comes with a website (https://soerenwengel.github.io/essdata) with links to the dataset and preprocessing code.\n\n**“[The Causal Chambers: Real Physical Systems as a Testbed for AI Methodology](https://arxiv.org/abs/2404.11341)” by Gamella et al. (2024)**\n\nThe authors build two physical devices, one of which (wind tunnel) produces real-world, time-series data from a dynamical system. There is a causal ground-truth graph for this system (Figure 3), which the authors use to benchmark the PCMCI+ algorithm (Figure 6a). I believe this is an extension of one of your baselines (PCMCI), which makes me suspect your method is also applicable. The authors provide a well-documented [notebook ](https://github.com/juangamella/causal-chamber-paper/blob/main/case_studies/causal_discovery_time.ipynb) to download the dataset and reproduce the PCMCI+ experiment. Using your method may be plug-and-play in this case.\n\nThere may be other suitable real-world datasets, but I found none after this search. A real-world experiment for the main contribution of the paper (the causal discovery algorithm) would further elevate the value of the paper, and I would be happy to raise my score as a result. This is only a suggestion, and my decision to accept is independent of whether the authors do this or not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2bmpmwhOYE", "reviewer": "Reviewer_4hZY", "summary": "This paper introduces a novel approach for causal discovery in stochastic processes modeled by stochastic differential equations (SDEs). The authors propose a conditional independence (CI) test based on signature kernels, which enables the identification of causal relationships in continuous-time dynamical systems, even under irregular or partially observed data. Key contributions include a causal discovery algorithm that leverages the directionality of time, as well as an efficient signature kernel-based CI test.", "questions": "The experimental setup involves setting small parameters for self-loops (e.g.,  $a_{ii} \\sim  U([-0.5, 0.5])$), while the parameters influencing causal effects between different variables are set higher (e.g., $a_{ij} \\sim U([-2,-1] \\cup [1, 2])$). While I understand this may help to emphasize inter-variable causal relationships, practical applications may not always exhibit this distinction so clearly. Additionally, could the authors clarify whether errors related to self-loops are reported in the Structural Hamming Distance (SHD) results?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-motivated, presenting a clear need for improved causal discovery methods within the context of stochastic processes.\n2. Extensive experimental evaluations support the effectiveness of the proposed approach. The method demonstrates consistent superiority over several baseline models, underscoring its potential contributions to the field.", "weaknesses": "1.\tThe paper’s claims regarding diffusion-dependence cases may be somewhat overstated. In particular, for SDE models involving \"driving noise\" (i.e., cases where the diffusion coefficient depends on $X_t$), certain **causal graphs may not be identifiable from observational data**. See example 5.5 in [1]. In such cases, identifying the generator of the SDE model—so as to identify the post-interventional distribution—may be a more reasonable goal, as explored in [2] for linear SDEs. This may also provide some insight into the **diffusion-dependence** results presented in Table 1, where the proposed method shows comparatively lower performance.\n\n[1] Hansen, Niels, and Alexander Sokol. \"Causal interpretation of stochastic differential equations.\" (2014): 1-24.\n\n[2] Wang, Yuanyuan, et al. \"Generator identification for linear SDEs with additive and multiplicative noise.\" Advances in Neural Information Processing Systems 36 (2024).\n\n2.\tThe section on signature kernels in Section 2 is mathematically dense and may be challenging for readers unfamiliar with the topic. Including more intuitive explanations would enhance accessibility.\n3.\tGiven the extensive use of mathematical notations, a summary table listing the key notations could be helpful for readers in following the manuscript’s developments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)