{'fraction_non_alphanumeric': 0.03229825271747594, 'fraction_numerical': 0.010776466191173265, 'mean_word_length': 4.287878787878788, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Bayesian Dirichlet Scores for Staged Trees and Chain Event Graphs

Chain event graphs (CEGs) are a recent family of probabilistic graphical models that have emerged as a suitable alternative to Bayesian networks (BNs) for asymmetric processes. These asymmetries include context-specific independencies and structural asymmetries (i.e. structural zeros and structural missing values). Model selection in CEGs is done through an intermediate model called staged trees, and similar to BNs, this can be done through a score-based approach. Moreover, a CEG is uniquely defined by its staged tree. In BNs, the Bayesian Dirichlet equivalent uniform (BDeu) score - obtained through a specific hyperparameter setting in the Bayesian Dirichlet score function - is popular for score-based model selection for its desirable theoretical properties such as ease of hyperparameter setting, preservation of effective sample size, and score equivalence. It has been shown that, under standard assumptions, the BD score function can analogously be defined for staged trees and thereby, for CEGs. However, unlike in BNs, there has been little research into the effects of hyperparameter setting in the BD score function on both these models. In this paper, we derive a BDeu score for staged trees and CEGs. Further, we explore the relationship between the BD sparse (BDs) score, proposed for BNs that contain unobserved configurations of its variables within a dataset, and the BDeu for staged trees and CEGs. Through this relationship, we demonstrate the favourable properties of CEGs in modelling processes with sparsity or asymmetry.


Introduction
Chain event graphs (CEGs) are probabilistic graphical models that can represent complex independence statements between variables on discrete data. They contain the popular graphical modelling family of discrete Bayesian networks (BN) as a subclass (Barclay et al., 2013). Unlike BNs, CEGs are able to model asymmetric processes. We say that a process is asymmetric when it exhibits at least one of two types of asymmetries. The first is asymmetric conditional independence relationships or context-specific conditional independencies which are independencies of the form X Y|Z = z 1 but X Y|Z = z 2 for some variables X, Y and Z where stands for probabilistic independence and the vertical bar shows conditioning variables on the right. These are expressed in the graph of a CEG through the colouring of its nodes. The second is structural asymmetry which occurs when the event space of a process does not conform to a product space structure (Shenvi, 2021). Structural asymmetries occur naturally or by design in many domains, such as public health , security  and migration (Strong et al., 2021). CEGs can accommodate these through their tree-based constructions.
CEGs are obtained from event trees, through the construction of an intermediate model called staged trees (Smith and Anderson, 2008). More specifically, model selection for CEGs is equivalent to obtaining the staged tree from the event tree as the mapping from the staged tree to the CEG is bijective Smith and Anderson, 2008). Hereafter, for simplicity, we will focus on staged trees. Note, however, that the advances in this paper are equally applicable to CEGs.
Event trees can be a more natural way of depicting a process as an unfolding of events (Shafer, 1996). Staged trees are created from event trees by embellishing their situations, i.e. non-leaf nodes, with colour. Situations are assigned the same colour if they have the same conditional transition probability and we define situations assigned the same colour as being in the same stage.
Example 1 Suppose there is a study on the length of hospital stays for women after giving birth. The response variable is X L , a binary variable recording whether an individual was in hospital for ≤ 2 days (value 1) or > 2 days (value 0). Three covariates were also recorded: • X A : The age of the individual: either ≥ 29 years (1) or < 29 years (0); • X P : The length of the pregnancy term: either ≥ 37 weeks (1) or < 37 weeks (0); • X B : The type of birth: either without (1) or with (0) a caesarean section. Figure 1 shows the directed acyclic graph (DAG) of the BN for this study based on the following independencies: Note that if we were to assign a strict ordering on the variables of the DAG, we could equivalently Figure 1: The DAG of the BN for the pregnancy example.
place X P or X A first. Now, suppose that recent studies show that the length of hospital stay was independent of age only when a c-section didn't occur, but not when it did. This can be written as This is an example of a context-specific conditional independence. The DAG in Figure 1 cannot represent this information without serious modifications.
We demonstrate now that through the use of colour, a staged tree can encode this information in its graph. Figure 2 gives two staged trees -T P with X P at the root and T A with X A at the root -both of which can represent Statement 1. Both of these trees are statistically equivalent (Görgen and Smith, 2018). Note that stages with only one situation have their colouring suppressed.
In both staged trees, edges with a corresponding label of 1 are directed upwards, and the edges in the tree have been labelled with the counts of individuals who traverse each edge. For example, the edge from s 3 to s 7 in T P represents that, in the sample, there are 10 women under the age of 29 with a term over 37 weeks and no c-section.
Figure 2: The staged tree for the pregnancy example with the context-specific conditional independence relationship, with X P first (T P , left) and X A first (T A , right).
Next, suppose that for any older individual with a pregnancy term less than 37 weeks (the situation s 6 ), the birth must necessarily be a c-section. This would imply that a birth without a c-section in such a scenario would be a structural zero (i.e. a logical impossibility), and so the count on the edge from s 6 to s 13 will always be zero: any individual at s 6 must also be at s 14 . Furthermore, suppose an additional variable recording whether a miscarriage occurred, X M , was introduced. Then, for women who suffer a miscarriage, X B is meaningless. This constitutes a structural missing value which is represented within the event tree by excluding any edges for X B for women who suffer a miscarriage. These are both examples of structural asymmetries, which cannot be represented by a BN but can be by a staged tree.
Various model selection methodologies have been explored for staged trees. Often, these methodologies are extensions of the structure learning techniques for BNs, which can be score-based, constraint-based or hybrid (Scutari, 2018). Constraint-based methods use statistical tests to learn conditional independence statements. Score-based methods are the more classical model selection methods aiming to maximise some objective function, such as the marginal likelihood or non-Bayesian methods including the Bayesian Information Criterion (Schwarz, 1978) or Akaike Information Criterion (Akaike, 1974). Hybrid methods are a combination of the two approaches.
For staged trees, score-based methods are the most common thus far, see Carli et al. (2022) for an example of hybrid model selection that fits a BN first, but very little research has been done on the properties of the scoring functions used. Score-based methods for BNs often have desirable properties for the score functions, such as ease of setting prior hyperparameters (particularly when no domain expertise is available), and score equivalence for equivalent probabilistic structures (Heckerman et al., 1995).
In BNs under certain assumptions the Bayesian Dirichlet score equivalence (BDe) metric (Heckerman et al., 1995) is score equivalent and when an effective sample size α, a measure of the strength of one's prior belief, is propagated uniformly through the tree, we get the Bayesian Dirichlet equivalent uniform (BDeu) score. This only requires the setting of one hyperparameter, and still satisfies score equivalence (Chickering, 1995), while essentially being a weakly informative prior. For the BDeu, this effective sample size is ideally kept consistent for each random variable. However, when values of some X i are unobserved for certain parent combinations, the effective sample size decreases, leading to overfitting and the inclusion of spurious arcs (Scutari, 2016). This can be a problem with sparse data, where the sample size is not large compared to the number of random variables and parent combinations. Scutari (2016) proposes an intuitive adjustment called the Bayesian Dirichlet sparse (BDs) score, where only non-zero parent combinations are considered and the effective sample size is maintained throughout. This has several nice properties for model selection, but is only asymptotically score equivalent (Scutari, 2018).
The purpose of this paper is two-fold. First, we extend the BDeu to staged trees, such that the desirable properties are maintained whilst also being applicable to a wider class of staged trees than current formulations. Second, we extend the BDs approach to staged trees using the explicit treatment of zeroes alongside this newly formulated BDeu. In Section 2, we introduce notation for BNs and staged trees. In Section 3, we review the BDeu and the BDs for BNs. In Section 4, we propose a new formulation of BDeu for staged trees. In Section 5, we discuss the relation between BDs and staged trees. We conclude with a discussion in Section 6.

