Causal Discovery from Subsampled Time Series with Proxy Variables
Authors: Mingzhou Liu
Xinwei Sun
Lingjing Hu
Yizhou Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: causal discovery
time series
subsampling
proxy variables
TL;DR: We propose to identify causal relations from subsampled time-series with proxy variables.

Abstract: Inferring causal structures from time series data is the central interest of many scientific inquiries. A major barrier to such inference is the problem of subsampling, *i.e.*, the frequency of measurement is much lower than that of causal influence. To overcome this problem, numerous methods have been proposed, yet either was limited to the linear case or failed to achieve identifiability. In this paper, we propose a constraint-based algorithm that can identify the entire causal structure from subsampled time series, without any parametric constraint. Our observation is that the challenge of subsampling arises mainly from hidden variables at the unobserved time steps. Meanwhile, every hidden variable has an observed proxy, which is essentially itself at some observable time in the future, benefiting from the temporal structure. Based on these, we can leverage the proxies to remove the bias induced by the hidden variables and hence achieve identifiability. Following this intuition, we propose a proxy-based causal discovery algorithm. Our algorithm is nonparametric and can achieve full causal identification. Theoretical advantages are reflected in synthetic and real-world experiments.

Causal Discovery from Subsampled Time Series with Proxy Variables
Mingzhou Liu
Xinwei Sun
Lingjing Hu
Yizhou Wang"
School of Computer Science, Peking University
2 Center on Frontiers of Computing Studies (CFCS), Peking University
School of Data Science, Fudan University
Yanjing Medical College, Capital Medical University
Institute for Artificial Intelligence, Peking University
Abstract
Inferring causal structures from time series data is the central interest of many scientific inquiries. A major barrier to such inference is the problem of subsampling, ie., the frequency of measurement is much lower than that of causal influence. To overcome this problem, numerous methods have been proposed, yet either was limited the linear case or failed achieve identifiability. In this paper. we propose a constraint-bed based algorithm that can identify the entire causal structure from subsampled time series, without any parametric constraint. Our observation is that the challenge of subsampling arises mainly from hidden variables at the unobserved time steps. Meanwhile, every hidden variable has an observed proxy, which is essentially itself at some observable time in the future, benefiting from the temporal structure. Based on these, we can leverage the proxies to remove the bias induced by the hidden variables and hence achieve identifiability. Following this intuition, we propose a proxy-based causal discovery algorithm. Our algorithm is nonparametric and achieve full causal identification. Theoretical advantages are reflected in synthetic and real-world experiments. Our code available at sttps://githut. wwt.coooooooiaoo.. cwm/1mz123321 pwopy///royy.... _ausallddscoveer.
Introduction
Temporal systems are the primary subject of causal modeling in many sciences, such as pathology, neuroscience, and economics. For these systems, common issue the difficulty of collecting sufficiently refined timescale data. That is, we can only observe subsampled version of the true causal interaction. This can cause serious problems for causal identification, since full observation (i.e., causal sufficiency [I]) is believed to be an important condition for causal identification, and the violation of which (e.g., the existence of hidden variables) can induce strong bias
example. In AD, patients suffer from memory loss due to the atrophy memory-relatee brain regions such as the Hippocampus (3. To monitor such atrophy, the standard protocol is to perform a MRI examination every six months [4] However, many studies have shown that the disease can progress much more rapidly than this [ 6.. For this reason, when recovering the causal interactions between brain regions, those at the unobserved time steps constitute hidden variables and induce spurious edges in the causal graph, shown in Figure (b).
Example 1.1. Take the pathology study of Alzheimer's 's disease (AD)
the brain
To resolve this problem, many attempts have been made recover the correct causal relations from subsampled data. However, none of them achieved general identifiability results. For example, in
"Conresonndence to sunxinwei @ fudan.edu.cm
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Hippocampus
Prontal
Amygdala
Temporal
Occipital
Cingulum
Frontal
Temporal
Parietal
Hippocamppus
Purietal
Cingulum
Amyzdala
Occipital
Spurious edges
consider subsampling
(b) ignore subsampling
Figure 1: Recovered causal pathways in Alzheimer's disease, with (a) our method that explicitly models the subsampling and (b) Dynotears [7] that neglects subsampling. Spurious edges that contradict clinical studies g are marked red. Please refer to Section 5.2 5.2 and Figure for details.
10 [22. identifiability was achieved only for linear data. As for nonlinear data, only small part the causal information (i.e., an equivalence class) could be identified 13 15 16]. Indeed, encountering such difficulties is no coincidence, considering the fact that there are many hidden variables in the system. Particularly, the hidden mediators prevent us from distinguishing the direct causation from possible mediation and hence only allow us recover some ancestral information.
In this paper, propose a constraint-based algorithm that identify the entire causal structure from subsampled data, without any parametric assumption. Our departure here is that in time series, every hidden variable has an observed descendent, which essentially itself at some observable time in the future]] Therefore, we can use the observed descendent as its prexy variable [17] and adjust for the bias induced by it. For this purpose, we first represent the ancestral information, which is composed of both direct causation and hidden mediation, with the Maximal Ancestral Graph (MAG) [8. Then, to distinguish causation from mediation, we use the observed descendants of the hidden mediators as their proxy variables and adjust for their induced mediation bias. We show that our the causal relations entailed in time series.
strategy can achieve complete identification is essentially nonparametric and only relies on the smoothness and completeness of the structural equation conduct valid proxy-based adjustment 19
Back to the AD example, as shown in Figure ! our method can recover causal pathways that align well with existing clinical studies g 1 while compared baselines fail to do so.
Our contributions are summarized below:
1. We establish nonparametric causal identification in subsampled time series.
We propose an algorithm to practically recover the causal graph.
3. We achieve more accurate causal identification than others on synthetic and real data.
The rest of the paper is organized as follows. First, in Section 2 we introduce the problem setting. basic assumptions, and related literature needed to understand our work. Second, in Section 3 we establish theories structural identifiability. Then, based these theories, in Section 4 we introduce the proposed causal discovery algorithm and verify its effectiveness in Section Finally, conclude the paper and discuss future works in S
For example, the hidden variable X(t.) the unobserved time step t. with X X(t.) + X(t,, + X (tu 2) X (to)) has observable descendent X (to) at observable time to in the future.

---

1
22
E3
4
ts
t1
D3
tg
M
M
B
B
(8)
Summary graph
(b) Full time DAG with k = (c) MAG over observed variables
Figure 2: Graph terminologies: (a) Summary graph. (b) Full time DAG with subsampling factor k: 2. Variables at observed time steps f,, t,, is are marked gray, while those at unobserved time steps t2, 44 dashed. (c) MAG
observed variables. The edges A(4) ((1) and A(la) M M(1a)
(resp.) induced by the inducing paths A(4) - A(12) - M(la) and A(la) - A(l2) M(1a) in the full time DAG. Please refer to the appendix for detailed explanations.
Preliminary
We start by introducing the causal framework and related literature needed to understand our work.
Time series model. Let X(1) (t), Xa(()] be multivariate time series with d variables defined at discrete time steps t= 1,,.,, T. We assume the data is generated by a first-order structural vector autoregression (SVAR) process [I6]:
(t) = (t 1),
where fa the structural function, PA, the parent of X,, and N; the exogenous noise.
Implicit in T is the assumptions that cause precedes effect, and that causation is invariant to time, Le., the structural function and the causal parents PA; keeps unchanged across time steps. These assumptions carry the fundamental beliefs of temporal precedence and stability on causality (.. therefore are widely adopted by existing works [10 [2 16].
Subsampling. The subsampling problem means that model ① can be only observed every k steps
10 12
16..
That is, we can only observe X(1), X(k: (k + 1), ...., X(I [
Graph terminologies. Causal relations entailed in model IT) can be represented by causal graphs (Figure 2 We first introduce the full time Directed Acyclic Graph (DAG) 20) which provides complete description the dynamics in the system.
Definition 2.1 (Full time DAG). Let G E) be the associated full time DAG of model II The vertex set V = {X()) the edge set E contains X₁(1- X2()) iff X; PAj.
We assume the full time DAG is Markovian and faithful to the joint distribution P(X(1), .... X(T)). Assumption 2.2 (Markovian and faithfulness).. For disjoint vertex sets A, B, V, A B/Z A LG Z/Z, where.L denotes d-separation in G.
In practice, it is often sufficient to know the causal relations between time series as whole, without knowing precisely the relations between time instants [21]. In this regard, we can summarize the causal relations with the summary graph (20].
Definition 2.3 (Summary graph). Let G (V,E) be the associated summary graph of model (I)
The vertex set V = X, the edge set E contains X; X,(i j) iff X; e PA,
In this paper, our goal is to recover the summary graph, given data observed at 1, 1 f
For this purpose, we need structure to represent the (marginal) causal relations between observed variables and hence link the observation distribution
summary graph. Here, we use the Maximal Ancestral Graph (MAG) 22), since it can represent casual relations when unobserved variables exist.
lk 1)] be the observed subset and L V be the unobserved subset. Let An(A) the ancestor A. Then, given any full time DAG G over V, the corresponding MAG Mg over O is defined as follows:
Specifically, for the variable set V = (x()) let O =

---

Definition 2.4 (MAG), In the MAG Mg. two vertices A, B O are adjacent iff there is an inducing path. relative L between them in G. Edge orientation is:
A Bin Mg if A An( G;
2. A < in Mg if Be An(A) in G;
3. A B in MG if A An(B) and B An(A) in G.
Remark 2.5. In the MAG, the directed edge A B means is the ancestor of B. The bidirected edge A ++ B mcans there is unobserved confounder U between A and B.
Proximal causal discovery. Recent works 23
[9] found that could the descendant (i.e., proxy) of an unobserved variable M to differentiate direct causation A + B from hidden mediation A + M + B. Specifically, suppose that:
Assumption 2.6 (Smoothness). For each causal pair A - B, the map - PP a) is Lipschitz with respect to the Total Variation (TV) distance, that is, there exists constant L such that:
TV P(B d')) s L/a a').
Assumption 2.7 (Completeness). For each causal pair A - B, the conditional distribution P(BIA) complete, that is, for any function g. we have:
(lg(b)la) 0 almost surely if and only if (b)) = almost surely.
Remark 2.8. Roughly, Assumption 2.6 relies on the continuity of the structural function fi and Assumption 2.7 requires that the characterization function of the exogenous noise N; non-zero. Please refer to 19 for a detailed discussion.
Under the above assumptions, 19 showed that:
Theorem 2.9 (199). Suppose that A and B are mediated by an unobserved variable M, and that M has proxy variable M' satisfying A LG M' Then, we identify whether A B by testing whether pr prbb)) ~ pr pr(mmm (a) has a linear relation. If the linear relation exists, then A + B, otherwise, haveA B.
Remark 2. 20. The linear relation can be tested by checking the least square residual of regressing pr (bla) on pr prmm((a). Please refer to [99 for details.
To ensure the existence of the proxy variable, we require the following self causation assumption, which states that each variable Xt(t) is influenced by its past Xt(t- 1).
Assumption 2.11 (Self causation). In model ( X, E PA, for each i = 1,...,d d.
Remurk 2.12. time series statisties, this also known as the autocorrelation assumption 24
Structural identifiability
In this section, establish the identifiability of the summary graph. For this purpose, connect the observational distribution to the summary graph with the bridge of the MAG.
Specifically, our analysis consists of three progressive results: Proposition 3.1 Proposition 3.3 and Theorem 3.5) First, in Proposition 3.1 we prove that the MAG can be identified from observational data. Then, in Proposition 3.3 show that the identified MAG almost uniquely reflects the structure of the summary graph, in the sense that only edges connecting vertices and their ancestors cannot be determined due to hidden mediators. Finally, in Theorem 3.5 we identify these underdetermined edges with the proxies the hidden mediators and therefore identify the whole summary graph.
'A path between A, B O is an inducing path relative to L if every non-endpoint vertex is either in L collider, and every collider is ancestor of either A or B.

---

O
X
Y
X
U
Y
vertices
vertices
q vertices
(a) Directed path
(b) Confounding structure
Figure Illustration of Definition 3.2 (a) directed path from A with length 4. (b) A confounding structure between A and B with lengths (r,
Next, we first introduce Proposition 3.1 which shows that the MAG is identifiable.
Proposition 3.1 (Identifiability of the MAG). Assuming model ( and Assumption 2.2 then the MAG over the observed variable ser O is identifiable, i.e., its skeleton and edge orientations can be uniquely derived from the joint distribution POO).
Since the identifiability of the MAG's skeleton under the faithfulness assumption is well-known result [T8] we focus on explaining identification edge orientations. Specifically, we will divide the edges into two classes: the instantancous edges and the lagged edges, and discuss their orientations respectively.
The instantaneous edge, e.g., A(ts) + M (tz), is an edge that connects two vertices at the same time. Since we assume cause must precede effect, instantaneous edge does not represent causation but latent confounding, therefore is bidirected according to Definition [.4 For example, in Figure 2 (c), the instantaneous edge Atts) + M (fz) represents the latent confounding A(tx) + A(t2) Mts) between A(ts) and M (t3). On the other hand, the lagged edge, e.g., A(ti) M (f3), is an edge that connects two vertices different time. The lagged edge represents ancestral information and hence is directed (-) from the past to the future.
To connect the identified MAG the summary graph, we first define the following graph structures, examples of which are shown in Figure
Definition 3.2 (Graph structures). In the summary graph,
directed path PAB from A with length / is sequence of distinct vertices A, Vi...., Vi, B where each vertex points to its successor. Two directed paths PAB, PAB. are called disjoint if they do not share any non-startpoint vertex.
2. A confounding structure CAB between A and B with lengths (r, 9) consists of a vertex U, directed path A A from U with length r, and directed path puB from U to B with length where Pu A and pu B are disjoint.
In the following, we explain the relationship between the identified MAG and the summary graph. In particular, we will discuss what the directed and bidirected edges the MAG (resp.) imply about the summary graph.
According Definition 2.4 the directed edge A(I) B(L+ k) in the MAG means is the ancestor of B. Therefore, in the summary graph, there either A - or directed path from A to B. On the other hand, the bidirected edge A(l k:) B(I+ k) in the MAG means there is latent confounder between them, which can be either A(t 1), f.e., A(t k) - -... A(t + +..._ B(t k), or third variable U(t + 1), i.e., A(t + k) graph, there is either directed path from A to B or confounding structure between them.
U(t 1)
B(t + k). Hence, in the summary
Summarizing the above observations, have the following proposition:
Proposition 3.3 (MAG to summary graph). If there are A(t) B(t k) and A(t+ B(t+ k) in the MAG, then, in the summary graph, there either
1. A B. 2. directed path from A to B with length 5 k 2-2. or
3. directed from from A to B with length I k and confounding structure between them with lengths (r S k 2, q k 2).
5

---

(a) Direct effect A
t1
f3
4
t3
M(4)
M(L2)
U
0
U
A
O
A
M
O
M
O
U
A
M
B
O
O
A(t,)
B(tg)
(b) Indirect effect
B
M(+)
(
U
0
U
0
A
A
0
M
M
U
DAMB
A
M
B
0
O
A(t,)
B(tg)
Summary graph
Full time DAG
MAG
Proxy model
Figure 4: Distinguishing the direct effect (A - B) from the indirect one (A .... B) with proxy variables. Note that though (a) and (b) have the same MAG, only the indirect effect A(ti) (122 B(tz) in (b) can be d-separated by M (t2). To test the d-separation, we can use M1ta) as the proxy variable.
the maximum length of the directed path is k 1, this is because any path longer than this can not be an inducing path and therefore can not induce A(t) - B(t k) in the MAG. Please refer the appendix for details.
Remark 3.4. In Proposition 3.3
Proposition 3.3 provides a necessary condition for having A B the summary graph, iee. there are both A(t) B( k) and A(t+ ke) ++ B(t + k) in the MAG. It also inspires us that, to the condition sufficient, we need distinguish the direct effect (A B) from the indirect one (A .....> B).
make
For this purpose, propose technical detail, we first brief our idea below. The indirect effect, unlike the direct one, relies on mediation and therefore can be d-separated by the (unobserved) mediator. To test the d-separation, we can use the observed proxy of the mediator, thanks to the self causation assumption in Assump- tion 2.11 For example, Figure (b), the indirect effect A(ti) M (tz) B(ts) from B can be d-separated by the mediator (t2), who has an observed proxy M (tx).
the proximal causal discovery method. Before preceding any
For the general case, the separation set is bit one representing direct effect are d-separated. Specifically, for two vertices A(t) and B(t + k), the separation set the union of sets M(L+ + S((). The set M(L+) 1) contains possible mediators, namely A(L 1) and any vertex Ms(1+ 1) (M; # B) such that A(I) - M, k) in the MAG and M; is not B's descendan"" The set S(t) is used to d-separate possible back-door paths between A(t) and B(t + R:), it contains any vertex (t) (S, A) such that S,(t) Bt k) or Sc(t) M₁ (t+ for some Mý M in the MAG.
complicated to ensure all paths except the
Equipped with the separation set, we then have the following identifiability result:
Theorem 3.5 (Identifiability of the summary graph). Assuming model (7), Assumption then the summary graph is identifiable. Specifically,
2.2 and
Assumptions 2.6 2.7 2.11
1. There is A + B in the summary graph iff there are A(t) B(t+ + k), A(t + k) + B(t k) in the MAG, and the set M(t + (((++))ur 1)t)(() is not sufficient to d-separate A(t), B(t k) in the full time DAG.
The condition "the set M(t+ 1) US()) is not sufficient to d-separate A(t), B(t k) in the full time DAG" can be tested by the proxy variable M(t+ k) of the unobserved set M(t 1).
"This can be justified from the MAG. Specifically, if M; is the descendant of B, then there is B(t) Vi(t +((++)) k), (i(t) V2(t+ k), ..., Vi(t) Mi(t+ k) in the MAG.

---

Theorem 3.5 provides a necessary and sufficient condition for having A + B in the summary graph.
This condition testable with the proxy M(++k) of the unobserved set M[(+1) (S(t) is observable). The validity of such proxying, iee, A(t) LG M(L+ (()(+)) is proved in the appendix.
4 Discovery algorithm
practically dis- cover the summary graph with Algorithm Specifically, given the observed data points, Algorithm first recovers the MAG according Proposition 3.1 Then, for each pair of vertices in the summary graph, it first uses the necessary condition of "having A(t + Bt + k) and A(t k) + Bt + k) in the MÁG" to construct underdetermined edges. Finally, among these underdetermined edges, it uses the proxy variable approach to identify direct causation and remove the indirect one, according to Theorem 3.5
Equipped with the identifiability results in Proposition 3.1
and Theorem 3.5
Below, we first introduce the Partially Determined Directed Acyclic Graph (PD-DAG), which will be used to represent the intermediate result of the algorithm.
Definition 4.1 (PD-DAG). A PD-DAG is DAG with two kinds of directed edges: solid (-) and dashed (-+). solid edge represents determined causal relation, while dashed one means the causal relation is still underdetermined. We use meta-symbol, asterisk (*->), to denote any of the two edges. In a PD-DAG
(V, E), the vertex points to the vertex B if the edge A+ E. The definition of the directed path and confounding structure are the same as in the summary graph.
Algorithm 1: Discover the summary graph
Data: Data observed / 1, I,.... 1..... [
Result: The summary graph
Construct the skeleton of the MAG with (26]. orient edges according to Proposition 3.1
For every vertex pair A, B, set Ax B if there A(t) B(t k:) and A(t + k) B(t in the MAG. Called the resulted PD-DAG Go Set G Go and iteratively execute:
/* Proposition 3.3 */
(a) For every A+ B, check
(i) directed path from A to B with length / i k-22
i directed path from A to B with length & k 1 and confounding structure between
A and B with lengths (r S k- 2,4 k- 2);
If 3 (i) or (ii), pass. Otherwise, set A B: (b) Randomly pick dashed edge A++ B, check whether A(t) ae B(t M 1), S(t): If the d-separation holds, remove Ax- B. Otherwise, set A + B /* Theorem 3.5 +/
/* Proposition 3.3
until all edges G are solid ones; return G
Remark 4.2. Algorithm I can be generalized to cases where the subsampling factor l is unknown, by skipping the step (a) below line 3.
Experiment
In this section, we evaluate our method on synthetic data and a real-world application, i.e., discovering causal pathways in Alzheimer's disease.
Compared baselines. Methods that account for subsampling: 1. SVAR-FCI [16] that extended the FCI algorithm to time series and recovered a MAG over observed variables; 2. NG-EM [10 that
achieved identifiability with linear non-Gaussianity and used Expectation Maximization (EM) for estimation. Methods that neglect subsampling: 1. Dynotears 7 that extended the score-based Notears [27 algorithm to the time series; 2. PC-GCE (2T) that modified the PC algorithm for temporal data with new information wwwetatiiionttttttieeeee conditional independence (CI) test.
7

---

Subsampling factor
6.8-
0.6-
0.4
6.6
Ours
SWAR FCI EH
DYAKOTEARS
0.0
PC-DCE
0.0
Sample
1.0
1.0
0.8
0.8
0.8
0.6
0.8
0.2
0.2
0.2
0.0
0.0
0.0
300
:000
1200
400
1000
1200
800
1000
1200
Figure 5: Performance of our method and baselines under different subsampling factors (upper row) and sample sizes (lower row).
Metrics. We use the Fr -core, precision, and recall, where precision and recall (resp.) measure the accuracy and completeness of identified causal edges, and F₁ 2. precision-recall
precision+recal!
Implementation details. The significance level is set to 0.05. For the MAG recovery, use the FCI algorithm implemented in the causallearn package" Temporal constraints, egg., causal precedence, time invariance, and self causation added as the background knowledge.
5.1 Synthetic study
Data generation. We generate radnom summary graphs with the Erdos Erdos-Renyi model 28 where the vertex number is set to 5, the probability of each edge is set to 0.3. For each graph, we generate temporal data with the structural equation (t) ΣYPAA fy (t ()) N,, where the function fiy is randomly chosen from (linear, sin, tanh, sqrt). the exogenous noise N, is randomly sampled from [uni form, gauss. exp. gamma). We consider different subsampling factors k= = {2, 3, 4, 5} and sample sizes n = {600, 800, 1000, 1200). For each setting we replicate over 100 random seeds.
Comparison with baselines. Figure shows the performance of our method and baselines under different subsampling factors (upper row) and sample sizes (lower row). As we can see, our method significantly outperforms the others in all settings. Specifically, compared with methods that account for subsampling (SVAR-FCI and NG-EM), our method achieves both higher precision and recall, indicating less detection error and missing edges. This advantage can be attributed the fact that method enjoys an identifiability guarantee (v.s. SVAR-FCI) and meanwhile requires no parametric assumption the structural model (v.s. NG-EM). Compared with methods that ignore subsampling (Dynotears and PC-GCE), our method achieves higher F1 Fi-score, precision, and comparable in recall. This result shows that method can effectively reduce the spurious detection induced by unobserved time steps. Besides, we can observe that Dynotears and PC-GCE slightly outperform SVAR-FCI and NG-EM, which again demonstrates the necessity of establishing nonparametric identification subsampling problems.
Intermediate results. We evaluate the intermediate results of Algorithm [ (MAG, edges identified by proxies, summary graph) and report the results in Figure 6 As shown, both the recovered MAG and edges identified by proxies have high accuracy under moderate subsampling factors and sample sizes, hence explaining the effectiveness our algorithm in recovering the summary graph. Meanwhile, we also observe that the performance slightly decreases when the subsampling factor & is large. This
hhttpa://gite wtt.giiub..oo.pr... com/py- hwompyywhy//eeee why/ccusall caccsaalllesss learn
We also consider different graph scales d (5, 15, 25,35, 45). Please refer to the appendix for details.

---

Subsampling factor
0.9
precaton
0.9
0.0
0.0
0.0
mag
praay
Summarry _.0g
Sample size
1.0
10-
0.9
prectaton
0.3
0.9
0.3-
600
800
1000
1200
600
800
3000
1200
600
800
1000
1200
sumple uze
sumble size
samp 500
Figure Evaluation of intermediate results. We report Fcooe, precision, and recall of the recovered MAG, edges identified by proxies, and the recovered summary graph.
is explained as follows. When is large, there are many unobserved steps between two observations, which weakens the correlation pattern in data and therefore breaks our faithfulness assumption.
5.2 Discovering eausal pathways in Alzheimer's disease
Background. Alzheimer's disease (AD) is one of the most common reuro-degenerative diseases. In AD, patients suffer from memory loss due to atrophy of memory-related brain regions, such as the Hippocampus (3] and Temporal lobe [29] A widely accepted explanation for such atrophy is: the disease releases toxic proteins, e.g., AB 33 and fax [31]: along anatomical pathways, these proteins spread from one brain region to another, eventually leading to atrophy of the whole brain 32 Recovering these anatomical pathways, i.e., underlying causal mechanisms, will benefit the understanding of AD pathology and inspire potential treatment methods.
Dataset and preprocessing, We consider the Alzheimer's Disease Neuroimaging Initiative (ADNI) dataset 4. which the imaging data acquired from structural Magnetic Resonance Imaging (sMRI) scans. We apply the Dartel VBM [33] for preprocessing and the Statistical Parametric Mapping (SPM) 34 for segmenting brain regions. Then, we implement the Automatic Anatomical
Labeling (AAL) atlas [35 to partition the whole brain into 90 regions. In total, we use 558 subjects with baseline and month-6 follow-up visits enrolled in ADNI-GO/1/2/3 periods.
Results. Figure shsows the recovered summary graph over 90 brain regions. For illustration, in Figure D (a), further group the brain regions into meta-regions according their anatomi- cal structures. We can observe that i) most causal pathways between meta-regions are unidirec- tional: ii) the identified sources of atrophy are the Hippocampus, Amygdala, and Temporal lobe, which are all carly-degenerate regions [3] [9]: iii) the topology order induced from our result, i.e., (Hip., Amy., Tem., Cin., Ins., Fro., Par., Occ.) coincides with the temporal degeneration order found in 8 9 These results constitute an important finding that can be supported by existing studies: the atrophy (releasing of toxic proteins) is sourced from the Hippocampus and gradually propagates to other brain structures along certain anatomical pathways 132 36).
In contrast, Figure (b), the causal relations recovered by the Dynotears baseling are less clear. For example, most of the identified interactions are bidirectional, which may be due to the spurious edges induced by subsampling. Besides, the identified atrophy source is the Frontal lobe, with AD-related regions identified as outcomes, which is inconsistent with clinical studies. These results, from another perspective, show the importance modeling subsampling in time series causal discovery.
'Please refer to the appendix for results of the other baselines.

---

Frontal Lobe
Tamporal Lobe
Occipital Lobe
Parietal
Cingulum
Hippocampus
Amyydala
Insuia
Figure 7: Recovered summary graph in Alzheimer's disease.
Conclusion
In this paper, we propose a causal discovery algorithm for subsampled time series. Our method leverages the recent progress of proximal causal discovery and can achieve complete identifiability without any parametric assumption. The proposed algorithm can outperform baselines on synthetic data and recover reasonable causal pathways in Alzheimer's ' disease.
Limitation and future work. Our method relies on an accurate test of the conditional independence (CI) and therefore may suffer from low recall when the CI patterns in data are weak. To solve this problem, will investigate theories high-efficiency CI tests and pursue a dedicated solution.
Acknowledgments
This work was supported by National Key R&D Program China (2022DD011490)
References
[1] Judea Pearl. Causality. Cambridge University Press, 2009.
[2] Patrick Suppes. Causal analysis of hidden variables. In PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, volume 1980, pages 563-571. Cambridge University Press, 1980.
[3] Mark J West, Paul D Coleman, Dorothy G Flood, and Juan C Troncoso. Differences in the pattern of hippocampal neuronal loss in normal ageing and alzheimer's disease. The Lancet, 344(8925):769-772. 1994.
[4] Ronald Carl Petersen, Paul S Aisen, Laurel A Beckett, Michael C Donohue, Anthony Collins Gamst, Danielle J Harvey, Clifford Jack, William J Jagust, Leslie M Shaw, Arthur W Toga, et al. Alzheimer's is disease neuroimaging initiative (adni): clinical characterization. Neurology, 74(3):201-209, 2010.
[5] Rachelle Smith Doody, Paul Massman, and Kay Dunn. method for estimating progression rates in alzheimer disease. Archives of neurology. 58(3):449 454, 2001.
[6] Craig J Thalhauser and Natalia I. Komarova. Alzheimer's disease: rapid and slow progression. Journal of the Royal Society Interface, 966): 19-126, 2012.
[7] Roxana Pamfil, Nisara Sriwattanaworachaii, Shaan Desai, Philip Pilgerstorfer, Konstantinos Georgatzis, Paul Beaumont, and Bryon Aragam. Dynotears: Structure learning from time-series
10

---

data. In International Conference on Artificial Intelligence and Statistics, pages 1595-1605 PMLR, 2020.
[8] Alexandra I. Young, Razvan V Marinescu, Neil P Oxtoby, Martina Bocchetta, Keir Yong, Nicholas C Firth, David M Cash, David I. Thomas, Katrina M Dick, Jorge Cardoso, et al. Uncovering the heterogeneity and temporal complexity of neurodegenerative diseases with subtype and stage inference. Nature communications, 9(1):4273, 2018.
[9] Jacob W Vogel, Alexandra L Young, Neil P Oxtoby, Ruben Smith, Rik Ossenkoppele, Olof T Strandberg, Renaud La Joie, Leon M Aksman, Michel J Grothe, Yasser IturiiaMedinn,, et al. Four distinct trajectories of tau deposition identified in alzheimer's disease. Nature medicine, 27(5):871-881, 2021.
[10] Mingming Gong, Kun Zhang, Bernhard Schoelkopf, Dacheng Tao, and Philipp Geiger. Discov- ering temporal causal relations from subsampled data. In International Conference on Machine Learning, pages 1998-1906 PMLR, 2015.
[11] Mingming Gong, Kun Zhang, Bernhard Schölkopf, Clark Glymour, and Dacheng Tao. Causal discovery from temporally aggregated time series. In Uncertainty in artificial intelligence: proceedings of the... conference. Conference on Uncertainty in Artificial Intelligence, volume 2017. NIH Public Access, 2017.
[12] Alex Tank, Emily B Fox, and Ali Shojaie. Identifiability and estimation of structural vector autoregressive models for subsampled and mixed- sixee-frrqqeecy time series. Biometrika, 106(2):433- 452, 2019.
[13] David Danks and Sergey Plis. Learning causal structure from undersampled time series. 2013.
[14] Sergey Plis, David Danks, Cynthia Freeman, and Vince Calhoun. late-agnostic (causal) structure learning. Advances in neural information processing systems, 28, 2015.
[15] Antti Hyttinen, Sergey Plis, Matti Järvisalo, Frederick Eberhardt, and David Danks. Causal discovery from subsampled time series data by constraint optimization. In Conference on Probabilistic Gruphical Models, pages 216-227. PMLR, 2016.
[16] Daniel Malinsky and Peter Spirtes. Causal structure learning from multivariate time series in settings with unmeasured confounding. In Proceedings of 2018 ACM SIGKDD workshop on causal discovery, pages 23-47, PMLR, 2018.
[17] Manabu Kuroki and Judea Pearl. Measurement bias and effect restoration in causal inference. Biometrika, 101(():423-44 4-73--4372220 2014.
[18] P Spirtes, C Meek, and T Richardson. Computation, causation and discovery, 1999.
[19] Mingzhou Liu, Xinwei Sun, Yu Qiao, and Yizhou Wang. Causal discovery with unobserved variables: proxy variable approach. arXiv preprint wrxiv:2305.05281 2023.
[20] Chang Gong, Di Yao, Chuzhe Zhang, Wenbin Li, and Jingping Bi. Causal discovery from temporal data: An overview and new perspectives. arXiv preprint arXiv:2303. /013000.01100 12, 2023.
[21] Charles K Assaad, Emilie Devijver, and Eric Gaussier. Discovery of extended summary graphs in time series. In Uncertainty in Artificial Intelligence, pages 96-106. PMLR, 2022.
[22] Jiji Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-11)
2008. [23] Wang Miao, Zhi Geng, and Eric J Tchetgen Tchetgen. Identifying causal effects with proxy variables of an unmeasured confounder. Biometrika, 105(4):987-993, 2018
[24] Maurice S Bartlett. On the theoretical specification and sampling properties of autocorrelated time-series. Supplement to the Journal of the Royal Statistical Society, 8(1):27 1946.
[25] ZA Lomnicki and SK Zaremba. On the estimation of autocorrelation in time series. The Annals of Mathematical Statistics, (8(1):140-155) 1957.
[26] Peter Spirtes, Clark Glymour, Richard Scheines, and David Heckerman. Causation, prediction. and search. MIT press, 2000.
[27] Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with no tears: Continuous optimization for structure learning. Advances in neural information processing systems, 31, 2018
11

---

[28] Paul Erdós, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
[29] Clifford R Jack, Ronald C Petersen, Yuecheng Xu, Peter C O'Brree,, Glenn E Smith, Robert Ivnik, Eric G Tangalos, and Emre Kokmen. Rate of medial temporal lobe atrophy in typical aging and alzheimer's disease. Newrology, 5144)9993-999 1998.
[30] Frank M LaFerla, Kim N Green, and Salvatore Oddo. Intracellular amyloid-3 in alzheimer's disease. Nature Reviews Neuroscience, 8(7):499-509) 2007.
[31] Michala Kolarova, Francisco Garcfa-Sierra, Ales Bartos, Jan Ricny, and Daniela Ripova. Struc- ture and pathology of tau protein in alzheimer disease. International journal of Alzheimer's disease, 2012, 2012.
[32] George Bloom. Amyloid-3 and tau: the trigger and bullet in alzheimer disease pathogenesis. JAMA neurology, 7 71(4):505-508, 2014.
[33] John Ashburner. Vbm tutorial. Wellcome Trust Centre for Neuroimaging, London, UK, 2010.
[34] Karl Friston. Statistical parametric mapping. Neuroscience databases: a practical guide, pages 237-250, 2003.
[35] Nathalie Tzourio-Mazoyerr Brigitte Landeau, Dimitri Papathanassiou, Fabrice Crivello, Octave Etard, Nicolas Delcroix, Bernard Mazoyer, and Mare Joliot. Automated anatomical labeling of activations in spm using macroscopic anatomical parcellation of the mni mri single-subject brain. Neuroimage, 15(1):273-289, 2002.
[36] Mingzhou Liu, Xiangyu Zheng. Xinwei Sun, Fang Fang. and Yizhou Wang. Which invariance should we transfer? A causal minimax learning approach. In Proceedings of the 40th Interna- fional Conference on Machine Learning, volume 202, pages 22488 -25227. PMLR, 23-29 Jul 2023.
12


Reviews:
[{"review_id": "eKb5bwfSI9", "reviewer": "Reviewer_GTBD", "summary": "This paper studies the problem of subsampled time series in causal discovery, in which the unobserved time steps may lead to the existence of latent confounders. To this end, this paper proposes a constraint-based algorithm by leveraging proxy variables to remove the bias induced by latent confounders. The experimental results verify the effectiveness of the proposed algorithm.\n", "questions": "Refer to Weaknesses", "limitations": "Refer to Weaknesses", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper addresses the problem of subsampled time series in causal discovery, which is important but challenging.\n\n2. The paper is well-structured and written.\n\n3. The experimental results show that the proposed method outperforms several representative baselines.", "weaknesses": "1. In Theorem 2.8, extra assumptions are required for testing conditional independent relations in related literature, but they are not discussed in this paper. \n\n2. How to search the proxy variable of target hidden variables. If an invalid proxy variable is selected, what is the output of the proposed algorithm?\n\n\n3. In simulation data, the dimension of the random graph is only five. Can you show the performance of the proposed method in a larger-scale network?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your efforts and valuable suggestions on our paper. We address your concerns below.\n\n**Q1.** In Theorem 2.8, extra assumptions are required for testing conditional independent relations in related literature, but they are not discussed in this paper.\n\n**A**: These assumptions are mentioned in Asm. 2.6 and Rem. 2.7.\n\n\n**Q2.** How to search the proxy variable of target hidden variables. If an invalid proxy variable is selected, what is the output of the proposed algorithm?\n\n**A**: The proxy of each hidden variable is itself at some observable time in the future, so no searching is needed. We mentioned this in Thm. 3.5 (line 190).\n\n\n**Q3.** In simulation data, the dimension of the random graph is only five. Can you show the performance of the proposed method in a larger-scale network?\n\n**A**: Our method is consistently accurate under different scales. Please refer to the supplementary PDF for details.\n\n\n"}, {"review_id": "oCglubGluY", "reviewer": "Reviewer_XP2k", "summary": "In this paper, the author(s) propose a new technique to learn the summary graph of time-series data. As a motivation for their work, the author(s) discuss the interesting application of learning causal pathways in Alzheimer’s disease. The time series model studied in this work is quite general, and suitable for many applications. The author(s) provide a simple algorithmic approach to learn the summary graph. This algorithm is essentially based on verifying d-separation, by testing conditional independence. The author(s) conclude with an experimental comparison, showing that their method achieves superior performance than a baseline, using various synthetic datasets and a real-world medical application.", "questions": "Can you please describe exactly step 1 in your algorithm? How do you test conditional independence?", "limitations": "Yes, the author address limitations in Section 6.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper studies an very important and difficult problem. The application of learning causal pathways in Alzheimer’s disease is very relevant. The paper is also well-written and easy to follow.", "weaknesses": "My main concern pertains the faithfulness assumption. Faithfulness it is useful for getting identifiability results, and it allows to recover the causal structure by testing conditional independence. However, in many scenarios there is no practical reason to assume faithfulness. The use of faithfulness significantly limits the novelty of their work. If I understand correctly, the implementation of their algorithm essentially uses conditional independence to recover the causal structure. Testing conditional independence is practically problematic. Hence, I also have doubts on the scalability of their method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your efforts on our paper. We address your concerns below and hope this can help you re-evaluate our paper.\n\n**Q1.** My main concern pertains to the faithfulness assumption. Faithfulness is useful for getting identifiability results, and it allows for recovery of the causal structure by testing conditional independence. However, in many scenarios, there is no practical reason to assume faithfulness. The use of faithfulness significantly limits the novelty of their work. \n\n**A**: Our method can work under the v-adjacency-faithfulness assumption [1], which requires that any two variables connected by an inducing path in the causal structure are dependent given any conditioning set. This assumption is strictly weaker than strong faithfulness and can handle common counterexamples such as the unshielded collider.\n\nThe faithfulness assumption or its weaker variations have been widely utilized in constraint-based and score-based causal discovery approaches. This can be justified by the mathematical insignificance of unfaithful distributions (a lower-dimensional plane in a higher-dimensional space) [2-4]. Furthermore, a recent investigation [5] indicates that any causal learning method deemed effective must adhere to the standard practice of incorporating algorithms under the faithfulness condition. This highlights the essential nature and significance of the faithfulness condition.\n\n[1] Zhang J, Eberhardt F, Mayer W, Li MJ. ASP-based discovery of semi-Markovian causal models under weaker assumptions. IJCAI. 2019.\n\n[2] Meek C. Strong completeness and faithfulness in Bayesian networks. UAI. 1995.\n\n[3] Spirtes P, Glymour CN, Scheines R. Causation, prediction, and search. MIT press. 2000.\n\n[4] Uhler C, Raskutti G, Bühlmann P, Yu B. Geometry of the faithfulness assumption in causal inference. The Annals of Statistics. 2013.\n\n[5] Lin H, Zhang J. On learning causal structures from non-experimental data without any faithfulness assumption. Algorithmic Learning Theory. 2020.\n\n\n**Q2.** Testing conditional independence is practically problematic. Hence, I also have doubts on the scalability of their method.\n\n**A**: Our method is scalable to larger sizes of the causal graph. For instance, it takes only 3 hours to run a simulation experiment with 45 variables (see Fig. 1 in the supplementary PDF). \n\nIn contrast, the baselines [10-12] (functional causal model-based), which use the EM algorithm for iterative estimation, cannot produce results in a feasible amount of time; The baseline Rhino [Gong et al. 2023] (score-based), which involves a double-nested optimization, requires up to 6-8 hours of training to converge.\n\nTo summarize, we believe that scalability is a common challenge for causal discovery methods, not just constraint-based ones. Addressing this issue is beyond the scope of this paper.\n\n[1] Gong W, Jennings J, Zhang C, Pawlowski N. Rhino: Deep causal temporal relationship learning with history-dependent noise. ICLR. 2023.\n\n**Q3.** Can you please describe exactly step 1 in your algorithm? How do you test conditional independence?\n\n**A**: As mentioned in line 220, we use the Fast Causal Inference (FCI) algorithm implemented in the $\\mathrm{causallearn}$ package to perform step 1. We use the kernel-based conditional independence test [Zhang et al. 2011].\n\n[1] Zhang K, Peters J, Janzing D, Schölkopf B. Kernel-based conditional independence test and application in causal discovery. UAI. 2011.\n"}, {"review_id": "eevm106AUK", "reviewer": "Reviewer_7zAn", "summary": "This paper proposed a non-parametric constraint-based algorithm that can identify the entire causal structure from subsampled data, which leverages the proxy variable to adjust the bias induced by the hidden variable.\n", "questions": "See the weakness above.", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Concise and clear theoretical derivation. Introduce the proposed method by discussing the connections between different graphs step by step.\n", "weaknesses": "- The paper is rather incremental as the core of the method is based on [19] to use proxy variables to detect and eliminate the confounding effect brought by the subsampling.  \n- Moreover, the method proposed by [19] seems to require more assumptions but is not disclosed in this paper. And it is unclear whether those specific assumptions can be satisfied in this work.\n- In addition, this work assumes the self-exciting property of the time-series which is not necessarily held and it is interesting to see how to find the proxy variables and what would be the result in this case.\n- It could be better to provide more than 5 vertex numbers in the experiment.\n- What would be the result if the causal graph becomes denser?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your efforts on our paper. We address your concerns below.\n\n**Q1.** The paper is rather incremental as the core of the method is based on [19] to use proxy variables to detect and eliminate the confounding effect brought by the subsampling.\n\n**A**: First note that our paper solves a very different problem from [19]. Our method is the first to achieve nonparametric causal identification in subsampled time series, setting it apart from existing methods that are limited to the linear case.\n\nMoreover, at the cores of our method lie the formulation of the subsampling bias (Def. 3.2, Prop. 3.3) and the identification of the separation set (Thm. 3.5 (1)). These analyses serve as the foundation for our use of proxy variables.\n\n**Q2.** Moreover, the method proposed by [19] seems to require more assumptions but is not disclosed in this paper. And it is unclear whether those specific assumptions can be satisfied in this work.\n\n**A**: [19] requires the smoothness of the structural equation and the invertibility of the transition matrix. All of them can be satisfied in our work. \n\nDue to space limits, we in Asm. 2.6 used the shorter version of their assumptions (Exam. 4.4, [19]). We will supplement the full assumptions to the manuscript as suggested.\n\n**Q3.** In addition, this work assumes the self-exciting property of the time-series which is not necessarily held and it is interesting to see how to find the proxy variables and what would be the result in this case.\n\n**A**: As stated in Rem. 2.11, the self-causation assumption is commonly used in time series. For cases where this assumption does not hold, no immediate guarantee of finding suitable proxies can be given. We will work on this in future work.\n\n**Q4.** It could be better to provide more than 5 vertex numbers in the experiment. What would be the result if the causal graph becomes denser?\n\n**A**: Our method is consistently accurate under different scales and densities. Please refer to the supplementary PDF for details.\n"}, {"review_id": "cUzC7R2sLT", "reviewer": "Reviewer_Y9xG", "summary": "# Summary\nIn this paper, the authors address the problem of inferring causal structures from subsampled time series data, where the frequency of measurement is much lower than that of causal influence. This presents challenges in identifying the causal structure, as hidden variables at unobserved time steps can induce bias. Existing methods that tackle this problem are limited to linear cases or fail to achieve identifiability.\n\nThe main contribution of this paper is a constraint-based algorithm that can identify the entire causal structure from subsampled time series without any parametric constraints. The authors propose a proxy-based causal discovery algorithm that leverages the temporal structure of time series data to remove the bias induced by hidden variables. The algorithm is nonparametric and can achieve full causal identification. Specifically, the author leverages the proxy variables to test the edge directions of the summary DAG from the uniquely identified MAG. \n\nThe authors demonstrate the theoretical advantages of their method and provide experiments on both synthetic and real-world data, showcasing improved performance over existing methods.", "questions": "1. In figure 4 proxy model, do you mean $M(t_2)$?", "limitations": "The author did discuss its limitations but they only discuss the limitations of conditional independence test. Howver, in the weakness section, I have raised several improvements the author can consider. I suggest including these discussions in the limitations as well. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "# Originality\n\nThe paper presents a novel approach to causal discovery in subsampled time series data by proposing a constraint-based algorithm that leverages proxy variables to handle the challenges posed by hidden variables at unobserved time steps. The originality of the method lies in its ability to identify the entire causal structure without any parametric constraints, setting it apart from existing methods that are limited to linear cases or fail to achieve full identifiability. The authors draw inspiration from the recent progress in proximal causal discovery and adapt it to the subsampled time series setting.\n\n# Quality\nThe quality of the paper is high, as it presents a well-formulated methodology with solid theoretical foundations. The authors provide rigorous proofs for their proposed algorithm's identifiability properties, ensuring that the algorithm is grounded in strong theoretical underpinnings. Although I have some questions regarding its generality and required assumptions, I will elaborate about them later.\n\nAs for the experiments, the author conduct 1 synthetic and 1 real-world experiment, which demonstrates its effectiveness against the baselines.\n\n# Clarity\n\nThe paper is well-written and clear in its presentation. The methodogy is clear, thanks to the intuitive explanation provided by the authors. They also provide necessary background information on causal discovery and related literature. \n\n# Significance\n\nThe problem that this paper aims to talks is significant in the field of tmeproal causal discovery. Although I don't think this paper fully addresses it, it made a reasonable progress towards the final destination. ", "weaknesses": "# Weakness\nAlthough the paper provide a solid progress towards the final destination, here are some limitations I am a bit worried about: \n\n## Assumptions are too strong:  \nOne assumption is that only 1 step window is considered in this paper. However, is this true in practice? Is it possible that some factors has long-standing effect (higher-order Markovian) to the target variable? Can your method handle such scenario? \n\nFor summary DAG, does it has to be a DAG? Since from general full-time DAG, the summary graph may not be a DAG and can contain cycles. Does your method handle such cases? For example, A(1) -> B(2) and B(1) -> A(2), and the summary graph is A<->B. \n\nWhat are the consequence if some variables are not self-caused? That means the proxy variables may not exists. In that case, full identifiablity cannot be establish, right? You may want to add something like to what extend of identifiability your method can establish without such assumption. \n\n## Comparison with baselines\nThe author includes some of the well-known baselines. Surprisingly, Dynotears performes reasonably ok considering that it is a linear model (in its original form). However, after Dynotears, several state-of-the-art baselines are proposed, like Rhino [1]. Can you compare your method with this nonlinear model?\n\n[1]Gong, Wenbo, et al. \"Rhino: Deep Causal Temporal Relationship Learning With History-dependent Noise.\" arXiv preprint arXiv:2210.14706 (2022). Code at https://github.com/microsoft/causica/tree/v0.0.0 \n\n## Scalability\n\nHow expensive it is to run such algorithm, since you need to test every pair. For real-world experiment, you scale it to 90 variables, how long does it need to run it? If your method can be scaled to higher-order SVAR, how does it scales with the window size?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the highly constructive feedback and thoughtful suggestions on our paper. We address your concerns below.\n\n**About assumptions**:\n\nWe first would like to point out that our assumptions, such as the first-order SVAR assumption and the self-causation assumption are commonly adopted in the literature [10-15,26-27]. \n\n**Q1.** One assumption is that only 1 step window is considered in this paper. However, is this true in practice? Is it possible that some factors has long-standing effect (higher-order Markovian) to the target variable? Can your method handle such scenario?\n\n**A**: The first-order Markov model offers a practical approximation for numerous real-world situations. This includes scenarios like Reinforcement Learning tasks based on the Markovian Decision Process, neural activities in the brain [Valdes-Sosa et al. 2004], epidemic spreading [Anderson et al. 1991], and economic growth [Orcutt et al. 1969].\n\nThe extension to the higher-order settings is not a trivial task, as longer causal chains may induce the bias in a much more complex way than shorter ones. We plan to address these cases in future work.\n\n\n[1] Valdes-Sosa PA. Spatio-temporal autoregressive models defined over brain manifolds. Neuroinformatics. 2004.\n\n[2] Cohen JE. Infectious diseases of humans: dynamics and control. JAMA. 1992.\n\n[3] Orcutt GH, Winokur Jr HS. First-order autoregression: inference, estimation, and prediction. Econometrica. 1969.\n\n\n**Q2.** For summary DAG, does it has to be a DAG? Since from general full-time DAG, the summary graph may not be a DAG and can contain cycles. Does your method handle such cases?\n\n**A**: Indeed, the summary graph can contain cycles. Our method can handle this case since it does not influence the identifiability results. We will modify the manuscript accordingly.\n\n**Q3.** What are the consequence if some variables are not self-caused? That means the proxy variables may not exists. In that case, full identifiablity cannot be establish, right? You may want to add something like to what extend of identifiability your method can establish without such assumption.\n\n**A**: Indeed, for this case, full identifiability cannot be established. What we can identify are ancestral equivalence classes [Plis et al. 2015]. We will supplement this discussion to the manuscript as suggested.\n\n[1] Plis S, Danks D, Freeman C, Calhoun V. Rate-agnostic (causal) structure learning. NeurIPS. 2015.\n\n\n**Comparison with Rhino**:\n\nOur method can outperform Rhino for about 30% in the f1-score on the synthetic dataset. Please refer to the supplementary PDF for details.\n\n**About scalability**:\n\nFirst note that we do NOT need to test every pair because most of the pairs can be screened out in step-3(a) with the necessary condition. \n\nIt takes about 20 hours to run the real-world experiment. This time cost is acceptable considering that many of the baselines, e.g., [10,11,17], can not produce results in a feasible amount of time.\n\nTo further validate the scalability of our method, we provide more experimental results in the supplementary PDF.\n\n\n**About Fig. 4**. Indeed, we mean $M(t_2)$. This is a typo."}, {"review_id": "hwFFpb1Rvd", "reviewer": "Reviewer_3AR7", "summary": "The authors suggest a method of causal discovery for multivariate time series under the regime when the data is being sampled at constant skips in the time dimension. Under mild assumptions, they prove that their method works asymptotically.", "questions": "1. I feel like Definition 2.3 can be phrased more simply. The way you wrote it makes it look circular.\n2. I am a little confused by the figures. In Figure 2.c., I don't understand why there wouldn't be an arrow from A(t_3) to M(t_5). Or perhaps the faded arrows count? Why is there a difference between faded and non-faded arrows?\n3. In Figure 3, where are some vertices faded and some not? Is there a difference? It looks like it is meant that faded means unobserved, but I don't think that's what you meant.\n4. Put Remark 4.2 outside of the algorithm.\n5. Line 224: random is misspelled.\n", "limitations": "None.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper's contribution is clear, the methods are interesting and novel, and the subject (causal inference in multivariate time series) is of interest to many. Other than some places I will mention, the explanations are clear.", "weaknesses": "I would like to see a little more discussion on previous work. I see citations about work that inspired the current one, for example [17, 19, 25] on using descendants of an unobserved variable to differentiate direct causation from hidden mediation, but I do not see citations for competing methods for causality under the regime of sampling on the time dimension. It would be good to be explicit about what the current state of the art is in that direction, and how the current work compares. You mention them in Section 5 (SVAR-FCI, NG-EM, Dynotears, PC-GCE) but I'd like to see a bigger discussion on the differences. Specifically, it would be great if we had a basic example in mind where \"naive\" approaches clearly fail, and make us understand how the proposed method avoids the issue intuitively.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive assessment and valuable suggestions on our paper. We will modify the manuscript accordingly. \n\n**About related works.** The existing methods have been discussed in lines 30-36. To summarize, identifiability is only achieved in linear data. As for nonlinear data, only a small part of the causal information (i.e., an equivalence class) can be identified.\n\n**About the example.** Please refer to Fig. 4 for the illustration example. In particular, naive approaches can not distinguish between the direct effect $A\\to B$ and the indirect one $A\\to M\\to B$, due to the latent mediator $M(t_2)$. Our method solves this problem by using $M(t_3)$ as the proxy variable of $M(t_2)$.\n\n**About figures.** For both Fig. 2c and Fig. 3, there is no difference between faded and non-faded arrows/vertices. We will modify these figures as suggested."}]

Author rebuttal:
We would like to express our gratitude to all the reviewers for their efforts and valuable comments. We are particularly pleased to hear that our work addresses an important and challenging problem (3AR7,Y9xG, GTBD, XP2K) and that our method is considered novel, solid (3AR7,Y9xG,7zAn), and well-presented (3AR7,Y9xG, GTBD,7zAn, XP2K).

Regarding the concerns raised, we first would like to emphasize that all our assumptions, including the faithfulness assumption, the SVAR assumption, and the self-causation (also known as autocorrelation) assumption, are commonly made in the literature [13-15, 26-27].

Furthermore, to demonstrate the scalability of our method, we conducted experiments on graphs with varying numbers of nodes $d=\{5,15,25,35,45\}$. The results are presented in Fig. 1 in the supplementary PDF. As shown, our algorithm consistently performs well ($F_1$-score = $\{0.94,0.94,0.93,0.91,0.90\}$) across different scales. These results validate that our method can effectively handle problems of various sizes.

Meta-review: This paper proposed a constraint-based method that can infer the causal structures from subsample time series data without any parametric constraints. Specifically, this method leverages the proxy variable to adjust the bias induced by the hidden variable. The idea is considered novel (reviewers GTBD, XP2k, Y9xG, 3AR7), and the method is sound and solid (reviewers 7zAn, Y9xG, 3AR7).
Reviewers proposed issues about assumption (reviewers XP2k, Y9xG, 7zAn, GTBD), implementation (reviewers XP2k), and experimental results (reviewers GTBD, Y9xG, 7zAn). Fortunately, the authors have addressed the main issues proposed by the reviewers (XP2k, 7zAn, GTBD, 3AR7). The decision is acceptance.
Decision: Accept (poster)