0cm part[0cm] chapter[1.25cm] []1.25cm *[.5pc].  section[1.25cm] []1.25cm []
subsection[1.25cm] []1.25cm *[.5pc]. [] figure[0em] *[.5pc]. [] table[0em]
*[.5pc]. [] lchapter[0em] []1.25cm *[.5pc].  lsection[0em] []1.25cm
lsubsection[.5em]

Discovering Causal Relations and Equations from Data A review of methods,
challenges and opportunities
*0.5cm August 28, 2024

Copyright © 2023 Gustau Camps-Valls, Andreas Gerhardus, Urmi Ninad, Gherardo
Varando, Georg Martius, Emili Balaguer-Ballester, Ricardo Vinuesa, Emiliano
Diaz, Laure Zanna, Jakob Runge

http://isp.uv.es

First version, August 28, 2024

> Discovering Causal Relations and Equations from Data
>
> Gustau Camps-Valls1,†, Andreas Gerhardus2,∗, Urmi Ninad3,∗, Gherardo
> Varando1,∗, Georg Martius4,5, Emili Balaguer-Ballester6,7, Ricardo Vinuesa8,
> Emiliano Diaz1, Laure Zanna9, Jakob Runge2,3
>
> 1Universitat de València, València, Spain
>
> 2German Aerospace Center, Jena, Germany
>
> 3Technische Universität Berlin, Berlin, Germany
>
> 4University of Tübingen, Tübingen, Germany
>
> 5Max Planck Institute for Intelligent Systems, Tübingen, Germany
>
> 6Bournemouth University, Bournemouth, UK
>
> 7Medical Faculty Mannheim and Heidelberg University, Mannheim, Germany.
>
> 8KTH Royal Institute of Technology, Stockholm, Sweden
>
> 9New York University, New York, USA
>
> ∗ These authors contributed equally.
>
> † Corresponding author at Image Processing Laboratory (IPL), E4 building -
> 4th floor, Parc Científic Universitat de València. C/ Cat. Agustín Escardino
> Benlloch, 9. 46980 Paterna (València). Spain. E-mail address:
><EMAIL_ADDRESS>
###### Contents

  1. 1 Introduction
    1. 1.1 Understanding in the physical sciences
    2. 1.2 Scientific discovery
      1. 1.2.1 Elements of scientific discovery
      2. 1.2.2 Elements of knowledge
      3. 1.2.3 Elements of models, governing equations and laws
    3. 1.3 Knowledge discovery from data
      1. 1.3.1 Discoverability and heuristic strategies
      2. 1.3.2 Modern approaches to data-driven discovery
      3. 1.3.3 AI for scientific discovery
    4. 1.4 Outline
  2. 2 Causal discovery in the physical sciences
    1. 2.1 A taxonomy of causal discovery methods
      1. 2.1.1 Preliminaries
      2. 2.1.2 Axes for categorising causal discovery methods
      3. 2.1.3 Description and categorisation of causal discovery methods
    2. 2.2 Challenges
      1. 2.2.1 Process challenges
      2. 2.2.2 Data challenges
      3. 2.2.3 Statistical and computational challenges
    3. 2.3 Opportunities for the physical sciences
      1. 2.3.1 Causal hypothesis testing and targeted interventions
      2. 2.3.2 Cause-effect estimation
      3. 2.3.3 Causal pathway analysis and mediation
      4. 2.3.4 Identifying causes and pathways leading to anomalies
      5. 2.3.5 Causal complex network analysis
      6. 2.3.6 Causally robust forecasting models
      7. 2.3.7 Physical simulation model evaluation
      8. 2.3.8 Counterfactual causal attribution of extreme events
      9. 2.3.9 Signal tracking for the discovery of proximal causes
      10. 2.3.10 Causal benchmarks, software and platforms
    4. 2.4 Perspectives
  3. 3 Learning physical laws from data
    1. 3.1 Explicit equation discovery with symbolic regression
      1. 3.1.1 Symbolic regression using discrete search methods
      2. 3.1.2 Sparse linear regression and neural network approach
      3. 3.1.3 Learning to solve symbolic regression
      4. 3.1.4 Comparison
    2. 3.2 Implicit equation discovery: dimensionality reduction and transfer operators
      1. 3.2.1 Reduced-order models
      2. 3.2.2 Transfer operators for learning nonlinear dynamics
      3. 3.2.3 Dynamic modes in neural-network latent spaces
      4. 3.2.4 Equation discovery in latent representations
      5. 3.2.5 Discovering fundamental variables
    3. 3.3 Perspectives
      1. 3.3.1 Challenges
      2. 3.3.2 Opportunities
  4. 4 Case studies in the physical sciences
    1. 4.1 Neuroscientific applications of physics-based machine learning
      1. 4.1.1 Overview of parsimonious models for neural population dynamics
      2. 4.1.2 Empirical reconstruction of neuronal trajectories
    2. 4.2 Learning causally interacting brain regions
      1. 4.2.1 Causality in the connected brain
      2. 4.2.2 Causal methods in neuroscience
    3. 4.3 Learning causal graphs of carbon and water fluxes
      1. 4.3.1 Introduction
      2. 4.3.2 Clustering of biosphere-atmosphere causal graphs at the site level
      3. 4.3.3 Causal relations at global scale
    4. 4.4 Causal climate model intercomparison
    5. 4.5 Learning density functionals
    6. 4.6 Discovering governing equations in boundary-layer transition to turbulence
    7. 4.7 Learning reduced-order models for vortex shedding behind an obstacle
    8. 4.8 Uncovering new physical understanding in wall-bounded turbulence
    9. 4.9 Discovery of ocean mesoscale closures
  5. 5 Concluding remarks
  6. Acknowledgements & Contributions

## Preface

> “As in Mathematics, so in Natural Philosophy, the Investigation of difficult
> Things by the Method of Analysis ought ever to precede the Method of
> Composition. This Analysis consists in making Experiments and Observations,
> and in drawing general Conclusions from them by Induction, and admitting of
> no Objections against the Conclusions, but such as are taken from
> Experiments, or other certain Truths … By this way of Analysis, we may
> proceed from Compounds to Ingredients, and from Motions to the Forces
> producing them; and in general, from Effects to their Causes, and particular
> Causes to more general ones, till the Argument end in the most general. This
> is the Method of Analysis” (Newton, 1718).

Physics is a field of science that has traditionally used the scientific
method to answer questions about why natural phenomena occur and to make
testable models that explain the phenomena. Discovering equations, laws and
principles that are invariant, robust and causal explanations of the world has
been fundamental in physical sciences throughout the centuries. Discoveries
emerge from observing the world and, when possible, performing interventional
studies in the system under study. With the advent of big data and the use of
data-driven methods, causal and equation discovery fields have grown and made
progress in computer science, physics, statistics, philosophy, and many
applied fields. All these domains are intertwined and can be used to discover
causal relations, physical laws, and equations from observational data. This
paper reviews the concepts, methods, and relevant works on causal and equation
discovery in the broad field of Physics and outlines the most important
challenges and promising future lines of research. We also provide a taxonomy
for observational causal and equation discovery, point out connections, and
showcase a complete set of case studies in Earth and climate sciences, fluid
dynamics and mechanics, and the neurosciences. This review demonstrates that
discovering fundamental laws and causal relations by observing natural
phenomena is being revolutionised with the efficient exploitation of
observational data, modern machine learning algorithms and the interaction
with domain knowledge. Exciting times are ahead with many challenges and
opportunities to improve our understanding of complex systems.

##  Chapter 1 Introduction

This paper reviews the recent advances in causal discovery and equation
discovery from data. Both problems are conundrums for scientists and
philosophers of science. After all, Science is about studying, discovering,
and understanding the structure and behaviour of the physical and natural
world through observation and experimentation. Understanding the system’s
structure involves performing interventions on the systems to evaluate their
responses. However, interventional experiments are often not feasible for
economic or ethical reasons, so relying on observations, simulations, and
domain knowledge must be exploited. In recent decades, discovering causal
relations and underlying governing laws from data have emerged as exciting
fields of research that promise advancing science.

###  1.1 Understanding in the physical sciences

A pertinent question arises here; what is understanding? Understanding is the
ability to comprehend and make sense of processes to gain a deeper knowledge
of a system. Understanding involves analysing information, making (eventually
causal) connections, and coming to conclusions. Whether the conclusions should
be falsifiable has been the subject of active discussion in the Philosophy of
Science (Popper, 2005; Munz, 2014). We aim to understand complex systems by
following the scientific method; make an observation, ask a scientific
question, form a hypothesis, theory, model, or explanation of the phenomena,
and make predictions, which are ultimately tested and whose results are used
to make new hypotheses or predictions (see Fig. 1.1).

ExperimentsTheory/modelPredictionsObservationsinferencehypothesis testing
Figure 1.1: Standard loop in understanding complex systems following the
standard scientific method. Understanding involves experimentation by refining
a descriptive mechanistic model. The initial model hypothesis is tested in
practice and, through experiments, yields observations that are confronted
with the model’s predictions. The unexplained processes are then used to
improve the model’s misspecification and predictions.

Understanding involves reasoning and thinking critically about a subject, a
system’s behaviour, or a problem. Understanding and explaining how a system
works is more complicated than making predictions about the system’s
behaviour. The Oracle of Delphi gave accurate predictions of the future and
the optimal course of action, but the lack of understanding frequently led to
disaster. True understanding is about making (truly accurate) predictions and,
more importantly, gaining knowledge of the causal chain. Science generally
aims to answer causal questions, infer causal relations, and attain
mathematical models (mainly laws and equations) that work well in most
situations, explain the system and underlying processes, and are invariant
across space and time. Without it, we cannot predict the consequences of our
actions (interventions) or analyse when, where and why things went wrong
(counterfactuals) (Pearl, 2009c).

Figure 1.2: The Oracle of Delphi at inference time.

Yet, what do we want to understand? And how do we generally do it? In physical
sciences, one typically analyses phenomena and instantiations of the physical
world, uses observations, and refines and tests models. For learning about the
system, one aims to (1) characterise its complexity in terms of trajectories,
persistence, stability and collapse, bifurcations and viability boundaries
(Sterman, 1994; Kwapień and Drożdż, 2012; Salcedo-Sanz et al., 2022; May,
1972), (2) obtain explanatory and causal models of their behaviour (Pearl,
2009a; Peters et al., 2017a; Runge et al., 2019a), and (3) discover and
formalise general laws, governing equations, and parameterizations
(Richardson, 1996; Brunton et al., 2016b; Chen et al., 2022). These three
components allow us to advance science and technology. However, in many
systems, governing equations and causal relations are (partially) unknown, and
recourse to first principles is untenable. Resorting to algorithms that can
discover laws, governing equations, and causal relations from data may thus
constitute a paradigm shift that promises to accelerate science.

###  1.2 Scientific discovery

Before revising the fields, let us take a step back and review the formalism
in the logic of science and the key elements, definitions, and challenges we
face in addressing such problems. What are the cornerstones for understanding
how science and the scientific method work? The philosophy of science studies
science’s assumptions, foundations, and implications. It examines the
implications of scientific theories and methods for understanding the world.
It concerns the fundamental questions at the heart of science, such as the
nature of knowledge, the limits of scientific inquiry, and the relationship
between science and values.

Scientific discovery is the process or product of successful scientific
inquiry. Objects of discovery can be things, events, processes, causes,
properties, theories, hypotheses, and their characteristics. Philosophical
discussions of scientific discovery vary widely in scope and definition, from
the narrowest sense of a “eureka moment” to the broadest sense of a
“successful scientific endeavour”. The utilisation of data sets to create and
test new hypotheses in philosophical discourse has led to a multifaceted and
intricate discussion regarding the precise definition and potential misuse of
the term “discovery”.

Figure 1.3: Archimedes (287-212 BC) in his bath. A woodcut by Flörtner
(1490-1546).

Human nature aims to discover. Always. Since the Bronze
Age111https://en.wikipedia.org/wiki/Timeline_of_scientific_discoveries .
Generations have created and discovered new principles, techniques, and
operations through millennia. Right after the Neolithic Revolution, the world
stopped except for some remarkable technological advances, like the invention
of the water wheel (476-221 BC) and the windmill (ca 644 BC). Romans were
amazed by stories of what Archimedes (287-212 BC) had been able to do. But,
bold as it may sound, one may claim that modern science was invented between
1572 when Tycho Brahe saw a nova or new star, and 1704 when Newton published
his Opticks (Wootton, 2015). What happened in that period prepared humanity
and scientists for a New Era: a research program endorsed with a scientific
method that allowed scrutinising new theories and validating or refuting
hypotheses and models of the world, and all that in the light of evidence and
observations. After fitting many ovoids to observational data, Kepler
discovered the laws of planetary motion (1609) and needed four years to
discover Mars’ orbit was an ellipse. The scientific method was slow but sure.
Galilei discovered the law of falling bodies (1638) by dropping two
cannonballs of different masses from the tower of Pisa and measuring the
effect of mass on the fall rate to the ground. And in 1662, Boyle discovered
the law of ideal gases. Only ten years later, in 1672, Newton discovered that
white light is a mixture of distinct coloured rays, and in 1687 he formulated
the classical mathematical description of the fundamental force of universal
gravitation and the three physical laws of motion. The triumph of Newtonianism
marks the end of the beginning of scientific discovery.

The history of science is a long and complex narrative punctuated by moments
of major scientific revolutions (Kuhn, 1962). Kuhn identified a general
pattern: A discovery is not a simple act but an extended, complex process that
culminates in paradigm changes. These events mark a fundamental shift in how
science is understood and practised and have greatly impacted scientific
progress. The first scientific revolution occurred in the 16th and 17th
centuries when the Copernican revolution challenged the traditional Ptolemaic
view of the universe (Copernicus et al., 1965). The next major scientific
revolution was the Enlightenment during the 18th century, which saw the
emergence of the scientific method and the development of modern physics and
chemistry, from formulating the laws of motion to discovering electricity.
This period also saw the emergence of scientific societies, which helped to
propagate and popularise scientific ideas. The 19th century saw the emergence
of the theory of evolution, which revolutionised the field of biology (Darwin,
1859). This revolution was followed by the rise of modern genetics, which
further expanded our understanding of the evolution of life (Watson and Crick,
1953). The 20th century saw the emergence of the quantum revolution, which
revolutionised our understanding of the physical world as it could not be
fully explained by classical physics (Heisenberg, 1925). Revolutions happen
only gradually, as it takes time for the scientific community to recognise
“both that something is and what it is” (Kuhn, 1962). Eventually, a new
paradigm becomes established, and the strange phenomena become the expected
phenomena.