Bayesian Networks
Let D denote the complete random data sample used. We define a BN B = (G, π) over the random variables X X X = (X 1 , . . . , X n ) as a DAG G whose nodes are given by the variables X X X and whose edge set consists of directed arcs such that lack of an edge between two nodes represents conditional independence between the variables represented by the nodes. Further, the dependencies in the BN are quantified by the conditional probability tables π. For a variable X i , let r i denote the size of its state space, q i denote the size of its parent state space, and let the Dirichlet hyperparameter for its j th parent combination be α i j = (α i j1 , . . . , α i jr i ). Let α i j = k α i jk . Let the corresponding observed number of individuals for variable X i , parent combination j and state k be n i jk , with vector of counts n i j = (n i j1 , . . . , n i jr i ) and n i j = k n i jk . For a graph G and complete sample D, suppose that the positivity, parameter independence and parameter modularity assumptions hold. Then, with prior hyperparameter vector α = (α 11 , . . . , α nq n ), we can define the BD score (Heckerman et al., 1995) as the product of the individual marginal likelihoods for each parent combination of each variable given as (2)

Staged Trees
We define a staged tree as (T , θ T ) where T is the underlying event tree, and θ T is the collection of conditional transitional probability vectors for its nodes. A leaf is any node with no outgoing edges and a situation is any non-leaf node. Define a stage u as a set of situations with equivalent conditional transition probability vectors. The collection of stages partitions the node set of T .
A level of a staged tree is the collection of situations which are the same distance, or number of edges, from the root. A staged tree is said to be stratified when the event space of the process is the product space of a pre-specified collection of variables. Here, each level of the tree corresponds to a different variable, and each situation at that level has the same number of outgoing edges, one for each state. We define a non-stratified staged tree as any staged tree which is not stratified.
Let Λ(T ) be the set of all root-to-leaf paths in tree T . For a path λ ∈ Λ(T ), let E(λ) be the edge set of that path. An edge e can also be written as the pair (v m , v n ), where e is the edge between the nodes v m and v n . For simplicity and clarity, we can write this edge as e m,n . Define the situation-

