Score-Based Causal Discovery with Temporal Background Information Tobias E. Larsen, Claus T. Ekstrøm, Anne H. Petersen Abstract Temporal background information can improve causal discovery algorithms by orienting edges and identifying relevant adjustment sets. We develop the Temporal Greedy Equivalence Search (TGES) algorithm and terminology essential for score-based causal discovery with tiered background knowledge. TGES learns a restricted Markov equivalence class of directed acyclic graphs (DAGs) using observational data and tiered background knowledge. To construct TGES we formulate a scoring criterion that accounts for tiered background knowledge. We establish theoretical results for TGES, stating that the algorithm always returns a tiered maximally oriented partially directed acyclic graph (tiered MPDAG) and that this tiered MPDAG contains the true DAG in the large sample limit. We present a simulation study indicating a gain from using tiered background knowledge and an improved precision-recall trade-off compared to the temporal PC algorithm. We provide a real-world example on life-course health data. 1]Section of Biostatistics, Department of Public Health University of Copenhagen Copenhagen, Denmark 1 Introduction When aiming to estimate the causal effect of an exposure using observational data, studies will make use of knowledge of the causal structure of the data. This structure will be represented as a Directed Acyclic Graph (DAG) [ Hernan and Robins, 2024 ] , where the variables are illustrated as nodes and direct causal effects are depicted as edges. In practice, studies often rely on the knowledge of field experts in order to construct a DAG. However, former work shows that there will not always be consensus of causal relationships among experts, hence researchers might be interested in using causal discovery as a data-driven alternative or complement [ Petersen et al., 2023a ] . Causal discovery seeks to estimate a causal network using empirical data. There exist two overall branches of causal discovery: constraint-based algorithms and score-based algorithms. A canonical algorithm in the constraint-based branch is the Peter Clark (PC) algorithm [ Spirtes and Glymour, 1991 ] , which uses conditional independence testing to rule out causal links. For the score-based algorithms, a seminal algorithm would be the Greedy Equivalence Search (GES) algorithm [ Chickering, 2003 ] , which scores graphs on their ability to fit the observed data. It has been proposed to utilize the temporal information embedded in longitudinal data to improve the estimation of the causal network, as we can rule out any causal effect going backward in time [ Petersen et al., 2021 ] . Several implementations are available for a temporal extension of the PC algorithm (TPC) [ Petersen, 2022 , Witte, 2023 ] . However, the PC algorithm is known to disproportionally favor high precision of the graph [ Petersen et al., 2023b ] , which could be an issue for subsequent causal inference, since a sparser graph imposes more constraints on the distribution and hence is more liable to introduce bias when the graph is incorrectly identified [ Malinsky, 2024 ] . GES is known to have a more balanced precision-recall trade-off [ Ramsey and Andrews, 2017 ] , which makes it an attractive alternative to PC. We have developed a temporal extension of the GES algorithm, which we call Temporal Greedy Equivalence Search (TGES), that inherits the desirable theoretical properties of GES, and proves to be a viable alternative to the temporal extension of PC. We present TGES and show that it is sound and complete in the limit of large sample sizes. Furthermore, we investigate the performance of TGES in finite samples. The paper is structured as follows. After introducing preliminary graph notation and assumptions in Section 2 , we present Greedy Equivalence Search (GES) in Section 3 . In Section 4 we define tiered background knowledge. In Section 5 we define a naive extension to GES which incorporates tiered background knowledge called Simple Temporal Greedy Equivalence Search (STGES). Furthermore, we introduce the main contribution, the Temporal Greedy Equivalence Search (TGES) algorithm, and show that it is sound and complete. In Section 6 we conduct a simulation study which compares TGES to the performance of GES, STGES, and TPC. TGES is here shown to have considerably better recall than TPC while maintaining a precision that is on par. We showcase TGES using a real-world data example in Section 7 , and conclude with a discussion in Section 8 . 2 Background and Notation Throughout the article we assume familiarity with the concepts of Directed Acyclic Graph (DAG), Partially Directed Acyclic Graph (PDAG), Complete Partially Directed Acyclic Graph (CPDAG), d-separation , faithfulness , Markov equivalence class and the Markov property (also known as the causal Markov assumption) [ Peters et al., 2017 ] ,. We denote a graph \mathcal{G} as a set of nodes \mathbf{V} and edges \mathbf{E} , such that \mathcal{G}=(\mathbf{V},\mathbf{E}) . A Markov equivalence class is denoted as \mathcal{E} . In this article, we assume there to be a data set consisting of d random variables \mathbf{X}=(X_{1},...,X_{d}) . The data set \mathbf{D} is assumed to be an observed sample of n i.i.d. observations of \mathbf{X} . We assume what is commonly referred to as causal sufficiency , namely that there are no unobserved confounders. We also assume no unobserved selection. We assume that the variables are realizations of a multivariate Gaussian distribution according to a DAG and parameters \theta . This DAG will be referred to as the true data-generating DAG or the underlying data-generating DAG and the true distribution is assumed Markov and faithful with respect to this DAG. The distribution of the underlying data-generating DAG \mathcal{G} will be denoted as p and the density as p(\mathbf{D}|\theta,\mathcal{G}) . Parents, children, ancestors, descendants, and non-descendants of a node X in \mathcal{G} we denote as \text{Pa}_{X}^{\mathcal{G}},\text{Ch}_{X}^{\mathcal{G}},\text{An}_{X}^{\mathcal{G}},\text{De}_{X}^{\mathcal{G}} , \text{NDe}_{X}^{\mathcal{G}} respectively, where X\in\text{De}_{X}^{\mathcal{G}} and X\notin\text{An}_{X}^{\mathcal{G}} . Whenever we compare two graphs, it is assumed that they are defined on the same set of nodes. We will consider PDAGs obtained by restricting a CPDAG according to background information, then [ Meek, 1995 ] has provided 4 orientation rules which together ensure that no more edges can be oriented in a PDAG. These rules are referred to as Meek’s rules and are given in Appendix B.1 . The graph that results from applying the rules is a maximally oriented partially directed acyclic graph (MPDAG) [ Perkovic et al., 2017 ] . The rules orient edges to prevent cycles and to maintain conditional independence statements. 3 Greedy Equivalence Search A score-based algorithm estimates a graph by comparing different graph structures’ ability to fit the data. The idea is that graphs embedding wrong conditional independencies will fit the data poorly. Provided a scoring criterion S(\mathcal{G},\mathbf{D}) , the simplest score-based algorithm is the Best Scoring Graph [ Peters et al., 2017 ] . Here, we score every graph \mathcal{G} over the nodes \mathbf{X} and choose the graph that yields the maximum score as our estimate, \hat{\mathcal{G}}=\argmax_{\mathcal{G}\text{ over }\mathbf{X}}S(\mathcal{G},\mathbf{D}) The number of DAGs to score for the Best Scoring Graph procedure, grows super-exponentially with the number of nodes, and the algorithm thus quickly becomes computationally infeasible [ OEIS Foundation Inc., 2023 ] . Instead of scoring every possible DAG to obtain an estimate, we can use the Greedy Equivalence Search (GES) [ Chickering, 2003 ] . GES starts with an empty graph and greedily adds edges to improve the score of the graph. The adding of edges is the first of two phases in GES and is referred to as the forward phase. After the forward phase, GES optimizes the score by greedily removing edges, which is referred to as the backward phase. An equivalence class \mathcal{E}^{\prime} is contained in the forward (backward) neighboring equivalence class of \mathcal{E} if and only if there exists a \mathcal{G}\in\mathcal{E} and a \mathcal{G}^{\prime}\in\mathcal{E}^{\prime} such that \mathcal{G} becomes \mathcal{G}^{\prime} by one single directed edge addition (removal). Each step in the phases of GES substitutes for a neighboring equivalence class if it has a higher score. If multiple neighboring equivalence classes have a higher score, then the one with the highest score is chosen. There are several extensions to GES, such as a third turning phase which seeks to reverse edges to improve the estimations on finite samples [ Hauser and Bühlmann, 2012 ] , or a Fast GES which is more feasible to use on high dimensional graphs [ Ramsey et al., 2017 ] . 3.1 Bayesian Information Criterion The Bayesian Information Criterion (BIC) [ Schwarz, 1978 ] is often used as the scoring criterion, and we denote it S_{B} and define it as \displaystyle S_{B}(\mathcal{G},\mathbf{D})=\log p(\mathbf{D}|\hat{\theta},\mathcal{G})-\frac{\#\text{parameters}}{2}\log n where \hat{\theta} is the maximum likelihood estimate. In this formulation, larger BIC means better model fit. The BIC holds several desirable properties such as being decomposable , which means we can rewrite the score as a sum of local scores of each node given the parents of the node [ Chickering, 2003 ] . When computing the difference in scores between two graphs, decomposability allows us to only compute the difference in the local scores of the nodes that differ in parent sets. Furthermore, the BIC is a consistent scoring criterion for Gaussian data [ Haughton, 1988 ] . Consistent scoring criteria disfavors graphs with independence statements not in the true distribution and graphs with too many edges. The BIC is a locally consistent scoring criterion as well, which means the score increases as a result of adding an edge that eliminates an independence constraint not in p and decreases as a result of adding an edge that does not eliminate such a constraint. BIC scores every DAG in the same Markov equivalence class the same, this property is referred to as score equivalence and gives sense to the notation S_{B}(\mathcal{E},\mathbf{D}) , even though we in practice will score a single \mathcal{G}\in\mathcal{E} [ Chickering, 2003 ] . GES requires a score equivalent, decomposable, consistent, and locally consistent score criterion (Formal definitions of these are provided in Appendix B.2 ), such as the BIC. These properties enable an efficient search space and that GES in the limit of large sample size correctly estimates the Markov equivalence class of the true data-generating DAG [ Chickering, 2003 ] . The results from Chickering [2003] (Lemmas 9,10 and Theorems 15, 17) are reproduced below: Theorem 1 . (Sound and Completeness of GES) GES using a score equivalent, decomposable, consistent and locally consistent score criterion, results in a CPDAG, and for n\rightarrow\infty the CPDAG is almost surely a sound and complete estimate of the Markov equivalence class of the true data-generating DAG. 4 Tiered Background Knowledge In this section, we give a formal introduction to what we have earlier called temporal information and describe how it can be used in causal discovery. We call it tiered background knowledge , as it is not restricted to information induced from time, although this is the main use case. We start out by defining background knowledge \mathcal{K}=(\mathcal{R},\mathcal{F}) as a set of required edges \mathcal{R} and forbidden edges \mathcal{F} . We say that a DAG \mathcal{G}=(\mathbf{V},\mathbf{E}) encodes the background knowledge \mathcal{K} if \mathcal{R}\subseteq\mathbf{E} and \mathcal{F}\cap\mathbf{E}=\emptyset . If a graph \mathcal{G} does not encode \mathcal{K} , we say that \mathcal{G} contradicts \mathcal{K} . We say a CPDAG/equivalence class \mathcal{E} is in agreement with background knowledge \mathcal{K} if there exists a \mathcal{G}\in\mathcal{E} that encodes \mathcal{K} . Analogously, a PDAG is in agreement with \mathcal{K} if the class of DAGs the PDAG represents contains a DAG that encodes \mathcal{K} . We say that a distribution encodes \mathcal{K} when the underlying data-generating DAG of the distribution encodes \mathcal{K} . We assume throughout that the background knowledge is encoded by the true distribution p . Before defining tiered background knowledge we give the definition of a tiered ordering . Definition 1 . (Tiered ordering, Bang and Didelez [2023] ) Let \mathcal{G} be a PDAG with node set \mathbf{V} of size d , and let T\in\mathbb{N},T\leq d . A tiered ordering of the nodes in \mathbf{V} is a map \tau:\mathbf{V}\mapsto\{1,...,T\}^{d} that assigns each node V\in\mathbf{V} to a unique tier t\in\{1,...,T\} . Definition 2 . (Tiered background knowledge, Bang and Didelez [2023] ) Given a tiered ordering \tau we define tiered background knowledge as \mathcal{K}_{\tau}=(\mathcal{R},\mathcal{F}) where \mathcal{R}=\emptyset and \mathcal{F} is the set of forbidden directed edges \{A\rightarrow B\} such that \tau(A)>\tau(B) . Graphs that encode the tiered background knowledge are made up of two types of edges: An edge \{A\rightarrow B\} is a cross-tier edge if \tau(A)<\tau(B) and an in-tier edge if \tau(A)=\tau(B) . Algorithm 1 Restrict PDAG according to \mathcal{K}_{\tau} [ Perkovic et al., 2017 ] 1: Input: \mathcal{K}_{\tau}=(\mathcal{R},\mathcal{F}) and PDAG \mathcal{W}=(\mathbf{V},\mathbf{E}) in agreement with \mathcal{K}_{\tau} 2: \mathbf{E}^{\prime}\leftarrow\mathbf{E} 3: for \left\{A\text{ --- }B\right\}\in\mathbf{E} do 4: if \left\{A\rightarrow B\right\}\in\mathcal{F} then 5: Replace \left\{A\text{ --- }B\right\} with \left\{A\rightarrow B\right\} in \mathbf{E}^{\prime} 6: end if 7: end for 8: Output: PDAG \mathcal{W^{\prime}}=(\mathbf{V},\mathbf{E}^{\prime}) If a CPDAG is in agreement with \mathcal{K}_{\tau} , we can restrict it according to \mathcal{K}_{\tau} (Algorithm 1 ) and obtain the resulting PDAG. This enables the orientation of additional undirected edges by Meek’s rules [ Meek, 1995 ] . By Bang and Didelez [2023] , the graph resulting from applying only Meek’s rule 1 until no further change is a tiered MPDAG , which no longer represents a Markov equivalence class, but instead a restricted equivalence class which we will denote \mathcal{E}^{\mathcal{K}_{\tau}} . Tiered background knowledge does not affect the existence or absence of adjacencies. It only affects directions, and only where there exists an adjacency between nodes in two different tiers (cross-tier). This may indirectly affect in-tier edge orientations as well (via Meek’s rule 1). 5 The Temporal Greedy Equivalence Search Algorithm In this section we first present a naive temporal modification of GES, then introduce a new score criterion that incorporates tiered background knowledge, and following this propose a more advanced temporal extension of GES. We prove that both are sound and complete. 5.1 Simple Temporal Greedy Equivalence Search The algorithm Simple Temporal Greedy Equivalence Search (STGES) is a naive modification of GES utilizing tiered background knowledge \mathcal{K}_{\tau} . First STGES runs GES to completion without taking \mathcal{K}_{\tau} into account to obtain a CPDAG. This CPDAG may not, due to statistical error, be in agreement with \mathcal{K}_{\tau} . STGES then removes all directed edges contradicting \mathcal{K}_{\tau} to obtain a PDAG that is in agreement with \mathcal{K}_{\tau} . Afterward, STGES restricts undirected edges according to \mathcal{K}_{\tau} using Algorithm 1 and then uses Meek’s rules 1-4 [ Meek, 1995 ] to orient additional edges. This is a post-hoc background knowledge approach following ideas presented by Perkovic et al. [2017] . The STGES algorithm is illustrated and pseudo code is provided in Appendix A . In the large sample limit, STGES is sound and complete: Theorem 2 . (Sound and Completeness of STGES) For n\rightarrow\infty STGES almost surely results in a CPDAG which is a sound and complete estimate of the Markov equivalence class of the true data-generating DAG. The proof of Theorem 2 is provided in Appendix B.3 . When using tiered background knowledge, we will often have very high trust in the validity of the information, for example, if this information is temporal. A post-hoc method such as STGES, will not reflect this, as the first part of the algorithm will completely disregard \mathcal{K}_{\tau} . Therefore, we propose an alternative algorithm that utilizes \mathcal{K}_{\tau} earlier on, we call this Temporal Greedy Equivalence Search (TGES). 5.2 Temporal Greedy Equivalence Search We require the score criterion in TGES to have certain properties. Like for GES, we require decomposability but will extend consistency, local consistency, and score equivalence to \mathcal{K}_{\tau} -consistency, local \mathcal{K}_{\tau} -consistency and \mathcal{K}_{\tau} -score equivalence respectively. The definition of \mathcal{K}_{\tau} -consistency is given in Appendix B.4 , since combining decomposability and \mathcal{K}_{\tau} -consistency leads to the more interpretable property of local \mathcal{K}_{\tau} -consistency . We denote independence and dependence in the distribution p as \perp\!\!\!\perp_{p} and \not\!\perp\!\!\!\perp_{p} , respectively. Definition 3 . (Local \mathcal{K}_{\tau} -Consistency) Let \mathcal{G} be any DAG that encodes \mathcal{K}_{\tau} , and let \mathcal{G}^{\prime} be the DAG that results from adding the edge \left\{X\rightarrow Y\right\} to \mathcal{G} . A scoring criterion S is \mathcal{K}_{\tau} -locally consistent if the following holds: i. If \tau(X)\leq\tau(Y) and Y\not\!\perp\!\!\!\perp_{p}X\mid\text{Pa}_{Y}^{\mathcal{G}} , then as n\rightarrow\infty S(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau})>S(\mathcal{G},\mathbf{D},\mathcal{K}_{\tau}) almost surely. ii. If \tau(X)\leq\tau(Y) and Y\perp\!\!\!\perp_{p}X\mid\text{Pa}_{Y}^{\mathcal{G}} , then as n\rightarrow\infty S(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau})\tau(Y) , then S(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau})0 then 7: (X^{\prime},Y^{\prime})\leftarrow\underset{(X,Y)}{\argmax}\left(\Delta s_{X,Y}\right) 8: Insert edge \left\{Y^{\prime}\rightarrow X^{\prime}\right\} in \mathcal{W} 9: \mathcal{W}\leftarrow CPDAG of \mathcal{W} 10: else 11: Output \mathcal{W} with no changes made 12: end if 13: Stage (ii): 14: \mathcal{W}\leftarrow Use Algorithm 1 on \mathcal{W} 15: Stage (iii): 16: \mathcal{W}\leftarrow Iterate over Meek’s rule 1 on \mathcal{W} 17: Output: \mathcal{W} Algorithm 5 Temporal_Backward_Step 1: Input: \mathcal{W},\mathbf{D},\mathcal{K}_{\tau} 2: Stage (i): 3: for all pair of nodes (X,Y) in \mathcal{W} where edge removal is valid do 4: \Delta s_{X,Y}\leftarrow s(X_{i},Pa^{\mathcal{W}}_{i}\setminus Y,\mathcal{K}_{\tau})-s(X_{i},Pa^{\mathcal{W}}_{i},\mathcal{K}_{\tau}) 5: end for 6: if any \Delta s_{X,Y}>0 then 7: (X^{\prime},Y^{\prime})\leftarrow\underset{(X,Y)}{\argmax}\left(\Delta s_{X,Y}\right) 8: Remove edge \left\{Y^{\prime}\rightarrow X^{\prime}\right\} in \mathcal{W} 9: \mathcal{W}\leftarrow CPDAG of \mathcal{W} 10: else 11: Output \mathcal{W} with no changes made 12: end if 13: Stage (ii): 14: \mathcal{W}\leftarrow Use Algorithm 1 on \mathcal{W} 15: Stage (iii): 16: \mathcal{W}\leftarrow Iterate over Meek’s rule 1 on \mathcal{W} 17: Output: \mathcal{W} Algorithm 6 Temporal_Turning_Step 1: Input: \mathcal{W},\mathbf{D},\mathcal{K}_{\tau} 2: Stage (i): 3: for all directed edges \left\{X\rightarrow Y\right\} in \mathcal{W} do 4: \Delta s_{X,Y}\leftarrow s(X_{i},Pa^{\mathcal{W}}_{X_{i}}\setminus Y,\mathcal{K}_{\tau})-s(X_{i},Pa^{\mathcal{W}}_{X_{i}},\mathcal{K}_{\tau})+s(Y_{i},Pa^{\mathcal{W}}_{Y_{i}}\cup X,\mathcal{K}_{\tau})-s(Y_{i},Pa^{\mathcal{W}}_{Y_{i}},\mathcal{K}_{\tau}) 5: end for 6: if any \Delta s_{X,Y}>0 then 7: (X^{\prime},Y^{\prime})\leftarrow\underset{(X,Y)}{\argmax}\left(\Delta s_{X,Y}\right) 8: Reverse edge \left\{X^{\prime}\rightarrow Y^{\prime}\right\} to \left\{Y^{\prime}\rightarrow X^{\prime}\right\} in \mathcal{W} 9: \mathcal{W}\leftarrow CPDAG of \mathcal{W} 10: else 11: Output \mathcal{W} with no changes made 12: end if 13: Stage (ii): 14: \mathcal{W}\leftarrow Use Algorithm 1 on \mathcal{W} 15: Stage (iii): 16: \mathcal{W}\leftarrow Iterate over Meek’s rule 1 on \mathcal{W} 17: Output: \mathcal{W} Appendix B Proofs and Definitions B.1 Meek’s Rules A B C \Rightarrow Rule 1 A B C A B C \Rightarrow Rule 2 A B C A B D C \Rightarrow Rule 3 A B D C A B D C \Rightarrow Rule 4 A B D C * * * * Figure 5: Representations of Meek’s rules 1-4 [ Meek, 1995 ] . A dashed edge is inferred by the rule. The symbol * is used to denote that the edge between B and C could either be \{B\rightarrow C\} , \{B\leftarrow C\} or \{B\text{ --- }C\} . B.2 Bayesian Information Criterion Definition 6 . (Decomposable score) A score criterion S is decomposable if we can write it as a sum of local scores of the nodes given the parents of the nodes \displaystyle S(\mathcal{G},\mathbf{D})=\sum^{d}_{i=1}s(X_{i},Pa^{\mathcal{G}}_{i}), (1) where s denotes the local score function, X_{i} is a node in \mathcal{G} , \text{Pa}_{i}^{\mathcal{G}} are the parents of X_{i} in \mathcal{G} . We have that local BIC, denoted s_{B} , is given as \displaystyle S_{B}(\mathcal{G},\mathbf{D})=\sum^{d}_{i=1}s_{B}(X_{i},Pa^{\mathcal{G}}_{i})=\sum^{d}_{i=1}\log p(\mathbf{D}_{i}|\hat{\theta},\mathcal{G})-\frac{\#\text{parameters}}{2}\log m\text{,} (2) where \mathbf{D}_{i} is the data of the nodes X_{i} and Pa^{\mathcal{G}}_{i} . p(\mathbf{D}_{i}|\hat{\theta},\mathcal{G}) is the likelihood of the local model defined on X_{i} and Pa^{\mathcal{G}}_{i} and \#\text{parameters} is the number of parameters in this local model. In the Gaussian case \#\text{parameters}=\#\text{edges} . We will denote d-separation in a DAG \mathcal{G} as \perp\!\!\!\perp_{\mathcal{G}} , and no d-separation in DAG \mathcal{G} as \not\!\perp\!\!\!\perp_{\mathcal{G}} . Next, we introduce some graph notation from Chickering [2003] concentrating on independence statements: Let \mathcal{G} and \mathcal{H} be two DAGs defined on the same set of nodes \mathbf{V} . We write \mathcal{G}\leq\mathcal{H} when every independence relationship in \mathcal{H} holds in \mathcal{G} : For all disjoint node sets \mathbf{A},\mathbf{B},\mathbf{C}\subseteq\mathbf{V} \displaystyle\mathbf{A}\perp\!\!\!\perp_{\mathcal{H}}\mathbf{B}|\mathbf{C}\Rightarrow\mathbf{A}\perp\!\!\!\perp_{\mathcal{G}}\mathbf{B}|\mathbf{C} The notation \leq is motivated as follows: if \mathcal{G}\leq\mathcal{H} then \mathcal{G} has fewer edges than \mathcal{H} . If there exists an independence statement in \mathcal{H} which is not in \mathcal{G} , we write \mathcal{G}\not\leq\mathcal{H} . If we have that \mathcal{G}\leq\mathcal{H} and \mathcal{H}\leq\mathcal{G} then we write \mathcal{G}\approx\mathcal{H} . If \mathcal{G}\approx\mathcal{H} then the two DAGs are Markov equivalent and hence belong to the same Markov equivalence class. In particular, if \mathcal{G}\approx\mathcal{H} and they both encode the same tiered background knowledge \mathcal{K}_{\tau} they belong to the same restricted equivalence class. Definition 7 . (Consistent Scoring Criterion) Let \mathcal{G}^{*} be the data-generating DAG from which the data \mathbf{D} were generated and n be the number of observations. A scoring criterion S is consistent if for n\rightarrow\infty , the following two properties hold almost surely: i. If \mathcal{G}^{*}\leq\mathcal{G}^{\prime} and \mathcal{G}^{*}\not\leq\mathcal{G} , then S(\mathcal{G}^{\prime},\mathbf{D})>S(\mathcal{G},\mathbf{D}) . ii. If \mathcal{G}^{*}\leq\mathcal{G} , \mathcal{G}^{*}\leq\mathcal{G}^{\prime} , and \mathcal{G}^{\prime} has fewer edges than \mathcal{G} , then S(\mathcal{G}^{\prime},\mathbf{D})>S(\mathcal{G},\mathbf{D}) . Definition 8 . (Locally Consistent Scoring Criterion) Let \mathbf{D} be a data set consisting of n records that are i.i.d. samples from some distribution p . Let \mathcal{G} be any DAG with no edge \left\{X\rightarrow Y\right\} , and let \mathcal{G}^{\prime} be the DAG that results from adding the edge \left\{X\rightarrow Y\right\} to \mathcal{G} . A scoring criterion S(\mathcal{G},\mathbf{D}) is locally consistent if as n\rightarrow\infty , the following two properties hold almost surely: i. If Y\not\!\perp\!\!\!\perp_{p}X|Pa^{\mathcal{G}}_{Y} , then S(\mathcal{G}^{\prime},\mathbf{D})>S(\mathcal{G},\mathbf{D}) . ii. If Y\perp\!\!\!\perp_{p}X|Pa^{\mathcal{G}}_{Y} , then S(\mathcal{G}^{\prime},\mathbf{D})\tau(B) , which is equivalent to stating that there exist an X_{q}\in\mathbf{V} with a parent A\in Pa^{\mathcal{G}}_{q} such that \tau(A)>\tau(X_{q}) . Thus we have for X_{q} that s_{\tau}(X_{q},Pa^{\mathcal{G}}_{q},\mathcal{K}_{\tau})=-\infty . Then, \displaystyle\sum^{d}_{i=1}s_{\tau}(X_{i},Pa^{\mathcal{G}}_{i},\mathcal{K}_{\tau})=\sum^{q-1}_{i=1}s_{\tau}(i)+\sum^{d}_{i=q+1}s_{\tau}(i)+s_{\tau}(X_{q},Pa^{\mathcal{G}}_{q},\mathcal{K}_{\tau}) \displaystyle= \displaystyle\sum^{q-1}_{i=1}s_{\tau}(i)+\sum^{d}_{i=q+1}s_{\tau}(i)-\infty\overset{\dagger}{=}-\infty=S_{\tau}(\mathcal{G},\mathbf{D},\mathcal{K}_{\tau})\text{,} where we shortened s_{\tau}(X_{i},Pa^{\mathcal{G}}_{i},\mathcal{K}_{\tau}) as s_{\tau}(i) for easier notation. \dagger is true since all s_{\tau}(X_{i},Pa^{\mathcal{G}}_{i},\mathcal{K}_{\tau})<\infty . ∎ Definition 10 . ( \mathcal{K}_{\tau} -Consistency) Let \mathcal{G}^{*} be the DAG from which the data \mathbf{D} were generated, n be the number of observations, and \mathcal{K}_{\tau} tiered background knowledge. A scoring criterion S is \mathcal{K}_{\tau} -consistent if the following all hold: i. If \mathcal{G}^{\prime} , \mathcal{G} both encode \mathcal{K}_{\tau} and we have that \mathcal{G}^{*}\leq\mathcal{G}^{\prime} and \mathcal{G}^{*}\not\leq\mathcal{G} , then for n\rightarrow\infty S(\mathcal{G}^{\prime},\mathbf{D})>S(\mathcal{G},\mathbf{D}) almost surely. ii. If \mathcal{G}^{\prime} , \mathcal{G} both encode \mathcal{K}_{\tau} , \mathcal{G}^{*}\leq\mathcal{G} , \mathcal{G}^{*}\leq\mathcal{G}^{\prime} , and \mathcal{G}^{\prime} has fewer edges than \mathcal{G} , then for n\rightarrow\infty S(\mathcal{G}^{\prime},\mathbf{D})>S(\mathcal{G},\mathbf{D}) almost surely. iii. If \mathcal{G}^{\prime} encodes \mathcal{K}_{\tau} and \mathcal{G} contradicts \mathcal{K}_{\tau} then S(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau})>S(\mathcal{G},\mathbf{D},\mathcal{K}_{\tau}) . Proposition 4 . TBIC is a \mathcal{K}_{\tau} -consistent scoring criterion Proof. (i) & (ii) : If \mathcal{G} and \mathcal{G}^{\prime} encode the tiered background knowledge \mathcal{K}_{\tau} then the scoring criterion TBIC is equal to the scoring criterion BIC which by Proposition 2 has property (i) and (ii) . (iii) : Assume \mathcal{G}^{\prime} encodes \mathcal{K}_{\tau} and \mathcal{G} contradicts \mathcal{K}_{\tau} . Then the property follows from the fact that S_{\tau}(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau})=S_{B}(\mathcal{G}^{\prime},\mathbf{D})>-\infty and S_{\tau}(\mathcal{G},\mathbf{D},\mathcal{K}_{\tau})=-\infty . ∎ Proposition 5 . A \mathcal{K}_{\tau} -consistent and decomposable scoring criterion is a locally \mathcal{K}_{\tau} -consistent scoring criterion. Proof. Let \mathcal{G} be any DAG that encodes \mathcal{K}_{\tau} and where adding the edge \left\{X\rightarrow Y\right\} to \mathcal{G} results in a DAG \mathcal{G}^{\prime} . It must then be that X\in\text{NDe}^{\mathcal{G}}_{Y} since adding the edge \left\{X\rightarrow Y\right\} results in a DAG and therefore no cycle. Hence, Y\perp\!\!\!\perp_{\mathcal{G}}X|\text{Pa}^{\mathcal{G}}_{Y} . Assume S is a decomposable and \mathcal{K}_{\tau} -consistent score criterion. We show that each of the properties (i)-(iii) for a locally \mathcal{K}_{\tau} -consistent score criterion is held by S . (i) & (ii) : Assume \tau(X)\leq\tau(Y) . By decomposability of the score criterion, the increase in score that results from adding \left\{X\rightarrow Y\right\} to \mathcal{G} is the same increase in score that results from adding \left\{X\rightarrow Y\right\} to any other DAG \mathcal{H} where \text{Pa}_{Y}^{\mathcal{H}}=\text{Pa}^{\mathcal{G}}_{Y} . Choose \mathcal{H} as a DAG where \text{Pa}_{Y}^{\mathcal{H}}=\text{Pa}^{\mathcal{G}}_{Y} and where adding \left\{X\rightarrow Y\right\} results in a completely connected DAG \mathcal{H}^{\prime} that encodes \mathcal{K}_{\tau} . Then \mathcal{H} will by default also encode \mathcal{K}_{\tau} . Since \mathcal{H}^{\prime} is fully connected, we have that \mathcal{G}^{*}\leq\mathcal{H}^{\prime} . We now continue the proof for (i) and (ii) separately. (i) : Assume Y\not\!\perp\!\!\!\perp_{p}X|Pa^{\mathcal{G}}_{Y} , then Y\not\!\perp\!\!\!\perp_{p}X|Pa^{\mathcal{H}}_{Y} since \text{Pa}_{Y}^{\mathcal{H}}=\text{Pa}^{\mathcal{G}}_{Y} . Since the data-generating DAG is Markov and faithful to the true distribution p , we have that Y\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}X|Pa^{\mathcal{H}}_{Y} . From this, we have that there exists an independence statement in \mathcal{H} which is not in \mathcal{G}^{*} and therefore \mathcal{G}^{*}\not\leq\mathcal{H} . By \mathcal{K}_{\tau} -consistency ( (i) in Def. 10 ) we have that S(\mathcal{H},\mathbf{D},\mathcal{K}_{\tau})S(\mathcal{H}^{\prime},\mathbf{D},\mathcal{K}_{\tau}) which implies that S(\mathcal{G},\mathbf{D},\mathcal{K}_{\tau})>S(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau}) . (iii) : Assume \tau(X)>\tau(Y) . Then \mathcal{G}^{\prime} contradicts \mathcal{K}_{\tau} , and by \mathcal{K}_{\tau} -consistency ( (iii) in Def. 10 ) we have that S(\mathcal{G},\mathbf{D},\mathcal{K}_{\tau})>S(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau}) . ∎ Proposition 6 . TBIC is a locally \mathcal{K}_{\tau} -consistent scoring criterion. Proof. TBIC is \mathcal{K}_{\tau} -consistent and decomposable by Proposition 3 and Proposition 4 . It then follows from Proposition 5 that TBIC is a locally \mathcal{K}_{\tau} -consistent scoring criterion. ∎ Proposition 7 . (TBIC is \mathcal{K}_{\tau} -score equivalent) For any DAGs \mathcal{G},\mathcal{G}^{\prime}\in\mathcal{E}^{\mathcal{K}_{\tau}} , we have that the TBIC scores are identical S_{\tau}(\mathcal{G},\mathbf{D},\mathcal{K}_{\tau})=S_{\tau}(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau}) . Proof. Both \mathcal{G} and \mathcal{G}^{\prime} encode \mathcal{K}_{\tau} hence S_{\tau}(\mathcal{G},\mathbf{D},\mathcal{K}_{\tau})=S_{B}(\mathcal{G},\mathbf{D}) and S_{\tau}(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau})=S_{B}(\mathcal{G}^{\prime},\mathbf{D}) by definition. We have that the corresponding equivalence class \mathcal{E} to the restrictive equivalence class \mathcal{E}^{\mathcal{K}_{\tau}} contains \mathcal{G},\mathcal{G}^{\prime}\in\mathcal{E} . We have by the score equivalence of BIC (Proposition 2 ) that S_{B}(\mathcal{G},\mathbf{D})=S_{B}(\mathcal{G}^{\prime},\mathbf{D}) . ∎ B.5 Proof of Lemma 1 We start out with restating the Lemma we wish to prove: Lemma 1 . TGES results in a tiered MPDAG. First, we prove the following lemmas: Lemma 2 . Let S be a \mathcal{K}_{\tau} -consistent, \mathcal{K}_{\tau} -score equivalent and decomposable scoring criterion. Then stage (i) in TGES using S applied to a restricted equivalence class \mathcal{E}^{\mathcal{K}_{\tau}} will terminate in a CPDAG that is in agreement with the tiered background knowledge \mathcal{K}_{\tau} . Proof. Let \mathcal{E}^{\mathcal{K}_{\tau}} be a restricted equivalence class that encodes \mathcal{K}_{\tau} , and S a \mathcal{K}_{\tau} -consistent scoring criterion. We have that all DAGs \mathcal{G}\in\mathcal{E}^{\mathcal{K}_{\tau}} encode the tiered background knowledge. Let \mathcal{E}^{\prime} be the equivalence class that results from stage (i) given \mathcal{E}^{\mathcal{K}_{\tau}} . Assume for contradiction that the equivalence class \mathcal{E}^{\prime} is not in agreement with \mathcal{K}_{\tau} . This implies that all DAGs \mathcal{G}^{\prime}\in\mathcal{E}^{\prime} contradict \mathcal{K}_{\tau} . By \mathcal{K}_{\tau} -consistency ( (iii) in Def. 10 ) we have that S(\mathcal{G}^{*},\mathbf{D},\mathcal{K}_{\tau})>S(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau}) . But since GES is greedy and S(\mathcal{G}^{*},\mathbf{D},\mathcal{K}_{\tau})>S(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau}) there is a contradiction, and hence it must be that \mathcal{E}^{\prime} is in agreement with \mathcal{K}_{\tau} . ∎ Lemma 3 . Each step in TGES results in a tiered MPDAG Proof. TGES commences with an empty graph which by default is a tiered MPDAG for any tiered background knowledge \mathcal{K}_{\tau} . Assuming we start with a tiered MPDAG, we prove that stage (i)-(iii) results in a tiered MPDAG. By Lemma 2 Stage (i) results in a CPDAG in agreement with \mathcal{K}_{\tau} . Stage (ii) restricts the CPDAG according to \mathcal{K}_{\tau} (Algorithm 1 ) resulting in a PDAG. Stage (iii) utilizes Meek’s rule 1, which by Bang and Didelez [2023] results in a tiered MPDAG. ∎ The proof of Lemma 1 now follows directly from Lemma 3 . B.6 Proof of Theorem 3 : Sound and Completeness of TGES We start out by restating the theorem we wish to prove: Theorem 3 . (Sound and Completeness of TGES) TGES using a \mathcal{K}_{\tau} -score equivalent, decomposable, \mathcal{K}_{\tau} -consistent and \mathcal{K}_{\tau} -locally consistent score criterion, results in a tiered MPDAG and for n\rightarrow\infty the tiered MPDAG is almost surely a sound and complete estimate of the restricted Markov equivalence class of the true data-generating DAG. This subsection will prove Theorem 3 by introducing and proving three lemmas for each of the phases of TGES. Theorem 3 follows directly from these lemmas. The first lemma concerns the forward phase of TGES: Lemma 4 . (TGES forward phase) Let \mathcal{G}^{*} be the DAG from which the data \mathbf{D} was generated, n be the number of observations in \mathbf{D} , and \mathcal{K}_{\tau} the tiered background knowledge. Let \mathcal{E}^{\mathcal{K}_{\tau}} be the restricted equivalence class that is a result of a forward phase in TGES on \mathbf{D} and \mathcal{K}_{\tau} commencing with the empty graph. Then for n\rightarrow\infty we have that all \mathcal{G}\in\mathcal{E}^{\mathcal{K}_{\tau}} encode \mathcal{K}_{\tau} and \mathcal{G}^{*}\leq\mathcal{G} almost surely. The second lemma is concerned with the backward phase: Lemma 5 . (TGES backward phase) Let \mathcal{G}^{*} be the DAG from which the data \mathbf{D} was generated, n be the number of observations in \mathbf{D} , and \mathcal{K}_{\tau} the tiered background knowledge. Let \mathcal{E}^{\mathcal{K}_{\tau}} be the restricted equivalence class that is a result of a backward phase in TGES on \mathbf{D} and \mathcal{K}_{\tau} commencing with a restricted equivalence class where all graphs \mathcal{G} encode \mathcal{K}_{\tau} and \mathcal{G}^{*}\leq\mathcal{G} . Then for n\rightarrow\infty we have that all \mathcal{H}\in\mathcal{E}^{\mathcal{K}_{\tau}} encode \mathcal{K}_{\tau} and \mathcal{G}^{*}\approx\mathcal{H} almost surely. As can be seen, TGES with only forward and backward phases fulfills Theorem 3 . The third lemma then ensures that the turning phase does not turn any edges when the graph is Markov equivalent to the data-generating DAG. Lemma 6 . (TGES turning phase) Let \mathcal{G}^{*} be the DAG from which the data \mathbf{D} was generated, n be the number of observations in \mathbf{D} , and \mathcal{K}_{\tau} the tiered background knowledge. Let \mathcal{E}^{\mathcal{K}_{\tau}} be the restricted equivalence class that is a result of a turning phase in TGES on \mathbf{D} and \mathcal{K}_{\tau} commencing with a restricted equivalence class where all graphs \mathcal{H} encode \mathcal{K}_{\tau} and \mathcal{G}^{*}\approx\mathcal{H} . Then for n\rightarrow\infty we have that all \mathcal{W}\in\mathcal{E}^{\mathcal{K}_{\tau}} encode \mathcal{K}_{\tau} and \mathcal{G}^{*}\approx\mathcal{W} almost surely. B.6.1 Proof of Lemma 4 : TGES forward phase In this subsection, we prove that as n\rightarrow\infty the forward phase of TGES almost surely results in a tiered MPDAG which contains an independence statement only if the same statements is in the true data-generating DAG. The way we show this is by assuming the forward phase of TGES does not result in such a tiered MPDAG, which then leads to there existing an edge addition which improves the score. This is a contradiction to the forward phase continuing until no neighboring restricted equivalence classes have a higher score. To show these contradictions we split into quite a lot of cases. To give an overview of the cases we illustrated them in Figure 6 . We also made minimal examples of pairs of a data-generating DAG and a DAG evaluated by the algorithm which correspond to each of the cases in Table 4 . First, we introduce some needed concepts. Note that for \mathcal{G}^{*} being the data-generating DAG, we can substitute \perp\!\!\!\perp_{p} and \not\!\perp\!\!\!\perp_{p} for \perp\!\!\!\perp_{\mathcal{G}^{*}} and \not\!\perp\!\!\!\perp_{\mathcal{G}^{*}} respectively, as the distribution p is assumed to be Markov and faithful w.r.t. \mathcal{G}^{*} . We will use that these two are interchangeable in the proof of Lemma 4 . We remind the reader that for any X,Y in \mathcal{G} where Y\in\text{NDe}^{\mathcal{G}}_{X} we have by the Markov property that X\perp\!\!\!\perp_{\mathcal{G}}Y|\text{Pa}^{\mathcal{G}}_{X} . By contraposition of the Markov property, we thus have \displaystyle X\not\!\perp\!\!\!\perp_{\mathcal{G}}Y|\text{Pa}^{\mathcal{G}}_{X}\Rightarrow Y\in\text{De}^{\mathcal{G}}_{X} (5) We define a path as in Hernan and Robins [2024] between two nodes X and Y in a DAG \mathcal{G} as a sequence of edges that connects X and Y such that no node is visited more than once. A path \pi is blocked given a set of nodes C if and only if it contains a non-collider that is in C , or it contains a collider that is not in C and the collider has no descendants in C [ Pearl, 2009 ] . A path is open if it is not blocked. Let \pi be a path, we denote the length of \pi as |\pi| , which is equal to the number of nodes visited including the endpoints. We introduce two lemmas that will help prove Lemma 4 . Lemma 7 . Let \pi be an open path in \mathcal{G} given nodes \mathbf{M} . Then any sub-path \pi_{s} of \pi is open in \mathcal{G} given \mathbf{M} if the endpoints of \pi_{s} are non-colliders on \pi . Proof. All non-colliders on \pi are not contained in \mathbf{M} , otherwise \pi would be blocked given \mathbf{M} . Let A and B be non-colliders on \pi and \pi_{s} be a sub-path of \pi such that A and B are the end points of \pi_{s} . All colliders on \pi are opened by \mathbf{M} , hence all colliders on \pi_{s} are opened by \mathbf{M} . Therefore, \pi_{s} is not blocked given \mathbf{M} and is hence open. ∎ Lemma 8 . Let \mathcal{G} be a DAG and X a node in \mathcal{G} . Let Y\in\text{NDe}^{\mathcal{G}}_{X} . Then the graph \mathcal{G}^{\prime} that results from adding the edge \left\{Y\rightarrow X\right\} to \mathcal{G} is also a DAG. Proof. We are adding a directed edge, hence all edges in \mathcal{G}^{\prime} will have a direction. We need only to prove that adding the edge does not introduce a cycle. For there to be a cycle introduced by adding the edge \left\{Y\rightarrow X\right\} in \mathcal{G} , there must be a directed path from X to Y . But then we have that Y\in\text{De}^{\mathcal{G}}_{X} which is a contradiction, hence we do not introduce any cycles by adding the edge. ∎ Now we restate Lemma 4 and then provide the proof. Lemma 4 . (TGES forward phase) Let \mathcal{G}^{*} be the DAG from which the data \mathbf{D} was generated, n be the number of observations in \mathbf{D} , and \mathcal{K}_{\tau} the tiered background knowledge. Let \mathcal{E}^{\mathcal{K}_{\tau}} be the restricted equivalence class that is a result of a forward phase in TGES on \mathbf{D} and \mathcal{K}_{\tau} commencing with the empty graph. Then for n\rightarrow\infty we have that all \mathcal{G}\in\mathcal{E}^{\mathcal{K}_{\tau}} encode \mathcal{K}_{\tau} and \mathcal{G}^{*}\leq\mathcal{G} almost surely. Proof. Each step in the TGES forward phase is ensured by Lemma 3 to result in a restricted equivalence class that encodes \mathcal{K}_{\tau} . We will make a proof by contradiction, where we assume that TGES forward phase results in a \mathcal{E}^{\mathcal{K}_{\tau}} where \exists\mathcal{G}\in\mathcal{E}^{\mathcal{K}_{\tau}} s.t. \mathcal{G}^{*}\not\leq\mathcal{G} . We will prove that if this holds, then there exists a single edge addition to \mathcal{G} that results in a DAG with a higher score. This contradicts forward TGES running until no further improvement of the score. For \mathcal{G}\in\mathcal{E}^{\mathcal{K}_{\tau}} assume \mathcal{G}^{*}\not\leq\mathcal{G} . Then there exists some node X and a node Y\in\text{NDe}^{\mathcal{G}}_{X} such that \displaystyle X\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}Y|\text{Pa}^{\mathcal{G}}_{X} If \tau(Y)\leq\tau(X) , then adding the edge \left\{Y\rightarrow X\right\} will by local \mathcal{K}_{\tau} -consistency ( (i) in Def. 3 ) improve the score, which is a contradiction to TGES adding edges till no further increase in score. Since Y\in\text{NDe}^{\mathcal{G}}_{X} we are ensured by Lemma 8 that adding the edge to \mathcal{G} results in a DAG, which completes the proof for this case. Instead, assume \tau(X)<\tau(Y) . We will split into four mutually exclusive cases of the d-separation statements of X and Y given \text{Pa}^{\mathcal{G}}_{Y} in \mathcal{G} and \mathcal{G}^{*} . We illustrate the cases by the Table 3 below: Y\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{Y} Y\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{Y} Y\not\!\perp\!\!\!\perp_{\mathcal{G}}X|\text{Pa}^{\mathcal{G}}_{Y} Case A Case B Y\perp\!\!\!\perp_{\mathcal{G}}X|\text{Pa}^{\mathcal{G}}_{Y} Case C Case D Table 3: Cases for proof of Lemma 4 when \tau(X)<\tau(Y) . Case A and Case B : In both cases, we have that Y\not\!\perp\!\!\!\perp_{\mathcal{G}}X|\text{Pa}^{\mathcal{G}}_{Y} which by the contrapositioned Markov property ( 5 ) means that X\in\text{De}^{\mathcal{G}}_{Y} . This implies that \tau(X)\geq\tau(Y) which contradicts the assumption that \tau(X)<\tau(Y) . Hence, Case A and Case B can not occur. Case C : In this case Y\perp\!\!\!\perp_{\mathcal{G}}X|\text{Pa}^{\mathcal{G}}_{Y} and Y\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{Y} . We have by \tau(X)<\tau(Y) that X\in\text{NDe}^{\mathcal{G}}_{Y} , and by Lemma 8 adding the edge \left\{X\rightarrow Y\right\} to \mathcal{G} will result in a DAG. Since Y\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{Y} , we have by local \mathcal{K}_{\tau} -consistency ( (i) in Def. 3 ) that adding the edge \left\{X\rightarrow Y\right\} will improve the score, which is a contradiction to TGES adding edges till no further increase in score. Case D : First, let us summarize Case D : \displaystyle Y\in\text{NDe}^{\mathcal{G}}_{X} (6) \displaystyle X\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}Y|\text{Pa}^{\mathcal{G}}_{X} (7) \displaystyle\tau(X)<\tau(Y) (8) \displaystyle Y\perp\!\!\!\perp_{\mathcal{G}}X|\text{Pa}^{\mathcal{G}}_{Y} (9) \displaystyle Y\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{Y} (10) By X\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}Y|\text{Pa}^{\mathcal{G}}_{X} ( 7 ) there exist an open path \pi in \mathcal{G}^{*} from X to Y given \text{Pa}^{\mathcal{G}}_{X} . We write the path as a sequence of nodes, ordered from X to Y , such that \pi=\{X,...,Y\} . By Y\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{Y} ( 10 ) the path \pi in \mathcal{G}^{*} is not open given \text{Pa}^{\mathcal{G}}_{Y} . The path \pi can be blocked by \text{Pa}^{\mathcal{G}}_{Y} in two non-exclusive ways: 1. (Non-collider closed by \text{Pa}^{\mathcal{G}}_{Y} ) There exist a non-collider V\in\pi where V\in\text{Pa}^{\mathcal{G}}_{Y} . 2. (Collider not opened by \text{Pa}^{\mathcal{G}}_{Y} ) There exist a collider C\in\pi where for \forall D\in\text{De}^{\mathcal{G}^{*}}_{C}\text{ we have that }D\notin\text{Pa}^{\mathcal{G}}_{Y} . Now we split into these two sub-cases. Starting from Y and following the path \pi backwards towards X , the first blockade is either: Case D.1. A non-collider V\in\pi where V\in\text{Pa}^{\mathcal{G}}_{Y} . Case D.2. A collider C\in\pi where for \forall D\in\text{De}^{\mathcal{G}^{*}}_{C}\text{ we have that }D\notin\text{Pa}^{\mathcal{G}}_{Y} . These two cases are mutually exclusive since we are only looking at the first blockade on \pi starting from Y and going towards X . The two cases cover all scenarios since there are no other way a path can be blocked. Case D.1. We assume the first blockade on the path \pi starting from Y and following the path backward towards X is a non-collider V\in\pi where V\in\text{Pa}^{\mathcal{G}}_{Y} . Then the following hold: \displaystyle V\in\text{NDe}^{\mathcal{G}}_{X} (11) \displaystyle X\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}V|\text{Pa}^{\mathcal{G}}_{X} (12) \displaystyle X\notin\text{Pa}^{\mathcal{G}}_{V} (13) We prove each statement: ( 11 ): We see that V\in\text{NDe}^{\mathcal{G}}_{X} ( 11 ) since V\in\text{Pa}^{\mathcal{G}}_{Y} and \text{Pa}^{\mathcal{G}}_{Y}\subseteq\text{NDe}^{\mathcal{G}}_{X} . If \text{Pa}^{\mathcal{G}}_{Y}\not\subseteq\text{NDe}^{\mathcal{G}}_{X} then there exist a Z\in\text{Pa}^{\mathcal{G}}_{Y} such that Z\in\text{De}^{\mathcal{G}}_{X} , but then Y\in\text{De}^{\mathcal{G}}_{X} which contradicts Y\in\text{NDe}^{\mathcal{G}}_{X} ( 6 ). ( 12 ): X and V are both non-colliders on \pi , hence we have by Lemma 7 that the sub-path \pi_{V}=\{X,...,V\} of \pi is an open path in \mathcal{G}^{*} given \text{Pa}^{\mathcal{G}}_{X} . Since there is an open path \pi_{V} in \mathcal{G}^{*} given \text{Pa}^{\mathcal{G}}_{X} we have that X\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}V|\text{Pa}^{\mathcal{G}}_{X} ( 12 ). ( 13 ): X\notin\text{Pa}^{\mathcal{G}}_{V} ( 13 ) by the following reasoning. If it were that X\in\text{Pa}^{\mathcal{G}}_{V} , and we have that V\in\text{Pa}^{\mathcal{G}}_{Y} , then it would be that Y\in\text{De}^{\mathcal{G}}_{X} , which contradicts Y\in\text{NDe}^{\mathcal{G}}_{X} ( 6 ). Now we consider the two distinct sub-cases: Case D.1.1. \tau(V)\leq\tau(X) Case D.1.2. \tau(V)>\tau(X) Case D.1.1. As V\in\text{NDe}^{\mathcal{G}}_{X} ( 11 ), we get from Lemma 8 that adding the edge \left\{V\rightarrow X\right\} will result in a DAG. Since \tau(V)\leq\tau(X) and X\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}V|\text{Pa}^{\mathcal{G}}_{X} ( 12 ), we have by local \mathcal{K}_{\tau} -consistency ( (i) in Def. 3 ) that adding the edge \left\{V\rightarrow X\right\} will improve the score, which is a contradiction to TGES adding edges till no further increase in score. Case D.1.2. First we see that since \tau(V)>\tau(X) , it must be that \displaystyle X\in\text{NDe}^{\mathcal{G}}_{V} (14) We split in two further sub-cases: Case D.1.2.1. V\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{V} Case D.1.2.2. V\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{V} Case D.1.2.1. By X\in\text{NDe}^{\mathcal{G}}_{V} ( 14 ) and Lemma 8 adding the edge \left\{X\rightarrow V\right\} to \mathcal{G} results in a DAG. Since \tau(V)>\tau(X) and V\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{V} , we have by local \mathcal{K}_{\tau} -consistency ( (i) in Def. 3 ) that adding the edge \left\{X\rightarrow V\right\} will improve the score, which is a contradiction to TGES adding edges till no further increase in score. Case D.1.2.2. Now note that we are in the exact same scenario as at the start of Case D . Therefore, set Y:=V and fix the path \pi:=\pi_{V} and go to the start of Case D . Now we show that if we continue setting Y:=V , we at some point end up in another case than Case D.1.2.2. . Since V\in\text{Pa}^{\mathcal{G}}_{Y} we know that V\neq Y , hence |\pi_{V}|<|\pi| . Since \pi is finite and |\pi_{V}|<|\pi| , we just need to show that for a |\pi_{V}| smaller than a specific integer, we can must end up in another case than Case D.1.2.2. . We show this for |\pi_{V}|<3 . Assume we are in Case D.1.2. and |\pi_{V}|<3 . A path must be at least of length 2 , hence |\pi_{V}|=2 . Thus, the path in \mathcal{G}^{*} consists of only one edge between X and V , and since we assumed \tau(X)<\tau(Y) in this case, it must be the edge \left\{X\rightarrow V\right\} in \mathcal{G}^{*} . And since X\notin\text{Pa}^{\mathcal{G}}_{V} ( 13 ) we have that V\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{V} , which mean we are in Case 1.2.1. . Case D.2. This is the case where starting from Y and following the path \pi backward towards X , the first blockade is a collider C\in\pi where for \forall D\in\text{De}^{\mathcal{G}^{*}}_{C}\text{ we have that }D\notin\text{Pa}^{\mathcal{G}}_{Y} . In particular, we know that C\notin\text{Pa}^{\mathcal{G}}_{Y} , since C\in\text{De}^{\mathcal{G}^{*}}_{C} . Since \pi is an open path given \text{Pa}^{\mathcal{G}}_{X} and C is a collider on the path, there must exist some D\in\text{De}^{\mathcal{G}^{*}}_{C} such that D\in\text{Pa}^{\mathcal{G}}_{X} , otherwise \pi is blocked given \text{Pa}^{\mathcal{G}}_{X} . Since D\in\text{De}^{\mathcal{G}^{*}}_{C} we know \tau(C)\leq\tau(D) , and since D\in\text{Pa}^{\mathcal{G}}_{X} we know \tau(D)\leq\tau(X) . Lastly, we know that \tau(X)<\tau(Y) ( 8 ), and hence it follows that \tau(C)<\tau(Y) . Now let K be the node to the right in the collider structure of C , such that \rightarrow C\leftarrow K and \pi=\{X,...,C,K,...,Y\} . Then K\in\text{Pa}^{\mathcal{G}^{*}}_{C} , hence \tau(K)\leq\tau(C) , and in particular, \tau(K)<\tau(Y) . Since \tau(K)<\tau(Y) we have that K\in\text{NDe}^{\mathcal{G}}_{Y} . It must be that K is a non-collider on the path \pi , since it is next to a collider C . Starting from Y , K came before C , and because we are not in Case D.1. , we know that \mathcal{K}_{\tau}\notin\text{Pa}^{\mathcal{G}}_{Y} . Since C was the first blockade given \text{Pa}^{\mathcal{G}}_{Y} on \pi starting from Y in \mathcal{G}^{*} , we know that \pi_{K}=\{K,...,Y\} is an open path in \mathcal{G}^{*} given \text{Pa}^{\mathcal{G}}_{Y} . Since there is an open path \pi_{K} in \mathcal{G}^{*} given \text{Pa}^{\mathcal{G}}_{Y} we have that Y\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}K|\text{Pa}^{\mathcal{G}}_{Y} . Since K\in\text{NDe}^{\mathcal{G}}_{Y} , we have by Lemma 8 that adding the edge \left\{K\rightarrow Y\right\} results in a DAG. Since \tau(K)<\tau(Y) and Y\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}K|\text{Pa}^{\mathcal{G}}_{Y} we have by local \mathcal{K}_{\tau} -consistency ( (i) in Def. 3 ) that adding the edge \left\{K\rightarrow Y\right\} will improve the score, which is a contradiction to TGES adding edges till no further increase in score. ∎ B.6.2 Proof of Lemma 5 : TGES backward phase This subsection introduces everything needed to prove Lemma 5 and states the proof of it. First, we introduce some concepts and notations from Chickering [2003] . We will say that an edge \left\{X\rightarrow Y\right\} in \mathcal{G} is covered if \text{Pa}^{\mathcal{G}}_{Y}=\text{Pa}^{\mathcal{G}}_{X}\cup X . Covered edges have the following property as described in Chickering [2003] : Let \mathcal{G} be any DAG, and let \mathcal{G}^{\prime} be the result of reversing the edge \left\{X\rightarrow Y\right\} in \mathcal{G} . Then \mathcal{G}^{\prime} is a DAG that is equivalent to \mathcal{G} if and only if \left\{X\rightarrow Y\right\} is covered in \mathcal{G} . For any subset \mathbf{A} of the nodes in \mathcal{G} , we say that a node A\in\mathbf{A} is maximal if there is no other node A^{\prime}\in\mathbf{A} such that A^{\prime} is an ancestor of A in \mathcal{G} . We will denote a node as a sink node if all nodes adjacent to it are parents of the node. Next, we introduce the following theorem from Chickering [2003] which we will extend for tiered background knowledge. Theorem 4 . (Theorem 4 in [ Chickering, 2003 ] ) Let \mathcal{G} and \mathcal{H} be any pair of DAGs such that \mathcal{G}\leq\mathcal{H} . Let r be the number of edges in \mathcal{H} that have opposite orientations in \mathcal{G} , and let m be the number of edges in \mathcal{H} that do not exist in either orientation in \mathcal{G} . Then, there exists a sequence of at most r+2m edge reversals and additions in \mathcal{G} with the following properties: 1. Each edge reversed is a covered edge 2. After each reversal and addition \mathcal{G} is a DAG and \mathcal{G}\leq\mathcal{H} 3. After all reversals and additions \mathcal{G}=\mathcal{H} Chickering [2003] shows that such a sequence of reversals and additions exist by showing each step in the sequence can be produced by Algorithm 7 with two DAGs \mathcal{G} and \mathcal{H} where \mathcal{G}\leq\mathcal{H} . He shows that Algorithm 7 will result in a DAG \mathcal{G}^{\prime} where: \mathcal{G}^{\prime}\leq\mathcal{H} and \mathcal{G}^{\prime} is ”closer” to \mathcal{H} than \mathcal{G} , in the sense that either the number of edges of opposite orientation has decreased by 1 and the number of different adjacencies remained the same or the number of different adjacencies has decreased by 1 and the number of edges of opposite orientation has maximally increased by one. We restate the algorithm from Chickering [2003] and include ” \triangleright\# ” for references used in a later proof. Algorithm 7 Apply-Edge-Operation [ Chickering, 2003 ] Input: DAGs \mathcal{G},\mathcal{H} \mathcal{G}^{\prime}\leftarrow\mathcal{G} while \mathcal{G} and \mathcal{H} contain a node Y that is a sink in both DAGs and for which \text{Pa}^{\mathcal{G}}_{Y}=\text{Pa}^{\mathcal{H}}_{Y} do Remove Y and all edges with an endpoint at Y from both DAGs. \triangleright 1. end while Let Y be any sink node in \mathcal{H} if Y has no children in \mathcal{G} then Let X be any parent of Y in \mathcal{H} that is not a parent of Y in \mathcal{G} . Add the edge \left\{X\rightarrow Y\right\} to \mathcal{G}^{\prime} \triangleright 2. else Let D\in\text{De}^{\mathcal{G}}_{Y} denote the (unique) maximal element from this set within \mathcal{H} . Let Z be any maximal child of Y in \mathcal{G} such that D is a descendant of Z in \mathcal{G} . if \left\{Y\rightarrow Z\right\} is covered in \mathcal{G} then Reverse \left\{Y\rightarrow Z\right\} in \mathcal{G}^{\prime} \triangleright 3. else if there exists a node X that is a parent of Y but not a parent of Z in \mathcal{G} then Add \left\{X\rightarrow Z\right\} to \mathcal{G}^{\prime} \triangleright 4. else Let X be any parent of Z that is not a parent of Y in \mathcal{G} . Add \left\{X\rightarrow Y\right\} to \mathcal{G}^{\prime} . \triangleright 5. end if end if Return \mathcal{G}^{\prime} We introduce a Proposition also from Chickering [2003] . Proposition 8 . [ Chickering, 2003 ] Let \mathcal{G} and \mathcal{H} be two DAGs such that \mathcal{G}\leq\mathcal{H} . If there is an edge between X and Y in \mathcal{G} , then there is an edge between X and Y in \mathcal{H} . We show in the following theorem, that if \mathcal{G} and \mathcal{H} encode \mathcal{K}_{\tau} then there exists a sequence of edge addition and reversals where each operation results in a DAG which encodes \mathcal{K}_{\tau} . The theorem is an extension of Theorem 4 and we will prove it using the same algorithm (Algorithm 7 ) to construct the sequence. Theorem 5 . Let \mathcal{G} and \mathcal{H} be any pair of DAGs such that \mathcal{G} \leq \mathcal{H} and they both encode the tiered background knowledge \mathcal{K}_{\tau} . Let r be the number of edges in \mathcal{H} that have opposite orientation in \mathcal{G} , and let m be the number of edges in \mathcal{H} that do not exist in either orientation in \mathcal{G} . Then, there exists a sequence of at most r+2m edge reversals and additions in \mathcal{G} with the following properties: 1. Each edge reversed is a covered edge 2. After each reversal and addition \mathcal{G} is a DAG that encodes \mathcal{K}_{\tau} and \mathcal{G} \leq \mathcal{H} 3. After all reversals and additions \mathcal{G}=\mathcal{H} Proof. We wish to show that by running Algorithm 7 at most r+2m times, we obtain a sequence with properties 1, 2 and 3. By Theorem 4 we have that 1 and 3 are fulfilled, and that after each iteration of running Algorithm 7 \mathcal{G}\leq\mathcal{H} . We also have that \mathcal{G}=\mathcal{H} after, at most, r+2m times. We thus only need to show that \mathcal{G} encodes \mathcal{K}_{\tau} after each reversal or addition performed by Algorithm 7 . We remind the reader of the relationship between \mathcal{G} and \mathcal{H} , as this will be used in the proofs. All d-separation statements in \mathcal{H} also hold in \mathcal{G} , i.e. A\perp\!\!\!\perp_{\mathcal{G}}B|C\Rightarrow A\perp\!\!\!\perp_{\mathcal{H}}B|C . Furthermore, we have that both DAGs encode \mathcal{K}_{\tau} , and hence the nodes have the same tiered ordering \tau in both DAGs. The proof is divided into the 5 cases where a modification is made to the DAG \mathcal{G} by Algorithm 7 , and we need to show that this modification does not contradict \mathcal{K}_{\tau} . The 5 cases are denoted with a numbered comment, \triangleright #, in the right-hand side of Algorithm 7 . \triangleright 1. First, we realize that by removing a sink node and all incident edges from a DAG that encodes \mathcal{K}_{\tau} we obtain a DAG that still encodes \mathcal{K}_{\tau} as no contradiction to tiered background knowledge can occur by removing edges. \triangleright 2. Here X\in\text{Pa}^{\mathcal{H}}_{Y} and it must be that \tau(X)\leq\tau(Y) hence the edge \left\{X\rightarrow Y\right\} encodes \mathcal{K}_{\tau} . \triangleright 3. Here Y is a sink node in \mathcal{H} , D is maximal in \mathcal{H} in the set \text{De}^{\mathcal{G}}_{Y} , D\in\text{De}^{\mathcal{G}}_{Y} , D\in\text{De}^{\mathcal{G}}_{Z} and Z\in\text{Ch}^{\mathcal{G}}_{Y} . We have that Z\neq Y by definition. We also have that Y\neq D . We see this by the following reasoning: We know that Y has children in \mathcal{G} , otherwise, we would have terminated in case \triangleright 1. Let A\in\text{Ch}^{\mathcal{G}}_{Y} . Then A is trivially also a descendant of Y in \mathcal{G} . By Proposition 8 there is an edge between Y and A in \mathcal{H} , which since Y is a sink node, must go into Y . Therefore, A\in\text{An}_{Y}^{\mathcal{H}} which means Y is not maximal in \mathcal{H} in the set \text{De}^{\mathcal{G}}_{Y} . D is chosen to be maximal which means Y\neq D . By Z\in\text{Ch}^{\mathcal{G}}_{Y} we have that \tau(Y)\leq\tau(Z) . We wish to show that \tau(Y)=\tau(Z) as this would mean that reversing the edge is not in contradiction with \mathcal{K}_{\tau} . We first assume that \tau(Y)<\tau(Z) . Then, since Y is a sink node in \mathcal{H} , all nodes are non descendants of Y in \mathcal{H} , and in particular D\in\text{NDe}^{\mathcal{H}}_{Y} . Therefore Y\perp\!\!\!\perp_{\mathcal{H}}D|\text{Pa}^{\mathcal{H}}_{Y} holds and since \mathcal{G}\leq\mathcal{H} we have that Y\perp\!\!\!\perp_{\mathcal{G}}D|\text{Pa}^{\mathcal{H}}_{Y} . We have that D\notin\text{Pa}^{\mathcal{H}}_{Y} as D\in\text{De}^{\mathcal{G}}_{Z} , which gives \tau(Z)\leq\tau(D) , and by assumption \tau(Y)<\tau(Z) , and an edge from D to Y would contradict \mathcal{K}_{\tau} . Since Z\in\text{Ch}^{\mathcal{G}}_{Y} and D\in\text{De}^{\mathcal{G}}_{Z} there must be a directed path in \mathcal{G} from Y to D , starting with a directed edge from Y to Z . As Y and D are d-separated in \mathcal{G} given \text{Pa}^{\mathcal{H}}_{Y} , there exist a node V\in\text{Pa}^{\mathcal{H}}_{Y} on the directed path from Y to D through Z in \mathcal{G} . \tau(Z)\leq\tau(V) since V is on the directed path in \mathcal{G} which start with Z , but since V\in\text{Pa}^{\mathcal{H}}_{Y} we also have that \tau(V)\leq\tau(Y) . We then have that \tau(V)\leq\tau(Y)<\tau(Z)\leq\tau(V) , but \tau(V)<\tau(V) is a contradiction to a node only belonging to a single tier, and it hence must be that \tau(Z)=\tau(Y) , which implies that the edge \left\{Y\rightarrow Z\right\} can be reversed while still encoding \mathcal{K}_{\tau} . \triangleright 4. Here X\in\text{Pa}^{\mathcal{G}}_{Y} and Z\in\text{Ch}^{\mathcal{G}}_{Y} it must be that \tau(X)\leq\tau(Y)\leq\tau(Z) . Hence the added edge \left\{X\rightarrow Z\right\} encodes \mathcal{K}_{\tau} . \triangleright 5. Here the setup is the same as described in \triangleright 2 in addition to X\in\text{Pa}^{\mathcal{G}}_{Z} . We wish to show that \tau(X)\leq\tau(Y) , and we assume for contradiction that \tau(Y)<\tau(X) . Since X\in\text{Pa}^{\mathcal{G}}_{Z} , we have that \tau(X)\leq\tau(Z) , hence \tau(Y)<\tau(Z) and we can then use same procedure as in \triangleright 2 to obtain a contradiction. It therefore must be that \tau(X)\leq\tau(Y) , and thus the edge \left\{X\rightarrow Y\right\} encodes \mathcal{K}_{\tau} . ∎ We include one more lemma needed for the proof of Lemma 5 . Lemma 9 . Let \mathcal{G} be a DAG and let \mathcal{G}^{\prime} be the DAG that is a result of either a covered edge reversal or an edge addition in \mathcal{G} . Then \mathcal{G}\leq\mathcal{G}^{\prime} . Proof. Assume the modification made was a covered edge reversal. Then \mathcal{G} and \mathcal{G}^{\prime} are Markov equivalent and in particular \mathcal{G}\leq\mathcal{G}^{\prime} . Instead, assume the modification was an edge addition. For \mathcal{G}\not\leq\mathcal{G}^{\prime} , there must exist an open path in \mathcal{G} which is blocked in \mathcal{G}^{\prime} . Adding an edge only allows for there to exist a new blocked path, not to block an existing open path. Therefore \mathcal{G}\leq\mathcal{G}^{\prime} . ∎ We restate Lemma 5 and present a proof of it: Lemma 5 . (TGES backward phase) Let \mathcal{G}^{*} be the DAG from which the data \mathbf{D} was generated, n be the number of observations in \mathbf{D} , and \mathcal{K}_{\tau} the tiered background knowledge. Let \mathcal{E}^{\mathcal{K}_{\tau}} be the restricted equivalence class that is a result of a backward phase in TGES on \mathbf{D} and \mathcal{K}_{\tau} commencing with a restricted equivalence class where all graphs \mathcal{G} encode \mathcal{K}_{\tau} and \mathcal{G}^{*}\leq\mathcal{G} . Then for n\rightarrow\infty we have that all \mathcal{H}\in\mathcal{E}^{\mathcal{K}_{\tau}} encode \mathcal{K}_{\tau} and \mathcal{G}^{*}\approx\mathcal{H} almost surely. Proof. The TGES backward phase consists of steps provided in Algorithm 5 (illustrated in Figure 1 ) where each step removes an edge from the tiered MPDAG. The phase continues to remove edges until there are no neighboring restricted equivalence classes with a greater score. First, we see that each step results in a restricted equivalence class which encodes \mathcal{K}_{\tau} by Lemma 3 . Next, see that after each step in the phase, all DAGs \mathcal{H} in the restricted equivalence class have that \mathcal{G}^{*}\leq\mathcal{H} . Assume that this is not the case, which means there exists a DAG \mathcal{H}^{\prime} in the restricted equivalence class such that \mathcal{G}^{*}\not\leq\mathcal{H}^{\prime} . Then we have by \mathcal{K}_{\tau} -consistency ( (i) in Def. 10 ) that the score has decreased, which is a contradiction to the algorithm being greedy. Let \mathcal{E}^{\mathcal{K}_{\tau}} be the result of the backward phase in TGES. We need only to show that for all DAGs \mathcal{G}\in\mathcal{E}^{\mathcal{K}_{\tau}} we have that \mathcal{G}\leq\mathcal{G}^{*} . We will prove this by contradiction: Assume that \exists\mathcal{G}^{\prime}\in\mathcal{E}^{\mathcal{K}_{\tau}} s.t. \mathcal{G}^{\prime}\not\leq\mathcal{G}^{*} . Let \mathcal{E}^{\mathcal{K}_{\tau}}_{*} be the restricted equivalence class which contains the true data-generating DAG \mathcal{G}^{*} . Then \mathcal{G}^{*}\in\mathcal{E}^{\mathcal{K}_{\tau}}_{*} and \mathcal{G}^{\prime}\in\mathcal{E}^{\mathcal{K}_{\tau}} . By \mathcal{G}^{\prime}\not\leq\mathcal{G}^{*} there exists an independence statement in \mathcal{G}^{*} which is not in \mathcal{G}^{\prime} , hence \mathcal{E}^{\mathcal{K}_{\tau}}_{*}\neq\mathcal{E}^{\mathcal{K}_{\tau}} . Since \mathcal{G}^{*}\leq\mathcal{G}^{\prime} and they both encode \mathcal{K}_{\tau} we have by Theorem 5 that there exists a sequence of modifications that can turn \mathcal{G}^{*} into \mathcal{G}^{\prime} , such that after each modification of \mathcal{G}^{*} , the modified DAG \tilde{\mathcal{G}^{*}} will encode \mathcal{K}_{\tau} and \tilde{\mathcal{G}^{*}}\leq\mathcal{G}^{\prime} . Because of the relation \mathcal{E}^{\mathcal{K}_{\tau}}_{*}\neq\mathcal{E}^{\mathcal{K}_{\tau}} , there must at least be one edge addition in the sequence, if there were only edge reversals, the restricted equivalence classes would be identical. Let \tilde{\mathcal{G}^{*}} be the graph that precedes the very last edge addition in the sequence. Then \tilde{\mathcal{G}^{*}} is contained in a neighboring restricted equivalence class (by definition) and we have by Lemma 9 that \mathcal{G}^{*}\leq\tilde{\mathcal{G}^{*}} . By \mathcal{K}_{\tau} -consistency ( (ii) in Def. 10 ) of the scoring criterion we have that S(\tilde{\mathcal{G}^{*}},\mathbf{D},\mathcal{K}_{\tau})>S(\mathcal{G}^{\prime},\mathbf{D},\mathcal{K}_{\tau}) , which contradicts that the backward phase iterates until there is no larger score among the neighboring restricted equivalence classes. Hence the resulting restricted equivalence class must be \mathcal{E}^{\mathcal{K}_{\tau}}_{*} . ∎ B.6.3 Proof of Lemma 6 : TGES turning phase This subsection introduces everything needed to prove Lemma 6 and states the proof of it. We start by introducing a proposition, which uses Theorem 5 . Proposition 9 . Let \mathcal{E}^{\mathcal{K}_{\tau}}_{*} be the restricted equivalence class that contains the true data-generating DAG from which the data \mathbf{D} was generated, n be the number of observations in \mathbf{D} , and \mathcal{K}_{\tau} tiered background knowledge. Then for a \mathcal{K}_{\tau} -score equivalent and \mathcal{K}_{\tau} -consistent scoring criterion S we have that for n\rightarrow\infty , \displaystyle S(\mathcal{E}^{\mathcal{K}_{\tau}}_{*},\mathbf{D})>S(\mathcal{E}^{\mathcal{K}_{\tau}},\mathbf{D})\text{ for all }\mathcal{E}^{\mathcal{K}_{\tau}}_{*}\neq\mathcal{E}^{\mathcal{K}_{\tau}}\text{ almost surely.} (15) Proof. If \mathcal{E}^{\mathcal{K}_{\tau}} does not encode \mathcal{K}_{\tau} , we have by \mathcal{K}_{\tau} -consistency ( (iii) in Def. 10 ) that S(\mathcal{E}^{\mathcal{K}_{\tau}}_{*},\mathbf{D})>S(\mathcal{E}^{\mathcal{K}_{\tau}},\mathbf{D}) . Now assume \mathcal{E}^{\mathcal{K}_{\tau}} encodes \mathcal{K}_{\tau} . Assume for contradiction that there exist a \mathcal{E}^{\mathcal{K}_{\tau}} such that S(\mathcal{E}^{\mathcal{K}_{\tau}}_{*},\mathbf{D})\leq S(\mathcal{E}^{\mathcal{K}_{\tau}},\mathbf{D}) where \mathcal{E}^{\mathcal{K}_{\tau}}_{*}\neq\mathcal{E}^{\mathcal{K}_{\tau}} . By \mathcal{K}_{\tau} -consistency ( (i) in Def. 10 ) we have that for \mathcal{G}\in\mathcal{E}^{\mathcal{K}_{\tau}} and \mathcal{G}^{*}\in\mathcal{E}^{\mathcal{K}_{\tau}}_{*} that \mathcal{G}^{*}\leq\mathcal{G} . By Theorem 5 there exists a sequence of edge reversals and additions that transform \mathcal{G}^{*} into \mathcal{G} . Since all edge reversals are ensured to result in a graph in the same restricted equivalence class, we have by \mathcal{K}_{\tau} -score equivalence of S that the score remains the same for each edge reversal. After each edge addition the score increases following Lemma 9 and by \mathcal{K}_{\tau} -consistency ( (ii) in Def. 10 ). Hence there can be no edge additions. This contradicts \mathcal{E}^{\mathcal{K}_{\tau}}_{*}\neq\mathcal{E}^{\mathcal{K}_{\tau}} . ∎ We restate the lemma and present the proof Lemma 6 . (TGES turning phase) Let \mathcal{G}^{*} be the DAG from which the data \mathbf{D} was generated, n be the number of observations in \mathbf{D} , and \mathcal{K}_{\tau} the tiered background knowledge. Let \mathcal{E}^{\mathcal{K}_{\tau}} be the restricted equivalence class that is a result of a turning phase in TGES on \mathbf{D} and \mathcal{K}_{\tau} commencing with a restricted equivalence class where all graphs \mathcal{H} encode \mathcal{K}_{\tau} and \mathcal{G}^{*}\approx\mathcal{H} . Then for n\rightarrow\infty we have that all \mathcal{W}\in\mathcal{E}^{\mathcal{K}_{\tau}} encode \mathcal{K}_{\tau} and \mathcal{G}^{*}\approx\mathcal{W} almost surely. Proof. By Proposition 9 any change to the restricted equivalence class will result in a lower score, hence no changes are made by the turning phase. ∎ B.6.4 Figures Y\in\text{NDe}^{\mathcal{G}}_{X} and X\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}Y|\text{Pa}^{\mathcal{G}}_{X} \tau(Y)\leq\tau(X) Insert \{Y\rightarrow X\} \tau(X)<\tau(Y) Y\not\!\perp\!\!\!\perp_{\mathcal{G}}X|\text{Pa}^{\mathcal{G}}_{Y} Y\perp\!\!\!\perp_{\mathcal{G}}X|\text{Pa}^{\mathcal{G}}_{Y} Case A Impossible Case B Impossible Case C Y\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{Y} Insert \{X\rightarrow Y\} Case D Y\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{Y} Case D.1. Non-collider V\in\pi s.t. V\in\text{Pa}^{\mathcal{G}}_{Y} Case D.2. Collider C\in\pi s.t. \forall D\in\text{De}^{\mathcal{G}^{*}}_{C},D\notin\text{Pa}^{\mathcal{G}}_{Y} Insert \{K\rightarrow Y\} Case D.1.1. \tau(V)\leq\tau(X) Insert \{V\rightarrow X\} Case D.1.2. \tau(V)>\tau(X) Case D.1.2.1. V\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}X|\text{Pa}^{\mathcal{G}}_{V} Insert \{X\rightarrow V\} Case D.1.2.2. Y:=V , \pi:=\pi_{V} Figure 6: Illustration of Lemma 4 proof. Here \pi is chosen as a path from X to Y in \mathcal{G}^{*} that is open given \text{Pa}^{\mathcal{G}}_{X} . This path exists by X\not\!\perp\!\!\!\perp_{\mathcal{G}^{*}}Y|\text{Pa}^{\mathcal{G}}_{X} . K is the node in the collider structure of C closest to Y on \pi . \pi_{V} is the sub-path of \pi which follows \pi from X to V . Case \mathcal{G} \mathcal{G}^{*} Edge addition \tau(Y)\leq\tau(X) X Y \tau=1 \tau=2 X Y \tau=1 \tau=2 Insert \left\{Y\rightarrow X\right\} Case C X Z Y \tau=1 \tau=2 X Z Y \tau=1 \tau=2 Insert \left\{X\rightarrow Y\right\} Case D.1.1. X Z Y \tau=1 \tau=2 X Z Y \tau=1 \tau=2 Insert \left\{Z\rightarrow X\right\} Case D.1.2.1. X Z Y \tau=1 \tau=2 X Z Y \tau=1 \tau=2 Insert \left\{X\rightarrow Z\right\} Case D.1.2.2. X Z W Y \tau=1 \tau=2 X Z W Y \tau=1 \tau=2 Set Y:=W and \pi:=\pi_{W}=\{X,Z,W\} . Then we are in Case D.1.1. afterwards and we insert \left\{Z\rightarrow X\right\} Case D.2. X Z_{1} Z_{2} Y \tau=1 \tau=2 X Z_{1} Z_{2} Y \tau=1 \tau=2 Insert \left\{Z_{2}\rightarrow Y\right\} Table 4: Examples of how each Case in the proof of Lemma 4 can occur. The first column notes the case, and the second and third column respectively contains a DAG G and data-generating DAG \mathcal{G}^{*} with tiered ordering \tau that correspond to the given case. The fourth column notes which edge addition that according to local \mathcal{K}_{\tau} -consistency will result in a higher score, and hence a contradiction. Appendix C Simulation Study C.1 Metrics C.1.1 Metric of Adjacencies Estimated edge True edge Result A B * * A B * * TP A B A B * * FN A B * * A B FP A B A B TN Table 5: Overview of values in confusion matrix for the metric of adjacencies, given a relation between two nodes in the estimated graph and the true graph. An edge with stars * symbolizes that the edge can be undirected or directed to either side. C.1.2 Metric of all Directions Estimated edge True edge Result A B A B TN A B A B FN A B A B FP A B A B TP A B A B FP, FN A B A B * * NA A B * * A B NA A B A B NA Table 6: Overview of values in confusion matrix for the metric of all directions, given a relation between two nodes in the estimated graph and the true graph. An edge with stars * symbolizes that the edge can be undirected or directed to either side. NA marks cases that are not scored by this metric. C.1.3 Metric of In-Tier Directions For any pair of nodes A,B : if \tau(A)=\tau(B) the entries of the confusion matrix for the metric of in-tier directions are counted equally to the metric of all directions (see Table 6 ). If instead \tau(A)\neq\tau(B) then the pair has no effect. C.2 Computation Time We ran 50 simulations for each number of nodes between 3 and 20 and computed the average time spent. We report both the total time spent by TGES and the time spent only in stage (i) of TGES. In this way, we can both assess whether there is a general change in computation time and whether there is a change in the time spent scoring graphs by using tiered background knowledge. Figure 7: Computational time for a given number of nodes from 3 to 20 nodes. For each number of nodes, the computation time is the mean for 50 simulations. The times are provided for GES (as implemented in the R package pcalg without using C++) TGES Stage (i) (time spent in Stage (i) of TGES) and TGES Total (total time spent by TGES). The total computation times spent by TGES and GES are more or less equal, as can be seen in Figure 7 . Across the number of nodes, the computation time of TGES in stage (i) is smaller than GES. This is most likely due to TGES needing to score fewer edges in the backward phase than GES as a result of using \mathcal{K}_{\tau} . This shows promise of TGES being faster than GES if we are able to restrict by \mathcal{K}_{\tau} and utilize Meek’s rule 1 in a faster way than the current implementation. C.3 All methods This section includes the plots shown in the article but with some additional methods. Figure 8: Standardized Structural Hamming Distance for GES, STGES, TGES, TPC with \alpha=0.001,0.01,0.1 . Figure 9: Metrics of adjacencies, all directions and in-tier directions for GES, STGES, TGES, TPC with \alpha=0.001,0.01,0.1 . Appendix D Data Example Mother married Birth Low paternal social class Length Weight Maternal smoking Childhood Intelligence test score Positive attitude towards school Bullied in school Low paternal social class BMI Youth Intelligence test score Employment status Adulthood Binge drinking BMI Total years of smoking Weekly contact with friends Cohabitation status Number of children Under- graduate education Depression Early old age Hospital contact due to heart disease Retirement Figure 10: Tiered MPDAG fitted using TGES with score criterion TBIC with a tuned penalty parameter such that the number of edges corresponds to the number of edges in Figure 12 . The data is from Petersen et al. [2023a] . Mother married Birth Low paternal social class Length Weight Maternal smoking Childhood Intelligence test score Positive attitude towards school Bullied in school Low paternal social class BMI Youth Intelligence test score Employment status Adulthood Binge drinking BMI Total years of smoking Weekly contact with friends Cohabitation status Number of children Under- graduate education Depression Early old age Hospital contact due to heart disease Retirement Figure 11: Tiered MPDAG fitted using TGES with score criterion TBIC on the data from Petersen et al. [2023a] . Mother married Birth Low paternal social class Length Weight Maternal smoking Childhood Intelligence test score Positive attitude towards school Bullied in school Low paternal social class BMI Youth Intelligence test score Employment status Adulthood Binge drinking BMI Total years of smoking Weekly contact with friends Cohabitation status Number of children Under- graduate education Depression Early old age Hospital contact due to heart disease Retirement Figure 12: Expert consensus DAG from Petersen et al. [2023a] . Expert TPC Adjacency Non-adjacency Adjacency 10 20 Non-adjacency 20 181 Table 7: Confusion matrix from Petersen et al. [2023a] for the TPC algorithm. TPC is tuned to fit a graph with exactly 30 edges. Expert \text{TGES}_{\text{tuned}} True False Positive 8 1 Negative 0 2 Table 8: Confusion matrix for the metric of all directions. Estimated using TGES with TBIC with tuned penalty parameter to match the number of edges in the expert graph. Expert \text{TGES}_{\text{tuned}} True False Positive 1 1 Negative 0 2 Table 9: Confusion matrix for the metric of in-tier directions. Estimated using TGES with TBIC with tuned penalty parameter to match the number of edges in the expert graph. The estimated graph has 12 in-tier edges out of 30 edges in total. Expert \text{TGES}_{\text{fixed}} True False Positive 10 2 Negative 0 3 Table 10: Confusion matrix for the metric of all directions. Estimated using TGES with TBIC. Expert \text{TGES}_{\text{fixed}} True False Positive 1 2 Negative 0 3 Table 11: Confusion matrix for the metric of in-tier directions. Estimated using TGES with TBIC. The estimated graph has 18 in-tier edges out of 55 edges in total.