The idea that there is such a thing as ‘the Scientific Revolution’ and that it
took place in the 17th century is thus a fairly recent one (Butterfield,
1965); some have argued that it can be seen as the construction of
intellectuals looking back from the 20th century (Wootton, 2015). Like the
term ‘Industrial Revolution’, the idea of a scientific revolution brings
problems of multiplication (how many scientific revolutions?) and
periodisation (how often?). Some philosophers of science have argued for
continuity, others have sought multiple revolutions: the Darwinian revolution,
the Quantum revolution, the DNA revolution, and so on, while others claim that
the real Scientific Revolution came in the 19th century when science and
technology married. Recently, we are witnessing the so-called 4th Industrial
Revolution, which conceptualises rapid change to technology, industries, and
societal patterns due to increasing interconnectivity, smart automation and
the amalgamation of artificial intelligence and automated machines. Yet, is it
only a technological revolution, or can machines discover and explain new
science? Are we facing the emergence of machine discovery of science?

Figure 1.4: Left: The title page of Johannes Stradanus’s New Discoveries
(‘Nova reperta’, c.1591) summarises the knowledge that marks off the modern
world from the ancient: the discovery of America, the invention of the
compass, the printing press, the gunpowder, the clock, silk weaving,
distillation and the saddle with stirrups. Right: Can AI start a new
scientific revolution? Is AI itself the scientific revolution?

####  1.2.1 Elements of scientific discovery

During the 18th and 19th centuries, the different elements of discovery
gradually became separated and discussed in more detail. Discussions concerned
the nature of observations and experiments, the act of having insight and the
processes of articulating, developing, and testing the novel insight. For
Whewell, for example, discovery comprised three elements: the happy thought,
the articulation and development of that thought, and the testing or verifying
it. In contrast to many 20th-century approaches, Whewell’s philosophical
conception of discovery articulates happy thoughts and integrates the process
of verification as an integral part of discovery. Thus, to verify a
hypothesis, the scientist needs to show that it accounts for the known facts,
that it foretells new, previously unobserved phenomena, and that it can
explain and predict phenomena which are explained and predicted by a
hypothesis that was obtained through an independent happy thought-cum-
colligation (Ducasse, 1951). Until the late 20th century, most philosophers
operated with a narrower notion of discovery than Whewell’s. Controversies in
the 20th century moved around whether or not the discovery process should
include the articulation and development of a novel thought.

####  1.2.2 Elements of knowledge

Throughout history, many scientific accounts have described methods of
knowledge generation and scientific reasoning without explicitly labelling
them as such. These methods include using the senses to gather knowledge,
observation and experimentation, analysis and synthesis, induction and
deduction, hypotheses, probability, and certainty (Table 1.1). By exploring
these methods, scientists have generated new knowledge and developed theories
about the nature of matter and natural forces. These methods are integral to
scientific inquiry and continue to be used today.

In the early modern period, authors such as Bacon and Newton advanced ideas
about generating and verifying empirical knowledge and the difficulties that
may arise in scientific inquiry. These theories were closely linked to
theories about matter and force. However, by the 18th and 19th centuries,
authors on scientific method and logic began citing early modern approaches to
model proper scientific practice and reasoning. At the same time, the
connection between the two was gradually severed. It was common in 20th-
century philosophy of science to draw a sharp contrast between those early
theories of the scientific method and modern approaches. Yet, recent research
in the history of the philosophy of science has shown that the development of
the scientific method was a gradual and ongoing process rather than a sudden
shift from one approach to another.

Yet, how can we build knowledge? Knowledge is a well-studied, yet elusive,
concept in the philosophy of science (Popper, 2005). Knowledge can be acquired
through observation, experimentation, and reasoning and is often expressed
through language, symbols, and concepts. In quantitative physical sciences, we
encapsulate our domain knowledge in mathematical constructs and equations that
describe the system under consideration. Knowledge is built on facts, that is,
observations about the physical world that are accepted as true and are often
the starting point for deeper analysis and understanding. Empiricism offers
resorts to perform experiments that are used to test the validity of facts and
to gain further insight into the underlying causes and effects of phenomena.
From there, scientists construct laws, which are generalisations based on many
observations and experiments, the rules describing the behaviour of a system
that can be used to predict future outcomes. In the scientific method,
hypotheses are testable explanations for facts and laws based on evidence but
have not been proven true. See Table 1.1.

We must use judgement to evaluate the validity of facts, experiments, laws,
hypotheses, theories, and evidence. Judgement involves forming an opinion or
deciding based on evidence and knowledge through reasoning and considering our
conclusions’ potential implications. Judgement is important in all aspects of
knowledge, from generating new ideas to applying existing knowledge. It is
important to remember that knowledge is not static but an ongoing discovery,
analysis, and interpretation process. New theories and hypotheses can be
formed as new evidence is discovered, and existing knowledge can be refined or
overturned. Formalising new knowledge needs arguments, which can be inductive,
deductive, analogical, and statistical. Inductive arguments are based on
observations and generalisations, while deductive arguments are based on
logical reasoning. Analogical arguments are based on similarities between two
or more cases, while statistical arguments are based on data and evidence and
formally linked to the probability theory.

##### Objectivity and subjective conviction.

Objectivity is the idea that scientific inquiry should be based on factual
evidence and logical reasoning, independent of personal bias or opinion.
Objectivity, as a (causal) statement, should be inter-subjectively tested
according to Popper (Popper, 2005) or be valid, justifiable or verifiable in
the sense of Dickerson (Dickerson, 2003). Objectivity can be challenged
because some scientific theories can never be fully justifiable or verifiable
but testable (i.e. reproducibility). On the contrary, conviction relies on
believing the inquiry’s findings are true and trustworthy, stating a
scientific argument without proofs (Popper, 2005). Conviction implies
arguments based on mere association, which are not necessarily causal,
verifiable, testable or reproducible and cannot justify a scientific statement
(Pearl, 2009c).

##### Universality, falsifiability, and consistency.

The concepts of universality, falsifiability, and consistency are essential
tools for understanding scientific method (Popper, 2005) (Table 1.1).
Universality, the principle of universalism, is the idea that scientific
truths can be applied to all situations. It is a fundamental tenet of
scientific inquiry, implying that the same principles can be used to explain
phenomena in different contexts. This allows scientists to conclude the
natural world, not limited to a single instance or context. It also makes
experiments more reliable and reproducible, as results can be compared across
multiple contexts. The latter relates to falsifiability introduced by Popper
(Popper, 2005): a scientific hypothesis must be tested and disproved.
Falsifiability is important for scientific research, as it allows for the
testing and refining of hypotheses. The concept of falsifiability is used to
evaluate the validity of scientific claims, as it implies that a hypothesis
can be disproved if it does not fit the evidence. Yet, scientific theories
must remain consistent over time; any change or modification to a scientific
theory must be able to be explained by existing evidence. Newton first
proposed this concept in the 17th century (Newton, 1833). All three concepts
remain an important part of the scientific method.

##### Empiricism.

Empiricism is a philosophical position that asserts that knowledge must be
acquired through sensory experience (Sellars et al., 1956). This means
knowledge is not innate and can only be gained through observation and
experimentation. Empirical evidence is necessary for scientific progress as
the only reliable way of assessing the validity of theories and hypotheses.
Empiricism is closely associated with the scientific method, as it gathers
data and evidence to understand the world comprehensively. This data then form
hypotheses and theories explaining why certain phenomena occur worldwide.
Empiricism has been challenged most notably by Feyerabend (Feyerabend, 1981),
where realism is promoted to enable the proliferation of new and incompatible
theories. This way, scientific progress comes through “theoretical pluralism”
allowing a plurality of incompatible theories, each of which will contribute
by competition to maintaining and enhancing the testability, and thus the
empirical content, of the others.

####  1.2.3 Elements of models, governing equations and laws

##### Identifiability and equifinality.

A relevant problem in model development is identifiability, the property by
which learning the true values of a model’s underlying parameters is
theoretically possible from an infinite number of observations (Ljung and
Glad, 1994; Peters et al., 2011). The impossibility arises when two more model
parameterisations are observationally equivalent, i.e., indistinguishability.
This situation is sometimes called equifinality; one can achieve the same
result or state description by many potential solutions and model
parameterisations. This is a very active field of research in statistics,
machine learning and functional analysis, where regularisation helps.
Combining domain knowledge with data-driven approaches, for example, may
alleviate cases of model misspecification, as the model solution would be
confined to a solution subspace with little expressive power and even
implausible solutions.

##### Compressibility, sparsity and compositionally.

A desirable property of models and governing equations is compositionality, by
which theory/models are typically a composition of a small set of elementary
functions (Udrescu and Tegmark, 2020). The problem of attaining compositional
models is challenging, as misspecification arises when defining model
components or facing multidimensional compositions. Compositionality also
advocates for sparse models, where combinations of simpler explanations are
preferred, directly implementing Occam’s razor in the model search. Besides,
intimately related, we find the desirable property of compressibility by which
data/models are compressible if and only if they exhibit a pattern: this way,
high-level models are much simpler than their low-level counterparts (Dennett,
1991; Shannon, 1948; Kolmogorov, 1963). As for attaining compositional models
or achieving the model’s sparsity, estimating multivariate information-
theoretic estimates is challenging here.

##### Generalisation, robustness, invariance and extrapolation.

Models should operate well in unseen but similar situations. The
generalisation property (or generalizability) gives confidence in the model’s
performance, expressive power, and predictions. Models operating in out-of-
the-sample regimes tend to extrapolate, thus compromising trustworthiness.
Extrapolation is about inferring the unknown from the known, estimating beyond
the original observation range, and predicting future data by relying on
historical data (Scott Armstrong and Collopy, 1993). Since the governing
equations and laws of Physics are invariant through space and time, inferred
models should be. However, attaining robust models that generalise well and
implement properties of invariance is typically challenged by the lack of
reliability of the data source, the accuracy of the extrapolation process
itself, the complexity of the data, and the potential for errors in the
extrapolation.

Table 1.1: Key concepts, definitions, and challenges for understanding complex systems from data.  Concept |  Definition |  Challenge in causal/equation discovery
---|---|---
Logic of scientific discovery
Consistency |  theory not leading to logical contradictions; refutes/includes/generalises previous theories; (Gödel, 1931; Tarski and Tarski, 1994; Popper, 2005) |  impossibility to perform controlled experiments repeated observations, or survey research; cf. hypothesis testing
Deduction |  type of inference where the conclusion follows logically from its premises (Johnson-Laird and Byrne, 1991; Popper, 2005) |  deduction breaks under confounders
Empiricism |  principle that only ‘experience’ can decide about the truth or falsity of a factual statement (Popper, 2005); central role of empirical evidence to form ideas, rather than innate ideas or traditions; cf. induction |  impossibility to perform experiments or access observations
Explanation |  deduction of a statement that describes the event using as premises one or more universal laws, together with certain singular statements (initial conditions) (Popper, 2005; Pearl, 2009c) |  no formal principle of causality or universal causation available
Falsifiability |  capacity for some proposition, statement, theory, or hypothesis to be proven wrong (Popper, 2005) |  discovered models and laws can be misspecified, untestable or incomplete
Induction |  method of reasoning where a general principle is derived from a set of observations (Popper, 2005; Munz, 2014; Reichenbach, 1991; Keynes, 2013), cf. generalisation (sample to population), probabilistic inference |  impossibility, data scarcity or conditions; unlike in deduction, the truth of the conclusion is only probable
Objectivity |  (causal) statement that can be inter-subjectively tested (Popper, 2005) or that is valid, justifiable or verifiable (Dickerson, 2003) |  elusive term, scientific theories can never be fully justifiable or verifiable, but testable, cf. reproducibility
Conviction |  stating a scientific argument without proofs (Popper, 2005) |  mere association is not causal, verifiable, testable or reproducible and cannot justify a scientific statement
Universality |  universal facts exist and can be progressively discovered, as opposed to relativism (Popper, 2005) |  model misspecification, reproducibility, theory testability; Universal laws transcend any finite number of their observable instances
Equation discovery: model properties and data challenges
Compositionality |  theory models are typically a composition of a small set of elementary functions (Udrescu and Tegmark, 2020) |  misspecification, multidimensional compositions
Compressibility |  data/models are compressible iff exhibit a pattern, high-level models are much simpler than their low-level counterparts (Dennett, 1991; Shannon, 1948; Kolmogorov, 1963) |  multivariate information-theoretic estimates are difficult, cf. sparsity
Extrapolation |  inferring the unknown from the known, estimation beyond the original observation range, predicting future data by relying on historical data (Scott Armstrong and Collopy, 1993) |  reliability of the data source, the accuracy of the extrapolation process itself, the complexity of the data, and the potential for errors in the extrapolation
Generalization |  model’s ability to adapt to new, unseen data drawn from the same/similar distribution as the one used to create the model (Vapnik, 1999) |  hard to evaluate, pointless in regime/domain shift, cf. extrapolation
Identifiability |  learning the true values of a model’s underlying parameters is theoretically possible from an infinite number of observations (Ljung and Glad, 1994; Peters et al., 2011) |  two or more model parameterisations are observationally equivalent, cf. indistinguishability, equifinality
Invariance |  probability of a certain event occurring remains the same, regardless of any changes to the underlying system or process (Olver, 1999; Kallenberg, 2005) |  strong assumption in many complex systems
Robustness |  property of models to perform well in noisy environments (presence of outliers, mixed noise distributions, missing data), extrapolation regimes, covariate shift |  hard-to-identify regimes, design model’s regularisers, cf. inductive bias, priors, Bayesian inference
Separability |  model can be written as a sum or product of two parts with no variables in common (Udrescu and Tegmark, 2020) |  misspecification, oversimplification
Smoothness |  model is continuous and perhaps even analytic in its domain (Schölkopf et al., 2021) |  oversimplification, inappropriate to deal with regime shifts and anomalies
Symmetry |  model exhibits translational, rotational, or scaling symmetry concerning some of its variables (Udrescu and Tegmark, 2020) |  inappropriate for unstructured data, macroscale-vs-microscale systems
Uncertainty |  epistemic situations involving imperfect or unknown information; it applies to predictions of future events, to physical measurements that are already made, or to the unknown (Lindley, 2013; Keynes, 2013) |  partially observable or stochastic environments, yet difficult to disentangle the sources and to quantify it properly
Units |  models & corresponding variables have known physical units (Udrescu and Tegmark, 2020) |  dealing with unknown factors and confounders
Causal inference: discovery, cause-effect estimation & counterfactuals
Causal discovery |  Reconstructing the full causal graph or pairwise causation from data and assumptions (Pearl and Mackenzie, 2018; Peters et al., 2017a) |  challenging, limited data, poor assumptions, incomplete knowledge, untestable
Causal effects |  Estimating causal effects (of hypothetical interventions) in terms of expectations or full interventional distributions (Winship and Morgan, 1999; Pearl, 1995) |  incomplete knowledge, untestable
Confounder |  variable causally associated with both exposure and outcome and not on the causal pathway between $X$ and $Y$ (Pearl, 2009c; Morgan and Winship, 2015; Spirtes et al., 1995) |  unobserved processes, hidden confounding, bidirected edges, periodicity, slow-time scales, discrete states
Counterfactuals |  Attribution of observed events or mediation analysis (Pearl, 1995; Morgan and Winship, 2015) |  incomplete knowledge, untestable
Covariate shift |  The system’s probability density function changes through time or space (Sugiyama and Kawanabe, 2012) |  hard to detect and correct models for, cf. invariance
Dependencies |  models trained to maximise statistical measures of linear or nonlinear association, or in-distribution prediction (Kotz and Drouet, 2001) |  non-causal, right-for-the-wrong-reasons
Faithfulness |  only the variables that are $d$-separated in a DAG will be independent (i.e., all others will be dependent) (Pearl, 2009c) |  requires an understanding of how different variables work together to cause an outcome
Missingness |  unobserved quantities or random variables, either missing at random or through particular mechanisms (McKnight et al., 2007) |  potentially leading to selection bias