Review
The BD score in Equation 2 is dependent on the structure of the BN, namely pa(i), the parent set of each X i , and the choice of the hyperparameters α i jk . For some choice of α, variously called the effective, imaginary or equivalent sample size, let α i jk = α/(r i q i ). This choice of hyperparameter gives the BDeu metric (Heckerman et al., 1995). The effective sample size for each variable X i is α i = j,k α i jk = α, and so is invariant with i. In addition, the BDeu metric is score equivalent which implies that the BDeu would give the same score to two DAGs that encode the same probability distribution (Chickering, 1995). This is a particularly desirable result, as often causal relationships (and thus strict ordering of arcs and variables) are not explicitly known, and so there can be several DAGs that are in the same equivalence class, and that should not be discriminated from each other. Furthermore, the BDeu metric often is used alongside a Uniform prior on the model space, where every model is given equal prior probability (Heckerman et al., 1995).
The BDeu metric only requires one hyperparameter specification, α, and so is easily generated without much prior information. However, it is not without its limitations (see Scutari (2016)). This includes the fact that the sensitivity to choices of α results in a prior that is not as weakly informative as one would like, particularly for medium-sized data (Steck and Jaakkola, 2003). Furthermore, it is common to associate the choice of α with the strength of one's prior beliefs, and increasing α decreases the variance of the posterior parameter estimates due to it appearing in the denominator for the expectation of a Dirichlet random variable, which is the posterior distribution (Heckerman et al., 1995). This motivates the goal to keep α consistent; if it decreases with each variable, then the posterior estimates will converge to the maximum likelihood estimators, leading to overfitting and spurious inclusion of arcs (Scutari, 2016).
This gradual decrease in the effective sample size occurs when there are zero counts, n i j = 0, i.e. when the j th parent combination for X i is unobserved. This could occur because of a small sample size, known as a sampling zero, or because the parameter positivity assumption is violated, known as a structural zero (Shenvi, 2021). Necessarily, when n i j = 0, we must have that n i jk = 0, the k th value for X i with parent combination j. As Γ(α i j ) = Γ(α i j + n i j ) and Γ(α i jk ) = Γ(α i jk + n i jk ), k = 1, . . . , r i , n i j no longer contributes to the BDeu metric. The BDeu metric thus can be expressed as a product over j such that n i j > 0, rather than over all j = 1, . . . , q i , and we get that j:n i j >0 k α i jk ≤ j,k α i jk = α. Hence, the effective sample size for the purposes of the calculation decreases with each occurrence of a zero count, potentially leading to the problems described above. Scutari (2016) proposes an intuitive and practical solution: letq i = #{ j : n i j > 0}, and define the hyperparameterα i jk = α/(q i r i ) when n i j > 0, and 0 otherwise. By only distributing the effective sample size across the parent combinations which are non-zero, and thus actually contribute to the BDeu metric, the effective sample size is maintained for each variable. This formulation of the hyperparameters gives the Bayesian Dirichlet sparse (BDs) metric (for full details, see Scutari (2016)), which is no longer fully Bayesian, but empirically Bayesian. For the prior on the model space, Scutari (2016) proposes the the Marginal Uniform prior alongside the BDs, which assigns equal probability to arc inclusion and arc exclusion.
Assuming parameter positivity holds, these zero counts are in reality sampling zeroes, and so as sample size increases, the BDs converges to the BDeu, as we would expect each combination to be observed eventually. Note that the BDs metric is not score equivalent unless n i j > 0 ∀i, j. Below we outline a major reason for the lack of score equivalence.

