CUTS: Neural Causal Discovery from Irregular Time-Series Data
Authors: Yuxiao Cheng
Runzhao Yang
Tingxiong Xiao
Zongren Li
Jinli Suo
Kunlun He
Qionghai Dai
Venue: ICLR 2023 poster (2023)
Keywords: Time series
Granger causality
Causal discovery
Neural networks
Graph neural networks

Abstract: Causal discovery from time-series data has been a central task in machine learning. Recently, Granger causality inference is gaining momentum due to its good explainability and high compatibility with emerging deep neural networks. However, most existing methods assume structured input data and degenerate greatly when encountering data with randomly missing entries or non-uniform sampling frequencies, which hampers their applications in real scenarios. To address this issue, here we present CUTS, a neural Granger causal discovery algorithm to jointly impute unobserved data points and build causal graphs, via plugging in two mutually boosting modules in an iterative framework: (i) Latent data prediction stage: designs a Delayed Supervision Graph Neural Network (DSGNN) to hallucinate and register unstructured data which might be of high dimension and with complex distribution; (ii) Causal graph fitting stage: builds a causal adjacency matrix with imputed data under sparse penalty. Experiments show that CUTS effectively infers causal graphs from irregular time-series data, with significantly superior performance to existing methods. Our approach constitutes a promising step towards applying causal discovery to real applications with non-ideal observations.

Published as a conference paper at ICLR 2023
CUTS: NEURAL CAUSAL DISCOVERY FROM IRREGULAR TIME-SERIES DATA
Yuxiao Cheng' Jinli Suo 12-
Runzhao Yang'
Tingxiong Xiao!
Zongren Li
Kunlun He
Qionghai Dai
'Department of Automation, Tsinghua University
PInstitute for Brain and Cognitive Science, Tsinghua University (THUIBCS)
Chinese PLA General Hospital
[cyx22, yangrz20, xtx22 @ma 1s. twsinnhuaa.eee.. en [ zizongren, kunlunhe) org {ilsuo, ghdai]ettinghueeeeee
ABSTRACT
Causal discovery from time-series data has been central task in machine learn- ing. Recently, Granger causality inference is gaining momentum due to its good explainability and high compatibility with emerging deep neural networks. How- ever, most existing methods assume structured input data and degenerate greatly when encountering data with randomly missing entries non-uniform sampling frequencies, which hampers their applications in real scenarios. To address this is- sue, here we present CUTS, neural Granger causal discovery algorithm to jointly impute unobserved data points and build causal graphs, via plugging in two mutu- ally boosting modules in iterative framework: (i) Latent data prediction stage: designs a Delayed Supervision Graph Neural Network (DSGNN) to hallucinate and register irregular data which might be of high dimension and with complex distribution; (ii) Causal graph fitting stage: builds a causal adjacency matrix with imputed data under sparse penalty. Experiments show that CUTS effectively in- fers causal graphs from irregular time-series data, with sigmificantly superior per- formance to existing methods. Our approach constitutes promising step towards applying causal discovery to real applications with non-ideal observations.
INTRODUCTION
Causal interpretation of the observed time-series data can help answer fundamental causal questions and advance scientific discoveries in various disciplines such medical and financial fields. To enable causal reasoning and counterfactual prediction, researchers in the past decades have been dedicated to discovering causal graphs from observed time-series and made large progress (Ger-
hardus& & Runge 2020 Tank et al. 2022 Khanna Tan 2020 Wu et al. 2022 Pamfil al. 2020 Lowe et al. 2022: Runge, 2021). This task is called causal discovery causal structure learning, which usually formulates causal relationships as Directed Acyclic Graphs (DAGs). Among these causal discovery methods, Granger causality (Granger 1969 Marinazzo al. 2008) is attracting wide attentions and demonstrates advantageous due to its high explainability and compatibility with emerging deep neural networks (Tank et al.) 2022 Khanna & Tan 2020 Nauta et al. 2019)).
In spite of the progress, actually most existing causal discovery methods assume well structured time-series, i.e., completely sampled with identical dense frequency. However, in real-world scenarios the observed time-series might suffer from random data missing (White et al.) 2011) or be with non-uniform periods. The former usually caused by sensor limitations transmission loss, while the latter occurs when multiple sensors are of distinct sampling frequencies. Robustness such data imperfections is urgently demanded, but has not been well explored yet so far. When confronted with unobserved data points, some straightforward solutions fill the points with zero padding, interpolation, or other imputation algorithms, such as Gaussian Process Regression or beural-networr-basee approaches (Cini et al.] 2022; Cao et al. [0188] Luo et al. (2088). We will show the experiments section that addressing missing entries via performing such trivial data imputation in pre- pro-pesocssng manner would lead to hampered causal conclusions.
Corresponding author

---

