Improving Finite Sample Performance of Causal Discovery by Exploiting Temporal Structure
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.
Tom: We're looking at the paper: "Improving Finite Sample Performance of Causal Discovery by Exploiting Temporal Structure".
Jane: Here's the gist of the paper. Improving Finite Sample Performance of Causal Discovery by Exploiting Temporal Structure is an algorithm that efficiently exploits temporal structure to improve causal discovery algorithms, rendering them more robust to statistical errors and ultimately increasing accuracy in finite samples<ref:2406.19503#pg2>.
Tom: This approach is particularly useful because temporal information is often available in biomedical or epidemiological data and is usually unambiguous and correct<ref:2406.19503#pg3>.
Jane: Discovering causal structures in data is a challenging task<ref:2406.19503#pg2>.
Tom: Existing algorithms are known to be unstable and sensitive to statistical errors, which makes them rarely used with biomedical or epidemiological data<ref:2406.19503#pg2>.
Paper summary: Tom: So, so this paper, "Improving Finite Sample Performance of Causal Discovery by Exploiting Temporal Structure," it's looking at a really hard problem there. They’re talking about how to find causal structures in data when you only have a finite sample size.
Jane: That's the core issue, right? Existing causal discovery algorithms are known to be unstable and they get really sensitive to statistical errors, which makes them pretty unreliable when you're using real biomedical or epidemiological data.
Lu: Yeah, that sensitivity is a major problem because expert knowledge or background information can sometimes be wrong or just not perfectly compatible with the actual data you have.
Meng: So what are they proposing? I need to know if this is just another tweak to an existing algorithm, or something fundamentally new. What's the main claim of this paper?
Tom: They’re presenting an algorithm that efficiently exploits temporal structure, which they call tiered background knowledge, for estimating those causal structures. The central thesis is that when you use this tiered knowledge correctly, it makes the causal discovery method much more robust to statistical errors and ultimately increases its accuracy even with finite samples >
Jane: And the paper points out that this kind of temporal information is often readily available in real-world data sources, like cohort or registry data. They suggest that using it efficiently renders the algorithm more stable for practical applications >
Lu: They extend a basic algorithm called PC, which they call the tiered PC or tPC algorithm. They incorporate this tiered background knowledge into several parts of the process, like modifying how they handle the skeleton phase and orienting cross-tier edges >
Meng: So what's the concrete evidence that this tiered knowledge actually helps? I want to see a specific result, not just a general claim about robustness.
Tom: The simulation study shows that incorporating this tiered background knowledge significantly improves graph estimation performance overall > Specifically, the improved recall of adjacencies happens with no or little loss in precision when you use the tiered ordering >
Jane: That sounds promising because recall and precision are both important metrics, right? So they also showed an overall increase in both the precision and recall of possible ancestral relations, which implies greater confidence in the causal conclusions you draw from these estimated graphs >
Lu: They formally prove that their oracle version of this tPC algorithm is sound and complete, meaning it outputs the unique maximally partitioned directed acyclic graph that represents both the independence model and that tiered background knowledge > Plus, they show that under any input set of conditional independencies, the partially directed graph they get at the end of phase three a is consistent with K tau >
Paper summary: Meng: Consistency sounds important for deployment. What about how stable this whole thing is? If we can't rely on it being order independent, it doesn's not really deployable in many settings >
Tom: They actually formally prove that the tLMPC stable algorithm is order independent, meaning its final output doesn't depend on the sequence in which you visit the variables > This stability is maintained across phases because they skip certain conditioning sets based on that tiered background knowledge rather than depending on the visit sequence itself >
Jane: That’s a strong point, because if it were order dependent, you'd have to worry about how your data was collected or ordered during the analysis > But what about how they test this on real-world data?
Lu: They applied it to data from the IDEFICS family study to show its practical use > The results indicated that graphs using detailed background knowledge, specifically tau three, share many of the same v structures and their equivalence classes are closer compared to those estimated without any background knowledge >
Meng: So what does that mean for us on the ground? If we have a complex system where we know some temporal relationships, this method is better than just throwing a standard algorithm at it > But if we only have partial knowledge, how much improvement can we actually expect?
Tom: The proportion of conflicting edges decreases as more background knowledge is included for all settings, which suggests that the more reliable the temporal information you feed in, the fewer weird or conflicting structures you end up with > They showed that recall of v structures clearly improves when more detailed background knowledge is included >
Jane: So if we take this to a practical application, like analyzing longitudinal health data where we know certain events happen in sequence, this method seems to offer a way to get better structural results than what's possible with just the raw data structure > This paper’s focus on how temporal structure improves finite sample performance is really what makes it relevant for fields like epidemiology >
Lu: Yes, and they did show how detailed background knowledge, tau three, yields the largest number of directed edges in their application to that specific study > That suggests that the more you know about the underlying process temporally, the richer your resulting causal graph estimate can be >
Meng: It’s interesting how they contrast this with using only partial knowledge like tau one or just partial background knowledge like tau two, showing a clear hierarchy in performance gains based on how much detail you provide > But I wonder what happens if that temporal knowledge itself is slightly inaccurate?
Paper summary: Tom: They acknowledge that the quality of the causal structure depends heavily on how reliable that temporal background knowledge is > The paper suggests using this approach strengthens the credibility of estimated graphs because temporal information is often highly reliable in those domains >
Jane: So, to wrap up this paper, "Improving Finite Sample Performance of Causal Discovery by Exploiting Temporal Structure," it’s about taking existing causal discovery tools and making them better suited for real data—especially finite samples like those from a study. The authors demonstrate that by efficiently incorporating temporal structure, or tiered background knowledge, the algorithm becomes much more stable and accurate >
Lu: They establish the soundness of their oracle version of this tPC algorithm, showing it outputs the unique maximally partitioned directed acyclic graph representing both the independence model and that tiered background knowledge > And they proved its order independence across all phases >
Meng: So, for those of us trying to ship models to production, what’s the real cost here? Is implementing this extra knowledge structure too much overhead compared to just running a standard PC algorithm on the raw data?
Tom: The paper points out that the naive, post hoc inclusion of background knowledge offered less improvement than efficiently incorporating it early in the algorithm > So you have to get that tiered structure right from the start for any real benefit >
Jane: What this means for people who just listen to the show is that when you're dealing with messy data, don't just rely on what the data says about connections; look into how temporal context—how things happen over time—can provide a strong, reliable scaffolding for building those causal models >
Lu: And they did flag a limitation: for more general types of background knowledge, it cannot necessarily be guaranteed that the estimated equivalence class will actually be consistent with that knowledge > So the method’s success is tied to the specific structure of the knowledge you feed it >
Meng: That's a fair caveat. If we try to apply this to a situation where our temporal assumptions are totally wrong, this whole framework might fall apart, right?
Tom: Exactly. The paper suggests that more general types of background knowledge present challenges when you try to incorporate the tiered structure while estimating the equivalence class > So it’s not a magic fix for every causal discovery problem >
Jane: Overall, this work shows that leveraging reliable temporal information from sources like registries and cohorts can significantly boost the accuracy of causal discovery in real-world scenarios, especially where data samples are limited. That’s what "Improving Finite Sample Performance of Causal Discovery by Exploiting Temporal Structure" is about >
Conclusion: Tom: So, this paper is titled "Improving Finite Sample Performance of Causal Discovery by Exploiting Temporal Structure." It’s about taking causal discovery and making it better when you only have a limited amount of data to work with.
Jane: Right, so basically it looks at how using the timeline of events—the temporal structure—can help us find the right cause and effect relationships even when our sample size is small.
Lu: The authors introduce this idea of tiered background knowledge and how exploiting that temporal information makes their algorithms much more stable and accurate for those finite samples.
Meng: What does that actually mean for someone trying to ship a model? Does it just make the graph look prettier, or does it actually help when the data is messy?
Tom: It helps when the data is messy because these algorithms are usually very sensitive to statistical errors, which ruins them with small datasets. This method makes them more robust to those errors.
Jane: And they show that this temporal context, which we often have in things like medical records or family histories, actually gives us a better map of the cause and effect relationships than just looking at the connections between variables in isolation.
Lu: They prove mathematically that this tiered knowledge improves graph estimation performance across several metrics, like recall for adjacencies and precision for v structures. It’s not just a hopeful claim; they show it works on simulations.
Meng: So the numbers are showing that adding more detailed temporal structure reduces the number of conflicting edges, which is good because conflicting edges mean your model isn't making sense.
Tom: Exactly. And they also prove this whole process stays order independent, meaning it doesn't matter in what sequence you visit the variables to get the final result. That’s a big deal for deployment because we don't want our results depending on an arbitrary visiting order.
Jane: So, to sum up, the title is about using time information to make causal discovery more reliable when data is scarce, and the authors show that this tiered approach significantly boosts accuracy and stability in practice.
Meng: It’s interesting because they admit that if the temporal background knowledge you feed them isn't actually correct—if your assumptions about the timeline are wrong—the method can still fail to be consistent with reality.
Lu: That’s the caveat, Meng. The method is strong when it gets the right temporal scaffolding, but it doesn't magically fix a fundamentally flawed model of time.
Tom: But for data where we know some things happen in order, like in epidemiology, this isn't just theoretical; it’s a tangible way to get better causal graphs from the data we have.
Jane: And that leads us next to how they actually tested this on a real study called IDEFICS, which really shows the practical benefits of using detailed temporal knowledge.
Leibniz Institute for Prevention Research and Epidemiology BIPS · Faculty of Mathematics and Computer Sciences University of Bremen
stat.ME, stat.ML
Submitted: 2024-06-27
Updated: 2024-06-27
DOI: 10.1177/09622802261422162
Code: https://github.com/bips-hb/tpc
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 83/100
The gist: Improving Finite Sample Performance of Causal Discovery by Exploiting Temporal Structure is an algorithm that efficiently exploits temporal structure to improve causal discovery algorithms…
Key concepts
- Finite Sample Performance
- This refers to how well a causal discovery algorithm works when you have a limited amount of data. Standard methods often fail or become unstable with small datasets, but this approach aims to make them more robust and accurate even when data is scarce.
- Tiered Background Knowledge
- This involves using different levels of pre-existing knowledge about the causal system, organized in tiers. By incorporating this structured knowledge early in the algorithm, the method gains stability and better performance because it leverages reliable temporal information specific to certain data types.
- V-structure
- A V-structure is a specific pattern in a causal graph where two independent causes point toward a single common effect. The paper measures the accuracy of identifying these structures, showing that incorporating background knowledge helps improve the recall and precision of finding these important patterns.
Terminology
Summary
Improving Finite Sample Performance of Causal Discovery by Exploiting Temporal Structure is an algorithm that efficiently exploits temporal structure to improve causal discovery algorithms, rendering them more robust to statistical errors and ultimately increasing accuracy in finite samples<ref:2406. p. 1 One major problem is that they can be unstable
or ambiguous with finite data due to sensitivity to sampling variation. In this paper, we describe
how temporal structure of the data, or more generally tiered background knowledge, can efficiently be
exploited to improve causal discovery algorithms, rendering the methods more stable and robust for
practical applications. This is very useful as temporal information is often available in biomedical or
epidemiological data, e. , when using patients’ records or cohort data as in life course epidemiology
[11], and it is usually unambiguous and correct.Where the paper says it
Where the paper says it
Introduction to the Problem
Discovering causal structures in data is a challenging task<ref:2406.19503#pg2>. Existing algorithms are known to be unstable and sensitive to statistical errors, which makes them rarely used with biomedical or epidemiological data<ref:2406. p. 0 Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. Existing
algorithms are known to be unstable and sensitive to statistical errors, and are therefore rarely
used with biomedical or epidemiological data. It has the advantages that it relies on relatively few assumptions, and that it is flexible,
allowing for various extensions and adaptations to different data types. However, the PC algorithm
also suffers from the limitations mentioned above: One is a lack of informativeness and the other is
sensitivity to statistical errors.Where the paper says it
Where the paper says it
The Tiered PC Algorithm
The authors introduce the tiered PC (tPC) algorithm, which extends the basic PC algorithm by exploiting tiered background knowledge<ref:2406.19503#pg3>. This extension is designed to make the methods more stable and robust for practical applications<ref:2406. p. 1 One major problem is that they can be unstable
or ambiguous with finite data due to sensitivity to sampling variation. In this paper, we describe
how temporal structure of the data, or more generally tiered background knowledge, can efficiently be
exploited to improve causal discovery algorithms, rendering the methods more stable and robust for
practical applications. If we were to switch (IIIb)
and (IV) of the tPC algorithm, the sample version would not guarantee the consistency with the tiered
background knowledge of all orientations following the application of Meek’s rules. Hence, we should
orient cross-tier edges before applying Meek’s rules in order to avoid unnecessary errors, as illustrated
in the following example.Where the paper says it
Where the paper says it
Benefits of Tiered Background Knowledge
The simulation study demonstrates that incorporating tiered background knowledge significantly improves graph estimation performance<ref:2406.19503#pg5>. Specifically, the improved recall of adjacencies comes at no or little loss in precision when using the tiered ordering<ref:2406.19503#pg6>. Furthermore, the study showed an overall increase in precision as well as recall of possible ancestral relations, implying greater confidence in causal conclusions drawn from graphs estimated using background knowledge<ref:2406. p. 1 While the PC algorithm has desirable
asymptotic properties [12, 13], with finite samples it is prone to errors due to erroneous conclusions
based on statistical tests propagating through the algorithm. It was previously shown that tiered
background knowledge improves the informativeness of the estimated graphs from infinite data [14].Where the paper says it
Soundness and Consistency
The authors establish that the oracle version of the tPC algorithm is sound and complete, meaning it outputs the unique MPDAG representing the independence model and the tiered background knowledge<ref:2406.19503#pg9>. Proposition 2 further shows that under any input set of conditional independencies, the partially directed graph obtained at the end of phase (IIIa) is consistent with Kτ<ref:2406. p. 8 Let Kτ be the tiered background knowledge used by the tPC algorithm. Under any
input set of conditional independencies, the partially directed graph obtained at the end of phase (IIIa)
of the tPC algorithm is consistent with Kτ . This order dependence is eliminated by the LMPC-stable
algorithm. Here, we establish formally that the tLMPC-stable algorithm is also order independent.Where the paper says it
Where the paper says it
Practical Application and Findings
The application to data from the IDEFICS/I.Family study illustrates how the tPC algorithm performs in practice<ref:2406. p. 1 In Section 4 we conduct an extensive simulation study exploring the finite sample performance of the
tPC algorithm. In Section 5 we show how the algorithm can be used in practice by applying it to data
from an actual children’s cohort study investigating the interplay of diet, physical activity and other
lifestyle factors with regard to several health outcomes [19]. It was previously shown that tiered
background knowledge improves the informativeness of the estimated graphs from infinite data [14]. In the present paper we specifically address finite sample properties and show how making efficient
use of tiered background knowledge increases the robustness towards statistical errors yielding more
accurate outputs. Similarly, conflicts (i. bidirected edges)
can also arise if Meek’s rules lead to conflicting orientations. Similarly, conflicts (i. bidirected edges)
can also arise if Meek’s rules lead to conflicting orientations. Similarly, conflicts (i. bidirected edges)
can also arise if Meek’s rules lead to conflicting orientations.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
The paper concludes that making use of tiered background knowledge greatly improves graph estimation, strengthening the credibility of the estimated graphs obtained from causal discovery because temporal background knowledge is often highly reliable<ref:2406.19503#pg9>. The naive, post hoc, inclusion of background knowledge offered less improvement than efficiently incorporating it early in the algorithm<ref:2406. p. 6 A first approach for combining background knowledge with a discovery algorithm is to impose it
post hoc onto the output. We define the following naive tiered PC (naive tPC) algorithm.Where the paper says it
Simulation Study Details
The simulation study compared MPDAGs constructed using no background knowledge (τ1), partial background knowledge (τA2, τB2, τC2 or τD2), and detailed background knowledge (τ5)<ref:2406.19503#pg9>. The comparison showed that the recall of v-structures clearly improves when more detailed background knowledge is included<ref:2406.19503#pg9>. Similarly, the precision of v-structures improves for dense graphs when including background knowledge<ref:2406. p. 1 While the PC algorithm has desirable
asymptotic properties [12, 13], with finite samples it is prone to errors due to erroneous conclusions
based on statistical tests propagating through the algorithm. It was previously shown that tiered
background knowledge improves the informativeness of the estimated graphs from infinite data [14].Where the paper says it
Data Application Details
The data application used the IDEFICS/I.Family study to estimate three different MPDAGs using τ1, τ2, and τ3<ref:2406.19503#pg9>. The estimated graphs with background knowledge (τ2 and τ3) share many of the same v-structures, and their equivalence classes are closer compared to the graph estimated without using background knowledge (τ1)<ref:2406. p. 5 If there are multiple orderings, τ1 and τ2, to be compared we say that τ1 is finer than τ2 (and τ2
is coarser than τ1) if for every Vi
, Vj ∈ V: τ2(Vi) < τ2(Vj ) ⇒ τ1(Vi) < τ1(Vj ). A tiered ordering entails background knowledge in the following way. Under any
input set of conditional independencies, the partially directed graph obtained at the end of phase (IIIa)
of the tPC algorithm is consistent with Kτ . Unlike the sample version of the naive tPC algorithm, the above states that the sample versions of
the basic tPC or tLPMC-stable algorithm are consistent with the tiered background knowledge before
using it to orient the cross-tier edges.Where the paper says it
Where the paper says it
Performance Metrics
The performance measures include correct skeleton, correct v-structures, ancestral relations, and possible ancestral relations<ref:2406.19503#pg9>. Precision and recall are calculated relative to the true DAGs for adjacencies and v-structures<ref:2406.19503#pg9>. The proportion of conflicting edges is computed using equation (6)<ref:2406. p. 5 Similarly, conflicts (i. bidirected edges)
can also arise if Meek’s rules lead to conflicting orientations. Similarly, conflicts (i. bidirected edges)
can also arise if Meek’s rules lead to conflicting orientations. Meek [21]). Note that in the first round of (II) with separating sets of size
zero, the same number of tests are carried out by the sample versions of tPC as by the PC algorithm;
in the next round with separating sets of size one, tPC typically performs fewer tests as it avoids
conditioning on the future (see Figures 32 and 33 in Appendix C.Where the paper says it
Where the paper says it
Where the paper says it
Order Independence
The tLMPC-stable algorithm was formally proven to be order independent, meaning its output does not depend on the sequence in which the variables are visited<ref:2406.19503#pg9>. This stability is preserved across phases because certain conditioning sets are skipped based on tiered background knowledge rather than the visit sequence<ref:2406. p. 8 This result means that the oracle versions of the tPC algorithm output the unique MPDAG representing the independence model and the tiered background knowledge, i. separating sets ‘in the
future’ can indeed be ignored as in phases (II) and (IIIa). Moreover, the output of the sample version of the basic PC algorithm depends on the sequence
(order) in which the variables are visited. To account for this, a modification has been introduced,
the so-called LMPC-stable algorithm, which is order independent through three phase specific modifications to (II-IV).Where the paper says it
Where the paper says it
Future Work
Future work will involve relaxing the causal sufficiency assumption by investigating the Fast Causal Inference (FCI) algorithm<ref:2406.19503#pg9>. Tiered background knowledge can be incorporated into FCI in a similar fashion as in the PC algorithm<ref:2406. p. 0 Existing
algorithms are known to be unstable and sensitive to statistical errors, and are therefore rarely
used with biomedical or epidemiological data. We present an algorithm that efficiently exploits
temporal structure, so-called tiered background knowledge, for estimating causal structures. Conflicting edges and ambiguous triples make the estimated graph difficult to interpret since it no
longer necessarily represents an equivalence class. However, they reflect the uncertainty entailed by
finite data. Existing
algorithms are known to be unstable and sensitive to statistical errors, and are therefore rarely
used with biomedical or epidemiological data. We present an algorithm that efficiently exploits
temporal structure, so-called tiered background knowledge, for estimating causal structures.Where the paper says it
Where the paper says it
Where the paper says it
Acknowledgements
This project was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project 281474342/GRK2224/ and 256000800<ref:2406.19503#pg9>. The references listed are [1] through [38]<ref:2406. p. 0 the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
References
[1] Spirtes P, Glymour CN, Scheines R. Causation, prediction, and search. p. 0 Ideally, we would like to input the data
into an algorithm that outputs one or more plausible causal directed acyclic graphs (DAGs) linking
the variables in the data. Such data driven approaches for estimating a causal DAG are known as
causal discovery (or causal search, structure learning etc. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[2] Vowels MJ, Camgoz NC, Bowden R. D’ya like DAGs? p. 0 Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. Ideally, we would like to input the data
into an algorithm that outputs one or more plausible causal directed acyclic graphs (DAGs) linking
the variables in the data. Ideally, we would like to input the data
into an algorithm that outputs one or more plausible causal directed acyclic graphs (DAGs) linking
the variables in the data. Such data driven approaches for estimating a causal DAG are known as
causal discovery (or causal search, structure learning etc. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[3] Maathuis MH, Colombo D, Kalisch M, et al. Predicting causal effects in large-scale systems from observational data. p. 0 Similarly, in an analysis of
healthcare data considering cardiac surgery it was found that many of the known predictors were in
fact only indirect causes of postoperative length of stay [6]. Also, it has been suggested to use causal
discovery to improve the quality of care for hip replacement patients by investigating the complex
clinical performance of implants with data from large patient registries [7]. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[4] Petersen AH, Osler M, Ekstrøm CT. Data-Driven Model Building for Life-Course Epidemiology. p. 1 Data driven methods for estimating
causal DAGs provide an alternative, or supplement, to relying solely on expert knowledge [9]. For
instance, in the context of building a life course model for depression in early old age, it was found that
different experts’ causal DAGs and the output of a causal discovery algorithm exhibited considerable
disagreement [10]. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[5] Foraita R, Witte J, B¨ornhorst C, et al. A Longitudinal Causal Graph Analysis Investigating Modifiable Risk Factors and Obesity in a European Cohort of Children and Adolescents. p. 0 Exceptions are, for example, two applications of causal discovery
to data from cohort studies finding that modifiable risk factors in early childhood or early life have
mostly indirect, if any, causal relations with later health outcomes[4, 5]. Similarly, in an analysis of
healthcare data considering cardiac surgery it was found that many of the known predictors were in
fact only indirect causes of postoperative length of stay [6]. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[6] Lee JJ, Srinivasan R, Ong CS, et al. Causal determinants of postoperative length of stay in cardiac surgery using causal graphical learning. p. 0 Exceptions are, for example, two applications of causal discovery
to data from cohort studies finding that modifiable risk factors in early childhood or early life have
mostly indirect, if any, causal relations with later health outcomes[4, 5]. Similarly, in an analysis of
healthcare data considering cardiac surgery it was found that many of the known predictors were in
fact only indirect causes of postoperative length of stay [6]. Exceptions are, for example, two applications of causal discovery
to data from cohort studies finding that modifiable risk factors in early childhood or early life have
mostly indirect, if any, causal relations with later health outcomes[4, 5]. Similarly, in an analysis of
healthcare data considering cardiac surgery it was found that many of the known predictors were in
fact only indirect causes of postoperative length of stay [6]. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[7] Cheek C, Zheng H, Hallstrom BR, et al. Application of a causal discovery algorithm to the analysis of arthroplasty registry data. p. 0 Exceptions are, for example, two applications of causal discovery
to data from cohort studies finding that modifiable risk factors in early childhood or early life have
mostly indirect, if any, causal relations with later health outcomes[4, 5]. Similarly, in an analysis of
healthcare data considering cardiac surgery it was found that many of the known predictors were in
fact only indirect causes of postoperative length of stay [6]. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. Existing
algorithms are known to be unstable and sensitive to statistical errors, and are therefore rarely
used with biomedical or epidemiological data. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[8] Tennant PW, Murray EJ, Arnold KF, et al. Use of directed acyclic graphs (DAGs) to identify confounders in applied health research: Review and recommendations. p. 2 We use ∗−∗ as a placeholder for an arbitrary edge type. We consider directed
acyclic graps (DAGs), partially directed acyclic graphs (PDAGs), completed PDAGs (CPDAGs), and
maximally oriented PDAGs (MPDAGs). Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[9] Didelez V. p. 0 Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. Ideally, we would like to input the data
into an algorithm that outputs one or more plausible causal directed acyclic graphs (DAGs) linking
the variables in the data. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[10] Petersen AH, Ekstrøm CT, Spirtes P, et al. Constructing Causal Life-Course Models: Comparative Study of Data-Driven and Theory-Driven Approaches. p. 1 Data driven methods for estimating
causal DAGs provide an alternative, or supplement, to relying solely on expert knowledge [9]. For
instance, in the context of building a life course model for depression in early old age, it was found that
different experts’ causal DAGs and the output of a causal discovery algorithm exhibited considerable
disagreement [10]. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[11] Kuh D, Ben-Shlomo Y. A life course approach to chronic disease epidemiology. p. 1 This is very useful as temporal information is often available in biomedical or
epidemiological data, e. , when using patients’ records or cohort data as in life course epidemiology
[11], and it is usually unambiguous and correct. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way.Where the paper says it
Where the paper says it
[12] Kalisch M, B¨uhlmann P. Estimating high-dimensional directed acyclic graphs with the PCalgorithm. p. 0 Ideally, we would like to input the data
into an algorithm that outputs one or more plausible causal directed acyclic graphs (DAGs) linking
the variables in the data. Such data driven approaches for estimating a causal DAG are known as
causal discovery (or causal search, structure learning etc. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[13] Harris N, Drton M. PC algorithm for nonparanormal graphical models. p. 0 To illustrate its usefulness in practice, we apply
the algorithm to data from a children’s cohort study investigating the interplay of diet, physical
activity and other lifestyle factors for health outcomes. Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[14] Bang CW, Didelez V. p. 0 Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. Figure 2 encodes
that Xpar. edu and Xsleep are marginally independent but become dependent conditionally on Xscreen time. An MPDAG represents a restricted equivalence class. In this paper, we are concerned with tiered background knowledge as given, say, by a partial
temporal ordering of the variables, e. Conflicting edges and ambiguous triples make the estimated graph difficult to interpret since it no
longer necessarily represents an equivalence class. However, they reflect the uncertainty entailed by
finite data. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[15] Scheines R, Spirtes P, Glymour C, et al. The TETRAD project: Constraint based aids to causal model specification. p. 3 Even under faithfulness, and given the correct independence model, we are still
limited by the fact that multiple DAGs can be Markov equivalent. The basic PC algorithm [1] is a constraint-based algorithm that estimates a CPDAG. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[16] Witte J, Foraita R. tpc: Temporal PC Algorithm; 2022. p. 0 Existing
algorithms are known to be unstable and sensitive to statistical errors, and are therefore rarely
used with biomedical or epidemiological data. We present an algorithm that efficiently exploits
temporal structure, so-called tiered background knowledge, for estimating causal structures. The basic PC algorithm makes use of faithfulness in phase (II) to construct the skeleton, and of
the particular conditional independencies encoded by v-structures in phase (III). When analysing the properties of causal discovery methods, the oracle version and the sample
version should be distinguished. We present an algorithm that efficiently exploits
temporal structure, so-called tiered background knowledge, for estimating causal structures. Tiered
background knowledge is readily available from, e. We present an algorithm that efficiently exploits
temporal structure, so-called tiered background knowledge, for estimating causal structures. Tiered
background knowledge is readily available from, e. We present an algorithm that efficiently exploits
temporal structure, so-called tiered background knowledge, for estimating causal structures. Tiered
background knowledge is readily available from, e. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[17] Petersen AH. causalDisco: Tools for Causal Discovery on Observational Data; 2023. p. 0 Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. The basic PC algorithm makes use of faithfulness in phase (II) to construct the skeleton, and of
the particular conditional independencies encoded by v-structures in phase (III). When analysing the properties of causal discovery methods, the oracle version and the sample
version should be distinguished. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[18] Andrews RM, Bang CW, Didelez V, et al. p. 0 Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. We consider an extension of the PC algorithm that exploits tiered background knowledge, and we
refer to this as the tiered PC (tPC) algorithm. Such an extension was previously suggested [1], and
versions of the tPC algorithm have been implemented in the TETRAD software [15] and R packages
[16, 17, 18], and have been applied [4, 5]. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way.Where the paper says it
Where the paper says it
Where the paper says it
[19] Ahrens W, Siani A, Adan R, et al. Cohort Profile: The transition from childhood to adolescence in European children–how I. p. 6 ◦
The following more complex example shows that more than just the cross-tier edges are oriented
as a consequence of tiered background knowledge. Consider the nodes in DAG D from Figure 1 (a) and their time structure
Early life (tier 1) parental education, breastfeeding
Childhood (tier 2) screen time, sleep, well-being
Adolescence (tier 3) physical activity, BMI
The corresponding CPDAG and tiered MPDAG are given in Figure 3. Finally, Section 6 provides a discussion of
the results. 2 Basic Concepts
In this section we introduce the formal graphical framework and describe the algorithms which ours
extends. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[20] Andersson SA, Madigan D, Perlman MD. p. 3 We refer to a class of Markov equivalent graphs as
a (Markov) equivalence class. An equivalence class of DAGs is represented by a CPDAG (a full
characterisation of CPDAGs can be found in Andersson et al. We refer to the resulting graph as a maximally oriented partially
directed acyclic graph (MPDAG) [25]. An MPDAG represents a restricted equivalence class. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[21] Meek C. p. 4 (III) If A and C are not adjacent, orient any A − B − C as A → B ← C (v-structure) if and only if
XA and XC are dependent when conditioning on XB. (IV) Orient further edges according to Meek’s rules 1-3 [21] (see Figure 12 in Appendix A. To illustrate its usefulness in practice, we apply
the algorithm to data from a children’s cohort study investigating the interplay of diet, physical
activity and other lifestyle factors for health outcomes. Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. Conflicting edges and ambiguous triples make the estimated graph difficult to interpret since it no
longer necessarily represents an equivalence class. However, they reflect the uncertainty entailed by
finite data. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[22] Colombo D, Maathuis MH. Order-independent constraint-based causal structure learning. p. 1 Detailed background can be found in Appendix A. As (constraint-based) causal discovery
reconstructs the causal structure from the pattern of conditional independencies in the data, we focus
on the relations between graphs, causal relations and conditional (in)dependencies. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[23] Ramsey J, Zhang J, Spirtes P. Adjacency-faithfulness and conservative causal inference. p. 0 To illustrate its usefulness in practice, we apply
the algorithm to data from a children’s cohort study investigating the interplay of diet, physical
activity and other lifestyle factors for health outcomes. Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. Such data driven approaches for estimating a causal DAG are known as
causal discovery (or causal search, structure learning etc. While algorithms for causal discovery were
first developed in the field of computer science more than twenty years ago [1] and have, since then,
continually been generalised and refined [2], their use with biomedical or epidemiological data is still
rare (other than in genetics [3]). the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[24] Kalisch M, M¨achler M, Colombo D, et al. Causal inference using graphical models with the R package pcalg. p. 0 To illustrate its usefulness in practice, we apply
the algorithm to data from a children’s cohort study investigating the interplay of diet, physical
activity and other lifestyle factors for health outcomes. Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. We consider an extension of the PC algorithm that exploits tiered background knowledge, and we
refer to this as the tiered PC (tPC) algorithm. Such an extension was previously suggested [1], and
versions of the tPC algorithm have been implemented in the TETRAD software [15] and R packages
[16, 17, 18], and have been applied [4, 5]. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[25] Perkovi´c E, Kalisch M, Maathuis MH. Interpreting and using CPDAGs with background knowledge. p. 8 Under any
input set of conditional independencies, the partially directed graph obtained at the end of phase (IIIa)
of the tPC algorithm is consistent with Kτ . Unlike the sample version of the naive tPC algorithm, the above states that the sample versions of
the basic tPC or tLPMC-stable algorithm are consistent with the tiered background knowledge before
using it to orient the cross-tier edges. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[26] Lauritzen SL, Wermuth N. Graphical models for associations between variables, some of which are qualitative and some quantitative. p. 0 Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. Ideally, we would like to input the data
into an algorithm that outputs one or more plausible causal directed acyclic graphs (DAGs) linking
the variables in the data. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[27] Andrews B, Ramsey J, Cooper GF. Scoring Bayesian networks of mixed variables. p. 0 Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. Ideally, we would like to input the data
into an algorithm that outputs one or more plausible causal directed acyclic graphs (DAGs) linking
the variables in the data. Such data driven approaches for estimating a causal DAG are known as
causal discovery (or causal search, structure learning etc. While algorithms for causal discovery were
first developed in the field of computer science more than twenty years ago [1] and have, since then,
continually been generalised and refined [2], their use with biomedical or epidemiological data is still
rare (other than in genetics [3]). the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[28] Spirtes P, Meek C, Richardson T. p. 4 (III) If A and C are not adjacent, orient any A − B − C as A → B ← C (v-structure) if and only if
XA and XC are dependent when conditioning on XB. (IV) Orient further edges according to Meek’s rules 1-3 [21] (see Figure 12 in Appendix A. Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. Ideally, we would like to input the data
into an algorithm that outputs one or more plausible causal directed acyclic graphs (DAGs) linking
the variables in the data. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[29] Chen Q, Malinsky D. tFCI; 2023. Available from: https://github.com/QixShawnChen/tfci<ref:2406. p. 0 the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
[30] Zhang J. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. p. 6 Edges are oriented either because they are part of a v-structure, they
are cross-tier edges, or they follow from Meek’s orientation rules. A first approach for combining background knowledge with a discovery algorithm is to impose it
post hoc onto the output. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[31] Andrews B, Spirtes P, Cooper GF. On the completeness of causal discovery in the presence of latent confounding with tiered background knowledge. p. 1 One major problem is that they can be unstable
or ambiguous with finite data due to sensitivity to sampling variation. In this paper, we describe
how temporal structure of the data, or more generally tiered background knowledge, can efficiently be
exploited to improve causal discovery algorithms, rendering the methods more stable and robust for
practical applications. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[32] Eberhardt F. Almost optimal intervention sets for causal discovery. p. 0 Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[33] Hauser A, B¨uhlmann P. Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs. p. 0 Ideally, we would like to input the data
into an algorithm that outputs one or more plausible causal directed acyclic graphs (DAGs) linking
the variables in the data. Such data driven approaches for estimating a causal DAG are known as
causal discovery (or causal search, structure learning etc. Improving Finite Sample Performance of Causal Discovery
by Exploiting Temporal Structure
Christine W. Bang1,2, Janine Witte1
, Ronja Foraita1
, and Vanessa Didelez∗1,2
1Leibniz Institute for Prevention Research and Epidemiology – BIPS
2Faculty of Mathematics and Computer Sciences, University of Bremen
June 27, 2024
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[34] Hauser A, B¨uhlmann P. Two optimal strategies for active learning of causal models from interventional data. p. 0 Ideally, we would like to input the data
into an algorithm that outputs one or more plausible causal directed acyclic graphs (DAGs) linking
the variables in the data. Such data driven approaches for estimating a causal DAG are known as
causal discovery (or causal search, structure learning etc. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[35] Squires C, Magliacane S, Greenewald K, et al. Active structure learning of causal DAGs via directed clique trees. p. 0 Ideally, we would like to input the data
into an algorithm that outputs one or more plausible causal directed acyclic graphs (DAGs) linking
the variables in the data. Such data driven approaches for estimating a causal DAG are known as
causal discovery (or causal search, structure learning etc. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[36] Fang Z, Zhao R, Liu Y, He Y. On the Representation of Causal Background Knowledge and its Applications in Causal Inference. p. 0 To illustrate its usefulness in practice, we apply
the algorithm to data from a children’s cohort study investigating the interplay of diet, physical
activity and other lifestyle factors for health outcomes. Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Where the paper says it
[37] Lauritzen SL. Graphical models. p. 0 To illustrate its usefulness in practice, we apply
the algorithm to data from a children’s cohort study investigating the interplay of diet, physical
activity and other lifestyle factors for health outcomes. Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
[38] Verma T, Pearl J. Equivalence and synthesis of causal models. p. 0 To illustrate its usefulness in practice, we apply
the algorithm to data from a children’s cohort study investigating the interplay of diet, physical
activity and other lifestyle factors for health outcomes. Keywords: causal inference, graphical models, causal graphs, cohort data, background knowledge, PC
algorithm
1 Introduction
Discovering causal structures in data is a challenging task. the DAG, to be given, usually derived from domain
∗Corresponding author: didelez@leibniz-bips. de
1
arXiv:2406.Where the paper says it
Where the paper says it
Appendix A Notation and terminology
The notation defines graphs, paths, and conditional independence concepts used throughout the paper<ref:2406.19503#pg9>. It details concepts like DAGs, Markov equivalence classes represented by CPDAGs, and the definition of a tiered ordering<ref:2406. p. 3 We refer to a class of Markov equivalent graphs as
a (Markov) equivalence class. An equivalence class of DAGs is represented by a CPDAG (a full
characterisation of CPDAGs can be found in Andersson et al.Where the paper says it
Meek’s Rules
Meek’s rules are used in phase (IV) to orient remaining undirected edges after cross-tier edges are oriented<ref:2406.19503#pg9>. These rules include Rule 1, Rule 2, Rule 3, and Rule 4<ref:2406. p. 5 Moreover, suppose that in phase (IV) A → B were oriented due to Meek’s rules. It would
then follow (by Meek’s 1st rule) that B → C.Where the paper says it
Algorithm Descriptions
The paper describes the tLMPC-stable algorithm in detail through Algorithms 1 through 5<ref:2406.19503#pg9>. Algorithm 2 describes the Skeleton phase, Algorithm 3 describes the V-structure phase (IIIa), Algorithm 4 describes the Cross-tier phase (IIIb), and Algorithm 5 describes Meek’s rules (IV)<ref:2406. p. 9 Since early errors
in the algorithm might propagate through the following steps, in particular through Meek’s rules, as
illustrated here, it is important to exploit background knowledge as early as possible and only apply
Meek’s rules at the end. Returning to the tPC algorithm as proposed here, phase (IIIb) would orient cross-tier edges and
obtain the graph in Figure 4 (d).Where the paper says it
Performance Measures
The performance measures include correct skeleton, correct v-structures, ancestral relations, and possible ancestral relations<ref:2406.19503#pg9>. Precision and recall are defined using equations (4) and (5) for adjacencies and v-structures<ref:2406. p. 2 A DAG with such a causal interpretation is referred to as a causal
DAG and will be assumed to satisfy the causal Markov property: A random variable is conditionally
independent of its non-effects given its direct causes [1]. In order to represent causal structures using DAGs, we need to make the assumption of causal
sufficiency: For each pair of nodes (variables), all their common causes are nodes in the DAG.Where the paper says it
Simulation Study Results
The simulation study compares MPDAGs constructed using τ1, τA2, τB2, τC2 or τD2, and τ5<ref:2406.19503#pg9>. The results show that the recall of adjacencies clearly improves when more detailed background knowledge is included<ref:2406. p. 1 It was previously shown that tiered
background knowledge improves the informativeness of the estimated graphs from infinite data [14]. In the present paper we specifically address finite sample properties and show how making efficient
use of tiered background knowledge increases the robustness towards statistical errors yielding more
accurate outputs. While the PC algorithm has desirable
asymptotic properties [12, 13], with finite samples it is prone to errors due to erroneous conclusions
based on statistical tests propagating through the algorithm. It was previously shown that tiered
background knowledge improves the informativeness of the estimated graphs from infinite data [14].Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Robust causal discovery for finite samples: The tPC algorithm, by exploiting tiered background knowledge, renders causal discovery algorithms
more robust to statistical errors and ultimately increases accuracy in finite samples.
This allows AI systems to produce more reliable causal graphs when working with real-world data from cohort studies or registries. -
Order independence in sample-based methods: The tLMPC-stable algorithm is formally proven to be order independent, meaning
The output of the tLMPC-stable algorithm does not depend on the sequence in which the variables are visited.
This eliminates an artificial dependency on data processing order, leading to more trustworthy results from iterative discovery algorithms. -
Enhanced conflict resolution: Incorporating tiered background knowledge prevents statistical errors by ensuring consistency throughout the algorithm, such that
the sample versions of the basic tPC or tLMPC-stable algorithm are consistent with the tiered background knowledge before using it to orient the cross-tier edges.
This capability allows AI systems to resolve conflicts arising from noisy data more accurately, potentially leading to alarger equivalence class
than methods without background knowledge. -
Improved edge recall and precision: The simulation study demonstrated that
exploiting tiered background knowledge offers a higher edge recall at almost no cost of precision,
suggesting that the system can recover more true adjacencies with only a small increase in false positives, which is beneficial when estimating the skeleton. -
Accurate ancestral relation recovery: The integration of tiered background knowledge leads to an
overall increase in precision as well as recall of (possible) ancestral relations,
enabling AI systems to draw more confident conclusions about indirect causal paths within the data structure.
Abstract
Methods of causal discovery aim to identify causal structures in a data driven way. Existing algorithms are known to be unstable and sensitive to statistical errors, and are therefore rarely used with biomedical or epidemiological data. We present an algorithm that efficiently exploits temporal structure, so-called tiered background knowledge, for estimating causal structures. Tiered background knowledge is readily available from, e.g., cohort or registry data. When used efficiently it renders the algorithm more robust to statistical errors and ultimately increases accuracy in finite samples. We describe the algorithm and illustrate how it proceeds. Moreover, we offer formal proofs as well as examples of desirable properties of the algorithm, which we demonstrate empirically in an extensive simulation study. To illustrate its usefulness in practice, we apply the algorithm to data from a children's cohort study investigating the interplay of diet, physical activity and other lifestyle factors for health outcomes.
Related papers
- Learning Robust Treatment Rules for Censored Data
- Neural Estimation of Summary Statistics for Simulation-Based Inference with Non-Asymptotic Guarantees
- Spectral divide-and-conquer MCMC for long stationary time series
- Improving the Efficiency of Subgroup Analysis in Randomized Controlled Trials with TMLE
- Personalized Federated Vector Autoregression with Personalization Diversity
- Doubly Robust and Efficient Calibration of Prediction Sets for Right-Censored Time-to-Event Outcomes