###  1.3 Knowledge discovery from data

####  1.3.1 Discoverability and heuristic strategies

The questions of what and how phenomena and mechanisms can be discovered have
been the subject of intense research and philosophical discussion. In the
philosophy of science, discoverability is the concept that scientific
knowledge must be discoverable and verifiable (Ducasse, 1951; Popper, 2005;
Langley, 2019; Langley et al., 1987b; Klahr and Simon, 1999). This means that
hypotheses or theories must be supported by evidence and based on empirical
observations and data. Furthermore, scientific knowledge must be available for
anyone to see and verify, ensuring that it is not biased or limited to a
specific group of people.

Recent advancements in the philosophy of science have seen a revival of
interest in heuristic strategies to discover knowledge; these strategies are
seen as problem-solving activities, whereby a discovery is a solution to a
problem. Heuristics-based discovery methodologies are neither completely
subjective and intuitive nor algorithmic or formalisable. This view has
shifted the scientific researcher from being viewed as a ‘puzzle solver’ to a
‘problem solver’ and ‘decision maker’ in complex, variable, and changing
environments (Wimsatt and Wimsatt, 2007). In this paper, we will review
mathematical models that address equation discovery and causal discovery by
generally formalising the problems as concrete statistical inference tasks;
regression, conditional dependence or density estimation.

####  1.3.2 Modern approaches to data-driven discovery

Observational discovery relies on modelling. Yet, what types of models? Table
1.2, cf. (Peters et al., 2017b), gives a simple categorisation of models from
mechanistic/physical models based on first principles and (rigid) equations
and laws but with desirable properties of interpretability, invariance and
robustness to distribution shifts, to purely statistical (machine learning)
models that excel in prediction and are learned from data. In the middle, we
have structural causal models, which can answer counterfactual questions but
do not necessarily capture physical knowledge. All three models are used in
quantitative data-driven science and map to different levels of discovery:
learning statistical associations in data streams, identifying causal
relations between variables, and discovering equations from data. Note the
resemblance to the Ladder of Causation proposed by Pearl and Mackenzie (2018)
with three rungs: association, intervention, and counterfactual. Discovering
causal and physical laws from observations is a paradigm shift in AI and can
impact the physical sciences and other disciplines. The fields of discovery of
scientific knowledge and causal models of scientific phenomena are intertwined
and tightly connected: our scientific endeavour is constantly challenged with
causal questions, robust model building, intervention analysis, and hypothesis
testing. The fields also share important theoretical challenges, where
generalizability, compressibility, robustness, invariance, and extrapolation
come into play.

Table 1.2: Simple taxonomy of models and their level. Figure partly reproduced from (Peters et al., 2017a). Model/Level | i.i.d. | distribution shifts | Counterfactuals | Physical insight | Data-driven
---|---|---|---|---|---
3 - Mechanistic | ✓ | ✓ | ✓ | ✓ | ✓
2 - Structural causal | ✓ | ✓ | ✗ | ? | ?
1 - Statistical/ML | ✓ | ✗ | ✗ | ✗ | ?

##### Level 1 – Learning statistical associations.

The most rudimentary approach to building association links from multivariate
time series data involves computing pairwise Pearson’s correlations or mutual
information, which capture relationships between variables at lag zero.
Networks derived from these measures have found applications in numerous
scientific and engineering domains, including climate network analysis (Donges
et al., 2009b), financial market network analysis (Fiedor, 2014), and brain
network analysis (Johnson et al., 2007; Takagi, 2020). However, mutual
information-based associations at lag zero cannot be interpreted directionally
since the term “information” implies a lack of directionality. Other regions
or variables may influence the nodes under investigation, or the association
could be due to a common driving process. Lagged association measures are
commonly used to account for directional links and quantify the time lag of
associations.

Lagged correlation analysis has a long history in climate research (Walker,
1923) and neuroscience (Medaglia et al., 2015; Richiardi et al., 2013), with
the delay at the maximum of the cross-correlation function being used to
interpret the delay of the underlying physical mechanism coupling two
processes. Other lagged measures of association, such as mutual information
(Granger, 1969), have been proposed to determine lags in nonlinear processes.
In addition to analysing time lags, the magnitude of the cross-correlation is
often used as a measure of the impact of one process on another or as a
measure of the strength of an association. This aligns with the statistical
interpretation of the square of correlation as the proportion of variance in
one process that can be linearly represented by another (Von Storch and
Zwiers, 2002; Chatfield, 2013).

However, relying solely on association measures, even those that account for
lags and nonlinearity, cannot uncover directionality, detect the delay of the
underlying mechanism, or provide a physically or causally interpretable
estimate (Runge et al., 2014). The widespread use and abuse of association
measures in engineering and science throughout the 20th century have impeded
the exploration and development of meaningful causation measures and hindered
the discovery of new and alternative explanatory laws from data.

##### Level 2 – Learning causal relations from observations.

A fundamental objective in the scientific enterprise is understanding the
causes behind the phenomena we observe (Pearl, 2009a; Peters et al., 2017a).
This is particularly challenging in disciplines dealing with complex dynamical
systems, where experimental interventions are expensive, unethical, or
practically impossible. In some fields (e.g., climate sciences, economics,
cardiology, and neurosciences), the current alternative is to rely on
computationally expensive simulation experiments. Still, those do not
adequately represent all relevant physical processes involved. At the same
time, a rapidly increasing amount of time series data is generated by
observations and also models. How can we use this wealth of data to gain new
insights into our fundamental understanding of these systems?

In recent years, rapid progress has been made in computer science, physics,
statistics, philosophy, and applied fields to infer and quantify potential
causal dependencies from data without intervening in the systems. Although the
truism that correlation does not imply causation holds, the key idea shared by
several approaches follows Reichenbach’s common cause principle (Reichenbach,
1991): if variables are dependent, then they are either causal to each other
(in either direction) or driven by a common driver. To estimate causal
relationships among variables, different methods take different, partially
strong, assumptions. Granger (Granger, 1969) addressed this question
quantitatively using prediction. At the same time, in the last decades,
several complementary concepts emerged, from nonlinear dynamics (Sugihara et
al., 2012) based on attractor reconstruction to computer science exploiting
statistical independence relations in the data (Pearl, 1995, 2009a). More
recently, statistics and machine learning research utilised the framework of
structural causal models (SCMs) (Peters et al., 2017a) for this purpose.
Causal inference from data is becoming a mature scientific approach (Pearl,
2009a).

Causal inference combines domain knowledge, ML models, and data to learn the
underlying system’s causal structure and quantify causal effects (Pearl,
2009b; Pearl et al., 2016; Pearl and Mackenzie, 2018; Spirtes et al., 2000;
Peters et al., 2017a). Causal inference can leverage observational or
(interventional) model output data (Pearl, 2009b) to learn, understand and
evaluate the plausibility of specific causal relations among the considered
variables. Today, many methods and tools are available to address challenges
in complex systems (Wagner, 1999; Sugihara et al., 2012) and many other
fields. Causality is pivotal not only for a better academic understanding of
processes in science but also for more robust forecasts, attributing the
causes of events, and improving the physics embedded in physics models. Many
fields of science and engineering are using causal inference/discovery
methods, from Earth and climate sciences (Runge et al., 2019a; Pérez-Suay and
Camps-Valls, 2019; Ebert-Uphoff and Deng, 2017; Raia, 2008; Reitsma, 2010;
Niemeijer and de Groot, 2008; Shepherd, 2019; Goodwell et al., 2020),
neurosciences (Reid et al., 2019; Siddiqi et al., 2022; Stokes and Purdon,
2017), social sciences (Marini and Singer, 1988; Russo, 2010), health and
epidemiology (Hernán, 2018; Glass et al., 2013; Hernan and Robins, 2020), or
economics (Hicks et al., 1980; LeRoy, 2004).

##### Level 3 – Equation discovery in physical systems.

The scientific enterprise distinctly differs from other intellectual
endeavours by relying on formal theories, laws, and models to explain and
predict observations and using such observations to construct, revise, and
evaluate its formal statements (Langley et al., 1987b; Langley, 2019; Klahr
and Simon, 1999). Many of these activities have been studied by philosophers
of science for over a century. The Logic of Science (Popper, 2005) (or
justification) aims to characterise how observational data, simulations, and
experiments can collectively support or refute laws, models, or theories.

A common claim was that scientific discovery requires some ‘creative spark’,
which cannot be analysed rationally or logically (Simon et al., 1989). Popper,
Hempel, and many other philosophers of science maintained that the discovery
process was inherently irrational and beyond any formal understanding. The key
insight came from Simon (Popper, 2005; Hempel, 2001; Simon et al., 1989), who
proposed that scientific discovery, rather than “depending on some unknown
mystical ability, is a variety of problem-solving that involves searching
through a space of problem states generated by applying mental operators and
guided by heuristics to make the search tractable.” Such observation
established the first heuristic programming methods of hypothesis (model)
search to automate the creative process and law discovery. Discovering numeric
laws from data has been approached by many authors in the past using grammars,
logic rules, propositional bases, entailment, and genetic algorithms, to name
a few (Falkenhainer and Michalski, 1986; Kokar, 1986; Żytkow et al., 1990;
Schaffer, 1990; Nordhausen and Langley, 1990; Langley, 2019; Moulet, 1992;
Gordon et al., 1994; Murata and Tanaka, 1994; Džeroski and Todorovski, 1995;
Washio and Motoda, 1997; Bradley et al., 2001; Koza et al., 2001). Later,
(Schmidt and Lipson, 2009b) proposed an automated algorithm to discover
Hamiltonians, Lagrangians, and other geometric and momentum conservation laws
without prior knowledge of physics, kinematics, or geometry. A new field was
born; learning explicit mathematical laws from observations, which was often
referred to as equation discovery or data-driven system identification
(Simidjievski et al., 2020).

Inspired by earlier work on the DENDRAL system (Feigenbaum et al., 1971),
which inferred structural models of organic molecules from their mass spectra,
the community developed different systems that created models of other
scientific phenomena (e.g., (Langley et al., 1987a)). The field was named
computational scientific discovery, and the challenge of automating it has
been approached by many researchers since then (Evans and Rzhetsky, 2010;
Fortunato et al., 2018; Bongard and Lipson, 2007; Schmidt et al., 2011; Waltz
and Buchanan, 2009; King et al., 2009). Efforts in this paradigm differ from
mainstream work in machine learning by producing scientific formalisms
(Langley et al., 2002a, b, 1987b), ranging from componential models in
particle physics (Kocabas, 1991) to reaction pathways in chemistry and to
regulatory models in genetics (King et al., 2004). Reviews have been edited by
Shrager and Langley (1990); Dzeroski and Todorovski (2007); Simidjievski et
al. (2020).

Recently, the field has been approached by scientists in AI, functional
analysis and mathematical operators, nonlinear control, and system
identification. Modern approaches that we will review in this paper consider:
Automated reverse engineering of nonlinear dynamical systems (Bongard and
Lipson, 2007), sparse-promoting solutions that identify parsimonious models of
nonlinear dynamics; e.g. relevance vector machine, a sparse Bayesian
regression method (Tipping, 2001) or the SINDy method (Brunton et al., 2016b;
Brunton and Kutz, 2022), which has been combined with deep neural networks
(Champion et al., 2019), reduced-order models (Mezić, 2005) and Koopman
operators based on kernel theory and autoencoders (Kaiser et al., 2020, 2021b;
Kostic et al., 2022; Klus et al., 2020; Lusch et al., 2018), differentiable
networks that can learn the true underlying equation and extrapolate to unseen
domains (Sahoo et al., 2018), a constrained symbolic regression methodology,
named AI Feynman, that enforces desirable constraints in equation learning
(compositionality, units, separability, symmetry, smoothness) (Udrescu and
Tegmark, 2020), genetic programming to distil laws of physics (Schmidt and
Lipson, 2009a), or a transformer-based architecture using massive pretraining
can predict formulas from data (Biggio et al., 2021).

A relevant challenge in this context is the discovery of state variables from
experimental/observational data. Almost in all equation and causal discovery
algorithms, the variables are given or assumed, which is impossible when
trying to understand new or highly complex systems. Some approaches exist in
the literature based on the combination of learning compact and expressive
feature representations, manifold learning for the determination of the
intrinsic dimensionality of the system representation coordinates, and SINDy
as a regulariser that enforces dynamic equations in the state space (Brunton
and Kutz, 2022; Chen et al., 2022; Pukrittayakamee et al., 2009; Schütt et
al., 2017). These approaches are somewhat related to the discovery of causal
relations under noise and latent functions, which is also an active field of
research (Stegle et al., 2010; Monti et al., 2020; Diaz et al., 2023).

####  1.3.3 AI for scientific discovery

“With the advent of data-driven methods that learn patterns and relations from
data, the tedious human endeavour of scientific discovery (laws, equations and
causes of phenomena) is being revolutionised… and accelerated in many fields.”

The debate about AI-based theories of scientific discovery has been ongoing
for decades, beginning with whether computers can devise new concepts or
merely process the concepts already included in a given computer language.
However, the discussion has been revived with the development of new
computational tools for data analysis. It is now largely uncontroversial that
machine learning tools can aid discovery, though there is still debate about
whether they generate new knowledge or merely speed up data processing.
Moreover, there is the question of whether data-intensive science
fundamentally differs from traditional research and the ethical implications
of “superhuman AI”. Philosophers have also focused on the opacity of machine
learning, asking whether we can say that humans and machines are “co-
developers” of knowledge. Ultimately, the debate about AI-based theories of
scientific discovery is still ongoing, with researchers considering both the
potential benefits and ethical implications of such tools.

The fields of equation discovery and causal inference that we will review in
this paper promise to shed light on the previous fundamental questions: what
can an algorithm learn and discover, what can AI explain, and what new science
may emerge through a collaborative AI-machine dialogue about science? An
integrative approach seems necessary, where domain experts, data and machine
work together in a data-driven framework that formulates and answer causal
questions and discover new laws (Pearl, 2009a). At a more general level, it
becomes pertinent to ask if machines can start a new scientific revolution and
even if AI itself is the ultimate scientific revolution (Russell, 2021; Boden,
2014; Gillies, 1998).

Causal and Equation Discovery Causal discovery Equation discovery Case studies
Taxonomy Challenges Opportunities Perspectives Taxonomy Learning equations
Representations Perspectives Brain activity Brain connectivity Carbon/water
fluxes Climate models Density functionals Boundary layer Vortex shedding
Turbulence Mesoscale closures Figure 1.5: Roadmap of the article.

###  1.4 Outline

This paper aims to review the most important concepts, methods, and previous
works on causal inference and discovery in the physical sciences. We use
statistical learning techniques to discover causal relations, physical laws,
and governing equations from data. Sec. 2 and Sec. 3 present general
frameworks and taxonomies for causal discovery and learning physical laws from
data, respectively. Both sections categorise the field, reviewing concepts and
methods, their specific characteristics, challenges, and opportunities in the
physical sciences. Sec. 4 provides examples of causal discovery and equation
discovery in a wide range of fields of the physical sciences: dynamical
systems, neuroscience, classical and quantum systems, fluid mechanics,
geosciences and climate sciences. We pay attention to how causality concepts
and methods can improve our knowledge of a given physical system from
observations. Sec. 5 outlines the most promising future lines of research in
this area of study at the intersection of machine learning and nonlinear
physical processes.

##  Chapter 2 Causal discovery in the physical sciences

Causal discovery, see for example (Spirtes et al., 2000; Peters et al., 2017a)
for extended expositions of the topic, has become increasingly popular in the
last years as a tool to discover the underlying causal structure of physical
systems (Runge et al., 2019a). There is an abundance and ever-growing number
of methods designed to work under different assumptions and tackle other use
cases. This section reviews several methods for causal discovery, focusing on
methods for time series and their potential use in physical sciences. To this
end, in Sec. 2.1, we first provide a taxonomy for many available causal
discovery methods. Sec. 2.2 discusses causal discovery’s challenges in real-
world applications. We conclude in Sec. 2.3 by discussing opportunities for
applications of causal discovery in the physical sciences. We would also like
to point to other reviews focusing on causal discovery of time series (Runge
et al., 2019a; Assaad et al., 2022b; Moraffah et al., 2021). In addition,
Runge et al. (2023) provides a shorter accessible summary of methods for
causal discovery and causal effect estimation with practical case studies to
illustrate typical challenges, such as contemporaneous causation, hidden
confounding and non-stationarity.

###  2.1 A taxonomy of causal discovery methods

Table 2.1: Taxonomy of methods for causal discovery. The entries in parentheses $(\cdot)$ indicate that there are versions of the algorithm in which the assumption is relaxed. We use the abbreviations ‘TSG’ for time series graph, ‘summary’ for summary graph and ‘ext. sum. graph’ for an extended summary graph.  Method | Target of Inference | Approach | Process Assumptions |  Data Assumption
---|---|---|---|---
|  Bi-/ Multi- variate |  Graph type |  Indep./ Asymm./ Score |  non- /linear |  Stoch. / Det. |  Con- temp. |  Cycles |  Hidden var.
GC (Granger, 1969) |  Bi. |  summary |  indep. |  linear |  stoch. |  ✗ |  lagged-only |  ✗
Mult-GC (Geweke, 1982) |  Multi. |  summary |  indep. |  linear |  stoch. |  ✗ |  lagged-only |  ✗
Mult-nonlin-GC (Diego Bueso, 2020) |  Multi. |  summary |  indep. |  nonlin. |  stoch. |  ✗ |  lagged-only |  ✗
TE (Schreiber, 2000) |  Bi. |  summary |  indep. |  nonlin. |  stoch. |  ✗ |  lagged-only |  ✗
Multi-TE (Barnett et al., 2009) |  Multi. |  summary |  indep. |  nonlin. |  stoch. |  ✗ |  lagged-only |  ✗
CCM (Sugihara et al., 2012) |  Bi. |  summary |  indep.(?) |  nonlin. |  det. |  ✓ |  ? |  partially
Ext.-CCM (Diaz et al., 2022) |  Bi. |  summary |  indep.(?) |  nonlin. |  det. |  ✓ |  ? |  partially
tsPC (Runge, 2020) |  Multi. |  TSG |  indep. |  both |  stoch. |  ✓ |  (✓) |  ✗
PCMCI (Runge et al., 2015b) |  Multi. |  TSG |  indep. |  both |  stoch. |  ✗ |  lagged-only |  ✗
PCMCI+ (Runge, 2020) |  Multi. |  TSG |  indep. |  both |  stoch. |  ✓ |  (✓) |  ✗
PCGCE (Assaad et al., 2022a) |  Multi. |  ext. sum. graph |  indep. |  both |  stoch. |  ✓ |  (✓) |  ✗
FCIGCE (Assaad et al., 2022a) |  Multi. |  ext. sum. graph |  indep. |  both |  stoch. |  ✓ |  (✓) |  ✓
tsFCI |  Multi. |  TSG |  indep. |  both |  stoch. |  (✓) |  (✓) |  ✓
SVAR-FCI (Assaad et al., 2022a) |  Multi. |  TSG |  indep. |  both |  stoch. |  ✓ |  (✓) |  ✓
SVAR-GFCI (Malinsky and Spirtes, 2018) |  Multi. |  TSG |  score & indep. |  both |  stoch. |  ✓ |  (✓) |  ✓
LPCMCI (Gerhardus and Runge, 2020) |  Multi. |  TSG |  indep. |  both |  stoch. |  ✓ |  (✓) |  ✓
(F)GES (Meek, 1997; Chickering, 2002b, a; Ramsey et al., 2017) |  Multi. |  summary |  score |  linear |  stoch. |  ✓ |  lagged-only |  ✗
DYNOTEARS (Pamfil et al., 2020) |  Multi |  TSG |  score |  linear |  stoch. |  ✓ |  lagged-only |  ✗
IDYNO (Gao et al., 2022) |  Multi |  TSG |  score |  linear and non-linear |  stoch. |  ✓ |  lagged-only |  ✗
NTS-NOTEARS (Sun et al., 2023) |  Multi |  TSG |  score |  linear and non-linear |  stoch. |  ✓ |  lagged-only |  ✗
TiMiNo (Peters et al., 2013) |  Multi. |  TSG |  indep. |  both |  stoch. |  ✓ |  lagged-only |  ✗
RHINO (Gong et al., 2023) |  Multi. |  TSG |  indep. |  both |  stoch. |  ✓ |  lagged-only |  ✗
VARLiNGAM (Shimizu et al., 2006) |  Multi. |  TSG |  asymm. |  linear |  stoch. |  ✓ |  lagged-only |  ✗

In this section, we structure the zoo of existing causal discovery methods to
guide method users in finding a method suitable for their application and
guide method developers in identifying open challenges. To this end, we
summarise the central formal aspects of the graphical-model-based causal
inference framework in Sec. 2.1.1. Then, in Sec. 2.1.2, we discuss several
characteristics (hereafter referred to as “axes”) by which methods can be
conceptually distinguished. Lastly, in Sec. 2.1.3, we present an extensive
(but not exhaustive) list of causal discovery methods and characterise these
methods according to previously introduced axes.

####  2.1.1 Preliminaries

At the heart of the graphical-model-based causal inference framework are
_structural causal models (SCMs)_ , e.g. (Bollen, 1989; Pearl, 2009c; Peters
et al., 2017a). An SCM serves as a causal model for the data-generating
process and specifies how the system reacts to _interventions_ , that is, to
idealised experimental manipulations that deliberately hold fixed a subset of
the system’s variables while not perturbing the system in any other way.

An SCM for a system described by the set of variables
$\mathbf{V}=\\{V^{1},\,\ldots,\,V^{n}\\}$ consists of $n$ so-called
_structural assignments_

$V^{i}:=f^{i}(pa^{i},\epsilon^{i})\quad\text{with $1\leq i\leq n$}\,,$ (2.1)

together with a product distribution
$p_{\epsilon}(\epsilon^{1},\,\ldots,\epsilon^{n})=p_{\epsilon}^{1}(\epsilon_{1})\cdot\ldots\cdot
p_{\epsilon}^{n}(\epsilon_{n})$ of the random variables $\epsilon^{i}$.
Formally, the $f^{i}$ are measurable functions that depend non-trivially on
all of their input arguments, and the
$pa^{i}\subseteq\mathbf{V}\setminus\\{V^{i}\\}$ are subsets of the system
variables $V^{1},\,\ldots,\,V^{n}$. The functions $f^{i}$ are interpreted as
the causal mechanisms by which the values of the respective variable $V^{i}$
are determined from the value of $\epsilon^{i}$ and the values of the
variables in $pa^{i}$. Consequently, the variables in $pa^{i}$ are referred to
as the _causal parents_ of $V^{i}$. The random variables $\epsilon^{i}$ are
interpreted as noise that summarises all factors that are not modelled
explicitly, and the factorisation of
$p_{\epsilon}(\epsilon^{1},\,\ldots,\epsilon^{n})$ amounts to the assumption
that the $\epsilon^{1},\,\ldots,\epsilon^{n}$ are jointly independent. This
joint independence is motivated by the view that any dependence between the
noise variables must be due to a causal relationship between them and that
such a dependence should then rather be modelled explicitly by enlarging the
set $\mathbf{V}$ of system variables.

The _causal graph_ of an SCM with system variables $V^{1},\,\ldots,\,V^{n}$ is
the directed graph whose vertices are the variables $V^{i}$ and with a
directed edge $V^{i}\rightarrow V^{j}$ if and only if $V^{i}$ is a causal
parent of $V^{j}$, that is, if and only if $V^{i}\in pa^{i}$. Consequently,
the causal graph of an SCM shows the _qualitative_ cause-and-effect
relationships as specified by the sets $pa^{i}$. If the causal graph is
acyclic, that is, if the causal graph is a directed acyclic graph (DAG), then
the SCM is said to be _acyclic_.

An SCM obtains causal meaning by asserting how the modelled system reacts to
interventions. Formally, an intervention on the variable $V^{k}\in\mathbf{V}$
is a mapping, conventionally denoted as $do(V^{k}:=v^{k})$, that maps the
original SCM and a number $v_{k}$ to a new SCM in which the original
structural assignment for $V^{k}$ is replaced by the new structural assignment
$V^{k}:=v^{k}$ and the noise variables $\epsilon^{k}$ is removed. This new SCM
is referred to as an _intervened SCM_ , and $do(V^{k}:=v^{k})$ is interpreted
as an idealised experimental manipulation by which the value of $V^{k}$ is
held fixed at $v_{k}$ while leaving the system unaltered else. This
specification of how the system reacts to interventions is why using the
symbol “$:=$” instead of “$=$” in (2.1) is conventional. On the level of
causal graphs, $do(V^{k}:=v^{k})$ amounts to removing all edges that point
into $V^{k}$ because, in the intervened SCM, the variable $V^{k}$ has no
causal parents. Interventions on subsets of variables are defined similarly.

In an acyclic SCM, the combination of noise distribution $p_{\epsilon}$ and
functions $f^{i}$ uniquely determines a distribution of the system variables
$V^{1},\,\ldots,\,V^{n}$. This distribution is often referred to as the
_entailed distribution of the SCM_. The entailed distribution $p(\cdot)$ of
the original SCM (that is, of the SCM that models that system without
interventions) is often referred to as the _observational distribution_. The
entailed distributions of the intervened SCMs are often referred to as
_interventional distributions_ and are conventionally often denoted as
$p(\cdot|\leavevmode\nobreak\ do(V^{k}:=v^{k}))$; and similarly for
interventions on subsets of system variables.

When using this notation, it is important to keep in mind that
$p(\cdot|\leavevmode\nobreak\ do(V^{k}:=v^{k}))$ is, in general, not equal to
$p(\cdot|\leavevmode\nobreak\ V^{k}=v_{k})$. Indeed,
$p(\cdot|\leavevmode\nobreak\ do(V^{k}:=v^{k}))$ is the distribution of the
_intervened_ SCM, whereas $p(\cdot|\leavevmode\nobreak\ V^{k}=v_{k})$
corresponds to _observing_ $V^{k}=v^{k}$; put differently: Correlation is not
equal to causation.

The article (Bongers et al., 2021) discusses in much detail the more
complicated case of cyclic SCMs. As shown there, cyclic SCMs need not entail a
unique distribution for the system variables. However, (Bongers et al., 2021)
defines a restricted class of cyclic SCMs, termed _simple SCMs_ , that entail
a unique distribution and that are closed under interventions. Moreover,
acyclic SCMs are a special case of simple SCMs.

In the time series case, which we are predominantly interested in this paper,
(2.1) can be generalised by putting a time index $t$ on $V^{i}$, $f^{i}$,
$pa^{i}$ and $\epsilon^{i}$. The commonly used term _causal stationary_ then
refers to time-invariance of the qualitative cause-and-effect relationships,
that is, to the situation that $pa^{i}_{t+\Delta t}=\\{V^{j}_{s+\Delta
t}\leavevmode\nobreak\ |\leavevmode\nobreak\ V^{j}_{s}\in pa^{i}_{t}\\}$ for
all $t$ and $\Delta t$.

####  2.1.2 Axes for categorising causal discovery methods

This section introduces and explains several axes for categorising and
distinguishing causal discovery methods. While it would be possible to
consider more axes yet, the authors believe that the choice of axes presented
here is a reasonable compromise between a sufficiently fine-grained
categorisation on the one hand and clarity of exposition on the other hand.
Table 2.1 lists many causal discovery methods and categorises them according
to the aforementioned axes. In Figure 2.1, we graphically illustrate some
axes.

Figure 2.1: Illustration of some axes along which causal discovery methods are
categorised in this review; see references in the main text to the respective
subparts of the figure.

##### Bivariate vs multivariate causal discovery.

This axis concerns the number of variables that are being considered.
Bivariate causal discovery aims to discover the causal relationship between
exactly two variables $X$ and $Y$ (in the non-temporal case) or between
exactly two component time series $X^{i}$ and $X^{j}$ (in the time series
case). Multivariate causal discovery aims to discover the causal relationships
between any number of variables or component time series, respectively.
Bivariate causal discovery often (but not necessarily) assumes _causal
sufficiency_ (see axis on causal sufficiency below). In the time series case,
bivariate causal discovery often (but not necessarily) targets to infer the
_summary graph_ rather than the _time series graph_ or _extended summary
graph_ (see axis on time series graph discovery below). If time lags are at
least partially resolved in the bivariate time series case, that is, if the
target of inference is the time series graph or the extended summary graph,
then one effectively deals with a multivariate causal discovery problem.

##### Time series graph discovery vs summary graph discovery vs extended
summary graph discovery.

This axis is specific to the temporal setting and concerns the target of
inference. Some methods are designed to learn the _time series graph_ (Runge
et al., 2012), also known as _full-time graph_ (Peters et al., 2013) and _time
series chain graph_ (Dahlhaus and Eichler, 2003), that is, the collection of
all causal links $X^{i}_{t-\tau}\rightarrow X^{j}_{t}$ including the
respective lags $\tau$ of these links. Part $a)i)$ of Figure 2.1 shows an
example of a time series graph with four component time series. As indicated
by the grey edges, the pattern of edges in this graph is implicitly assumed to
repeat both to the left (past) and right (future). Due to this repetitive
structure of the edges, a time series graph is uniquely specified by the
collection of edges that point into a vertex at an arbitrary reference time
step $t$. Other methods disregard the information about the time lags and
instead learn the _summary graph_ (Peters et al., 2017a). In the summary
graph, there is exactly one vertex per component time series $X^{i}$ and an
edge $X^{i}\rightarrow X^{j}$ if and only if there is an edge in the time
series graph $X^{i}_{t-\tau}\rightarrow X^{j}_{t}$ at any lag $\tau$. Part
$a)iii)$ of Figure 2.1 shows the summary graph associated with the time series
graph in part $a)i)$ of the same figure. Another option is to learn _extended
summary graphs_ (Assaad et al., 2022a). These graphs go midway between
learning time series and summary graphs by distinguishing between
contemporaneous and lagged links but disregarding the information about the
specific time lags of lagged links. Specifically, the extended summary graph
contains exactly two vertices per component time series $X^{i}$, namely the
vertex $X^{i}_{t}$ for the present time steps and the vertex $X^{i,-}$ for all
past time steps. There is an edge $X^{i}_{t}\rightarrow X^{j}_{t}$ if and only
if, this same edge is also in the time series graph, there is an edge
$X^{i,-}\rightarrow X^{j}_{t}$ if only if there is at least one $\tau\geq 1$
such that $X^{i}_{t-\tau}\rightarrow X^{j}_{t}$ is in the time series graph,
and there is no edge between $X^{i,-}$ and $X^{j,-}$. By this construction,
extended summary graphs do distinguish between $X^{i}_{t-\tau}\rightarrow
X^{j}_{t}$ with $\tau>0$ and $X^{i}_{t}\rightarrow X^{j}_{t}$ but do not
distinguish between, for example, $X^{i}_{t-2}\rightarrow X^{j}_{t}$ and
$X^{i}_{t-1}\rightarrow X^{j}_{t}$. Part $a)ii)$ of Figure 2.1 shows the
extended summary graph associated with the time series graph in part $a)i)$ of
the same figure. Resolving the lag structure does yield more information but
also implies a more complex target of inference. Learning more complex graphs
(e.g., a time series graph vs a summary graph) is conceptually and
statistically more challenging.

Methods for time series causal discovery typically require the user to specify
a maximal lag $\tau_{max}$ up to which the method is supposed to be sensitive.
If the target of inference is the time series graph, then this choice is
apparent as the learned graph has exactly $\tau_{max}+1$ steps. For example,
if the user specifies the maximal lag to be $\tau_{max}=3$, then the learned
graph has exactly $4=3+1$ time steps, and the method cannot find causal links
of lag $\tau\geq 4$ even if such links are present. If time series graph
discovery is combined with the assumption of causal sufficiency, then this
combination implicitly implies no causal links with a lag larger than
$\tau_{max}$. If causal sufficiency is not assumed, then this additional
implicit assumption is not made. Also, methods for summary and extended
summary graph discovery typically require the specification of a maximal lag
up to which the method is sensitive. As opposed to that, when learning summary
graphs or extended summary graphs the choice of $\tau_{max}$ is not apparent
from the learned graph. However, this choice is not apparent from the learned
graph in the summary graph and extended summary graph cases.

For the case of causal models for time series, the causal arrow between any
two variables can be at any time lag ranging from zero, i.e. a contemporaneous
link, to infinity. A causal discovery algorithm can thus aim to either infer
the full graph with edges being classified by time lags or to infer the
summary graph where the time lag of the causal effect is irrelevant.

##### Methods based on independence, asymmetry, scores and context.

“The wide variety of causal discovery methods can be structured into
independence-based, asymmetry-based, score-based, and context-based
approaches.”

This axis distinguishes causal discovery methods by the type of
information/signal that they use to learn the causal graphs from data. In this
review, as is common in the literature (for example, see (Glymour et al.,
2019)), we distinguish the independence-based, asymmetry-based, and score-
based approaches. Further, we consider the context-based approach to
distinguish those methods that employ the invariance of causal mechanisms
across different environments. An exact delineation between these four
approaches is not always possible as there are _hybrid_ methods that combine
more than one approach.

First, _independence-based causal discovery_ , sometimes called _constraint-
based causal discovery_ , utilises marginal and conditional independencies
between variables to learn the causal graph or a set of causal graphs
consistent with those independencies. Recall that an SCM is defined by a
collection of structural assignments for each variable, where each assignment
is a function of the variable’s parents and a noise term. The collection of
noise variables is assumed to be jointly independent. Independence-based
causal discovery relies on the fact that, for data generated by an SCM, the
structure of the SCM’s causal graph imprints some independencies onto the data
(Verma and Pearl, 1990a; Geiger et al., 1990; Pearl, 2009c). This property is
known as _causal Markov condition_ (Spirtes et al., 2000). Alternatively, if
one does not assume that an SCM generates the data, then the causal Markov
condition is not automatically implied but needs to be assumed separately,
leading to the so-called _causal Markov assumption_. The $d$-separation
criterion (Pearl, 1988) allows to graphically determine all independencies
that are necessarily implied in a given causal graph (Verma and Pearl, 1990b;
Geiger et al., 1990; Pearl, 2009c). The basic idea then is to run statistical
tests of marginal and conditional independencies on the data and, second, use
the results of these tests to constrain the causal graph’s structure.

For the second of these two steps to hold, one further needs to make the
_causal faithfulness assumption_ (Spirtes et al., 2000). This assumption says
there are no independencies beyond those necessarily implied by the causal
Markov condition in the observed data. For example, causal faithfulness
excludes that a variable $X$ causally influences another variable $Y$ along
multiple pathways which in total cancel out exactly—because otherwise there
would be statistical independence, namely the marginal independence of $X$ and
$Y$, that would not be implied by the causal Markov condition.

For linear models and infinite samples, causal faithfulness is guaranteed
except for Lebesgue measure zero sets in parameter space (Spirtes et al.,
2000). However, (Robins et al., 2003) shows that causal faithfulness ensures
point-wise consistency but not uniform consistency of, for example, the famous
PC algorithm (Spirtes et al., 2000) (see below for the details on the PC
algorithm). Uniform consistency of the PC algorithm is proven under the
stronger _strong-faithfulness assumption_ (Zhang and Spirtes, 2002; Kalisch
and Bühlman, 2007). However, (Uhler et al., 2013) shows that the set of not
strongly-faithful distributions has a non-zero Lebesgue measure for various
graph structures. This analysis indicates that causal faithfulness should be
regarded as a strong assumption. There are also weaker types of faithfulness
assumptions, for example, the _adjacency faithfulness_ and _orientation
faithfulness_ assumptions (Ramsey et al., 2006; Zhang and Spirtes, 2008).

Independence-based causal discovery is non-parametric in that no assumption on
the SCM’s functional relationships and/or noise distributions needs to be
made. However, choosing a particular method for (conditional) independence
testing may implicitly impose a parametric assumption. For example, testing
for (conditional) independence by (partial) correlation implicitly makes the
assumption that the data-generating process is linear Gaussian. Conversely, if
a parametric assumption can be made, this assumption might favour specific
methods for (conditional) independence testing. For example, suppose one can
assume linear Gaussian data. In that case, it is reasonable to use a (partial)
correlation instead of more general (conditional) independence tests like, for
example, a test based on (conditional) mutual information as given in (Runge,
2018).

Many independence-based causal discovery are proven to be _sound and complete_
, meaning they provably learn the respective target of inference if they are
given ground-truth knowledge of (conditional) independencies. However, the
statistical tests of (conditional) independence are expected to make errors in
finite samples even if all assumptions are met. For the famous PC algorithm
(Spirtes et al., 2000) (see below for more details), there are also
probabilistic finite-sample guarantees (Zhang and Spirtes, 2002; Kalisch and
Bühlman, 2007).

Typically, there are multiple graphs that by means of the causal Markov
condition, imply the exact same set of (conditional) independencies. For
example, the three graphs $X\rightarrow Y\rightarrow Z$ and $X\leftarrow
Y\leftarrow Z$ and $X\leftarrow Y\rightarrow Z$ by means of the causal Markov
condition all imply exactly the same independence, namely that $X$ and $Z$ are
conditionally independent given $Y$ (and no further independencies). Such
graphs are said to be _Markov equivalent_ to each other and constitute a
_Markov equivalence class_. Consequently, independence-based causal discovery
algorithms cannot distinguish between Markov equivalent graphs. Instead, these
algorithms target learning a graphical representation of the entire Markov
equivalence class to which the true causal graph belongs. Since the graphs
$X\rightarrow Y$ and $X\leftarrow Y$ are Markov equivalent, independence-based
causal discovery can not infer the causal direction in the fundamental non-
temporal bivariate case (see axis I). Independence-based causal discovery
becomes meaningful for at least three variables; however, in the time series
case, even two variables suffice to make non-trivial causal inferences
(because then, if the variables are resolved in time, there are effectively
more than just two variables).

Second, _asymmetry-based causal discovery_ makes and relies on parametric
assumptions on the form of the functional relationships and/or noise
distributions of the data-generating SCM (Peters et al., 2017a).

This approach is motivated by the elementary bivariate case, that is, by
finding the causal relationship between two variables $X$ and $Y$. As
explained above, with independence-based causal discovery, it is not possible
to distinguish the Markov equivalent graphs $X\rightarrow Y$ and $X\leftarrow
Y$. This impossibility is not a shortcoming of independence-based causal
discovery but rather is fundamental unless stronger assumptions are made
(Peters, 2012; Peters et al., 2017a). The proof of the impossibility of
distinguishing between $X\rightarrow Y$ and $X\leftarrow Y$ works by showing
that if the true data-generating SCM goes in the direction $X\rightarrow Y$,
then one can always construct an alternative SCM in the direction $X\leftarrow
Y$ that gives rise to the same data distribution as the true SCM.

The basic idea for removing this fundamental ambiguity is as follows: For
certain choices of _restricted_ SCMs, defined by certain restricted parametric
assumptions, it is impossible to have a restricted SCM in the first direction
$X\rightarrow Y$ and simultaneously a restricted SCM in the second direction
$X\leftarrow Y$. Hence, given the assumption that the true SCM lies in the
restricted class of models, it becomes possible to distinguish the causal and
anti-causal direction. A restricted class of SCMs with this property is said
to be _identifiable_. This approach to causal discovery relies on the
expectation that the SCM in the causal direction generically has lower
complexity than any alternative SCM in the anti-causal direction. As explained
in Section 4.1.2 of (Peters et al., 2017a), this expectation can be motivated
by the principle of _independence of cause and mechanism_ (Daniušis et al.,
2010; Peters, 2012). There are also asymmetry-based causal discovery methods
for learning the causal graph between two or more variables for multivariate
causal discovery (Peters et al., 2017a).

Third, _score-based causal discovery_ chooses one or multiple best-scoring
graphs with respect to a predefined scoring function. This scoring function is
typically built on the likelihood of the observed data given a particular
graph and an assumed parametric statistical model (Peters et al., 2017a). This
approach requires searching over the space of causal graphs. Even if causal
sufficiency (see axis on causal sufficiency) and acyclicity (see axis on
cycles below) are assumed, in which case the causal graph is a _directed
causal graph (DAG)_ , the search space of graphs already grows super-
exponentially, e.g. (Chickering, 2002b). An exact search is thus infeasible
even for a moderate number of variables. Instead, greedy search techniques are
often used, e.g. in the famous GES algorithm (Chickering, 2002b, a) (see below
for details on this algorithm). If the assumed statistical model does not
yield identifiability beyond the Markov equivalence class, then the scoring
function must be chosen such that Markov equivalent graphs have the same
score. Hence, one can search over the space of Markov equivalence classes
rather than over the space of graphs.