Published as a conference paper at ICLR 2023
To push causal discovery towards real applications, attempt to infer reliable causal graphs from irregular time-series data. Fortunately, for data that are assumed to be generated with certain causal structural models (Pamfil et al., 2020; Tank et al., 2022). a well designed neural network can fill small proportion of missing entries decently given a plausible causal graph, which would conversely improve the causal discovery, and so forth. Leveraging this benefit, we propose to conduct causal discovery and data completion in mutually boosting manner under an iterative framework, instead of sequential processing. Specifically, the algorithm alternates between two stages, i.c., (a) Latent data prediction stage that hallucinates missing entries with a delayed supervision graph neural net- work (DSGNN) and (b) Causal graph fitting stage inferring causal graphs from filled data under sparse constraint utilizing the extended nonlinear Granger Causality scheme. We name our algo- rithm Causal discovery from ilre Time-Series (CUTS), and the main contributions are listed as follows:
We proposed CUTS, a novel framework for causal discovery from irregular time-series data, which to our best knowledge the first to address the issues of irregular time-series in causal discovery under this paradigm. Theoretically CUTS can recover the correct causal graph with fair assumptions, as proved in Theorem
In the data imputation stage we design a deep neural network DSGNN, which success- fully imputes the unobserved entries in irregular time-series data and boosts the subsequent causal discovery stage and latter iterations.
We conduct extensive experiments to show our superior performance to state-of-the-ar causal discovery methods combined with widely used data imputation methods, the ad- vantages of mutually-boone -boosinng strategies over sequential processing, and the robustness of CUTS (in Appendix Section A.4)
2 RELATED WORKS
Causal Structural Learning/ Causal Discovery. Causal Structural Learning (or Causal Dis- covery) is fundamental and challenging task in the field of causality and machine learning, which can be categorized into four classes. (i) Constraint based approaches which build causal graphs by conditional independence tests. Two most widely used algorithms are PC (Spirtes & Glymour 1991) and Fast Causal Inference (FCI) (Spirtes et al.] 2000) which is later extended by |Ennner & Hoyer (2010) to time-series data. Recently, |uugee et al. propose PCMCI to combine the above two constraint- bansed algorithms with linear/nonlincar conditional independence tests (Gerhardus & Runge 2020 Runge| 2018b) and achieve high scalability on large scale time-series data. (ii) Score- based learning algorithms based on penalized Neural Ordinary Differential Equations (Bellot et al.) 2022) or acyelicity constraint (Pamfil et al., (020). (iii) Convergent Cross Mapping (CCM) firstly proposed by SSgghhara et al. (2012) that tackles the problems of nonseparable weakly connected dynamic systems by reconstructing nonlinear state space. Later, CCM is extended to situation of synchrony (Ye et al. 2015), confounding (Benkō al., (0200) or sporadic time series (Brouwer ct al. 2021]. (iv) Approaches based on Additive Noise Model that infer causal graph based on ad- ditive noise assumption (Shimizu al., 2006 Hoyer et al., 2008). Recently [Hoyer al. (2008) extend ANM to nonlinear models with almost any nonfinearities. (v) Granger causality approach proposed by Granger (1969) which has been widely used to analyze the temporal causal relation- ships by testing the aid of a time-series on predicting another time-series. Granger causal analysis originally assumes that linear models and the causal structures can be discovered by fitting Vector Autoregressive ( (VAR) model. Later, the Granger causality idea was extended to nonlinear situations (Marinazoo et al. 2008). Thanks its high compatibility with the emerging deep neural network, Granger causal analysis is gaining momentum and is used in our work for incorporating neural network imputing irregular data with high complexities.
Neural Granger Causal Discovery. With the rapid progress and wide applications of deep Neural Networks (NNs), researchers begin to utilize RNN (or other NNs) to infer nonlinear Granger causal- ity. Wu et al. (2022) used individual pair-wise Granger causal tests, while Tank et al. (2022) inferred Granger causality directly from component- wise NNs by enforcing sparse input layers. Building on
Tank et al. (2022> 's idea, Khanna & Tan (2020) explored the possibility of inferring Granger causal- ity with Statistical Recurrent Units (SRUs,/Oliaa et al. (2017). Later, Löwe et al. (2022) extends the neural Granger causality idea to causal discovery on multiple samples with different causal relation-
2

---

Published as a conference paper at ICLR 2023
ships but similar dynamics. However, all these approaches assume fully observed time-series and show inferior results given irregular data, which is shown in the experiments section. In this work, leverage this Neural Granger Causal Discovery idea and build two-stage iterative scheme to impute the unobserved data points and discover causal graphs jointly.
Causal Discovery from Irregular Time-series. Irregular time-series very common in real scenarios, causal discovery addressing such data remains somewhat under-explored. When con- fronted with data missing, directly conducting causal inference might suffer from significant error (Runge 2018a; Hyttinen et al. (016)). Although joint data imputation and causal discovery has been explored static settings (Tu et al. 2019 Gain Shpitser 2018 Morales-Alvarez et al.j 2022 Geffner et al., (022). it is still under explored in time series causal discovery. There are mainly two solutions either discovering causal relations with available observed incomplete data (Gain & Shpitser 2018 Strobl et al., 2018) or filling missing values before causal discovery (Wang) jet al. 2020, Huang et al. 2020p. To infer causal graphs from partially observed sereseries, sev- eral algorithms are proposed, such as Expectation Maximization approach (Gong et al. (2015), La-
Expectation-Mxximizatioo
tent Convergent Cross Mapping (Brouwer et al.) 2021). Neural-ODE based approach (Bellot et al.
2022). Partial Canonical Correlation Analysis (Partial CCA). Generalized Lasso Granger (GLG) (Iseki et al., (019), etc. Some other researchers introduce data imputation before causal discovery and have made progress recently. For example, [Cao et al. (2018) learn impute values via itera- tively applying RNN and Cini et al. (2022) use Graph Neural Networks, while a recently proposed data completion method by Chen al. (2022) uses Gaussian Process Regression. In this paper, we use a deep neural network similar to Cao et al. (2018)'s work, but differently, we propose to impute missing data points and discover causal graphs jointly instead of sequentially. Moreover, these two processes mutually improve each other and achieve high performance.
3 PROBLEM FORMULATION
3.1 NONLINEAR STRUCTURAL CAUSAL MODELS WITH IRREGULAR OBSERVATION
Let us denote by X' = [ L uniformly sampled observation of a dynamic system, in which 2 represents the sample vector at time point and consists of N variables {2r,), } with E [1..... L} and E {1. (1..... N}. In this paper, we adopt the representation proposed by Tank et al. (2022) and Khanna Tan 22000) and assume each sampled variable Ft, be generated by the following model
F1,5 [ F(-r:- Ft-r:-1INN) + Ct.a: i i= 1,2,.... N.
Here denotes the maximal time lag. In this paper, we focus on dealing with causal inference from irregular time series, and use a bi-value observation mask or, to label the missing entries, i.c., the observed vector equals to its latent version when 0z,i equals to 1: Tz.; - Fz,s Or,5- In this paper we consider two types of recurrent data missing practical observations:
Random Missing, The ith data point in the observations are missing with a certain probability pi here in our experiments the missing probability follows Bernoulli distribution ot,5 Ber(1 Pt).
Periodic Missing, Different variables are sampled with their own periods T, We model the sampling process for ith variable with an observation function or, Ene 8(t nfi), T, 1,2, with o(-) denoting the Dirac's delta function.
3.2 NONLINEAR GRANGER CAUSALITY
For a dynamic system, time-series i Granger causes time-series when the past values of time-series 2; aid in the prediction of the current and future status of time-series æz. The standard Granger causality is defined for linear relation scenarios, but recently extended to nonlinear relations:
Definition Time-series i Granger cause j if and only if there exists xt-Tu-11, Dt-r:
f ( 2' 1,51 11- +
(2)
f ( Lt- rit- 1,6 Rt 21-ra-1,N)
i.e., the past data points of time-series influence the prediction of at...
3

---

Published as a conference paper at ICLR 2023
Ty iterations
It: Iterations
Non-imputed and Non-sueervsoory
Imputted but Non-supervisery
Imputed and Supervisory
[b]
Latent Data Prediction Stage
Causal Graph Fitting Stage
Unobserved Value
T+.
Observed Value
Imputation
M
Tmax
Imputed Value
M
Neural Netwerk
Epreed
Delayedd Superdiiion
Exprad
M
Figure I: Illustration of the proposed CUTS, with 3-variable example. (a) Illustration of our learn- ing strategy described in Section 4.3 with three groups of iterations being of the same alternation scheme shown in (b) but different settings in data imputation and supervised model learning. (b) Illustration of each iteration in CUTS. The dynamics reflected by the observed time-series I1 and 22 are described by DSGNN in the Latent data prediction stage (left). With the modeled dynam- ies, unobserved data points are imputed (center) and fed into the Causal graph fitting stage for an improved graph inference (right).
Granger causality highly compatible with neural networks (NN). Considering the universal ap- proximation ability of NN (Hornik et al. 1989), it is possible to fit causal relationship function with component-wise MLPs or RNNs. Imposing a sparsity regularizer onto the weights of net- work connections, as mentioned by Tank et al. (2022) and Khanna & Tan (2020), NNs can learn the causal relationships among all variables. The inferred pair-wise Granger causal relationships can then be aggregated into Directed Acyclic Graph (DAG), represented as adjacency matrix N
A = {aa; Ji.j=1 where ai = 1 denotes time-series Granger causes j and 0:j 0 means oth- erwise. This paradigm is well explored and shows convincing empirical evidence in recent years
Tank et al. 2022 Khanna & Tan 2020) Löwe et al. 2022).
Although Granger causality is not necessarily the true causality, Peters et al. (2017) provide justifi- cation (time-invariant) Granger causality when assuming no unobserved variables and no instan- taneous effects, is mentioned Löwe al. (2022) and Vowels et al. (202T).
In this paper, we propose a new inference approach to successfully identify causal relationships from irregular time-series data.
4 IRREGULAR TIME-SERIES CAUSAL DISCOVERY
CUTS implements the causal graph as a set of Causal Probability Graphs (CPGs) g (M, J mur') where the element my,aj E M, represents the probability of causal influence from Zt-r,i to Lt.j, i.e. Mr.ij = p( - æt.j). Since we assume no instantaneous effects, time- series Granger cause if and only if there exist causal relations on least one time lag, we define our discovered causal graph À to the maximum value across all time lags {1,..., Tman)
قبب max 1,....:.... M. .5))
(3)
Specifically, if J..j is penalized to zero (or below certain threshold), we deduce that time-series i does not influence the prediction time-series j. i.e., i does not Granger cause j.
During training, we alternatively learn the prediction model and CPG matrix, which are respec- tively implemented by Latent data prediction stage and Causal graph fitting stage. Besides, proper learning strategies designed to facilitate convergence.
4.1 LATENT DATA PREDICTION STAGE
The proposed Latent data prediction stage is designed to fit the data generation function for time- series with neural network fø.. which takes into account its parent nodes in the causal graph. Here we propose Delayed Supervision Graph Neural Network (DSGNN) for imputing the missing entries in the observation.
4

---

Published as a conference paper at ICLR 2023
The imputs to DSGNN include all the historical data points (with maximum time lag Tmax) Tt-r:t-1,i and the discovered CPGs. During training we sample the causal graph with Bernoulli distribution, in a similar manner to Lippe et al. (2021)ss work, and the prediction & is the output of the neural network So.
L1,1 fa. (X' O S) fa ( @ $1: -.- O $1:7,Ni),
(4)
where S { ,, and 8T,6) Ber(1 my,a) and @ denotes the Hadamard product. S is sampled for each training sample in a mini-batch. The fitting is done under supervision from the observed data points. Specifically, we update the network parameters oi by minimizing the following loss function
Lpred (2,2,0)= = E (C2 (LLL .
(5)
7(01.,..00::...
where O2 denotes the observation mask, (-) is the dot product, and L2 represents the MSE loss function. Then, the data imputation is performed with the following equation
(m++1)
Ot,i and m 2 11
(6)
Or = 1 or m < m
Here m indexes the iteration steps, and 30 denotes the initial data (unobserved entries filled with zero order holder). a is selected to prevent the abrupt change of imputed data. For the missing points, their predicted value _.(rm) is unsupervised with L but updated to ((m) obtain a "delayed" error in causal graph inference. Moreover, we impute the missing values with the help of discovered
CPG G (sampled with Bernoulli Distribution), illustrated in Figure (b), which proved to significantly improve performance in experiments.
4.2 CAUSAL GRAPH DISCOVERY STAGE
After imputing the missing time-series, we proceed to learn CPG in the Causal graph fitting stage, to determine the causal probability p( -> Ft.j) = my..6. we model this likelihood with m,,53 = (0,,,)) where (-) denotes the sigmoid function and 0 the learned parameter set. Since we assume no instantaneous effect, it is unnecessary to learn the edge direction in CPG.
In this stage we optimize the graph parameters 0 by minimizing the following objective
Egraph &L R.,.,O. 0.0 = Lpred
+ (0)0()
where Lpred is the squared error loss penalizing prediction error defined in Equation (5) and || 1/1
being the L1 regularizer to enforce sparse connections on the learned CPG. If E [1, Tmazz] Oz.i5 penalized -o (and m.,ij + 0), then deduce that time-series i does not Granger cause j-
4.3 THE LEARNING STRATEGY.
The overall learning process consists of n = n, + T22 + n2 epochs, which illustrated in Figure (a): in the first ni epochs DSGNN and CPG are optimized without data imputation (missing entries are set with initial guess); in the next n2 epochs the iterative model learning continues with data imputation, but the imputed data are not used for model supervision; for the last na epochs the learned CPG is refined based on supervision from all the data points (including the imputed ones).
The main training process the alternation between Latent data prediction stage and Causal graph fitting stage. Considering that after sufficient iterations (here + f22) the unobserved data points can be reliably imputed with the discovery of causal relations, and we can incorporate these predicted points to supervise the model and fine-tune the parameters to improve the perfor- mance further. the last ny epochs CPG optimized with the loss function
Fine-tuning.
Eee (E, (x,²)) L2 (#1.L. LI. + 1l)a(0))l1
(8)
Parameter Settings. During training the 7 value for Gumbel Softmax is initially set to a relatively high value and annealed to low value in the first nı +22 epochs and then reset for the last ny epochs. The learning rates for Latent data prediction stage and Causal graph fitting stage are respectively set as Ir Iramn and Ir graphh and gradually scheduled to 0. 1. and 0. p. during all n; + n2 + ng epochs. The detailed hyperparameter settings are listed in Appendix Section A.3
5

---

Published as a conference paper at ICLR 2023
4.4 CONVERGENCE CONDITIONS FOR GRANGER CAUSALITY.
We show in Theorem that under certain assumptions, the discovered causal adjacency matrix will converge to the true Granger causal matrix.
Theorem Given a time-series dataset X = (a1LA generated with Equation we have
1. YYE VT {I.... Tmaa?, causal probability matrix element my.ūj (B converges to if time-series does not Granger cause j. and
2. 3r E {I,.., Tmaa J Mrrjj converges to 1 time-series Granger cause j.
if the following two conditions hold:
1. DSGNN fer in Latent data prediction stage model generative function Is with an error smaller than arbitrarily small value eNN,i
Xp, where STā5=1 is set 2. 3Ay Vi,j 1,..., N, [1,, (X (X fe, (X o ST > S with element $7,1j =
The implications behind these two conditions can be intuitively explained. Assumption is intrinsi- cally the Universal Approximation Theorem (Hornik et al. 1989) of neural network, i.e., the network of an appropriate structure and fed with sufficient training data, Assumption 2 means there exists a threshold Åo to binarize fl (X O Sr,j==1 fa. (X @ Sr,ij=u)l,, serving as an indicator as to whether time-series j contributes to prediction
The proof of Theorem iss detailed in Appendix Section A.I Although the convergence condition is relevant to the appropriate setting of X, we will show in Appendix Section A.4.6 that our algorithm is robust to the setting changes of X over a wide range.
5 EXPERIMENTS
Datasets. We evaluate the performance of the proposed causal discovery approach CUTS on both numerical simulation and real-scenario inspired data. The simulated datasets come from linear Vector Autoregressive (VAR) model and nonlinear Lorenz-96 model (Karimi & Paul 2010). while the real-scenario inspired datasets are from NetSim (Smith al., [011], an fMRI dataset describing the connecting dynamics of 15 human brain regions. The irregular observations are generated according to the following mechanisms: Random Missing (RM) simulated by sampling uniform distribution with missing probability pı; Periodic Missing (PM) is simulated with sampling period T, randomly chosen for each time-series with the maximum period being T Tmax- For statistical quantitative evaluation of different causal discovery algorithms, we take average over multiple p3 and T; in our experiments.
To demonstrate the superiority of our approach, compare with five baseline algorithms: (i) Neural Granger Causality (NGC, Tank et al. (2022), which utilizes MLPs and RNNs combined with weight penalties infer Granger causal relationships, in the experiments we use the component-wise MI.P model; (ii) economy-SRL (eSRU, Khanna & Tan (2020). a vari- ant SRU that is less prone over- fitting when inferring Granger causality; (iii) PCMCI (proposed method in which we use conditional independence
Baseline Algorithms.
by Runge et al.). non- tests provided along with its repository_ i.e., ParCorr (linear partial correlation) for conditional independence tests for linear scenarios and GPDC (Gaussian Process regression and Distance Cor- relation Rasmussen] (2003) (Székely et al. (2007) for nonlinear scenarios. (iv) Latent Convergent Cross Mapping (LCCM, Brouwer et al. (2021)) CCM-based approach that also tackles the irreg- ular time-series problem. (v) Neural Graphical Model (NGM, Bellot et al. (2022)) which is based on Neural Ordinary Differential Equations (Neural-ODE) to solve the irregular time-series problem. In terms of guantitative evaluation, we use area under the ROC curve (AUROC) as the criterion. For NGC, AUROC values are computed by running the algorithm with À varying within range of values. For eSRU, PCMCI, LCCM, and NGM, the AUROC values are obtained with different thresholds. For fair comparison, we applied parameter searching to determine the hyperparameters

---

Published as a conference paper at ICLR 2023
VAR Simulation
Lorenz-96 Simulation
Amaann M Myp Myp M mn podppb Mh M
Vo
Time-series
Groundtruth CPG
Time-series
Groundtruth CPG
Figure 2: Examples of our simulated VAR and Lorenz-96 datasets, with two of the total 10 gener- ated time-series from the groundtruth CPG plotted orange and blue solid lines, while the non- uniformly sampled points are labeled with scattered points.
of the baseline algorithms with the best performance. For baseline algorithms unable to handle ir- regular time-series data, i.e., NGC, PCMCI, and eSRU, imputed the irregular time-series before feeding them to causal discovery modules, and use three data imputation algorithms, i.c., Zero- order Holder (ZOH), Gaussian Process Regression (GP), and Multivariate Time Series Imputation by Graph Neural Network (GRIN, Cini et al. (2022)
5.1
VAR SIMULATION DATASETS
VAR datasets are simulated following
Tmaa
3t A, +
where the matrix A, the sparse autoregressive coefficients for time lag т. Time-series Granger cause time-series j if 3r E {l,...,Tma: Tmar) Dr.ij > 0. The objective of causal dis- covery reconstruct the non-zero elements causal graph A (where each element of A aij max(a1.5) Lift..... Of mr )) with Á. We set Tmee 3, N 10 and time-series length L = 10000 in this experiment. For missing mechanisms, we set = 0.3, 0.6, respectively for respectively for Periodic Missing. Experimental results are We can see that CUTS beats PCMCI, NGC, and eSRU com-
Random Missing and Taaa shown in the upper half of Table [ bined with ZOH, GP, and GRIN most cases, except for the case of VAR with random missing (p 0.3) where PCMCI GRIN is better by only small margin (+0.0012). The superiority is especially prominent when with a larger percentage of missing values (p = 0.6 for random missing and Tmex 4 for periodic missing). Differently, data imputation algorithms GP and GRIN provide performance gain in some scenarios but fail to boost causal discovery in others. This indicates that simply combining previous data imputation algorithms with causal discovery algorithms cannot give stable and promising results, and is thus less practical than our approach. We also beat LCCM and NGM which originally tackles the irregular time series problem by a clear margin. This hampered performance may be attributed to the fact that LCCM and NGM both utilize Neural-ODE to model the dynamics and do not cope with VAR datasets well.
5.2 LORENZ-96 SIMULATION DATASETS
Lorenz-96 datasets simulated according
dæy,i
= It, xx,141) 1 Zt,4 + F,
(10)
di
where -11,5-1( 11,141 is the advection term, 2,,; is the diffusion term, and F is the external forcing (a larger F implies a more chaotic system). this Lorenz-96 model each time-series x; is affected by historical values of four time-series 2;-2, 2;-1, H,, 32 and each row in the ground truth causal graph A has four non-zero elements. Here we set the maximal time-series length I. = 1000, N 10, force constant F 10 and show experimental results for F = 40 in the Appendix Section A.4.7 From the results in the lower half of Table [ one can draw similar conclusions to those VAR datasets: CUTS outperforms baseline causal discovery methods either with without data imputation.
5.3 NETSIM DATASETS
7

---

Published as a conference paper at ICLR 2023
Table I: Performance comparison of CUTS with (i) PCMCI, eSRU, NGC combined with imputation method ZOH, GP. GRIN and (ii) LCCM, NGM which do not need data imputation. Experiments are performed on VAR and Lorenz-96 datasets in terms of AUROC. Results are averaged over 10 randomly generated datasets.
VAR with Random Missing
VAR with Periodic Missing
Methods
Imputation
p 0.3
p 0.6
Tmaz 2
Tmax
ZOH
0.9904 = 0.0078
0.9145 + 0.0204
0.9974 + 0.0040
0,9787 1 0.0196
PCMCI
GP
0.9930 + 0.0072
0.8375 0.0651
0.9977 0.0038
0.9332 + 0.1071
GRIN
0.9983 = 0.0028
0.9497 = 0.0132
0.9989 0.0017
0.9774 + 0.0169
70H
0.9899 + 0.0105
0.9325 + 0.0266
0.9808 + 0.0117
0.9439 + 0.0264
NGC
GP
0,9821 = 0.0097
0.5392 0.1176
0.9833 0,0108
0.7350 0.2260
GRIN
0.8186 + 0.17200
0.5918 + 0.1170
0.8621 + 0.0661
0.6677 + 0.1350
ZOH
0.9760 = 1.0113
0.8464 0.0299
0.9580 = 0.0276
0.9214 0,0257
eSRU
GP
0.9747 + 0.0096
0.8988 + 0.0301
0.9587 + 0.0191
0.8166 0.15
GRIN
0.9677 = 0.0134
0.8399 = 0.0242
0.9740 0.0150
0.8574 + 0.0869
L.CM
0.6851 + 1.0411
0.6530 0.0212
0.6462 0.0225
0.6388 + 0.0170
NGM
0.7608 = 0.0910
0.6350 + 0.0770
0.8596 + 0.0353
0.7968 0.0305
CUTS (Proposed)
0.9971 + 0.0026
0.9766 + 0.0074
0.9992 0.0016
0.9958 + 0.0069
Lorenz-96 with Random Missing
Lorenz with Periodic Missing
Methods
Imputation
p= 0.3
p 0.6
Tmax = =2
T Timx 4
ZOH
0.8173 + 0.0491
0.7275
0.0534
0.7229 0.0348
0.7178 0.0668
PCMCI
GP
0.7545 = 0.0585
0.7862 = 0.0379
0.7782 + 0.0406
0.7676 + 0.0360
GRIN
0.8695 + 0.0301
0.7544 0.0404
0.7299 + 0.0545
0.7277 + 0.0947
ZOH
0,9933 = 0.0058
0.9526 = 0.0220
0.9903 + 0.0096
0.9776 + 0.0120
NGC
GP
0.9941 + 0.0064
0.5000 + 0.0000
0.9949 + 0.0050
0.7774 4: 0.2300
GRIN
0.9812 = 0.0105
0.7222 0.0680
0.9640 0.0193
0,8430 0.0588
ZOH
0.9968 + 0.0038
0.9089 1 0.0261
0.9958 + 0.0031
0.9815 1 0.0148
cSRU
GP
0.9977 = 0.0035
0.9597 0.0169
0.9990 0.0015
0.9628 + 0,0371
GRIN
0.9937 1 0.0071
0.9196 0.0251
0.9873 1 0.0110
0.8400 0.1451
LCCM
0.7168 = 0.0245
0.6685 + 0.0311
0.7064 + 0.0324
0.7129 + 0.0235
NGM
0.9180 + 0.0199
0.7712 0.0456
0.9751 0.0112
0.9171 1 0.0189
CUTS (Proposed)
0.9996 = 0.0005
0.9705 0.0118
1.0000 = 0.0000
0.9959 + 0.0042
To validate the performance of CUTS on real- scenario data, We use data from 10 humans in NetSim dataset=] which is generated with syn- thesized dynamics of brain region connectivity and unknown us and the algorithm. The total length of each time-series data I, = 200 and the number of time-series N 15. By testing our CUTS on this dataset we show that our algo- rithm is capable of discovering causal relations with irregular time-series data for scientific dis- covery. However, L 200 is a small data size, therefore we only perform experiments with the Random Missing situation. Experimental re- sults shown in Table 2 tell that our approach beats all existing methods on both missing pro- portions.
Table 2: Quantitative results on NetSim dataset. Results averaged over 10 human brain subjects.
NetSim with Random Missing
Met.
Imp.
p= = 0.1
p p= 0.2
ZOH
0.7625 + 0.0539 0.7455 = 0.0675
PCMCI
GP
0.7462 1 0.039
0.7551 1 0.0451
GRIN
0.7475 = 0.0517
0.7353 = 0.0611
ZOHI
0.7656 + 0.0576
0.7668 1 0.0403
NGC
GP
0.7506 = 0.0532
0.7545 = 0.0518
GRIN
0,6744 1: 0.0743
0,5826 1 0,0476
ZOH
0.6384 + 0.0473
0.6592 + 0.0248
eSRU
GP
0.6147 1 0.0454
0.6330 1 0.0449
GRIN
0,6141 1:200 0.0529
0.5818 1 0.0588
LCCM
0.7711 + 0.0301
0.7594 + 0.0246
NGM
0.7417 1 0.0380
0.7215 + 0.0330
CUTS
0.7948 + 0.0381
0.7699 + 0.0550
5.4 ABLATION STUDIES
Besides demonstrating the advantageous performance of the final results, we further conducted a series of ablation studies quantitatively evaluate the contributions of the key technical designs or learning strategies in CUTS. Due to page limit, we only show experiments on Lorenz-96 datasets with Random Missing settings this section, and leave the other results in the Appendix Section
A.4.2
Causal Discovery Boosts Data Imputation. To validate that Latent data prediction stage helps Causal graph fitting stage, we reset CPGs M to all-one matrices in Latent data prediction
Shared http:///ww..tmiiooo...ddddaeeees
8

---

Published as a conference paper at ICLR 2023
Table 3: Quantitative results of ablation studies. "CUTS (Full)" denotes the default settings in this paper. Here we run experiments on Lorenz-96 datasets. Ablation study results on other datasets are provided in Appendix Section A.4.2
Lorenz-96 with Random Missing
Lorenz-96 with Periodic Missing
Methods
p 0.3
p = 0.6
Taaz 2
T Taaz 4
CUTS (Full)
0.9996 + 0.0005
0.9705 + 0,0118
1.0000 = 0.0000
0.9959 = 0.0042
ZOH for Imputation
0.9799 + 0.0071
0.8731 1 0.0312
0.9981 + 0.0021
0.9865 0.0128
GP for Imputation
0.9863 = 0.0058
0.8575 + 0.0536
0.9965 = 0.0036
0.9550 = 0.0407
GRIN for Imputation
0.9793 1 0.0126
0.8983 1: 0,0299
0.9869 + 0.0101
0,9325 + 0.0415
No Imputation
0.9898 = 0.0045
0.9206 0.0216
0.9968 = 0.0032
0.9797 0.0204
Remove CPG for Imput.
0.9972 1 0.0021
0,9535 1 0.0167
0.9989 1 0.0011
0.9926 + 0.0045
No Finetuning Stage
0.9957 + 0.0036
0.9665 + 0.0096
0.9980 = 0.0025
0.9794 0.0124
stage and then εt, is predicted with all time-series instead of only the parent nodes. This ex- periment is shown as "Remove CPG for Imput." " Table It is observed that introducing CPGs in data imputation is especially helpful with large quantities of missing values (p 0.6 for Random Missing or T Taa for Periodic Missing). Comparing with the scores in the first row, we can see that introducing CPGs in data imputation boosts AUROC by 0.0011 0.0170.
Data Imputation Boosts Causal Discovery. To show that Causal graph fitting stage helps Latent datu prediction stage, we disable data imputation operation defined in Equation 6 i.e., 0. In other words, Causal graph fitting stage is performed with just the initially filled data (Appendix Section AA.32)), with the results shown as "No Imputation" in Table 6 Compared with the first row, we can see that introducing data imputation boosts AUROC by 0.0032 ~ 0.0499. We further replace data imputation module with baseline modules (ZOH, GP, GRIN) show the effectiveness of our design. It is observed that our algorithm beats "ZOH for Imputation", "GP for Imputation", "GRIN for Imputation" in most scenarios.
We disable the finetuning stage and find that the per- formance drops slightly, as shown in the "No Finetuning Stage" row in Table In other words, the finetuning stage indeed helps to refine the causal discovery process.
Finetuning Stage Raises Performance.
5.5 ADDITIONAL EXPERIMENTS
We further conduct additional experiments in Appendix to show experiments on more datasets (Ap- pendix Section A.4.1). ablation study for choice of epoch numbers (Appendix Section AA..3). ab- lation study results on VAR and NetSim datasets (Appendix Section (A.42)). performance on 3- dimensional temporal causal graph (Appendix Section A.4.4). CUTS's performance superiority on regular time-series (Appendix Section A.4.5). robustness to different noise levels (Appendix Section A.4.8), robustness to hyperparameter settings (Appendix Section A.4.6). and results on Lorenz- with forcing constant F = 40 (Appendix Section A.4.7). We further provide implementation details and hyperparameters settings of CUTS and baseline algorithms Appendix Section A.3 and the pseudocode of our approach in Appendix Section A.5
6 CONCLUSIONS
In this paper we propose CUTS, a time-series causal discovery method applicable for scenarios with irregular observations with the help of nonlinear Granger causality. We conducted a series of experiments multiple datasets with Random Missing as well as Periodic Missing. Compared with previous methods, CUTS utilizes two alternating stages to discover causal relations and achieved superior performance. We show in the ablation section that these two stages mutually boost each other to achieve an improved performance. Moreover, our CUTS is widely applicable for time- series with different lengths, scales well large sets of variables, and is robust noise. Our code is publicly available at fhttps:: http:::///ttttti /gtptb..tttttgg///g///ggg..... com/ jarrcyx//unn
In this work assume no latent confounder and no instantaneous effect for Granger causality. Our future works includes: (i) Causal discovery in the presence of latent confounder or instantancous effect. (ii) Time-series imputation with causal models.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
For the purpose of reproducibility, we include the source code in the supplementary files, and will published GitHub upon acceptance. Datasets generation process is also included in source code. Moreover, we provide all hyperparameters used for all methods in Appendix Section [A.4.6] The experiments are deployed on a server with Intel Core CPU and NVIDIA RTX3090 GPU.
ACKNOWLEDGMENTS
This work is jointly funded by Ministry of Science and Technology of China (Grant No. 2020AAA0108202), National Natural Science Foundation of China (Grant No. 61931012 and 62088102) Beijing Natural Science Foundation (Grant No. Z200021), and Project of Medical En- gineering Laboratory of Chinese PIAA General Hospital (Grant No. 2022SYS72KY21..
REFERENCES
Alexis Bellot, Kim Branson, and Mihaela van der Schaar. Neural graphical modelling in continuous- time: Consistency guarantees and algorithms. In International Conference Learning Repre- sentations, February 2022.
Zsigmond Benkō, Ádám Zlatniczki, Marcell Stippinger, Dániel Fabó, András Sólyom, Loránd Eröss, András Telcs, and Zoltán Somogyvári. Complete Inference of Causal Relations between Dynamical Systems, February 2020.
Edward De Brouwer, Adam Arany, Jaak Simm, and Yves Moreau. Latent Convergent Cross Map- ping. In International Conference on Learning Representations, March 2021.
Wei Cao, Dong Wang, Jian Li, Hao Zhou, Lei Li, and Yitan Li. BRITS: Bidirectional recurrent imputation for time series. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Haonan Chen, Bo Yuan Chang, Mohamed Naiel1, Georges Younes, Steven Wardell, Stan Kleinikkink, and John S. Zelek. Causal discovery from sparse time-series data using echo state network, January 2022.
Andrea Cini, Ivan Marisca, and Cesare Alippi. Filling the G.ap.s: Multivariate time series im- putation by graph neural networks. In International Conference on Learning Representations, February 2022.
Doris Entner and Patrik O. Hoyer. On causal discovery from time series data using FCL. Probabilistic graphical models, pp. 121-128, 2010.
Alexander Gain and Ilya Shpitser. Structure learning under missing data. In International Confer- ence on Probabilistic Graphical Models, pp. 121-132. PMLR, 2018.
Tomas Geffner, Javier Antoran, Adam Foster, Wenbo Gong, Chao Ma, Emre Kiciman, Amit Sharma, Angus Lamb, Martin Kukla, Nick Pawlowski, Miltiadis Allamanis, and Cheng Zhang. Deep End- to-end Causal Inference, June 2022.
Andreas Gerhardus and Jakob Runge. High-recall causal discovery for autocorrelated time series with latent confounders. In Advances in Neural Information Processing Systems, volume 33, pp. 12615-12625. Curran Associates, Inc., 2020.
Mingming Gong, Kun Zhang, Bernhard Schoelkopf, Dacheng Tao, and Philipp Geiger. Discover- ing temporal causal relations from subsampled data. In Proceedings of the 32nd International Conference on Machine Learning, pp. 1898-1906. PMLR, June 2015.
C. W. J. Granger. Investigating causal relations by econometric models and cross-spectral methods. Econometrica, 37(3):244438, 1969. ISSN 0012-9682. doi: 10.2307/1912791.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural nefworks, 255):359-366, 1989.
10

---

Published as a conference paper at ICLR 2023
Patrik Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. In Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008.
Xiaoshui Huang, Fujin Zhu, Lois Holloway, and Ali Haidar. Causal discovery from incomplete data using an encoder and reinforcement learning, June 2020.
Antti Hyttinen, Sergey Plis, Matti Järvisalo, Frederick Eberhardt, and David Danks. Causal discov- ery from subsampled time series data by constraint optimization. In Proceedings of the Eighth International Conference on Probubilistic Graphical Models, pp. 216-227, PMLR, August 2016.
Akane Iseki, Yusuke Mukuta, Yoshitaka Ushiku, and Tatsuya Harada. Estimating the causal effect from partially observed time series. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01))3919-339) 3926, July 2019. ISSN 2374-3468. doi:
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparamcterization with gumbel-softmax. November 2016. doi: 10.48550/arXiv. www..iii..v11.111111 144.
A. Karimi and M. R. Paul. Extensive chaos in the lorenz-96 model. Chaos: An Interdisciplinary Journal of Nonlinear Science, 20(4):043105, December 2010. ISSN 1054-1500. doi: 106/0../ 3496397.
Saurabh Khanna and Vincent Y. F. Tan. Economy statistical recurrent units for inferring nonlinear granger causality. In International Conference on Learning Representations, March 2020.
Phillip Lippe, Taco Cohen, and Efstratios Gavves. Efficient neural causal discovery without acyclic- ity constraints. In International Conference on Learning Representations, September 2021.
Sindy Löwe, David Madras, Richard Zemel, and Max Welling. Amortized causal discovery: Learn- ing to infer causal graphs from time-series data. In Proceedings of the First Conference on Causal Learning and Reasoning, pp. 509-525, PMLR, June 2022.
Yonghong Luo, Xiangrui Cai, Ying ZHANG, Jun Xu, and Yuan xiaojie. Multivariate Time Series Imputation with Generative Adversarial Networks. Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Daniele Marinazzo, Mario Pellicoro, and Sebastiano Stramaglia. Kernel-granger causality and the analysis of dynamical networks. Physical review F, 77(5):056215, 2008.
Pablo Morales-Alvarez. Wenbo Gong, Angus Lamb, Simon Woodhead, Simon Peyton Jones, Nick Pawlowski, Miltiadis Allamanis, and Cheng Zhang. Simultaneous Missing Value Imputation and Structure Learning with Groups, February 2022.
Meike Nauta, Doina Bucur, and Christin Seifert. Causal discovery with attention-based convo- lutional neural networks. Machine Learning and Knowledge Extraction, 1(1):312-340, March 2019. ISSN 2504-4990. doi: 101.3900/aake001001,,
Junier B. Oliva, Barabáss Póczos, and Jeff Schneider. The statistical recurrent unit In Proceedings of the 34th International Conference on Machine Learning, pp. 2671-2680. PMLR, July 2017.
Roxana Pamfil, Nisara Sriwattanaworachal Shaan Desai, Philip Pilgerstorfer, Konstantinos Geor- gatzis, Paul Beaumont, and Bryon Aragam. DYNOTEARS: Structure learning from time-series data. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pp. 1595-1605. PMLR, June 2020.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of Causal Inference: Founda- lions and Learning Algorithms. The MIT Press, 2017. ISBN 978-0-262-03731-0 978-0-262- 34429-6.
Robert J. Prill, Daniel Marbach, Julio Radz-Rodr, Peter K. Sorger, Leonidas G. Alexopoulos, Xiaowei Xue, Neil D. Clarke, Gregoire Altan-Bonnet, and Gustavo Stolovitzky. Towards a Rig- orous Assessment of Systems Biology Models: The DREAM3 Challenges. PLOS ONE, 5(2):
e9202, 2010. ISSN 1932-6203. doi: 10. 00.1371/juumall.one.0000000
11

---

Published as a conference paper at ICLR 2023
Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer School Machine Learning. pp. 63-71. Springer, 2003.
J. Runge. Causal network reconstruction from time series: From theoretical assumptions to practical estimation. Chaos: An Intendisciplinary Journal of Nonlinear Science, 28(7):075310, July 2018a. ISSN 1054- 1500. doi: 10.1063/1.502500
Jakob Runge. Conditional independence testing based on a nearest- estimator of conditional mutual information. In Proceedings of the Twenty-Firg International Conference on Artificial Intelligence and Statistics, pp. 938-947. PMLR, March 2018b.
Jakob Runge. Necessary and sufficient graphical conditions for optimal adjustment in causal graphical models with hidden variables. In Advances in Neural Information Processing Systems, volume 34, pp. 15762-15773
Curran Associates, Inc., 2021.
Jakob Runge, Peer Nowack, Marlene Kretschmer, Seth Flaxman, and Dino Sejdinovic. Detecting and quantifying causal associations in large nonlinear time series datasets. Science Advances, (1 (1)):cau44996. doi: 10. 1001126/siaadv.aa44999
Shohei Shimizu, Patrik O. Hoyer, Aapo Hyv&4228, rinen, and Antti Kerminen. A Linear Non- Gaussian Acyclic Model for Causal Discovery. Journal of Machine Learning Research, 7(72): 2003-2030, 2006. ISSN 1533-7928.
Stephen M. Smith, Karla L. Miller, Gholamreza Daimi-Khorshhdn; Matthew Webster, Christian F. Beckmann, Thomas E. Nichols, Joseph D. Ramsey, and Mark W. Woolrich. Network modelling methods for FMRI. Neurolmage, (4(2):875-89)) January 2011. ISSN 1053-8119. doi: 10.1016/ j.neuroimage2201 201.:m...........000 20100.8..633.
Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social science computer review, 9(1):62-72, 1991.
Peter Spirtes, Clark N. Glymour, Richard Scheines, and David Heckerman. Causation, Prediction, and Search. MIT press, 2000.
Eric V. Strobl, Shyam Visweswaran, and Peter L. Spirtes. Fast causal inference with non-random missingness by test-wise deletion. International journal of data science and analytics, 6(1):47 ::77 62, 2018.
George Sugihara, Robert May, Hao Ye, Chih-hao Hsieh, Ethan Deyle, Michael Fogarty, and Stephan Munch. Detecting Causality in Complex Ecosystems. Science, 33861006) October 2012. doi: 10. 10.11166/cee 1227079.
Gábor J. Székely, Maria L. Rizzo, and Nail K. Bakirov. Measuring and testing dependence by correlation of distances. The Annals of Statistics, 35(6):2769-2777)) December 2007. ISSN 0090- 5364, 2168-8966. doi: 14000905560000000005500
Alex Tank, Ian Covert, Nicholas Foti, Ali Shojaie, and Emily B. Fox. Neural granger causality. IEEE Transactions Patter Analysis and Machine Intelligence, 44(8):4267-4279, 2022. ISSN 1939-3539. doi: 10.110///AAMM22011.00666
Ruibo Tu, Cheng Zhang, Paul Ackermann, Karthika Mohan, Hedvig Kjellström, and Kun Zhang. Causal discovery in the presence of missing data. In Proceedings of the Twenty-Second Interna- tional Conference on Artificial Intelligence and Statistics, pp. 1762-1770. PMLR, April 2019.
Matthew J. Vowels, Necati Cihan Camgoz, and Richard Bowden. D'ya like dags? A survey on structure learning and causal discovery, March 2021.
Yuhao Wang, Vlado Menkovski, Hao Wang, Xin Du, and Mykola Pechenizkiy. Causal discovery from incomplete data: A deep learning approach, January 2020.
Ian R. White, Patrick Royston, and Angela M. Wood. Multiple imputation using chained equations: Issues and guidance for practice. Statistics in medicine, 30(4)3377-399, 2011.
12

---

Published as a conference paper at ICLR 2023
Ronald J. Williams. Simple statistical Pradient-following algorithms for rennereeen learning. Machine learning, ((3):229-255 1992.
Alexander P. Wu, Rohit Singh, and Bonnie Berger. Granger causal inference on dags identifies genomic loci regulating transcription. In International Conference on Learning Representations, March 2022.
Hao Ye, Ethan R. Deyle, Luis J. Gilarranz, and George Sugihara. Distinguishing time-delayed causal interactions using convergent cross mapping. Scientific Reports, 5(1):14750, October 2015. ISSN 2045-2322. doi: 10.1038/srep14750.
13

---

Published as a conference paper at ICLR 2023
A
APPENDIX
CONTENTS
A.I Convergence Conditions for Granger Causality
14
A.I.I
Proof of Theorem
14
1.1.2
The Effects of Data Imputation
15
A.1.3
Convergence of Sigmoidal Gradients
16
A.2
An Example for Trregular Time-series Causal Discovery
16
A.3
Implementation Details
17
A.3.1
Gumbel Softmax for Causal Graph Fitting
17
A.3,2
Initial Data Filling
17
A.3.3
Hyperparameters Settings
17
A.4
Additional Experiments
19
A.4.1
DREAM-3 Experiments
19
A.4.2
Ablation Study on VAR and NetSim datasets
19
A.4.3
Ablation Study for Epoch Numbers
19
A.4.4
Performance Temporal Causal Graph
19
A.4.5
Causal Discovery with Structured lime-series Data
19
A.4.6
Robustness Hyperparameters Settings
19
A.7.7
Lorenz-96 Datasets with F=40
19
A.4.8
Robustness to Noise
20
A.5
Pseudocode for CUTS
20
A.6
MSE Curve for Data Imputation
21
A.1
CONVERGENCE CONDITIONS FOR GRANGER CAUSALITY
A. 1.1.1 PROOF OF THEOREM 1
We proved that in Theorem our CUTS can discover the correct Granger causality with the follow- ing assumptions:
1. DSGNN fo. in Latent data prediction stage model generative function with error smaller than arbitrarily small value ENN.i
2. Ioo, ji,j 1, ..., N₂ 1If, (X @ ST,ij=1) So, (X' o Sr,j=)) do. where Sr,jjt is set S with element 87,1) I.
In Causal graph fitting stage the loss function
(C o.)
Cgraph (8,2,0,0)
HOLLOO + +1)o00))1
(11)
G0, - for O S))² +llo
14

---

Published as a conference paper at ICLR 2023
where Sr,if Ber(o((fr,)))), c (or.0.100.2.3) We use the REINFORCE
(Williams 1992 trick
and mr, gradient is calculated as
0
Es, [Cgraph]
(300,, S0y (X S))2
Ps. Xo (0r.i)))))
08
00..1
= = 0 (100,)))0000 ( Jos (X @ Sr.jj=1)) o(0+.15)
0 (07.3)))
(1 - o ),, (Tt. - So. (X 3 S))j=))) a(0ris) - 0 (07,5))
=o' (((n Jo, (X' S),
c.ors - Say (X 2 Sr.jjoo) + X).
(12)
Where Sr,5== denotes S=
= { Fmoe with sr,ij set to I. and (XO Sn(j=1) = fo, (01-
r=1
81:7,1i lé: ...y Tt-r-t-1.N NNN 81,7, According to Definition [ time-series does not Granger cause j if VT E {1,... Tmar ) Dt-r.i is invariant of the prediction of an. Then we have V7 E (1,-.. Tmaz], (-.)))) Sas (,..,,,..... O,-.., i.e., Ja, (X.S. Sos (r,
Applying additive noise model (ANM, Equation I we can derive that
i E., ggroph a' (Goss)) = = (0 0.
(13)
00
This is a sigmoidal gradient, whose convergence is analyzed in Section A. Likewise, we have Br E [1..... Tmazi, fe, (X Sr,1==1) + fa, (X @ ST,j==0) if time-seris Granger cause j. and B7 satisfying
0 E., Eor.. [Caraph] o' d' ((E - (X @ Sr,
00
(14)
- (x - for (X o STuj= + A).
Assuming that fa, (-) accurately models causal relations f((-) (i.e., DSGNN fo, in Latent data pre- diction stage model generative function fi with an error smaller than arbitrarily small value exN,), applying Equation I
we have
E. B...y (graph) = o' =0'(0r,))) (ct - (x1. - fa, (X @ ST.rf=))) + A)
00
(15)
o''(0.,)) (c (et. + Af )2) A)
o' =0'(0,,))) (-2e1,) Aft.j ; 2 Ar5())) 2),
where noise term Ct ((,, Afi Sa, (X @ ST,0=1) Sa, (X @ Sy,jj=o) This gradient expected to be negative when Vi,j = L, N, E(c 2 pλo > X, where p the missing probability, i.e., E[c;] = p (here we only consider the random missing scenario). Since we can certainly find satisfying the above inequality, 0T.i5 will go towards +00 with a properly chosen and mr.ij + 1. Moreover, we show in Appendix Section A.4. CUTS is robust to a wide range of X values. When applies to real data we use Gumbel Sottmax estimator for improved performance Jang et al. 2016).
A.1.2 THE EFFECTS OF DATA IMPUTATION
To show why data imputation boosts causal discovery, we suppose -t-r' a parent node of æt, is unobserved and imperfectly imputed with as 2,-r', + F.-r' If time-series i Granger cause j. then f (..., r..... # f(... It It-r'.j....) Let 8y'.8j = ((.',. f(.., f..rd and
0 E..., [Cropph] = (0 00,43
87,,,)) - (ee,s + 8 + +
(16)
= =''(0r,s)(oor. + 8, Afss - A2.) +
15

---

Published as a conference paper at ICLR 2023
The expectation
Bec,
30..5 Esr.s (Caraph)) o' (((0r)))),,,,
fig) + +
As a result, if we cannot find lower bound for d, gradient for 7 is not guaranteed to be positive or negative and the true Granger causal relation cannot be recovered. On the other hand,
Tt-r'j is appropriately imputed with [8rrasl S 6 < A we can find À pd põ to insure negative gradient and 4,,5 will go towards +00.
A.1.3 CONVERGENCE SIGMOIDAL GRADIENTS
We now analyze the descent algorithm for sigmoidal gradients with learning rate a (for simplicity we denote 03 as 0):
0₂ = f + (0x-1()
This is a monotonic increasing sequence. We show that this sequence converges to +00, Va: 0. If this is not the case, 3M > O,s.t. vi > O, we have O; I M, since this sequence is monotonic increasing, we have
e t
e 0x
e --M
0k-1 = 0g + ad
(1 (1+e 0x)2 2 0g + ad
(1 (1+e- 2 0k + ad
(1 (1+e-A))
then 3k, s.t. 0% > M. this contradicts with "Vi > 0,0, < M", then we have 0g + too and for any finite number M, 0g converge to M in finite steps. And likewise sequence 0/- 0 - (e)o'(0x-1) converges to < -M in finite steps. This enables us to choose a threshold to classify causal and non-causal edges.
A.2 AN EXAMPLE FOR IRREGULAR TIME-SERIES CAUSAL DISCOVERY
In this section we provide simple example for irregular causal discovery and show that our algo- rithm capable recovering causal graphs from irregular time-series. Suppose we have a dataset with 3 time-series 1 22, 33. which are generated with
1 c1 ž1,2 f2(21-1.2 + ct,, F₁,3 15(21-1,1, + e1,3.
(17)
where 61, C22 Eg are the noise terms and follow (10, o). We assume only 22 is randomly sampled with missing probability P2
0,1 1, 02,2 Ber(1 [1 p2), 0t,3 1,
(18)
where Ber(-) denotes the Bernouli distribution. Then the groundtruth causal relations can be illus- trated in Figure 3 (left). We use DSGNN føz to fit f2 supervised on observed data points of æ2, i.e. mins, L2(2 for (x)=,,1),, Vt, s.t. or = 1. Given fe.. the unobserved values of 22 can be imputed with 6122 = for (IL,1) and we fa(-) with for (.) in Latent data prediction stage:
arg min C2(x1,3; Sos (I1-1,1, #1-1,2)
d1
(19)
min C2(11,,, for 111 11, (oc-
and CPGs M, is optimized in Causal graph fitting stage with
mig Mi
+ + 21-1313188)
(20)
where $1.ij is sampled with Gumbel Softmax technique denoted with Equation 21 Since -;-1.3 is invariant to the prediction 2r,3 given æ,,1 and æt,2, 51.33 can be penalized to zero with a proper A. Here we conduct an experiment to verify this example. We set L 10000, random missing probability P2 = 0.2. The illustration of the discovered causal relations is Figure 3 Results show that CUTS without data imputation tends to ignore causal relations from 22 (with missing values) to other time-series. This causal relation V; - D3 are instead "replaced" by Ø3 + D3. which leads to incorrect causal discovery results.
16

---

Published as a conference paper at ICLR 2023
2-2
C-1
1-2
(-1
t-2
(-
X1
X1
3/2
Faise Positive
Negative
True
Discovery with (No Data Imputation)
Biscovery
Figure 3: An three-time-series example demonstrating the advantages of introducing data imputa- tion, with the groundtruth causal graph the left column. The recovered causal graph without data imputation (middle column) shows some false positive and false negative edges, while CUTS (right column) exhibits perfect results.
A.3 IMPLEMENTATION DETAILS
A.3.1 GUMBEL SOFTMAX FOR CAUSAL GRAPH FITTING
In our proposed CUTS, causal relations are modeled with Causal Probability Graph (CPGs), which describe the possibility of Granger causal relations. However, the distributions of CPGs are discrete and cannot be updated directly with neural networks in Causal gruph fitling stage. To achieve a continuous approximation of the discrete distribution, we leverage Gumbel Softmax technique Jang et al. 2016), which can be denoted as
exp((log(v)) + g)/T) Sr, exp((log(Mr.ss) + g)/T) exp((log(1 my + g)/T)'
(21)
where g = - loolllloolllo (og(u)), u Uniform(O, 1). The parameter is set according to the "Gumbel tau" item in Table During training we first set a relatively large value of and decrease slowly.
A.3.2 INITIAL DATA FILLING
The missing data points filled with Zero-Order Holder (ZOH) before the iterative learning pro- cess to provide an initial guess ((0), An intuitive solution for initial filling is Linear Interpolation, but would hamper successive causal discovery. For example, if æt-2.; and Tt are observed and 2t-1.i is missing, 2r-1, à is filled 2 ( + 2t,;), then æt,i be directly predicted with 20("), v;-2,4 and other time-series cannot help the prediction of æt,; even if there exists Granger causal relationships. To show the limitation of filling with linear interpolation, we con- ducted ablation study VAR datasets with Random Missing (p 0.6). In this experiment, initial data filling with ZOH achieves AUROC of (0.9766 + 0.0074) while that with Linear interpolation achieves an inferior accuracy (0.9636 0.0145). This validates that Zero-order Holder better option than linear interpolation as an initial filling implementation.
A.3.3 HYPERPARAMETERS SETTINGS
To fit data generation function we use DSGNN fø, for each time-series: i. Each DSGNN contains a Multilayer Perceptron (MLP). The layer numbers and hidden layer feature numbers are shown in Table 4 For activation function we use LeakyReLU (with negative slope 0.05). During training use Adam optimizer and different learning rate for Latent data prediction stage and Causal graph fitting stage (shown as "Stage Lr" and "Stage Lr" in Table with learning rate scheduler. The input step for fs, also denotes the chosen
time lag for causal discovery. For VAR and Lorenz- 96 datasets we already know the max time lag of the underlying dynamics (Tmaz 3), while for NetSim datasets this parameter is chosen empirically.
17

---

Published as a conference paper at ICLR 2023
Table Hyperparameters settings of CUTS in the aforementioned experiments. "0 d2 parameters exponentially increase/decrease from to d2.
means
Methods
Hyperparam.
VAR
Lorenz
NetSim
DREAM-3
R:
5
50
200
20
15
150
30
300
200
50
0.1
Input
3
3
Batch size
128
128
CUTS
Hidden features
128
128
128
128
Network layers
3
Weight decay Stage Lr
0.001
0
0.001
10
10
10 - 10
10 + 10
10 -> 10
Stage
10
2
10
10 2 10
10
10
10 10
Gumbel y
1-1.1 0.1
1 0.1
1 1 0.1
1 - 0.1
Table 5: Hyperparameters settings of the baseline causal discovery and data imputation algorithms.
Methods
Hyperparameters
VAR
Lorenz
NetSim
DREAM-3
Timn
5
PCMCI
PCa
0.05
0.05
0.05
0.05
CI Test
ParCorr
GPDC
ParCor
ParCorr
0.1
0.1
0.1
0.7
Leaming rate
0.01
0.01
0.001
0.001
eSRU
Batch size
250
250
100
100
Epochs
2000
2000
2000
2000
Leaming rate
0.05
0.05
0.05
0.05
NGC
Aridac
0.01
0.01
0.01
0.01
Swoeping Range
0.02 - 0.2
0.02 - 0.2
0.04 - 0.4
0.02 - 0.01
Epochs
200
200
200
200
GRIN
Batch size
128
128
128
128
Window
3
3
3
Epochs
50
50
50
50
L.CM
Batch
10
Hidden size
20
20
20
20
Steps
2000
2000
2000
2000
Horizon
5
5
5
5
GL.reg
0.05
0.05
0.05
0.05
Chunk num
100
100
100
46
For baseline algorithm choose parameters mainly according the original paper official repository (PCMCf) eSRU NGC GRIN For fair comparison, we applied parameter searching determine the key hyperparameters of the baseline algorithms with best performance. Tuned parameters are listed in Table
http:///ghhbbbbooonaakoonnggggge hhttss//ggtuub..o//aaaaaaaaa for GCI http::////ttttacooommmaaaaa-aaae Group/grin
18

---

Published as a conference paper at ICLR 2023
A.4 ADDITIONAL EXPERIMENTS
A.4.1 DREAM-3 EXPERIMENTS
DREAM-3 (Prill et al. 2010 is gene expression and regulation dataset mentioned in many causal discovery works as quantitative benchmarks (Khanna & Tan 2020 Tank et al. 2022). This dataset contains 5 models, each representing measurements of 100 gene expression levels. Each measured
trajectory has a time length of T = 21. This is too low to perform random missing or periodic missing experiments, so with DREAM-3 we only compare our approach with baselines in regular time-series scenarios. The results are shown in Table [1
A.4.2 ABLATION STUDY ON VAR AND NETSIM DATASETS
Besides the ablation studies on Lorenz-96 datasets shown in Table 3 we additionally show those on VAR and NetSim in Tables [ and 7 In Table G one can see that "CUTS (Full)" beats other configurations in most scenarios, and the advantage is more obvious with higher missing percentage (p 0.6 for Random Missing and Tmax 4 for Periodic Missing), On the NetSim datasets with too small data size L = 200, "CUTS (Full)" beats other configurations at a small missing probability
(p 0.1).
A.4.3 ABLATION STUDY FOR EPOCH NUMBERS
In our proposed CUTS, each step can be recognized as a refinement causal discovery, with builds upon previous imputation results. Since the data imputation and causal discovery mutually boost each other, the performance may be affected by different settings of learning steps. In Table we conduct experiments to show the impact of different epoch numbers VAR, Lorenz-96, and Netsim datasets. We set ni, n22 723 proportional to original settings.
A.4.4 PERFORMANCE ON TEMPORAL CAUSAL GRAPH
In the previous experiments, caleulate causal summary graphs with ر.ة max ( (m+,ú) Timur ie., maximal causal effects along time axis. Our CUTS also supports discovery of 3-dimensional temporal graph {m We conduct experiments to investigate our performance for temporal causal graph discovery. The results are shown in Table T0
A.4.5 CAUSAL DISCOVERY WITH STRUCTURED TIME-SERIES DATA
We show in this section that CUTS is able recover causal relations not only with irregular time- series but also with regular time-series, which is widely used for performance comparison in previ- ous works. We again tested our algorithm VAR, Lorenz-96, and NetSim datasets, and the results are shown in Table II It is observed that our algorithm shows superior performance to baseline methods.
A.4.6 ROBUSTNESS TO HYPERPARAMETERS SETTINGS
We show that CUTS is robust to changes of hyperparameters settings, with experiment results listed in Table 12 For existing Granger-causality based methods such as NGC (Tank et al.) [022) and eSRU (Khanna & Tan 2020), parameters À and the maximum time lag Tmea are often required to be tuned precisely. Empirically, À is chosen to balance between the sparsity of the inferred causal relationship and data prediction accuracy, and Tmar is chosen according to the estimated maximum time lag. In this work we find our CUTS gives similar causal discovery results across a wide range of A (0.01 0.3) and (3 9).
A.4.7 LORENZ-96 DATASETS WITH F=40
We further conducted experiments with external forcing constant F = 40 on Lorenz-96 datasets instead of F 10 in Section 5.2 We show that our approach produces promising results with p = 0.3 for random missing and man = for periodic missing, as shown in Table with AUROC score higher than 0.9.
19

---

Published as a conference paper at ICLR 2023
Table 6: Quantitation results of ablation studies VAR dataset. "CUTS (Full)" denotes the default settings in this paper. The highest scores (or multiple ones with ignorable gaps) of each column are bolded for clearer illustration.
VAR with Random Missing
VAR with Periodic Missing
Methods
p 0.3
p 0.6
Teaz
Tea
CUTS (Full)
0.9971 0.0026
0.9766 = 0.0074
0.9992 0.0016
0.9958 + 0.0069
ZOH for Imputation
0.9908 0.0065
0.9109 0.0328
0.9974 0.0020
0.9782 1 0.0197
for Imputation
0.9964 0.0026
0.9240 = 0.0327
0.9980
0.0018
0.9442 + 0.0429
GRIN Imputation
0.9963 0.0047
0.9014 + 0.0273
0.9992 0.0012
0.9818 + 0.0174
No Imputation
0.9945 + 0.0038
0.9624 + 0.0132
0.9968
0.0032
0.9797 + 0.0204
Remove CPG Imput.
0.9975 0.0020
0.9624 + 0.0132
0.9991 0.0016
0.9906 + 0.0123
No Finetuning Stage
0.9960 + 0.0073
0.9736 = 0.0074
0.9974 0.0032
0.9835 + 0.0160
Table 7: Quantitation results of ablation studies on NetSim dataset. "CUTS (Full)" denotes the default settings in this paper.
NetSim with Random Missing
Methods
p == 0.1
p = 0.2
CUTS (Full)
0.7948 = 0.0381
0.7699 t 0.0550
ZOH for Imputation
0.7937 = 0.0349
0.7878 + 0.0361
GP for Imputation
0.7845 = 0.0362
0.7890 + 0.0443
GRIN for Imputation
0.7745 1 0.0452
0.7553 1 0.0513
No Imputation
0.7650 + 0.0272
0.7164 1 0.0343
Remove CPG for Imput.
0.7912 + 0.0389
0.7878 + 0.0361
No Finetuning Stage
0.7650 + 0.0272
0.7164 1 0.0343
A.4.8 ROBUSTNESS TO NOISE
We experimentally show that CUTS is robust noise, shown in Table 9 linear Lorenz-96 datasets for this experiment (L = 1000, f = 10) and set additive Gaussian white noise with standard deviation 0.1, 0.3, respectively.
We choose the
A.5 PSEUDOCODE FOR CUTS
We provide the pseudocode of two boosting modules of the proposed CUTS in Algorithm T and 2 respectively, and the whole iterative framework in 3 Detailed implementation is provided in supplementary materials and will uploaded to GitHub soon.
Algorithm Latent data prediction stage
Input: Time series dataset ( (II.1,1 FIaNN observation mask (o1:1.1; o1:A,:; Adam optimizer Adam(-)
Output: DSGNNs parameters (01,...,,,
for = to N do
Ht, < So. (Zr-r:--1 81:7,j), 8raf Ber(1 my,is)
22, = ΣN, (cll).....m........
Φ. Adam( Cprea)
end for
20

---

Published as a conference paper at ICLR 2023
Table 8: Quantitative comparison on learning step numbers, in terms of AUROC. We set 11 12, f3 proportional to original settings, c.g.. original settings ni = 50, n2 = 250, n3 = 200 then "50% Steps" means n1 25, n2 125, f2 100.
VAR with Random Missing
VAR with Periodic Missing
Methods
p= 0.3
p 0.6
Tmax 2
Tma 4
25% Steps
0.9912 = 0.0041
0.9492 0.0119
0.9951 = 0.0047
0.9818 = 0.0158
50% Steps
0.9949 1 0.0034
0.9640 0.0087
0.9978 1 0.0028
0.9894 1 0.0125
75% Steps
0.9965 + 0.0027
0.9729 0.0075
0.9985 + 0.0023
0.9921 0.0105
100% Steps
0.9971 + 0.0026
0.9766 0.0074
0.9992 + 0.0016
0.9958 + 0.0069
Lorenz-96 with Random Missing
Lorenz-96 with Periodic Missing
Methods
p 0.3
p p= 0.6
Tmao= =2
Tmaz
25% Steps
0.9811 + 0.0069
0.9052 0.0208
0.9924 + 0.0050
0.9655 + 0.0216
50% Steps
0.9952 = 0.0022
0.9456 0.0153
0.9987 + 0.0015
0.9855 + 0.0112
75% Steps
0.9987 = 0.0016
0.9613 0.0128
0.9998 + 0.0005
0.9930 + 0.0062
100% Steps
0.9996 = 0.0005
0.9705 + 0.0118
1.0000 + 0.0000
0.9959 + 0.0042
NetSim with Random Missing
Methods
p 0.1
p 0.2
25% Steps
0.7737 +: 0.0346
0.7403 + 0.0355
50% Steps
0.7963 + 0.0399
0.7699 + 0.0443
75% Steps
0.7961 + 0.0390
0.7714 + 0.0503
100% Steps
0.7948 = 0.0381
0.7699 + 0.0550
Table 9: Accuracy of CUTS on Lorenz-96 datasets with different noise levels. The accuracy is calculated in terms of AUROC.
Lorenz-96 with Random Missing
Methods
Noisc
p = 0.3
p = 0.6
0.1
1.0000 0.0000
0.9843 + 0.0073
CUTS
0.3
1.0000 0.0001
0.9825 + 0.0080
0.9999 + 0.0002
0.9722 + 0.0108
A.6 MSE CURVE FOR DATA IMPUTATION
The Mean Square Error (MSE) of the imputed time-series, imputed time-series without the help of causal graph, and the groundtruth time-series during the whole training process are shown in Figure We can see that under all configurations our approach successfully imputes missing values with significantly lower MSE compared to initially filled values. Furthermore, in most settings imputing time-series without the help of causal graph are prone overfit. The imputed time-series then boost the subsequent causal discovery module, and discovered causal graph help prevent overfit in imputation.
21

---

Published as a conference paper at ICLR 2023
Quantitative comparison for 3-dimensional temporal causal graph discovery VAR datasets, in terms of AUROC.
Table 10:
VAR with Random Missing == 0.3
Methods
p
p= 0.6
CUTS
0.9979 + 0.0018 0.9848 + 0.0053 0.9170 + 0.0127
VAR with Periodic Missing
Methods
Tiaaz
Taaa= = =2
Tmae 1
CUTS
0.9973 + 0.0024
0.9938 + 0.0036 0.9612 + 0.0286
Table 11: Accuracy of CUTS and five other baseline causal discovery algorithms on VAR, Lorenz- 96, NetSim, and DREAM-3 datasets without missing values. The accuracy is calculated in terms of AUROC.
Methods
Lorenz-96
VAR
NetSim
DREAM-3
PCMCT
0.7515 0.0381
0.9999
0.0002
0.7692
0.0414
0.5517 + 0.0261
NGC
0.9967 0.0058
0.9988 0.0015
0.7616 0.0504
0.5579 +:2 0.0313
eSRU
0.9996 0.0005
0.9949 0.0040
0.6817 = 0.0263
0.5587 + 0.0335
LCCM
0.9967 0.0058
0.9988
0.0015
0.7616 = 0.0504
0.5046 = 0.0318
NGM
0.9996 0.0005
0.9949
0.0040
0.6817 = 0.0263
0.5477 = 0.0252
CUTS
1.0000 0.0000
0.9999 0.0002
0.8277 = 0.0435
0.5915 + 0.0344
Table 12: Accuracy of causal discovery results of CUTS under different hyperparameters À and Tmaz settings.
A
AUROC
Tmaz
AUROC
0.01
0.9962 = 0.0029
3
0.9971 + 0.0026
CUTS
0.03
0.9964 + 0.0029
6
0.9972 + 0.0032
0.1
0.9971 = 0.0026
0.9972 + 0.0042
0.3
0.9962 + 0.0027
Comparison of CUTS with (i) PCMCL, eSRU, NGC combined with imputation method ZOH, GP, GRIN and (ii) LCCM, NGM which does not need data imputation. Results are averaged over randomly generated datasets.
Table 13:
Random Missing
Periodic Missing
Method
Imputation
p 0.3
Touz
ZOH
0.7995 0.0361
0.8164 = 0.0313
PCMCI
GP
0.8124 1 0.0221
0.7871 1 0.0323
GRIN
0.8193 + 0.0329
0.7816 + 0.0361
ZOH
0.8067 1: 0.0267
0.8558 +: 0.0248
NGC
GP
0.8350 + 0.0314
0.8250 + 0.0257
GRIN
0.6293 1 0.0523
0,7114 = 0.0129
ZOH
0.8883 0.0131
0.9463 + 0.0208
eSRU
GP
0.9499 0.0061
0.8893 1 0.0160
GRIN
0.9417 + 0.0199
0.9494 + 0.0129
LCCM
0.6437 + 0.0267
0,6215 = 0.0343
NGM
0.6734 1 0.0403
0.7522 1 0.0520
CUTS (Proposed)
0.9737 + 0.0105
0.9289 + 0.0145
22

---

Published as a conference paper at ICLR 2023
Algorithm 2 Causal graph fitting stage
Input: Time series dataset (I FI.L,N }; observation mask (OI:L,1.... 01.L,N J: Adam op-
timizer Adam(.): ); Gumbel softmax function Gumbel(.) described with Equation 21
Output: Causal probability mr,jis Vj 1,,,,
for 1 N do
t4,i t fa. (I O $1: ) 87,1J = Gumbel(1 my,i5)
Sgraph (X, (x,,) Lyred (, N, O) + (l)o(0)]11
0 - Adam(0. Cgraph)
end for
Algorithm 3 Causal Discovery from Irregular Time-series (CUTS)
Input: Time series dataset (æI:L,1; FI-L,N] with time-series length L; observation mask
"o...,,,.,,,I..... Zero-order holder (ZOH) imputation algorithm ZOH(-); Adam optimizer A-am(-)
Output: Discovered causal graph
Initialize (0) = ZOH (x1.L.), Causal Probability Graphs M, = 0, Vr = 1, Tma
# Warming up
for n iterations do
Update {ØI...., ΦN with Algorithm 1
Update M, with Algorithm end for
Causal discovery with data imputation for n2 iterations do
Update { 3N with Algorithm Update M, with Algorithm for 1 to N do
(1
a) (m)
azt
(m)
01,i = 0
(m+1) Data update: Lti
(0)
01, =
end for end for Finetuning
Reset 0r,i 1, 14 = 1,.., T,i 1,..,N for ria iterations do
Update fø..... ΦN with Algorithm
Update M, with Algorithm end for
for i = 1 to N do
for j = to do
ājjj = max (m1.ij, M m5)
end for end for return Discovered causal adjacency matrix where each elements is āz.j-
23

---

Published as a conference paper at ICLR 2023
VAR with Random Missing
VAR with Periodic Missing
0.45
0.40
0.7
0.25
0.20
0.3
Stops
Steps
Lorenz-96 with Random Missing
Lorenz-96 with Periodic Missing
0.7
End mepacce
Lourd Jaher
0.30
Jdlin
Imparrie Graps
0.25
0.30
0.05
0.1
0.00
Stegs
NetSim with Random Missing
0.50
Fentary
085
0.20
0.10
Stens
Figure 4: Average MSE curve of imputed data VAR datasets with Random Missing / Periodic Missing (top), Lorenz-96 datasets under Random Missing Periodic Missing (middle), and NetSim datasets with Random Missing (bottom).
24


Reviews:
[{"review_id": "twfFS8-CP0", "reviewer": "Reviewer_ADkU", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors present a Granger causal discovery framework for unstructured time series data which leverages an alternating formulation comprising of a) data imputation and b) subsequent causal discovery. The basic premise is centered around providing empirical results on how data imputation aids the causal discovery and vice versa. Ablation studies based results along with comparisons using different combinations of Causal Discovery and data imputation techniques (Random and periodic missing patterns only considered) indicate the superior performance of the proposed CUTS method.", "summary_of_the_review": "I believe the paper presents a good empirical study of a framework which nicely combines two techniques a) data imputation and b) causal discovery in an alternating style framework to deal with the problem of causal discovery from unstructured time series data. While the approach is interesting and the paper is reasonably easy to follow, the results for some cases do not indicate significant improvements. However, the more major concern I have is with the technical rigor is missing to support some claims on data imputation supporting causal discovery. ", "strength_and_weaknesses": "**Strengths**\n\n- Problem of causal discovery from unstructured time series data is an important problem and the paper presents a framework which is intuitive and relatively easy to follow.\n\n- The authors have put in significant effort to benchmark their technique with various combinations of causal discovery and missing pattern imputation techniques.\n\n**Weakness**\n- The paper as a whole does not do a good job in providing a technically rigorous narrative on why or how Data imputation boost Causal Discovery.  The vice versa argument seems reasonable enough, but given that the imputation is just confined to addressing two patterns in time series data (random and periodic patterns), I wonder if the causal discovery would benefit with the limited insight provided by the data imputation framework.\n- To support these claims, I do notice that in general the AUROC improvements for VAR with Random missing are marginal compared to other competing methods in Table 1. \n\n**Minor writing issues**\n\n- ParCorr first occurrence is not defined on Page 6.\n- ZOH first occurrence is not defined on Page 5.\n- Table 2 title should be Quantitative and Table 3 title should also be Quantitative", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Ud29FWHTR4d", "reviewer": "Reviewer_SHw1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper presents an auto-regressive style model for joint causal graph learning and missing data imputation for unstructured temporal data. The model is trained in a two-step procedure alternating between training the imputation model and the graph learning (EM-style algorithm). The model parametrises the graph using an independent Bernoulli distribution and the Gumbel softmax for enabling gradient based learning. The paper compares the method to relevant temporal discovery methods and achieves competitive performance.", "summary_of_the_review": "The paper tackles and important and interesting problem of discovering causal graphs from temporal data with missing values. However, the evaluation only compares to baselines without proper data imputation capabilities and does not offer a comparison on fully observed data. Furthermore, important literature is missing, and it would be good to discuss some of the model assumptions around Granger causality vs other causal discovery assumptions. Lastly, the model choices about noise distributions and loss functions should be better justified.", "strength_and_weaknesses": "Strengths:\n- The paper tackles the important problem of modelling timeseries data with missing entries.\n- The experimental results show competitive or superior results to relevant baselines.\n- The proposed method seems to incorporate a lot of small tweaks that improve the model performance - there seems to be value in analysing the training behaviour a bit further.\n\nWeaknesses:\n- Some important related works are missing: [1] tackles temporal causal discovery with Neural ODEs that would be able to handle inconistent sampling intervals, [2] performs joint structure learning and data imputation, [3] performs temporal causal discovery using the NOTEARS framework for continuous DAG learning. Methods based on the same framework have been applied to static data for joint causal discovery and data imputation [4]. All these weaken the novelty of this paper.\n- The paper mentions that it is based on Granger causality. However, the current formulation also allows for an interpretation as an additive noise model: ie $x_i = f(pa_i) + e_i$. Could you please comment on this? This interpretation would also allow for the identification of the temporal causal graph $A_{0, \\tau}$ rather than just the summary graph $\\hat{A} = max_t A_{t}$.\n  - Please add some comments about the difference between Granger causality and ANMs or PCMCI that also identify the temporal causal graph.\n- It is unclear how $\\tau_{max}$ is chosen. Is this assumed to be known? What if this isn't known?\n- All experiments use missing data. It would be great to see a baseline comparing to datasets with full observability.\n\nMisc:\n- What's the intuition of using the moving average as a training signal for the imputation network?\n- For the graph discovery stage - do you calculate an expectation over multiple graph samples or is this amortised over different batches? Or do you use the same graph sample for optimising this loss?\n- Please explain ZOH earlier in the text.\n- Eq 3: what is $e$? What's the assumption about it? This might make or break the use of the L2 loss.\n- Please pay attention to the use of `\\citep` and `\\citet`.\n- Eq 5: You use inconsistent $\\tau=0...$ and $\\tau=1,...$.\n- p5 just above eq 11: I believe $n_2$ should be $n_3$.\n- p2: \" to conduct causal inference and ..\" - should this be \"causal discovery\"? Causal inference tackles the question of inferring causal estimates (e.g. ATEs).\n\n[1] Bellot, Alexis, Kim Branson, and Mihaela van der Schaar. \"Neural graphical modelling in continuous-time: consistency guarantees and algorithms.\" International Conference on Learning Representations. 2021.\n[2] Morales-Alvarez, Pablo, et al. \"VICause: Simultaneous Missing Value Imputation and Causal Discovery with Groups.\" arXiv preprint arXiv:2110.08223 (2021).\n[3] Pamfil, Roxana, et al. \"Dynotears: Structure learning from time-series data.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2020.\n[4] Geffner, Tomas, et al. \"Deep End-to-end Causal Inference.\" arXiv preprint arXiv:2202.02195 (2022).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LIIV18fqD3", "reviewer": "Reviewer_jtS8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a deep learning-based Granger causality model for discovering the Granger causal graph and imputing missing values at the same time. The author claim this model can handle missing completely at random and periodic missing scenarios.\nThe main methodology is to iteratively apply the data imputation and graph learning, where the graph learning stage is further split into three sub-stages: (1) without imputed value; (2) with imputed value but not as model supervisory; (3) with imputed value. \nThe graph is sampled from an independent Bernoulli distribution with a Gumbel-softmax gradient estimator.\n\nEmpirically, the author conducts 2 synthetic experiments with the Netsim fMRI dataset, where the model achieves better results. ", "summary_of_the_review": "My main concern regarding this paper is the technical soundness and claims made by the author. In general, I think this paper can be improved if the author can clarify the concerns and elaborate more on its novelty.\n\n", "strength_and_weaknesses": "## Strength\nGranger causality with deep learning has been a popular research topic in recent years, and this model is an extension of some well-known previous work. The idea behind this model is intuitive and easy to follow. Despite some typos in the math, the model formulation is easy to understand. Although I think the author should conduct more real-world experiments (e.g. DREAM3/4 dataset), the author has conducted sufficient ablation studies for synthetic experiments to demonstrate some of the properties of the model. \n\n## Weakness\nAfter reading the paper, I have some concerns regarding the proposed method: (1) theoretical results and soundness; (2) clarity regarding the periodic missing. \n\nSpecifically, first, I am not fully sure the proposed objective in eq.10 is correct. Since the adjacency matrix is sampled from an independent Bernoulli distribution, which is modeled by the parameter $\\theta$. This means this is very similar to a variational framework, where the Bernoulli distribution is a mean-field approximation, see the formulation [1] and [2] for details. This means the with Gaussian noise variable, the $L_{pred}$ in eq.10 is similar to the likelihood term in ELBO and $\\Vert \\sigma(\\theta) \\Vert_1$ is similar to the prior, however, the entropy of the Bernoulli distribution is missed in eq.10. This means the proposed objective is not a proper likelihood, so how it can guarantee it recovers the ground truth graph? (I will explain my concern of theorem 1 in the following). How to explain the differences?\n\nThe author provides theorem 1 to justify the convergence of the CUTs. However, I am not fully sure this will hold. For equation 15, the inputs to $f_{\\phi_i}$ should be the parents of node $x_{t,i}$, why it is $x_{t-\\tau:t-1, i}$? Is this a typo?\nIn eq.17, when $S$ and $f_\\phi$ are not the ground truth, how this two cases with $S_{ij=1}$ equals $S_{ij=0}$? Also, the negative gradient has a derivative of the sigmoid function, meaning that the magnitude of the gradient will go toward 0, meaning that more rigorous analysis is needed to claim convergence.\n\nFor equations 18 and 19, I am not sure the assumption \"$f_\\phi$ accurately models the $f_i$\" is a reasonable one. Without learning a good graph, it is hard to learn a good $f_\\phi$. Thus, I don't think this assumption will hold in general. In addition, due to a similar reason as above, careful analysis is needed to claim convergence. \n\n\nFor the clarity, if I understand correctly, the author tries to model the non-uniform sampling interval as the missing value problem (i.e. periodic missing). In this case, it can only tackle a subset of \"non-uniform sampling interval\" since it assumes a fixed period. If that is the case, I wonder how CUTs will work in the following example: $x_1$ is sampled with interval T and $x_2$ is sampled with interval 2T, In that case, $x_2$ will be missing at $t=T, 3T, 5T, ...$ (assuming start t=0). So how CUTs can impute this value $x_2$ in-between since no observation is provided?\n\n[1] Geffner, T., Antoran, J., Foster, A., Gong, W., Ma, C., Kiciman, E., ... & Zhang, C. (2022). Deep End-to-end Causal Inference. arXiv preprint arXiv:2202.02195.\n[2] Morales-Alvarez, P., Lamb, A., Woodhead, S., Jones, S. P., Allamanis, M., & Zhang, C. (2021). VICause: Simultaneous Missing Value Imputation and Causal Discovery with Groups. arXiv preprint arXiv:2110.08223.\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5BHHpSzTDi", "reviewer": "Reviewer_fTfw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes an architecture to infer causal link from irregularly sampled time series data. The authors embrace the Granger causality paradigm. The method works by interleaving missing data imputation scheme and causal graph learning. The causal graph is used to structure the imputation predictions by using only causal predictors. The inferred causal graph is assumed to get more accurate as the imputation gets better. The model proceeds in three stages. The first is learning the forecasting / imputation and causal graph using the initial imputation. The second is similar but replaces the missing values with the predictions from stage 1. The third further refines the causal graph learning by replacing the missing values by the imputation from the second stage. The causal graph of the last stage is the predicted causal graph of the model.", "summary_of_the_review": "Interesting idea that would deserve additional experiments to fully grasp the contribution of the method. The clarity and the positioning with respect to existing works could be improved.", "strength_and_weaknesses": "### Strengths\n\n- This paper addresses an important problem in causal discovery : inferring causal dependencies from irregular time series. \n- The method appears to outperform baselines it is comparing against.\n- The iterative refinement of the imputation is a good idea and the authors show that the data fitting and causal graph discovery are helping each other.\n- The paper proposes different ablations (though I believe complementary experiments would be required - see below).\n\n\n### Weaknesses\n\n\n- The biggest weakness of this paper is the clarity. I think Figure 1 and Figure 2 should be mixed together so you make very clear that each stage 1-2-3 corresponds to doing one iteration of Figure 1. The notation at the beginning of Section 4.2 is uncommon as well (what is $p(x \\rightarrow p(x))$, this lacks rigour. Similarly, $\\theta$ is not directly understood as parametrising $m$. Only in point of Theorem 1 does it become apparent, which is, I believe, the wrong place to introduce this concept. \n\n- In the definition of Granger causality, I think there is a mistake in the causal direction. If I’m not mistaken, you mean $j$ causes $i$.\n\n- The implications of the assumptions of Theorem 1 should be discussed in the main text. It’s important for the reader to have an intuitive grasp of when this theorem holds. \n\n- It seems that each stage is a refinement of the causal graph learning by using more accurate imputations. In that respect, I think it would make sense to have an experiment that investigates the impact of a different number of refinement steps. It does not seem to be present in the ablation study section.\n\n- The related section misses the whole line of work of causality in time series using convergent cross mapping. I encourage the authors to show how their paper situates with respect to that literature.  In particular, extensions of such methods have been proposed for irregular time series (e.g. Latent Convergent Cross Mapping - https://openreview.net/pdf?id=4TSiOTkKe5P), which represents a relevant baseline for the problem discussed here. \n\n- You are comparing your approach with a GP for imputation. I believe a GP is non causal as it may use observations from the future to predict information from the past. I have few questions regarding this. First do you think it is an issue that the imputation is non-causal. Second, if not, would your approach fare better if another non-causal imputation strategy would be used (e.g. BRITS that you are referring to). In which case, a single step of imputation followed by a causal graph learning step could be enough to reach similar performance. \n\n- I think unstructured time series is not the appropriate name for the type of time series you are considering. In my experience, this is more often referred to as *irregular* time series. \n\n- Despite the bold numbers, it seems difficult to appreciate the magnitude of the improvement in performance this method is giving. Indeed, the difference between AUC results are very small. \n\n- Minor : Right above equation 11, I believe you mean last $n_3$ Epochs and not $n_2$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster