GRACE-C: Generalized Rate Agnostic Causal Estimation via Constraints
Authors: Mohammadsajad Abavisani
David Danks
Sergey Plis
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Causal structure learning
causal learning
graph theory
brain imaging
fMRI

Abstract: Graphical structures estimated by causal learning algorithms from time series data can provide highly misleading causal information if the causal timescale of the generating process fails to match the measurement timescale of the data. Existing algorithms provide limited resources to respond to this challenge, and so researchers must either use models that they know are likely misleading, or else forego causal learning entirely. Existing methods face up-to-four distinct shortfalls, as they might a) require that the difference between causal and measurement timescales is known; b) only handle very small number of random variables when the timescale difference is unknown; c) only apply to pairs of variables (albeit with fewer assumptions about prior knowledge); or d) be unable to find a solution given statistical noise in the data. This paper aims to address these challenges. We present an approach that combines constraint programming with both theoretical insights into the problem structure and prior information about admissible causal interactions to achieve speed up of multiple orders of magnitude. The resulting system scales to significantly larger sets of random variables ($>100$) without knowledge of the timescale difference while maintaining  theoretical guarantees. This method is also robust to edge misidentification and can use parametric connection strengths, while optionally finding the optimal among many possible solutions.

Published as a conference paper at ICLR 2023
GRACE-C: GENERALIZED RATE AGNOSTIC CAUSAL ESTIMA-
TION VIA CONSTRAINTS
Mohammadsajad Abavisani'
David Danks
Department of Electrical and Computer Engineering Georgia Institute of Technology
Halicioglu Data Science Institute and Department of Philosophy
Atlanta, GA 30332
University of California San Diego San Diego, CA 92093 ddanks@ucsd. edu
s. w.aavvisan@@gatedd edu
Sergey M. Plis
TReNDS center
Department of Computer Science
Georgia State University Atlanta, GA 30302 s. wwwppplmallll...mmm. com
ABSTRACT
Graphical structures estimated by causal learning algorithms from time series data can provide misleading causal information the causal timescale of the generating process fails to match the measurement timescale of the data. Existing algorithms provide limited resources to respond to this challenge, and so researchers must either use models that they know likely misleading, or else forego causal learning entirely. Existing methods face up-to-four distinct shortfalls, as they might require that the difference between causal and measurement timescales known; b) only handle very small number of random variables when the timescale difference unknown; e) only apply to pairs of variables; or be unable find a solution given statistical noise in the data. This paper addresses these challenges. Our approach combines constraint programming with both theoretical insights into the problem structure and prior information about admissible causal interactions achieve multiple orders of magnitude in speed-up. The resulting system maintains theoretical guarantees while scaling significantly larger sets random variables (> 100) without knowledge timescale differences. This method also robust edge misidentification and can parametric connection strengths, while optionally finding the optimal solution among many possible ones.
INTRODUCTION
Dynamic causal models play a pivotal role in modeling real-world systems in diverse domains, including economics, education, climatology, and neuroscience. Given sufficiently accurate causal graph over random variables, one predict, explain, and potentially control some system; more generally, one can understand it. In practice, however, specifying or learning an accurate causal model of dynamical system can be challenging for both statistical and theoretical reasons.
One particular challenge arises when data are not measured at the speed of the underlying causal connections. For example, fMRI scanning of the brain indirectly measures dynamical neural activity by measuring the resulting bloodflow and oxygen level changes in different brain regions. However, fMRI measures occur (at most) every second while the brain's actual dynamics are known proceed at faster rate (Oram & Perrett, 1992), though we do not know how much faster. In general, when the measurement timescale is significantly slower than the causal timescale (as with fMRI) learning can output vastly incorrect causal information. For instance, if we only measure every other timestep
CCoresponding author

---

Published as a conference paper at ICLR 2023
in Figure 1, then the true graph (top left) would differ from the data graph (top right). We might thus conclude that variable 2 directly influences variable 5, when variable is the actual direct cause. These errors can lead to inefficient or costly attempts at control. More generally, understanding of system depends on the timescale of the causal relations, not the timescale of measurements.
In this paper, we consider the problem of learning the causal structure at the causal timescale from data collected at an unknown measwrement timescale. This challenge has received significant attention in recent years (Plis et al., 2015b; Gong al., 2015; Hyttinen al., 2017: Plis et al., 20),a), but all current algorithms have significant limitations (see Section 2) that make them unusable for many real-world scientific challenges. Current algorithms show the theoretical possibility of causal learning from undersampled data, but their practical applicability is limited to small graph sizes, perhaps only a pair of variables (Gong et al., 2015). In contrast, we present a provably correct and complete solution that can operate on 100-node graphs, and hence is potentially applicable in biological and other domains, for learning causal timescale structure from undersampled data.
2 RELATED WORK AND NOTATION
A directed dynamic causal model is a generalization of "regular" causal models (Pearl et al., 2000; Spirtes et al., 1993): graph G includes n distinct nodes for random variables V (V1, V2,..., Vnl at both the current timestep / (V'), and also previous timesteps (V"+t) for which there is a direct cause of some V,. We assume that the "true" underlying causal structure is first-order Markov: the independence V TL Vー V holds for all k > 1. G is thus over 2V, and the only permissible edges are V - VI, where possibly i j- The quantitative component of the dynamic causal model is fully specified by parameters for --) We assume that these conditional probabilities are stationary over time, but the marginal P(V') need not be stationary.
Caunal timescale
messurement trnencate
Freskaa graphig ca ammereaaneg Suree
GI
G²
We denote the timepoints of the underlying causal structure as (f" ".,.....,,.... The data are said to be undersampled at rate We denote under- sample rate with superscripts: the true causal graph (i.e., undersampled at rate 1) is G the same graph undersampled at rate u is G". To determine the implied G for u 1, the graph is first "unrolled" by adding instantiations of G' at previous timesteps, where 2r bear the same causal relationships to Vr-1 that V- bear to V", and so forth. In this unrolled (time-indexed by f) graph, all V at intermediate timesteps are unmeasured; this lack of measurement is equivalent to marginalizing out (the variables in) those timesteps to yield G". The problem of moving from G' to G" was structurally addressed by Danks & Plis (2013), and parametrically addressed (for 2-variable systems) by Gong al. (2015).
Figure 1: Causal graph GP and its undersampled version G2: un- rolled and compressed versions.
if measurements occur at (f) "P.,," ,"
...,,"""",,,, "","",..,
Various representations have been developed for graphs with latent confounders, including partially- observed ancestral graphs (PAGs) (Zhang, 2008) and maximal ancestral graphs (MAGs) (Richardson & Spirtes, 2002). However, these graph-types cannot easily capture the types of latents produced by undersampling (Mooij & Claassen, 2020). Instead, we use compressed graphs, along with properties that were previously proven for this representation (Danks & Plis, 2013). A compressed graph includes only V, where temporal information is implicitly encoded in the edges. In particular, a compressed graph G for dynamic causal graph G has V; V, in G iff V - Vř is in G. Undersampling (i.c., marginalizing intermediate timesteps) is a straightforward operation for compressed graphs: length-u directed path from V; to Vj in G' iff there is a directed
(1) V; V, in G" iff there path from Vi-u to VJ in G); and (2) V1 + V, in G" iff there exists length-s s u directed paths from VE to V,, and to Vj. in G¹ (i.e., V& is an unobserved common cause in G fewer than u timesteps back). (See Appendix A for additional lemmas and proofs.) The bottom row of Figure shows compressed graphs for the unrolled ones on the top row; the left shows the causal timescale and the right shows the graphs undersampled at rate 2. (See Appendix B for more examples of graphs through undersampling.)
This assumption is relatively weak, as we do not assume that we measure this causal timescale. The causal timescale could be arbitrarily fast. This assumption is form of causal sufficiency (Spirtes et al., 2000).
2

---

Published as a conference paper at ICLR 2023
derecty 02
Gt demely 0.25
desse ty 0.3
Given this framework, the overall causal learning chal- lenge can now be stated as: given g but not u (alter- nately: given dataset D at unknown undersample rate), what is the set of possible G There will often be many possible G' that appear the same after undersampling. and so we use [[][] to denote the equivalence class of G' that yield ' (the given causal graph inferred from data D) for some u. That is, [H]] = [g 3u(g" = +O).
10
method RASL
SRASL
10
Time to solve (min)
10"
There are 2n possible G'. so perhaps unsurprisingly, the problem of inferring [[+[] is No-complete:
Density of H
10
"yn Ppr Here Lf
Theorem 1 (Hyttinen et al. (2h17) 1l). De- ciding whether consistent G' exists for given H is NP-complete, for all undersampling rates u 2 2.2
10
Nodell gr
Several algorithms exist for this problem. Mesochronal Structure Learning (MSL) (Plis et al.. 2015b) infers [']] in a non-brute force manner given known u. Every edge in G" corresponds to one or more paths of length u in G and so Go can be constructed by identifying intermediate nodes for each edge in G". MSL. uses Depth-Firs Search (DFS) through the state space of possible identifications, where each implies a G If
10
4
2
Undersampling
Figure 2: Comparison of sRASL (red) with pre- vious state-of-the-art RASL (blue).
G" = H, then G [ Otherwise, search continues. MSL backtracks in the DFS whenever some G" includes edge that is absent from H, as the candidate G and all its supergraphs cannot be in [']]].
Although Plis et al. (2015b) showed that the concept of causal inference from undersampled data is feasible, MSL is computationally intractable on even moderate-sized graphs. Hyttinen et al. (2017) used the implied constraints develop Answer Set Programming (ASP) (Simons et al., 2002; Niemelä, 1999; Gelfond & Lifschitz; Lifschitz, 1988) method that formulated this causal inference challenge as rule-based constraint satisfaction problem that is well-suited for ASP-type solvers. In essence, the algorithm in Hyttinen et al. (2017) takes as input the measured causal graph H, determines the set of implied constraints on G', and then uses the general-purpose Answer Set Solver Clingo (Gebser et al., 201 I) to determine the set of possible G significantly faster than MSL. The same idea of using Boolean satisfiability solvers to integrate (in)dependent data constraints has been used for various other causal learning challenges (Hyttinen et al., 2013; Triantafillou et al., 2010).
Although the method in Hyttinen et al. (2017) is significantly faster than MSI., one must specify the undersampling rate (or else run the method sequentially for all possible thereby losing much of the computational advantage). In contrast, the Rate-Agnostic (Causal) Structure Learning (RASL) approach (with several variants) (Plis al., 201 5a) makes no such assumption. RASL algorithms similar to MSL, but consider each possible u for some G.. RASL reduces computational complexity with two additional stopping rules for given G²: (1) if some G has previously been seen, then further undersampling of G' will not produce new graphs; and (2) if G is not edge-subset of H for all k, then do not consider any edge-superset of G (Plis et al., 2015a). Despite these improvements, RASL still faces memory and run-time constraints for even moderate numbers of nodes.
One key observation from all of these learning algorithms is the importance of strongly connected components (SCCs) (Danks & Plis, 2013), where the variables in compressed graph H can be fully partitioned based on SCC membership.
Definition 2.1. An SCC in compressed graph H is a maximal set of nodes S C V such that, for every X, Y S there is a directed path from X to Y.
SCCs can be highly stable despite undersampling: the mode-membershin of an SCC does not change as we undersample, as long as the greatest common divisor (ged) of the set of lengths of all simple loops (directed cycles without repeated nodes) in the SCC is 1.3
Proof provided in Hyttinen et al. (2017). In general, we omit previously published proofs.
"The condition easily holds, as it requires only (1) the graph is relatively dense with different loop lengths, (2) least node in the SCC has self-loop (i.c., autocorrelated).
3

---

Published as a conference paper at ICLR 2023
Theorem 2 (Danks & Plis (2013)[hheorem 3]). S is SCC in G" Yu ged( [s) for SCC S E G'
The algorithms in this paper all take as imput the measurement timescale graph H. perhaps estimated from data at an (unknown) undersampling rate. We do not here develop algorithms to learn H, as there are many existing algorithms for learning graphical structure: at the measurement timescale (Chu et al., 2008; Entner & Hoyer, 2010; Granger, 1969); for time series with latent confounders (Jabbari et al., 2017; Malinsky & Spirtes, 2018; Gerhardus & Runge, 2020); or accounting for structured latents such as those that occur in undersampling (Moneta et al., 2011; Cook et al., 2017).
In this paper, we develop sRASL (for solver-based RASL), a novel solution to the rate-agnostic structure learning problem that leverages multiple types of insights and constraints (e.g., Theorem 2), and thereby significantly outperforms previous methods. The contributions of this paper are threefold: first, we reformulate the RASL algorithm from search-based procedure to a constraint satisfaction problem encoded in a declarative language (Fahland et al., 2009). Second, we show how to add ensure that SRASL provides straight-
additional constraints based on SCC structure. Third, forward way to find approximate solutions when H is an unreachable graph (i.e., when [+] = 0). These advances collectively provide up three orders of magnitude improvements in speed, thereby enabling causal inference given undersampling data involving over 100 nodes. Figure 2 compares sRASL (red) with the previously- fastest RASL (Plis et al., 2015a) method (blue) on the same graphs. For the example H. RASL required nearly 1000 minutes to compute [[]] but only 6 seconds for sRASI.. Even the longest-to-comp [[]]] for sRASI. took 20.5 seconds vs. 780 minutes for RASI..
3 sRASL: OPTIMIZED ASP-BASED CAUSAL DISCOVERY
The sRASI approach takes input (potentially) undersampled graph H. whether learned from data D. expert domain knowledge. both of these, or some other source. sRASL's agnosticism about the source of the input graph enables wider applicability, as we can use whatever information is available (Danks& & Plis, 2019). In the asymptotic (data) limit, the sRASL output is the full [*]].
sRASL leverages the fact that connections between SCCs in H must form a directed acylic graph. More specifically: if X - Y with X E Y. E B for SCCs A # B, then C + D for all C E A, D B. 4 Theorem 2 provides the (weak) condition under which SCC membership is preserved under undersampling. These two observations imply that structural features provide additional constraints beyond the obvious ones (see Section 4.3). In particular, if H has a roughly modular structure, then sRASL generates many more constraints than the formulation of Hyttinen et al. (2017). (See Appendix D for an ablation study of speed effects of these added constraints.)
Listing 1 shows the Clingo (see Appendix F for brief introduction) code of sRASL, which involves exactly representing the conditioning and marginalization operations (from Section 2) in ASP. Line 1 specifies the first-order graph structure of Ht (e.g., the edge 1 - 10 translates to hdirected(1, 10)). Line 2 encodes the second-order structure of H, including the partition of V into SCCs. Separate code adds these predicates and basic descriptive information (Lines 3, 4,5) the Clingo code. maxu on line 3 specifies the maximum undersampling rate; noter that there is provably a where G" = G for all k u, under the same condition that leads to stable SCC membership:
Theorem 3 (Plis et al.
3.1.). ged( Ls) = I for all SCCs S g V, then G" G
for all u f S np + y + d + 1.
where y is the transit number d is graph diameter", and nF is the Frobenius number. 8 In practice, the plausible undersampling rate will often be much lower than the theoretical upper bound in Theorem 3, and maxu could be set by expert knowledge. For example, the underlying rate of brain activity is generally thought to be- ~ 100 milliseconds and fMRI devices measure approximately every two seconds. Hence, "= 20 is plausible upper bound on undersampling in fMRI studies."
*If C < D, then by definition of SCC, there exists X < C mutually reachable, so must be in the same SCC, contra A # B.
Y. X,Y are thus
'The full code is available at https://gitlab..co woomm///drramlingggunfii
'Length of the "longest shortest path" from a node that touches all simple loops of the SCC. graph nodes.
"Length of the "longest shortest path" between any
*For set B of positive integers with ged(B)= = 1, ny is the max integer with my # Ei_, a;B, for a; 2 0
'Of course, the actual undersample rate could be much lower than 20. Voxels typically contain 8 10 layers of neurons, the "causal timescale of voxel" could easily be high 1000 ms (i.e., 2).
4

---

Published as a conference paper at ICLR 2023
%( input graph edge specifications here * e.g.: hdirected(1,5) ...))
%( input graph SCC specifications here e.g.: sccsize(0, 5). scc(1, 0) ...)
#const n 10, maxu = 20
node(1..n).
1 {u((I_mmxu)) 1.
(xdgel(X, (X)e(X), node
dxrected(X, Y, 1) :- (X,el(X, Y)
directed(X, Y, L) :- directed 2, L-1),, (Z, Y), L <= U, u(U).
bidirected(X, Y, U) :- directed(Z, x, L), directed(Z, Y, L), node (X;;)); X <sY,
< U. u(U).
10
directed(X, Y, L), not hdirected(X, Y), node(X; u(L).
11 :- bidirected(X, Y, L), not hbidirected(X, Y), (X)) u(L), < Y.
:- not directed Y, L), hdirected(X, Y), (X;1) u(L). not bidirected Y, L), hbidirected(X, Y), node(X; u(L), X Y. the following is only used when SCC accounting is enabled
15 :- exgel(X, Y), scc(x, K), scc(Y, L), K != L, sccsize(L, 2), Z > 1, not dkg
Listing I: sRASL encoding in the clingo ASP-language
1- directed Y, L), no. no_hdirected(X, Y. W), no:)(X;Y), u(L). [N01, [N01,X,Y] bidirected(X, Y. L), hbidirected(X,, Y. W) (X;Y) u(L), X Y. [W01, [W01,X,Y]
t~ not directed(X, Y, I), hdirected(X, Y, W), (X;))X;)), u(L). [N01,X,
I~ not bidirecteddX, Y, L), hbidirecteddX, Y, W), (X))) u(L), X < (Wa1,X,Y)
Listing Integrity constraints replace Lines 11-14 in Listing to convert sRASL into optimization problem
Line 6 in Listing stipulates that all edges in G are possible (by default), and so the output will contain any possible model that does not violate the integrity constraints of lines 11 15. Lines 7 and 8 define paths of length L in the graph (i.e., an edge in G¹). As described in Section 2,
a path of length u. Line similarly defines bidirected edges in G X = 3N,1: (X dn Z mis G
Y- G" = x - G' where
Lines 10 - 13 provide the core constraints that ensure sRASL returns only G' for which there exists with G" H. Line adds constraint of impermissibility of cycles between SCCs: if each SCC considered super-node, Line 15 ensures that the graph of SCC connections in H is acyclic.
SRASI. can return the empty set (i.e., there are no suitable G¹). typically because of statistical noise or other errors in estimating specifying H. 10 We can instead run sRASL in an optimization mode to find optimal (though not perfect) outputs (see Section 4.5 for details). In such cases, sRASL finds the set of G' that are, for some u, closest to H by the objective function:
G u" E arg min
Σ [[e e G"I w(e H)) + Σ 1le e w(e (( eEH
where the indicator function I(c) if holds and 0 otherwise. w(e E H) indicates the importance (i.c., reliability) edge e; w(e E H() indicates the reliability of the absence an edge. Since H is an undersampled graph, it consists of directed and bidirected edges. We thus implement both w(e E H) and w(e & H) as two pairs of n n matrices, one pair for existence and absence of directed edges, and one pair for bidirected edges. To learn the optimal graph at the true causal timescale, the corresponding G" each G in the solution set is compared H, and penalized for the difference according to the weights.
The reliability weights may also be based on strength of connection. For example, H is estimated Granger Causality Structural Vector Autoregressive (SVAR) (Granger, 1969; Lütkepohl, 2005) model, then the edge-weights may enable Clingo to preferentially ignore edges with weaker
Among all possible graphs that have combination of hoth directed (2*) and bidirected (2G)) edges, only fraction are possible by undersampling a
5

---

Published as a conference paper at ICLR 2023
connection strength. In addition to using observed data to estimate the weights, prior knowledge can play a key role: edges known to exist can be given higher weight, while those known to not exist could be given reduced (or zero) weight (See also Appendix D). The approach is flexible as it can combine estimates from data and expert knowledge. Applications to fMRI data for causal structure discovery at causal time scale shown in Appendix E.
In order to incorporate Equation in Listing 1, we replace its exact integrity constraints (Lines 10 - 13) with the optimization formulation (Gebser al., 2011) in Listing 2. In Listing 2, we specify a weight for each edge (or lack there of) in H using W, with importance specified using W@i syntax with being the importance.
3.1 SRASL COMPLETENESS AND CORRECTNESS
sRASL exhibits significant improvements in computation time, so it is important to show that we do lose generality or theoretical guarantees. We demonstrate correctness and completeness using the notion of direct encoding of the problem (i.e., the space of solutions is fully characterized, and any non-solution violates a constraint). We first prove (see Appendix A):
Theorem 4. Listing is direct encoding of the undersampling problem.
Clingo is a complete solver, based on CDNL (Conflict-Driven Nogood Learning) (Drescher & Walsh, 20.1), itself based on CDCL (Conflict-Driven Clause Learning) (Marques Silva & Sakallah, 1996; Marques-SSaSSS Silva Sakallah, 1999). Hyttinen et al. (2014)[Theorem 2] and Hyttinen et al. (2013)[eection 5.2] show that, if the ASP encoding is the direct encoding of the problem, then ASP will produce the complete set of solutions in the infinite sample space limit. In other words, Theorem 3.1 implies: since our algorithm yields least sound solution, Clingo will produce all possible solutions. Therefore, soundness results in completeness. That is, sRASL's success is not due heuristics or some incomplete not-everywheree-come algorithmic step."
4
RESULTS
A major virtue of sRASL is its empirical performance, (where we have known ground truth) to understand this performance in more detail. These experiments used Clingo in parallel mode using 10 threads computing computational complexity, all experiments were run on a slurm cluster that submits jobs to one of the 19 machines on the same network, each with 64 cores and 512 GB of RAM.
now consider range of simulations
AMD EPYC 7551 CPUs. Given
4.1 COMPARING sRASL RASL
We first compare sRASL with the existing RASL method, which struggles with graphs larger than 6 nodes (Plis al.. 2015a) (Figure 2). We generated 100 6-node SCCs for each density in [0.2. 0.25, 0.3], and then undersampled each graph by 3. and 4. Each column of Figure consists of graphs of approximately same density (increasing density from left-to-right), and subcolumns represent different undersample rates (for that density). As Figure 2 shows, sRASL is typically three orders of magnitude faster than RASI,, even on small graphs. similar comparison with the method of Hyttinen et al. (2017) that iteratively loops through possible values of u can be found in Figure 9 of Appendix C.
COMPARING GRAPH SIZE
It is perhaps unsurprising that sRASL runs much faster than RASL, sRASL uses ASP solver (which were previously known to yield faster algorithms (Hyttinen et al., 2017)). We next explored how large graphs could be that sRASL could handle. More generally, we aimed to better understand how sRASL's computational performance scales with the number of nodes in single-SCC graphs. The focus single SCCs motivated by the theoretical need understand the size-speed tradeoff. Moreover, many real-world systems consist of tightly coupled factors with many feedback loops (i.e., a single SCC). We consider multiple-SCC graphs in the next subsections.
11 Simulation testing provides further evidence. We found that sRASL. and RASI, produced identical outputs for 1000 different input graphs, and RASL. is known be correct and complete (Plis al., 201 20155r/Th 3.6).

---

Published as a conference paper at ICLR 2023
Graphs with 64 nodes but different sizes
nodes
16 nades
32 nodes
SCCs
SCCs
SCCs
10
10
Solved
25
32 50
16 SCCs
99 22
Timed out
Time to solve (min)
Time to solve (min)
10"
24 hours Timeout
d9 3 2000 d 554
Density
Pl
10"
10"
32 SCCs
A49660 40 Brrn
Density P
10
2
40 6/6
10
10'
10"
25
20
75,75 A
25,75 25,75 25.75
2
Undersampling
Undersampling
Figure 4: Time behavior of graphs of size 64 with various SCC sizes. The time-out for this experiment was 24 hours (1440 Minutes).
Figure 3: Time behavior of graphs of size 8, 16, and 32. Red line shows experimental time-out of 24 hours. Green/Gray dots represent input graphs that were/were not solved within the 24-hours window.
We generated 50 random single-SCC graphs each of 8, 16, and 32 nodes, all with average degree of 1.4 outgoing edges per node. We then undersampled each graph by 3. and and used each individual undersampled graph as input to sRASI. (i.e., 150 different input graphs for each size). We used a 24-hour timeout (i.e., stopped the run if did not finish in 24 hours). Figure shows the increasing computational costs both number of nodes and undersample rate increase. Notably, sRASL was able to learn [?]] for many 32-node Single-SCC graphs, though it reached timeout for all 32-node H at 4. That is, for low u, sRASL scales to much larger single-SCC graphs than RASL.
4.3
COMPARING SCC SIZE MULMPPL-SSCE GRAPHS
The other major innovation of sRASL is incorporation of constraints derived from the SCC structure. We thus investigated the performance of sRASL on large, structured, multiple-SCC graphs. Many real-world systems exhibit some degree of modularity, where there are dense or feedback connections within a module or subsystem, and relatively sparser connections between modules or subsystems. In theory. sRASL should perform well on these kinds of structures since it incorporates SCC-based constraints. Please refer to Appendix for an ablation study on the marginal benefit provided by these additional constraints for SCC structures.
We tested the value of SCC-based constraints using graphs with 64 nodes that differed their SCC structure. Specifically, randomly generated 50 graphs each of: 32 size-2 SCCs; 16 size-4 SCCs; 8 size-8 SCCs; size- 16 SCCs; or 2 size-32 SCCs. We then undersampled each graph by и = 2,3, or 4, and ran sRASL (again with 24-hour timeout).
Figure 4 shows the computation time for these graphs, with increasing SCC size (and decreasing number of SCCs) from left to right. The first key observation is that sRASL successfully found [[] for 64-node graphs, at least when there was some internal structure. Second, and relatedly, we observe wide range of computation times for these graphs, even though all had the same number of nodes (64). We clearly see the impact of SCC structure, as sRASL was dramatically faster when there were many small SCCs, rather than few large SCCs. The results in Figure 3 might seem to suggest an "upper bound" around 30 nodes for sRASL. But the results in Figure 4 make it clear that any potential "upper bound" primarily on the number of nodes within the SCCs, rather than the total number of nodes in the graph.
4.4 COMPARING GRAPH SIZE WITH CONSTANT SCC SIZE
The previous results suggest that sRASL might be able to solve much larger graphs, as long as the SCCs are not overly large. More generally, the previous simulations showed that sRASL's computational cost scales (at least) exponentially in the size of the SCC, but did not reveal how scales in the number of SCCs.
7

---

Published as a conference paper at ICLR 2023
Graphs of same SCC size each row with different number of SCCs.
10
1x7=7
2x7=14
4x7=28
6x7=42
8x7=56
10x7=70
12x7=84
14x7=98
10'
10
10
10
Time to solve (min)
10
2x8=16
4x8=32
6x8
8x8-64
12x8-96
Density of
10
10
10
75
25
25
10
1x10=10
2x10=20
2
3
4
10
10
4x10=40
6x10=60
8x10=80
10
20
50
86
2
3
4
2
3
2
3
4
2
3 4
Undersampling
Figure S: Time behaviour of graphs with same SCCs sizes but with multiple number SCCs. Top row: graphs of SCC size 7 with 1.2,.., number SCCs. Middle row: graphs of SCC size Bottom row: graphs of SCC size 10. Bottom-right corner shows an example of structured graph with 98 nodes composed 14 SCCs of size 7. Fach color represents one SCC.
We again generated 50 different graphs for each of several settings. We used SCCs with and 10 nodes, and varied the number of SCCs within graph (again for 2, 3, and 4). Figure shows computational cost sRASL, where each row includes graphs whose SCCs are the same size, and the number of SCCs increases from left- left-to-right. The critical observation here is that the time complexity grows approximately linearly in the number SCCs, rather than exponentially (or worse). For example, the graph shown in Figure 5 has 98 nodes, but SRASL successfully computes [H] in approximately 20 minutes. (Recall that RASL. took 17 hours to compute a graph with only 6 nodes.)
This simulation demonstrates that sRASL is usable relatively large graphs, as long there is appropriate internal structure. One might worry, though, whether real-world systems have the right structure. For fMRI (brain) data, Sanchez-Romero al. (2019) recently aggregated number of simulations realistic causal graphs for brain processes studied with fMRI, and the largest SCC in these aidely-accepted models has only nodes. Moreover, typical brain parcellations contain only 50 100 regions (= nodes), and sRASL can easily handle 100-node graphs if SCCs are 8 - 10 nodes.
The results in this subsection suggest that we could potentially find [[] for even larger graphs (n > 100), as long as they were composed of reasonably-sized SCCs. However, we found that the Clingo language and solver seems be limited in the number of atoms that can handle. In our simulations, graphs of size 100 seem to be the limit for Clingo to handle all the predicates. An open question whether sRASL can be optimized produce fewer predicates (or Clingo improved to handle more atoms).
4.5 OPTIMIZATION
Finally, we explored the optimization capability of Clingo. Recall that sometimes [[] = 0 due to statistical errors or other noise learning H. Clingo can solve an optimization problem based on user-specified weights and priorities, and output single solution with minimum cost function (along with u for this solution). In particular, we can use Clingo to find G' whose G" (for some u) are closest (relative to the edge weights) to H."!
12f [[] then this optimization will simply return single graph from [[[]]
8

---

Published as a conference paper at ICLR 2023
Deg
1.5
Dog 2.0
Deg 2.5
Deg 1.5
Deg 2.0
Deg 2.5
Deg 1.5
Deg 2.0
Deg 2.5
omission
domalized iroo
0.8
0.8
0.4
0.0
1.0
commission
Undersampling
Undersampling
Undersampling
Noraaizzed
0.6
Rate 2
Rate
Rate 4
0.4
6 7
8
9
Graph Size
Graph Size
Graph Size
Figure 6: The omission (top) and commission (hottom) error of different graph sizes and undersampling of two, three and four from left right.
In this simulation, we first randomly generate G' and undersample a random to get G" = H such that ['H] # 0. then assign weights to the edges of H and randomly delete one edge H. run sRASL on this "broken" H to learn suitable G'. Red bars in Figure 6 show the edge omission and commission errors for this approach. We see that, except for high undersamplings, the optimization capability of Cling
be used frequently retrieve the true G that is, this version of sRASI. is robust to small errors in H in many settings.
A more complex approach is to first the optimization method identify solution G and undersample rate Mopr- We can then undersample this solution G by Mope to get G"pr- We then use sRASL obtain [G (i.e., the full equivalence class of the undersampled graph that "nearest" to
H). We then compute the error based on the minimum error among all G' E [[ that is, we ask whether the true graph was found somewhere in [[ This approach is motivated by the intended of sRASL by domain scientists, where they use domain knowledge to help select graph(s) from the equivalence class. Blue bars in Figure 6 show that this more complex method provides improved performance compared regular optimization.
5 CONCLUSION AND DISCUSSION
Real-world scientific problems frequently involve measurement processes that operate a different timescale than the causal structure of the system under study. As causal learning and analysis methods are increasingly used to address societal and policy challenges, it is increasingly critical that we use methods that reveal usable information (while also being clear when we cannot infer some information). Obviously, like any method, sRASL could yield information that is misused, but the aim here is to provide another useful tool in the scientists' and policy-makers toolboxes. If measurements occur at slower rate than the causal influences. then causal discovery from those undersampled data can yield highly misleading outputs. Multiple methods have been developed to infer aspects of the underlying causal structure from the undersampled data/graph. However, the assumptions or computational complexities of those algorithms make them unusable for most real-world challenges. In this paper, we have developed and tested sRASL, a novel approach that is less subject to those same limitations. More specifically, sRASL provides all consistent solutions (without knowledge of exact undersampling rate) for large (100-node) graphs in a usable amount of time. sRASL also shows reasonable robustness statistical error in the estimated graph by finding the closest consistent solution. Future research will focus on application of sRASL to actual neuroimaging data, and extensions to situations with multiple measurement modalities.

---

Published as a conference paper at ICLR 2023
6 ACKNOWLEDGMENTS
This work was supported by NIH RO1MH129047 and in part by NSF 2112455, and NIH 2R01EB006841. We are grateful Antti Hyttinen, Matti Järvisalo, and Frederick Eberhardt for discussions on clingo.
REFERENCES
Tianjiao Chu, Clark Glymour, and Greg Ridgeway. Search for additive nonlinear time series causal models. Journal of Machine Learning Research, 9(5), 2008.
John W Cook, David Danks, and Sergey M Plis. Learning dynamic structure from undersampled data. In Proceedings of the UAI Causality Workshop, 2017.
David Danks and Sergey Plis. Learning causal structure from undersampled time series. In NIPS Workshop on Causality, volume pp. 1-10, 2013.
David Danks and Sergey Plis. Amalgamating evidence of dynamics. Synthese, 196(8):3213-3230, 2019.
Christian Drescher and Toby Walsh. Conffict-driven constraint answer set solving with lazy nogood generation. In Twenty-Fifft Fifth AAAI Conference on Artificial Intelligence, 2011.
Doris Entner and Patrik O Hoyer. On causal discovery from time series data using FCI. Probabilistic graphical models, pp. 121-128, 2010.
Dirk Fahland, Daniel Lübke, Jan Mendling, Hajo Reijers, Barbara Weber, Matthias Weidlich, and Stefan Zugal. Declarative versus imperative process modeling languages: The issue of understand- ability. In Enterprise, Business-Process and Information Systems Modeling, pp. 353-366. Springer, 2009.
Martin Gebser, Benjamin Kaufmann, Roland Kaminski, Max Ostrowski, Torsten Schaub, and Marius Schneider. Potassco: The Potsdam answer set solving collection. Ai Communications, 24(2): 107-124, 2011.
M Gelfond and V Lifschitz. The stable model semantics for logic programming. ICSLP, 1988.
Andreas Gerhardus and Jakob Runge. High-recall causal discovery for autocorrelated time series with latent confounders. Advances in Neural Information Processing Systems, 13:15615-12225,
2020.
Mingming Gong, Kun Zhang, Bernhard Schoelkopf, Dacheng Tao, and Philipp Geiger. Discovering temporal causal relations from subsampled data. In International Conference on Machine Learning, pp. 1189--9966 PMLR, 2015.
Clive WJ Granger. Investigating causal relations by econometric models and cross-spectral methods. Econometrica: journal of the Econometric Society, pp. 424-438, 1969.
Antti Hyttinen, Patrik O Hoyer, Frederick Eberhardt, and Matti Jarvisalo. Discovering cyclic causal models with latent variables: A general baT-baased procedure. arXiv preprint arXiv: arXiv:1309 113300996666 2013.
Antti Hyttinen, Frederick Eberhardt, and Matti Järvisalo. Constraint-based Causal Discovery: Conflict Resolution with Answer Set Programming. In UAI, pp. 340-349, 2014.
Antti Hyttinen, Sergey Plis, Matti Järvisalo, Frederick Eberhardt, and David Danks. constraint optimization approach to causal discovery from subsampled time series data. International Journal of Approximate Reasoning, 90:208 225, 2017.
Fattaneh Jabbari, Joseph Ramsey, Peter Spirtes, and Gregory Cooper. Discovery of causal models that contain latent variables through bayesian scoring of independence constraints. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 142-157. Springer, 2017.
10

---

Published as a conference paper at ICLR 2023
V Lifschitz. The stable model semanties for logic programming, 1988.
Helmut Lütkepohl. New introduction multiple time series analysis. Springer Science & Business Media, 2005.
Daniel Malinsky and Peter Spirtes. Causal structure learning from multivariate time series settings with unmeasured confounding, In Proceedings of 2018 ACM SIGKDD workshop on causal discovery, pp. 23-47. PMLR, 2018.
Joao P Marques-Silve and Karem A Sakallah. GRASP: A search algorithm for propositional satisfiability. IEEE Transactions on Computers, 48(5):506-521, 1999.
J.P. Marques Silva and K.A. Sakallah. GRASP-A new search algorithm satisfiability. In Pro- ceedings of International Conference on Computer Aided Design, pp. 220-227, 1996. doi: 10.1 10.1109/ICCAD. 19966769077.
A. Moneta, N. Chlaß, D. Entner, and Hoyer. Causal search structural vector autoregressive models. In Journal of Machine Learning Research: Workshop and Conference Proceedings. Causality in Time Series (Proc. NIPS2009 Symposimm on Causality in Time Series), volume 12, pp. 95-114 14, 2011.
Joris M Mooij and Tom Claassen. Constraint-based causal discovery using partial ancestral graphs in the presence of cycles. In Conference on Uncertainty in Artificial Intelligence, pp. 1159-1168. PMLR. 2020.
Ilkka Niemelä. Logic programs with stable model semanties as a constraint programming paradigm. Annals of mathematics and Artificial Intelligence, 25(3):241-273, 1999.
MW Oram and DI Perrett. Time course of neural responses discriminating different views of the face and head. Journal of neurophysiology. 68(1):00-84 1992.
Judea Pearl et al. Models, reasoning and inference. Cambridge, UK: CambridgeUnivversiiyyrersss, 19: 2, 2000.
Sergey Plis, David Danks, Cynthia Freeman, and Vince Calhoun. Rate-agnostic (causal) structure learning. In Advances in neural information processing systems, pp. 3303-3311, 2015a.
Sergey Plis, David Danks, and Jianyu Yang. Mesochronal structure learning. In Uncertainty in artificial intelligence: proceedings the... conference. Conference on Uncertainty in Artificial Intelligence, volume 31. NIH Public Access, 2015b.
Thomas Richardson and Peter Spirtes. Ancestral graph Markov models. The Annals of Statistics, 30 (4):962-1030, 2002.
Ruben Sanchez-Roment Joseph Ramsey, Kun Zhang, Madelyn RK Glymour, Biwei Huang, and Clark Glymour. Estimating feedforward and feedback effective connections from fMRI time series: Assessments of statistical methods. Network Neuroscience, 3(2):274-306, 2019.
Patrik Simons, Ilkka Niemelä, and Timo Soininen. Extending and implementing the stable model semantics. Artificial Intelligence, 138(1-2):181-234 2002.
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search. Springer New York, 1993. doi:
URL https://doi. orw.ii.rrg1..... 100. 1007/
378-1-4612-2748-1
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, Prediction, and Search. MIT press, 2000.
Sofia Triantafillou, Joannis Tsamardinos, and Ioannis Tollis. Learning causal structure from over- lapping variable sets. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 860-867. JMLR Workshop and Conference Proceedings, 2010.
Jiji Zhang. Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 9: 1437-1474, 2008.
11

---

Published as a conference paper at ICLR 2023
A APPENDIX
We start with proving some results used in conversion of the DBN structures to their compressed graph representations.
Lemma 1. For all G2 contains no directed edges between variables at the same time step.
Proof. vvu = holds by assumption for G For > I, every directed edge corresponds to a directed path of length in Gj. Since all directed edges in Gi are from / to (or more generally, from / t (k + 1)), every directed path in G is from an earlier time step to the current one. Hence, no directed edge in G2 can be from V to Vi
Lemma If the Markov order of Gj is 1, then the Markov order of all Gu is also 1 (relative to measurement al rale u).
Proof. The Markov order a dynamic causal graph is the smallest m such that V is independent of vi given Vr-1 ..... Vi-mt for all r > m. If the Markov order of G is 1, then all paths from V to V must be blocked by V-1 for r > 1. Since graphical structure is replicated across timesteps, it follows that all paths from V to V must be blocked by Vi-" for is which corresponds to Markov order for measurements at rate u.
Therefore, the Markov order of Gn
The following theorem demonstrates correctness of our ASP algorithm. Theorem 4. Listing is a direct encoding of the undersampling problem.
Proof. We will prove this by contradiction. Let call the undersampled input graph the algorithm H, considering that is the undersampled version of a graph G at rate Mrree By definition, every directed edge H corresponds to a path of length Utree in G Similarly, every bidirected edge in HH corresponds to an unobserved common cause fewer than Upue timesteps back(refer to Section 2 for exact definition). Line 7 11 in Listing considers all such G's without exclusion. Let us call the set all the pairs of graphs and corresponding undersampling rates described by Listing S.
Let us assume there is pair G and ua that is in S but if we undersample G by ua let us call G will not be the same H. If G" has an extra directed(bidirected) edge, this will contradict with line 12(13) of Listing 1. Similarly, H has a directed edge that in not present in G it will contradict with line 14(16). Therefore, Listing I is direct encoding of the undersampling problem.
B EXAMPLES OF CHANGES IN GRAPHS THROUGH UNDERSAMPLING
In this section, we provide additional examples to visualize how graphs will change through under- sampling.
C COMPARING sRASL AND MODIFIED VERSION THE HYTTINEN ET AL. (2017)
As mentioned in Section Hyttinen al. (2017) specifies the undersampling rate u. Therefore. a comparison of their method with ours will not be fair one. However, one can iterate over undersampling rates find all the solution at different undersampling rates. In this section, we compare the performance of this modified version of Hyttinen et al. (2017) to our proposed method. Figure 9 summarizes this experiment. As we can see, proposed method in Hyttinen al. (2017) performs compatibly with our method in small graphs. However, as the graphs grow larger, the advantage our method gains significance. Specifically, Hyttinen et al. (2017) struggles with large graphs and larger undersampling rates. Most of the test cases graphs larger than 30 nodes and undersampling greater than did not complete in the dedicated 24-hour period. While our method was able compute the equivalence class of all the graphs much faster than 24 hours.
12

---

Fulbbaiac
contsspvee a as
ICL. ai paper
2023)
U
U-5
U
-
4
U-3
U-6
U
-
Fagre
7: Essmppgee of a
gerpli 7anole
linee
uz1
U-2
U-3
U-4
U:5
U-8
U
U
8
U
-
9
U
10 =
11 U レー
12 U -
Exaupee Figue 8.
12 gegpli intersmunale
tine. 11
13

---

Published as a conference paper at ICLR 2023
node
rode
node
node
node
node
node
10"
24 houes
10
mruis
2017
10
10
2
3
4
2
3
5
3
5
5
5
4
5
3
4
5
Figure 9: Time behavior of the same set of graphs when solved with our proposed method (blue) and modified version of Hyttinen al. (2017) with iterating over undersampling rates (orange). The time out for this experiment was 24 hours and the numbers orange indicate number examples that was not completed in 24-hour period.
D THE EFFECTS OF ACCOUNTING FOR SCCs IN sRASL
In this section, we show the results of additional experiments on the effects of accounting for strongly connected components (SCCs) when the graph has modular structure (i.e., consists of several interconnected strongly connected components). For this experiment, we generated 50 random graphs sized to with multiple SCCs as described in Table1. Then on the same set of graphs, sRASL once with using our additional constraints for SCC structures and once without accounting for the modular structure. We limited the computational resources available to each run to 24 hours time cutoff with RAM limit of 50 GB. The results presented in Figure 11 show that using additional constraints to account for SCC structure dramatically reduces the time and memory needed compute equivalent classes for undersampled graphs. Furthermore, the difference between time and memory requirements to solve for these graphs with and without constraints for SCCs increases for larger graphs as the computational requirements for the latter grow a much faster pace. This result allows us to handle much larger graphs as shown in Figure 5 of the main paper.
node
11
22
RAM
10
24 hours
10
minutes
10
SCC
False
SCC
False TimeOul
10
SCC
False COM
10
Raye
0.5
0.3 0.5
0.5 0.3
0.3
0.5
0.5 0.3
Dansity
Figure 10: Time behavior of the same set of graphs when solved with and without accounting for additional constraints accounting the SCC structure. While sRASL most the 15-node graphs in 24 hours period without the SCC constraints due to either timeout or Out Of Memory error(OOM), the longest it takes solve a 15-node graph with SCC constraints is 14 seconds. None of the graphs failed to compute the complete equivalence class within the time and memory allocated when solved accounting for the SCC structure.
Table I: Number of SCCs and nodes per SCC of the graphs in the benchmark datasct
Num Nodes
8
9
10
11
12
13
14
15
Num SCCs
3
3
3
SCC Sizes
4,4
3,3,3
3,3,4
3,4,4
4,4,4
4,4.5
4.5.5
5,5,5
14

---

Published as a conference paper at ICLR 2023
1ode +
1
reCE 12
rCCe -
FOCE
10"
50C Floo (crored) NC0 Fakur linokhegee)
167
0.5
0.5 0.5
9.5
0.5 0.5
Decdty
Dendly
Decity
Dendry
Decdty
Dendyy
Figure 11: A knowledge of definite presence of an edge in g' between, for example, nodes 3 and 4, i.c. V, V/+1 can be casily encoded by adding edgel 4) to Listing I. In this experiment, we have added knowledge about a pair of arbitrary selected edges of G' to the problem specification (orange dots) and compared the run time with the ASP specification that does not include this additional information about the solution (blue dots). The time out for the new computation already shown in Figure The speed up with the additional constraints is clearly visible on the plots.
hours and the examples all the same the ones
E sRASL APPLIED TO REAL FMRI DATA
SUB
CA23DG
ERC
CA1
BA35
PHC
BA36
Figure Estimated graph from fMRI data of resting state left hemisphere medial temporal lobe using sRASL after obtaining measurement time scale graph by applying Granger Causality. Regions interest include cornu ammonis (CA1), and dentate gyrus together (CA23DG); entorhinal cortex (ERC); perirhinal cortex divided in Brodmann areas (BA35 and BA36);; and parahippocampal cortex (PHC)..
In order to demonstrate the the application of our method, we used publicly available data from (Sanchez-Romero al., 2019) and applied our method on the resting-state fMRI data. We used the 10 datasets of concatenated recording for 10 individuals, comprising seven regions of interest from medial temporal lobe, each containing 4,210 datapoints.
We first generated estimated graphs H from the fMRI data using Granger Causality (Granger, 1969; Cook et al., 2017). Note that these estimated graphs are at the measurement timescale (they include bidirected edges) and due to statistical and measurment error are often not reachable from any graph at causal time scale G!! Therefore, we apply sRASL optimization on H to get the closest reachable graph causal time scale. Figure shows the result of our estimated graph causal time scale. It is important to note that with empirical data, we do not have fully defined ground truth to assess our findings.
15

---

Published as a conference paper at ICLR 2023
Following our approach on Section 4.5, use the estimated graph Gop in Figure 12 and undersample it by the rate that our sRASL optimization has found, i.e. Hopr to get Gpr- We then use sRASL to obtain Gpr (i.c., the full equivalence class of the undersampled graph that "nearest" to H). In the case of resting state fMRI data from left hemisphere medial temporal lobe, the full equivalence class consists of 23 graphs that are shown in Figure 13, From this class of equally possible underlying causal graphs, psychologists and experts can examine and determine with causal graph is the most reasonable one.
BRIEF INTRODUCTION ON clingo AND ANSWER SET PROGRAMMING (ASP)
clingo (Gebser et al., 2011) combines a grounder gringo and a solver clasp. clingo declarative programming system based on logic programs and their answer sets, used to accelerate solutions of computationally involved combinatorial problems. The grounder converts all parts of cl clingo program to "atoms," (grounds the statements) and the solver finds "stable models." In ASP, the answer set is a model in which all the atoms are derived from the program and each "answer" is a stable model where all the atoms simultancously true.
general clingo program includes three main sections, which we show below using our algorithm as example:
1. Facts: these are the known elements of the problem. For example, the input to Listing 1 is a graph for which we know the edges. A directed edge from node I to node 5 is in H translates to hdirected 5) (line 1) or if node is part of the SCC number 2, we state this fact in clingo by scc (line 2).
2. Rules: much like an if-else statement, a rule in cl clingo consists of a body and a head, formatted as head :- body. If all the literals in the body are true, then the head must also be true. Rules can include variables (starting with capital letters). and they are used to derive new facts after grounding For example:
directed Y, 1) :- edge (X, Y).
means that for any instantiations of the variables X and Y. if we have an edge from X to there is directed path from X to Y of length 1. Before this line, if the model contained the fact edge 1 (2, 3), this line would generate a new fact: directed 3, 1).
Another type of rule the "choice rule" that describes all the possible ways to choose which atoms are included in the model. For example, in line 5 of Listing we used a choice rule to state that the undersampling rate u can anything from to maxu. The cardinality constraint:
(u 20)
will generate 20 different models (they will not all actually be generated they conflict with other predicate in each model, or else it would not be possible). In each of these 20 models, one subset of all possible atoms generated with this choice rule exists (ø, {u(1)}, fu(1), u(2)), example of an unconstrained choice rule is line 6 in Listing 1, where we want to generate one model for each possible way edges can be present in a graph between two nodes X and Y. We can also limit the choice rule. In our problem, only one undersampling rate is present at each solution. We limit the cardinality constraint to have only one member in each model:
An
1 (u(1..20)) 1.
the on the left is the minimum instantiations of this atom in the model and the on the right is the maximum. Therefore, we only generate (?9) 20 models with this rule, namely one for each undersampling rate. Having several choice rules will multiply the number of generated models by each choice rule.
3. Integrity Constraints: if choice rules are to generate new models, integrity constraints are there to remove the wrong models from the answers set. More specifically, an integrity constraint is the form:
:- LO, L1, where literals Lo, L..... cannot be simultancously positive. For example, in line 16 of Listing we have:
(5)
exgel Y), Scc(X, K), Scc(Y, L), K != scesize(L, 2), Z > 1, not dag (K, L).
(6)
16

---

Published as a conference paper at ICLR 2023
Figure Equivalence class (IG", 1) of all possible graphs causal time scale (G's s) that can be undersampled
and reachGr im. Psychologists and experts can examine and determine with causal graph is the most reasonable one
17

---

Published as a conference paper at ICLR 2023
for cases where the graph consists of several SCCs that are connected using DAG. If the SCCs connected by a cyclic directed graph, then the whole graph will become one big Strongly Connected Component. Integrity constraint states that if there is not directed edge from node in SCC K to node in SCC L as part of the initial DAG, there cannot be such edgel (X, y) from node X to node Y, if node X is in SCC K and node Y is in SCC I..
18


Reviews:
[{"review_id": "fpHLxhpX7P2", "reviewer": "Reviewer_yZ3C", "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 work addresses the problem of learning a causal graph, or rather the set of compatible graphs in the equivalence class, from time-series data when facing the challenge of undersampling, that is, when the sampling rate does not match the rate of the data-generating process. It assumes the presence of a compressed graph which can, asymptotically, be learned from time-series data and the objective is to identify all the causal graphs that are compatible with the compressed graph at some sampling rate. Thus, the authors propose an algorithm, sRASL, which reformulates a search-based algorithm, RASL by (Plis et al., 2015), along with additional structural insights into a constraint satisfaction problem. Experimental evaluation shows a clear advantage of the proposed algorithm over the search-based approach.", "summary_of_the_review": "The proposed algorithm provides a clear advantage over previous methods in terms of speed and scalability. This is evident from the experiment though some further expansion of the results would be helpful (comparison to Hyttenin et al. (2017)). However, the method assembles ideas from previous works making the novelty and contribution marginal.", "strength_and_weaknesses": "Strengths: The evaluation of the proposed algorithm shows a significant speedup compared to RASL and thus provides a clear advantage in terms of scalability.\n\nWeaknesses & comments:\n1- Source of undersampled graph H: The authors state the following:\n> sRASL algorithm takes as input a (potentially) undersampled graph H, whether learned from data D, expert domain knowledge, a combination of the two, or some other source.\n\nIt is understandable to make such an assumption whenever there are theoretical guarantees that a compressed graph can be asymptotically learned from data. If such a result is known in the literature, it should be made clear in the text. However, it sounds unlikely that such a structure can be fully learnable as is the case with PAGs (Zhang, 2008).\n\n2- Evaluation: There is no comparison of the performance of sRASL and the work of (Hyttinen et al., 2017). I understand that the latter assumes the undersampling rate is known but a comparison is possible by running \"the method sequentially for all possible u\".\n\n3- Citation confusion: The citations on page 2 regarding the works of MAGs and PAGs are incorrect. The work of (Richardson & Spirtes, 2002) presents the theoretical formulation of ancestral graphs where MAGs are a special case. However, MAGs are not learnable from data. Zhang (2008) builds on this work by Spirtes and others to formulate a complete learning algorithm, the output of which is a PAG. The cited work by Zhang is for inference applied on top of PAGs; a more suitable citation is the one below.\n\nZhang, J. (2008). On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17), 1873-1896.\n\n4- Typos:\n+ p.4, \"As a concreate example of the improvements\": concreate  --> concrete\n+ p.5, \"In order to incorporate Equation 5 in Listing 1\": do you mean Equation 1?\n+ p.6, \"In other words, Theorem 5 implies\": Do you mean Thm. 4? Theorem 5 in the appendix is the exact replica of Theorem 4.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "cRqPu7q5Nqu", "reviewer": "Reviewer_FQ5L", "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": "This paper provides an Answer Set Programming based algorithm for determining a true directed causal structure from an under-sampled version of it.  The original problem is NP-complete, and previous methods have not been successful with even moderate-sized graphs, but the new method (sRASL) can deal with up to 100 nodes.\n", "summary_of_the_review": "UPDATE: Raised score from 5 to 6.\n\n----\n\nI can't give a higher rating than this unless the authors can explain their omission of so much (seemingly) related literature from the paper, and their reasons for only comparing to one (almost a straw-man) method.  If these things can be explained to my satisfaction, then I would be happy to raise my score.\n\n### Minor Comments\n\n1. The comparison at the end of section 2 is slightly unfair, since you take the longest computation from RASL and then give its sRASL counterpart.  You could presumably give the longest computation from sRASL and then say what its RASL counterpart was!\n\n2. Similarly, the comment on page 9 ('except for high undersamplings') sounds wrong, given that you only use a maximum undersampling of 4; this is far lower than the 20 you describe as being likely in fMRI data.\n\n### Typos\n - throughout: many `\\cite` (or `\\citet`) commands should be replaced by `\\citep`.\n - page 1: 'importantly incorrect' - this is a strange choice of phrase.\n - page 2: the references for PAGs and MAGs appear to be the wrong way around.\n - page 4: 'Section4.3' $\\to$ 'Section 4.3'.\n - page 5: 'In order to incorporate Equation 5 in Listing 1': this comment comes out of the blue, and no mention of the equations in Appendix C has previously been made.\n - page 9: 'tool in the scientists’ policy-makers’ toolboxes' - is there a missing word here?\n - pages 10-11: please ensure that your references are consistent and that the capitalization is correct.", "strength_and_weaknesses": "UPDATE: Since the authors have added the references and explained the reasoning behind other choices, I will revise my score upwards.\n\n----\n\nA clear strength is the improvement in the speed of discovering these underlying structures, which is impressive.\n\nThere are several weaknesses, however.  First, a significant part of the literature on causal discovery in time series is entirely omitted.  A short list (I am sure it is not exhaustive) would include Granger (1969), Chu and Glymour (2008), Entner and Hoyer (2010), Malinsky and Spirtes (2018), Jabbari et al. (2017) and Gerhardus and Runge (2020).  I would also expect to see a comparison of the method to at least one other state-of-the-art discovery algorithm, rather than to a worse incarnation of the method in the paper.\n\nSecond, the graph is assumed to be first order Markov without instantaneous effects, and the under-sampling assumed to be at a fixed integer; there is no reason to believe that either of these assumptions will hold in a real problem.  \n\nThird, there is no real data application.  This is not necessarily a problem, but given that the motivation focuses very strongly on fMRI data and the paper claims that this new algorithm ought to be able to handle such data, I was disappointed not to see it applied.\n\n### References\n\nChu, T. and Glymour, C. (2008). Search for Additive Nonlinear Time Series Causal Models. _Journal of Machine Learning Research_, 9:967–991.\n\nEntner, D. and Hoyer, P. (2010). On Causal Discovery from Time Series Data using FCI. In _Proceedings of the 5th\nEuropean Workshop on Probabilistic Graphical Models_, pages 121–128.\n\nGerhardus, A. and Runge, J. High-recall causal discovery for autocorrelated time series with latent confounders. In _Advances in Neural Information Processing Systems_ 33 (2020): 12615-12625.\n\nGranger, C. W. J. (1969). Investigating causal relations by econometric models and\ncross-spectral methods. _Econometrica_, 37:424–438.\n\nJabbari, F., Ramsey, J., Spirtes, P., and Cooper, G. (2017). Discovery of Causal\nModels that Contain Latent Variables Through Bayesian Scoring of Independence Constraints. In\n_Machine Learning and Knowledge Discovery in Databases_, pages 142–157.\n\nMalinsky, D. and Spirtes, P. (2018). Causal Structure Learning from\nMultivariate Time Series in Settings with Unmeasured Confounding. In _Proceedings of 2018 ACM SIGKDD Workshop\non Causal Disocvery_, volume 92, pages 23–47, PMLR.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XBVhnEl24A", "reviewer": "Reviewer_kYJa", "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 new algorithm to solve the problem of recovering, as much as possible, the original graphical causal structure at the causal timescale from the derived graphical structure at a measurement timescale, where measurements are made every u number of time steps for an unknown u. The new algorithm is based on ASP and incorporates some new constraints that were not exploited in previous algorithms. Experiments show that the new algorithm scales much better than the previous methods.   ", "summary_of_the_review": "This is a well written paper presenting an improved method to tackle an interesting problem. The improvement demonstrated by experiments is significant, though more experiments on simulated or real data would probably better vindicate the utility of the method. ", "strength_and_weaknesses": "Strengths:\n\n1. The proposed algorithm addresses a commonly encountered challenge to causal discovery and achieves a very significant speedup in comparison to previous attempts. \n2. The experiments demonstrate some nice properties of the new algorithm.\n3. This paper is well written and relatively easy to follow.  \n \nWeaknesses:\n\n1. There is no experiment with real or even simulated data. I am a little puzzled why no empirical demonstration is attempted on streamlining the proposed algorithm with a causal discovery algorithm applied to data at the measurement time scale.\n2. For the optimization version of the algorithm, it is unclear how the weights should be determined. Are they supposed to be entirely user or expert specified? Or is there a data-driven procedure to assign the weights. Conceivably some causal discovery methods may yield interpretable weights on the inferred edges, but this prospect does not seem to be discussed in the paper.    \n3. It is also unclear to me why no empirical comparison is made to the ASP-based algorithm in Hyttinen et al. (2017). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DrmEbE_uHF", "reviewer": "Reviewer_9RAD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 focused on the causal discovery problem on the dynamic systems. The proposed method focuses on the problem that the measurements timescale and the causal timescale do not match. To solve this problem, this paper proposes Rate-Agnostic Structure Learning, that uses undersamples graph H as input learned from data D, domain knowledge or other sources. The learned graph from first order markov shows effective undersampling rate, from the full space of G1. sRASL proposed in this paper does not suffer from assumptions or computational complexities.", "summary_of_the_review": "In summary, this paper proposes to solve an interesting and challenging problem. The proposed method is sound and valid across different settings of datasets. ", "strength_and_weaknesses": "Strengths:\n1. The study problem in this paper is quite interesting, it focuses on learning causal graph from dynamic systems. This problem is quite challenge when the data are undersampled. \n2. The proposed algorithm has faster performance without asking for specific undersampling rate.\n\nWeaknesses:\n1.  It might be better to compare with more other baselines.\n2.  It might be more clear to show how the graph changes with the time changing.\n\nAdditional questions:\n1.  What is the main difference between sRASL and RASL?\n2.  How would the undersampling rate influences the causal discovery results?", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6Eqrh3Sa7R", "reviewer": "Reviewer_3inH", "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 work studies the problem of learning a causal network from temporal data in the presence of under sampling. In particular, the authors propose a solver based approach for learning a graph from under sampled data, which improves upon prior art significantly in terms of running time. The core of the approach is converting an existing algorithm (RASL) which is score based to a solver based approach.", "summary_of_the_review": "Overall, I think this paper provides a nice extension to the existing literature. The problem of learning from under sampled time series is nearly ubiquitous in practical applications. I found the proposed method to be well reasoned, clearly presented, and to have good justification via empirical evidence. While I would have preferred to see a more thorough analysis of the behavior of the algorithm under misspecification, I consider this to be a nice addition to the literature. ", "strength_and_weaknesses": "Strengths:\n* Compelling task\n* Practical and reasonably scalable approach for learning graphs under under sampling\n* Compelling experimental evidence\n\nWeaknesses:\n* Would be nice to see a more substantive analysis of the behavior of the algorithm when assumptions fail to hold and the algorithm is finding \"close\" solutions\n* Still relatively modest in scale. While 100 nodes is substantially larger than prior art large scale temporal systems can contain substantially more variables. \n* As I mention below, it would be nice to have an algorithmic description of the method in a more common format. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "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: notable-top-25%