Fourth, _context-based causal discovery_ requires access to data of the same
system in different contexts. The term _different context_ is understood
rather broadly: Its meaning ranges from, for example, observing the same
physical system at other locations to, for example, observing a system both
before and after an intervention. The basic assumption and idea of this
approach to causal discovery are that the causal mechanisms, that is, the
functional mappings from causes to effects and hence also the conditional
distributions of the effects given their causes, remain unchanged across all
contexts (unless the effect variable is the target of an intervention in one
of the contexts). In contrast, marginal distributions and hence also the
conditional distributions of causes given their effects can change (Peters et
al., 2017a). A prime example of a context-based causal discovery method is
Invariant Causal Prediction (Peters et al., 2016) (see below for more
details). The _joint causal inference (JCI)_ framework (Mooij et al., 2020)
proposes to model all contexts with one graph by including one or multiple so-
called _context variables_ whose values determine the context and subsequently
pooling the data from the different contexts into one joint dataset. This
enlargement of the system by context variables effectively reduces the case of
multiple contexts to the standard case of a single context. Consequently, it
is possible to apply standard causal discovery algorithms to the pooled data
(if the respective assumptions are met). One might thus argue that context-
based causal discovery should not be considered a distinct approach to causal
discovery but should instead be characterised by the requirement of data from
multiple contexts.

##### Linear or nonlinear dependencies.

This axis concerns the form of the functional relationships in the data-
generating structural causal model. Broadly, see part $b)$ of Figure 2.1, one
can distinguish between linear and nonlinear functional relationships. In
independence-based and score-based causal discovery, an assumption of
linearity can enter implicitly by using partial correlation for testing
conditional independence (independence-based approach) or by choice of the
statistical model (score-based approach). In asymmetry-based causal discovery,
an assumption of linearity is, if made, typically explicit by choice of the
functional model. Various asymmetry-based causal discovery methods do not
assume linearity but still use restricted functional model classes that do not
allow for entirely generic dependencies, for example, the functional model
class of nonlinear additive noise models (Hoyer et al., 2008). However, for
simplicity, we here only distinguish the methods by whether or not they assume
linearity.

##### Deterministic vs stochastic systems.

This axis concerns an assumption on the type of data-generating process. Some
methods assume the data are generated by a deterministic process, for example,
a deterministic dynamical system. In contrast, other methods make explicit use
of the assumption that the data-generating process is inherently stochastic,
see part $c)$ of Figure 2.1. In the case of stochastic data-generating
processes, the stochasticity is interpreted as dynamical noise that arises due
to factors outside of the model. Dynamical noise needs to be distinguished
from measurement noise: The former is an inherent property of the data-
generating process, and the latter arises from uncertainty in the data-
collection process. The causal inference and discovery frameworks have also
been extended to dynamical systems, both deterministic and stochastic, without
stable equilibrium distribution (Mooij et al., 2013b; Bongers and Mooij, 2018;
Rubenstein et al., 2018).

##### Contemporaneous links.

This axis is specific to the temporal setting and concerns a connectivity
assumption on the causal time series graph. Some methods make the assumption
that all causal links in the time series graph are _lagged_ , meaning that all
causal links are of the form $X^{i}_{t-\tau}\rightarrow X^{j}_{t}$ with
$\tau>0$, whereas _contemporaneous_ links, that is, links of the form
$X^{i}_{t}\rightarrow X^{j}_{t}$ are assumed to be absent. Other methods do
not make this assumption. For example, in the time series graph in part $a)i)$
of Figure 2.1, there are the contemporaneous edges $Z_{t}\rightarrow W_{t}$
and $Y_{t}\rightarrow X_{t}$. Consequently, methods that assume the absence of
contemporaneous links would, by assumption, disallow this particular time
series graph. Contemporaneous causal links correspond to causal influences
that act on a time scale shorter than the measurement interval; for example, a
causal influence on a time scale of six hours in daily measured data.

##### Causal cycles.

This axis concerns a connectivity assumption on the causal graph. Many methods
assume the absence of cyclic causal relationships. This assumption means that
a variable $X^{j}_{t}$ cannot be a causal ancestor of another variable
$X^{i}_{t-\tau}$ if that second variable $X^{i}_{t-\tau}$ is a causal ancestor
of the first variable $X^{j}_{t}$. For example, the lower graph in part $d)$
of Figure 2.1 has the causal cycle $X_{t}\rightarrow Y_{t}\rightarrow X_{t}$.
Because causation cannot go backwards in time, the assumption of acyclicity
only restricts the contemporaneous section of the causal time series graph.
The assumption is thus only relevant for $\tau=0$. In particular, even with
the assumption of acyclicity, it is possible to model temporal feedbacks. For
example, although the upper graph in part $d)$ of Figure 2.1 is acyclic, it
displays a causal influence of time series $X$ on $Y$ (by the edge
$X_{t}\rightarrow Y_{t}$) and a causal influence of time series $Y$ on $X$ (by
the edge $Y_{t-1}\rightarrow X_{t}$). For example, if the component time
series $X^{i}$ causally influences another component time series $X^{j}$ at,
say, lag $\tau=1$ (i.e., in the time series graph, there is the link
$X^{i}_{t-1}\rightarrow X^{j}_{t}$ or an indirect directed path from
$X^{i}_{t-1}$ to $X^{j}_{t}$), then one can still allow a causal influence of
$X^{j}$ on $X^{i}$ (e.g., $X^{j}_{t-2}\rightarrow X^{i}_{t}$ or
$X^{j}_{t}\rightarrow X^{i}_{t}$ or indirect directed paths from $X^{j}_{t-2}$
or $X^{j}_{t}$ to $X^{i}_{t}$). It is not allowed, however, that $X^{i}$ and
$X^{j}$ causally influence each other both at lag $\tau=0$. For example, if
both $X^{i}_{t}\rightarrow X^{j}_{t}$ and $X^{j}_{t}\rightarrow
X^{k}_{t}\rightarrow X^{i}_{t}$ are present, then the time series graph is
cyclic. There are also causal discovery methods that allow cyclic causal
relationships, e.g. (Forré and Mooij, 2018; Strobl, 2019; M. Mooij and
Claassen, 2020; Bongers et al., 2021). These methods typically infer less
informative graphs than those inferred by methods that do not allow causal
cycles. The early work (Richardson, 1996) considers the special case of causal
discovery in _linear_ cyclic systems.

##### Causal sufficiency.

This axis concerns an assumption that can be viewed as an assumption on the
data-generating process or the data-collection process. The assumption of
_causal sufficiency_ (Spirtes et al., 2000) says that there are no _latent
confounders_ , also called _unobserved confounders_ or _hidden common causes_.
A latent confounder is an unobserved variable that (potentially indirectly
through other unobserved variables) causally influences two observed variables
$X^{i}_{t-\tau}$ and $X^{j}_{t}$. For example, in the lower graph in part $e)$
of Figure 2.1 the unobserved variable $Z$ acts as a latent confounder of the
variables $X$ and $Y$. Consequently, this graph violates causal sufficiency
whereas the upper graph in part $e)$ of Figure 2.1 satisfies causal
sufficiency. Methods that do not assume causal sufficiency typically infer
graphs that are less informative than the graphs inferred by methods that do
assume causal sufficiency. For example, consider the elementary non-temporal
bivariate case with two variables $X$ and $Y$. If these variables are
dependent and causal sufficiency is assumed, then either $X$ causes $Y$
($X\rightarrow Y$), or $Y$ causes $X$ ($X\leftarrow Y$). If causal sufficiency
is not assumed, then there is the third possibility that neither $X$ causes
$Y$ nor vice versa but that there rather is an unobserved variable $L$ which
causes both $X$ and $Y$ ($X\leftarrow L\rightarrow Y$ or, for example,
$X\leftarrow L^{\prime}\leftarrow L\rightarrow L^{\prime\prime}\rightarrow Y$
with other unobserved variables $L^{\prime}$ and $L^{\prime\prime}$).

####  2.1.3 Description and categorisation of causal discovery methods

Here, we list and briefly explain several existing causal discovery methods
for time series data. We summarise this list and the placement of each method
with respect to the axes presented above in Table 2.1. In Figure 2.2, we
illustrate and compare an example time series graph and the respective
graphical objects obtained by some of the discussed causal discovery
algorithms when applied to data generated from an SCM with that time series
graph.

Figure 2.2: Figure illustrating a time series graph (TSG) and the respective
graphs discovered by applying various causal discovery methods to data
generated from an SCM with that time series graph. (a) Time series graph. (b)
The discovered undirected graph by considering (lagged) correlations, where
spurious correlations are highlighted as dashed grey lines. (c) The directed
graph discovered by multivariate Granger causality does not consider
contemporaneous links and retains a spurious link from $Y$ to $W$. (d) Graph
discovered by CCM. (e) The graph discovered by applying the plain PC and
(F)GES algorithms fail to show lagged links and, in addition, fail to orient a
link that the time series adapted algorithms can orient. (f) The time series
version of PC (tsPC), PCMCI+, and the time series version of GES (tsGES)
discover both lagged and contemporaneous links and orient edges up to the
Markov equivalence class. (g) Plain FCI has the same drawbacks as plain PC or
(F)GES. (h) FCI-based time series causal discovery algorithms account for
latent confounders and thus discover causal arrows up to latent confounding.
In particular, the algorithm cannot exclude that the association between
$Y_{t-1}$ and $Z_{t}$ is due to latent confounding rather than a causal
relationship. (i) The PCGCE algorithm discovers the extended summary graph up
to its Markov equivalence class. (j) Var-LiNGAM discovers all causal
relationships correctly if the assumptions of linear relationships and
additive non-Gaussian noise are satisfied.

##### Granger Causality.

Granger Causality (GC) (Granger, 1969, 1980) is originally a statistical test
to decide whether a time series $X_{t}$ is a _cause_ of another time series
$Y_{t}$, in the sense that past values of $X_{t}$ have significant predictive
power in forecasting $Y_{t}$. GC is thus, in principle, a simple test of
temporal (or lagged) relationship and predictability. Nevertheless, under
causal sufficiency and no contemporaneous effects assumptions, it can be
formally shown that GC testing detects actual causal links (see e.g. Peters et
al. (2017a) for a formal derivation of these results in the SEM setting).

In a multivariate setting, which is seldom the case, testing if $X_{t}$ causes
$Y_{t}$ requires controlling for all possible confounders. Therefore the
conditional GC (Granger, 1980; Geweke, 1982; Chen et al., 2004; Barrett et
al., 2010), includes in the restricted and full models the past of all other
_relevant_ time series in the system that are not $X_{t}$ and $Y_{t}$.
Classically, GC considers linear models for which standard $t$-tests or
$F$-tests can be employed, but non-linear extensions have been considered both
in econometrics (Bell et al., 1996; Hiemstra and Jones, 1994; Abhyankar, 1998;
Warne, 2000; Diks and Panchenko, 2006) and in physical and biological
applications (Ancona et al., 2004; Marinazzo et al., 2008b; Diego Bueso,
2020).

##### Linear and nonlinear Granger causality in dynamic systems.

A unified view of (nonlinear) GC with kernel methods for the physical sciences
was introduced in (Diego Bueso, 2020). Two examples are given here: 1.
Bivariate system with coupled non-linear and autoregressive relations given by
$x_{t+1}=3.4x_{t}(1-x_{t}^{2})$ $\exp(-x_{t}^{2})+\varepsilon_{t}^{x}$ and
$y_{t+1}=3.4y_{t}(1-y_{t}^{2})$
$\exp(-y_{t}^{2})+{0.5x_{t}y_{t}}{2}+\varepsilon_{t}^{y}$, where $\varepsilon$
is white Gaussian noise with zero mean and variance $0.4$. The causal
direction is $X\to Y$. The histogram of the estimated causal index $\delta$ on
the left figure reveals GC’s insensitivity to the causal direction, the high
false positive rate of KGC (Marinazzo et al., 2008a), and a higher detection
power by the XKGC (Diego Bueso, 2020). 2. Two logistic maps system defined as
$x_{t+1}=1-1.8x_{t}^{2}$ and
$y_{t+1}=(1-\alpha)(1-1.8y_{t}^{2})+\alpha(1-1.8x_{t}^{2})$, where
$\alpha\in[0,1]$ controls the coupling strength. The causal relationship
implemented is $X\to Y$, and the challenge is to assess the detection power of
methods without introducing any external variable, just using $X$ and $Y$. We
analyse segments of length $n=2000$ and fixed $p=2$. The left figure shows the
prediction skills for varying $\alpha$. Note that the system is completely
synchronised at $\alpha=0.37$. T XKGC (Diego Bueso, 2020) improves detection
power over GC/KGC for any $\alpha$.

Transfer entropy (Schreiber, 2000) between $Y_{t}$ and $X_{t}$ measures the
amount of unique information contained in the past of $X_{t}$, denoted
$X^{-}=\\{X_{t-1},X_{t-2},\ldots\\}$, about the state of $Y_{t}$ and is
defined as $\mathcal{T}_{X\rightarrow
Y|Z}=H(Y_{t}|Y^{-},Z^{-})-H(Y_{t}|Y^{-},X^{-},Z^{-})$. Transfer entropy can be
considered as the generalisation of GC by extending the implicit conditional
independence test to arbitrary orders of dependence. Indeed, Barnett et al.
(2009) proved that (linear) GC and transfer entropy causality are equivalent
under the assumptions of VAR model class and Gaussian error distributions.

##### CCM.

Convergent cross-mapping (CCM) (Sugihara et al., 2012) is based on the simple
observation that if data from a deterministic dynamical system is generated by
a system of ordinary differential equations (ODEs), then the explicit form of
these equations directly defines the causes of each variable in the system:
$x$ is a cause of $y$ if the dynamics (any of the derivatives of $y$) is
expressed in terms of the state of $x$. For example, in the Lorenz attractor
system:

$\displaystyle x^{\prime}$ $\displaystyle=\sigma y-\sigma x$ $\displaystyle
y^{\prime}$ $\displaystyle=-xz+\rho x-y$ $\displaystyle z^{\prime}$
$\displaystyle=xy-\beta z$ (2.2)

$x_{t}$ is caused by $y_{t}$, $y_{t}$ is caused by $x_{t}$ and $z_{t}$ and
$z_{t}$ by $x_{t}$ and $y_{t}$ as summarised by the summary directed graph of
Fig. 2.3.

$x$$z$$y$ Figure 2.3: Summary graph for Lorenz attractor system.

Learning the generating ODE from time series data would allow us to recover
the causal relations and summary-directed graph. Nevertheless, relying on
Takens’ theorem (Takens, 1981), Sugihara et al. (2012) concluded that it is
not necessary to recover the exact ODE to recover its causal properties: if
one has a cause and effect variable within an ODE system, then a qualitative
description of the dynamics of the cause based on the dynamics of the effect
can be recovered. Surprisingly, while one would need a large number of lags to
estimate an ODE where no parametric assumptions have been made, Takens’
theorem states that a good enough estimate, i.e. one that retains the causal
properties of the ODE, can be made with at most $2d+1$ lags where $d$ is the
number of variables in the ODE.

