A Survey on Causal Discovery Methods for I.I.D. and Time Series Data
Authors: Uzma Hasan
Emam Hossain
Md Osman Gani
Venue: Accepted by TMLR ()

Abstract: The ability to understand causality from data is one of the major milestones of human-level intelligence. Causal Discovery (CD) algorithms can identify the cause-effect relationships among the variables of a system from related observational data with certain assumptions. Over the years, several methods have been developed primarily based on the statistical properties of data to uncover the underlying causal mechanism. In this study, we present an extensive discussion on the methods designed to perform causal discovery from both independent and identically distributed (I.I.D.) data and time series data. For this purpose, we first introduce the common terminologies used in causal discovery literature and then provide a comprehensive discussion of the algorithms designed to identify causal relations in different settings. We further discuss some of the benchmark datasets available for evaluating the algorithmic performance, off-the-shelf tools or software packages to perform causal discovery readily, and the common metrics used to evaluate these methods. We also evaluate some widely used causal discovery algorithms on multiple benchmark datasets and compare their performances. Finally, we conclude by discussing the research challenges and the applications of causal discovery algorithms in multiple areas of interest.

Published in Transactions on Machine Learning Research (09/2023)
A Survey on Causal Discovery Methods for I.I.D. and Time Series Data
Uzma Hasan
Namahasan@uubcc.ce
Causal AI Lab
Department of Information Systems
University of Moryland, Baltimore County Baltimore, MD, USA
Emam Hossain
emamh @umbbc edu
Causal AI Lab
Departmend of Information Systems University of Moryland, Baltimore County Boltimore, MD, USA
Md Osman Gani
mogani@umbc.co edu
Causal Al Lab
Department of Information Systems
University of Moryland, Ballimore Counly Baltimore, MD, USA
Reviewed on OpenReview: https: // openreview. net/ forum? id= ddC
Abstract
The ability understand causality from data one of the major milestones of human-level intelligence. Causal Discovery (CD) algorithms can identify the cause-effect relationships among the variables of system from related observational data with certain assumptions. Over the years, several methods have been developed primarily based on the statistical propertics of data to uncover the underlying causal mechanism. In this study, we present an extensive discussion on the methods designed to perform causal discovery from both independent and identically distributed (T.ID..) data and time series data. For this pur- pose, first introduce the common terminologies used in causal discovery literature and then provide comprehensive discussion of the algorithms designed to identify causal rela- lions in different settings. We further discuss some of the benchmark datasets available for evaluating the algorithmic performance, off-the-shelf tools or software packages to perform causal discovery readily, and the common metrics used to evaluate these methods. We also evaluate some widely used causal discovery algorithms on multiple benchmark datasets and compare their performancos. Finally, we conclude by discussing the research challenges and the applications of causal discovery algorithms multiple arcas of interest.
1 Introduction
The identification of the cause-effect relationships among the variables of system from the corresponding data is called Causal Discovery (CD). A major part of the causal analysis involves unfolding the cause and effect relationships among the entities in complex systems that can help us build better solutions in health care, earth science, politics, business, education, and many other diverse areas (Peyrol (1996), Nogueira et al. (2021)) ). The cousal ezplanations precisely the causal factors obtained from a causal analysis play an important role in dccision-making and policy formulation as well as in foresocing the consoquences of interventions without actually doing them. Causal discovery algorithms enable the discovery of the underlying causal structure given set of observations. The underlying causal structure also known causal graph

---

Published in Transactions on Machine Learning Research (09/2023)
(CG) is representation of the cause-effect relationships between the variables in the data Pearl 2009
Causal graphs represent the causal relationships with directed arrows from the cause to the effect. Discovering the causal relations, and thereby, the estimation of their effects would enable us to understand the underlying data generating mechanism (DGM) better, and take necessary interventional actions. Howover, traditional Artificial Intelligence (AT) applications rely solely on predictive models and often ignore causal knowledge. Systems without the knowledge of causal relationships often cannot make rational and informed decisions (Marwala (2015)). The result may be devastating when correlations are mistaken for causation. Because two variables can be highly correlated, and yet not have any causal influence each other. There may be third variable often called latent confounder or hidden factor that may be causing both of them (see Figure 2 (a)). Thus, embedding the knowledge of causal relationships in black-box Al systems is important to improve their explainability and reliability (Dubois & Prade (2020), Ganguly et. al.] (2023)). )) In multiple fields such as healthcare, politics, economics, climate science, business, and education, the ability to understand causal relations can facilitate the formulation of better policics with a greater understanding of the data.
The standard approach to discover the cause-effect relationships is perform randomized control trials (RCTT) (Sibbald & Roland (1998)). However, RCTs are often infeasible to conduct due to high costs and some ethical reasons (Resnik (2008)). As result, over the last few decades, rescarchers have developed a variety of methods to unravel causal relations from purely observational data (Glymour et al. 2019 Vowels et al. (2021) ). These methods are often based on some assumptions about the data and the underlying mechanism. The outcome of any causal discovery method is a causal graph or a causal adjacency matrix where the cause and effect relations among the entities or variables are represented. The structure of a causal graph is often similar to directed acyelic graph (DAG) where directed edges from one variable to another represent the causc-cffect relationship between them. Figure 2 (b) represents causal graph showing the factors that are responsible for causing Cancer. This type of structural representation of the underlying data-generating mechanism is beneficial for understanding how the system entities interact with each other.
There exists a wide range of approaches for performing causal discovery under different scttings or assump- tions. Some approaches are designed particularly for independent and identicully distribuled (I.I.D.) dala (Spirtes et al. (2000b), Chickering (2002)) i.e. non-temporal data while others are focused on time series data (Runge et al. 2019), Hyvärinen et al. (2010)) temporal data. Since in real-world settings, both types of data are available in different problem domains, it is essential to have approaches to perform causal struc- ture recovery from both of these. Recently, there has been a growing body of research that considers prior knowledge incorporation for recovering the causal relationships (Mooij et al. (2020), Hasan & Gani (2022).
Hasan & Gani (2023)). ). Although there exist some surveys (see Table 1 on causal discovery approaches [Heinze-Demi et al.] (2018), Glymour et al.] (2019), Guo el. al. (2020), Vowels el al. (202T), Assaad et al. (2022b)), none of these present a comprehensive review of the different approaches designed for structure re- covery from both I.ID, and time series data. Also, these surveys do not discuss the approaches that perform causal discovery in the presence of background knowledge. Hence, the goal of this survey is to provide an overview of the wide range of existing approaches for performing causal discovery from I.I.D. as well as time scries data under different settings. Existing surveys lack combined overview of the approaches present for both I.I.D. and time series data. So in this survey, we want to introduce the readers to the methods available in both domains. We discuss prominent methods based on the different approaches such as conditional independence (CT) testing, score function usage, functional causal models (FCMs), continuous optimization strategy, prior knowledge infusion, and miscellaneous ones. These methods primarily differ from each other based on the primary strategy they follow. Apart from introducing the different causal discovery approaches
Data
Causal Graph
Figure 1: Causal Discovery: Identification of a causal graph from data.
2

---