Consistency Issues
Consider the case where n i j = 0. In the BDs setting, each outgoing edge will have a hyperparameter α i jk = 0. This is equivalent to treating it is as a structural zero. However, n i j = 0 means that at least one of the states of one of its parents in this j th combination is unobserved. This unobserved parent combination may be a sampling or structural zero. As the first variable in the BN has no parents, it will always have nonzero hyperparameters. Using this and the fact that any zero hyperparameter must follow a zero count for one of its parents, when n i j = 0, there will always be a zero count with a non-zero prior hyperparameter amongst its ancestors. This could be thought of as the first zero in the chain of the process. This initial zero, with its non-zero hyperparameter, is treated as a sampling zero, but its descendants, which will be zero as a result, are treated as structural zeroes. We believe this inconsistency is why the BDs is not score equivalent, as for models with different variable orderings, a different zero count will be treated as a sampling zero even if these competing models are supposed to be in the same equivalence class.
Example 1 (continued) We refer to the DAG in Figure 1. Suppose there were no individuals over 29 years of age observed, but there were younger individuals. In this case, α A = α, α A,1 = α A,0 = α/2, and so the older individuals are a sampling zero. Necessarily, because there were no individuals over 29 observed, there were also no births observed for those over 29, and so two of the four parent combinations for X B are unobserved. Thus, the hyperparameters for these parent combinations will be zero, they will be assumed to be structural zeroes, and they will not contribute to the BDs metric. However, no such births were observed because no older individuals were observed, yet the reasons for their absences are being considered differently.
Refer now to T P in Figure 2, and assume no individuals over 29 are observed, so the edges e 1,4 (the edge from situation s 1 to s 4 ) and e 2,6 have zero counts. Calculating the hyperparameters in the same way as for the BDs, these edges will have nonzero hyperparameters, corresponding to sampling zeroes, but the situations they enter, s 4 and s 6 , will not be observed. Their outgoing edges, say e 4,9 , will now have α 4,9 = 0, and they will be a structural zero. Labelling the edges of the tree with the hyperparameters, and picturing the hyperparameters propagating along the edges of the tree, some edges go from nonzero to zero, and others increase to account for them in maintaining the effective sample size. Hence, the issues with consistency in definitions of zeroes can be seen clearly through a staged tree.