##### The CCM pseudo-algorithm for checking if two variables $X$ and $Y$ are
causally related:

1. Choose embedding dimension $E$: number of lags to use with $1\leq E\leq 2d+1$. 2. Estimate cross-map skill $\rho(l)$ for a sequence of several observations $l_{1},\ldots,l_{N}$ with $l_{N}\leq L$, $L$ is the maximum number of available observations in the time series. For each $l_{i}$: (a) Construct shadow manifold $M_{x}$: in practice represented by matrix $Y\in R^{l\times E}$ with time series $y_{t},y_{t-1},y_{t-2},y_{t-E+1}$ (b) Assume the shadow manifold satisfies Takens’ theorem condition and retains the metric properties of manifold $M$. Thus estimate euclidean distance $d_{i}$ of $E$+1 nearest points on manifold $M_{x}$ to point $(x_{t},x_{t-1},\ldots,x_{t-E+1})$. Denote the time indices corresponding to these points as $t_{1},t_{2},\ldots,t_{E+1}$. (c) Construct estimate of $y_{t}$ using simplex projection in shadow manifold: weighted average of $E+1$ nearest points (on $M_{x}$) with weights determined according to the exponentially weighted distance on $M_{x}$ of each point (calculated in the previous step): $\hat{y}_{t}=\sum_{i=1}^{E+1}w_{i}y_{t_{i}}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \text{where}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ w_{i}=\frac{\exp(-\frac{d_{i}}{d_{1}})}{\sum_{i}\exp(-\frac{d_{i}}{d_{1}})}$ (2.3) (d) Construct cross-map skill $\rho(l)=Corr(y_{t},\hat{y_{t}}|M_{x}$) 3. Check if cross-map skill $\rho(l)$ converges as $l$ tends to $L$. As the number of observations used increases, the manifold estimation should be denser, so cross-map skill should improve and converge, provided our assumption that $M_{x}$ retains the metric properties of $M$ is true.

The algorithm should also be applied symmetrically to establish the
convergence of the cross-map skill $\hat{x}_{t}|M_{y}$. If both cross-map
skills converge, we can establish that both variables belong in the same ODE
system, and the causal relations are bi-directional. Note that in step 2c, we
only use the shadow manifold $M_{x}$ to determine which points and with which
weights should be used to estimate $y_{t}$. If the convergence of the cross-
map skill happens in only one direction, the proper conclusion is that a uni-
directional causal relationship exists between the two variables. If the
cross-map skill of $\hat{y}_{t}|M_{x}$ converges, the proper conclusion is
that $y$ causes $x$. This is somewhat counterintuitive, at least from the
point of view of more classical causal discovery methods, because to establish
that $x$ is an effect of the cause $y$, we must be able to predict the cause
$y$ using the effect $x$, where for all other methods discussed in this work
it is the other way around.

##### PC-based methods.

In the following, we start with an exposition of the PC algorithm (Spirtes et
al., 2000). We then explain both a naive (tsPC) and more sophisticated (PCMCI)
time series adaption.

  1. 1.

PC. The original PC algorithm (named after Peter and Clark’s authorship
(Spirtes et al., 2000)) was constructed for i.i.d random variables and thus,
in particular, for non-time series data. Below, we will also describe an
extension to the time series case. The PC algorithm assumes that the
underlying causal graph is a (_directed acyclic graph DAG_). A DAG has only
directed edges ($\rightarrow$ and $\leftarrow$) and no cycles. As for
independence-based algorithms in general, the PC algorithm assumes the causal
Markov condition and causal faithfulness to infer $d$-separations on the
causal graph from conditional independencies alone. Moreover, the algorithm
assumes causal sufficiency. Consequently, the algorithm cannot distinguish
between two graphs with the same set of $d$-separations. The graphical
representation of an equivalence class of DAGs with the same $d$-separations
is known as a (_completed partially-directed acyclic graph CPDAG_), which is
the object of discovery of PC. As compared to DAGS, CPDAGs can contain
undirected edges (${\circ\\!{\\--}\\!\circ}$). These undirected edges signify
that both orientations ($\rightarrow$ or $\leftarrow$) are compatible with the
set of conditional independencies.

##### The PC algorithm starts from a fully connected undirected graph and
consists of three phases:

(a) The _skeleton phase_ uses statistical (conditional) independence tests to
infer the adjacencies of the underlying causal graph. If two variables $X$ and
$Y$ are found to be independent conditional on a (possibly empty) set of
variables $\mathbf{Z}$, then the edge between $X$ and $Y$ is removed. (b) The
_collider orientation phase_ then orients all _collider motifs_ , that is,
motifs of the form $X\rightarrow Y\leftarrow Z$ where $X$ and $Z$ are non-
adjacent. These orientations can be inferred because collider motifs impose a
particular pattern of (conditional) (in-)dependencies. (c) The _orientation
phase_ finally uses graphical rules (Meek, 1995) to infer the orientation of
as many remaining unoriented edges as possible using the acyclicity assumption
and the fact that all colliders have been found in the previous step.

As compared to a brute-force execution of the skeleton phase as done in the
so-called SGS algorithm (Spirtes et al., 2000), the PC algorithm improves this
phase as follows: Instead of searching for conditioning sets $\mathbf{Z}$ that
renders a pair of variables $X$ and $Y$ independent (and thereby non-adjacent)
within the set of all variables in the system, it is sufficient to restrict
the search to those variables that are adjacent to $X$ and $Y$. The
sufficiency of this specified search is a direct consequence of assuming the
causal Markov condition.

The PC algorithm is fully non-parametric by construction and lends itself to
various application cases. It performs optimally when the underlying causal
graph is sparse and the number of variables is much less than the sample size.
However, for sufficiently sparse graphs, PC was shown to be computationally
feasible for very high-dimensional graphs as well (Kalisch and Bühlman, 2007).
In the worst-case scenario of very dense graphs, the number of conditional
independence tests to be performed grows exponentially with the number of
variables.

A variant of PC called _PC-stable_ (Colombo et al., 2014) was shown to be
_order-independent_ , that is, invariant under permutations of the variables
(this invariance is a desired property because it should not matter which
variable is considered to the be “first” and which is considered to be the
“last” variable). Another variant called for _Conservative PC_ (Ramsey et al.,
2006) is sound even if instead of the (full) causal faithfulness assumption,
only the weaker _adjacency faithfulness_ assumption is made. It is also
possible to infer whether or not _orientation faithfulness_ is violated
(Ramsey et al., 2006).

Although the PC algorithm was originally developed for the acyclic case, the
work (M. Mooij and Claassen, 2020) shows that PC is also consistent in the
presence of cycles if the learned graph is interpreted in a slightly different
way using the so-called $\sigma$-separation (Bongers et al., 2021). The proof
of this consistency uses the $\sigma$-separation (Bongers et al., 2021), which
is a generalisation of $d$-separation to the cyclic case. Subsequently, it
imposes a modified version of the Markov and faithfulness assumptions, namely
the $\sigma$-Markov and the $\sigma$-faithfulness conditions. Under these
conditions, the PC algorithm is proven to correctly learn the
$\sigma$-separation equivalence class of the true (potentially cyclic) causal
graph.

  2. 2.

tsPC. The naive extension of the PC algorithm to the time series case is
called tsPC, an example implementation is given in (Runge, 2020). The general
idea is to fix an integer $\tau_{\text{max}}$ that is supposed to be equal to
or larger than the maximum time-lag of any edge in the causal time series
graph and to learn the finite segment of the time series graph on a time
window $[t-\tau_{\text{max}},t]$. Here, $t$ is an arbitrary reference time
step, and samples are created by sliding the time window over all recorded
time steps. This approach implicitly assumes that the causal relationships do
not change throughout the recorded time steps. Suppose the assumption of no
contemporaneous causal influences is made. In that case, it is sufficient only
to run the skeleton phase of PC because then the orientation of all edges is
determined by time order (an effect cannot precede its cause). As discussed in
(Runge, 2020), tsPC suffers from a sub-optimal finite-sample performance due
to autocorrelation. This issue is remedied by the _PCMCI_ algorithm, explained
below. See Figure 2.2 for an illustration of the graphs learned by PC and tsPC
for the time series case example.

  3. 3.

PCMCI. The PCMCI algorithm (Runge et al., 2019b) is a time series causal
discovery algorithm that addresses some of the shortcomings of the naive time
series adaption of PC, in particular the issue of low detection power. PCMCI
assumes the time series graph to have no contemporaneous causal influences.
This assumption implies the absence of contemporaneous cycles, but feedback
cycles involving time lags are possible. Additionally, PCMCI assumes the time
series data are generated by a causally stationary process (that is, the
causal relationships are assumed to not change over time).

As discussed in (Runge et al., 2019b; Runge, 2020), two main challenges with
time series data hamper the performance of independence-based discovery
algorithms in time series. These challenges are related to autocorrelation, a
common feature in time series. First, using non-i.i.d. samples (created in a
sliding window fashion as explained above) typically leads to ill-calibrated
conditional independence tests, that is, uncontrolled type I errors, because
the degrees of freedom are reduced and cannot be easily measured. This ill-
calibratedness leads to inflated false positives, that is, the discovery of
dependence when, in fact, independence is true. Secondly, high autocorrelation
implies that there is little new information in the next time step compared to
the previous step. Depending on how the conditioning sets in conditional
independence tests are selected, this results in low effect sizes leading to
low detection power of true links. The effect size of a (conditional)
independence test is defined as the absolute value of the population value of
the test statistic; for example, in a (partial) correlation test, the effect
size is the absolute value of the population value of the (partial)
correlation. While there is a trade-off in addressing both of these
challenges, the PCMCI algorithm and its generalisation PCMCI+ (see below)
algorithms remedy these challenges to an extent by using a particular choice
of conditioning sets in the independent tests that decides about the presence
versus the absence of an edge between a given pair of variables. We spell out
the details below.

##### The PCMCI algorithm unfolds in two phases:

(a) The first phase, referred to as $\text{PC}_{1}$, is a _condition-selection
phase_ that aims to infer a superset $\hat{\mathcal{P}}(X^{j}_{t})$ of the
parents of each variable $X^{j}_{t}$ at time step $t$. The PC1 algorithm is a
variant of the PC and works as follows: Each sub-step of the skeleton phase is
indexed by the integer $p$, starting at $p=0$ and successively increasing $p$
in increments of one. Within each sub-step, the algorithm tests for
independence of $X^{i}_{t-\tau}$ and $X^{j}_{t}$ given a conditioning set that
consists of those $p$ potential parents of $X^{j}_{t}$ (less $X^{i}_{t-\tau}$)
that have the highest association with $X^{j}_{t}$ according to the previous
(conditional) independence tests. This particular choice of conditioning sets
increases the effect sizes of the (conditional) independence tests, as can be
understood information-theoretically (Runge, 2015). A higher effect size leads
to a higher statistical power (equivalently, to a lower probability of a type
II error), that is, makes it more likely to detect dependence if dependence is
true. However, since the effects of autocorrelation have not been dealt with
yet, this phase of PCMCI is affected by the same issues as the naive time
series extension of PC in terms of false positives. (b) The second phase
conducts for each pair of variables $X^{i}_{t-\tau}$ and $X^{j}_{t}$ the so-
called _momentary conditional independence (MCI) test_ that tests the null
hypothesis $X^{i}_{t-\tau}\rotatebox[origin={c}]{90.0}{$\models$}X^{j}_{t}\ |\
\hat{\mathcal{P}}(X^{j}_{t})\backslash\\{X^{i}_{t-\tau}\\},\hat{\mathcal{P}}(X^{i}_{t-\tau})\
.$ If this hypothesis is not rejected, the edge between $X^{i}_{t-\tau}$ and
$X^{j}_{t}$ is removed. While the condition on $\hat{\mathcal{P}}(X^{j}_{t})$
only would suffice to condition out confounded and indirect connections, the
additional conditioning on $\hat{\mathcal{P}}(X^{i}_{t-\tau})$ removes auto-
dependencies from $X^{i}_{t-\tau}$ such that the conditional independence
tests are well-calibrated and false positives are controlled at the desired
level (Runge et al., 2019b). Note that no orientation phase is required
because, by the assumption of no contemporaneous causal influences, all edges
are time-lagged and oriented by time order.

The numerical studies in (Runge et al., 2019b) show that in combination with
the MCI tests in its second phase, PCMCI improves detection power and false
positive control compared to the naive time series adaption.

  4. 4.

PCMCI+. The PCMCI+ algorithm (Runge, 2020) extends PCMCI to the case where
contemporaneous edges are allowed by suitably modifying the MCI phase (but
still disallowing contemporaneous causal cycles and latent confounders). It
consists of three phases: First, a $\text{PC}_{1}$ lagged phase. Second, an
MCI contemporaneous phase. Third, an orientation phase. The first phase
applies the $\text{PC}_{1}$ algorithm (see above) to the lagged edges. Its
goal is to infer a superset of the _lagged_ parents of each variable
$X^{j}_{t}$. However, due to the potential presence of contemporaneous links,
the first phase converges to a superset $\hat{\mathcal{P}}(X^{j}_{t})$ of the
lagged parents of $X^{j}_{t}$ plus the parents of the contemporaneous
ancestors of $X^{j}_{t}$. The MCI contemporaneous phase is initialised with
all the links found in the previous phase and all possible contemporaneous
links. It then conducts the conditional independence tests
$X^{i}_{t-\tau}\rotatebox[origin={c}]{90.0}{$\models$}X^{j}_{t}\ |\
\mathbf{S},\hat{\mathcal{P}}(X^{j}_{t})\backslash\\{X^{i}_{t-\tau}\\},\hat{\mathcal{P}}(X^{i}_{t-\tau})$,
where, in addition to the lagged conditions of the MCI tests in PCMCI,
$\mathbf{S}$ are sets of contemporaneous adjacencies of $X_{t}^{j}$ (and
$X_{t-\tau}^{i}$ for $\tau=0$). This removes all remaining spurious links due
to contemporaneous confounding or indirect paths. Finally, the orientation
phase orients all lagged links according to time order and then applies PC
orientation rules (Meek, 1995) to orient as many contemporaneous edges as
possible. See Figure 2.2 for an illustration.

##### FCI-based methods.