Published in Transactions on Machine Learning Research (09/2023)
Pollution
Smoker
Cancer
s
C
X-ray
Dysponea
(a)
(b)
Figure 2: (a) Latent confounder causes both variables S and C, and the association between S and C' is denoted by which can be mistaken as causation. The graph in (b) is a causal graph depicting the causes and effects of cancer (Korb & Nicholson (2010)).
and algorithms for L.LD. and time series data, we also discuss the different tools, metrics, and benchmark datasots used for performing CD and the challenges and applications of CD in a wide range of areas.
Table 1:
Comparison among the existing surveys for causal discovery approaches. different approaches can be found in section and section
A discussion on the
Survey
Focused Approaches
LLD.D Data
Time Series Data
Heinze- Demnl al. 2018
Constraint, Score, Hybrid & FCM- based approaches.
X
Glymour et al. (2019)
Constraint-based, Score-based, & FCM-bused ap- proaches.
Traditional
x
Guo et (2020)
Constraint- Score-based,
X
FCM-based approaches.
Vowels et al.
(0021)
Continuous Optimization based.
X
Assaad et (002bb)
Constraint-based Score-based based, FCM-based, etc. approaches for time series data. Constraint-based, Score-based, FCM-based, Hybrid-based, Continuous Ootriiitti--tiiiiiiiiiiioooooo based, Booor-Kowleddge--a based, and Mis- cellaneous.
This study
To summarize, the structure of this paper is as follows: First, we provide a brief introduction to the common terminologies the field of causal discovery (section Second, we discuss the wide range of causal discovery approaches that exist for both I.I.D. (soction and timo-scrics data (section 4 Third, we briefly overview the common evaluation metrics (section and dalasets (section 6 used for evaluating the causal discovery approaches, and report the performance comparison of some causal discovery approaches in section Fourth, we list the different technologics and open-source software (section 8 available for performing causal discovery. Pifth, we discuss the challenges (section 9.1 and applications (section 9.2 of causal discovery in multiple areas such as healthcare, business, social science, economics, and so on. Lastly, we conclude by discussing the scopes of improvement future causal discovery research, and the importance of causality in improving the existing predictive AI systems which can thereby impact informed and reliable mecisio in different areas of interest (section 10
2 Preliminaries of Causal Discovery
In this section, we briefly discuss the important terminologies and concepts that are widely used in causal discovery. Some common notations used to explain the terminologies presented in Table 2
3

---

Published in Transactions on Machine Learning Research (09/2023)
Table 2: Common notations.
Notation
Description
G
A graph or DAG or ground-truth graph
G'
An estimated graph
X,Y,
Observational variables
X Y
An unoriented or undirected edge between X and Y
X
directed edge from to where X the cause and Y is the effect
X AY
Absence of an edge or causal link between X and Y
X
2
y
V-structure or Collider where Z is the common child of X and Y
Independence or d-separation
X Z
X is d-separated from Y given Z
2.1 Graphical Models
A graph G = (V, E) consists of a set of vertices (nodes) and a set of edges E where the edges represent the relationships among the vertices. Figure 3 (a) represents a graph G with vertices V = [X, Y, Z] and edges E [ Y), (X, 2), Y), There can be different lypes of edges in graph such as directed edges (-), undirected edges (-), bi-directed edges (++), etc. (Colombo et al. )2012)) A graph that consists of only undirected edges (-) between the nodes which represent their adjacencies is called skeleton graph Sc. This type of graph is also known as an undirected graph (Figure 3 (b)). A graph that has a mixture of different. types of edges is known as a mixed graph MG (Figure 3 (c))- path between two nodes X and Y is a sequence of edges beginning from X and ending at Y. A cycle is a path that begins and ends at the same vertex. graph with no cycle e is called an acyelic graph. And, a directed graph in which the edges have directions (-+) and has no cycle is called directed acyclic graph (DAG). In DAG G, a directed path from X to Y implies that X is ancestor of Y, and Y is descendant of X. The graph G in Figure (a) is DAG as it is acyclic, and consists of directed edges.
X
Y
X
Y
Z
(a)
(b)
(c)
Figure 3: (a) A graph G, (b) its skeleton graph Sa, (c) a mixed graph Mc with directed & undirected edges.
There can be different kinds of DAGs based on the type of edges they contain. A class of DAG known as partially directed acyclic graph (PDAG) contains both directed (-) and undirected (-) edges. The mixed graph of Figure 3 (c) is also a PDAG. A completed PDAG (CPDAG) consists of directed (-) edges that exist in every DAG G having the same conditional dependencies, and undirected (-) edges that are reversible G. An extension of DAGs that retain many of the significant propertics that are associated with DAGs is known as ancestral graphs (AGs). Two different DAGs may lead the same ancestral graph (Richardson & Spirtes (0022])). Often there are hidden confounders and selection biases in real-world data. Ancestral graphs can represent the data-generating mechanisms that may involve latent confounders and/or selection bias, without explicitly modcling the unobserved variables. There exist different types of ancestral graphs. A maximal ancestral graph (MAG) is a mixed graph that can have both directed (+) and bidirectional (++) edges (Richardson & Spirtes (200bb)) A partial ancestral graph (PAG) can have four types of edges such as dirccted (-+), bi-directed (++), partially directed (o-+), and undirected (-) (Spirtes (2001)) That is, edges in a PAG can have three kinds of endpoints: -, o, or >. An ancestral graph
without bi-directed edges (++) is DAG (Triantafillou & Tsamardinos (0066)
4

---

Published in Transactions on Machine Learning Research (09/2023)
2.2 Causal Graphical Models
A causal graphical model (CGM) causal graph (CG) is DAG G that represents joint probability distribution P over set of random variables X X2.., Xa) where P is Markovian with respect to G. In CGM, the nodes represent variables X, and the arrows represent causal relationships between them. The joint distribution can be factorized as follows where pa(a,, G) denotes the parents of x; in G.
d P(x1....... ra) 11 P(ailpa(as, G))
(1)
Causal graphs are often used to study the underlying data-generating mechanism in real-world problems. For any dataset with variables X, causal graphs can encode the canso-effect relationships among the variables using directed edges (+) from cause to the effect. Most of the time causal graphs take the form of a DAG. In Figure (a), X is the cause that effects both Y and Z (i.e. Y X Z). Also, Z is cause of Y (i.e. Z - Y)- The mechanism that enables the estimation of causal graph G from dataset D is called causal discovery (CD) (Figure D The outcome of any causal discovery algorithm is a causal graph G where the directed edges (-+) represent the cause-and-effect relationship between the variables X in D. However, some approaches have different forms of graphs (PDAGs, CPDAGs, ancestral graphs, etc.) as the output causal graph. Table lists the output causal graphs of some common approaches which are discussed in soction 3
Table 3: List of some CD algorithms with their output causal graphs A detailed discussion of the algorithms is section The cells with V represent the type of graph produced by the corresponding algorithm.
Algorithms
DAG
PDAG
CPDAG
MAG
PAG
PC
FCI
RFCI
GES
GTES
MMHC
LINGAM
NOTEARS
GSMAG
2.2.1 Key Structures in Causal Graphs
There are three fundamental building blocks (key structures) commonly observed in the graphical models or causal graphs, namely, Chain, Fork, and Collider. Any graphical model consisting at least three variables composed of these key structures. We discuss these basic building blocks and their implications in dependency relationships below.
Definition 1 (Chain) A chain X - is grophical structure configuration of three variables X, Y, and Z in graph G where X has directed edge to Y and Y has directed edge to Z (see Figure 4 (a)). Here, X causes Y and Y causes Z, and Y is called a mediator.
Definition 2 (Fork) A fork Y + > Z is triple of variables X, Y, and 7 where one variable the common parent of the other two variables. In Figure (b), the triple (X, Y, Z) is a fork where X is common parent of Y and Z.
Definition 3 (Collider /V-structure) A v-structure or collider X + + is a triple of variables X,
Y, and Z where one variable is a common child of the other two variables which are non-adjacend. In Figure 4 (c), the triple (X, Y, Z) is a u-structure where Z is a common child of X and Y, but X and Y are non adj-adjecnnt the graph. Figure A (d) is also a collider with a descendant W.
5

---

Published in Transactions on Machine Learning Research (09/202))
X
X
X
(d) Collider with descendants
(a) Chain
(b) Fork
(c) Collider
Figure 4: Fundamental building blocks in causal graphical models.
2.2.2 Conditional Independence in Causal Graphs
Testing for conditional independence (CI) between the variables one of the most important techniques to find the causal relationships among the variables. Conditional independence between two variables and Y results when they are independent of cach other given third variable Z (i.c. X TL Y Z). In the case of causal discovery, CI testing allows deciding any two variables are causally connected or disconnected. An important criterion for CT testing is the d-separation criterion which is formally defined below.
path in blocked by set of nodes if either Definition 4 (d-separation) Pearl 1988
?. contains a chain of nodes X --Y Y + Z or a fork X - Z such that the middle node Y is in N,
d. p contains collider X + +- Z such that the collision node Y is not in N, and descendant of Y is in N.
If N blocks every path between two nodes, then they d-separated, conditional N, and thus inde- pendent conditional on N.
In d-separation, d stands for directional. The d-separation criterion provides a of rules to check if two variables are independent when conditioned set of variables. The conditioning variable be single variable or set of variables. However, two variables with a directed edge (-) between them are always dependent. The set of testable implications provided by d-separation can be benchmarked with the available data D. If a graph G might have been generated from dataset D, then d-separution tells us which variables in G must be independent conditional on other variables. If every d-separation condition matches a conditional independence in data, then no further lest. can refute the model (Pearl (1988)). If there is least one path between variables that is unblocked, then they are d-connected. If two variables are d- d-connected, then they are most likely dependent (except intransitive cases) (Pearl 1988 The d-scparation conditional independence between the variables in the key structures (Figure building blocks of causal graphs follow some rules which are discussed below:
Conditional Independence in Chains: If there only one unidirectional path between variables X and Z (Figure (a)), and Y is any variable or set of variables that intercept that path, then X and are conditionally independent given Y, i.c. X 1 Z Y.
il. Conditional Independence Forks: a variable is a common cause of variables and Z, and there is only one path between and Z, then Y and Z independent conditional on X (i.e. Y X) (Figure b)).
iii. Conditional Independence in Colliders: and Y (Figure (c)), and there is only one path between X and Y, then X and Y are unconditionally independent (i.e. X Y). But, they become dependent when conditioned on or any descendants of 7 (Figure d)).
variable is the collision node between two variables X

---

Published in Transactions on Machine Learning Research (09/2023)
2.2.3 Markov Equivalence in Causal Graphs
A set of causal graphs having the same set of conditional independencies is known Markov equivalence class (MEC). Two DAGs that are Markov equivalent have the (i) same skeleton (the underlying undirected graph) and (ii) same v-structures (colliders) (Verma & Pearl (2022)). That is, all DAGs in a MEC share the same edges, regardless of the direction of those edges, and the same colliders whose parents are not adjacent. Chain and Fork share the same independencies, hence, they belong to the same MEC (Figure 5
Definition 5 (Markov Blanket) For any variable X, its Markov blanket (MB) is the set of variables such that X is independent of all other variables given MB. The members in the Markow blanket of any variable will include all of ils porents, children, and spouses.
Z
X
Z
x
Two Chains
Fork
Markov Equivalent
Figure 5: Markov Equivalence in Chains and Fork.
Markov equivalence in different types of DAGs may vary. A partial DAG (PDAG) a.k.a an essential graph (Perković al. (2017)) can represent an equivalence class of DAGs. Each equivalent class of DAGs can be uniquely represented by a PDAG. A completed PDAG or CPDAG represents the union (over the set of edges) of Markov equivalent DAGs, and can uniquely represent MEC (Malinsky & Spirtes (016b)). More specifically, in CPDAG, an undirected edge between any two nodes X and Y indicates that some DAG in the equivalence class contains the edge X-> and some DAG may contain -- Figure G shows CPDAG and the DAGs (G and H) belonging to an equivalence class.
Markov equivalence in the case of ancestral graphs works as follows. A marimol ancestral groph (MAG) represents DAG where all hidden variables marginalized out and preserves all conditional independence relations among the variables that are true in the underlying DAG. That is, MAGs model causality and conditional independencies in causally insufficient systems (Triantafillou & Tsamardinos (0016)) Partial ancestral graphs (PAGs) represent an equivalence class of MAGs where all common edge marks shared by all members in the class are displayed, and also, circles for those marks that are uncommon are presented. PAGs represent of the observed d-separation relations in a DAG. Different PAGs that represent distinct equivalence classes of MAGs involve different sets of conditional independence constraints. An MEC of MAGs can be represented by PAG (Malinsky & Spirtes (2016b)).
X
Y
X
Z
W
2
W
CPDAG G &H
DAG G
DAG H
Figure 6: DAGs G and H belong to the same MEC. The leftmost graph is CPDAG of G and H with undirocted edge (-) between X and Z, and the rest of the edges same in G and H.

---

Published in Transactions on Machine Learning Research (09/2023)
2.3
Structural Causal Models
Pearl (2009) defined class of models for formalizing structural knowledge about the dala- process known as the structural causol models (SCMs). The SCMs are valuable tools for reasoning and decision- making in causal analysis since they are capable of representing the undorlying causal story of data (Kaddour
ct al. 2022
Definition 6 (Structural Causal Model) (U,,FF where
Pearl 2009
A structural causal model is a 4-tuple M
i. U is set of background variables (also colled erogenous) that are determined by factors oulside the model.
i. V is a set (V1, V2...., Vnd of endogenous variables that are determined by variables in the model, viz. variables in U.V.
M.. F is a of functions {f1,
such that each fi is mapping from the respective domains of U, PA; to Vi and the entire set F forms mapping from U to V. In other words, each Si assigns value to the corresponding V; E V, U2 fi(pa, u.), for 1,2....1.
êc. P(u) is probability function defined over the domain of U.
Each SCM M is associated with a causal graphical model G that a DAG, and a set functions fa Causation SCMs can be interpreted as follows: a variable Y is directly caused by X if X in the function f Y. In other words, each fs assigns value the corresponding V; V, 2/2 + fl(p,, uz), for i 1.2..... n. In the SCM of Figure 7 X is direct cause of Y as X appears in the function that assigns Y's value. That is, if a variable Y is the child of another variable X, then X is direct cause of Y. In Figure 7 Ux, Uy and Uz are the exogenous variables; X, Y and Z are the endogenous variables, and fx, fy & fz are the functions that assign values to the variables in the system. Any variable is an erogenous variable if (i) it is an unobserved or unmeasured variable and (tt) it cannot be a descendant of any other variables. Every endogenous variable is a descendant of at least one exogenous variable.
U x
Uy
X
Uz
X fUx Y - fx( Uy)
Z - fz(,
Y
Z
Causal Graph G
Set of functions f
Figure 7: A Structural Causal Model (SCM) with causal graph G and functions fx, fr and fz which denotes how the variables X, Y, and Z are generated respectively.
2.4 Causal Assumptions
Often, the available data provide only partial information about the underlying causal story. Hence, is essential to make some assumplionss ions about the world for performing causal discovery (Lee & Honavar (2020) ). Following are the common assumptions usually made by causal discovery algorithms.
i. Causal Markov Condition (CMC): The causal Markov assumption states that a variable X is inde- pendent every other variable (except its descendants) conditional on all of its direct causes (Scheines) (1997)). That is, the CMC requires that every variable in the causal graph independent of its non- descendants conditional on its parents (Malinsky & Spirtes (2016a)). In Figure g W is the only descen- dant of X. As per the CMC, X is independent of Z conditioned its parent. Y (X ll Z Y)-
8

---

Published in Transactions on Machine Learning Research (09/202))
W
Y
Z
Figure 8: Illustration of the causal Markov condition (CMC) among four variables.
ii. Causal Faithfulness Condition (CFC): The faithfulness assumption states that except for the variables that are d-separated in DAG, all other variables are dependent. More specifically, for set of variables V whose causal structure is represented by DAG G, no conditional independence holds unless entailed by the causal Markov condition (Ramsey et al. (2012)). That is, the CFC a.k.a the Stability condition is a converse principle of the CMC. CFC can be also explained in terms of d-separation as follows: For every three disjoint sets of variables X, Y, and Z, X and are not. d-separated by 7 in the causal DAG, then X and Y are not independent conditioned on Z (Ramsey al. (2012)): The laithfulness assumption may fail in certain scenarios. For example, it fails whenever there exist. two paths with equal and opposite effects between variables. It also fails in systems with deterministic relationships among variables, and also, when there is failure of transitivity along a single path (Weinberger (2018)
iii. Causal Sufficiency: The causal sufficiency assumption states that there exist la- tent/hidee hott/hidde/// htwhh//dd/oooeeeeeeeeeeeee unobserved confounders, and all the common causes are measured. Thus, the assumption of causal sufficiency is satisfied only when all the common causes of the measured variables are measured. This is a strong assumption as it restricts the search space of all possible DAGs that may be inferred. However, real-world datasets may have hidden confounders which might frequently cause the assumption to be violated such scenarios. Algorithms that violate the causal sufficiency assumption may observe degradation in their performance. The causal insufficiency in well-orrld datasets may be overcome by leveraging domain knowledge in the discovery pipeline. The CMC tends to fail for a causally insufficient set of variables.
iv. Acyclicity: is the most common assumption which states that there are no cycles in a cousal graph. That is, graph needs to be acyelic in order to be causal graph. As per the acyclicity condition, there be directed paths starting from node and ending back to itself. This resembles the structure of directed acyelic graph (DAG). A recent approach (Zheng et al. (2018)) has formulated new function (Equation 2 to enforce the acyclicity constraint during causal discovery in continuous optimization settings. The weighted adjaceney matrix W in Equation 2 is DAG if satisfies the following condition where o is the Hadamard product, WoW is the matrix exponential of W W, and is the total number of vertices.
h(W) toWe d
(2)
v. Data Assumptions: There can be different types of assumptions about the data. Data may have linear nonlinear dependencies and can be continuously valued discrete valued in nature. Data can be independent and identically distributed (L..D.) or the data distribution may shift with time (c.g. time-series data). Also, the data may belong to different noise distributions such as Gaussian, Gumbel, or Exponential noise. Occasionally, some other data assumptions such as the existence of selection bias, missing variables, hidden confounders, etc. are found. However, in this survey, we do not focus much on the methods with these assumptions.
3 Causal Discovery Algorithms for I.I.D. Data
Causal graphs are essential as they represent the underlying causal story embedded in the data. There are two very common approaches to recovering the causal structure from observational data, i) Constraint- based (Spirtes et al. (2000b), Spirtes (2001), Colombo et al. (201)) and ti Score-based (Chickering 2002
Among the other types of approaches, functional causal models (FCMs)-bused (Shimizu et al. (2006) Hoyer
et al. (2008) approaches and hybrid approaches (Tamardiinss al. (2006) are noteworthy Recently, some gradient-based approaches have been proposed based neural networks (Abiodun et al. 2018 and
9

---

Published in Transactions on Machine Learning Research (09/2023)
Causal Discovery Algorithms (for LLD. data)
Contraint-based
Score-based
FCM-based
Gradient-based
Miscellancous
PC 3.1.
GES
3.2.1
LiNGAM 3.3.1
NOTEARS 3.4.1
FRITL 3.5.2
FCI
FGS 3.2.2
ANM 3.3.2
GraN-DAGo
3.4.2
HCM 3.5.3
Anytime FCT 3.1.3
SGES
3.2.3
PNL
GAE 3.4.3
ETIO 335.6
RFCI 331.4
RL-BIC
Direct 3.3.5
(3..44
DAG-GNT NNGGGNN 034.44
JCI
3.5.8
FCI with TBK 3.1.50
A-star search 3.2.5
GOLEM 3.4.5
Kg2Caussl
3.5.9
PC-stable 3.1.6
Triplet A-star
3.2.6
CGNN 3.3.6
DAG-NoCurs
334.6
Meta-RL. 3.5.11
PKCL"
3.1.7
KCRI. 3.2.7
CAM
3.3.7
ENCO 3.4.7
LFCM 3.5.13
Figure Taxonomy of some causal discovery approaches for LLD.. data. The approaches are classified based on their core contribution or the primary strategy they adopt for causal structure recovery. The ap- proaches that leverage prior knowledge are marked by symbol. Some of the gradient-based optimization approaches that use score function are indicated by symbol. They are primarily classified as gradient- based methods because of the use of gradient descent for optimization. However, they can be a score-based method too as they compute data likelihood scores on the way.
a modified definition (Equation 2) of the acyclicity constraint (Zheng et al. 2018 Yu et al 2019 Other approaches include the ones that prioritize the use of background knowledge and provides ways to incorporate prior knowledge and experts' opinion into the scarch process (Wang al. (2020): Sinha Ramsey (2021) In this section, we provide an overview of the causal discovery algorithms for L.I.. data based the different types of approaches mentioned above. The algorithms primarily distinguish from each other based the core approach they follow to perform causal discovery. We further discuss noteworthy similar approaches specialized for non-I.I.D. or time series data in section
3.1 Constraint-based
Testing for conditional independence (CT) is core objective of constraint- causal discovery approaches. Conditional independence tests can be used to recover the causal skeleton if the probability distribution of the observed data is faithful to the underlying causal graph (Marx & Vreeken (2019)). ). Thus, constraint-
based approaches conduct C1 tests between the variables to check for the presence or absence of edges. These approaches infer the conditional independencics within the data using the d-separation criterion to scarch for a DAG that entails these independencies, and detect. which variables are d-separated and which are d-connected Triantaffilou & Tsamardinos (2016)). X is conditionally independent of Z given Y Le. X Tl Z Y in Figure 10 (a) and in Figure 10 (b), X and Z are independent, but are not conditionally independent given Y. Table lists different types of CI tests used by constraint-based causal discovery approaches.
Z
X
Y
(a)
(b)
Figure 10: (a) X 1L Z Y and (b) X and Z are not conditionally independent given Y.
10

---

Published in Transactions on Machine Learning Research (09/2023)
Table 4: Types of conditional independence (CT) tests. Please refer to the study Runge 2018 for a detailed discussion on CI tests.
Conditional Independence Test
Ref.
Conditional Distance Correlation (CDC) test
Wang al.
20155)
2.
Momentary Conditional Independence (MCI)
Runge et al.
2019
3.
Kernel-based CI Lest (KCTT)
Zhang et al
2012
4.
Randomized Conditional Correlation Test (RCoT)
Strobl et
(2019)
5.
Generative Conditional Independence Test (GCIT)
Bellot & van der Schaar
20199
6.
Model-Powered CI test.
Sen et al. 2017
Randomized Conditional Independence Test (RCIT)
Strobl et a.
20199
8.
Kernel Conditional Independence Permutation Test
Doran et a 2014
9.
Gaussian Processes and Distance Correlation-basse (GPDC)
Rasmussen et al (0006
10.
Conditional mutual information estimated with a k-nearest
Runge 2018
neighbor estimator (CMIKnn)
3.1.1 PC
The Peter-Clark (PC) algorithm (Spirtes al. (2000b)) one of the oldest constraint-basee algorithms for causal discovery. To learn the underlying causal structure, this approach depends largely on conditional independence (CI) tests. This is because it is based the concept that two statistically independent variables are not causally linked. The outcome of PC algorithm is a CPDAG. It learns the CPDAG of the underlying DAG in three steps: Step 1 Skeleton identification, Step 2 V-structures determination, and Step 3 Edge orienlations. It starts with a fully connected undirected graph using every variable in the dataset, then eliminates the unconditionally and conditionally independent edges (skeleton detection), then finds and orients the v-structures colliders (i.c. X Y + Z) based on the d-scparation set of node pairs, and finally orients the remaining edges based on two aspects: i) availability of no new v-structures, and ii) not allowing any cycle formation. The assumptions made by the PC algorithm include acyclicity, causal faithfulness, and causal sufficiency. It is computationally more feasible for sparse graphs An implementation of this algorithm can be found in the CDT repository also, in the gCastle toolbox (Zhang et al. (2021a))- A number of the constraint-baset approaches namely FCI, RFCI, PCMCI, PC-stable, etc. use the PC algorithm as a backbone to perform the CI tests.
http//eeeeenAII///m causall wwwccddrrsstooooooooooo toolbox and
x
W
W
Z
W
Z
Complete graph
Skeleton identification
V-structures identification
Orientation of the remaining edges
Figure 11:
Step-by workflow of the PC (Spirtes et al. 2000b)) algorithm.
3.1.2 FCI
The Fast Causal Inference (FCI) algorithm (Spirtes al. (2000a)) is variant of the PC algorithm that infer conditional independencies and learn causal relations in the presence of many arbitrary latent and selection variables. As result, it is accurate in the large sample limit with a high probability even when there exists hidden variables, and selection bias (Berk) (188))) The first step of the FCI algorithm is similar to the PC algorithm where it starts with a complete undirected graph to perform the skeleton determination. After that, requires additional tests learn the correct skeleton and has additional orientation rules. In the worst case, the number of conditional independence tests performed by the algorithm grows exponentially with the number of variables in the dataset. This can affect both the speed and the accuracy of the algorithm in the
11

---

Published in Transactions on Machine Learning Research (09/2023)
case of small data samples. To improve the algorithm, particularly in terms of speed, there exist different variants such as the RFCT (Colombo et al. (2012) ) and the Anytime FCT (Spirtes (2001) algorithms.
3.1.3 Anytime FCI
Anytime FCI Spirtes 2001 is a modified and faster version of the FCI (Sirtts et al. (2000a)) algorithm. The number of CI tests required by FCI makes it infeasible if the model has a large number of variables. Moreover, when the FCT requires independence tests conditional on a large set of variables, the accuracy de- creases for a small sample size. The outer loop of the FC1 algorithm performs independence tests conditional the increasing size of variables. In the anytime FCI algorithm, the authors showed that this outer loop can be stopped anytime during the execution for any smaller variable size. As the number of variables in the conditional set reduces, anytime FCI becomes much faster for the large sample size. More importantly, it is also more reliable on limited samples since the statistical tests with the lowest power are discarded. To support the claim, the authors provided proof for the change in FCI that guarantees good results despite the interruption. The result of the interrupted anytime FCI algorithm is still valid, but as it cannot provide answers to most questions, the results could be less informative compared to the situation if it was allowod to run uninterrupted.
3.1.4 RFCI
Really Fast Causal Inference (RFCI) (Colombo et al. (012 is much faster variant of the traditional FCI for learning PAGs that uses fewer CI tests than FCI. Unlike FCI, RFCI assumes that causal sufficiency holds. To ensure soundness, RFCT performs some additional lests before orienting v-structures and discriminating paths. It conditions only on subsets of the adjacency sets and unlike FCI, avoids the CT tests given subsets of possible d-separation sets which can become very large even for sparse graphs. As a result, the number of these additional tests and the size of their conditioning sets are small for sparse graphs which makes RFCI much faster and computationally feasible than FCT for high-dimensional sparse graphs. Also, the lower computational complexity of RFCI leads to high-dimensional consistency results under weaker conditions than FCI.
3.1.5 FCI with Tiered Background Knowledge
Andrews et al. (2020) show that the Fast Causal Inference (FCT) algorithm (Spirtes et al. (2000a) is sound and complete with ticred background knowledge (TBK). By tiered background knowledge, it means any knowledge where the variables may be partitioned into two or more mutually exclusive and exhaustive subsets among which there is a known causal order. Tiered background knowledge may arise in many different situations, including but not limited to instrumental variables, data from multiple contexts and interventions, and temporal data with contemporaneous confounding. The proof that FCI is complete with TBK suggests that the algorithm is able to find all of the causal relationships that are identifiable from tiered background knowledge and observational data under the typical assumptions.
3.1.6 PC-stable
The independence tests in the original PC method are prone to errois in the presence of a few samples, Additionally, because the graph is updated dynamically, maintaining or deleting an edge incorrectly will affect the neighboring sets of other nodes. As result, the sequence in which the CI tests are run will affect the output graph. Despite the fact that this order dependency is not significant issue in -iv-eiieniional situations, it is severe problem in high-dimensional settings. To solve this problem, Colombo et al. (2014) suggested changing the original PC technique to produce a stable output skeleton that is independent of the input dataset's variable ordering. This approach, known as the stable-PC algorit queries and maintains the neighbor (adjacent) sets of every node at each distinct level. Since the conditioning sets the other nodes are unaffocted by an edge deletion at one level, the outcome independent of the variable ordering. They demonstrated that this updated version greatly outperforms the original algorithm in high-dimensional settings while maintaining the original algorithms' low-dimensional settings performance. However, this
12

---

Published in Transactions on Machine Learning Research (09/2023)
modification lengthens the algorithm's runtime even more by requiring additional CI checks to be done each level. The R-package poalg contains the source code for PC-stable.
3.1.7 PKCL
Wang et al. (2020) proposed an algorithm, Prior-Know hhoo--nnolllggeddivenn Local Causal Structure Learning (PKCL), to discover the underlying causal mechanism belween bone mineral densily (BMD) and its factors from clinical data. It first discovers the neighbors of the target variables and then detects the MaskingPOs to eliminate their effect. After that, it finds the spouse of target variables utilizing the neighbors set. This way the skeleton of the causal network is constructed. In the global stage, PKCL leverages the Markov blanket (MB) sets learned the local stage to learn the global causal structure in which prior knowledge is incorporated to guide the global learning phase. Specifically, it learns the causal direction between feature variables and larget variables by combining the constraint-based and score-based structure search methods. Also, in the learning phase, it automatically adds casual direction according to the available prior knowledge.
3.2 Score-based
Score-based causal discovery algorithms search over the space of all possible DAGs to find the graph that best explains the data. Typically, any acore-based approach has two main components: (i) a search strategy to explore the possible search states space of candidate graphs G', and (ûi) a score function to assess the candidate causal graphs. The search strategy along with a score function helps to optimize the search over the space of all possible DAGs. More specifically, a score function S(G', D) maps causal graphs G' to a numerical score, based on how well G' fits a given dataset A commonly used score function to select causal models the Bayesian Information Criterion (BIC) (Schwarz (978a)) which defined below:
S(G', (D',D)= -2log L(G', D} + klog where n is the number of samples in D, the dimension of G' and L is the likelihood function associated with the candidate graph G'. The lower the BIC score, the better the model. BDeu, BGe, MDL, etc. (listed in Table 5) are some of the other commonly used score functions. These objective functions are optimized through a heuristic search for model selection. After evaluating the quality of the candidale causal graphs using the score function, the rcore-based methods output one or more causal graphs that achieve the highest score (Huang et al. (2018b)). ). We discuss some of the well-known approaches this category below.
(3)
Score-based CD
Search Strategy (Greedy, A*, RL, etc.)
Score Function (BIC, BDeu, MDL, etc.)
Figure 12: General components of score-basod causal discovery approach.
3.2.1 GES
Greedy Equivalence Search (GES) (Chickering (0022 is one of the oldest score- based causal discovery algorithms that perform greedy search over the space of equivalence classes of DAGs. Each search state is represented by CPDAG where some insert and delete operators allow for single-edge additions and deletions respectively. Primarily GES works in two phases: i) Forwards Equivalence Search (FES), and ii) Backward Equivalence Search (BES). In the first phase, FES starts with an empty CPDAG (no-edge model), and greedily adds edges by taking into account every single-edge addition that could be performed to every DAG in the current equivalence class. After an edge modification done to the current CPDAG, score function is used to score the model. If the new score is better than the current score, only then the
13

---

Published in Transactions on Machine Learning Research (09/2023)
modification is allowed. When the forward phase reaches local maximum, the second phase, BES starts where at each step, it takes into account all single-edge deletions that might be allowed for all DAGs in the current equivalence class. The algorithm terminates once the local maximum is found in the second phase. Implementation GES is available at the following Python packages: Causal Discovery Toolbox or CDT (Kalainathan Goudet (2019) and gCastle (Zhang et al. (2021a)). GES assumes that the score function is decomposable and can be expressed as a sum of the scores of individual nodes and their parents. A summary workflow of GES is shown in Figure 13
Series of single-edge additions
Series of single-edge deletions
No-edge model
FES local
BES local maximum
maximum
Start
End
Figure 13: Different stages in the GES algorithm.
3.2.2 FGS
Fast Greedy Search (FGS) Ramsey 2015 is another score-based method that is optimized version of the GES algorithm Chickering [2002]). This optimized algorithm is based on the faithfulness assumption and uses an alternative method to reduce scoring redundancy. An ascending list L is introduced which stores the score difference of arrows. After making a thorough search, the first edge c.g. X + is inserted into the graph and the graph pattern reverted. For variables that are adjacent to or Y with positive score differences, new edges are added L. This process in the forward phase repeats until the L becomes empty. Then the reverse phase starts, filling the list L and continuing until L is empty. This study considered the experiment where GES able to search over 1000 samples with 50,000 variables in 13 minutes using 4-core processor and 16GB RAM computer. Following the new scoring method, FGS was able to complete the task with 1000 samples on 1,000,000 variables for sparse models in 18 hours using a supercomputer having 40 processors and 384GB RAM at the Pittsburgh Supercomputing Center. The code for FGS is available on GitHub as a part of the Tetrad project:
com/ cmi-phil/tetrad
3.2.3 SGES
Selective Greedy Equivalence Search (SGES) (Chickering & Moek (2015) is another score-based causal dis- covery algorithm that is restrictive variant of the GES algorithm Chickering (2022). By assuming perfect generative distribution, SGES provides a polynomial performance guarantee yet maintains the asympiotic accuracy of GES. While doing this, it is possible to keep the algorithm's 's large sample guarantees by ignoring all but a small fraction of the backward search operators that GES considered. In the forward phase, SGES uses polynomial number of insert operation calls to the score fuucciion. In the backward phase, it consists of only a subset of delete operators of GES which include, consistent operators to preserve GES's consistency over large samples. The authors demonstrated that, for given set of graph-theoretic complexity features,
Table 5: Some commonly used score functions for causal discovery. Please refer to the study Huang et al. (018a) for a detailed discussion of the score functions.
Score Function/ Crrtterion
Ref.
Minimum description length (MDL)
Schwarz
1978h
Bayesian information criterion (BIC)
Schwarz
1978a
Akaike information criterion (AIC)
Akaike
(1988
Bayesian Dirichlet equivalence score (BDeU)
Buntine
[199T
Bayesian metric for Gaussian networks (BGe)
Geiger
Heckerman
1994
Factorized normalized maximum likelihood (fNML)
Silander et al.
2008
14

---

Published in Transactions on Machine Learning Research (09/2023)
such maximum-clique size, the maximum number of parents, and v-width, the number of score assessments by SGES can be polynomial in the number of nodes and exponential in these complexity measurements.
3.2.4 RL-BIC
RI-BIC a score-based approach that. uses Reinforcement Leurning (RL) and BIC score search for the DAG with the best reward (Zhu et al. (2019)). For data-to-graph conversion, it uses an encoder-decoder architecture that takes observational data as input and generates graph adjacency matrices that used to compute rewards. The reward incorporates BIC score function and two penalty terms for enforcing acyclicity. The actor-crilic RL algorithm is used as a search strategy and the final output is the causal graph that achieves the best reward among all the generated graphs. The approach is applicable to small and medium graphs of up to 30 nodes. However, dealing with large and very large graphs is still a challenge for it. This study mentions that their future work involves developing more efficient and effective score function since computing scores much more time consuming than training N.Ns. The original implementation of the approach is available at: https: https://gi //tp:////ttbb...//
Critic
Feedback of rewards
Encoder
Decoder
Score Computation
Encodes
Adjacency matrix of graphs
Data
Actor
Figure 14: Components of the RL-BIC Zhu et al. 2019 approach.
3.2.5 A search
Xiang & Kim 2013) proposed one-stage method for learning sparse network structures with continuous variables using the A search algorithm with lasso in its scoring system. This method increased the compu- tational effectiveness of popular exact methods based on dynamic programming. The study demonstrated how the proposed approach achieved comparable or better accuracy with significantly faster computation time when compared to two-stage approaches, including L.MB and SBN. Along with that, a heuristic ap- proach was added that increased A* lasso's effectiveness while msintaining the accuracy of the outcomes. In high-dimensional spaces, this is promising approach for learning sparse Bayesian networks.
3.2.6 Triplet A#
Lu et al. (2021) uses the A exhaustive search (Yuan & Malone 20133 combined with an optimal BIC score that requires milder assumptions on data than conventional CD approaches to guarantee its asymptotic correctness. The optimal BIC score combined with the exhaustive search finds the MEC of the true DAG if and only if the DAG satisfies the optimal BIC Condition. To gain scalability, they also developed approximation algorithm for complex large systems based on the A* method. This extended approach is named Triplet A which can scale up to more than 60 variables. This extended method is rather general and can be used to scale up other exhaustive scarch approaches as well. Triplet A can particularly handle lincar Gaussian and non-Gaussian networks. It works in the following way. Initially, it makes a guess about the parents and children of each variable. Then for each variable and its neighbors (Y, Z), it forms a cluster consisting of X,Y Y, Z with their direct neighbors and runs an exhaustive search on cach cluster. Lastly, it combines the results from all clusters. The study shows that empirically Triplet A outperforms GES for large dense networks.
15

---

Published in Transactions on Machine Learning Research (09/2023)
3.2.7 KCRL
Prior Knowledge-based Causal Discovery Framework with Reinforcement Learning a.k.a. KCRL Hasan &
Gani ) is a framework for causal discovery that utilizes prior knowledge as constraints and penalizes the search process for violation of these constraints. This utilization of background knowledge significantly improves performance by reducing the search space, and also, enabling a laster convergence to the optimal causal structure. KCRL leverages reinforcement learning (RL) as the search strategy where the RL agent is penalized each time for the violation of any imposed knowledge constraints. In the KCRL framework (Figure 15p, at first, the observational data is fed to an RL agent. Here, data-to-adjacene matrix conversion is done using an encoder-decoder architecture which is part of the RL agent. At every iteration, the agent produces an equivalent adjacency matrix of the causal graph. A comparator compares the generated adjacency matrix with the true causal edges in the prior knowledge matrix Pm, and theroby, computes a penally p for the violation of any ground truth edges the produced graph. Each generated graph also scored using a standard scoring function such as BIC, A reward is estimated as sum of the BIC score SBIE, the penalty for acyelicity h(W), and weighted prior knowledge penalty 8p. Finally, the entire process halts when the stopping criterion S. is reached, and the best-rewarded graph is the final output causal graph. Although originally KCRL was designed for the healthcare domain, it can be used in any other domain for causal discovery where some prior knowledge is available. Code for KCRL is available at https://github. haat///oo/maaaaaaaa///ee.. KCRL
R SBIC + 8p + h(W)
(4)
Feedbock reword signal
Agent
Folse
Graph
Adjocency
AL environment
Motrix
Comparator
Penalty
Reward estimation
Sy reached
Groph discovery
Feed Pa
Return the cousal with
X
Prior knowledge matrix Pm
Figure 15: The KCRL (Hasan & Gani (202 framework.
Another recent method called KGS (Hasan Gani (2023) leverages prior causal information such as the presence or absence of a causal edge to guide greedy score-based causal discovery process towards more restricted and accurate search space. It ratess how the search space as well as scoring candidate graphs can be reduced when different edge constraints are leveraged during search over equivalence classes of causal networks. It concludes that any type of edge information is useful to improve the accuracy of the graph discovery as well as the run time.
3.2.8 ILPed structure learning
Bartlett & Cussens 2017 looked into the application of integer linear programming (ILP) to the structure learning problem. To boost the effectiveness of ILP-based Bayesian network lcarning, they suggested adding auxiliary implied constraints. Experiments were conducted to determine the effect of each constraint on the optimization process. It was discovered that the most effective configuration of these constraints could significantly boost the effectiveness and speed of IL.P-based Bayesian network learning. The study made significant contribution the field of structure learning and showed how well ILP can perform under non-essential constraints.
16

---

Published in Transactions on Machine Learning Research (09/2023)
3.3 Functional Causal Model-based
Functional Causal Model (FCM) based approaches describe the causal relationship between variables in a specific functional form. FCMs represent variables as a function of their parents (direct causes) together with an independent noise term E' (see Equation 5 (Zhang et al. (2013)). FCM-based methods can distin- guish among different DAGs in the same equivalence class by imposing additional assumptions on the data distributions and/or function classes (Zhang et al. (2021b)). Some of the noteworthy FCM-based causal discovery approaches are listed below.
x= E
(5)
EE
X1 f (E,)
E1
E4
E2
X2 f2 (X2, E2)
X3 = fa (Bg)
X3
X4 f (81 E4)
X1
X
X
Figure 16: functional causal model (FCM) with four variables.
3.3.1 LiNGAM
Linear Non-Gaussian Acyelic Model (LINGAM) aims to discover the causal structure from observational data under the assumptions that the data generating process is linear, there no unobserved confounders, and noises have non-Gaussian distributions with non-zero variances (Shimizu et al. (2006)). It uses the statistical method known as independent component analysis (ICA) (Comon 1994)). ) and states that when the assumption of non-Gaussianity is valid, the complete causal structure can be estimated. That is, the causal direction is identifiable the variables have a lincar relation, and the noise (e) distribution is non-Gaussian in nature. Figure 17 depicts three scenarios where when and & are Gaussian (case 1), the predictor and regression residuals are independent of each other. For the other two cases, X and are non-Gaussian, and we see that for the regression in the anti-causal backward direction (X given Y), the regression residual and the predictor not independent carlier. That is, for the non-Gaussian cases, independence between regression residual and predictor occurs only for the correct causal direction. There are 3 properties of a LiNGAM. First, the variables z; = 21, T2, En are arranged in a causal order k(i) such that the cause always preceedes the effect. Second, cach variable x; is assigned a value as per the Equation where e, the noise/ noise/disturbant ddisuurance term and by denotes the causal strength between 24 and xy. Third, the exogenous noise e; follows a non-Gaussian distribution, with zero mean and non-zero variance, and are hidden confounder. Python implementation of the LINGAM algorithm is available at https: pttps://github. com/ cát15/1ingam
independent of each other which implies that there
well as in the gCastle package (Zhang et al. (2021b)). Any standard ICA algorithm which can estimate independent components of many different distributions can be used in LiNGAM. However, the original implementation uses the FastICA (Hyvarinen 1999h) algorithm.
24
Σ (())((())
biy +
(6)
3.3.2 ANM
Hoyer el al. 2008) performs causal discovery with additive noise models (ANMs) and provides a generaliza- tion of the linear non Con-Gausiian causal discovery framework to deal with nonlinear functional dependencies where the variables have an additive noise. It mentions that nonlinear causal relationships typically help break the symmetry between the observed variables and help in the identification of causal directions. ANM assumes that. the data generating process of the observed variables is per the Equation 7 where
17

---

Published in Transactions on Machine Learning Research (09/2023)
Regression of given X: Y- bx
Regression of X given Y:X b
Gaussian
Case 2: Uniform
Case 3: Super-Gaussian
Causal asymmetry between two variables having linear relation (Glymour et al. (2019)). ) Here, the causal direction from X to Y. total of three scenarios depicted where both X and follow the i) Gaussian, ii) Uniform, or iii) Huper-Gaussio distribution for each of the scenarios.
Figure 17:
variable is function of its parents and the noise term which is an independent additive noise. An implementation of ANM is available in the gCastle package (Zhang et al. (2021a))
24 -(PA..) +
(7)
3.3.3 PNL
Post-nonlinear (PNT.) acyelic causal model with additive noise (Zhang & Hyvärinen realistic model where each observed continuous variable made up of additive noise-filled nonlinear functions of its parents, followed by nonlinear distortion. The influence of sensor distortions, which are frequently seen in practice, is taken into account by the second stage's nonlinearity. A two-step strategy is proposed to separate the cause from the effect in a two-variable situation, consisting of restricted nonlinear 1CA followed by statistical independence tests. The PNL model was able to effectively separate causes from effects when applied to solve the PCauseEffectPairss' task proposed by Mooij & Janzing (2010) the Pot-luck challenge. That is, it successfully distinguished the cause from the effect, even if the nonlinear function the cause is not invertible.
(2010) a highly
3.3.4 Direct-LiNGAN
Shimizu et al. [2011) proposed DirectLiNGAM, direct method for learning a linear non-Gaussian structural equation model (SEM) which is direct method to estimate causal ordering and connection strengths based non- Gaussiaattn.. This approach estimates causal order of variables by successively reducing each independent component from given data in the model which is completed in steps equal to the number of the variables in the model. Once the causal order of variables is identified, their connection strengths are estimated using conventional covariance-basse approaches. If the data strictly follows the model i.c. all the model assumptions are met and the sample size is infinite, it converges to the right solution within small number of steps. If some prior knowledge on part of the structure is available, suggests using those for more efficient learning. Doing will reduce
methods such as least squares and maximum likelihood
18

---

Published in Transactions on Machine Learning Research (09/2023)
the number of causal orders and connection strengths to be estimated. Its implementation can be found at: http://hhh.....ooooo///////////a
3.3.5 SAM
proposed the algorithm known as Structural Agnostic Modeling (SAM) that uses an adversarial learning approach to find the causal graphs. Particularly, it searches for an FCM using Generative Adversarial Neural-networks (GANs) and enforces the discovery sparse causal graphs through adequate regularization terms. A learning criterion that combines distribution estimation, sparsity, and acyclicity constraints is used to enforce the end-to-end optimization of the graph structure and parameters through stochastic gradient descent. SAM leverages both conditional independencies and distributional asymmetries in the data lo find the underlying causal mechanism. It aims to achieve optimal complexity /fit trade-off while modeling the causal mechanisms. SAM enforces the acyclicity constraint of a DAG using the function in Equation [ where, A is the adjacency matrix of the ground-truth graph G, and denotes the total number of nodes in G. The latest implementation of SAM available in the CDT package (Kalainathan & Goudet (2019)) Also, an older version of SAM is available at httts:///githu: wttp///vviyaaaaaaaaaaaaaa
Kalainathan et al. 2018
tr tr(A') i!
0
(8)
3.3.6 CGNN
Causal Generative Neural Networks (CGNN) an FCM-based framework that uses neural networks (NNs) to learn the joint distribution the observed variables (Goudet et al. (2018)). Particularly, it uses a gen- erative model that minimizes the marimum meon discrepancy (MMD) between the generated and observed data. CGNN has high computational cost. However, it proposes approximate learning criterion to scale the computational cost to linear complexity in the number of observations. This framework can also be used to simulate interventions on multiple variables in the dataset. An implementation of CGNN in Pytorch is available at https://tthaaa...oooo/o/cc/ttttp
3.3.7 CAM
Causal Additive Model (CAM) is a method for estimating high-dimensional additive structural equation models which are logical extensions of linear structural equation models (Bühlmann et al. (2014)). In order address the difficultics of computation and statistical accuracy in the absence of prior knowledge about underlying structure, the authors established consistency of the maximum likelihood estimator and developed effective computational algorithm. The technique demonstrated using both simulated and actual data and made use of tools in sparse regression techniques. The authors also discussed identifiability problems and the enormous size of the space of potential models, which presents significant computational and statistical accuracy challenges.
3.3.8 CAREFL
Causal Autoregressive Flows (CAREFL) uses autoregressive flow models (Huang et al. (018c)) for causal discovery by interpreting the ordering of variables an autoregressive flow based on structural equation models (SEMs) (Khemakhem et al. (2021)). In general, SEMs define generative model for data based causal relationships. CAREFL shows that particularly offine flows define new class of causal models where the noise is modulated by the cause. For such models, it proves new causal identifiability result that generalizes additive noise models. To Iearn the causal structure efficiently, it selects the ordering with the highest test log-likelihood and reports a measure of causal direction based on the likelihood ratio for non-linear SEMs. Autoregressive flow models also enable CAREFL to evaluate interventional queries by fixing the interventional variable while sampling from the flow. Morcover, the invertible property of autoregressive flows facilitates counterfactual queries as well. Code implementation of CAREFL is available at httt::://giiaubb..co//gooooo////
19

---

Published in Transactions on Machine Learning Research (09/2023)
3.4
Gradient- based
Some of the recent studies in causal discovery formulate the structure learning problem as a continuous optimization task using the least squares objective and an algebraic characterization of DAGs (Zheng et al. (2018); Ng al. (2020)). Specifically, the combinatorial structure learning problem has been transformed into continuous one and solved using gradient-based optimization methods (Ng et al. (2019)). These methods leverage gradients of objective function with respect to parametrization of a DAG matrix. Apart from the usage of well-studied gradient-based solvers, they also leverage GPU acceleration which has changed the nature of the task (Ng et al. (2020)). Furthermore, to accelerate the task they often employ deep learning models that are capable of capturing complex nonlincar mappings (Yu et al. (2019)). As a result, they usually have a faster training time as deep learning is known to be highly parallelizable on GPU, which gives promising direction for causal discovery with gradient-based methods (Ng et al. (2019)). In general, these methods are more global than other approximate greedy methods. This is because they update all edges at each step based on the gradient of the score and as well based the acyclicity constraint.
3.4.1 NOTEARS
DAGs with NO TEARS (Zhnng ct al. 2018 is a recent breakthrough in the field of causal discovery that formulates the structure learning problem as a purely contintous constrained optimization task. It leverages an algebraic characterization of DAGs and provides a novel characterization of acyclicity that allows for a smooth global search, in contrast to a combinatorial local search. The full form of the acronym NOTEARS is Non-combinatorial Optimization via Trace Exponential and Augmented lagRangian for Structure learning which particularly handles linear DAGs. It assumes a linear dependence between random variables and thus models data D as structural equation model. To discover the causal structure, it imposes the proposed acyclicity function (Equation [0] as a constraint combined with a weighted adjacency matrix W with least squares loss. The algorithm aims to convert the traditional combinatorial optimization problem into a continuous constrained optimization task by leveraging an algebraic characterization of DAGs via the trace exponential acyclicity function as follows:
min F(W) WEROOD
min F(W). WER subject to h(W)=0
(9)
subject G(W)EDAGs
where G(W) is graph with nodes induced by the weighted adjacency matrix W, F Rdxdd - is a regularized score function with a least-square loss E, and h Rdxd + R is smooth function over real matrices that enforces acyclicity. Overall, the approach simple and can be executed in about 50 lines of Python code. Its implementation in Python is publicly available at https://githm:i com/ www//eng/noooearr. The acyclicity function proposed in NOTEARS is as follows where o is the Hadamard product and wow is the matrix exponential of W o W.
A(W) = WoW, - -d=
(10)
3.4.2 GraN-DAG
Gradient-based Neural DAG Learning (GraN-DAG) is a causal structure learning approach that uses newral networks (NNs) to deal with non-linear causal relationships (Lachapelle et al. (2019)) ). It uses stochastic gradient method to train the NNs to improve scalability and allow implicit regularization. It formulates a novel characterization of acyclicity for NNs based on NOTEARS (Zheng et al. (2018)). To ensure acyclicity in non-linear models, it uses an argunent similar to NOTEARS and applies it first at the level of neural network paths and then at the graph paths level. For regularization, GraN-DAG uses a procedure called preliminary neighbors selection (PNS) to select a set of potential parents for each variable. It uses a final pruning step to remove the false edges. The algorithm works well mostly in the case of non-linear Gaussian additive noise models. An implementation of GraN-DAG can be found at hhttps://ggthhhii httpps///ggtbbb.c////aaaaaaaaaas
20

---

Published in Transactions on Machine Learning Research (09/2023)
3.4.3 GAE
Graph Autoencoder (GAE) approach a gradient-based approach to causal structure learning that uses a gruph auloencoder framework to handle nonlinear structural equation models (Ng et al.] (2019) ). GAF is a special case of the causal additive model (CAM) that provides an alternative generalization of NOTEARS for handling nonlincar causal relationships. GAE is casily applicable to voctor-valued variables. The architecture of GAE consists of a variable wise encoder and decoder which are basically multi-layer perceptrons (MLPs) with shared weights across all variables X,, The encoder-decoder framework allows the reconstruction of each variable X; to handle the nonlinear relations. The final goal is to optimize the reconstruction error of the GAE with 1 penalty where the optimization problem is solved using the augmented Lagrangian method competitive in terms of scalability as it has near-linear training
Neeirovssy (1999)) The approach time when scaling up the graph size 100 nodes. Also, in terms of time efficiency, GAE performs well with average training time of fewer than 2 minutes for graphs of 100 nodes. Its implementation can be found at the gCastle (Zangg et al. 2021a repository.
3.4.4 DAG-GNN
DAG Structure Learning with Graph Neural Networks (DAG-GNN) is graph-based deep generative model that tries to caplure the sampling distribution faithful to the ground-truth DAG (Yu et al. (2019)). It leverages variational inference and a parameterized pair of encoder-decoders with specially designed graph neural networks (GNN). Particularly, it uses Variational Autoencoders (VAEs) to capture complex data distributions and sample from them. The weighted adjacency matrix W of the ground-truth DAG is a learnable parameter with other neural network parameters. The VAF model naturally handles various data types both continuous and discrete in nature. In this study, the authors also propose a variant of the acyclicity function (Equation 11] which is more suitable and practically convenient for implementation with the existing deep learning hods In the acyclicity function, d the number of nodes, a is a hyperparameter, and 1 is an identity matrix. An implementation of the DAG-GNN algorithm is available at
IT[T + o w)4 d
(11)
3.4.5 GOLEM
Gradient-based Optimization of DAG-penalized Likelihood for learning linear DAG Models (GOLEM) is a wlkelihood-base causal structure learning approach with continuous unconstroined optimázation (Ng et al. (2020)) It studies the asymptotic role of the sparsity and DAG constraints for learning DAGs in both linear Gaussian and non-Gaussian cases. It shows that when the optimization problem is formulated using likelihood-based objective instead of least squares (used by NOTEARS), then instead of a hard DAG constraint, applying only soft sparsity and DAG constraints is enough for learning the true DAG under mild assumptions. Particularly, GOLEM trics to optimize the score function in Equation 12 w.r.t. the weighted adjacency matrix B representing a directed graph. Here, I(B; x) is the maximum likelihood estimator, Rsparse(B) penalty to encourage sparsity (i.c. fewer edges), and (DAG(B) the penalty that enforces DAGness on B.
= L(B;x)+ + Raparse (B)
(B) + (DAG(B)
(12)
In terms of denser graphs, GOLEM scoms to outperform NOTEARS since it can reduce the number of optimization iterations which makes it robust in terms of scalability. With gradient-based optimization and GPU acceleration, it can easily handle thousands of nodes while retaining high accuracy. An implementation of GOLEM can be found the gCastle (Zhang et al. (202aa) repository.
3.4.6 DoC-l
DAG-NoCus also known as DAGs with No Curl uses two-step procedure for the causal DAG search Yuu et al. (021)). ). At first, it finds an initial cyclic solution to the optimization problem and then employs the
21

---

Published in Transactions on Machine Learning Research (09/2023)
Hodge decomposition [Bhatia et al. (2012) of graphs to learn acyelic graph by projecting the cyclic graph to the gradient of potential function. The goal of this study is to investigate how the causal structure can be learned without any explicit DAG constraints by directly optimizing the DAG space. To do so, it proposes the method DAG-NoCurl based on the graph Hodge theory that implicitly enforces the acyclicity of the learned graph. As per the Hodge theory on graphs (Lim (020)); a DAG is a sum of three components: a curl-free, a divergence-free and a harmonic component. The curl-free component an acyclic graph that motivates the narning of this approach. An implementation of the method can be found at the link sttps://githur httpa///o/..oooooooo122////00000 NoCur
3.4.7 ENCO
Efficient Neural Causal Discovery without Acyclicity Constraints (ENCO) uses both observational and inter- ventional data by modeling a probability for every possible directed edge between pairs of variables (Lippe et al. (202 ). It formulates the graph search as an optimization of independent edge likelihoods, with the edge orientation being modeled as a separate parameter. This approach guarantees convergence when in- terventions on all variables are available and do not require explicitly constraining the score function with respect to acyclicity. However, the algorithm works on partial intervention sets as well. Experimental re- sults suggest that ENCO is robust in terms of scalability, and is able to detect latent confounders. When applied to large networks having 1000 nodes, it is capable of recovering the underlying structure due to the benefit of its low-varianc, gradient estimators. The source code of ENCO is available at this site: https:/ htte:///gtthtt..e. paan/phlippe//ee
Intervention
Sample graphs
Estimate log-iikelihoods and averoge
Determine gradients
Groph Porometers
Figure 18: Graph optimization mechanism of ENCO.
3.4.8 MCSL
Masked Gradient-based Causal Structure Learning (MCSL) (gg et al. (2022) utilizes reformulated structural equation model (SEM) for causal discovery using gradient- basee optimization that leverages the Gumbel-Softrar approach (Jang et al. (2016)). This approach is used to approximate a binary adjacency matrix and is often used to approximate samples from a categorical distribution. MCSL reformulates the SEM with additive noises a form parameterized by the binary graph adjacency matrix. It states that, if the original SEM is identifiable, then the adjacency matrix can be identified up to super-graphs of the true causal graph under some mild conditions. For experimentation, MCSL uses multi-layer perceptrons (MLPs), particularly having 4-layers as the model function which is denoted as MCSL-ML.. An implementation of the approach can be found in the gCastle (Zhang et al. (2021a)) package.
3.4.9 DAGs with No Fears
Wei et al. (2020) provides an in-depth analysis of the NOTEARS framework for causal structure learn- ing. The study proposed a local scarch post-processing algorithm that significantly increased the precision of NOTEARS and other algorithms and deduced Karustl-Kuhn-Tucker (KKT) optimality conditions for an equivalent reformulation of the NOTEARS problem. Additionally, the authors compared the effec- tiveness of NOTEARS and Abs-KKTS on varions graph types and discovered that Abs-KKTS performed better than NOTEARS in terms of accuracy and computational efficiency. The authors concluded that this work improved the understanding of optimization-base causal structure learning and may result. in
22

---

Published in Transactions on Machine Learning Research (09/2023)
further advancements in precision and computational effectiveness. The code implementation is available httpp:///githuub.co/////////////
3.5 Miscellaneous Approaches
Apart from the types of approaches mentioned so far, there are some other causal discovery approaches that use some specialized or unique techniques to search for the graph that best describes the data. There also cxists some methods that are specialized to handle latent or unobscrved confounders. Also, there are some approaches that, are hybrid in nature, iee. they are based on the combination of const score-based, FCM-based, gradient-based, etc. causal discovery approaches. For example, some approaches integrate conditional independence testing along with score functions to design a hybrid approach for causal discovery. A detailed discussion can be found below.
3.5.1 MMHC
Max-Min Hill Climbing (MMHC) is hybrid causal discovery technique that incorporates the concepts from both score-based and constraint-basee algorithms (Teamardinos et al. (2006)) ). A challenge in causal discovery is the identification of causal relationships within reasonable time in the presence of thousands of variables. MMHC can reliably learn the causal structure in terms of time and quality for high-dimensions scttings. MMHC is a two-phase algorithm that assumes faithfulncss. In the first phase, MMHC uses Max-Min Parents and Children (MMPC) (Tsamardinos el al. (2003)) to initially learn the skeleton of the network. In the second phase, using a greedy Bayesian hill-climbing search, the skeleton is oriented. In the sample limit, MMHC's skeleton identification phase is reliable, but the orientation phase offers no theoretical assurances. From the results of the experiments performed, MMHC outperformed PC (Spirtes et al. (2000b)), Sparse Candidate (Friedman et al. (2013)), ) Optimal Reinsertion (Moore & Wong (2003) and GES [Chickering (2002)) in terms of computational efficiency. Considering the quality of reconstruction, MMHC performs better than all the above-mentioned algorithms except for GES when the sample size is 1000. The authors also proved the correctness of the results. The implementation of MMHC available at sattp://ww/ dss-dalllllaa aaeelllaborg//aaeee swppseueppesssss////e httmm//ppr//mmcccttiieeeoeeeeeee library of Bayesian network learning and local causal discovery methods.
html as part of Causal Explorer 1.3, a
3.5.2 FRITL
To discover causal relationships in linear and non-Gaussian models, Chen et al. (2021) proposed a hybrid model named FRITL. FRITL works in the presence or absence of latent confounders by incorporating inde- pendent noise-based techniques and constraint-based techniques. FRITL makes causal Markov assumption, causal faithfulness assumption, linear acyclic non-Gaussianity assumption, and one latent. confounder as- sumption. In the first phase of FRITL., the FCI algorithm is used to generate asymptotically accurate results. Unfortunately, relatively few unconfounded direct causal relations are normally determined by the FCI since always reveals the presence of confounding factors. In the second phase, FRITL identifies the unconfounded causal edges between observable variables within just those neighboring pairings that have been influenced by the FCI results. The third stage can identify confounders and the relationships that cause them to alfect other variables by using the Triad condition (Cai et. al. (2019)). If further causal relationships remain, Independent Component Analysis (ICA) is finally applied to notably reduced group of graphs. The authors also theoretically proved that the results obtained from FRITL are efficient and accurate. FRITL produces results that are in close accord with neuropsychological opinion and in exact agreement. with a causal link that is known from the experimental design when applied to real functional magnetic MRI data and the SACHS (Sachs et al. (2005)) dataset.
PAG construction
Infer local causal structures
Detect shared hidden confounders
Estimate remaining
using FCI
causal edges
Stage-1
Stage-2
Stage-3
Stage-4
Figure 19: Stages of the FRITL model.
23

---

Published in Transactions on Machine Learning Research (09/2023)
3.5.3 HCM
Most of the causal discovery algorithms are applicable only to either discrete or continuous data. However, in reality, we often have to work with mixed-type data (e.g., shopping behavior of people) which don't receive enough attention in causal discovery. Li et al. (2022 proposed the approach Hybrid Causal Discovery Mixed-type Data (HCM) to identify causal relationships with mixed variables. HCM works under the causal faithfulness and causal Markov assumption. HCM has three phases where in the first phase, the skeleton graph is learned in order to limit the search space. To do this, they used the PC-stable approach along with their proposed Mixed-lype Randomized Causal Independence Test (MRCIT) which can handle mixed-lype data. They also introduced a generalized score function called Cross- Cross-Validaes Validation based Mixed Information Critcrion (CVMIC). In the second phase, starting with empty DAG, they add edges to the DAG based the highest CVMIC score. In order to reduce false positives, the learned causal structure is pruned using MRCIT once again in the final phase with slightly bigger conditional set.. They compared their approach with other causal discovery approaches for mixed data and showed HCM's 's superiority. However, they didn't 't consider any unobserved confounders in the dataset which allows for further improvement. They made the code available on the following Git site: htttps:/ggite
com/DAMO- DAWP/DDAOOOODMIM/AAA AALL/AAAA2222HC
Skeleton Groph S Discovery via PC-stable & MRCIT
Causal Graph Cg Discovery via Greedy search & CVMIC
Pruning Cg via MRCIT
Phose 1
Phose 2
Phase 3
Figure 20: Different phases of the method HCM.
3.5.4 SADA
One of the biggest limitations of the traditional causal discovery methods is that these models cannot identify causal relations when the problem domain is large or there is small number of samples available. To solve this problem, Cai et al. (2013) proposed a Split- aire-and--ae Merge causal discovery method named SADA which assumes causal faithfulness. Even in situations when the sample size is substantially less than the total number of variables, SADA can reliably identify the causal factors. SADA divides the main problem into two subproblems and works in three phases. Initially, SADA separates the variables of the causal model into two sets V1 and V/2 using a causal cut set C' where all paths between V1 and V/2 are blocked by C. This partitioning is continued until the variables in each subproblem are loss than some threshold. In the next phase, any arbitrary causal algorithm is applied to both subproblens and the causal graphs are generated. Here, they used LiNGAM as the causal algorithm. Then these graphs are merged in the final step. But to handle the conflicts while merging, they only kept the most sigmificant edge and eliminated the others whenever there existed multiple causal paths between two variables in the opposite direction. They compared the performance of SADA against baseline LiNGAM (without splitting and merging), and the results showed that SADA achieved better performance in terms of the metrics precision, recall, and Fl score.
3.5.5 CORL
Ordering-based Causal Discovery with Reinforcement Learning (CORL) formulates the ordering search prob- lem multi-step Markov decision process (MDP) to learn the causal graph (Wang et al. (2021) )) It imple- ments the ordering generating process with decoder architecture and finally uses RL to optimize the proposed model based on the reward mechanisms designed for cach order. A generated ordering is then processed using variable selection to obtain the final causal graph. According to the empirical results, CORL performs better than existing RL-based causal discovery approaches. This could happen because CORL does not require computing the matrix exponential term with O(d3) cost because of using ordering scarch. CORL is also good in terms of scalability and has been applied to graphs with up to 100 nodes. The gCastle package contains implementation of CORL.
24

---

Published in Transactions on Machine Learning Research (09/2023)
3.5.6 ETIO
ETIO is a versatile logic-bused causal discovery algorithm specialized for business applications (Borboudakis & Tsamardinos (2016)). Its features include i) the ability to utilize prior causal knowledge, ii) address- ing selection bias, hidden confounders, and missing values in data, and iii) analyzing data from pre and post-interventional distribution. ETIO follows query-based approach, where the user queries the algorithm about the causal relations of interest. In the first step, ETIO performs several CI tests on the inpul dataset. Particularly, it performs non-Bayesian tests that return p-values of the null hypothesis of conditional inde- pendencies. Then it employs an empirical Bayesian method that converts the p-values of dependencies and interdependencies into probabilities. Later, it selects a consistent subset dependence, and prior knowledge constraints to resolve conflicts which are ranked order of confidence. Particularly, ETTO imposes an m- separation constraint if a given independence is more probable than the corresponding dependence. These imposed constraints are the ones that correspond to test results, in order of probability, while removing con- flicting test results. Finally, it identifies all invariant features based input queries using the well-known declarative programming language, answer set programming (Gelfond & Lifschitz (1888)
3.5.7 VQCD
Discovering causal relationships from observational data has been a challenging task, especially for the bivariate cases as it is difficult to determine whether there actually exists cause-effect relationship whether it is the effect of hidden confounder. Tagasovska et al. (2020) proposed the approach bivariate Quantile Causal Discovery (bQCD) to determine causal relationships in bivariate settings. Although they made no assumptions on the class of causal mechanisms, they did assume that there exists no confounder, feedback, or selection bias. They utilized quantile scoring in place of Kolmogorov complexity (Kolnogorov (1963)), and used conditional quantiles, pinball loss instead of conditional mean, and squared loss. The approach bQCD performs almost similarly to the state-of-the-art techniques but it is much more computationally inexpensive. Also, the usage of quantile conditioning instead of mean conditioning makes bQCD more robust to heavy tails as the mean is more susceptible to outliers than the quantile. Moreover, not making any assumptions about the parametric class allows bQCD to be applied to variety of processes where baseline methods perform significantly poorly when the assumptions do not hold. The source code of bQCD written in R. is available on this site: https://github. com/tagas/bQCD
3.5.8 JCI
Joint Causal Inference (JCI) leverages prior knowledge by combining data from multiple datasets from different contexts (Mooij et al. (2000)) Particularly, JCI is a causal modeling framework rather than a specific algorithm, and can be implemented using any causal discovery algorithm that can take into account some background knowledge. The main idea of JCT is to first, consider auxiliary context variables that describe the context of each data set, then, pool all the data from different contexts, including the values of the context variables, into single data set, and finally apply standard causal discovery methods to the pooled data, incorporating appropriate background knowledge on the causal relationships involving the context variables. The framework is simple and casily applicable as it deals with latent confounders, cycles (if the causal discovery method supports this), and various types of interventions in a unified way. The JCI framework also facilitates analysis of data from almost arbitrary experimental designs which allow rescarchers to trade off the number and complexity of experiments to be done with the reliability of the analysis for the purpose of causal discovery.
Context Variable Generation
Any Standard CD Algorithm
Cousal Discovery
Background Knowledge
Multiple Datasets from Different Contexts
Single Dataset Generation
Figure 21: Workflow of the JCI framework.
25

---

Published in Transactions on Machine Learning Research (09/2023)
3.5.9 Kg2Causal
Kg2Causal (iinha & Ramssy (2021) uses a large-scale general-purpose biomedical knowledge graph as a prior for data-driven causal discovery. With a set of observed nodes in a dataset and some relationship edges between the nodes derived from knowledge graph, Kg2Causal uses the knowledge graph-derivod edges to guide the data-driven discovery of a causal graph. The main idcas of this approach are first, mapping each variable in the dataset to node in the knowledge graph, and querying relationships between them; next, extracting subgraph containing the connected variables with edges between them; and then this edge set is used as prior knowledge to guide an optimizing scoring step for inferring the causal graph. An implementation of Kg2Causal is available at htttps://gittee http://co///ggnn/////aaaaaa in R language.
3.5.10 C-MCMC
Constrained MCMC (C-MCMC) introduces prior knowledge into the Markow chain Monte Carlo (MCMC) algorithm for structure learning Xu et al. 2015)). C-MCMC uses the following three types of prior knowl- edge: the existence of parent nodes, absence of parent nodes, and distribution knowledge including the conditional probability distribution (CPD) of edges and the probability distribution (PD) of nodes. All prior knowledge should be given by domain experts. Existence knowledge means that for any node X;, node-set pa(X;) includes all parent nodes of X,, The absence of knowledge means that for node X;, node-set pa();) does not include any parent node of X,, PD/CPD knowledge means that the PD of node and the CPD of an edge are known. Considering that the prior knowledge may not be consistent and reliable, a confidence lambda. is assigned by domain experts on each the prior knowledge that ranges from to 1. This denotes the certainty level of prior knowledge. A lambda value of indicates very high confidence in this knowledge.
3.5.11 Mela-RL
Meta-RL is a meta-learning algorithm in a Reinforcement Learning (RL) setting where the agent learns perform interventions to construct causal graph (Sauter et al. (0022) ). The goal is to be able to use previous learning experiences during training to generalize in unseen environments. This approach has some strong assumplions such as i) each environment is defined by an acyelic SCM, ii) every observable variable can be intervened on, iii) for each environment in the training set, the underlying SCM is given, and iv) intervention can be performed on at most one variable at a time. Mcta-RL has two phases: i) Training, and ii) Application. The training phase starts by randomly choosing an SCM from a set environments. There are mainly two sets of actions that an agent performs: a) interventional actions, and b) structure actions. In each step, any one action can be performed on the set of variables interventional actions in each step. However, in case of the structural actions (c.g. add, delete, reverse), the agent policy only gets updated at the end of the training procedure where a reward is sent to the agent. The reward is computed by comparing the hamming distance of the generated PDAG to the true causal structure when the training is completed. A recurrent LSTM layer enables the policy to remember samples from the nost-interventioall distributions in the earlier steps. This should help to better identify causal relations since the results of sequential interventions can be used estimate the distribution. Once trained, Meta-RL can then be applied environments that have structure unseen during training. For training, 24 SCMs with 3 observable variables, and 542 SCMs with observable variables were created. Code to reproduce experiments run Meta-RL is available at httts:://gii wttp://////anannineeeeeeeeaeaeee
generate a PDAG. The agent policy updated via the
One limitation of this approach is that it needs modification in terms of scalability. Also, in real-world scenarios, every variable might not be accessible for intervention.
3.5.12 Tabu search for SEM
Marcoulides et al. 19988 presents an approach to structural equation modeling (SEM) specification search that makes use of Tabu search, a heuristic optimization algorithm. Using a neighborhood of the current solution as its focus, the tabu search technique avoids local optimality by examining the area around the current solution. To prevent cycling, assigns recently involved attributes a tabu status. A number of defi- nitions and parameters, such the neighborhood definition and the model selection criterion, are necessary
26

---

Published in Transactions on Machine Learning Research (09/2023)
Random Choice
Each Step
Fpisade
Intervention Accions
Ubservation
Agent Policy
Structure Actions
Policy Updote
Reward
Agent Model
Figure 22: Training phase of the Meta-RL algorithm (Sauter et al. 2022
implement the Tabu search procodure for SEM specification scarch. The authors conclude that Tabu search is a promising strategy for SEM specification search after demonstrating its ellicacy in number of example analyses.
3.5.13 LFCM
Latent Factor Causal Models (LFCMs) (Squires al. (2022) perform causal discovery in the presence of latent variables. These models are motivated by gene regulatory networks. LFCMs work in three stages where they discover: (i) clusters of observed nodes, (ii) partial ordering over clusters, and (iii) finally, the entire structure over both observed and latent nodes. A graph G is called latent factor causal model (LFCM) if it satisfies the following conditions: (a) Unique cluster assumption: Each observed node has exactly one latent parent, (b) Bipartite assumption: There are no edges between pairs of observed nodes or between pairs of latent nodes, (c) Triple-child assumption: Each latent node has at least 3 observed children and (d) Double-parent assumption. The other assumption of LFCMs that allows non-exogenous latent variables. For cluster formation, LFCMs rely on t-separation (Sullivant al. (2010)). When two ordered pairs of variables jo.g. (X,, Xj) and (X,,, X,)) are t-separated, then they belong the same cluster. LFCMs are biologically motivated class of causal models with latent variables. The limitations of LFCMs include their applicability to only linear Gaussian SEM, some major structural restrictions, and that it can fail when the true graph violates the double parent assumption.
There are some other noteworthy methods that are specialized to handle latent variables or unobserved confounders. Kocaoglu et al.] (2017) presented a non-parametric algorithm for learning causal graph in the presence of hidden variables. The study took stage-by-stage approach, first to learn the induced graph be- tween observational variables, and then use it to discover the existence and location of the latent variables. The authors further proposed algorithm to discover the latent structure between variables depending on the adjacency. To identify ancestral relationships and transitive closure of the causal graph, the algo- rithun employed a pairwise independence (est under interventions. Then Kocaoglu et al. (2019) addressed causal discovery by linking conditional independencies from observed data to graphical constraints using the d-separation critcrion. broadened the application of this stratogy scenarios involving numerous exper- imental and observational distributions. The authors proposed that CIs and d-separation constraints are just. subset of broader constraints obtained from comparing various distríbutions, which is especially useful
27

---

Published in Transactions on Machine Learning Research (09/2023)
l
4
42
X1
X2
X
X
X5
L
X
X
Xg
Figure 23: The graph G on the left is latent factor causal model (LFCM), and the graph on the right is the latent graph L(G) for G (Squires et al. (0222)
in the context of do-caleulus for soft interventions. They introduced the notion inderventional equivalence class of causal graphs with latent variables, which linked graphical structures to groups of interventional distributions that adhered to do-calculus. Two cansal graphs are interventionally equivalent if they produce identical interventional distributions that can not be distinguished by invariances.
Sometimes complex systems require the knowledge of both observations and experiments for recovering the underlying causal relationships. Utilizing both observational and interventional data from various domains, the authors in et al.] proposed a novel approach for identifying causal structures in semi-Markovian systems with latent confounders. They made link between learning from interventional data within single domain and learning from observational data across domains. They introduced the idea of S-Markov, properly connecting multi-domain distributions to pairs of causal graphs and interventional targets, to navigate the complexitics of observational and experimental data. new causal discovery algorithm called S-FCI was introduced that builds on the S-Markov property and is capable of effectively learning from a mixture of observational and interventional data from various domains.
Jaber et al. (020)) integrates soft experimental and observational data to find the structure in non-Markovian systems with latent variables. They introduced the idea of M-Markov in this context when the intervention targets were unidentified. This idea links a causal graph G and list of interventional targets T to the causal invariances found in both observational and interventional data distributions. They also introduced a graphical method for evaluating equivalence between causal graphs with varions interventional targets and an algorithm for learning the equivalence class.
Recently, Bellot et al. (002)) studied structure learning in discrete models with arbitrary latent dependencies, and proposed a new score based on the asymptotic expansion of the marginal likelihood to capture both equality and inequality constraints in observational data. Furthermore, it claims to be the first score-based method to learn causal models with latent variables.
The different methods discussed in this section so far use a variety of strategies to perform causal discovery under diverse settings and assumptions. Therefore, we present a comparative analysis of some of the common methods Table basod on their assumptions, output causal graph, techniques used, advantages, and disadvantages. This comparative analysis will help readers to find the similar and dissimilar methods, and also help in deciding which method could be appropriate for performing causal discovery given the data and its assumptions.
28

---

Published in Transactions on Machine Learning Research (09/2023)
Lacks scalabiity as loss foasible denser graphs in the worsh case, the no. of CI tosts porformed grows expone with the no.. of variables.
Per Performs some additionl tosts before orienting v-structures and discrim innting paths Search space can 87OW exponentiall with the growing no. of variables Require high power computing to run
Scala only up LO & lew (around 30) variables
Estimsted rosults may vary in case of mixxd data
Qualitty the resulls dependk on the quality of the initial solution and the choice of parsmeters
Faces performance and computati computational challenges as the number of variables Increasees
Assumes acyallo conssa relacionalips which may not always the case in roal woold scenarios
Scales up better only with large number of somples ppples
Not generalizate lizabl in non-linea gaussion cases
Requires knowledge greph
Hos complexity iseues
Works well mostly for continuou dats
May not work well for linear causal volations
eateggrical valmes)
Lacks scalability
Not suttable for dense graphs
Disdvantaa
Faster variani of FCI. uses fewer CI computation for high-dinensse computtiionally feasibble sparse graphs
Run time faster compured to
Faster varian: CES, roduces scoting the constraint- bhate- mothods
redundance dannyyy smables parallelizat
Model gets leodbacc to updale feorrect its search strategy
Can landle both lineea Gaussan & non Gansian networlas, scales up to more than 60 variables
know lodge constraints Determines the diroction of every causal arrow, does not r require the Faithfulness aesumptin
Good for sparse causal graphs
Considers avoiding local optima also, cyole avoldance
Establishes consistency of the maximum likelhhood estimator for low and high-d/mensionn casis
Can seale up to 100 nodees Lower run time, masily applicable to voctor- valt-nd variables, & handles nou- Sun-linerr relatione well Can handle both discrete and vector-vall valued variables, and is capable caphuring complex noulincar ppppigss
Good computationn efficiency, scalability and applicable for high dindddmttaiin dintansional settings
Works in prosence or absence latent confounders Leverages information from existing literature or domsin
Compatationally mtre fraxible for sparss graphs.
Hondles latent and selection variables.
Considers prior
Simple method, easy to implemee eemeennnt
Advantages
Table B: Comparion among discovery algorithms for L.I.D. data.
Gradient- based, uses blackbox stochastic optimization solvers to solve the problem maximiaing the ELBO Hyhrid: uses both score and constraint-based braannttbaased techniques MMPC to initially leara the skeleton of the werkurk.. then uses groedy Beyeelea hill- ti-cllmbiing search Ilybrid, uses FCI, Triad condition and ICA Prior know gedge constraints
Conditional Independencs (CI) Tests
Conditional Independence tosts
BIC score- based reiuforcement learning search
Scoro-based RL soarch strategy
FCM- basod, uses Independent. couponnet analyssis
Searches for FCM using GANSs
Ieeratively modiftes the model and evaluntes its fit to the data by exanining neighborhood of the current solution
FCM-bassed uses sparse regression techniques and decouples order search among the variisics
uses a regularized score- score-function function with least least-squal sqquare loss
Gradient based approach that uses graph autoencodor framework
se
added in a spore- score-based based method
funding step same ass PC
Score-based based greedy search
Score- based greedy search
Models data as a SEM,
A search combined with BIC score
Technique used
CI tosts, Skeleton
Outcome
CPDAG
CPDAG
PAG
PNG
DAG
DAG
DAG
DAG
DAG
DAG
DAG
DAG
DAG
DAG
DAG
DAG
PAG
DAG
Lincer DCP, no unobeervod con confounders, nun- Gaussaa moisus
Derompushbi score- score- function, unbiased prior knowledge
Finite soarch space, well-defined objective function
Acyalicity, linear dependence between variables
Faltbfulness, sufficiency, decomposabble score- function
Faithful nesss non- Caussiants latent confounder assumption
Presence of knowledge graph
Faithfulness, Sufficiency
Causal Markow condition, faithfulrees
Sufhicieney, Acyelicity
Strneture learning under additive noise models
Faithfilness, sufficiency
Decomsposlble score function, acyclicity
CMC, faithhulnesss
Weak Paithfulness
Assmmptions
Decomposable score function
Acyolicity
Acyclicity
Methods
PC
PCI
RFCI
GBS
PGS
RI-BIC
Triplet A
KCRL
LiNGAM
SAM
Tabu search
CAM
NOTEARS
GAE
DAG-GNN
MMMHC
FRITL
Ke2Causal
29

---

Published in Transactions on Machine Learning Research (09/2023)
4 Causal Discovery Algorithms for Time Series Data
Time series data arise when observations are collected over period of time. So far the methods that we have discussed are specialized for causal discovery from I.I.D or time-independent data. However, often, real-world data in different domains can be a time series (non-I.I.D. data). For this type of data, there are different specialized causal discovery approaches based on CI testing, SEM/FCMs, Granger causality (Granger [1999)) or deep neural networks. In this section, first, we provide a brief introduction to some of the common terminologies related time-series data and temporal causal discovery. Then, we discuss the notable causal discovery approaches for time-sories data.
Definition 7 (Time Series Data)
Time series data is a collection of observations measured over consis- lent intervals of time. The obsercalion of time series variable X at time t is denoted by X
Examples of time series data include retail sales, stock prices, climate data, heart rate of patients, brain activity recordings, temperature readings, etc. Any time series data may have the following properties:
Trend: When the data show a long-term rise or fall, a trend is present. Such long-term increases or decreases in the data might not be always linear. The trend is also referred to as changing direction when it might switch from an upward trend to a downward trend.
ii Seasonality: It refers to the seasonal characteristics of time series data. Seasonality exists when the data regularly fluctuates based on different time spans (e.g. daily/weekly/ monthly/ /quurturrrrr////ree yyerrlyyy An example temperature data, where mostly observed that the temperature is higher in the summer, and lower in the winter. Any analysis related to time scries usually takes advantage of the scasonality in data to develop more robust models.
ii Autocorrelation: Autocorrelation or self-correlation is the degree of similarity between a given time se- ries and a lagged version of itself over successive time intervals. Time series data is usually autocorrelated i.c., the past influences the present and future (Lawton et al. (2001)).
iv Stationarity & Non-stationaritay Stationarity means that the joint probability distribution of the stochastic process does not change when shifted in time. A time series is stationary if it has causal links such that for variables X and X2, if X - X at any limestamp 4, then X - X also holds for all l' * This condition does not hold for a non-stationary time series where X + +X at a particular time need not necessarily be true at any other time stamp f'.
Let X1 (X),, X .... X } be multivariate time series with variables and t time steps. At any particular timestamp 1, the state of the n variables can be represented as X = (X,, X?,..., X The past of a variable X is denoted by X The parent set of a variable includes all the nodes with an edge towards it. The goal of any temporal causal discovery approach is to discover the causal relationships between the time series variables. Any time series causal graph may have the following types of causal relationships/ /edges: (i) Instantaneous edges, and (ii) Lagged edges.
Definition 8 (Instantaneous Causal Effect) When the delay between cause and effect is 0 timesteps, í.e. causal effects are of the form X; X7 or X; + Xt (self-causation), then it is known as an instantaneous contemporaneous causal relationship/ hettoosssip///ffee (Nauta et al. (2019)..
Definition 9 (Lagged Causal Effect) When the delay between cause and effect at least or more timesteps (i.e. causal effects of the form Xi_ + X3 or Xi_ + Xi), then it is known as a lagged causal plationship/effedd That is, lagged causal effect occurs when variable causes onother variable or itself with time lag 1 or more.
In Figure 24 the red-colored edges represent the instantancous causal effect (relationships among the variables at the same time step), and the blue edges represent the lagged causal effect. The green edges represent special form of temporal causal relationships known as the changing modules (CM). The CMs
30

---

Published in Transactions on Machine Learning Research (09/202))
Changing Module
X
X
X
Instanianeous edge
X
x2_
xi
Lagged edge
X
x²
x2
Figure 24: Types of causal relationships: Instantaneous edges (red), Lagged edges (blue), and Changing modules (green).
represent the direct effect of time stamp on variable (e.g. - X3 in Figure Details on CM are available in Ferdous et al. (2023b).
The causal graphs produced by different temporal causal discovery algorithms vary based on the details of the relationships they represent. Any temporal causal discovery algorithm may produce any of the following two types of temporal causal graph as its outcome: a full-time cousal graph or a summary causal graph (see Figure 25
Definition 10 (Full-time Causal Graph) A full-time causal graph represents both the instantaneous (X; X or X > x;) and time-lagged (Xi_ + X or X - x;)) causal edges where the lag between a cause and effect is specified in the graph. A full-time casual graph may sometimes present the changing modules well.
X
X
x1
x
x
x
x
xi
x
X
x2_
x
x2
x²
Figure 25; Full-time causal graph (Left) & Summary causal graph (Right)
Figure 25 (left) represents a full-time causal graph where both instantaneous relations (e.g. X² + X3, X1 2-1 12 and lagged relations (e.g. x²_ + X2, X3_ + X?) among the variables are depicted.
Definition 11 (Summary Causal Graph) A summary causal graph is a reduced version of full-time causal graph where each lagged node represents the entire past (X{_) of its corresponding instantaneous node ), and the eract time lag between the cause and effect is not specified in the graph.
31

---

Published in Transactions on Machine Learning Research (09/2023)
Causal Discovery Algorithms (for time series data)
Contraint-base
FCM-based
Gradient-based
Granger Causelity-based
Miscellaneous
tsFC1
4.1.1
VarLiNGAM 4.2.1
DYNOTEARS 4.3.1
GVAR 44.1 NAVAR ACD (4.4.3)
oCSE
4.5.1
PCMCI LPCMCT
TIMINo 4.2.2
NTS-NOTEARS (4.3.2)
TCDF
NBCB L5.3
CDANs 4.1.6
PCTMI
Figure 26: Taxonomy of some of the discussed causal discovery approaches for time series data. The approaches are classified based their contribution the primary strategy they adopt for causal structure recovery. The approaches that can leverage prior knowledge are marked by an symbol. Some of the gradient- based approaches that use score function are indicated by o symbol. They are primarily classified as such as they use gradient descent for optimization. However, they can be a acore-based method too as they compute data likelihood scores on the way.
In the following subsections, we describe briefly some of the notable causal discovery algorithms that focus on time series data. Figure 26 presents taxonomy of some of the discussed approaches.
4.1
Constraint-based
4.1.1
tsFCI
The algorithm time series FC1 or tsFCI (Entner & Hoyer (0100) adapts the Fast Causal Inference (Spirtes et al. (2000a)) algorithm (developed for the causal analysis of non-temporal variables) to infer causal re- lationships from time series data. It works in two phases: (i) an adjacency phose, and (ii) an orien- tation phase. Tt makes use of temporal priority and consistency throughout time to orient edges and restrict conditioning sets. It provides a window causal graph, and advantage is that it can detect lagged hidden confounders. However, disadvantage is that it cannot model cyclic contemporaneous causation, and also instantaneous relationships. A code package that implements tsFCI is available at https://sitte htt.d//eaooos/sso/oaaaaaaaaaaaaa
4.1.2 PCMCI
A problem with large-scale time series data is that although adding more variables makes causal analysis more interpretable, if the additional variables don't have significant effect on the causal model, this, in turn, makes the analysis less powerful, and original causal relations may also be overlooked. Moreover, at large dimensions, certain nonlinear tests even lose their ability to limit false positive rates (FPRs). Runge et al. (219)) proposed a two-stage algorithm PCMCI that can overcome this problem. In Step-1, the model selects conditions using PC₁ (a variant of the skeleton discovery part of the PC algorithm) to remove irrelevant variables which solve the issue of low power in the causal discovery process. In Slep-2, the momentary conditional independence (MCT) test is used which helps to reduce the FPR even when the data is highly correlated. The MCI test measures if two variables are independent not given their parent sets (see Equation 13
x XXIP
(13)
PCMCI assumes that the data is stationary, has timo-lagged dependencies, and also assumes causal suffi- ciency. Even when the stationary assumption is violated (probably by obvious confounders). PCMCI still pro- vides more robust. performance than Lasso regression the PC algorithm. However, for highly predictable
32

---

Published in Transactions on Machine Learning Research (09/2023)
systems where little new information is produced at each time step, PCMCI is not good fit. Python imple- mentation of PCMCT is available in the Tigramile package (tttesr//sttu...caaaaaaooogggggg
Xi-2
X
X
x
Unconditional Independence Testing
Lagged Dependencies Testing
x²
Porent Set Detection
Return Lagged
X1-2
X2
x²
Input Time Series Data
PCI
MCI
Relations
Causal
XP-2
x
X2
Figure 27: Steps involved in the PCMCI method for time series causal discovery.
4.1.3 PCMCI+
PCMCI+ Ruugge 20200) is an extension of the PCMCI algorithm discover contemporary or instantancous causal links. PCMCI- also assumes causal sufficiency like the PCMCI algorithm. It is also two-stage algorithm where in the first stage, irrelevant edges from the causal model are eliminated. Unlike PCMCI, the edges are removed separately for lagged and contemporary conditioning sets where the contemporary phase employs more CI tests than the lagged phase. In the second stage, PCMCI+ employs the notion of momentary conditional independence (MCT) to improve the selection of conditioning sets for the various CT tests, improving their autocorrelation calibration, and boosting their detection power. The results show that when there high autocorrelation in the data, PCMCI+ can achieve better performance in terms of higher recall, lower false positives, and faster execution compared to the PC algorithm. For lower autocorrelation, PCMCI+ performs almost similarly to PC. Implementation of PCMCI+ is also available in the Tigramite package htttp://gghhabbb.ooo/aaabrrggggg
4.1.4 LPCMCI
Latent PCMCI (LPCMCI) is a constraint based causal discovery algorithm to determine causal relationships from large-scale time scrics data (Gerhardus & Runge (2020)). This is another extension of the PCMCI algorithm as it can discover causal relationships even in the presence of latent confounders. Moreover, it gives the flexibility to use the model when the data is linear nonlinear, and also when the data has lagged or contemporary conditioning sets. The authors identified that when the CT tests have a low effect sizo, existing techniques like FCI suffer from low recall in the presence of autocorrelation. They demonstrated that this issue can be solved by including causal parents in the conditioning sets. By utilizing the orientation rules, these parents can be identified as early as in the edge removal stage. The results show that the proposed LPCMCI method can achieve higher recall than the bascline model SVIR-FCI. However, LPCMCI cannot differentiate all members of the Markov class, and also, when the faithfulness assumption doesn't 'tt hold, LPCMCI might lead to incorrect conclusion. Along with PCMCI and PCMCI+, the Python code of LPCMCI is also available in the Tigramite GitHub package.
4.1.5 CD-NOD
Many existing approaches assume that the causal model is static, and therefore, there will be a fixed joint distribution of the observed data. However, these methods fail when the underlying data changes over time, and causal parameters vary during the period. [uang et al. (2020) proposed causal discovery method that assumes that the parameter of the causal model can change over time or different datasets, and they named the method CD-NOD, Constraint--ossed Causal Discovery from Heterogencous/ satrrngenoous/ooontattinnaa /Nonstttioarryy Data. The proposed method can determine causal direction by taking advantage of distribution shifts, and these distri- bution changes, in the presence of stationary confounders, are helpful for causal discovery. The distribution shifts can be either time or domain indexes and are denoted by a surrogate variable C. Broadly, CD-NOD has two phases where the first phase it recovers the causal skeleton Sc, and in the second phase it orients the edges as per some orientation rules. Given that the causal model offers concise summary of how the joint
33

---

Published in Transactions on Machine Learning Research (09/2023)
distribution changes, they demonstrated that distribution shift contains important information for causal dis- covery. Recently, researchers discovered that this idea could help solve machine learning problems of domain adaptation and forecasting in nonstationary situations (Schölkopf et al. (2012); Zhang et al. (2013)) ). The con- ducted experiments this study demonstrate the changes of causal infiuence between the different states of brain functions, and the empirical results show that. CD-NOD has improved precision and F1 score. However, they didn't consider that the causal directions might flip, and the power of conditional independence tests might reduce because of the distribution shifts. The algorithm's 's source code is available in the following link: www/ciwmeiiiieccc BwwBBBiwiii--- Huang/ Caae/aaasaallaaa -Disllviiscoory from- Non Wow.ooooootttatiiaaraaeeeeeeeeee Hateeooooooeeeeoooooooooeooooo fctps://githin com
Time Series Variables V
Complete Undirected graph Ug
Changing Modules Cm Detection
Phase 2: Identification of Cousal Direction
Skeleton Graph Sg Detection
x²
Surrogate Variable C Pooee Index)
Phose 1
Figure 28: Illustration of CD-NOD's phase-1.
4.1.6 CDANs
Ferdous et al. (202bb) introduces a constraint-based causal discovery approach called CDANs for aulocor- related and stationttoay time series data that handles high dimensionality issues. The method identifies both lagged and instantancous causal edges along with changing modules that vary over time. By optimizing the conditioning sets in constraint-based search, and also considering lagged parents instead of condition- ing on the entire past, it tries to address the high dimensionality problem. CDANs first detect the lagged adjacencies, then identify the changing modules and instantaneous adjacencies, and finally determine the causal direction. The code to implement this method available at https: /tt///gtttbbbb com woom//ferdoussCDAi An extended version of this study is presented in Ferdous et al. (2023a), where the method called eCDA Ns is introduced that is capable of detecting lagged and instantaneous causal relationships along with temporal changes. The method eCDANs addresses high dimensionality by optimizing the conditioning sets while con- ducting CI tests and identifies the changes in causal relations by introducing a proxy variable to represent time dependency.
4.2 Functional Causal Model (FCM)-based
4.2.1 VarLiNGAM
VarLiNGAM Hyvärinen al. 2010 combines the non-Gaussian instantancous models with autoregres- sive models and shows that non-Gaussian model is identifiable without prior knowledge of network strue- ture. It estimates both instantaneons and lagged causal effects in models that are an example of struc- tural vector antoregressive (SVAR) models. Those models are a combination of structural equation mod- els (SEM) and vector autoregressive (VAR) models. VarLiNGAM also shows that taking instantaneous influences into account can change the values of the time-lagged coefficients to a great extent. Thus, neglecting instantaneous influences can lead to misleading interpretations of causal effects. It also as- sesses the significance of the estimated causal relations. An implementation of this method is available html
al:
4.2.2 TaMINo
Time-series Models with Independent Noise (TiMINo) (Peters el al. (2013) studies a class of restricted structural equation models (SEMs) for time-series data that include nonlinear and instantaneous effects. It assumes X, be a function of all dircct canses and some noise variable, the collection of which is supposed be jointly independent. The algorithm is based on unconditional independence tests and is applicable to multivariate, linear, nonlinear, and instantaneous interactions. Tf the model assumptions are
34

---

Published in Transactions on Machine Learning Research (09/2023)
not satisfied by the data, TiMINo remains mostly undecided instead of making wrong causal decisions. While methods like Granger causality are built on the asymmetry of time direction, TiMINo additionally takes into account identifiability emerging from restricted SEMs. This leads to a straightforward way of dealing with unknown time delays in different time series. An implementation of TiMINo is available in this repository: https: wttpelu...ooo.aaaeeeeeeeeeeeeeee cot///aasaaaad//aaaaal oaaaaaaaee for time series
4.3
Cradient-based
4.3.1
DYNOTEARS
Parnfil et al. (0020) proposed the Dynamic NOTEARS (DYNOTEARS) which is a structure learning ap- proach for dynamic data that simultaneously estimates contemporaneomt (intra-slice) and time-lagged (inter- slice) relationships between variables in a time-series. DYNOTEARS revolves around minimizing a penalized loss subject to an acyclicity constraint. The optimization finds the conditional dependencies that are best supported by the data. It leverages insight from the approach NOTEARS (Zheng al. (2018) which uses an algebraic characterization of acyclicity in directed graphs for static data. The assumptions made by DYNOTEARS include that the structure of the network is fixed through time, and is identical for all time series in the data. This approach is scalable to high-dimensional dalasets. An implementation of this approach is available in the CausalNex library (https://githie com /uwntuublacklaass/ also at httpp:://git tiuth..th.h.oo com/ haam//cassaaacuuseeea causal discovery for time_series series
and
4.3.2 NTS-NOTEARS
NTS-NOTEARS (Sun et al. (0211) is causal discovery method for time series data. that uses 1-D convolutional neural networks (CNNs) to capture linear, nonlinear, lagged, and instantancous relations among variables in time series data along with ensuring the acyclicity property of a DAG. It ex- tends the continuous optimization- DAGs, and adapts the acyclicity constraint from that approach. assumes that there are no latent confounders the data, and the underlying data-generating process is fixed and stationary over time. NTS-NOTEARS is faster than other constraint-basel methods because of the use of nonlinear conditional independence tests. It incorporates prior knowledge into the learning process promote the use of opti- mization constraints convolutional layers for better casual discovery. Its implementation is available at: hanpa/ooooooiiaaaauusoa//7/////0
approach NOTEARS for learning nonparametric instantaneous
4.4 Granger Causality (GC)-based
investigated the causal relationships between the variables in a time series data which is known as Granger Causality (GC). It is based on the basic assumption that couses precede their effecls. The author defines GC as follows: A time series variable X causes X2, if the probubility of X conditional on its own past, and the past of X (besides the set of the available information) does not equal the probability of X conditional on ils own past alone. The GC test can't be performed directly on non-stationary data. The non-stationary data needs to be transformed into stationary data by differencing it, either using first-order or second-order differencing. Granger Causality can be used when there are no latent confounders, and also, no instantancous effects exist, i.c., no variable causes another variable at the same time stamp.
Granger 1969
4.4.1 GVAR
Generalized Vector AutoRegression (GVAR) Marcinkeviës & Vogt 2021 is a framework for inferring mul- tivariate Granger causality under nonlinear dynamics based on autoregressive modeling with self-explanning neural networks. It allows the detection of signs of Granger-causal effects and inspection of their variability over time addition to relational inference. It focuses on two aspects: first, inferring Granger-causal rela- tionships in multivariate time series under nonlinear dynamics, and second, inferring signs of Granger-causal relationships. A reproducible code of the approach is available at: htttp:://gi httphh/wwcccmm/09244///////a
35

---

Published in Transactions on Machine Learning Research (09/2023)
4.4.2 NAVAR
Bussmann et al. ) proposed the approach Neural Additive Vector AutoRegression (NAVAR) which is a causal discovery approach for capturing nonlinear relationships using neural networks. It is particularly trained using deep neural networks that extract the (additive) Granger causal influences from the time evolution in multivariate time scries. NAVAR assumes an additive structure where the predictions depend linearly on independent nonlinear functions of the individual input variables. These nonlinear functions are modeled using neural networks. The additive structure of NAVAR allows scoring and ranking the causal relationships. Currently, NAVAR is implemented with MLPs and LSTMs as the backbone using Python which is available at: https:://gitae such as dilated CNNs and transformers can also be used to model NAVAR.
However, more complex architectures
4.4.3 ACD
Most causal discovery algorithms applied for time-series analysis find a causal graph for the data, and then refit the model whenever new samples do not fit with the underlying causal graph. But in many cases, samples share connections among them, for example, the brain activity of different regions al different times. When the algorithms fit a new model, this dynamic nature between the samples is lost, and can no longer identify the actual causal relation. To solve this problem, Löwe et al. (2022) proposed the Amortized Causal Discovery (ACD) technique which can identify the causal relations when samples are from different causal graphs but share common dynamics. ACD consists of an encoder and decoder. The encoder predicts the causal graph's is edges by learning Granger causal relations, and under the assumed causal model, the decoder simulates the dynamics of the system for the next timo-step. Implementation of the model is available at: /t/ httpa//.w......eeeeeecaaaaaaaaaa
4.5
Miscellaneous Approaches
4.5.1
oCSE
Causal network inference by Optimal Causation Entropy (oCSE) (unn et al. (2015a)) is based on the optimal causation entropy principle which utilizes a two-step process (aggregative discovery and progressive removal) to jointly infer the set of causal parents of each node. It proposes a theoretical development of cousation entropy, an information-theortts statistic designed for causal inference. Particularly, it proves the optimal causation entropy principle for Markov processes which is as follows: the set of nodes that directly cause a given node the unique minimal set of nodes that marimizes cousation entropy. This principle transforms the problem of causal inference into the optimization of causation entropy. Causation entropy can be regarded a type of conditional mutual information designed for causal structure inference which generalizes the traditional, unconditioned version of transfer entropy. Causation entropy when applied to Gaussian variables also generalizes Granger causality and conditional Granger causality. An advantage of the method oCSE is that it often requires a relatively smaller number of samples, and fewer computations to achieve high accuracy. Due to ils aggregative nature, the conditioning set encountered in entropy estimation remains relatively low-dimensional for sparse networks. An implementation of the oCSE algorithm is available on this website:
4.5.2 TCDF
Temporal Causal Discovery Framework (TCDF) (Nauta et al. (2019) is a deep learning framework that discovers the causal relationships in observational time series data. Broadly, TCDF has the following steps: (i) Time series prediction, (ii) Attention interpretation, (iii) (a) Causal validation, (iii) (b) Delay discovery, and (iv) Temporal causal graph construction. TCDF consists of N independent iitentiionbbsse convolutional newral networks (CNNs) all with the same architecture but a different larget time series. Each network receives all observed time series as input. The goal of each network is to predict one time series based on the past values of all time series in the datasct. A time scries X, is considered a potential cause of the target time series X, if the attention score is beyond certain threshold. By comparing all attention scores, a set of potential causes is formed for each time series. TCDF validates whether potential cause
36

---

Published in Transactions on Machine Learning Research (09/2023)
(found by the attention mechanism) is actual cause of the predicted time series by applying causal validation step. TCDF uses permalalion imporlance (PT) as a causal validation method which measures how much an error score increases when the values of variable are randomly permuted. Finally, all validated causal relationships are included in a temporal causal graph. TCDF learns the time delay between cause and effect by interpreting the werwork's kernel weights. This framework has experimented with simulated financial market data and FMRI data. It discovered roughly 95-97% of the time delays correctly. However, it performs slightly worse on short time series in FMRI data since a deep learning method has many parameters to fit. An implementation of TCDF can be found at: https: /etgt/gttttu////e www/toNaattaannnn Nauta/TCDF
Causal Validation
Step 3(0)
X1
Time Series
Attention Interpretation
Step 4
2
X2*
Prediction
Step 3(b)
Delay Discovery
X2
X3
x3
Step
Step 2
5
Input
Output
Figure 29: Interpretation of how the TCDF (Nauta et al. (2019)) method works. The numbers the causal edges denote the time delay between the cause and effect.
4.5.3 NBCB
Noise-based, Coise-based/Consttee /Constraint-based approach is hybrid approach that learns summary causal graph from observational time series data without being restricted to the Markov equivalent class even in the case of instantaneous relations. A summary causal greph is one that represents the causal relations between time series without including lags. That is, it only represents the cause-effect relations in a given time series without the time delay between the cause and the effect. To find the summary graph, NBCB uses hybrid approach which is divided into two steps. First, it uses bosse-based procedure find the potential causes of each time series under the assumption of additive noise models (ANMs). Then, it uses constraint- causal graph. The second step is based on new temporal causation entropy measure proposed by this study that is an extension of the causation entropy to time series data for handling lags bigger than one time step. Furthermore, this study relics on a lighter version of the faithfulness hypothesis, namcly adjacency faithfulness. An implementation of NBCB is available in the site https://githii: com/ccassaad//aaaccccccccaoo cauasaaddcaussa.. discovery for time series
NBCB (ssaad et al. (0021)
approach to prune all unnecessary causes and hence ends up with oriented
4.5.4 PCTMI
PCTMI Assaad et al. 2022a) is an entropy-based approach that discovers the summary causal graph for time series data with potentially different sampling rates. To do so this study proposes a new temporal mutual information measure defined on a Hindow-based representation this mcasure relates an entropy reduction principle that can be seen as a special case of the probabilistic missing principle. PCTMI combines these two concepts in PC-like algorithm (Spirtes al. (2000b)) to construct the summary causal graph. PCTMI focuses particularly on the summary graph, rather than the full-time graph. It has mainly two steps: (t) Skeleton construction and (ti) Edge orientation. The skeleton construction as well as the orientation of instantaneous relations is similar to the PC algorithm but adapted for time series data. To orient the lagged relations, it uses the rules of an entropic reduction (ER) principle (Michalos 1972)). )) PCTMI assumes both the causal Markov condition and faithfulness of the data distribution, common assumptions for constraint-baser CD approaches. An implementation of PCTMI is available on this website: |uttps://github. com/ ckasssad/ causal www.ldddsssseeeeeeeeeeee for time _eeeeeserre____eee
time series. Then shows how
The methods discussed above use different strategies to perform causal discovery under variety of settings and assumptions. Therefore, present comparative analysis of some of the common approaches in Table 7 based on their assumptions, output, techniques used, advantages, and disadvantages.
37

---

Published in Transactions on Machine Learning Research (09/2023)
Non com-sttttionaity property is not bandled
Contemporannon edges is uol identifed,, some causal liniss remain moorented
May lead to wrong concluston faithfulaee is violated, can't distingnissh all members of MBC Some caueal directions may not be identifiable, if the identifiabriit conditions not satisdied
Hidden confounders hand led, and inapplicable to non- not-linest data
Rigid about the mocll asstntppu easuttptions potions, somelinms remain deciedee
Undersam plannpingg not handled well, inapplicable to non- linelieeer data
Inspplicable when there rodats Intent confounders
Produced score. nntrrxx can be analysed only by the Causede pla forrm Takes very long
Litte for dense graphs
Performs alightl worse short time series,
does not cosure acyclicity
not estimate full-time cansel graph
Does not estimate full-time causal graph
Some caussll linles remain unoriented
Disadvantage
Handles hidden confounders
Hondles bigh-dimensionn ninionall uel wetworkss applicablee linsur
or tonlinear, and conti montimuons discrote data
Dotects both contemporanees and lagged causel links
Handles large- scale time series dala, lateni confourdeess and discrete/cone htr//enttinnsss.. salued data, incorporates prior knowledge
Detects changing muculess
Applicable to mullvvaciate linear, neni nonlinear ineer and instantan cous cases
Sralable high-dimensionn datasets, producos both bothlagged lagged and instantaneous edges
Incorporates prior knowleds ledge
Easy to implement, can detoet nonlinear relations
Often requires a relatively smaller number of samples
Easy to imppleeent, can detect hidden confounders
Deterts both lagged and instantaneout temporal edges
Lower complexity
Advantages
restricted to the MEC
Table Comparison of some consell discoveryy algorithms for time datn.
Hybrid (constraint and noise- coise-based), causation entropy Constrain nt- www.aatt--hoooooo sonstruction hosod,, , skenleton
PC, ER. principle to orient lagged edges
Cous Cruitrsint- bossseed momeentryy CI (MCI) test
Technique used
Cons Constraint- basedd, adaptation for tlmee series les data
Constraint basod, MCI test
Constraint hassdd
Constraint- lassed
FCM/SEM-- baseed
FCM FCM/SEE /L///SE--MR bassri
Score- based approsch
Grudient based, me0e CNNNs
Granger- lity based
Optimal Causation Entropy principle
Atsention- based CN Ns
Outcome Graph
Partial ancostral graph
Full Lime graph with lagged edges
Full time graph with logged and contemporaneeo edges
Time sories directed maxiinal ancesdral graphs (DMAGs)
Summary or full sime graph incorporating the changing modnles
Full tilttmme ranneal DAG (with causal strengt lhs)
Causal summary time graph
Full time causal graph
Pull time graph
Full time causal graph
(with lagged edges only)
Summary causal graph
Pull time graph
Summary causal graph
Summary causel graph
Independent nnise, identifiahiltty
and identical for all time series in the data No lateul coufounder ere. DGP fixed
Causal Markoy condition, faithfulness
Cauusal faithfuluest absenne selection bias
Psoudo Causel Sufficency, fulnes, no selection hins
DGP is lintar, there are unobservnd confounders and non- non-Cousall Causslan nolses with no1 2e10 vatiances
Acyelicity, notwork structure is fixer through
Faithfulness, Acyolicity
Temporal precedence: the caasse precedes ins effect
Causal Markov condition and faithfulness
stationacily, cautell sufficiency
Causal suffielency
stationary over time.
Additive structure
Assimption
Ad Jajaeeccy
faithfulness
NTS-NOTEARS
VALLNNAM
DYNOTEARS
Methods
tsFCI
PCMC1
PCMCI+
LPCMCI
CD-NOD
TIMINO
NAVAR
OCSE
TCDF
NBCB
PCTMI
38

---

Published in Transactions on Machine Learning Research (09/2023)
5 Evaluation Metrics for Causal Discovery
In this section, discuss the common metrics used to evaluate the performance of causal discovery algorithms. These metrics are common for both LLD. and time series causal discovery evaluation.
Structural Hamming Distance (SHD): SHD the total number of edge additions, delctions, or reversals that. are needed convert the estimated graph G' into ground-truth graph G (Zheng et al.) (2018p; Cheng et al. (2022)). It estimated by determining the missing edges, extra edges, and edges with incorrect direction in the produced graph compared to its true graph. A lower hamming distance means the estimated graph is closer the true graph, and vice versa. An estimated graph is fully accurate when its SHD = O. We show the calculation of SHD for the graphs in Figure 30 using the formula in Equation [4] where A = total number of edge additions, D = total number of edge deletions, and Rt = total number of edge reversals. In Figure 30, we need to add the edge D + C, delele the edges D - B and D + A, and reverse the edges C' + B and C + in the generated graph (graph b) to convert it into the true graph (graph a). Therefore, the SHD graph (graph a).
+ 2 mcans a total of actions are required reach the truc
SHD A+ D
(14)
(a)
(b)
Figure 30: (a) Ground-truth graph G, and (b) Estimated graph G'.
Structural Intervention Distance (SID): SID is distance metric for DAGs proposed by Peters &
Bühhmann 2015). It measures the closeness between DAGs in terms of their capacities for causal effects. Specifically, computes the number of falsely inferred intervention distributions (Cheng et al. (2022) to
reflect how false edges in the generated graph can influence the effects obtained.
False Discovery Rate (FDR): FDR the expected fraction of false discoveries among all the discoveries. In terms of causal discovery, FDR represents the ratio of the extra edges over the of the true edges and extra edges. Here, extra edges mean the edges that are present in the estimated graph but not present in the actual graph the false positives (FP), and true edges mean edges that are present in both the graphs or the true positives (TP). The lower the FDR, the better the performance of causal discovery.
FP FDR = FP
(15)
True Positive Rate (TPR): TPR denotes the proportion of the positives in the data correctly identified positives. In terms of causal graphs, TPR is the ratio of the edges in the estimated graph that are also present in the true graph (TP) to the total number of true edges (true positives (TP) and false negatives (FN)). The higher the TPR of an estimated graph, the better the discovery.
TP
TP TP + FN
TPR = Actual
(16)
False Positive Rate (FPR): In general terms, FPR is the proportion of negatives that are incorrectly identified as positives. In terms of causal graphs, FPR is the ratio of the false edges produced by the estimated
39

---

Published in Transactions on Machine Learning Research (09/2023)
graph that absent in the true graph (false positives/extra edges) over the sum of true negatives (TN) and false positives (FP). The lower the FPR, the better the causal discovery performance.
FP
FP
FPR = ActualNegabin
(17)
FN
Precision returns the proportion of true positives (TP) among all the values predicted as positive. That is, out of all the positives predicted, what percentage is truly positive. In terms of causal discovery, precision the fraction of the correct or semi-correct edges over all the produced edges (Shen
Precision:
et al. 2020)).
TP
Precision
(18)
FP
Recall: Recall returns the proportion of the correctly predicted positive values. That is, out of the total positives, what percentage are predicted as positive? In causal discovery, recall is the fraction of edges in the ground-truth graph that are correctly or semi-correctly estimated (Shen et al (2020)). The recall metric is the same as TPR.
TP Recall TP+ + FN
(19)
F1 Score: The F1 score metric combines the precision and recall metrics into a single metric. It is the harmonic mean of precision and recall and is mostly used in cases of imbalanced data.
2ТP
F1 scorE = 2TP + FN+FP
(20)
Matthews Correlation Coefficient (MCC): MCC is a single- metric that summarizes the con- fusion matrix. It takes into account all four entries of the confusion matrix (TP, TN, FP, and FN). The value of MCC is 1 when the discovery of edges is fully accurate (FP = FN = 0), indicating perfect causal discovery. On the contrary, when the algorithm always misidentifies (TP TN = 0), then the MCC -1, representing the worst possible discovery. Thus, the MCC value lies between -1 and 1.
TP x TN- - FP x FN VITN+ +FN((F+++ TP)(TN + (P) (P)N++TP))
MCC=
(21)
From the above-listed metrics, the SHD metric more insightful compared to the others as allows us know how far the estimated graph is from the ground-truth graph. SHD provides insight into the total number of modifications that need to be done in the estimated graph to transform it into the ground-truth graph. The MCC metric is also good in terms of summariking the outcome of a CD algorithm as it is the only metric that takes into account all of TP, TN, FP, and FN. The F1 score metric is quite useful too as it combines the precision and recall metrics. One should consider using the SHD metric in order to understand how far the estimated graph is from the ground-trutt graph. The TPR metric can be used if one interested only knowing the proportion of the true edges discovered. One can use the FDR metric get an idea about the proportion of the false estimated edges by the algorithm. However, consideration of only a single metric for the performance evaluation of the algorithms can be problematic. A single metric can not fully express the actual performance of the approach.
6 Datasets for Causal Discovery
There are a couple of benchmark causal discovery datasots from different domains that are often used for the evaluation of causal discovery approaches. In this section, we discuss briefly some commonly used I.I.D. and time series datasets.
40

---

Published in Transactions on Machine Learning Research (09/2023)
6.1 I.I.D. datasets
ASIA: ASIA is synthetic dataset, also known the Lung Cancer dataset (Lauritzen & Spiegel- halter (1888) ). The associated graph (Figure 31 (a)) is small toy network that models lung cancer in patients from Asia. Particularly, it is about different lung diseases (luberculosis, lung cancer, or bronchitis), their relations to smoking, and patients' visits to Asia. This dataset is often used for benchmarking causal graphical models. The ground-truth graph has nodes and edges. Lippe ct al. (2021), and Hasan & Gani (2022) have used this dataset for the evaluation of their approaches. It. is available here: lnttps://wwt bnlearn. com ber wwtp:/breeeiiioe wwwsitory.///peeeooo wwwprry/ddsireteeereeeeee seseessmall.... htm.hmmlll.m #asia
LUCAS: The LUCAS (Lung Cancer Simple Set) is a synthetic datasct that contains toy data generated artificially by causal Bayesian nelworks with binary variables (Lucas et al. (2004)). Here, the target variable is Lung Cancer. The data-generating model of the LUCAS dataset is Markov process, which means that the state of the children is entirely determined by the state of the parents.
The ground-truth graph (Figure 31 (b)) is a small network with 12 variables and 12 edges. Hasan Gani (2022) used this dataset to evaluate their framework. The dataset and ground truth can be found here: httpa://wwit causality. wtw.. Ch/data/LUCna html
Visit
Smoking
Arwinty
Peer Pressure
Sonatics
Asia
Aflera
Smoking
Attension Disorder
lung Cancer
Tuberculosis
Teilow Fingers
Fung Born Pven Day
Coughing
X-ray results
Dyspineo
Car Assident
Tuberculosis lungcancer
Fatigue
Figure 31: Ground-truth network of the ASIA (left), and LUCAS (right) datascts.
SACHS: SACHS (Sachs et al. (2005) is real dataset that measures the expression levels of multiple phosphorylated protein and phospholipid components in human cells. It is the most commonly used dataset for evaluating causal discovery approaches. It has a small network with 11 nodes and 17 edges (Figure 32 The dataset has both observational and interventional samples. Most of the CD approaches use the n = 853 obscrvational samples to evaluate their mothod. This dataset has been used by many approaches such as Zheng et al. (2018), Zhu et al. (2019), Ng al.] (2020). Lachapelle et al. (2019) & Ng et al. (2022), Lippe al. (0221) for evaluation purposes. Link: https://www, bnl earn. www.bonrrpsitttr/rraaiooooo small html#sachs
PMC
Mlg
PIP2
I4+k
Erb
Ale
Figure 32: Ground-truth network of the SACHS dataset.
The CHILD (Siiegehhatter et al. 1993) dataset is medical Bayesian network for diag- nosing congenital heart disease in a newborn "blue baby". The ground-truth network is a medium graph that consists of 20 nodes and 25 edges (Figure 34.. The dataset includes features such as patient demographics, physiological characteristics, and lab test reports (Chost X-ray, CO2 re- ports, etc.). This dataset was used by Lippe al. (2021) in their study, and can be found here: https: ://www//wwww. bnl maleern.ccm hwt.:///aaneppaaoorr//sseeeeeeee
CHILD:
41

---

Published in Transactions on Machine Learning Research (09/202))
Die d'AAppyyr
Sick
DactFlow
frbling
JunpPtaranch
FunggFiw
Age
Grunting
HypDlistib
Hyposioln(12
Chesttray
LVHinoport
Granting
LowerBudy
C02Meportt
XiayRaport
Figure 33: Ground-truth network of the CHILD dataset.
ALARM: Logical Alarm Reduction Mechanism (ALARM) is a patient monitoring system (Bein- lich et al. (1989)) designed to provide alarm message for patients, and has associated syn- Thetic dataset. In particular, it implements cautionary alarm message for patient monitoring. The ground-truth graph is a medium-sized network with 37 nodes and 46 edges. This dataset was used by Yu et al. (2019), and Cai et al. (2013) to evaluate their approaches. The ground-truth network available in this repository: https:// www..///ew.bb.a.....mmmamabaaaae bnlearn. com/barepositoryy/
HEPAR2: It is a probabilistic causal model for the diagnosis of liver disorders (Onisko 2003
This causal Bayesian network tries to capture the causal links among different risk factors, diseases, symptoms, and test results. The ground-truth graph is a large network with 70 nodes and 123 edges which is available in the bulearn (Scutari (2009]) repository: /https://wit bnlearn com/
bnrepository/discreee- large. html#hepar2
6.2 Time Series datasets
MMRI datasets: Functional Magnetic Resonance Imaging (IMRI) is popular approach to inves- tigating dynamic brain networks (Cao et al. (019)). Different types of fMRI data are often used to evaluate time-series causal discovery approaches. ZZhang et al. (2017) used the fMRI Hippocam- pus dataset (Laumann et al. (2015)) that contains signals from six separate brain regions. Nauta eet. al. (2019) used a simulated blood oxygen level-dependent (BOL.D fMRT dataset that has 28 different underlying networks from 50 brain regions. measures the neural activity of different brain regions based on the changes in blood flow. |Huang et al. (2020) tested their approach us- ing the task fMRI data learn information flows between brain regions, and how causal influ- ences change across resting state and task states. Some simulated fMRI data. is available here: https://githuu: http://///aaaaaaa/o/////e/aaaaa/
CauscMe Earth Sciences data: CauscMe (Muñoz-Marí et al. (2220)) a platform that contains benchmark causal discovery datasets evaluate, and compare the performance of different CD approaches. It contains datasets generated from both synthetic models mimicking real challenges and real-world data sets from the earth science domain where the ground-truth network is known with high confidence. Bussmaan et al. (2021) used different datasets from the CauseMe platform in their study. Specifically, they used the synthetic nonlinear VAR dataset, the hybrid climate and weather dataset, and the real-world river run-off dataset to evaluate their algorithm. It was also used by Runge al. (2099) their experiments. The datasets can be found at: https://causer: uv es/
causaLens datascts: Lawrence et al. 2021 from causaLens proposed a framework for generat- ing synthetic time series data with a known ground truth causal structure for evaluating time series causal discovery approaches. They have an open-source repository (nttps://githi) com/ Gausalense/dan1-nnuiipp////
that captures the source code and datasets of their proposed frame- work. Datasets can be generated specifying different assumptions (causal sufficiency, L.ID.,, instan- taneous effects, etc.) using example script in the repository. This facilitates the users to generate
42

---

Published in Transactions on Machine Learning Research (09/2023)
data as per their roquirements. Located in England, causaLens is leading software company with focus on developing intelligent machines based on causal AT.
DREAM3 challenge datasets: DREAM3 Priil et al. (2010)) is a simulated gene expression dataset often used for evaluating time-series causal discovery algorithms. It has five different datasets of E. coli and yeast gene networks (Ecolil, Ecoli2, Yeast1, Yeast2, and Yeast3), cach consisting of maximum of 100 variables. [Bussmann el al. (0021) used this dataset to evaluate their approach. Every dataset has 46 time series and every time series consists of only 21 timesteps. Some of these datasets can be found here: httpp://gitthb.cr wwt..///babbbuuaann//aaaaaaaaaaa
Stock market datasets: Stock market datasets contain multiple continuous time series data which are very useful to assess temporal causal discovery algorithms. Huang et al. (2020) used two different stock market datasets downloaded from Yahoo Finance to test their approach. It contains daily returns of stocks from Hong Kong and the United States. Link to a simulated Finance dataset from the study by Nauta et al. (2019) https://github. cww. httpaa////D///eeeeetttterrre///e Finance
7
Benchmarking Causal Discovery Algorithms
In this section, we report the performance of some common causal discovery approaches on I.1.D, and time scries datascts. We compare the approaches in terms of three common metrics: SHD, TPR, and FDR.
7.1 Experiments on I.I.D. data
For causal discovery on the I.I.. datasets, we choose the following commonly used datasets with available ground-truth graphs: ASTA (small network), CHILD and ALA (medium networks), and HEPARE R2 (large network). The CSV version of the datasets and their corresponding ground-truths are available in the causal- learn repository: httts:///gtti:
The causal discovery approaches that are benchmarked for the I.LD. datasets are: PC, GES, LiNGAM, Pirect-LiNGAR NOTEARS, DAG-GN GNN,, GraN-DAG, GOLEM, and MCSL. The implementations of the algorithms have been adopted from the gCastle (Zhang et al. (021aa) package.
coom/py-whj haa-shhccausl-laarr
Table 8: The benchmarking of some common causal discovery algorithms for L.I.D. datasets. The best results w.r.t each metric (SHD, TPR, and FDR) are boldfaced. Lower SHD and FDR are betler, while higher
TPR signifies better performance.
ASTA
CHILD
ALARM
HEPAR2
Methods
SHD
TPR
FDR
SHD
TPR
FDR
SHD
TPR
FDR
SHD
TPR
FDR
PC
0.6
0.3
43
0.24
0.86
0.67
0.6
172
0.35
0.75
GES
0.63
0.38
34
0.38
0.89
0.74
0.61
0.5
0.23
LiNGAM
7
0.25
0.6
23
0.28
0.63
43
0.43
0.55
111
0.1
0.32
Direct-LiNGAM LINGAM
0.5
0
28
0.12
0.82
40
0.39
0.5
110
0.1
0.07
NOTEARS
0.13
0.83
22
0.16
0.64
0.17
0.38
123
DAG-GNN
7
0.25
0.5
24
0.24
0.7
39
0.196
0.31
123
0
1
GraN-DAG
0.13
0
24
0.04
44
0.044
0.75
122
0.008
GOLEM
11
0.25
0.75
49
0.2
0.88
60
0.26
0.71
157
0.05
0.89
MCSL
19
0.5
0.82
140
0.56
0.91
164
0.72
0.93
1743
0.45
0.97
From the results reported in Table g we that for the ASIA dataset, both GES and Lirect-LiNGAM approaches have the best (lowest) SHD. MCSL on the other hand has the worst (highest) SHD for ASIA. For the CHILD dataset, NOTEARS performs the best w.r.t. SHD, and once again MCSL has the worst SHD. A reason for the poor performance of MCSL could be due to its tendency to produce as many as possible edges without caring much about the false positives. DAG-GNN has the best (lowest) SHD for the ALARM dataset, and once again GES outperforms others with the lowest SHD in the case of the HEPAR2 dataset. In terms of TPR, GFS, and MCSL both outperform others twice. That is GES has the best. TPR for
43

---

Published in Transactions on Machine Learning Research (09/2023)
ASIA
CHILD
ALARM
HEPAR2
ASIA
CHILD
ALARM
HEPAR2
1.00
500
3.75
SHD (lg 9oal)
100
60
3.50
0.25
UINDAM
DimotL/NAA
NOTBARS
GrAMDAGG
GOLEM
NCSL
3.00
DAG
LiKaad
Direc LacsLaou. AM
NOTEARS
MCJL
Approaches
Approaches
ASIA
CHILD
ALARM
HEPAR2
1.00
0.75
0.50
FDR
0.25
0.00
GBS
UADDA
Dieck
NOTEARS
DAG-Ow
GrakDAG
GOLEM
Approaches
Figure 34: SHD, TPR, and FDR plots of the different benchmarked approaches some L.L.D. datasets. Lower SHD and FDR are better, while higher TPR signifies a better performance.
the ASTA and ALARM networks, and MCSL has the highest TPR for the CHILD and HEPAR2 networks. With respect to FDR, GraN-DAG outperforms the other algorithms with the lowest FDR in the case of all the datasots except the ALARM datasct. DAG-GNN has the best FDR in the case of ALARM. PC and GES seem to do well comparatively for the datasets with small graphs. Gradient- NOTEARS, DAG-GNN, and GraN-DAG seem to be on par w.r.t. the SHD metric across all the datasets. However, the metrics of all the approaches in the case of the HEPAR2 dataset which has a large ground- truth network are quite poor. This signifies that most of the existing approaches are not fully sufficient to handle large or very large networks, and should focus on improving their scalability. The development. of new approaches should consider the scalability factor of the algorithm so that they can handle real-world large networks having 100 to 1000 nodes.
methods such as
7.2 Experiments on time series data
We compared the performance of some temporal causal discovery algorithms namely PCMCI, PCMCI+ VarLiNGAM, DyNOTEARS, and TCDF on two time series datasets. The first dataset is the Syn-6 data which is a synthetic dataset with 6 variables and a lag period of 2. The details of data generation can be found the study Ferdous et al. (2023b). The second dataset. fMRT data with 10 variables having a lag period of Please refer to the study Nauta et al. (2019) for the details of this dataset. The ground- truth graphs of both datasets are also available in the listed studies. Some of the temporal algorithms only produce summary causal graphs that lack any information about the time lag between the cause and effect. Since both of our experimental datascts have ground-truth graphs with specified time lags, we tested and compared only those temporal algorithus that specify the time lags (i.e. produce full-time causal graphs). The implementation of the PCMCI and PCMCI+ have been adopted from the following repository: https::// tht.tbb..ttuu..... www/ http///aaooouugeggraaaa.tt
VarLiNGAM and DyNOTEARS from hitps:: //gi com/ cwtssaadasaaaaaaaaaaaaaaaaaaaaaa causal www.saaalsssaaarraaaaaaaaaaaaaa. discovery_foo for__rfo_r_____ tite_ttmm______________ee sime_seriest and TCDF from https://githut com/ M- N-NNutat//CDFFF The performance metrics from the conducted experiments reported in Table g
44

---

Published in Transactions on Machine Learning Research (09/2023)
The benchmarking of some common causal discovery algorithms for time series data. The best rosults w.r.t each metric (SHD, TPR, and FDR) are boldfacod. A lower SHD and FDR are better. While
Table 9:
higher TPR signifies better performance.
Syn-6 data
fMRI data
Methods
SHD
TPR
FDR
SHD
TPR
FDR
PCMCI
14
0.63
0.69
61
0.52
01.82
PCMCI+
11
0,50
0.63
26
0,43
0.61
VarLiNGAM
15
0.50
0.73
30
0.48
0.66
DyNOTEARS
28
0.83
0.83
95
0.81
0.84
TCDF
10
0
1
27
0.38
0.64
Syn-6 data
IMRI data
Syn-6 data
1MRI data
Syn-6
1MRI
100
1.00
1.00
75
0.75
0.75
50
0.50
0.50
25
0.25
0.00
POMCI
POMcH
VarL.NGAM
DyNOTEAR
TGDF
POWCI
PONCH
VarLINAAM
DyNOTEAR
TCDF
PCMC
PCMC
VarLINGAM
DyNOTEAR
TODF
Approaches
Approaches
Approaches
Figure 35: SHD, TPR, and FDR plots of the benchmarked approaches the time series datasets. A lower SHD and FDR are better. While higher TPR signifies better performance.
The above results demonstrate that PCMCI+ performs the best in the case of both datasets w.r.t. the metrics SHD and FDR. This signifies that PCMCI+ produces lower false edges compared to the other approaches. DyNOTEARS has the best TPR in the case of both datasets. This signifies its ability to discover more true edges than others. However, it docs not perform well in terms of SHD and FDR. TCDF performs very poorly in the case of the Syn-6 data. It couldn't discover a single true edge which causes its TPR to be 0 and a very high FDR. Although in the case of fMRI data, it has good SHD and FDR, it still has the lowest TPR signifying its tendency to produce low amount of true odges.
Table 10: Performance results of two other temporal causal discovery algorithms. These are compared separately since the edges produced by these methods do not provide any time lag information.
Syn-6 data
fMRI data
Methods
SHD
TPR
FDR
SHD
TPR
FDR
oCSE
0.75
0.54
15
0.48
0.29
GrangerPW
15
1
0.65
19
0.57
0.45
We further tested the ability of some temporal algorithms which only produce summary time graph their outcome. Their performance results are reported in Table 10 The graphs produced by these methods do not incorporate any time lag information. Hence, only partial information may be obtained from these summary graphs. From the empirical results, we see that in the case of both datasets, oCSE performs better than GrangerPW in terms the SHD and FDR metrics. While GrangerPW outperforms oCSE in both cases w.r.t. TPR.
8 Tools for Causal Discovery
We briefly introduce the tools and software publicly available for users to perform causal discovery. These tools include the implementations of some benchmark causal discovery approaches as well famous datasets, and commonly used evaluation metrics. Please refer the table in the following page for the details of the tools software packages.
45

---

Published in Transactions on Machine Learning Research (09/2023)
Also, contains famous benchmark networks in different formats such as BF,, DSC, NET, RDA, and RDS. . Link: https: / /ww..www...... bu anlearn. .com/
Causal Discovery Toolbox has algorithms from the balearn package, pealg packages, etc. based on observational data.
. implements state-offthe art CD approaches and relevant useful APIs. Also implements Cl
Inc Includes some recently develop oped gradient- bas-bbaeeeee. causal discovery methods with optional GPÚ acceleration.
Contains functions that allow users, eexperts to add the known causal edges or remove the false edges model the Mlansiis better.
. Allows graph creation by hand, using a random graphi generator, or a search algorithu. It has esor-friendly GUI which allows users to input. data and background knowledge and it outputs the causal graph based on the search algorithm selected by the user. It also allows learning the generated graph's parameters.
2017 * Implements Mixed Graphical Models (MGMs) to learn cansal connections from directed or undirected graphs. Provides framework for learning cansal structure from mixed data (both continuous and discrete). . Link: https://gii /ttp///ttbbbb/// comm http/bbnoslll aaanoslab/aao wwc.ccasaaaaaooaa 1KGM
implements CD algorithms (FGES, GFCI, RFCI, FCI, etc. for contimtons datn, discrete data, and mixed data.
Provides general API for the four steps of causal inference (modeling, identification estima- tion, and refutation)
Implements the NOTEARS algorithm and uses NetworkX to visualize causal edges.
tests like the Fisher-z test, Chi-Sp Square test, etc., and score. functions such as BIC, BDeu. Contains several benchmark causal datasets.
Contains functions for generating data from either simulator or real world dataset.
Implemeeen implements a variety of si'sscor- sccor-based based, constraint- based, hybrid algorithms.
Too box
wte/e//eeeeeeeee SeanTechSolu... wwn.tiiinsss/oooooo oos Caa//aaaaalllaaaa www.issoveeyoooooooo Link: https: ht///gittbb com/ Fen////Feeeee
Temporal CD algorit hms such as PCMCI, PCMC1+ and I.PCMI.
A GUI version of the package also available for easy user control.
Focuses causal assumstion and their validation Contains CansalData Frame, an extension of pandas DataFrame
Link: https: / //ggttttt github. com/ py why www.whhyooo///a /dowby
Link: https: // /github com/ quantumblace caamblackkll.m abs causalnas
Link: https: / /githbb...... com/ cau -piip /ac/caaaaaaa...aaa learn
. Link: https: / github. com/ huawei nnohh brustserttiie
Link: https: /ttpp:///g/aai //github. com/ jakobrunge, t iiggaariie
Link: https: / //gttub. com/ bd2kccd/ py causal
Table 11: A brief overview of the tools packaags for Causall Discovery:
. Link: https: / ggghhuu. com/ cmu httppppppppppaaeeeeeeeeeeeppaaap /ttteaadd
Available a algorithms, datasets APIs
Year
2007
2018
2017
2022
2021
2021
2018
2016
2018
Marco Scutari, Ph.D.
CMU-CLeaR group
Huawei Noah's Ark Lab
BlactumBlack Labs
&
for Causal Discovery (UPitt- CMU)
Neha Abraham Benos Lab
Jakob Runge
BD2K Center
Developer
FenTTech solutions
cmnu- cauupphil phil
Microsoft
Language
Python
Python
Python
Python
Python
Python
Python
JAVA
R
R
Repository
causall causal-leam -laam
CausalNEX
Tigramite
py-cansal
bulearn
gCastle
Tetrad
Cansal MGM
do-why
CDT
2
3
4
5
8
10
46

---

Published in Transactions on Machine Learning Research (09/2023)
9 Challenges and Applications of Causal Discovery
9.1 Challenges
Despite the years of progress made in developing different approaches for causal discovery, there exist some concerns, and challenges that need to be addressed during the development of any causal discovery approach. One of the major concerns about the causal discovery algorithms is the strong assumptions they make to recover the underlying causal graph from data. These assumptions make the task really challenging when any of these are violated. One such assumplion the causal sufficiency which considers that there are no unobserved/late /latent variables. Several methods estimate the causal relationships assuming there are no unobscrved confounders. Howover, this might not be the case in rcal-world data. When roal-world data violates this assumption and has hidden confounders, the estimation results could be distorted, and lead to false conclusions. Often real datasets have hidden confounders that must be taken into account to obtain a true causal graph that represents the data generating process efficiently. Otherwise, this may lead to the possibility of biases in the analysis. Therefore, the collected observational data with latent confounders is insufficient to infer the true underlying causal structure (Squires et al. (2022)) ). Some studies such as Jabbari ct al. (2017): Liu et al. (021), etc. address the presence of latent variables in causal discovery. Another assumption which is the causal faithfulness condition also fails in multiple cases (e.g., if some variables are completely determined by others).
Most of the CD algorithms are based on the assumption that the data samples are independent and identically distribuled (I..D.). However, in many real-world scenarios, the data may have been generated in a different way, and thus, the iid assumption is violated (Lee & Honavar (2020)). ). In such cases, using CD algorithms that assume that the data is I.I.D. may produce spurions and mislcading relationships. Apart from failures of the assumptions, some approaches may get stuck to a local optimum. Especially, greedy methods (e.g. GES (Chickering (2002)), SGES (Chickering & Meek] (2015)), etc.) can get trapped in local optimum, even with large datasets. These methods may often produce sub-optimal graphs in the absence of infinite data. Computational complerity is another challenge for causal discovery algorithms. The search space grows super-erponentiaalyy due to the combinalorial nature of the solution space, which makes even simple methods computationally expensive (Chickering] (1996)). In the case of the score-based approaches, the large search space over all possible DAGs is a major drawback. Hence, score-based methods seem to work well when there are few or moderate number of nodes. However, these methods suffer when the space of equivalence classes tends to grow super exponentially for dense networks. Lack of abundant observational data is another major concern for many CD approaches. For constraint- basod approaches such PC (Spirtes let al. (2000b)). ) FCI (Spirtes el al. (2000a)), etc., accurate CI testing is possible only when an infinite amount of data is available. With a finite amount of data, conditional independence (CI) tests become really challenging. Another disadvantage of the constraint-base
approaches is that with a large sample size or high dimensionnlilyy, the number of CI lests grows exponentially. Even, in some cases, the algorithun might take weeks to provide the output. That is, the run time of the algorithm becomes way too long.
Structure identifiability of the underlying causal model (Shimizu et al. (0006) is another issue in causal discovery. A causal graph G is typically not identifiable given observational data only, a set of possible graphs could have generated the data. Also, the statistical issues stemmiing from high-dimensional datasets are of concern. Apart from these, major challenge is the lack of enough benchmark datasets with ground truth to train and evaluate the developed cansal models. The lack of a comprehensive public data repository consisting of ground-truth graphs hinders the proper evaluation of CD approaches. This problem is severe for arcas such as climate science where there is almost never any exact ground truth available (Melkas et al.. (2021)). Hence, the only way to analyze the produced graphs in such scenarios is to let domain experts inspect those and see if they actually make sense lEbert-Uphoff & Deng (2017). Gani et al. (0023)
In the case of causal discovery from time series data, along with the aforementioned challenges, there are some other challenges too which cause research in this area to be still growing. In many real-world applications, the observed data are obtained by applying subsampling or temporal aggregation to the original causal processes, which makes it tough to discover the underlying causal graph (Gong et al.] (2017)). Also, is difficult to infer the causal relations across samples with different underlying causal graphs (Löwe et al. (2022)). Some approaches also suffer from nonlinear relations in time-series data. Another important challenge is the
47

---

Published in Transactions on Machine Learning Research (09/2023)
discovery of causal relations from large-scale observational time series datasets which is active area of research.
9.2 Applications
Causal discovery is widely used in various fields, ranging from healthcare, economics, earth science, education, machine learning, natural language processing, and many more. The challenges faced with correlation- machine learning have facilitated the development. of several causal discovery techniques and increased their applications in many domains.
In biomedical and healthcare domains, the key research questions revolve around identifying the under- lying causal mechanism to find the risk factors that can be changed to cure disease. To serve this purpose, researchers have been using causal discovery techniques for a long time. Mani & Cooper (1999) used a modified local causal discovery technique identify the factors contributing to infant mortality in the USA. Wang et al. (2066) used stepwise causal discovery method identify active components or combinations of the components in herbal medicine. The Fast Causal Inference (FCT) and Fast Greedy Equivalence Search (FGS) methods were used by Shen et al. (2020) to see how accurately these techniques standard' graph of Alzheimer's Disease. They evaluated the performance of the algorithms on the dataset collected from the Alzheimer's Disease Neuroimaging Initiative (ADNT) and found that the causal graphs generated by FCI and FGES are almost identical to the 'gold standard' graph created from the literature. They also suggested that using longitudinal data with as much prior knowledge as feasible will maximize the effectiveness of causal discovery algorithms. More recently, Shhen al. (2021) proposed causal discovery tochnique that be applied to large-scale Electronic Health Record (EHR) data and has been applied to identify the causal structure for lype-2 diabetes mellitus. Before applying the algorithm, they utilized a data transformation method that converts longitudinal data to disease events. The algorithm uses BIC score to find the causal graph which overlaps 81% with the graph validated by the professionals. Some studies (Bikak) et al. (2020). Gani et al. (2023) have combined the outcomes from several causal discovery algorithms with the opinions health experts develop more reliable and plausible causal graphs. Gani el al. (2023) studies the effect of liberal versus conservative oxygen therapy on the mortality of ICU patients where they present an expert-augnented causal estimation framework. The framework systematically combines results from set of causal discovery algorithms with expert opinions to produce the final causal graph (Figure 36) that is used to answer some important clinical causal queries.
generate the 'gold
Sualer
COPO
ARDS
Surger
10FA
Pask Ai Prnser
Min Mei 3bl
PuT
Orygantes
critical care patients Gani et al. (2023)) ). This causal graph was determined by the majority voting of 7 causal discovery algorithms combined with opinions from the domain experts.
Figure 36: Causal factors determining the influence of oxygen Cherapy on the mortality of
Earth science and climate related research is another domain where causality has been widely adopted. The well-known PC algorithm was applied find the causal links between Eastern Pacific Oscillation (EPO). Western Pacific Oscillation (WPO), North Atlantic Oscillation (NAO), and Pacific-North America (PNA) patterns which four important patterns of mospheri low-frequency variability in boreal winter EEert-
48

---

Published in Transactions on Machine Learning Research (09/2023)
The results, which support carlier research dynamical processes, suggested that WPO and EPO are almost identical from cause-and-effect standpoint due to their high contemporaneous coupling. The PC and PC stable algorithms were applied to daily geopotential height data at 500MB over the borcal winter (Ebert-Upe Uphoff & Deng). The results showed that the atmospheric interactions become less strong on average over the whole Northern Hemisphere. Reduced interconnectedness across various geographic places the result of this weakening, particularly the tropics. Causal discovery methods were also applied to verify the results obtained from dynamic climate models. Hammerling al. (2015) used the PC algorithm to learn the causal signatures from the output of the dynamic model. These causal signatures can provide an additional layer of error checking and identify whether the results of dynamic models are accurate or not. Ombadi et al. (2020) applied Granger causality, PC, convergence cross- mrossmmappnn,, and transfer entropy to hydrological models. The authors used these causal discovery methods to identify and investigate the causes of evaporation and transpiration in shrubland areas throughout the course of the summer and winter. Furthermore, the study Huang et al. (2021) investigated the causal relations between multiple almospheric processes and sea. ice variations using three different data-driven causal discovery algorithms, and based on their experiments, they found that it is very challenging to directly apply the state-of tatee-fftheeaarr data-driven causal discovery approaches to the specific climate topic considered. Recently, Ali et al. (0023) studied the cansal relation between Greenland blocking and sea ice melt using some deep learning based causal analysis techniques.
Uphoff & Deng 2012
Tide
Natural variability
Coastal retreat
Arctic storm
Sea level
Climate change
Ecosystem damage
Storm surge
Solt inundation
Nature of ecosystem
Open water season
Figure 37: Causal influence of climate and environmental factors on the collapse of an Arctic ecosystem from storm surge (Shepherd & Lloyd] (2021))
The education sector has leveraged causal discovery techniques for docades now. Druzdzel & Glymour (1995) performed experiment based on the Tetrad II (Scheines et al. (1994)) causal discovery program why the retention rate of U.S. universities is low compared to their reputation. The causal discovery model identified that the retention rate mostly depends on the quality of incoming students. Fancsali (2014) used the PC and FCI algorithms to answer questions based on their causal effect. They specifically considered the satuation given that a student. who plays computer games scored poorly in his exam, can the algorithms answer whether reducing gaming time will improve his results? Quintana (2020) employed the PC and FGS algorithms find which social and economic factors are directly related to academic achievements. The algorithms found earlier accomplishment, executive functions such thinking skills, sustained attention focusing, and ambition as the primary drivers of academic performance, which is in line with other studies.
Over the past few years, the intersection of causality with Machine Learning (ML) and Artificial Intelligence (AI) techniques is quite a topic of interest. Sun et al. (2015b) utilized Granger causality for selecting machine learning features in two-dimensional space. This approach outperformed the traditional feature selection techniques like Principal Component Analysis (PCA) (Abdi & Williams (2010)), Functional Connectome (FC) (Bishop et al. (1995)), and Recursive Feature Elimination (RFE) (Guyon al. (2002)
due to the ability of Granger causality to identify the causal connection between the input variable and the
chosen time scries. Nogucira et al. (2021) published survey paper that mainly focused on the applications of causal discovery in machine learning. They discussed how the constraint-based and score-based approaches, as well as causal neural networks and causal decision trees, were applied along with machine learning in various topics. Although previously rescarchers were not much interested in applying causal techniques Natural Language Processing (NLP). an important sub-field of AI, recently several causal discovery methods have been applied in this area. To get a deeper explanation, one can read the survey written by
49

---

Published in Transactions on Machine Learning Research (09/2023)
Feder et al. 2021 that discusses the applications of different causal discovery techniques in NLP and how these techniques can help to improve this domain further.
In addition to the abovementioned domains, causal discovery techniques are also being used in business, macroeconomics, manufacturing, and software engineering, to name a few. Hu et al. (2013) used a causal Bayesian network with some specialized constraints to analyze the risks associated with software development projects. Luo al. (2021) used causal discovery models to identify the relationship between flight delays and service nodes. Hall-Hoffarth (2022 employed causal discovery in macrocconomic dynamic stochastic general equilibrium (DSGE) models to learn the underlying causal structure. Vuković & Thalman (2022) wrote a review paper identifying the applications of causal discovery in manufacturing where root cause analysis, causality in a facilitator role, fault detection, analysis, and management have been highlighted as important areas of application. In business, the understanding of causal relations plays a vital role in designing effective interventions such as launching a new advertising campaign or a promotion (Borboudakis & Tsamardinos 2016)).
Apart from these applications, to learn the causal structure from relational data, Lee & Honavar (0020) developed a method called RRCD (Robust Relational Causal Discovery) where they demonstrated how CI test created for LLD. data can be successfully used to test for relational conditional independence (RCT) against relational data. Moreover, some methods model casual relationships by the incorporation of background knowledge obtained from several sources including experts' opinions, domain knowledge, prior evidence, relevant literature, etc. An importance of such a kuowledge- based strategy is that additional causal relationships may become identifiable with the incorporation of background knowledge (Hasan & Gani 2022 )- Even specifying one variable the cause of another, can further refine the set of potential graphs. thereby increasing the nunber of identifiable causal relationships (Wang et al. 20200)) Some studies (Gani ct al. (2023), Adib et al. (2022b), Adii et al. (2022a)) even highlight the importance of meman-in-ther human-in-the--lop. and recommend taking into account domain experts' opinions to verify the graphs produced by different causal discovery algorithms. Other than these, causal discovery have been applicd in representation learning as well. Yang et al. (2021) proposed a generative model named CausalVAB which learns disentangled and causally meaningful representations of the data by combining ideas of VAE with the SCM. They introduced causal layer with a DAG structure to be learned inside the vanilla VAE model which converts independent exogenous factors into causal endogenous ones.
All in all, causal discovery approaches and techniques have been widely adopted in several areas for un- derstanding the underlying causal relationships, and thereby deriving actionable insights. However, while applying causal discovery methods it is very important to consider the corresponding assumptions. If the assumptions made by the respective algorithm are violated by the data, then it may often lead to biased results. Thus, it is important ensure that the assumptions hold for unbiased discovery of causal graphs.
10 Discussion
Traditional AI applications that solely rely upon predictions lack explainability and are often difficult to comprehend due to their black-box nature. Causal analysis can overcome the lack of explainability in the existing Al models by embedding casual knowledge into them. These models have greater transparency, and thereby, achieve greater reliability. A crucial part of the causal analysis is causal discovery. It is the recovery of the underlying causal structure represented in a graphical form. Such visualizations of causal relationships are casy to comprehend as well as more appealing to a user. In this survey, we introduce a wide variety of existing approaches to perform causal discovery. We also provide brief overview of the common terminologies used in the area of causal discovery and summarize the different types of algorithms available for structure learning from both I.L.D, and time series data. Apart from discussing the approaches, we also discuss the commonly used datasets, metrics, and toolboxes for performing causal discovery efficiently. In order to select an appropriate approach for learning the causal structure, one can consider some of the following aspects. Selecting the approach whose assumptions are met by the data is very crucial. For example, some methods work well for either lincar or non-lincar data while some may need a very high amount of samples to operate efficiently. So, before choosing an algorithm, is important to understand if the assumptions made are also supported by the data or not. When the assumptions are violated by the
50

---

Published in Transactions on Machine Learning Research (09/2023)
data, there is high chance of obtaining misleading results from the algorithm. Also, some algorithms have faster run time while others are comparatively much slower. Particularly, some constraint-based methods tend to be much slower when the number of variables are high as they need to conduct a huge amount of CI tests. Therefore, one should also select the approach considering the time available to perform the experiments.
With the growing number of approaches for causal structure learning, an essential future research direction is to look deeper into the common challenges or limitations faced during the process. Towards the end of this paper, discuss some of the common challenges as well as wide variety of applications of causal discovery in multiple fields. Future cousality research should focus on the nature of real-world datascts, and develop methods that take into account these practical constraints for better and more reliable structure recovery. It is often observed during experiments that different methods produce causal graphs that disagree with each other to a great extent. In fact, the experiments (benchmarking) that we performed, we also observed a significant disagrocment among the approaches w.r.t. their estimated causal graphs. Therefore, it is needed to accurately quantify the uncertainty of the inferred suctuuee.. This is particularly important for the areas such the healthcare sector which is related to the well-being of humans. It is also important to consider any available background knowledge such as domain expertise, literature evidence, ctc. during the causal discovery process which may help to overcome the existing challenges. Once the causal community becomes successful in addressing the existing challenges, we may hope to have better approaches with greater accuracy and reliability.
References
Hervé Abdi and Lynne J Williams. Principal component analysis. Wiley interdisciplinary reviews: compu- tational stolislics, 2(4):433 459, 2010.
Ohudare Isaac Abiodun, Aman Jantan, Abiodun Esther Omolara, Kemi Victoria Dada, Nachaat AbdElatif Mohamed, and Humaira Arshad. State-of-the-art in artificial neural network applications: A survey. Heliyon, 4(1 =e00988,,,,, 2018.
Riddhiman Adib, Md Osman Gani, Sheikh lqbal Ahamed, and Mohammad Adibuzzaman. Causal discovery on the effect of antipsychotic drugs on delirium patients in the icu using large chr datasct. arXiv preprint arXiv:2205.011 01057, 2022a.
Riddhiman Adib, Md Mobasshir Arshed Naved, Chih-Hao Fang, Md Osman Gani, Ananth Grama, Paul Griffin, Sheikh Iqbal Ahamed, and Mohammad Adibuzzaman. Ckh: Causal knowledge hierarchy for estimating structural causal models from data and priors. arXiv preprint ar arxiv:2204. 19775, 2022b.
Hirotogu Akaike. Information theory and an extension of the maximum likelihood principle. Selected papers of hirotugu akaike, pp. 213, 1998.
Sahara Ali, Omar Faruque, and Jianwu Wang. Quantifying causes of arctic amplification via deep learning based time-series causal inference. arXie preprint UrXiv:2303.0711 2023.
Bryan Andrews, Peter Spirtes, and Gregory F Cooper. On the completeness of causal discovery in the presence of latent confounding with tiered background knowledge. In International Conference on Artificial Intelligence and Statistics, pp. 4002-4011 PMLR, 2020.
Charles K. Assuad, Emilie Devijver, Eric Gaussier, and Ali Ait- A mixed noise and constraint-based approach to causal inference in time series. Tn Nuria Oliver, Fernando Pérez-Cruz, Stefan Kramer, Jesse Read, and Jose A. Lozano (eds.), Machine Learning and Knowledge Discovery in Databoses. Research Track, pp. 453 453-468, Cham, 2021. Springer International Publishing. ISBN 00--3-030-8444--4
Charles K Assaad, Emilie Devijver, and Eric Gaussier. Entropy-based discovery of summary causal graphs in time series. Eutropy, 24(8):1156, 2022a.
Charles K Assaad, Emilic Devijver, and Eric Gaussier. Survey and evaluation of causal discovery methods for time series. Journal of Artificial Intelligence Research, 73:767-811 8819 2022b.
51

---

Published in Transactions on Machine Learning Research (09/2023)
Mark Bartlett and James Cussens. Integer linear programming for the bayesian network structure learning problem. Artificial Intelligence, 244:258 271, 2017.
Ingo A Beinlich, Henri Jacques Suermondt, R Martin Chavez, and Gregory F Cooper. The alarm monitoring system: A case study with two probabilistic inference techniques for belief networks. In AIME 89: Second European Conference Artificial Intelligence in Medicine, London, August 29th-31st 1989. Proceedings, pp. 247 256. Springer, 1989.
Alexis Bellot and Mihaela van der Schaar. Conditional independence testing using generative adversarial networks. Advances Newral Information Processing Systems, 32, 2019.
Alexis Bellot, Junzhe Zhang, and Elias Bareinboim. Scores for learning discrete causal graphs with un- observed confounders. Technical report, Technical Report R-83, Causal Al Lab, Columbia University, 2022.
Richard A Berk. An introduction to sample selection bias in sociological data. American sociological review, pp. 386 398, 1983.
Harsh Bhatia, Gregory Norgard, Valerio Pascucci, and Peer-Timo Bremer. The helmholtz-hodge decompo- sition survey. IEEE Transactions on visualization and computer graphics, 19(8):1386-144 1404, 2012.
Marvi Bikak, Shravan Kethireddy, Md Osman Gani, and Mohammad Adibuwaman. Structural causal model with expert augmented knowledge to estimate the effect of oxygen therapy. CHEST, 158(4):A636, 2020.
Christopher M Bishop al. Neural networks for pattern recognition. Oxford university press, 1995.
Giorgos Borboudakis and Ioannis Tsamardinos. Towards robust and versatile causal discovery for business applications. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1435 1444, 2016.
Peter Bühlmann, Jonas Peters, and Jan Ernest. Cam: Causal additive models, high-dimensional order search and penalized regression. 2014.
Wray Buntine. Theory refinement on bayesian networks. In Uncertainly proceedings 1991, pp. 52 60. Elsevier, 1991.
Bart Bussmann, Jannes Nys, and Steven Latré. Neural additive vector autoregression models for causal discovery in time series. In International Conference on Discovery Science, pp. 446-460. Springer, 2021.
Ruichu Cai, Zhenjie Zhang, and Zhifeng Hao. Sada: A general framework to support robust causation discovery. In International conference on machine learning, pp. 208 216. PMLR, 2013.
Ruichu Cai, Feng Xie, Clark Glymour, Zhifeng Hao, and Kun Zhang. Triad constraints for learning causal structure of latent variables. Advances in neural information processing systems, 32, 2019.
Xuefei Cao, Björn Sandstede, and Xi Luo. A functional data method for causal dynamic network modeling of task-related fmri Frontiers in neuroscience, 13:127, 2019.
Wei Chen, Kun Zhang, Ruichu Cai, Biwei Huang, Joseph Ramsey, Zhifeng Hao, and Clark Glymour. Fritl: A hybrid method for causal discovery in the presence of latent confounders. arXie preprint or xrx:221033. 14238, 2021.
Lu Cheng, Ruocheng Guo, Raha Moraffah, Paras Sheth, Kasim Selcuk Candan, and Huan Liu. Evaluation methods and measures for causal learning algorithms. IEEE Transactions on Artificial Intelligence, 2022.
David Maxwell Chickering. Learning bayesian networks is np-complete. In Learning from data, pp. 121-130.
Springer, 1996.
David Maxwell Chickering, Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-5t) 554, 2002.
52

---

Published in Transactions on Machine Learning Research (09/2023)
David Maxwell Chickering and Christopher Meek. Selective greedy equivalence search: Finding optimal bayesian networks using a polynomial number of score evaluations. arXiv preprint. or orxi 10::1566000 021 13, 2015.
Diego Colombo, Marloes H Maathuis, Markus Kalisch, and Thomas S Richardson. Learning high-dimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics, pp. 294-224411111 004--21, 2012.
Diego Colombo, Marloes H Maathuis, et al. Order-independent constraint- based causal structure learning. Mach. Learn. Res., 15(1):374133782, 2014.
Pierre Comon. Independent component analysis, new concept? Signal processing, 36(3):287-314, 1994.
Gary Doran, Krikamol Muandet, Kun Zhang, and Bernhard Schölkopf. A permutation-based kernel condi- tional independence test. In UAI, pp. 132-141. Citescer, 2014.
Marck Druzdzel and Clark Glymour. What do college ranking data tell us about student retention: causal discovery action. In Proceedings of 4th workshop on intelligent. informalion systems. IPI PAN Press, Augustow, Poland, pp. 1-10. Citeseer, 1995.
Didier Dubois and Henri Prade. A glance at causality theories for artificial intelligence. A Guided Tour of Artificial Intelligence Research: Volume I: Knowledge Representation, Reasoning and Learning, pp- 275 305, 2020.
Imme Ebert-Uphoff and Yi Deng. Using causal discovery to learn about our planct's climato-recent progress.
Imme Ebert-Uphoff and Yi Deng. Causal discovery for climate rescarch using graphical models. Journal of Climate, (5(7))56648 5665, 2012.
Imme Ebert-Uphoff and Yi Deng. Causal discovery in the geosciencos-using synthetic data to learn how to interpret results. Computers Geosciences, 99:50-60, 2017.
Doris Entner and Patrik O Hoyer. On causal discovery from time series data using fci. Probabilistic gruphical models, pp. 121-128, 2010.
Stephen Fancsali. Causal discovery with models: behavior, affect, and learning in cognitive tutor algebra. In Educational Data Mining 2014. Citeseer, 2014.
Amir Feder, Katherine A Keith, Emaad Manzoor, Reid Pryzant, Dhanya Sridhar, Zach Wood-Doughty, Jacob Eisenstein, Justin Grimmer, Roi Reichart, Margaret Roberts, et al. Causal inference in natural language processing: Estimation, prediction, interpretation and beyond. arXiv preprint arXiv:2109.00799 2021.
Muhammad Hasan Ferdous, Uzma Hasan, and Md Osman Gani. ecdans: Efficient temporal causal discovery from autocorrelated and non-stationary data (student abstract). Proceedings of the AAAI Conference on Artificial Intelligence, (7(1)) Junc. 2023a. doi: 10. 10.1609/ vtt//aaai.v...3...... 007113.26964.
Muhammad Hasan Ferdous, Uzma Hasan, and Md Osman Gani. Cdans: Temporal causal discovery from autocorrelated and non-stationary time series data. Proceedings of Machine Learning Research, 2023b. Accepted in 8th Machine Learning for Healthcare Conference, arXiv preprint arXiv:2302.03248
Nir Friedman, Ifach Nachman, and Dana Pe'er. Learning bayesian network structure from massive datasets: The' sparse candidate' algorithm. arXiv preprint 1tti:::301.669, 2013.
Niloy Ganguly, Dren Fazlija, Maryam Badar, Marco Fisichella, Sandipan Sikdar, Johanna Schrader, .Jonas Wallat, Koustav Rudra, Manolis Koubarakis, Gourab K Patro, al. A review of the role of causality in developing trustworthy ai systems. arXiv preprint ar Xix:::2302.06975 2023.
Md Osman Gani, Shravan Kethireddy, Riddhiman Adib, Uzma Hasan, Paul Griffin, and Mohammad Adibuz- zaman. Structural causal model with expert augmented knowledge to estimate the effect of oxygen therapy mortality in the icu. Artificial Intelligence in Medicine, 137: 10249,,, 2023.
53

---

Published in Transactions on Machine Learning Research (09/2023)
Dan Geiger and David Heckerman. Learning gaussian networks. In Uncertainty Proceedings 1994, pp. 235-245 243. Elsevier, 1994.
Michael Gelfond and Vladimir Lifschitz. The stable model semantics for logic programming, In JCLP/SLA volume 88, pp. 1070-1080. Cambridge, MA, 1988.
Andreas Gerhardus and Jakob Runge. High-recall causal discovery for autocorrelated time series with latent confounders. Advances in Neural Information Processing Systems, 33:12615 11215-112220 12625, 2020.
Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical models. Frontiers in genetics, 10:524, 2019.
Mingming Gong, Kun Zhang, Bernhard Schölkopf, Clark Glymour, and Dacheng Tao. Causal discovery from temporally aggregated time series. In Uncerlainly in artificial intelligence: proceedings of the... conference. Conference on Uncertainty in Artificial Intelligence, volume 2017. NIH Public Access, 2017.
Olivier Goudet, Diviyan Kalainathan, Philippe Caillou, Isabelle Guyon, David Lopez-Paz, and Michele Scbag. Learning functional causal models with gencrative noural networks. In Explainable and interpretable models in computer vision and machine learning, pp. 39 80. Springer, 2018.
Clive WJ Granger. Investigating causal relations by econometric models and cross-spectral methods. Econo- metrica: journal of the Econometric Society, pp. 424-438, 1969.
Ruocheng Guo, Lu Cheng, Jundong Li, P Richard Hahn, and Huan Liu. A survey of learning causality with data: Problems and methods. ACM Compuling Surveys (CSUR), 53(4):1 37, 2020.
Isabelle Guyon, Jason Weston, Stephen Barnhill, and Vladimir Vapnik. Gene selection for cancer classifica- tion using support vector machines. Machine learning, (611):3894422 2002.
Emmet Hall-Hoffarth. Causal discovery of macroeconomic state-space models. NXiv:2204.0237, 2022.
arXiv preprint
Dorit Hammerling, Allison Baker, and Imme Ebert- Uphoff. What can we learn about climate model runs from their causal signatures. In Proceedings of the Fifth International Workshop on Climate Informatics: CI, volume 2223, 2015.
Uzma Hasan and Md Osman Gani. Kerl: A prior knowledge based causal discovery framework with rein- forcement learning. Proceedings of Machine Learning Research, 182(2022):1-244 2022.
Uzma Hasan and Md Osman Gani. Kgs: Causal discovery using sowwllede-guiide.. greedy equivalence search. arXiv preprint Xrx:222904. 05499, 2023.
Christina Heinze- Heinze-Deml, Marloes Maathuis, and Nicolai Meinshausen. Causal structure learning. Annual Review of Statistics and Its Application, 5:371-391, 2018.
Patrik Hoyer Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. Advances in neural information processing systems, 21, 2008.
Yong Hu, Xiangzhou Zhang, EWT Ngai, Ruichu Cai, and Mei Liu. Software project risk analysis using bayesian networks with causality constraints. Decision Support Systems, 56:439-449, 2013.
Biwei Huang, Kun Zhang, Yizhu Lin, Bernhard Schölkopf, and Clark Glymour. Generalized score functions for causal discovery. In Proceedings of the 24th ACM SIGKDD internalional conference on knowledge discovery data mining, pp.
2018a.
Biwei Huang, Kun Zhang, Yizhu Lin, Bernhard Schölkopf, and Clark Glymour. Generalized score functions for causal discovery. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery E dala mining, pp. 1551-1560 2018b.
54

---

Published in Transactions on Machine Learning Research (09/2023)
Biwei Huang, Kun Zhang, Jiji Zhang, Joseph D Ramsey, Ruben Sanchez-Romero, Clark Glymour, and Bernhard Schölkopf. Causal discovery from wederroeneoous/nnnniiaaiee data. J. Mach. Learn. Res., 21 (89):1-58 53, 2020.
Chin-Wei Huang, David Krueger, Alexandre Lacoste, and Aaron Courville. Neural autoregressive flows. In International Conference on Machine Learning, pp. 2078-2088 PMLR, 2018c.
Yiyi Huang, Matthäus Kleindessner, Alexey Munishkin, Debvrat Varshney, Pei Guo, and Jianwu Wang, Benchmarking of data-driven causality discovery approaches in the interactions of arctic sea ice and at- mosphere. Frontiers in big Data, 4:642182, 2021.
Aapo Hyvarinen. Fast and robust fixed-point algorithms for independent component analysis. IEEE trans- actions on Neurol Networks, 10(3):626 634, 1999.
Aapo Hyvärinen, Kun Zhang, Shohei Shimizu, and Patrik O Hoyer. Estimation of a structural vector autoregression model using non non-gaussianity. Journal of Machine Learning Research, 11(5), 2010.
Fattaneh Jabbari, Joseph Ramsey, Peter Spirtes, and Gregory Cooper. Discovery of causal models that contain latent variables through bayesian scoring of independence constraints. In Machine Learning and Knowledge Discovery in Databases: Europeon Conference, ECML PKDD 2017, Skopje, Macedonia, September 18-22, 2017, Proceedings, Part II 10, pp. 142- 447-157.20 Springer, 2017.
Amin Jaber, Murat Kocaoglu, Karthikeyan Shammugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. Advances in neural information processing systems, 33:9551-9561, 2020.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparamcterizatiin with gumbel-softmax. arXiv preprint arXiv:1611.01144, 2016.
Jean Kaddour, Aengus Lynch, Qi Liu, Matt J Kusner, and Ricardo Silva. Causal machine lcarning: A survey and open problems. aixio preprint or 2rv::22066 15475, 2022.
Diviyan Kalainathan and Olivier Goudet. Causal discovery toolbox: Uncover causal relationships in python. arXiv preprint Xix::19903. 02278, 2019.
Diviyan Kalainathan, Olivier Goudet, Isabelle Guyon, David Lopez-Paz, and Michèle Sebag. Structural agnostic modeling: Adversarial learning of causal graphs. arXiv preprint arXi:: 1803.0499, 2018.
Ilyes Khemakhem, Ricardo Monti, Robert Leech, and Aapo Hyvarinen. Causal autoregressive flows. In International conference artificial intelligence and statistics, pp. 3520-3528 PMLR, 2021.
Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. Advances in Neural Information Processing Systems, 30, 2017.
Murat Kocaoglu, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. Characterization and learn- ing of causal graphs with latent variables from soft interventions. Advances in Neural Information Pro- cessing Systems, 32, 2019.
Andrei N Kolmogorov. On tables of random numbers. Sankhya: The Indian Journal of Slatislics, Series A, pp. 369-376, 1963.
Kevin B Korb and Ann E Nicholson. Bayesion artificial intelligence. CRC press, 2010.
Sébastien Lachapelle, Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien. Gradient-based neural dag learning. Xrxiv preprint arXiv:1906.022 02226, 2019.
Timothy Laumann, Evan M Gordon, Babatunde Adeyemo, Abraham Z Snyder, Sung Jun Joo, Mei-Ye Yen Chen, Adrian W Gilmore, Kathleen B McDermott, Steven M Nelson, Nico UF Dosenbach, al. Functional system and areal organization of highly sampled individual human brain. Newron, 87(3):657-66) 670, 2015.
55

---

Published in Transactions on Machine Learning Research (09/2023)
Steffen L Lauritzen and David Spiegelhalter. Local computations with probabilities graphical structures and their application to expert systems. Journal of the Royal Statisticnl Sociely: Series B (Melhodologieal), 50(2):157 -94,, 1988.
Andrew R. Lawrence, Marcus Kaiser, Rui Sampaio, and Maksim Sipos. Data generating process to evaluate causal discovery techniques for time series data. arXiv preprint arXim:2144.00033 2021.
Richard Lawton et al. Time series analysis and its applications: Robert h. shumway and david s. stoffer; springer texts in statistics; 2000, springer-verlag.fuk pound] 55, $ 79.95, isbn 0-387-98950-1. Interna- lional Journal of Forecasling, 17(2):299 301, 2001.
Sanghack Lee and Vasant Honavar. Towards robust relational causal discovery. In Uncertainty in Artificial Intelligence, pp. 345-355. PMLR, 2020.
Adam Li, Amin Jaber, and Elias Bareinboim. Causal discovery from observational and interventional data across multiple environments.
Yan Li, Rui Xia, Chunchen Liu, and Liang Sun. hybrid causal structure learning algorithm for mixed-type data. 2022.
Lek-Heng Lim. Hodge laplacians on graphs. Siam Review, 62(3):685 715, 2020.
Phillip Lippe, Taco Cohen, and Efstratios Gavves. Efficient neural causal discovery without acyclicity constraints. Xixi preprinl or Niv:21077.14883 2021.
Anqi Liu, Hao Liu, Tongxin Li, Saeed Karimi-Bidheni Yisong Yue, and Anima Anandkumar. Dis- entangling observed causal effects from latent confounders using method of moments. arXiv preprint arXiv:2101.0661 2021.
Sindy Löwe, David Madras, Richard Zemel, and Max Welling, Amortized causal discovery: Learning infer causal graphs from time-scries data. In Conference Causall Learning and Reasoning, pp. 509-525. PMLR, 2022.
Ni Y Lu, Kun Zhang, and Changhe Yuan. Improving causal discovery by optimal bayesian network learning.
In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 8741-8748, 2021.
Peter JF Lucas, Linda C Van der Gaag, and Ameen Abu-Hanna. Bayesian networks in biomedicine and health-care. Artificial intelligence in medicine, 30(3):201-22 214, 2004.
Qian Luo, Lin Zhang, Zhiwci Xing, Huan Xia, and Zhao-Xin Chen. Causal discovery of flight service process based on event sequence. Journal of Advanced Trunsportation, 2021, 2021.
Daniel Malinsky and Peter Spirtes. Estimating causal effects with ancestral graph markov models. In Conference on Probabilistic Graphical Models, pp. 299-309. PMLR, 2016a.
Daniel Malinsky and Peter Spirtes. Estimating causal elfects with ancestral graph markov models. In Conference on Probabilistic Graphical Models, pp. 299 309.399..0 PMLR, 2016b.
Subramani Mani and Gregory F Cooper. A study in causal discovery from population-based infant birth and death records. In Proceedings of the AMTA Symposium, pp. 315. American Medical Informatics Association, 1999.
Ričards Marcinkevičs and Julia E. Vogt. Interpretable models for granger causality using self-cxplaining neural networks. Xie preprint arXiv:2101.00 2021.
George A Marcoulides, Zvi Drezner, and Randall Schumacker. Model specification searches in structural equation modcling using tabu search. Structural Equation Modeling: A Multidisciplinary Journal, 5(4): 365 075-376,14 1998.
Tshilidzi Marwala. Causality, correlation and artificial intelligence for rational decision making. World Scientific, 2015.
56

---

Published in Transactions on Machine Learning Research (09/2023)
Alexander Marx and Jilles Vreeken. Testing conditional independence discrete data using stochastic complexity. In The 22nd International Conference on Artificial Intelligence and Stalistics, pp. 196-505. PMLR, 2019.
Laila Melkas, Rafael Savvides, Suyog H Chandramouli, Jarmo Mäkelä, Tuomo Nieminen, Ivan Mammarclla, and Kai Puolamáki. Interactive causal structure discovery in earth system sciences. In The KDD'2 '1 Workshop Causal Discovery, pp. 3 3-25. PMLR, 2021.
Alex C Michalos. A probabilistic theory of causality. Philosophy of Science, 39(4):560-55) 5610005611111 1972.
Joris Mooij and Dominík Janzing. Distinguishing between cause and effect. In Causalily: Objeclives and Assessment, pp. 147-156. PMLR, 2010.
Joris M Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. The Journal of Machine Learning Research, 21(1):3919 4026, 2020.
Andrew Moore and Weng-Keen Wong. Optimal reinsertion: A new search operator for accelerated and more accurate bayesian network structure learning. In ICML, volume 3, pp. 552 559, 2003.
Muñoz-Mari, G Mateo, Runge, and G Camps- Valls. Causeme: an online system for benchmarking causal discovery methods, 2020.
Meike Naula, Doina Bucur, and Christin Seifert. Causal discovery with atlention-based convolutional neural networks. Machine Learning and Knowledge Extraction, 1(1):19, 2019.
AS Nemirovsky. Optimization numerical methods for nonlinear continuous optimization. 1999.
Ignavier Ng. Shengyu Zhu, Zhitang Chen, and Zhuangyan Fang. A graph autoencoder approach to causal structure learning. Xie preprint or arXix:1911.074.00 2019.
Ignavier Ng, AmirEmad Ghassami, and Kun Zhang. On the role of spansity and dag constraints for learning lincar dags. Advances in Newral Information Processing Systems, 33:17943-17954, 2020.
Ignavier Ng, Shengyu Zhu, Zhuangyan Fang, Haoyang Li, Zhitang Chen, and Jun Wang. Masked gradient- based causal structure learning. In Proceedings of the 2022 SIAM International Conference on Dala Mining (SDM), pp. 124-432. SIAM, 2022.
Ana Rita Nogueira, João Gama, and Carlos Abreu Ferreira. Causal discovery in machine learning: Theories and applications. Journal of Dynamics and Games, 8(3):203, 2021.
Mohammed Ombadi, Phu Nguyen, Soroosh Sorooshian, and Kuo-lin Hsu. Evaluation of methods for causal discovery in hydrometeorological systems. Water Resources Research, 56(7)=22020RR022251,, 2020.
Agnicszka Onisko. Probabilistic causal models in medicine: Application to diagnosis of liver disorders. In Ph. D. dissertation, Inst. Biocybern. Biomed. Eng., Polish Acudemy Sci., Worsaw, Poland, 2003.
Roxana Pamfil, Nisara Srivattanaworachaii, Shaan Desai, Philip Pilgerstorfer, Konstantinos Georgatzis, Paul
Beaumont, and Bryon Aragam. Dynotears: Structure learning from time-series data. Tn International Conference on Artificial Intelligence and Statistics, pp. 1595 1605. PMLR, 2020.
Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufman Publishers, San Mateo, CA, 1988.
Judea Pearl. Causality, Cambridge university press, 2009.
Emilija Perković, Markus Kalisch, and Malocs H Maathuis. Interpreting and using cpdags with background knowledge. Xiv preprinl arXiv: 170700211, 2017.
Jonas Peters and Peter Bühhlannn Structural intervention distance for evaluating causal graphs. Neural compulation, 27(3):771-799 1799, 2015.
57

---

Published in Transactions on Machine Learning Research (09/2023)
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Causal inference time series using restricted structural equation models. Advances in Neural Information. Processing Systems, 26, 2013.
Mark Peyrot. Causal analysis: Theory and application. Journal of Pediatric Psychology, 21(1):3 24 1996.
Robert Prill, Daniel Marbach, Julio RaeziRoorig Peter Sorger, Leonidas G Alexopoulos, Xiaowei Xue, Neil D Clarke, Gregoire Altan-Bonnct, and Gustavo Stolovitzky. Towards rigorous asscssment of systems biology models: the dream3 challenges. PloS one, :(2), 2010.
Rafael Quintana. The structure of academic achievement: Searching for proximal mechanisms using causal discovery algorithms. Sociological Methods & Research, pp. 0049124120996208,, 2020.
Joseph Ramsey, Jiji Zhang, and Peter L Spirtes. Adjaacncy--aitthuuhres and conservative causal inference. arXiv preprint ar 1206. 6843, 2012.
Joseph Ramsey. Scaling up greedy causal search for continuous variables. ar preprint orXi::1007.07749 2015.
Carl Edward Rasmussen, Christopher KT Williams, et al. Gaussion processes for machine learning, volume 1. Springer, 2006.
David B Resnik. Randomized controlled trials in environmental health rescarch: ethical issues. Journal of environmental health, 70(6):28, 2008.
Thomas Richardson and Peter Spirtes. Ancestral graph markov models. The Annals of Statistics, 30(4): 0030, 2002a.
Thomas Richardson and Peter Spirtes. Ancestral graph markov models. The Annals of Statistics, 30(4): 962-1030, 2002b.
Jakob Runge. Conditional independence testing based on nearest-neighhor estimator of conditional mutual information. In International Conference on Artificial Intelligence and Statistics, pp. 988-947. PMLR, 2018.
Jakob Runge. Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time scries datasets. In Conference on Uncertainty in Artificial Intelligence, pp. 1388-1397. PMLR, 2020.
Jakob Runge, Peer Nowack, Marlene Kretschmer, Seth Flaxman, and Dino Sejdinovic. Delecting and quan- tifying causal associations in large nonlinear time series datasets. Science advances, 5(11)reaau4996, 2019.
Karen Sachs, Omar Perez, Dana Pe'er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 308(5721):523 529, 2005.
Andreas Sauter, Erman Acar, and Vincent François-Lavet. A meta-reeiforrcement learning algorithm for causal discovery. arXie preprinl arXiv:2207.08457, 2022.
Richard Scheines. An introduction to causal inference. 1997.
Richard Scheines, Peter Spirtes, Clark Glymour, and Christopher Meek. Tetrad ii: Tools for discovery, 1994.
Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Fleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal learning. arXiv preprint arXiv:1206.644 2012.
Gidcon Schwarz. Estimating the dimension of a model. The annals of statistics, pp. 461-464, 1978a.
Gideon Schwarz. Estimating the dimension of model. The annals of statistics, pp. 461 464, 1978b.
Marco Scutari. Learning bayesian networks with the bulearn package. ar preprint arXiv:0908.3817, 2009.
58

---

Published in Transactions on Machine Learning Research (09/2023)
Rajat Sen, Ananda Theertha Suresh, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkot- tai. Model-powered conditional independence test. Advances in neural information processing systems. 30, 2017.
Xinpeng Shen, Sisi Ma, Prashanthi Vemuri, and Gyorgy Simon. Challenges and opportunitics with causal discovery algorithms: application to alzheimer's pathophysiology. Scientific reports, 10(1):1-12, 2020.
Xinpeng Shen, Sisi Ma, Prashanthi Vemuri, M Regina Castro, Pedro Caraballo, and Gyorgy Simon. novel method for causal structure discovery from ehr data and its application to type-2 diabetes mellitus. Scientific reports, 11(1):1-9, 2021.
Theodore G Shepherd and Elisabeth A Lloyd. Meaningful climate science. Climatic Change, 169(1-2):17, 2021.
Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non- gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
Shohci Shimizu, Takanori Inazumi, Yasuhiro Sogawa, Aapo Hyvärinen, Yoshinobu Kawahara, Takashi Washio, Patrik Hoyer, and Kenneth Bollen. Directlingam: A direct method for learning a linear non-gaussian structural equation model. The Journal of Machine Learning Research, 12:1225 1248, 2011.
Bonnie Sibbald and Martin Roland. Understanding controlled trials. why are randomised controlled trials important? BMJ: British Medical Journal, 316(7126):201. 1998.
Tomi Silander, Teemu Roos, Petri Kontkanen, and Petri Myllymäki. Factorized normalized maximum likelihood criterion for learning bayesian network structures. In Proceedings of the 4th European workshop on probabilistic graphical models (PGM-08), pp. 257-272, 2008.
Meghamala Sinha and Stephen Ramsey. Using a general prior knowledge graph to improve data-driven causal nelwork learning. In AAAI Spring Symposium: Combining Machine Learning with Knowledge Engineering, 2021.
David J Spiegelhalter, A Philip Dawid, Steffen L Lauritzen, and Robert G Cowell. Bayesian analysis in expert systems. Statistical science, pp. 219-247, 1993.
Peter Spirtes. An anytime algorithm for causal inference. In International Workshop on Artificial Intelligence and Statistics, pp. 278-285. PMLR, 2001.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Cansation, prediction, and search. MIT press, 2000a.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000b.
Chandler Squires, Annie Yun, Eshaan Nichani, Raj Agrawal, and Caroline Uhler. Causal structure discovery between clusters of nodes induced by latent factors. In Conference Causal Learning and Reasoning, pp. 669 687. PMLR, 2022.
Eric V Strobl, Kun Zhang, and Shyam Visweswaran. Approximate kernel-based conditional independence tests for fast non porpaaaettricc causal discovery. Journal of Causal Inference, 7(1), 2019.
Seth Sullivant, Kelli Talaska, and Jan Draisma. Trek separation for gaussian graphical models. 2010.
Jie Sun, Dane Taylor, and Erik M Bollt. Causal network inference by optimal causation entropy. SIAM Journal on Applied Dynamical Systems, 14(1):73-106, 2015a.
Xiangyu Sun, Guiliang Liu, Pascal Poupart, and Oliver Schulte. Nts-notears: Learning nonparametric
temporal dags with time-series data and prior knowledge. arXiv preprint arXiv:2109 NXi:22099004280 04286, 2021.
59

---

Published in Transactions on Machine Learning Research (09/2023)
Yougiang Sun, Jiuyong Li, Jixue Liu, Christopher Chow, Bingyu Sun, and Rujing Wang. Using causal discovery for feature selection in multivariate numerical time series. Machine Learning, 2015b.
Natasa Tagasovska, Valérie Chavez-Demoulin, and Thibault Vatter. Distinguishing cause from effect using quantiles: Bivariate quantile causal discovery. In International Conference on Machine Learning, pp. 9311-9323. PMLR, 2020.
Sofia Triantafillou and Ioannis Tsamardinos. Scoro-based vs constraint-based causal learning in the presence of confounders. In Cfa wai, pp. 59 67, 2016.
Joannis Tsamardinos, Constantin Aliferis, and Alexander Statnikov. Time and sample efficient discovery of markov blankets and direct causal relations. In Proceedings of the ninth ACM SIGKDD international conference Knowledge discovery and data mining, pp. 673 678, 2003.
Joannis Tsamardinos, Laura E Brown, and Constantin F Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Machine learning, 65(1):31-78, 2006.
Thomas S Verma and Judea Pearl. Equivalence and synthesis of causal models. In Probabilistic and Causal Inference: The Works of Judea Pearl, pp. 221 236. 2022.
Matthew J Vowels, Necati Cihan Camgoz, and Richard Bowden. D'ya like dags? a survey on structure learning and causal discovery. ACM Computing Surveys (CSUR), 2021.
Matej Vuković and Stefan Thalmann. Causal discovery in manufacturing: A structured literature review. Journal of Manufacturing and Materials Processing, 6(1):10, 2022.
Wei Wang, Gangqiang Hu, Bo Yuan, Shandong Ye, Chao Chen, Yayun Cui, Xi Zhang, and Liting Qian. Prior-knowledge-drive local causal structure learning and its application on causal discovery between type 2 diabetes and bone mineral density. IEEE Access, 8:108798 -1108798-108810, 2020.
Xiaoqiang Wang, Yali Du, Shengyu Zhu, Liangjun Ke, Zhitang Chen, Jianye Hao, and Jun Wang. Ordering- based causal discovery with reinforeement learning. arXiv preprint arXic:2105.0660 2021.
Xueqin Wang, Wenliang Pan, Wenhao Hu, Yuan Tian, and Heping Zhang. Conditional distance correlation. Journal of the Americon Statistical Association, 110(512):1726 1776-1444, 2015.
Yi Wang, Xuewei Wang, and Yiyu Cheng. A causal discovery approach to identifying active components of herbal medicine. In 2005 IEFF Engineering in Medicine and Biology 27th Annual Conference, pp. 7718 7721. IEEE, 2006.
Dennis Wei, Tian Gao, and Yue Yu. Dags with no fears: closer look at continuous optimization for learning bayesian networks. Advances in Neural Information Processing Systems, 33:3895 3906, 2020.
Naftali Weinberger. Faithfulness, coordination and causal coincidences. Erkenntnis, 83(2):113 133, 2018
Jing Xiang and Seyoung Kim. A lasso for learning a sparse bayesian network structure for continuous variables. Advances in Neural Information Processing Systems, 26, 2013.
Jun-Gang Xu, Yue Zhao, Jian Chen, and Chao Han. A structure learning algorithm for bayesian network using prior knowledge. Journal of Computer Science and Technology. 30(4):713-72) 2015.
Mengyue Yang, Furui Liu, Zhitang Chen, Xinwei Shen, Jianye Hao, and Jun Wang. Causalvae: Disentangled representation learning via neural structural causal models. In Proceedings of the IEEE/CVE conference on computer vision and pottern recognition, pp. 9593-9602, 2021.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gnn: Dag structure learning with graph neural networks. In International Conference on Machine Learning, pp. 7154-7163 PMLR, 2019.
Yue Yu, Tian Gao, Naiyu Yin, and Qiang Ji. Dags with no curl: An efficient dag structure learning approach. In International Conference on Machine Learning, pp. 12156 12166. PMT., 2021.
60

---

Published in Transactions on Machine Learning Research (09/2023)
Changhe Yuan and Brandon Malone. Learning optimal bayesian networks: A shortest path perspective. Journal of Artificial Intellignnce Research, 48:23 65, 2013.
Keli Zhang, Shengyu Zhu, Marcus Kalander, Ignavier Ng, Junjian Ye, Zhitang Chen, and Lujia Pan. geastle: A python toolbox for causal discovery. arXiv preprint 2Xxm:211111555 2021a.
Keli Zhang, Shengyu Zhu, Marcus Kalander, Ignavier Ng, Junjian Ye, Zhitang Chen, and Lujia Pan. geastle: A python toolbox for causal discovery. arXiv preprint vrXiu:2111.1515.. 2021b.
Kun Zhang and Aapo Hyvärinen. Distinguishing causes from effects using nonlinear acyclic causal models. In Causality: Objectives and Assessment, pp. 157 164. PMLR, 2010.
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. arXiv preprint arXiv: 200..377, 2012.
Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. In International conference on machine learning, pp. 819 827. PMLR, 2013.
Kun Zhang, Zhikun Wang, Jiji Zhang, and Bernhard Schölkopf. On estimation of functional causal models: general results and application to the post-nonlinear causal model. ACM Transactions on Intelligent Systems and Technology (TIST), 7(2):1-22 22, 2015.
Kun Zhang, Biwei Huang, Jiji Zhang, Clark Glymour, and Bernhard Schölkopf. Causal discovery from non- stationary sectaary/hheereee /hetteogeooooouu data: Skeleton estimation and orientation determination. In IJCAI: Proceedings of the Conference, volume 2017, pp. 1347. NIH Public Access, 2017.
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with tears: Continuous optimization for structure learning. Advances in Neural Information Processing Systems, 31, 2018.
Shengyu Zhu, Ignavier Ng, and Zhitang Chen. Causal discovery with reinforcement learning. arXie preprinl arXiv:1906.044 2019.
61


Reviews:
[{"review_id": "v6g0FqV4o6", "reviewer": "Reviewer_hQ5b", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\n1. this paper well presents the basic concepts, terminologies, and assumptions for causal discoveries;\n2. the authors provide a good collection of existing methods with details for both i.i.d. and time series data;\n3. the authors also list a few notable benchmark datasets and did some comparison studies for i.i.d data.\n\n*Weaknesses*\n\n1. As a survey paper, the authors use 7 pages to talk about assumptions and methods for temporal causal discovery, which is very unbalanced compared to the overall (a total of 45 pages). I highly recommend the authors either focus on causal discovery for i.i.d. data, or for temporal data, but definitely not both.\n\n2. As for the part of \"causal discovery for i.i.d. data\":\n\n a. What is the difference between this survey and existing works? To name a few:\n  - Glymour, Clark, Kun Zhang, and Peter Spirtes. \"Review of causal discovery methods based on graphical models.\" Frontiers in genetics 10 (2019): 524.\n  - Nogueira, Ana Rita, et al. \"Methods and tools for causal discovery and causal inference.\" Wiley interdisciplinary reviews: data mining and knowledge discovery 12.2 (2022): e1449.\n  - Spirtes, Peter, and Kun Zhang. \"Causal discovery and inference: concepts and recent methodological advances.\" Applied informatics. Vol. 3. No. 1. SpringerOpen, 2016.\n\n b. Why did the authors separate the score-based and the optimization-based methods? They should all belong to the score-based as the optimization-based methods are also constructing a score.\n\n c. Please be careful to use \"causal discovery\" v.s. \"learning DAG\". These two are different concepts and as a survey, it is important to clarify them.\n\n3. As for the part of \"causal discovery for temporal data\", many things remain unclear:\n\n a. What are rigorous definitions of properties on page 28?\n\n b. What are evaluation metrics here?\n\n c. Why there is no comparison study for causal discovery methods using temporal data?\n\n d. What are the challenges here?\n\nOverall, this paper is trying to put everything which unfortunately loses the main focus and leads to a few notable weaknesses that the authors may consider addressing.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This survey paper focuses on reviewing causal discovery methods for temporal and non-temporal data. Overall, this paper well presents the basic concepts, terminologies, and assumptions for causal discoveries, and provides a good collection of existing methods with details for both i.i.d. and time series data. The authors also list some benchmark datasets and did comparison studies for i.i.d data. However, this paper is trying to put everything which unfortunately loses the main focus and leads to a few notable weaknesses that the authors may consider addressing.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please consider addressing *Weaknesses* above.", "broader_impact_concerns": "The authors may alert audiences in Section 9.2 Applications, that applying causal discovery methods without validating assumption may lead to biased results.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JVTJa4y2kj", "reviewer": "Reviewer_GhUw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe survey is easy to follow and the writing is clear. It covers most of the well-known methods in causal discovery and some new ones. This survey can help beginners quickly become familiar with the methods of causal discovery.\n\nWeaknesses:\nThis survey is more like a list of causal discovery approaches, but it falls short in terms of in-depth analysis and comparisons among these methods. Furthermore, it may be also important to provide some comments about future research directions.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a comprehensive review of causal discovery methods, including well-known methods and some new ones. This survey can help beginners quickly become familiar with the methods of causal discovery.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "This survey lacks in-depth analysis and comparisons among the different causal discovery approaches. Therefore, it is recommended that the authors incorporate more comprehensive analyses of the advantages and disadvantages associated with each method, along with guidance on selecting appropriate approaches based on different conditions. Additionally, the inclusion of more empirical results would greatly enhance the overall quality and usefulness of the survey.\n\n\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zE4a7GfAFJ", "reviewer": "Reviewer_xzg1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- This review is quite long and covers both i.i.d. and times series data causal discovery methods. In term of pure contents, this list is quite extensive.\n- list of toolboxes and implementation of each method is quite useful \n- for each method, authors add some detailed discussed on their approaches. \n\n\nWeaknesses:\n\n- the benchmark experiment does not quite compare each method extensively, and only done with i.i.d. data. No conclusion or guidance is provided in this regard, so experiment section is lacking. \n- There are a few presentation issues (discussed below). Mainly, I feel the organization of methods does not make too much sense in a lot of places, and some explanation or justification are needed. \n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "this paper is a survey on existing causal discovery method for i.i.d. and time series data. It discuss some of relevant methods in these areas, as well as metrics, datasets, and available software and toolboxes. In addition, some prior knowledge based approaches are discussed, which is also quite different from existing literature. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Title: temporal data contains irregular time series data (using authors's definition, non-consistent interval data) as well and quite a few causal discovery, which this paper does cover. Authors should just use time series or specify regular time series. Moreover, since authors discuss and used more contents to cover i.i.d. case, it does not make sense to put \"non-temporal\" after \"temporal\" data, \n\n- page 2, paragraph 2: a lot of citation are wrongly attributed and should go back to original papers. For example, Chen et al 2021b and Hasan & Ganni 2022 cannot be the first one who mentioned RCT cost.\n\n- by combining i.i.d. data and time series data survey into one, authors maybe could offer some insight across both regimes, which would justify such a combination. \n\n- background knowledge: typical tabu list or other background knowledge is heavily related to Bayesian formulation (as prior). Authors could have explored this direction and related literature much further. \n\n- I suggest authors make a separate section and add more related works on learning graphs with latent variables (there are way more works around MAG/ADMG/latent tree learning, from Richardson et al, and growing body of literature in recent AI conferences) or condense these methods just to briefly describe them, as I don't think they are the focus on this work. \n\n- Organization and Figure 9: while some existing literature my use such taxonomy, I do not quite agree such a classification of different methods, as they are quite confusing and do not illustrate the differences among each other. For example, continuous optimization methods a lot of times uses functional causal model based models (the reason is they share similar objective functions), and dividing them into different categories does not make much sense. In addition, the continuous optimization or gradient-based approach in name is just an optimization approach, in contrast to traditional discrete optimization (such as search approaches, including integer programming formulation used in score-based methods). Their objectives are a scoring function as well (for example, least square or others are log-likelihood objective scores. They may not use Bayesian prior such as complexities in BIC, but they have L1 as complexity control. Overall, they are still a scoring function). Hence, they are also score-and-search methods (just different searching strategies). Prior knowledge based may just be additional constraints in the optimization process, and can be constraint or score-based. Overall, this organization is quite superficial. \n\n- Some inclusion of algorithms and/or its placement in the section organization are quite arbitrary. For example, RRCD seems for relation data, but not pure i.i.d. or times series data. Some algorithms like ANM and PNL focuses on bivariate cases instead of learning the whole graphs, and authors fail to distinguish and highlight it for each method. I'm not sure if JCI with multiple datasets or domains count as prior knowledge or background knowledge based approaches (maybe a separate direction for causal algorithms to improve generalization. along with CD-NOD - which is not for time series data, makes more sense). Moreover, I don't think CausalVAE fit in causal discovery algorithms, as they never evaluate CD performances. \n\n- Moreover, A few important works are not included. For example, a big part of score-based approaches on dynamic programming and integer programming causal discovery algorithms are not discussed (they are the state of the art methods in exact causal discovery learning). Popular CAM method (which include PNS) is not discussed. DAG-NoFear, which highlights the limitation of gradient-based methods, is not discussed. \n\n- While it is nice to have discussion on each method, the overall clarity on the similarity and difference between each method is not very high. If there is a complete list of dimensions to organize and compare these methods, it would greatly improve the paper. Maybe a summarizing table or figure along these dimensions would be useful. \n\n- Which metric is more insightful, and which is problematic? or what conditions does one should consider use them?\n\n- Some datasets do not have link provided, while others do. \n\n- Benchmark: how do you generate data, as some algorithms are traditionally use discrete data while others use continuous algorithms?\n\n\nOther: \n\n- \"gold standard\"\n- \"no cycle among edges\" vague\n- \". While every endogenous variables\" fragment\n- \"existence of selection biases ...\" I don't think these assumptions are common for causal discovery algorithms talked in the paper.\n- Anytime FCI \"takes into consider selection bias\" but authors mention FCI works \"in the presence of many arbitrary latent and selection variables\". \n- PNL \" effectively separate cases ..\" more details needed on \"effectively\". ", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The balance of the reviewer sentiment is more towards accept than reject. There were initial and lingering concerns that the material would be better presented as two separate papers: one survey on causal discovery for IID data and one survey on causal discovery for time series data. This may be more of an editorial choice on the part of the authors and did not seem to diminish the quality of the claims or support of the evidence. Indeed, by combining them into one paper the audience may be able to better understand the similarities and differences between methods for each type of data. Overall, the survey is a timely contribution to the causal discovery literature and meets the acceptance criteria for the venue.
Decision: Accept (poster)