BDeu for Staged Trees
The agglomerative hierarchical clustering (AHC) algorithm is the most common score-based method to merge situations into stages at each level of the tree (Freeman and Smith, 2011) . The BD metric itself is a popular choice of scoring function (Freeman and Smith, 2011), and Cowell and Smith (2014) proposed a BDeu analogue for CEGs. However, this BDeu analogue was notationally lacking, and did not have the flexibility to cover the entire staged tree family, which is larger than the BN family. In particular, it is only applicable to stratified staged trees, which has a direct, although sometimes approximate 1 , translation as a BN. For example, in a staged tree, a structural zero can be represented by deleting the associated edge (Shenvi, 2021), and so the underlying event tree is no longer stratified. The BDeu analogue to this tree would result in overestimation of the number of edges in the tree and subsequently the effective sample size would not be maintained.
We propose a new way of setting the hyperparameters for the BDeu for CEGs which is centred on path uniformity, where every possible path is equally probable. We assign each path a uniform prior weight based on the effective sample size and number of paths, and back-propagate this through the staged tree to obtain the prior hyperparameters for each situation and its edges, α i j and α i jk respectively. This is motivated by the uniform prior on paths mentioned in Barclay et al. (2013).
There is a one-to-one correspondence between the root-to-leaf paths in a tree, and its leaf nodes, as each leaf represents a unique unfolding of the process, so these can also be referred to interchangeably. Let L be the number of leaf nodes; that is L = #Λ(T ). For each leaf node, we assign a weight of α L . Then, for each situation and edge in the tree, the prior hyperparameter is simply the sum of the prior weights of the leaf nodes descendant from it. With uniform weights, this is simply the product of α L and the size of situation-or edge-centred event. Consider a situation s i j , the j th situation at level i, with r i j outgoing edges. Then, the hyperparameter for its k th outgoing edge e i jk is The hyperparameter for the situation s i j can be defined similarly. Using the fact that: #Λ(e i jk ), 1. The translation will be approximate in the presence of context-specific information.
we also have that α i j = k α i jk as desired. Now, this BDeu metric will be calculated stage-wise, not situation-wise. That is, rather than summing over the contributions for each situation at a level, the contributions for each stage are considered instead. Suppose a stage u j consists of N j situations, labelled s (l) j , l = 1, . . . , N i j . Then, the edge hyperparameters for u j are The hyperparameter for the stage itself is α j = r j k=1 α jk . This extends similarly to the counts n j for the stage. Then, in a staged tree where all leaves are the same distance from the root, and where no stage is on multiple levels, for the level i which has J i stages, we have that Note that the effective sample size is maintained for the applicable staged trees described above, which include all stratified staged trees. When there is an asymmetric process with paths of different lengths, each time a path is concluded, the effective sample size for the tree as a whole will decrease by the weight attributed to this path. This could be accounted for by, at each level, weighting each path based on the remaining number of leaves rather than total number of leaves in the tree, in a way an analogue to the BDs. However, doing this violates the conservation of the hyperparameters moving from edge to situation that is necessary for score equivalence, as discussed in Section 6. Furthermore, if a stage is on multiple levels, which is possible for a non-stratified staged tree, then interpreting the BDeu by level can lead to overestimation of the effective sample size. As such, it is better to look at the collection of stages as a whole, rather than by level. Once the hyperparameters have been set, the BDeu metric for a staged tree T with J stages (the most general form) can now be formulated as: Example 1 (continued) Revisiting the staged tree T P for the pregnancy example in Figure 2, there are 16 leaf nodes, corresponding to 16 = 2 4 root-to-leaf paths. For the edge between s 3 and s 7 , so an individual under 29 with a term over 37 weeks and no c-section (which can be associated with s 7 itself), there are 2 leaves that are descendant, and so #Λ(s 7 ) = 2, α 3,7 = α 7 = 2α 16 = α 8 . This should not be surprising considering there are 4 singleton stages, so 8 edges in total to divide the effective sample size across.
However, now look at the stage u red = {s 1 , s 2 }. Each edge has 4 descendant leaves, but looking at the edges for the stage as a whole, each of the two edges has 4 + 4 = 8 descendant leaves, and so the prior hyperparameter of each edge is α 2 . This level only contains one stage and so the effective sample size is still α.
Recall the equivalent depiction T A in Figure 2. In both trees, the levels for X B and X L are the same, except possibly reordered vertically, and their product will be the same. We focus on calculating the BDeu metric for just the first two levels, for a general α. For T P , this is: Meanwhile, for T A this is: which is the exact same as (5), and the two statistically equivalent trees have the same score.
This new formulation of the BDeu metric is essentially a different way of expressing the BDeu initially proposed in Cowell and Smith (2014), but now versatile enough to be applied to non-stratified staged trees. This flexibility will be advantageous when addressing zero counts.