A major success of causal discovery is the development of methods for learning
causal relationships without assuming causal sufficiency. One famous example
is the FCI algorithm (Spirtes et al., 1995, 2000; Zhang, 2008b). We review the
standard FCI algorithm and several of its time series adapations.

  1. 1.

FCI. The FCI algorithm generalises the PC algorithm (see above) to the
causally insufficient case. In addition to latent confounders, the algorithm
can also deal with _selection variables_. These variables influence whether a
given sample point belongs to the observed population. For example, a certain
satellite observation might be more likely to be made if the cloud cover is
not too dense. Consequently, the statistical dependence relations will be
biased (giving it the name _selection bias_) as only one segment of the entire
population of possible satellite observations is being considered. Below, we
assume the absence of selection variables and explain the specialisation of
FCI in this case.

##### Quick Introduction to Maximal Ancestral Graphs.

To deal with latent confounders (and selection variables), FCI works with a
larger class of graphical models than PC does: Instead of DAGs, FCI works with
_maximal ancestral graphs_ (_MAGs_) (Richardson and Spirtes, 2002). Maximal
ancestral graphs can be interpreted as projections of the underlying DAG
(which consists of observed variables, latent confounders, and selection
variables) to a graph over the observed variables only. When assuming the
absence of selection variables (as we do here), it is sufficient to work with
a subset of MAGs that are called _directed maximal ancestral graphs_ (_DMAGs_)
(M. Mooij and Claassen, 2020). Parts of the literature for notational
simplicity do not explicitly distinguish between MAGs and DMAGs, that is,
speak of MAGs although referring to DMAGs. Directed maximal ancestral graphs
can have two types of edges: directed edges ($\rightarrow$) and bidirected
edges ($\leftrightarrow$). A directed edge $X\rightarrow Y$ says that variable
$X$ causally influences variable $Y$. This causal influence can be direct or
indirect through one or multiple unobserved variables. A bidirected edge
$X\leftrightarrow Y$ says that $X$ and $Y$ are subject to latent confounding
and that, at the same time, neither $X$ causally influences $Y$ nor the other
way around. Being subject to latent confounding means that there is an
unobserved variable $L$ that (potentially indirectly through other unobserved
variables) causally influences both $X$ and $Y$. In addition, an edge between
$X$ and $Y$ (i.e., $X\rightarrow Y$ or $X\leftarrow Y$ or $X\leftrightarrow
Y$) means that $X$ and $Y$ are not (conditionally) independent given any set
of observed variables. A subtle part of the interpretation of DMAGs is that
directed edges $X\rightarrow Y$ can “hide” latent confounding. That is to say,
while $X\rightarrow Y$ does say that $X$ causally influences $Y$, it is
possible that $X$ and $Y$ are also subject to latent confounding. Even if
there is such additional latent confounding, then the DMAG does not, in
addition, also contain the edge $X\leftrightarrow Y$ because there is at most
one edge between any pair of variables. However, for a certain type of
directed edges, called _visible_ and which can be determined graphically from
the DMAG, one can assert with certainty that there cannot be additional latent
confounding (Zhang, 2008a).

The FCI algorithm works in a way that is similar to the PC algorithm: First, a
sequence of (conditional) independence tests is performed to find the skeleton
(that is, the adjacencies) of the graph. Second, several orientation rules are
applied to determine the direction of as many links as possible. For these
details, we refer to the original works (Spirtes et al., 1995, 2000; Zhang,
2008b) or to more technical reviews of FCI, for example, see Section S2 in the
supplementary material of (Gerhardus and Runge, 2020).

As in the case of the PC algorithm, FCI does not learn a unique DMAG but
rather a Markov equivalence class of DMAGs. These equivalence classes are
graphically represented by _directed partial ancestral graphs_ (_DPAGs_)
(Zhang, 2008a, b; M. Mooij and Claassen, 2020). In addition to directed
($\rightarrow$) and bidirected edges ($\leftrightarrow$), DPAGs can also
contain edges of the types $X{\circ\\!{\rightarrow}}Y$ and
$X{\circ\\!{\\--}\\!\circ}Y$. An edge $X{\circ\\!{\rightarrow}}Y$ says that
$Y$ does not have a causal influence on $X$ while $X$ might or might not have
a causal influence on $Y$, whereas an edge $X{\circ\\!{\\--}\\!\circ}Y$ does
not make any claim about whether or not $X$ or $Y$ have a causal influence on
each other. See Figure 2.2 for an illustration of the graph that the FCI
algorithm discovers when applied to time series data. The work (M. Mooij and
Claassen, 2020) has shown that FCI, originally developed with the assumption
of acyclicity, can also be consistently applied to data that is generated by a
cyclic SCM with certain regularity conditions.

  2. 2.

tsFCI. The tsFCI algorithm (Entner and Hoyer, 2010) adapts FCI to causally
stationary time series. Here, the term _causal stationarity_ means that the
causal relationship between the variables $X^{i}_{t-\tau}$ and $X^{j}_{t}$ is
the same as the causal relationships between the variables $X^{i}_{s-\tau}$
and $X^{j}_{s}$ for any time steps $t$ and $s$. In other words, the causal
relationships are assumed invariant in time. As compared to the FCI algorithm,
tsFCI applies the following two conceptual modifications: First, lagged links
($\tau\geq 1)$ are by default oriented as
$X^{i}_{t-\tau}{\circ\\!{\rightarrow}}X^{j}_{t}$. These default orientations
are valid because an effect cannot precede its cause. Note that it would not
be valid to orient all lagged links as $X^{i}_{t-\tau}\rightarrow X^{j}_{t}$
because $X^{i}_{t-\tau}\leftrightarrow X^{j}_{t}$ (i.e., latent confounding)
is a possibility. Second, so-called _homologous_ edges are by default oriented
in the same way. That is if the edge between $X^{i}_{t-\tau}$ and $X^{j}_{t}$
has been found to have a certain orientation (for example,
$X^{i}_{t-\tau}\rightarrow X^{j}_{t}$ or $X^{i}_{t-\tau}\leftarrow X^{j}_{t}$)
and if in addition there is an edge between $X^{i}_{s-\tau}$ and $X^{j}_{s}$
for $s\neq t$, then this latter edge is immediately oriented in the same way
as the former edge (for example, oriented as $X^{i}_{s-\tau}\rightarrow
X^{j}_{s}$ or $X^{i}_{s-\tau}\leftarrow X^{j}_{s}$). This copying of edge
orientations is valid because of causal stationarity. In addition to these
modifications, tsFCI uses the knowledge of time order and causal stationarity
to apply further modifications that are useful from a computational and/or
statistical point of view.

There are two versions of tsFCI, both of which have been introduced in the
original work (Entner and Hoyer, 2010): One version does not allow for
contemporaneous causal influences in the data-generating process and another
version in which such influences are allowed. Figure 2.2 shows an illustration
of the output of tsFCI (its version that allows contemporaneous causal
influences) and other FCI-based time series causal discovery algorithms (see
below) in the case of an example time series graph.

In the graph learned by tsFCI (both variants), there can be an edge between
the pair of variables $X^{i}_{s-\tau}$ and $X^{j}_{s}$ (for example,
$X^{i}_{s-\tau}\leftrightarrow X^{j}_{s}$ or, only if $\tau=0$,
$X^{i}_{s}\leftarrow X^{j}_{s}$) and at the same time no edge between the pair
of variables $X^{i}_{t-\tau}$ and $X^{j}_{t}$ for $t>s$. At first sight, this
non-repetition of edges seems to contradict the assumption of a causally
stationary time series. However, there is, in fact, no contradiction: The
“additional” edge between $X^{i}_{s-\tau}$ and $X^{j}_{s}$ can result from
_temporal confounding_ , that is, result from confounding by variables that
are before the observed time window $[t-\tau_{\max},t]$.

  3. 3.

SVAR-FCI. The SVAR-FCI algorithm (Malinsky and Spirtes, 2018) is another
adaption of FCI to causally stationary time series. As compared to tsFCI
(variant with contemporaneous causation), SVAR-FCI removes the “additional”
edges that have been discussed in the last paragraph in the section on tsFCI.
More specifically, whenever SVAR-FCI detects marginal or conditional
independence of $X^{i}_{t-\tau}$ and $X^{j}_{t}$ and hence removes the edge
between these two variables, then the algorithm automatically and immediately
also removes the edges between the variables $X^{i}_{s-\tau}$ and $X^{j}_{s}$
for all time steps $s$. Consequently, in the graph learned by SVAR-FCI, the
variables $X^{i}_{t-\tau}$ and $X^{j}_{t}$ are adjacent if and only if for all
$s$ the variables $X^{i}_{s-\tau}$ and $X^{j}_{s}$ are adjacent.

The removal of the additional edges is justified by the fact that these edges
are known to result from confounding variables that are before the observed
time window. Hence, these edges would also disappear in tsFCI (both variants)
for an appropriately increased length of the observed time window. Moreover,
due to this modification, SVAR-FCI requires a smaller number of (conditional)
independence tests than tsFCI. However, as has been realised and explained in
(Gerhardus, 2021), SVAR-FCI, in theory, discovers fewer edge orientations than
tsFCI (variant with contemporaneous causation). To the authors’ knowledge, an
empirical comparison of tsFCI (variant with contemporaneous causation) and
SVAR-FCI on finite samples that would shed light on this trade-off has not yet
been performed.

  4. 4.

SVAR-GFCI. The SVAR-GFCI algorithm (Malinsky and Spirtes, 2018) is another
adaption of FCI to causally stationary time series. This algorithm is a hybrid
method that combines independence-based and score-based causal discovery. In
the first step, the algorithm employs a time series variant of the score-based
GES algorithm (see below for an explanation of the GES algorithm). The
adjacencies found in this first step are then passed as starting conditions to
the independence-based SVAR-FCI algorithm.

  5. 5.

LPCMCI. The LPCMCI algorithm (Gerhardus and Runge, 2020), also known as
Latent-PCMCI, is another adaption of FCI to causally stationary time series.
As compared to SVAR-FCI, Latent-PCMCI applies the ideas of PCMCI and PCMCI+
(see above) generalised to the causally insufficient case. Simulation studies
in (Gerhardus and Runge, 2020) show that Latent-PCMCI strongly outperforms
SVAR-FCI on finite samples, especially for strongly autocorrelated and
continuously valued variables.

  6. 6.

Learning extended summary graphs. Extended summary graphs (Assaad et al.,
2022a) are time-compressed representations of time series graphs that
distinguish between contemporaneous and lagged links (so they are more
informative than summary graphs) but that do not distinguish between two
different non-zero lags (so they are less informative than time series graph),
see Sec. 2.1.2 above for more details. To learn extended summary graphs,
(Assaad et al., 2022a) propose the PCGCE and FCIGCE algorithms. The basic idea
of both these algorithms is to group the past time steps of each component
time series $X^{i}$ into a vector variable $X^{i,-}$ and then, using
conditional independence tests that can handle vectors of variables,
respectively apply the PC and FCI algorithms directly to the extended summary
graph. Specifically, (Assaad et al., 2022a) use a conditional independence
test based on conditional mutual information. Moreover, for practical reasons,
the vector variable $X^{i,-}$ does not contain _all_ past time steps of
$X^{i}$ but all those time steps within the time window $[t-\gamma,t-1]$ where
$\infty>\gamma\geq 1$ is a user-specified positive integer that corresponds to
the maximal lag up to which the method is supposed to be sensitive (this
parameter $\gamma$ corresponds to the parameter $\tau_{max}$ in PCMCI, for
example).

##### Greedy Equivalence Search (GES).

GES (Meek, 1997; Chickering, 2002b, a) is probably the most famous score-based
causal discovery method for i.i.d data assuming that the true causal graph is
a DAG. It performs greedy steps directly on the CPDAG, thus searching in the
Markov equivalent class space. Chickering (Chickering, 2002b) proved that an
efficient two-phase greedy search, combined with the BIC score is sufficient
to find the true CPDAG in the large sample limit (the Meek conjecture (Meek,
1997)) assuming causal sufficiency. Ramsey et al. (Ramsey et al., 2017)
developed Fast GES (FGES) an optimised and parallelised version of the GES
algorithm, which they were able to scale up to a million variables.
Additionally, GES has been improved by bounding polynomially the score
evaluations (Chickering and Meek, 2015); to obtain statistical efficiency
(Chickering, 2020); to obtain finite-sample correction of confidence intervals
(Gradu et al., 2022) and to deal with latent variables (Claassen and Bucur,
2022). Similarly to other methods developed for i.i.d. data, (F)GES can be
applied to uniformly-sampled causally stationary time series by simply
considering the transformed lagged variables and imposing that the effects
cannot precede the causes in time.

##### Continuous optimisation methods.

A recent advance in structure learning has been the development of so-called
continuous optimisation methods, particularly score-based methods which avoid
the explosion of the discrete space of DAGs by employing continuous
optimisation. The first such method is the NOTEARS algorithm proposed by Zheng
et al. (Zheng et al., 2018) which proposed $h({\bf
W})=\operatorname{tr}(\exp({\bf W}\circ{\bf W})-d$ as differentiable
characterisation of acyclicity for a weighted adjacency matrix ${\bf W}$, that
is $h({\bf W})=0$ if and only if the associated graph is a DAG. Such
differentiable characterisations allow the plug-in use of different continuous
optimisation methods and even complex function parameterisations (Zheng et
al., 2020; Ng et al., 2022; Lachapelle et al., 2020; Ng et al., 2020; Yu et
al., 2021; Bello et al., 2022). Various implementations of the continuous
optimisation framework for structure learning from time series are available:
(1) DYNOTEARS (Pamfil et al., 2020) considers structural linear VAR (SVAR)
models, allowing for contemporaneous links and enforcing acyclicity among the
instantaneous edges. (2) IDYNO (Gao et al., 2022) is designed to perform
structural discovery from both observational and interventional data.
Moreover, both linear and non-linear relationships are considered. (3) NTS-
NOTEARS (Sun et al., 2023) models cause-effect relationships through one-
dimensional convolution neural networks (CNN) and allows prior knowledge to be
encoded and exploited directly by the optimisation procedure.

##### (VAR)LiNGAM.

Linear non-Gaussian acyclic model (LiNGAM) (Shimizu et al., 2006) is a
classical method for causal discovery which assume acyclicity, causal
sufficiency, linear relationships and non-Gaussian additive independent
noises. Under those assumptions, the model is shown to be identifiable thanks