BDs for Staged Trees
We now attempt to extend the BDs to staged trees. Unlike BNs, staged trees require the user to be explicit with regards to their treatment of zero counts as sampling zeros or structural zeros. The latter is represented by deleting the corresponding edge in the tree. As the tree depicts the entire unfolding of the process, any inconsistencies will raise questions on the logic behind the underlying prior assumptions. For staged trees, a differential treatment of a particular zero count on a path between competing models will necessarily take us out of the equivalence class and therefore, will generally result in different scores for the models. To stay within the equivalence class of a staged tree, all competing models must treat each zero count consistently; either as a structural zero, or as a sampling zero. This could be interpreted as an assertion on the path itself. Due to the versatility of the staged tree, these decisions need not be uniform across all paths, i.e. one zero can be structural whilst another can be sampling. However, in the absence of any prior information, or a known logical unfolding of the process, we argue that treating all zeros in the same manner is beneficial.
Suppose we characterise each zero count in the staged tree as a sampling zero. This is in fact the usual BDeu metric without any adjustments, and thus runs into the same problems as for the BN. Similarly, defining any single path as a sampling zero will still decrease the effective sample size once the first zero on the path occurs. In order to maintain the effective sample size whilst also being consistent, we could instead define each of the zero counts as a structural zero. We then define an adjusted tree T * as T when each edge that is assumed to be a structural zero is deleted. Necessarily, this enforces a certain stage structure in the tree, as situations can only be in the same stage as other situations which have the same number of edges, and same edge labels. Once this stage structure is enforced, any staged tree which includes this stage structure can now be compared.
This methodology demonstrates part of the motivation for the expression of the BDeu in terms of leaves. The adjusted tree T * is a non-stratified staged tree once any edge is deleted unless all identical edges for a variable are deleted, which would raise questions on the variable's inclusion in the first place. Hence, we now define the staged tree equivalent of the BDs as the BD structurally sparse (BDstruc) metric, which is simply the BDeu applied to the adjusted tree. The effective sample size will be maintained (in equivalent scenarios as for the BDeu), one of the incentives for the BDs. In addition, if the BDeu is score equivalent, so is the BDstruc, due to the consistency in treatment of zeroes across competing models within the equivalence class. We thus propose that when no prior information is available, the BDstruc should be used.
Example 1 (continued) We refer again to the staged tree T P in Figure 2, and assume each zero count is a structural zero. This deletes the edge from s 6 to s 13 , which also deletes s 13 , l 13 and l 14 . We also delete the edge from s 11 to l 10 , which deletes l 10 , and removes s 11 from the same stage as s 7 and s 9 . The adjusted staged tree, T * P can be seen in Figure 3. Note that the indexing for the situations and leaves has been updated to account for the deletions. Furthermore, s 9 is in its own stage. Now, the levels for X B and X L no longer have the same number of edges for each node, and the adjusted tree is no longer stratified. The BDstruc is now the BDeu applied to this non-stratified tree with all structural zeroes. In this case, L = 13, and α 3 = α 4 = 4α 13 , while α 5 = 3α 13 and α 6 = 2α 13 . The hyperparameters still sum to α as desired, but now the situations s 5 and s 6 have a lower prior belief than s 3 and s 4 . Intuitively, this makes sense; we are assuming each path has an equal probability of traversal and so situations on less paths have a lower prior probability of being visited. Consequently, the situations and edges that share paths with s 5 and/or s 6 will also have lower prior beliefs. In particular, for the edge from s 0 to s 1 we have that α 0,1 = 8α 13 , but α 0,2 = 5α 13 . The BDstruc score can be calculated, and when compared to T A (through the adjusted tree T * A ) in a similar way to the BDeu, they have the same score.

Discussion
In this paper we proposed a new formulation of the hyperparameters for the BDeu metric for staged trees and CEGs. This metric is now capable of being applied to non-stratified staged trees, which often occur in applications of real-world systems. This greater applicability can be combined with the assumptions of structural zeroes and the creation of an adjusted staged tree to calculate the BDstruc metric. The BDstruc metric, as with the BDs, maintains the effective sample size throughout for staged trees where each path is of the same length and stages are not on multiple levels.
We posit that the BDeu is score equivalent, and the next step is to publish a formal proof. The statistical equivalence classes of staged trees can be traversed through two operators, the swap and resize, outlined in Görgen and Smith (2018) and Görgen et al. (2022). The swap operator reorders suitable subtrees, and the BDeu metric on these subtrees is invariant by commutativity. Examples of suitable subtrees, called twins, can be seen in Figure 2 for the subtrees containing X P and X A , where their order is reversed. The score equivalence of these two trees was shown in Section 4. Furthermore, the resize operator transforms suitable subgraphs into subtrees where each root-toleaf path is one edge, or vice versa. These suitable subgraphs come in two cases but are in essence saturated subgraphs, across which the BDeu simplifies nicely.
In staged trees, issues with sparsity are at their worst for the final level, the edges that enter the leaves. In the BDstruc, we have proposed treating these zeroes as structural zeroes, in the same way as for all other edges. However, when an edge entering a leaf has a zero count, but the situation it is emanating from has a non-zero count, there are arguments for both treatments. Treating it as a structural zero and deleting the edge is the simplest way, consistent with the rest of the BDstruc, and hence maintains any score equivalence should this level be reordered. It also avoids any spurious merging with other stages. However, often this final level is logically placed, either as a designated response variable or obvious end of the process, and so reordering is not considered. Moreover, the effective sample size will not be affected, as it is the final level. In addition, while spurious merging is avoided, so is all merging, and valuable stage information could be lost, particularly if it was a sampling zero in reality. This is a common occurrence when the tree is sparse. Finally, in a sparse tree, many edges may be deleted if they were designated as structural zeroes, which can significantly affect the prior hyperparameters throughout the tree, due to back-propagation, and also limit interesting stage discoveries for the final level. As such, whilst we propose the BDstruc as a generally applicable solution, we suggest strong consideration should be given to the treatment of each zero count in particular.