CHARACTERIZING AND IDENTIFYING SEPARABLE GRAPHICAL MODELS B Y C HRISTOPHER M EEK 1,a AND K AYVAN S ADEGHI2,b 1 Department of Statistics, University of Washington, a [email protected]
arXiv:2607.01057v1 [stat.ML] 1 Jul 2026
2 Department of Statistical Science, University College London , b [email protected]
We study a broad class of graphical models whose independencies correspond to vertex separation in mixed graphs with directed, undirected, and bidirected edges, that are capable of encoding independence structures arising from feedback, latent and selection mechanisms. In particular, we introduce separable graphs, in which each missing edge implies the existence of a separating set for its endpoints, and essentially separable graphs, those graphs separation equivalent to a separable graph. We show that these models include many existing graph families used to define graphical models an provide several characterizations of separable graphs and essentially separable graphs. We also provide multiple characterizations of separation equivalence for separable graphs. One is a graphical characterization—extending earlier results for specific subfamilies—in terms of ordinary graph properties. Another is a separational characterization, depending only on graph separation properties. Finally, we provide a canonical representation for the equivalence classes of essentially separable graphs and develop an algorithm that, under suitable assumptions, identifies the equivalence class of any essentially separable graph.
1. Introduction. Graphical models provide a simple intuitive means of describing sets of independence facts that arise in different statistical contexts. A graphical model consists of a graph and a statistical model — a family of probability distributions — such that each probability distribution in the family satisfies a set of statistical independence facts defined by vertex separation in the graph. When considering probability distributions over product measurable spaces with index set V,1 one uses a graph G = (V, E) whose vertices correspond to the index set V and a set of edges E in conjunction with a separation criterion to describe the set of independence facts that are required to hold. Such a separation criterion defines the global Markov properties of a graphical model defined by the graph G. Different classes of graphs arise naturally in different applications. For example, undirected graphs arise in physics [8], directed acyclic graphs arise in genetics [28], and chain graphs generalize these classes [11]. Cyclic graphs arise when modeling systems with feedback [9, 16]. Graphs with bidirected edges and undirected edges arise in systems in which there are latent and selection processes [18, 23]. Different separation criteria also arise naturally in different contexts. The most common separation criterion is d-separation and its various generalizations (e.g., m-separation, c-separation). Additional examples of separation criteria are σ -separation used for non-linear feedback systems [6, 22], p-separation used for modeling independence among regression residuals [1], and δ -separation used for dynamical systems [5]. In this paper, we consider mixed graphs that allow for multiple edges between any pair of vertices where an edge can either be undirected, directed, or bidirected edges MSC2020 subject classifications: Primary 62H22; secondary 62D20. Keywords and phrases: Anterial graphs, Graph separation, Separable graphs, Inducing vertices, Markov properties, Structure identification. N 1 A measurable space ×v∈V Xv , v∈V Fv where, for v ∈ V , Fv is a σ-field over the set Xv .
1
2
and a generalization of d-separation. The family of graphical models defined by these mixed graphs can model feedback, latent and selection processes and includes as subclasses many existing classes of graphical models. We introduce two types of mixed graphs: separable graphs and essentially separable graphs. Separable graphs are those in which every missing edge between two vertices corresponds to the existence of a separating set for the two vertices. Essentially separable graphs are those graphs that are separation equivalent to some separable graph. Separable and essentially separable graphs unify a large set of existing graphs used to define graphical models. Separable graphical models generalize the families of undirected, directed, chain graphical models, maximal ancestral graphs, maximal chain mixed graphs, and maximal anterial graphs. Essentially separable graphical models additionally include ancestral [18], anterial [19], and chain mixed graphical models [10]. As both separable and essentially separable graphs include some cyclic graphs, graphical models defined in terms of these families include models that can be used to describe systems with feedback. The defining property of separable graphs has appeared previously [10, 18] as an emergent property of a maximization process in which one adds edges to a graph to form an equivalent larger graph until one cannot further augment the graph. In particular, [18] shows that maximal ancestral graphs and [10] shows that maximal chain mixed graphs have the emergent property that every missing edge corresponds to the existence of a separating set. In contrast, we use the property to define separable graphs. This allows us to define a more general family of graphs including some cyclic graphs. We show, however, that for the class of mixed graphs, a maximal graph need not be separable under d-separation. We provide characterizations of separable graphs and essentially separable graphs. In one graphical characterization we show that essentially separable graphs are essentially acyclic graphs, that is, they are separation equivalent to an acyclic graph. Furthermore, we show that the family of anterial graphs introduced by [19] is essentially equivalent to the family of essentially separable graphs, that is, the family of statistical models associated with the graphical models defined by anterial graphs is identical to the family of statistical models associated with essentially separable models. This result has significant potential computational benefit due to the fact that anterial graphs are simple acyclic graphs. We provide graphical characterizations of several graph families including the family of essentially undirected graphs; those graphs that are separation equivalent to some undirected graph. A graphical characterization of chain graphs that are equivalent to undirected graphs was provided by [27]. Unlike this characterization undirected graphs, our characterization is purely based on the separation properties of the graph. In particular, we introduce the concept of an inducing vertex; a vertex that induces a dependence between separated sets of vertices when added to a separating set. We show that a graph is essentially undirected if and only if it contains no inducing vertex. In addition to its utility in this characterization, we show that the existence of an inducing vertex in a graph provides information about anterior relationships between the inducing vertex and other vertices in the graph. We also provide a characterization of essential graphs in terms of their separation properties. We also provide three characterizations of separable equivalence for separable graphs, describe a canonical representation for the equivalence class of essentially separable graphs, and provide a structure identification algorithm for essentially separable graphical models. The first characterization of separation equivalence is in terms of two graph having the same adjacencies and the same minimal inducing walks. This result is a direct generalization of the characterizations of separation equivalence for directed acyclic graphs [26], chain graphs [7], and ancestral graphs [31] to separable graphs. Our second characterization shows that we only need to consider adjacency and a subset of minimal inducing walks called discriminating inducing walks.
SEPARABLE GRAPHICAL MODELS
3
Our final characterization is given in terms of two separational properties of pairs of vertices; vertex separability and the induced arrowhead property. Our final characterization is that two separable graphs are separation euqivalent if and only if the graphs have the same vertex separability and the same induced arrowheads. This characterization is particularly useful for developing structure identification algorithm as it is a separational characterization which implies that, in principle, an structure identification algorithm using independence tests can identify the equivalence class based only on the properties used in the characterization. Our representation for the equivalence classes of separable graphs relies on this characterization and, particularly, the induced arrowhead property. We show that we can represent the equivalence class of an essentially separable graph by a graph with the same adjacencies as a separable graph in the equivalence class and whose only arrowheads on edges are induced arrowheads. Finally, our structure identification algorithm for essentially separable graphs, the SGI algorithm, relies on identifying separating sets and inducing vertices. The SGI algorithm generalizes the CI and FCI algorithms of [23]. In particular, the CI and FCI algorithms identify the structure of graphical models defined by ancestral graphs, whereas the SGI identifies the structure of a graphical model defined by separable graphs. The algorithm is conceptually simple: the algorithm searches for separating sets for pairs of vertices. If a separating set is found, the edge between the separated vertices is remove edges. Then the separating set is used to identify inducing vertices. If inducing vertices are found, they are are used to orient edges. The algorithm then continues to search for separating sets. We provide sufficient conditions for the algorithm to correctly identify the equivalence class of an essentially separable graph and a polynomial bound on the number of independence tests required. 2. Preliminaries. In this section we introduce the key objects of study in this paper including independence models, statistical independence models induced by probability distributions, vertex independence models induced by mixed graphs, mixed graphical models, and the problem of structure identification of graphical models. 2.1. Independence models. An independence model is a representation of the independencies and dependencies that hold in a system of objects O . Such models are well-studied (e.g., [24]) and used in a variety of contexts including two contexts relevant to this paper; vertex separation in graphs — a system of vertices, and statistical independence in probability distributions — a system of variables. An independence model I = (O, T ) where O is a set of objects where T ⊆ TO is a set of triples and TO is the set of all possible triples (A, B, C) of disjoint subsets of O . For independence model I = (O, T ) and triple (A, B, C), if (A, B, C) ∈ T , then we say that A is independent of B given C and write A ⊥ ⊥I B | C . If ∖ (A, B, C) ̸∈ T then we say A and B are dependent given C and write A ⊥ ⊥ I B | C . For two independence models I = (O, T ) and I ′ = (O′ , T ′ ), we define I ⊆ I ′ if O ⊆ O and T ⊆ T ′ . Finally, we denote the set of all independence models by I . 2.1.1. Independence properties. An independence property is a logical formula of independence and dependence statements where upper-case letters indicate sets of variables, lower-case letters indicate a singleton set of variables and distinct letters in a formula indicate that the sets are disjoint. Furthermore, two or more adjacent letters are used to indicate union of those sets. For instance, BD in the weak union property in Table 1 is used in place of B ∪ D. An independence property holds in an independence model for O if for every possible assignment of disjoint sets of O to letters in the logical formula, the logical formula is a true statement about the independence model. For instance, the symmetry property in Table 1 holds in the independence model I for V if for all (A, B, C) ∈ TV it is the case that
4
if A ⊥ ⊥I B | C then B ⊥ ⊥I A | C . Table 1 contains a set of independence properties that are called the semi-graphoid properties.[15] An independence model I is a semi-graphoid if all of the semi-graphoid properties hold in I . A⊥ ⊥∅|C A⊥ ⊥B|C A⊥ ⊥ BD | C A⊥ ⊥ BD | C A⊥ ⊥ B |C ∧A⊥ ⊥ D | CB
=⇒ B ⊥ ⊥A|C =⇒ A ⊥ ⊥ B |C ∧A⊥ ⊥D|C =⇒ A ⊥ ⊥ B | CD =⇒ A ⊥ ⊥ BD | C TABLE 1 The semi-graphoid independence properties.
trivial symmetry decomposition weak union contraction
Table 2 contains several additional independence properties. An independence model I is a compositional graphoid if the semi-graphoid properties given in Table 1 hold in I and the intersection and composition properties of given in Table 2 hold in I . A⊥ ⊥I B | CD ∧ A ⊥ ⊥I D | CB A⊥ ⊥I B | C ∧ A ⊥ ⊥I D | C A⊥ ⊥I B | C ∧ A ⊥ ⊥I B | Cd
=⇒ A ⊥ ⊥I BD | C =⇒ A ⊥ ⊥I BD | C =⇒ A ⊥ ⊥I d | C ∨ d ⊥ ⊥I B | C TABLE 2 Additional independence properties
intersection composition weak transitivity
2.1.2. Dyadic independence models. Next we provide a useful characterization of the equivalence of two independence models. An independence model I is a dyadic independence model if the trivial, symmetry, composition, and decomposition properties hold in I . The function Pairwise is the independence model projection that maps an independence model to the independence model consisting of all and only the pairwise triples that hold in the given independence model. In particular, Pairwise((O, T )) = (O, { (A, B, C) ∈ T | |A| = 1 ∧ |B| = 1 }). Two independence models I and I ′ are pairwise equivalent if Pairwise(I) = Pairwise(I ′ ). The following proposition shows that for dyadic independence models, equivalence and pairwise equivalence are themselves equivalent.2 P ROPOSITION 2.1. If I and I ′ are dyadic independence models then I and I ′ are equivalent (i.e., I = I ′ ) if and only I and I ′ are pairwise equivalent (i.e., Pairwise(I) = Pairwise(I ′ )). The importance of Proposition 2.1 is that one need only verify pairwise independence facts to guarantee equivalence of any dyadic independence model. 2.2. Distributions and statistical independence models. We use P to denote a probability distribution over variables V and assume that P is from some defining family of probability distributions P .3 Note that we will use V to refer to both a set of vertices in a graph and a set 2
Note that if a theorem, proposition, lemma, or corollary has no citation then its proof can be found in an Appendix. N 3 More formally, the defining family has a common product measurable space ×v∈V Xv , v∈V Fv indexed by V . Typically, one also assumes that there is a common dominating measure but this is not required here.
SEPARABLE GRAPHICAL MODELS
5
of variables. The statistical independence or statistical dependence of two sets of variables given a third set of variables is a property of a distribution. We denote the fact that A and B are independent given C in P by A ⊥ ⊥P B | C and denote the fact that A and B are ∖ dependent given C in P by A ⊥ ⊥ P B | C . We use statistical independence to define the statistical independence model for distribution P as I(P ) = { (A, B, C) ∈ TV | ∀a ∈ A ∀b ∈ B a ⊥ ⊥P b | C }.
A statistical independence model derived from a distribution is guaranteed to satisfy the semi-graphoid independence properties as shown in the following proposition. A proof of this can be found in [24]. P ROPOSITION 2.2. graphoid.
If P is a probability distribution over V then I(P ) is a semi-
2.3. Mixed graphs. The family of mixed graphs G is the family of loop-less mixed multigraphs with the symmetric edges { — , ≺—≻ } and asymmetric edge { —≻ } over a set of vertices V . A graph G = (V, E) ∈ G has a finite set of vertices V and a finite set of edges E ⊆ E = V × T × V where edges have a type t ∈ T = { — , ≺—≻ , —≻ }, there are no loops (i.e., (a, t, a) ̸∈ E ), and the set of edges is symmetric (i.e., if (a, t, b) ∈ E and t ∈ { — , ≺—≻ } then (b, t, a) ∈ E ). The set E is the set of all possible edges with endpoints in V . 2.3.1. Edges and endmarks. An edge (a, t, b) ∈ E connects its endpoints a and b and has edge type t ∈ { −, ≺—≻, —≻ }. A pair of distinct vertices a, b ∈ V in a graph G ∈ G can have up to four distinct edges connecting them and each edge is either an undirected (a — b), a bidirected (a ≺—≻ b), or one of two distinct directed edges (a —≻ b or b —≻ a). An edge that connects a and b is often denoted by e(a, b) or e(b, a). This denotation indicates only the endpoints of the edge but not its type. We also use the letter e, often with a subscript (e.g., ei ) to denote an edge without reference to either its type or its endpoints. We often depict edges both in text and in figures. For instance, if e(a, b) = (a, —≻ , b) ∈ E then we can depict the edge as either a —≻ b or b ≺— a and this is true regardless of whether the edge type is symmetric or asymmetric because the symbols used for symmetric edge types are laterally symmetric and the symbol for the asymmetric edge type is not laterally symmetric. Two vertices a and b are adjacent in a graph if there is an edge that connects them in the graph. We denote the set of vertices adjacent to a vertex b in graph G by Adj(b, G). Each endpoint of an edge in a graph G ∈ G has an endmark which is either an arrowhead or a tail. For instance, the edge a —≻ b has a tail at a and an arrowhead at b. An endmark of a vertex a for an edge e(a, b) in a graph is exclusive if all edges that connect a and b have the same endmark at a. If an exclusive endmark is an arrowhead it is called an exclusive arrowhead and otherwise it is called an exclusive tail. If an edge e(a, b) has an arrowhead at b then we say that the edge is into b and if it has a tail at a we say that the edge is out of a. 2.3.2. Walks: edge sequences, vertex sequences, and section sequences. In this section we define walks in graphs as edge sequences that satisfy particular constraints and define terminology and notation related to walks. We also define the vertex sequence of a walk and the section sequence of a walk. A walk in graph G is an edge sequence in which (i) every terminal edge shares an endpoint with its adjacent edge, and (ii) every internal edge shares one of its endpoints with one of its adjacent edges and its other endpoint with its other adjacent edge. We use lower-case Greek letters ω , γ , and τ both with and without subscripts to denote walks. We will often depict a walk by an alternating sequence of vertices and edge types such as a —≻ b — c.
6
Associated with every walk ω is its unique vertex sequence ver(ω). For instance, the walk ω = a —≻ b — c has vertex sequence ver(ω) = (a, b, c). We use Ver(ω) to denote the set of vertices that appear on a walk. A chord of a walk γ with vertex sequence ver(γ) = (v1 , . . . , vn ) is an edge e(vr , vs ) between a pair of non-consecutive vertices vr an vs . A walk is chordless if it has no chords. We often describe vertices relative to a walk using the following natural definitions. A vertex v is on (or appears on) a walk γ if v is on ver(γ). A vertex v is called an internal vertex on a walk γ if v is an internal vertex of ver(γ). A vertex v is the first vertex of a walk γ if v is the first vertex of ver(γ). A vertex v is the last vertex of a walk γ if v is the last vertex of ver(γ). We use first(γ) and last(γ) to denote, respectively, the first and last vertex of walk γ. A vertex v is called an endpoint of a walk γ is either the first or last vertex of γ . If the first vertex of a walk γ is v1 and the last is vn then the walk γ is between v1 and vn . Also associated with a walk ω is a section sequence sec(ω) = (σ1 , . . . , σm ) such that (i) ver(γ) = σ1 + . . . + σn , (ii) if vertex sequence σi has more than one vertex then ω(σi ) is an undirected walk, (iii) no pair of adjacent sections can be combined to form a longer undirected subwalk of ω ; that is ω(σi−1 + σi ) is not an undirected walk. A section of a walk γ is any vertex subsequence that appears on the section sequence of the walk sec(γ). We use lower-case Greek letters σ and σ ′ both with and without subscripts to denote sections on a walk. Note that we choose to use vertex sequences to represent sections as a section may consist of a single vertex. For instance, for the walk ω = a —≻ b ≺—≻ c every section is a vertex sequence of length one; sec(ω) = ((a) , (b) , (c)). A section σi of a walk ω with sec(ω) = (σ1 , . . . , σm ) is a collider section if 1 < i < m, the edge e(last(σi−1 ), first(σi )) on ω has an arrowhead at first(σi ), and the edge e(last(σi ), first(σi+1 ) has an arrowhead at last(σi ). Any section on a walk that is not a collider section is a non-collider section. Note that the endpoints of a walk are always on non-collider sections. 2.3.3. Types of walks and anterior sets. In this section we define several types of walks, and define anterior and posterior vertex sets that are defined in term of walks in a graph G ∈ G. First we define several type of walk. A walk ω with ver(ω) = (v1 , . . . , vn ) is a circuit if the first and last vertices of the walk are identical (i.e., v1 = vn ).4 A walk is undirected if all of the edges on the walk are undirected edges. A walk γ with vertex sequence ver(γ) = (v1 , . . . , vn ) is an anterior walk if it contains only undirected and directed edges and if the edge e(vi , vi+1 ) on ω is directed then it is oriented vi —≻ vi+1 . A walk ω with vertex sequence ver(ω) = (v1 , . . . , vn ) is a directed walk if it is an anterior walk containing only directed edges. A semi-directed walk is an anterior walk with at least one directed edge. If ω with ver(ω) = (v1 , . . . , vn ) is either a directed walk, anterior walk, or a semi-directed walk then the walk is from v1 to vn . Next we define the concepts of anterior sets in a graph. The vertices anterior to a set of vertices A in graph G is the set Ant(A, G) containing A and all vertices j ∈ V such that there is a anterior walk from j to some vertex a ∈ A. A set of vertices A is an anterior set in a graph G if A = Ant(A, G). A set of vertices A is anterior to a set of vertices B in graph G if A ⊆ Ant(B, G). 2.3.4. Connecting walks and vertex separation. A vertex separation criterion captures the separation properties of a graph and one typically defines a vertex separation criterion in terms of connecting walks in the graph. In this section, we extends previous definitions of 4
Unlike some definitions of circuit, we allow for repeated vertices and repeated edge.
SEPARABLE GRAPHICAL MODELS
7
d-connecting walks to mixed graphs in order to define a vertex separation criterion for mixed graphs. A walk ω between distinct vertices a and b is a connecting walk given C ⊆ V in graph G ∈ G if (1) every collider section of ω has a vertex in C , and (2) no non-collider section has a vertex in C . Note that C cannot contain either endpoint of the walk if the walk is connecting given C . If there is a connecting walk between a and b given C in graph G then a ⊥ ⊥b|C ∖ holds in G. If there is no connecting walk between a and b given C in graph G then a ⊥ ⊥ b|C ∖ ∖ holds in G. If a ⊥ ⊥ b | C holds in G then we write a ⊥ ⊥ G b | C and, otherwise a ⊥ ⊥G b | C . Two vertices a and b in graph G are separated if there is a set C such that a ⊥ ⊥G b | C . 2.3.5. Independence models of mixed graphs. Vertex separation in a graph is then used to define an independence model over the vertices. In particular, the graph independence model for graph G = (V, E) is I(G) = (V, { (A, B, C) ∈ TV | ∀a ∈ A ∀b ∈ B a ⊥ ⊥G b | C }) .
The independence model of a mixed graph satisfies additional independence properties. The following proposition was proved in [21]. P ROPOSITION 2.3. hold in I(G).
If G is a mixed graph then the compositional graphoid properties
In addition, the weak transitivity independence property was shown to hold in mixed graph in [20]. P ROPOSITION 2.4.
If G is a mixed graph then weak transitivity holds in I(G).
2.3.6. Separation equivalence and separation equivalence classes. Separation equivalence and separation equivalence classes play an important role in characterizing graphical models and in identifying their structure. The separation equivalence of two graphs is defined in terms of their independence models as G ≡ G′ if I(G) = I(G′ ).5 Note that the independence model of a graph is decomposable, thus, Proposition 2.1 implies that one only needs to consider walk in order to establish the separation equivalence of two graphs. In particular, two graphs G and H are separation equivalent if and only if (1) if there exists a connecting walk given C in G then there is a connecting walk given C in H , and (2) if there exists a connecting walk given C in H then there is a connecting walk given C in G. The separation equivalence class of a graph is the set of graphs that are separation equivalent to the graph. The equivalence class of a graph G with respect to ≡ relative to a graph family F is the set of graphs [G]F = { G′ ∈ F | G ≡ G′ }. Note that we do not explicitly mention the equivalence relation ≡ when denoting the separation equivalence class of a graph because the only equivalence classes of graphs that we consider are separation equivalence classes. When no family is mentioned the graph family is take to be the set of all mixed graphs G , that is, [G] = [G]G . 5
Separation equivalence is also called Markov equivalence.
8
2.4. Graph properties and graph separation properties. A graph property is a Boolean function of one or more graphs. A graph property f (G1 , . . . , Gk ) is a graph separation property if it can be expressed as a Boolean function of the independence models of the graphs; that is, for some Boolean function h, f (G1 , . . . , Gk ) = h I(G1 ), . . . , I(Gk ) . Such a property depends on each graph only through its induced independence model. Throughout this paper we distinguish between graphical characterizations, which are defined in terms of arbitrary graph properties, and separational characterizations, which are defined in terms of graph separation properties. A key advantage of separational characterizations is that they depend only on the independence models of the graphs and are therefore invariant under separation equivalence. 2.5. Graphical models, separational and statistical equivalence. A graphical model is defined with respect to a defining graph structure G and a defining set of distributions P . A graphical model is a tuple MGP = (G, PG ) such that G ∈ G and PG = { P ∈ P | I(G) ⊆ I(P ) }. If I(G) ⊆ I(P ) we say that P is Markov with respect to G.6 Thus PG represents the set of distributions in P that are Markov with respect to G. We use MG to denote MGP unless the choice of the P is relevant. It is useful to compare graphical models in terms of the independence models of their defining graphs, and the set of distributions that are Markov with respect to their defining graph. Two graphical models MG , MH are separation equivalent if G ≡ H . Two graphical models MG , MH are statistically equivalent if PG = PH . The following proposition relates the separation equivalence and statistical equivalence of graphical models. It follows from the fact that the set of distributions that are Markov with respect to a graph is defined in terms of the independence model of the defining graph. P ROPOSITION 2.5. If two graph are separation equivalent (i.e. F ≡ H ) then MFP is P. statistically equivalent to MH Statistical equivalence can fail to imply separation equivalence if the family of defining distributions is not rich enough to distinguish between graphs that are not separation equivalent. 2.6. Graph families and essential graph families. A graph family F is any subset of the family of mixed graphs G (i.e., F ⊆ G ). In this section we distinguish several types of mixed graphs and notation for the set of graphs of each type. A graph is simple if there is at most one edge between any pair of vertices. The family of simple graphs is Gsimp . A graph is acyclic if it contains no semi-directed circuit and is cyclic otherwise. The family of acyclic graphs is Gacyc . A graph G is maximal if adding any edge between any two non-adjacent vertices in G changes its independence model. The family of maximal graphs is G max . We define essential graph families using the equivalence closure of a generating graph family with respect to separation equivalence. The equivalence closure of a set F ⊆ G with respect to equivalence relation ∼ on G is the set cl∼ (F) = { F ∈ F | ∃G ∈ G, G ∼ F }. The essential graph family generated by F is the set E(F) = cl≡ (F). Equivalently, this is the union of all separation–equivalence classes that intersect F . 6
The relationship I(G) ⊂ I(P ) — all of the separation facts in the graph correspond to independence facts in the distribution — is sometimes referred to as P satisfying the global Markov condition with respect to graph G. Other concepts relating independence in a distribution and separation in a graph exist. See [11] for a discussion of other such relationships between graphs and probability distributions.
SEPARABLE GRAPHICAL MODELS
9
2.7. Comparing the expressivity graph families. We can compare graphical models in terms of their graphical expressivity and their separational expressivity. We compare the graphical expressivity of two graphical model families by comparing the graphs that they contain. For instance, if F ⊂ H then H is more graphically expressive than MF . Thus, the family of chain graphs is more graphically expressive than both the family of undirected and directed acyclic graphs. We compare the separational expressivity of two graph families using the sets of graphs contained in the essential families generated by the two families. If E(F ) ⊂ E(H) then we say that H is more separationally expressive than G. We denote this relationship by F ⊏ H. If E(F) = E(H) then the two families are essentially equivalent and denote the relationship by F ≡ H. Because essential families are defined as the separation-equivalent closure, such settheoretic comparison compare the families of induced independence models associated with the graph family. The implications of essential equivalence for graphical models is considered in the next section. 2.8. Graphical model families. A graphical model family is defined in terms of a defining family of graphs F ⊆ G and a defining family of distributions P . In particular, S the graphical P model family defined by P and F is the set of graphical models MF = G∈F MGP . For instance the family of Gaussian anterial graphical models is the set of models MP Gant if P is the set of all Gaussian probability distributions over the set of variables V . Other types of graphical models are defined by using other defining families of distributions and graphs. We will typically assume that different graphical model families share the same defining family of distributions P and use, for instance, MF to denote MP F. We compare the statistical expressivity of two graphical model families using the set of models that they define. We use the relations ≡ and ⊑ to compare statistical expressivity. These relations are defined as follows MF ≡ M H
if
Models(MF ) = Models(MH )
MF ⊏ M H
if
Models(MF ) ⊂ Models(MH )
where Models(MH ) = { PH | (H, PH ) ∈ MH }. If MF ≡ MH then the two graphical model families are modeling equivalent. If MF ⊏ MH then MH is more statistically expressive than MF . The following proposition captures the implication that the essential equivalence of two graph families on the statistical expressivity of the graphical model families that they define. The proposition follows from the fact that essentially equivalent graph families have the same graphs modulo separation equivalence and Proposition 2.5. P ROPOSITION 2.6. If two graph families are essentially equivalent (i.e, F ≡ H) then for any defining family P , the graphical model families that they define are modeling equivalent P (i.e., MP F ≡ MH ). 2.9. Structure identification algorithms and identification. The goal of a structure identification algorithm is to identify graphical properties of the structure of a generating graph G∗ given an observed distribution P ∗ .7 In this paper we focus on independence test based 7
It is also natural to consider a structure identification algorithm that takes data sampled from a generative distribution as input. Assuming that we observe the generative distribution allows us to focus on identification rather than other notions of correctness like asymptotic consistency or rates of identification.
10
structure identification algorithms in which one uses only the results of statistical independence tests to identify the structure of G∗ . This type of structure identification algorithm is often called a constraint-based learning algorithm. Furthermore, we choose to represent the identified structure of G∗ with a graph. Thus, our focus is on graphical structure identification algorithms, where a graphical structure identification algorithm is a function l ∈ I 7→ G that maps the independence model I(P ∗ ) to a graph G ∈ G . We begin by noting that two separation equivalent graphs cannot be distinguished by a graphical structure identification algorithm. This is due to the fact that a graphical structure identification algorithm is invariant under separation equivalence. In other words, the two separation equivalent graphs have equivalent independence models (i.e., I(G) = I(H)) which implies that any graphical structure identification algorithm applied to these independence models will result in identical graphs (i.e., l(I(G)) = l(I(H))). Thus separation equivalent graphs are indistinguishable based on statistical independence tests. Thus, a graphical structure identification algorithm can only hope to distinguish separation equivalence classes of graphical models. In order for a graphical structure identification algorithm to correctly identify the separation equivalence class of a generating graph G∗ we need to make identifying assumptions connecting I(P ∗ ) and I(G∗ ). A typical assumption between P ∗ and G∗ is the Markov assumption. A distribution P ∗ is Markov with respect to G∗ (i.e., P ∈ PG ). The Markov assumption, however, is not sufficient to guarantee the identification of the equivalence class of the generating graph. The assumption only guarantees that I(G∗ ) ⊆ I(P ∗ ). If, for instance, there is a product distribution8 P ∈ P then P ∈ PG for all G ∈ F . Thus, if the generative distribution P ∗ is a product distribution, all graphical structures are indistinguishable if one only assume that P ∗ is Markov with respect to G∗ . Thus, in order to identify the equivalence class of the generating graph G∗ , one must make an additional compatibility assumption between P ∗ and G∗ generally, or between I(P ∗ ) and I(G∗ ) in the case of an independence test based structure identification algorithm. Such an assumption must ensure that at least some additional dependence facts hold in P ∗ . The typical assumption (e.g., [23]) is that P ∗ is Markov and faithful with respect to G∗ or equivalently that P ∗ is perfect with respect to G∗ . A probability distribution P ∗ is perfect with respect to G∗ if I(P ∗ ) = I(G∗ ). A weaker assumption that is appropriate for a graphical structure identification algorithm is perfect testing, where one assumes that, for any (A, B, C) considered during the execution of the algorithm, the result of statistical independence tests on P ∗ matches the result of a separation test on G∗ (i.e., A ⊥ ⊥I(P ∗ ) B | C if and only if ∗ A⊥ ⊥I(P ∗ ) B | C ). In this case we say P provides perfect testing for G∗ with respect to a graphical structure identification algorithm. The sufficiency of the perfect testing assumption for identifying the equivalence class of G∗ for any graph family F is due to the fact that G ≡ H is defined as I(G) = I(H). Thus, if a graphical structure identification algorithm uses enough statistical tests it can distinguish graphs that are not separation equivalent. Finally, we define when a graphical structure identification algorithm identifies the separation equivalence class of a graph family given a probability distribution under some compatibility condition. A compatibility condition is a Boolean function of a distribution and a graph; a function in P × G 7→ { True, False }. A graphical structure identification algorithm l ∈ I 7→ G identifies the separation equivalence class of a graph family F given P ∗ ∈ P under compatibility condition C if for all G∗ ∈ F and for all P ∗ ∈ P it is the case that if C(P ∗ , G∗ ) then l(I(P ∗ )) ≡ G∗ . 8
vi .
A distribution is a product distribution if P (V ) =
Q
vi ∈V P (vi ) where P (vi ) is the marginal distribution of
SEPARABLE GRAPHICAL MODELS
11
3. Separable graphs. A graph G is separable if every pair of non-adjacent vertices is separable. The family of separable graphs is denoted by Gsep . In this section, we provide a characterization of separable graphs and of separable vertices in mixed graphs. The existence of separating sets is closely connected to the adjacency properties of a mixed graph. Recall that C is a separating set for two vertices i and j in graph G if i ⊥ ⊥G j | C and that that two vertices i and j are separable in graph G if there is a separating set C . The following propositions capture the fact that the existence of a separating set for two vertices implies that the two vertices are not adjacent. This proposition follows from the fact that two vertices that are adjacent cannot be separated by any separating set. P ROPOSITION 3.1.
If i and j are separable in G then i ̸∈ Adj(j, G).
The lack of a separating set for a pair of two vertices, however, does not imply the existence of an edge between the two vertices. Consider the pair of vertices (b, c) in Graph G2 in Figure 1. These vertices are not separable and thus Graph G2 is not separable. One can verify that there is no separating set for this pair of vertices by exhaustively considering the possible separating sets. The following theorem characterizes when two vertices are separable in a graph and provides a more direct approach to verifying that two vertices are separable. T HEOREM 3.2. [Pairwise anterior separation] Two vertices i and j are separable in graph G if and only if i ⊥ ⊥G j | Ant({ i, j }, G) \ { i, j }. This characterization of vertex separability generalizes the characterization of [10] from chain mixed graphs to mixed graphs. Again considering vertices (b, c) in Graph G2 , we can ∖ see that b ⊥ ⊥ G2 c | ade which implies, by Theorem 3.2, that b and c are not separable. In order to characterize separable graphs we consider two types of walks: collider walks and inducing walks. A collider walk is a walk in which all internal vertices on the walk are on collider sections of the walk. Note that this implies that the endpoints of a collider walk are the only vertices on non-collider sections of the walk. A collider walk is trivial if it contains no collider sections and it is non-trivial otherwise. Any walk consisting of a single edge is a trivial collider walk. A collider walk in a graph is an inducing walk if there is no edge in the graph between the endpoints of the walk. Note that an inducing walk must have at least one internal vertex and thus a walk consisting of a single edge is not an inducing walk because it has no internal vertices. Inducing walks are important with respect to separability due to the fact that they can induce dependence between vertices that are not adjacent. They also play an important roll in other results in the paper including one of our characterizations of separation equivalence. The next theorem characterizes separable graphs in terms of whether the graph contains a self-inducing walk. A self-inducing walk is an inducing walk such that every collider section is anterior to one of the endpoints of the inducing walk.9 T HEOREM 3.3.
A graph is separable if and only if it contains no self-inducing walks.
This characterization generalizes the results of [10] and [18] to the family of mixed graphs. The graph G1 in Figure 1 is an example of a separable graph. Separability can be verified by the separation facts b ⊥ ⊥G1 e | d, a ⊥ ⊥ G1 b | ∅ , a ⊥ ⊥G1 d | ∅ and a ⊥ ⊥G1 e | ∅. 9 A self-inducing walk is closely related to both the primitive inducing path of [18] and the primitive inducing walk of [10]. In fact, if either a primitive inducing path or primitive inducing walk has no edge between its endpoints then it is a self-inducing walk.
12
F IG 1. Separable graph G1 and essentially separable graph G2 that is not separable.
4. Essentially separable graphs. A graph G is essentially separable if there is a graph G′ ≡ G such that G′ is separable. Thus, the family of essentially separable graphs is the essential graph family E(Gsep ) generated by separable graphs. When considering graphical models defined by graphs, if a graphical model is defined in terms of a essentially separable graph then there is a statistically equivalent graphical model that is defined in terms of a separable graph. Graph G2 in Figure 1 is not separable. This follows from Theorem 3.3 and the fact that the walk b —≻ d ≺—≻ c is a self-inducing walk. The graph, however, is essentially separable. In particular, if edge b ≺—≻ c is added to this graph then one obtains graph G1 , an equivalent separable graph. The equivalence can be verified by enumerating the separation facts for the two graphs. For acyclic graphs, a graph is separable if and only if it is maximal (see, Corollary 2 of [10]). This correspondence, however, fails for mixed graphs as illustrated by Graph G3 of Figure 2. This graph is an example of a cyclic graph that is maximal but not essentially separable. Graph G3 is not separable due to the fact that b —≻ d ≺— c is a self-inducing walk and Theorem 3.3. Note a —≻ e ≺— d is also a self-inducing walk. To see that the graph G3 has no equivalent separable graph we start by noting that two separation facts are true in graph G3 : (1) a ⊥ ⊥G3 b | ∅ and (2) a ⊥ ⊥G3 b | cd. Suppose there is a separable graph G′3 that is ′ equivalent to G3 . Graph G3 must have an edge e(b, c) and an edge e(a, c). If e(b, c) has a tail at c or e(a, c) has tail c in G′3 then fact (1) would not be true. However, if both edges have arrowheads at c then fact (2) would not hold. Thus, no such separable graph G′3 equivalent to G3 exists.
F IG 2. A graph that is not essentially separable and maximal.
SEPARABLE GRAPHICAL MODELS
13
Next we show that graph G3 is maximal. No edge e(a, b) can be added due to the fact that a and b are separable due to (e.g.) separation fact (1). We have shown above that no edge e(b, c) can be added so the only other edges that could be added is the edge e(a, d). Consider adding an edge e(a, d) to the graph. If e(a, d) has a tail at d or e(b, d) has a tail at d in G′3 then fact (1) would not be true. However, if both edges have arrowheads at d then fact (2) would not hold. Thus, no such separable graph G′3 equivalent to G3 exists. Thus, no such edge can be added to the graph and G3 is maximal. In the remainder of the paper we provide results about separable and essentially separable families of graphs and the graphical models defined by these graph families. 5. Graphical characterization of essentially separable graphs. In this section we provide a graphical characterization of essentially separable graphs. Furthermore, we show that any graphical models defined in terms of an essentially separable model has an equivalent graphical model defined in terms of a simple acyclic graphs called an anterial graph. A graph G is essentially acyclic if there is an acyclic graph G′ that is separation equivalent to G. Thus the family of essentially acyclic is the essential graph family E(Gacyc ) generated by acyclic graphs. A graph that is not essentially acyclic is essentially cyclic. Consider graphs G4 and G5 from Figure 3. The two graphs are separation equivalent as a is separated from d given bc in both graphs, b is separated from c given ad in both graphs, and these are the only separation facts that hold in these graphs.
F IG 3. A cyclic graph G4 and an equivalent acyclic graph G5 .
The next theorem provides a characterization of essentially separable graphs as those graphs that are essentially acyclic. T HEOREM 5.1. acyclic.
A graph is essentially separable if and only if the graph is essentially
The graph G3 from Figure 2 is essentially cyclic. This follows from Theorem 5.1 and the fact that G3 is not essentially separable. The following corollary of Theorem 5.1 shows that, separable graphical models ME(Gsep ) and acyclic graphical models MGacyc are modeling equivalent. C OROLLARY 5.2.
ME(Gsep ) ≡ MGacyc .
Next we define Anterialize algorithm that converts a graph to an anterial graph. An anterial graph is a simple mixed graph G such that (1) G has no semi-directed circuits, and (2) if i ≺—≻ j then i ̸∈ Ant(j, G) and j ̸∈ Ant(i, G). We denote the family of anterial graphs by
14
Gant ⊆ Gsimp ∩ Gacyc . The graph G1 in Figure 1 is an example of a separable graph that is not an anterial graph but is simple and acyclic. The graph G1 is not anterial due to the existence of the edge c ≺—≻ d such that d ∈ Ant(c, G). The Anterialize algorithm is shown in Algorithm 1. We denote the graph obtained by applying Algorithm 1 to graph G by Anterialize(G). The graph Anterialize(G) is a simple graph with the same adjacencies as G such that an edge e(i, j) in Anterialize(G) has a tail at i if and only if there is an anterior walk from i to j in G. Consider applying the Anterialize algorithm to graph G4 of Figure 3. Consider the directed edge a —≻ c. Due the fact that there is an anterior walk from c to a (i.e., c ∈ Ant(a, G)) and an anterior walk from a to c (the edge it self), the edge e(a, c) in Anterialize(G4 ) must be a — c. By a similar argument, all of the edges must be undirected and the result Anterialize(G4 ) is the graph G5 also from Figure 3.
Algorithm 1 The Anterialize algorithm Input: A graph G = (V, E). Output: An anterial graph. E′ = ∅ for each edge e(i, j) ∈ E do if i ∈ Ant(j, G) and j ∈ Ant(i, G) then E′ = E′ ∪ { i — j } else if i ∈ Ant(j, G) then E ′ = E ′ ∪ { i —≻ j } else if j ∈ Ant(i, G) then E ′ = E ′ ∪ { i ≺— j } else E ′ = E′ ∪ { i ≺—≻ j } return V, E ′
The following theorem proves that that every separable graph has an equivalent anterial graph and that such a graph can be obtained using the Anterialize algorithm. T HEOREM 5.3. For every graph G, the graph Anterialize(G) is an anterial graph; if G is a separable graph then Anterialize(G) is a separable graph and G ≡ Anterialize(G). Theorem 5.3 has significant implications about the statistical expressivity of graphical sep models defined using the family of separable anterial graphs Gant that is captured in the following corollary. C OROLLARY 5.4.
sep . ME(Gsep ) ≡ MGant
Corollary 5.4 shows that the family of essentially separable graphical models is modeling equivalent to the family of separable anterial graphical models. This is notable as anterial graphs are simple acyclic graphs which, from a computational perspective, allows structure identification algorithm that seek to identify the equivalence class of an essentially separable graph to focus on simple graphs rather than multigraphs. 6. Separational characterizations of essential graph families. In this section we give separational characterizations of three essential graph families (defined in Section 2.6): essentially separable graphs (Section 4), essentially acyclic graphs (Section 5), and essentially undirected graphs, the essential family E(Gund ) generated by the family of undirected graphs.
SEPARABLE GRAPHICAL MODELS
15
We use separational characterizations because they are invariant under separation equivalence (see Section 2.4). This ensures that each characterization applies uniformly to all graphs in an essential family and clarifies the separation structure shared by the graphs in these families. Many familiar graph properties are not invariant under separation equivalence. For example, in Section 4 we observed that adjacency is not invariant, and in Section 5 we observed that acyclicity and undirectedness are also not invariant. Indeed, each of the essential graph families considered here is generated from a graph family defined by properties that fail to be invariant under separation equivalence. We begin by characterizing essentially undirected graphs. A fundamental distinction between undirected graphs and, for instance, directed graphs, is that adding a vertex to a separating set for two vertices in a directed graph can induce a dependence between the two vertices. The simplest example of this phenomena is the graph i —≻ k ≺— j with three ver∖ tices and two edges in which i ⊥ ⊥G j | ∅ and i ⊥ ⊥ G j | k . In this example, the vertex k induces dependence between i and j given the empty set. We call vertex k an inducing vertex. It is useful to generalize the concept of an inducing vertex by defining the concept of an inducing object in an independence model and by considering sets of objects that induce dependence. An object d ∈ O is an inducing object for (A, B, C) ∈ TO in independence model ∖ I for O if both A ⊥ ⊥I B | C and A ⊥ ⊥ I B | Cd. The inducing objects for (A, B, C) ∈ TO in in∖ dependence model I is the set IV(A, B, C, I) = { d ∈ O | A ⊥ ⊥I B | C ∧ A ⊥ ⊥ I B | Cd }. We say that d ∈ O is an inducing object in independence model I for O if there exists (A, B, C) such that d is an inducing object for (A, B, C) in I . Next we generalize to consider sets of objects that induce dependence. A set of objects D ⊆ O is an inducing set for (A, B, C) ∈ TO in independence model I for O if both A ⊥ ⊥I ∖ B | C and A ⊥ ⊥ I B | CD . The inducing sets for (A, B, C) ∈ TO in independence model I is ∖ the set of sets IS(A, B, C, I) = { D ∈ 2O | A ⊥ ⊥I B | C ∧ A ⊥ ⊥ I B | CD }. The existence of an inducing set in an independence model allows one to infer the existence of additional dependence facts. Consider the induced dependence property: ∖ ∖ ∖ A⊥ ⊥I B | C ∧ A ⊥ ⊥ I B | CD =⇒ A ⊥ ⊥ I D | CB ∧ D ⊥ ⊥ I B | CA. As described in the next proposition, the induced dependence property is guaranteed to hold in any semi-graphoid independence model. P ROPOSITION 6.1. pendence model.
The induced dependence property holds in any semi-graphoid inde-
Due to Propositions 2.2 and 2.3, the induced dependence property holds for both statistical independence in probability distributions and vertex separation in mixed graphs. Furthermore, if we consider, inducing sets of size one (i.e., |D| = 1) then the induced dependence property is a statement about the properties of inducing objects (e.g., inducing vertices or inducing variables). For instance, in the context of mixed graphs, the induced dependence property can be used to guarantee the existence of connecting walks from the existence of an inducing vertex. Vertex d being an inducing vertex for sets A and B given set C implies the existence of two connecting walks, one starting at a vertex in A and the other starting at a vertex B with both terminating at d. The following theorem provides a characterization of essentially undirected graphs in terms of the existence of inducing vertices in the induced independence model of the graph. T HEOREM 6.2. inducing vertex.
A graph G is essentially undirected if and only if I(G) contains no
16
We illustrate this proposition with two examples. Consider graphs G4 and G5 from Figure 3. As described in Section 5, the two graphs are separation equivalent. This implies that G4 is essentially undirected and, by Theorem 6.2 graph G4 has no inducing vertices. Next consider graph G6 and G7 from Figure 4. The two graphs are separation equivalent and thus, Theorem 6.2 implies that G6 has no inducing vertices. This example illustrates that the graphical condition given by [27] for a chain graph to have no equivalent undirected graph is not appropriate for mixed graphs.
F IG 4. An essentially undirected graph G6 and an equivalent undirected graph G7 .
Next we consider ordering information in graphs and how it relates to inducing vertices in graphs. We use ⪅ to denote a preorder over a set; a preorder is a binary relation that is transitive and reflexive. We use the following notation for the derived relations (i) a ≈ b if a ⪅ b and b ⪅ a, (ii) a < b if a ⪅ b and b ̸⪅ a, (iii) a ∥ b if a ̸⪅ b and b ̸⪅ a, and (iv) a ⋎ b if a ⪅ b or b ⪅ a. We use a preorder ⪅ over V to define functions from subsets of V to subsets of V . In particular, V⪅A = { b ∈ V | ∃a ∈ A, b ⪅ a }, V⪆A = { b ∈ V | ∃a ∈ A, b ⪆ a }, and [A]≈ = { b ∈ V | ∃b ∈ A, b ≈ k }. Preorders arise naturally when considering graphs. The induced preorder of a graph G is denote ⪅G and defined as a ⪅G b if a = b or there is an anterior walk from b to a in G, that is b ∈ Ant(a, G). The relation ⪅G for graph G = (V, E) is a preorder on V as reflexivity is guaranteed by the definition and anterior walks can be appended to show transitivity. Note that the relation a ≈G b implies that either a = b or the existence of anterial walks from a to b and from b to a in graph G. We begin by noting that the existence of an inducing set in a graph provides information about anterior relationship between the inducing set and other vertices in the graph. P ROPOSITION 6.3. lently D ̸⊆ V⪆Cij ).
If D ∈ IS(A, B, C, G) then D ∩ Ant(C ∪ { i, j }, G) ̸= ∅ (or equiva-
It often simpler to consider inducing vertices. The following property is the specialization of the Proposition 6.3 to inducing vertices. P ROPOSITION 6.4. b∈ / V⪆Cij ).
If b ∈ IV(i, j, C, G) then b ̸∈ Ant(C ∪ { i, j }, G) (or equivalently
Next we consider the relationship ≈G induced by a graph G and show that any pair of vertices a ≈G b is also equivalent with respect to membership in sets of inducing vertices in the induced independence model of G. An independence model I satisfies the inducing vertex equivalence property with respect to ⪅ if for all vertices a, b ∈ V , if a ≈ b then for all i, j ∈ V and C ⊆ V , it holds that a ∈ IV(i, j, C, I) if and only if b ∈ IV(i, j, C, I).
SEPARABLE GRAPHICAL MODELS
17
P ROPOSITION 6.5. For any graph G, the inducing vertex equivalence property holds in I(G) with respect to ⪅G . Consider the following property that generalizes the inducing vertex equivalence property to inducing sets. An independence model I satisfies the inducing set equivalence property with respect to ⪅ if for all vertices d ∈ V and all non-empty sets D, E ⊂ V , such that E, D ⊆ [d]G ≈ , and all i, j ∈ V and C ⊆ V , it holds that D ∈ IS(i, j, C, I) if and only if E ∈ IS(i, j, C, I). The inducing set equivalence property, unlike the inducing vertex equivalence property, is not guaranteed to hold in all graphs. For instance, consider Graph G3 of Figure 2. In this graph, [c]≈ = { c, d, e } = IV(a, b, ∅, G3 ) which illustrates Proposition 6.5. The fact that a⊥ ⊥G3 b | cde shows that the inducing set property does not hold. T HEOREM 6.6. G is essentially separable if and only if I(G) satisfies the inducing set equivalence property with respect to ⪅G . The following corollary of Theorem 6.6 follows from Theorem 5.1. C OROLLARY 6.7. G is essentially acyclic if and only if I(G) satisfies the inducing set equivalence property with respect to ⪅G . As shown in subsequent sections, inducing vertices and derived concepts like induced arrowheads are also useful for developing separational characterizations of the separation equivalence of separable graphs (Section 8), representing the equivalence classes of separable graphs (Section 9), and identifying essentially separable graphs (Section 10). 7. Graphical characterizations of separation equivalence. In this section we provide two graphical characterizations of the separation equivalence of two graphs. First we show that two separable graph are separation equivalent if and only if they have the same adjacencies and same minimal inducing walks. This characterization is a direct generalization of the characterizations of separation equivalence for directed acyclic graphs [26], chain graphs [7], and ancestral graphs [31] to separable graphs. We begin by defining the property of two graphs having the same adjacencies. Two graphs have the same adjacencies if for every edge in one graph there is a corresponding edge with the same endpoints in the other graph and vice versa. Note that the definition of same adjacencies does not require the corresponding edges to be of the same type. In other words, only the endpoints of the edges matter and not their endmarks. Next we define the property of two graphs having the same minimal inducing walks. We define the property based on an equivalence relation over collider walks rather than walk equality.10 To motivate the need to introduce an equivalence relation, consider the graph a ≺—≻ b ≺—≻ c and the graph a —≻ b ≺— c. These two graphs are separation equivalent but their sets of minimal inducing walks are disjoint. Thus, in order to characterize separation equivalence we need to introduce an equivalence relation. In particular, two collider walks γ and ω are equivalent γ ≡ ω if ver(γ) = ver(ω) and sec(γ) = sec(ω) or ver(rev(γ)) = ver(ω) and sec(rev(γ)) = sec(ω) where rev(γ) is the walk with the same edges as γ but the opposite traversal order. Two graphs have the same minimal inducing walks if for every minimal inducing walk ω in one graph there is a corresponding minimal inducing walk ω ′ such that ω ≡ ω ′ and vice versa. 10
We extend this equivalence relation to all walks in Appendix B.5.
18
T HEOREM 7.1. Two separable graphs are equivalent if and only if they have the same adjacencies and same minimal inducing walks. We illustrate this theorem with two examples. Let MIW(G) be the set of minimal inducing walks in a graph G. Consider graphs G4 and G5 , from Figure 3. The two graphs have the same adjacencies and MIW(G4 ) = MIW(G5 ) = ∅. Thus, by Theorem 7.1, G4 ≡ G5 . Next consider the graph G1 from Figure 1 and graph G8 from Figure 5. These two graphs have the same adjacencies and MIW(G1 ) = {a —≻ c ≺—≻ b, a —≻ c ≺—≻ d, a —≻ c ≺— e} ≡ {a —≻ c ≺— b, a —≻ c ≺— d, a —≻ c ≺— e} = MIW(G8 ). Thus, by Theorem 7.1, G1 ≡ G8 .
F IG 5. Separable graph G8 is equivalent to graph G1 of Figure 1.
Next we present a useful characterization of separation equivalence and describe a useful property related to this characterization. This characterization is refinement of the first characterization where we compare minimal discriminating inducing walks rather than minimal inducing walks. In order to define minimal discriminating inducing walks, we need a few additional definitions. A section on an inducing walk is discriminated if the section is not anterior to either endpoint of the inducing walk. An inducing walk discriminates a collider section if the section is discriminated by the walk. An inducing walk is a (simple) discriminating inducing walk if it contains exactly one discriminated section and a compound discriminating inducing walk if it contains more than one discriminated section. Note that an inducing walk containing no discriminated sections is a self-inducing walk. Two graphs have the same minimal discriminating inducing walks if for every minimal discriminating inducing walk ω in one graph there is a corresponding minimal discriminating inducing walk ω ′ such that ω ≡ ω ′ and vice versa. T HEOREM 7.2. Two separable graphs are equivalent if and only if they have the same adjacencies and the same minimal discriminating inducing walks. For the graphs G8 from Figure 5 and G1 from Figure 1 the set of minimal inducing walks and the set of minimal discriminating inducing walks are identical, that is, every minimal inducing walk in these graphs is also a minimal discriminating inducing walk. The next proposition shows that discriminated sections of minimal discriminating inducing walks contain inducing vertices and that all other vertices are not inducing vertices. P ROPOSITION 7.3. If walk ω between a and b is a discriminating inducing walk that discriminates collider section σ in graph G and C separates a and b in G then every vertex on σ is in IV(a, b, C, G) and every other vertex on ω is not in IV(a, b, C, G). This proposition along with Proposition 6.4 play an essential role in proving that our structure identification algorithm identifies all required arrowheads.
SEPARABLE GRAPHICAL MODELS
19
8. Separational characterization of separation equivalence. In this section we show that two separable graphs are separation equivalent if and only if they have the same vertex separability and same induced arrowheads. We begin by defining the property of two graphs having the same vertex separability. Two graphs have the same vertex separability if, for every pair of vertices, the pair is separable in one graph if and only if it is separable in the other. This property is useful because it is a graph separation property that, when the graphs are assumed separable, is equivalent to the graphical condition that the graphs have the same adjacencies. Consequently, the separational property of same vertex separability can replace the graphical property of same adjacency in Theorems 7.1 and 7.2. Next we define the property of two graphs having the same induced arrowheads. The induced arrowheads of a graph are defined in terms of the vertex property of being an inducing vertex defined in Section 6, and two properties of pairs of vertices: vertex separability and the arrowhead inducing property. A pair of vertices (b, d) is arrowhead inducing at b if there exists i, j, C such that b ∈ IV(i, j, C, G) and d ̸∈ IV(i, j, C, G). A pair of vertices (a, b) has an induced arrowhead at b if the pair is arrowhead inducing at b and the pair is not vertex separable. The induced arrowhead property of a pair of vertices is a graph separation property as the property of begin an inducing vertex and vertex separability are both graph separation properties. Note that the definition of an induced arrowhead due to the fact it is a graph separation property, makes no mention that an edge has an arrowhead endmark. The following proposition, shows that, despite this property, the existence of an induced arrowhead on an edge in a graph implies the existence of an exclusive arrowhead on that edge. P ROPOSITION 8.1. If an edge e(d, b) in a graph G has an induced arrowhead at b then the edge has an exclusive arrowhead at b in G. Two graphs G and G′ have the same induced arrowheads if for every pair of vertices (a, b) in G, the pair has an induced arrowhead at b in I(G) if and only if the pair has an induced arrowhead at b in I(G′ ). Note that the property is separational, that is, it is defined in terms of graph separation properties of the two graphs. T HEOREM 8.2. Two separable graphs are equivalent if and only if they have the same vertex separability and same induced arrowheads. We illustrate this theorem with two examples. Consider graphs G4 and G5 , from Figure 3. The two graphs have the same adjacencies and neither graph has any induced arrowheads. Thus, by Theorem 8.2, G4 ≡ G5 . Next consider graph G1 from Figure 1 and graph G8 from Figure 5. These two graphs have the same adjacencies and both graphs have the same four induced arrowheads: an induced arrowhead at c on edges e(a, c), e(b, c), e(d, c), and e(d, c). Thus, by Theorem 8.2, G1 ≡ G8 . Finally, we note that, unlike the characterizations in Section 7, this characterization is not graphical, but rather separational, in the sense that it can be defined purely in terms of the induced independence models of the two graphs. The fact that this characterization, and the definitions of same vertex separability and same induced arrowheads are separational is useful for developing structure identification algorithms that use statistical tests of independence. In particular, this allows for the identification of adjacencies and arrowheads sufficient to identify the equivalence class of a graph from statistical tests under suitable assumptions.
20
9. Representing equivalence classes of separable graphs. In Algorithm 2 we define the InducedArrowheads algorithm that takes a mixed graph and returns a mixed graph with the same adjacencies while preserving arrowheads on edges only if they have induced arrowheads. Algorithm 2 InducedArrowheads Input: A graph G = (V, E). Output: A simple graph. E′ = ∅ for each e(i, j) ∈ E do if edge e(i, j) has induced arrowheads at i and j then E ′ = E ′ ∪ { i ≺—≻ j } else if edge e(i, j) has an induced arrowhead at i then E ′ = E ′ ∪ { i ≺— j } else if edge e(i, j) has an induced arrowhead at j then E ′ = E ′ ∪ { i —≻ j } else E ′ = E′ ∪ { i — j } return V, E ′
We illustrate the InducedArrowheads algorithm by applying it to Graph G1 of Figure 1. The result is Graph G8 shown in Figure 5. The graph has the same adjacencies at G1 . Each of the arrowhead endmarks on an edge is an induced arrowhead on the edge. For instance, the edge a —≻ c has an induced arrowhead at c due to the facts that c ∈ IV(a, b, ∅, G) and a ̸∈ IV(a, b, ∅, G). Next we consider properties of the InducedArrowheads algorithm. First we establish that the InducedArrowheads algorithm preserves separation equivalence if applied to a separable graph. T HEOREM 9.1.
If G is separable then G and InducedArrowheads(G) are equivalent.
Next, we consider different types of representations of equivalence classes of graph. The equivalence class of a ∈ A given equivalence relations ≡ is denoted [a]≡ A but we use [a]A when the equivalence relation is clear from context. A function f ∈ A 7→ B is a canonical representation function for equivalence classes of A with respect to ≡ if it is the case that a ≡ a′ if and only if f (a) = f (a′ ) for all a, a′ ∈ A. A function f ∈ A 7→ A is a projection if f (f (a)) = f (a) for a ∈ A. A function f ∈ A 7→ A is a canonical projection for A with respect to equivalence relation ≡ if f is a projection and, for a ∈ A, it holds that f (a) ≡ a. Thus, a canonical projection is a type of canonical representation. Furthermore, showing that a function is a canonical representation function does not require showing f (a) ≡ a. The following theorem shows that the InducedArrowheads function is a canonical projection. T HEOREM 9.2. The InducedArrowheads algorithm is a canonical projection for separable graphs with respect to separation equivalence. We relate the InducedArrowheads representation of an equivalence class of separable graph to a generalization of the concept of the largest graph to mixed graphs. The concept of the largest chain graph was introduced in [7]. A graph G′ is a largest equivalent simple graph of G if G′ ≡ G and G′ is simple and G′ has the largest number of tail endmarks of any simple separable graph equivalent to G. Let Largest(G) be the set of largest equivalent graphs to G.
SEPARABLE GRAPHICAL MODELS
21
Frydenberg showed that for chain graphs, every equivalence class contains a unique largest graph that is equivalent to the members of the equivalence class. The next corollary follows directly from Theorem 9.2 — the fact that InducedArrowheads is a canonical projection — and generalizes Frydenberg’s uniqueness result to separable graphs. C OROLLARY 9.3. If G is a separable graph then Largest(G) contains a unique graph which is the graph InducedArrowheads(G). Finally, we related the InducedArrowheads representation of an equivalence class to anterial graphs. C OROLLARY 9.4. graph.
If G is a separable graph then InducedArrowheads(G) is an anterial
10. Identifying essentially separable graphs. In this section, we develop the SGI algorithm, a constraint-based graphical structure identification algorithm that uses only independence tests. We show that SGI identifies the separation-equivalence class of essentially separable graphs under perfect testing and provide a bound on the number of independence tests required. The SGI algorithm is shown in Algorithm 3. The algorithm outputs a simple graph G as a representation for an equivalence class of essentially separable graphs. The use of a simple graph is justified by Corollary 5.4. Algorithm 3 The SGI Algorithm Input: Independence model I for variables V . Output: A simple mixed graph over V . E ← { vi — vj | { vi , vj } ⊆ V ∧ vi ̸= vj } G ← (V, E) ▷ Initialize to be a simple undirected complete graph. socs ← 0 ▷ socs is current size of conditioning sets. while socs < SepSetBound(G) do for pair (i, j) ∈ V × V do if i ∈ Adj(j, G) then candidates ← Ant(i, G) ∪ Ant(j, G). for C ⊆ candidates such that |C| = socs do if i ⊥ ⊥I j | C then ▷ Check if C is a separating set Remove edge between i and j in G. IV = ∅ for k ∈ V \ (C ∪ { i, j }) do ▷ Find inducing vertices for i, j, C ∖ if i ⊥ ⊥ I j | Ck then ▷ Check if k is an inducing vertex IV = IV ∪{ k } for k ∈ IV do ▷ Use Orientation Rule 1 for l ∈ Adj(k, G) do if l ̸∈IV then Change endmark at k on e(l, k) to an arrowhead. socs ← socs + 1 ▷ Try larger conditioning sets. return G
We begin with an overview of the algorithm. The SGI algorithm starts with a simple complete undirected graph G, that is, a graph in which all edges are undirected and there is an undirected edge between every pair of vertices. The algorithm systematically searches for separating sets C of increasing size for pairs of adjacent variables i and j and uses independence model I = I(P ∗ ) to test whether i ⊥ ⊥I j | C . If the test determines that i and j
22
are separated by C then the edge between i and j is removed. The algorithm then identifies the inducing vertices IV(i, j, C, I) and uses them to add arrowhead endmarks to existing edges. The algorithm continues to try to remove edges until it has considered separator sets of sufficient size. Unlike many independence test based graphical structure identification algorithms, the SGI algorithm adds orientation information and determines the adjacency structure concurrently and uses this orientation information to restrict the search for separating sets. In particular, the SGI algorithm implicitly uses the following induced arrowhead identification rule to add arrowheads to the current representation G. O RIENTATION RULE 1 (Induced arrowhead identification rule). If there is an edge e(k, l) in simple graph G such that there exists vertices i and j and vertex set C such that k ∈ IV(i, j, C, I) and l ̸∈ IV(i, j, C, I), change the endmark at k on e(k, l) to be an arrowhead. The induced arrowhead identification rule is a sound orientation rule under the assumption that I = I(P ∗ ) provides perfect testing for an essentially separable graph G∗ . This is due to the fact that induced arrowheads are exclusive arrowheads (Proposition 8.1). Note that the algorithm uses previously identified orientation information to restrict attention to sets of vertices that are potentially anterior separating sets. This restriction is justified by the following theorem and the soundness of the added arrowheads under the assumption of perfect testing. P ROPOSITION 10.1. (Minimal separator implies anterior separator). If C is a minimal separating set for a pair of vertices then C is an anterior separating set for the pair of vertices. In order to effectively terminate the algorithm, we need to an upper bound the size the minimal separating sets for a pair of vertices that are adjacent in the current graph G. Proposition 10.1 and the correctness of Orientation Rule 1 and edge removal provides a simple tighter bound on the size of the minimal separating set in a graph. In particular, if C is a minimal separator for a and b in G∗ , then |C| ≤ | Ant(ab, G∗ )| ≤ | Ant(ab, G)|. This, however is not a tight bound and leads to excess computation. For instance, if G∗ is undirected and connected the bound is vacuous. In graphs without bidirected edges, the degree of the vertices — the cardinality of the set of adjacent vertices — can be used to bound the size of the minimal separating set. This, however, is not possible for mixed graphs. For instance, consider graph G11 shown in Figure 6. In order to separate a and e in G11 the minimal separating set is the set { b, c, d } that includes vertex c that is adjacent to neither a nor b. This motivates the definition of the induced adjacencies of a vertex. The induced adjacencies of a vertex a given vertex b in graph G is the set iAdj(a, b, G) that contains the vertices connected to a by collider walk in which every internal vertex is in Ant(ab, G). In graph G11 , iAdj(a, b, G) = iAdj(b, a, G) = { b, c, d }.11 The anterior induced adjacencies of a vertex a given vertex b in graph G is the set aiAdj(a, b, G) = iAdj(a, b, G) ∩ Ant(ab, G). The next proposition shows that, if a and b are separable then the anterior induced adjacencies of a given b are sufficient to separate a and b. P ROPOSITION 10.2. aiAdj(a, b, G).
If a and b are separable in graph G then a ⊥ ⊥G b | C where C =
SEPARABLE GRAPHICAL MODELS
23
F IG 6. Graph G11 illustrates that vertex separation is non-local.
The quantity SepSetBound(a, b, G) is the separation set bound for a pair of vertices a and b in graph G and defined to be 0 if a ̸∈ Adj(b, G) and to be SepSetBound(a, b, G) = max(|aiAdj(a, b, G)|, |aiAdj(b, a, G)|) otherwise. The following proposition captures the fact that the separation set bound for G bound the size of the minimal separation set in G∗ . P ROPOSITION 10.3. If a ̸∈ Adj(b, G∗ ) and |C| is a minimal separating set for a and b in G∗ then under perfect testing, |C| ≤ SepSetBound(a, b, G). We then use this bound to define an overall bound for the graph G. The separation set bound of graph G is defined to be SepSetBound(G) = maxa,b∈V SepSetBound(a, b, G) and use it to determine when to terminate the SGI algorithm. The following theorem describes the correctness of the SGI algorithm. The correctness result assumes that the P ∗ provides perfect testing with respect to G∗ for the SGI algorithm. T HEOREM 10.4. If G∗ is essentially separable then SGI(I(G∗ )) ≡ G∗ and if G ≡ G∗ is separable then SGI(I(G∗ )) = InducedArrowheads(G). From Corollaries 9.3 and 9.4, the graph SGI(I(G∗ )) is both the largest graph equivalent to G∗ and an anterial graph equivalent to G∗ . C OROLLARY 10.5. If G∗ is essentially separable and P ∗ provides perfect testing for G∗ with respect to SGI then the SGI algorithm identifies the equivalence class of G∗ . We illustrate the SGI algorithm applied to I(G2 ) from Figure 1. The initial graph is the simple complete undirected graph (not shown). The first separation fact that is found is a⊥ ⊥G b | ∅. The algorithm removes the edge between a and b and then computes the set IV(a, b, ∅, G) = { c }. It then uses Orientation Rule 1 to add arrowhead endmarks at c on the edges e(a, c), e(b, c), e(d, c), e(e, c). The results at this point is shown as Graph G9 in Figure 7. The algorithm then continues to search for separation facts. It next finds that a ⊥ ⊥G d | ∅ , removes the edge e(a, d), computes the set IV(a, d, ∅, G) = { c }. In this case the application of Orientation Rule 1 adds no new arrowhead endmarks. It next finds a ⊥ ⊥G e | ∅, removing the edge, and again no new arrowhead endmarks are added. The result at this stage is shown at Graph G10 in Figure 7. The algorithm then finds b ⊥ ⊥G e | ∅, and removes the edge e(b, e) and adds no new arrowhead endmarks. No additional independencies are found and the result is the graph G8 in Figure 5. Note that the adjacencies of G6 and G2 are not the same as G2 is essentially separable. Nonetheless, it does have the same adjacencies as the graph G1 and the same induced arrowheads. 11 The set of induced adjacencies is a generalization of the set D-SEP defined by [23] and Proposition 10.2 is related to Theorem 6.2 and Lemma 6.2.4 proved in [23].
24
F IG 7. Graph G9 and G10 are intermediate graphs obtained while applying the SGI algorithm.
The next theorem provides a simple bound on number of independence tests required by the SGI algorithm in terms the properties of a graph equivalent to G∗ . T HEOREM 10.6. If G∗ is essentially separable and P ∗ provides perfect testing for G∗ then the SGI algorithm requires O(|V |SepSetBound(G)+1 ) independence tests where G = Largest(G∗ ) is the representation of the equivalence class of G∗ . 11. Discussion. This paper contributes to a long series of work investigating the properties of families of graphical models and algorithms identifying equivalence classes of graphical models using independence tests. In this section, we discuss aspects of our work as it relates to previous work that has not been discussed in the previous sections. 11.1. Essentially cyclic graphical models. Cyclic directed graphs have been used to represent the equilibrium of systems with feedback. For instance, [16] considers simple graphs with directed edges and [9] considers reciprocal graphs; graphs with directed and undirected edges with additional restrictions. Both of these families are subfamilies of the mixed graphs considered in this paper. A characterization of separation equivalence for directed graphs was given by [17]. A structure identification algorithm that identifies the equivalence class of a directed graphical models under perfect testing was given in [16]. More recently an alternative characterization of separation equivalence for directed graphs was given by [2]. The family of directed graphs includes some essentially cyclic graphs (e.g., graph G3 from Figure 2). The characterizations of the separation equivalence of separable graphs given in Sections 7 and 8 include some cyclic graphs but does not include essentially cyclic graphs. A natural generalization of our work and previous work on directed graphs is to provide a characterization of separation equivalence for all mixed graphs, to develop a canonical representation function for the equivalence class of mixed graphs, and to develop structure identification algorithms that identify the equivalence class of mixed graphs. 11.2. Sound and complete representation of equivalence classes. In this paper, the goal of our SGI structure identification algorithm is to obtain a representation of the equivalence class of the generative graphical model under perfect testing. In fact, the output of SGI provides additional information about the generative structure of the graphical model as all identified arrowheads are exclusive arrowheads and shared by all equivalent separable graphs. A natural goal for a structure identification algorithm it to provide correct information about endmarks (soundness) and as much information about endmarks as possible (completeness).
SEPARABLE GRAPHICAL MODELS
25
This is typically accomplished through the application of orientation rules. A set of sound and complete orientation rules for directed acyclic graphs was presented by [12] and for ancestral graphs by [29]. From Theorem 9.2, we know that if G is a separable graph then InducedArrowheads(G) ≡ G. Corollary 9.3, implies that it is not possible to add any additional arrowheads. This implies that the SGI structure identification algorithm is arrowhead complete in the sense that no additional arrowheads can be added. Developing a set of sound and complete orientation rules for essentially separable graphs (e.g., applied to the output of the SGI algorithm) is a natural next step. In order to accomplish this one needs to extend the class of graphs used to represent the output as in [29]. This is due to the fact that for some separation equivalence classes some but not all of the tail endmarks are exclusive. The arrowhead completeness of the SGI algorithm enables one to explore the impact of the ontological assumptions about the generative process on the identifiability of features of the equivalence class of the generative model. For instance, if we assume that G is a directed acyclic graph, then one can use the PC algorithm and the orientation rules R1-R4 of [12] to obtain a sound and complete set of endmarks under perfect testing. However, an equivalent graph, under the weaker assumption that the generative model is essentially separable might not have the same arrowheads. For instance, consider the graph with edges a —≻ c, b —≻ c, c —≻ d. The result of the PC algorithm and the orientation rules under perfect testing adds of an arrowhead at d on the edge e(c, d) which is not added by the SGI algorithm. This is justified by the existence of the equivalent graph in which e(c, d) is undirected. Such additional arrowheads are sound when making the ontological assumption that the family generating processes are directed acyclic graphs rather than essentially separable graphs. This situation is similar when assuming G is an ancestral graph and applying the orientation rules R1-R4 of [29]. Again, one obtains an arrowhead at d on e(c, d) as the orientation rules are sound for ancestral graphs but not for essentially separable graphs. 11.3. Assumption for identification and their plausibility. The correctness results for the SGI algorithm (Corollary 10.5) assume perfect testing. In this section we consider the tenability and plausibility of this identification assumption. A distribution P is perfect with respect to G if A ⊥ ⊥G B | C ⇐⇒ A ⊥ ⊥P B | C .12 Clearly, if a distribution P is perfect with respect to G then I(P ) provides perfect testing for G. We establish the tenability of the perfect testing assumption by establishing the existence of perfect distributions for all essentially separable graphs. This follow from the paper [20] that shows the existence of a perfect distribution for every chain mixed graphs and Theorem 5.3, every separable graph has an equivalent anterial graph. Other related results for more restricted graph families and distribution families are those of [13, 14, 23]. Next we consider the plausibility of the identification assumption. Previous work has justified the assumption of the generative distribution being a perfect distribution for particular defining distribution families and graph families by showing that, in a specific measure theoretic sense, most distributions that can be represented by a graph are perfect. [13, 14, 23] One can hope to extend these results to richer families of graphs and families of distributions to show the plausibility of the assumption of perfect testing. 11.4. Elucidating the assumptions for identification. The perfect testing assumption used in Corollary 10.5 does not provide insight into the nature of the assumptions required 12 This assumption is sometimes referred to as the distribution and the graph being faithful; see, for example, [20]. Faithfulness, however, often refers only one direction. In particular, the direction opposite of P ∗ being Markov with respect to G∗ ; see [23].
26
the SGI algorithm correctness. The conjunction of the following alternative compatibility conditions are sufficient for SGI to identify structure and provide some insight into the requirements for correctness. 1) Bounded vertex separability perfectness: for all i and j , the vertices i and j are not vertex separable in G∗ if and only if for all C ⊆ V \ { i, j } such that |C| < ∖ SepSetBound(i, j, G∗ ), i ⊥ ⊥P ∗ j | C. 2) Bounded induced arrowhead perfectness: if vertices k and l are not vertex separable in G∗ , then for all i, j , and C ⊆ V \ { i, j } such that |C| < SepSetBound(i, j, G∗ ), k ∈ IV(i, j, C, I(G∗ )) ∧ l ∈ / IV(i, j, C, I(G∗ )) ⇐⇒ k ∈ IV(i, j, C, I(P ∗ )) ∧ l ∈ / IV(i, j, C, I(P ∗ ))
Informally, the sufficiency of these conditions follows from Theorem 8.2 and the following informal arguments. The bounded vertex separability perfectness condition guarantees adjacency correctness in the result of the SGI algorithm. The forward direction of this condition guarantees that no required edge is removed and the reverse direction of the condition guarantees that missing edges are removed. The forward direction of bounded vertex separability is essentially a bounded version of adjacency faithfulness of [30] with the other direction being a bounded local Markov condition (see also [25]). The bounded induced arrowhead perfectness condition guarantees that any edge in the result of the SGI algorithm will be oriented with an arrowhead if and only if it has an induced arrowhead in G∗ . The induced arrowhead is stronger than perfect testing as it requires (e.g.) correctness for all i, j and all separating sets C with |C| < SepSetBound(i, j, G∗ ) but the algorithm uses (e.g.) only minimal separating sets. Finally, we note that the assumption of perfect testing is also sufficient but not minimal due to the fact that one can recover from (1) failing to remove an edge due to an incorrect test if there is another test later that removes the edge, and (2) failing to orient an induced arrowhead on an edge in G∗ if another edge removed later leads to the orientation of the required induced arrowhead. 11.5. More efficient structure identification algorithms. Most independence test based structure identification algorithms, such as the the PC algorithm [23], the FCI algorithm [23] and the FCI+ algorithm [3], use some sort of locality in their search for separatings sets for pairs of variables. For instance, the PC algorithm, when trying to separate vertices a and b only consider vertices that are adjacent to a and b. As discussed in Section 10, this is sufficient in if there are no bidirected edges. If, however, the generative structure includes bidirected edges one needs to augments the candidate set for potential separating sets to include additional vertices. For instance, the FCI [23], RFCI [4], and FCI+ [3] each consider vertices beyond those adjacent to the endpoints of an edge they are trying to remove. In this paper, we also consider extended sets of vertices that we call the set of induced adjacencies. Unlike these other approaches, we do not restrict separating sets to to induced adjacencies but rather allow for a non-local search among vertices that are potentially anterior to the endpoints of the edge that we are trying to remove. One can, however, consider a more localized version of the SGI algorithm in which we choose potential separating sets for i and j using the current graph G. In particular, Proposition 10.2 shows that the anterior inducing adjacencies provide a more localized separation criterion as compared to search among vertices that are anterior to either i or j . This, one can choose C to be a subset of aiAdj(i, j, G) or to be a subset of aiAdj(j, i, G). One complication in doing so, is that, unlike the sets Ant(i, G) and Ant(j, G), there is no guarantee that aiAdj(i, j, G) ⊆ aiAdj(i, j, G∗ ). Thus if searching from among possible separating sets (e.g.)
SEPARABLE GRAPHICAL MODELS
27
C ⊆ aiAdj(i, j, G) we need to check all subsets of size ≤ socs. It would be interesting to compare alternative structure identification algorithms that use both locality and orientation information to improve computational efficiency. In addition to computational efficiency, it is important to consider the statistical reliability of structure identification algorithms. There are a number of different approaches to improving reliability including using redundant tests and removing unnecessary tests. The SGI algorithm, after identifying a separating set, determines the complete set of inducing variables for the separated vertices. It is not necessary to identify this entire set as many of the induced arrowheads can be identified on the basis of other separating sets. It would be interesting to explore the reliability of the SGI algorithm as compared with other independence test based structure identification algorithms and to explore if reliability or efficiency can be improved by using locality and by being lazy about computing complete sets of inducing variable for separated vertices especially when future tests will establish the existence of an arrowhead. Finally, we note that Classen et al. [3] also provide a polynomial bound for identifying ancestral. The polynomial bound we provide in Theorem 10.6 is not, however, directly comparable.
11.6. Maximal graphs. In Section 4, we showed that there are maximal graphs that are not separable. Previous work such as [10] and [18] have provided maximization algorithm for subfamilies of mixed graphs. It would be interesting to develop algorithms that transform a graph into a maximal equivalent graph and study their properties. The properties of maximal graphs are likely to prove useful in extending the results on characterizing separation equivalence to all mixed graphs and in developing identification algorithms for the separation equivalence classes of mixed graphical models. 11.7. Other separation criteria. The focus of this paper has been on the properties of mixed graphs with respect to d-separation. It would be interesting to consider separable, essentially separable and essentially acyclic graphs defined with respect to other separation criteria. In particular, the σ -separation criteria has been defined for mixed graphs with directed and bidirected edge. It would be interesting to extend σ -separation to mixed graphs and explore the properties of σ -separable, σ -essentially separable, and σ -essentially acyclic graphs. In particular, one might expect that all mixed graphs in such an extension, are σ essentially acyclic, given the work by [22] and [6] related to acyclification. Furthermore, one would then expect that all mixed graphs are σ -essentially separable. REFERENCES [1] A NDERSSON , S. A., M ADIGAN , D. and P ERLMAN , M. D. (2001). Alternative Markov properties for chain graphs. Scandinavian Journal of Statistics 28 33-85. https://doi.org/10.1111/1467-9469.00224 [2] C LAASSEN , T. and M OOIJ , J. M. (2023). Establishing Markov equivalence in cyclic directed graphs. In Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI-23) (R. J. E VANS and I. S HPITSER, eds.). Proceedings of Machine Learning Research 216 433–442. PMLR. https://doi.org/10.48550/arXiv.2309.03092 [3] C LAASSEN , T., M OOIJ , J. M. and H ESKES , T. (2013). Learning Sparse Causal Models is not NP-hard. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI 2013) 172–181. AUAI Press. https://doi.org/10.48550/arXiv.1309.6824 [4] C OLOMBO , D., M AATHUIS , M. H., K ALISCH , M. and R ICHARDSON , T. S. (2012). Learning highdimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics 40 294–321. https://doi.org/10.1214/11-AOS940 [5] D IDELEZ , V. (2008). Graphical models for marked point processes based on local independence. Journal of the Royal Statistical Society Series B: Statistical Methodology 70 245-264. https://doi.org/10.1111/ j.1467-9868.2007.00634.x
28 [6] F ORRÉ , P. and M OOIJ , J. M. (2020). Causal calculus in the presence of cycles, latent confounders and selection bias. In Proceedings of the 35th Uncertainty in Artificial Intelligence Conference (UAI-19) (R. P. A DAMS and V. G OGATE, eds.). Proceedings of Machine Learning Research 115 71–80. PMLR. https://doi.org/10.48550/arXiv.1901.00433 [7] F RYDENBERG , M. (1990). The chain graph Markov property. Scandinavian Journal of Statistics 17 333– 353. https://www.jstor.org/stable/4616181 [8] G IBBS , J. W. (1902). Elementary Principles in Statistical Mechanics. Yale University Press. [9] KOSTER , J. T. A. (1996). Markov properties of nonrecursive causal models. The Annals of statistics 24 2148-2177. https://doi.org/10.1214/aos/1069362315 [10] L AURITZEN , S. and S ADEGHI , K. (2018). Unifying Markov properties for graphical models. The Annals of Statistics 46 2251 – 2278. https://doi.org/10.1214/17-AOS1618 [11] L AURITZEN , S. L. (1996). Graphical Models. Oxford University Press, Oxford, UK. https://doi.org/10. 1093/oso/9780198522195.001.0001 [12] M EEK , C. (1995). Causal inference and causal explanation with background knowledge. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. UAI’95 403–410. Morgan Kaufmann, San Francisco, CA, USA. https://doi.org/10.48550/arXiv.1302.4972 [13] M EEK , C. (1995). Strong completeness and faithfulness in Bayesian networks. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. UAI’95 411–418. Morgan Kaufmann, San Francisco, CA, USA. https://doi.org/10.48550/arXiv.1302.4973 [14] P EÑA , J. M. (2009). Faithfulness in chain graphs: the discrete case. International Journal of Approximate Reasoning 50 1306–1313. https://doi.org/10.1016/j.ijar.2009.06.006 [15] P EARL , J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco, CA, USA. [16] R ICHARDSON , T. (1996). A discovery algorithm for directed cyclic graphs. In Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence. UAI’96 454–461. Morgan Kaufmann, San Francisco, CA, USA. https://doi.org/10.48550/arXiv.1302.3599 [17] R ICHARDSON , T. (1997). A characterization of Markov equivalence for directed cyclic graphs. International Journal of Approximate Reasoning 17 107-162. https://doi.org/10.1016/S0888-613X(97) 00020-0 [18] R ICHARDSON , T. S. and S PIRTES , P. (2002). Ancestral graph Markov models. Annals of Statistics 30 9621030. https://doi.org/10.1214/aos/1031689015 [19] S ADEGHI , K. (2016). Marginalization and conditioning for LWF chain graphs. The Annals of Statistics 44 1792 – 1816. https://doi.org/10.1214/16-AOS1451 [20] S ADEGHI , K. (2017). Faithfulness of probability distributions and graphs. Journal of Machine Learning Research 18 5429–5457. https://doi.org/10.48550/arXiv.1701.08366 [21] S ADEGHI , K. and L AURITZEN , S. L. (2011). Markov properties for mixed graphs. Bernoulli 20 676-696. https://doi.org/10.3150/12-BEJ502 [22] S PIRTES , P. (1995). Directed cyclic graphical representations of feedback models. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence 491–498. Morgan Kaufmann, San Francisco, CA, USA. https://doi.org/10.48550/arXiv.1302.4982 [23] S PIRTES , P., G LYMOUR , C. and S CHEINES , R. (1993). Causation, Prediction, and Search. Lecuture Notes in Statistics 81. Springer-Verlag, New York, NY, USA. https://doi.org/10.1007/978-1-4612-2748-9 [24] S TUDENY, M. (2005). Probabilistic Conditional Independence Structures. Springer-Verlag London, New York, NY, USA. [25] T EH , K. Z., S ADEGHI , K. and S OO , T. (2025). A general framework on conditions for constraint-based causal learning. Scandinavian Journal of Statistics 52 2209-2241. https://doi.org/10.1111/sjos.70023 [26] V ERMA , T. and P EARL , J. (1990). On the equivalence of causal models In Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence 220-227. Elsevier Science, Amsterdam, The Netherlands. https://doi.org/10.48550/arXiv.1304.1108 [27] W ERMUTH , N. and L AURITZEN , S. L. (1990). On substantive research hypotheses, conditional independence graphs and graphical chain models. Journal of the Royal Statistical Society Series B: Statistical Methodology 52 21–72. https://doi.org/10.1111/j.2517-6161.1990.tb01771.x [28] W RIGHT, S. (1925). Correlation and causational. Journal of Agricultural Research 20 162-177. [29] Z HANG , J. (2007). A characterization of Markov equivalence classes for directed acyclic graphs with latent variables. In Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence. UAI-07 450–457. AUAI Press, Arlington, Virginia, USA. https://doi.org/10.48550/arXiv.1206.5282 [30] Z HANG , J. and S PIRTES , P. (2008). Detection of Unfaithfulness and Robust Causal Inference. Minds and Machines 18 239–271. [31] Z HAO , H., Z HENG , Z. and L IU , B. (2005). On the Markov equivalence of maximal ancestral graphs. Science in China Series A: Mathematics 48 548—562. https://doi.org/10.1360/04ys0023
SEPARABLE GRAPHICAL MODELS
29
APPENDIX A: PROOFS OF PROPERTIES OF INDEPENDENCE MODELS In this section we prove Proposition 2.1 from Section 2.1. P ROPOSITION 2.1 If I and I ′ are dyadic independence models then I and I ′ are equivalent (i.e., I = I ′ ) if and only I and I ′ are pairwise equivalent (i.e., Pairwise(I) = Pairwise(I ′ )). P ROOF. The forward direction follows from the fact that the Pairwise projection of an independence model contains all and only the pairwise independence statements that hold in a graph. For the reverse direction we assume that Pairwise(I) = Pairwise(I ′ ). Assume that the claim does not hold. In that case there must be an (A, B, C) such that either (i) ∖ ∖ A⊥ ⊥I B | C and A ⊥ ⊥ I ′ B | C or (ii) A ⊥ ⊥ I B | C and A ⊥ ⊥I ′ B | C . Without loss of generality, assume (i). From decomposition we have a ⊥ ⊥I b | C for a ∈ A and b ∈ B . From pairwise equivalence, we have a ⊥ ⊥I ′ b | C for a ∈ A and b ∈ B . Finally, from composition we have A ⊥ ⊥I ′ B | C . Thus we have a contradiction and the claim holds. APPENDIX B: PROOFS OF USEFUL PROPERTIES OF WALKS AND VERTEX SETS B.1. Manipulating walks. We can use the subsequence operator to define a subwalk. For instance, if ω = (e1 , . . . , en ) then γ = ω(ei , ej ) = (ei , . . . , ej ) is the subwalk containing all of the edges from ei to ej . We extend the definition of the subwalk operator to allow for the specification of a subwalk via a pair of vertices on the walk or a subsequence of the vertex sequence of the walk. Consider the walk ω = (e1 , . . . , en−1 ) with vertex sequence ver(ω) = (v1 , . . . , vn ). We use ω(vi , vj ) to refer to the subwalk of ω containing the edges corresponding to adjacent pairs of vertices on the vertex subsequence ver(ω)(vi , vj ). We also allow the subwalk operator to be applied to a vertex subsequence of the vertex sequence of the walk. For instance, ω((vi , . . . , vj )) = ω(vi , vj ). Note that the subwalk operator can be used to reverse the sequences of edges in a walk. For instance, ω(vn , v1 ) = (en−1 , . . . , e1 ) is the walk whose first vertex is the last vertex of the walk ω . Note that ω(vi , vi ) = ω(()) = ω((vi )) = () is an empty walk. We use the binary operator + to append two sequences (e.g., ω(e1 , en ) = ω(e1 , ei ) + ω(ei , en )) B.2. Termination properties of walks. A walk ω with ver(ω) = (v1 , . . . , vn ) is into v1 if the edge e(v1 , v2 ) on ω has an arrowhead at v1 , otherwise it is out of v1 . For instance, the walk a —≻ b ≺—≻ c is out of a and into c. A walk ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) is weakly into v1 if either (1) ω is into v1 or (2) the edge e(last(σ1 ), first(σ2 )) has an arrowhead at last(σ1 ), otherwise it is strongly out of v1 . For instance, the walk a — b —≻ c —≻ d — e is strongly out of a and weakly into e. Note that a walk that is into an endpoint is necessarily weakly into that endpoints and that a walk that is strongly out of an endpoint is necessarily out of that endpoint. B.3. Open walks and connecting walks. Next we define a generalization of connecting walks that yields an equivalent definition of vertex separation that is useful for describing and proving results about mixed graphs. A walk ω is open given C if every collider section of ω is anterior to C ∪ { i, j } and every internal vertex on a non-collider section is not in C . If a walk is not open given C then it is closed given C . Note that the walk i ≺—≻ a ≺—≻ i — b ≺— j is open given C = { i }. A collider section of a walk is open given C if every vertex is anterior to C and is closed otherwise. A non-collider section of a walk is open given C if every vertex on the section that is not an endpoint of the walk is not in C. Thus, a walk is open given C if and only if every section of the walk is open given C.
30
The concept of shortest open walk often plays an important role in proving separation properties of graphs (including the following lemma). A walk ω is a shortest open walk given C if ω is open given C and there is no shorter walk that is open given C . The following lemma captures the property that if is there is an open walk between i and j given C there must be another open walk given the C \ { i, j }. L EMMA B.1. If walk ω between i and j is open given C in graph G then there is an open walk ω ′ that is open given C \ { i, j } in G. P ROOF. Let ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) be the shortest walk between i and j that is open given C such that there is no subwalk including ω itself between i and j that is open given C \ { i, j }. We consider two cases. Case 1: C ∩ { i, j } = ∅. In this case, the walk ω is open given C \ { i, j }. This contradiction the assumption that there is no subwalk open given C \ { i, j } and we have a contradiction. Case 2: C ∩ { i, j } ̸= ∅. Note that the only occurrence of i on σ1 can be as vertex v1 and the only occurrence of j on σm can be as vertex vn . If the only section containing i is on σ1 and the only occurrence of j is on σm then ω open given C \ { i, j }, a contradiction. If i ∈ C ∩ { i, j } then every occurrence of i must be in a non-collider section otherwise the walk is not open given C . Similarly for j. If every occurrence of i or j is on collider section that contains a member of C \ { i, j } then ω is open given C \ { i, j }, a contradiction. Thus there must be a collider section containing a vertex in { i, j } and no other vertex in C \ { i, j }. Without loss of generality, assume σk is a collider section containing vl = i and no vertex in C \ { i, j }. In this case, the walk ω(vl , vn ) is a shorter walk open given C, a contradiction. In all cases we have a contradiction so the lemma must hold. The following lemma proves that one can transform an open walk given C into another open walk given C in which all collider sections are anterial to a vertex in C . L EMMA B.2. If there is a walk ω between i and j that is open given C then there is a walk ω ′ between i and j open given C \ { i, j } in which all collider sections on ω ′ are anterior to C \ { i, j }. P ROOF. Let ω be an open walk given C with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ). By Lemma B.1, we can assume that C ∩ { i, j } = ∅. We construct the required walk ω ′ as follows: If there is a collider section on ω that is anterior to v1 but not anterior to C then choose i to be as large as possible such that σi is such a collider section and choose i = 1 otherwise. If i > 1 then let γi be the shortest anterior walk from first(σi ) to v1 and let γ1 = () otherwise. Due to the choice of σi , the walk γi contains no vertices in C . If there is a collider section on ω that is anterior to vn but not anterior to C that is not before σi then choose j to be as small as possible but with j ≥ i such that σj is such a section and let j = m otherwise. If j ̸= m then let γj be the shortest walk from a vertex vb in σj to vn and let γj = () otherwise. Again, due to the choice of σj , the walk γj contains no vertices in C . Finally, let ω ′ = γi + ω(first(σi ), last(σj )) + γj . The walk ω ′ is an open walk given C such that all collider sections are anterior to C . The following proposition demonstrates that open walks and connecting walks yield the equivalent definitions of vertex separation in a mixed graph.
SEPARABLE GRAPHICAL MODELS
31
L EMMA B.3. There is a connecting walk between i and j given C \ { i, j } if and only if there is an open walk between i and j given C . P ROOF. For the forward direction, assume there is a walk ω that is a connecting walk given C . The walk ω is also an open walk given C as every non-collider section contains no vertex in C and every collider section contains vertex in C and thus is anterior to Ant({ i, j }, G). For the backward direction, assume there is a walk between i and j that is an open walk given C . From Lemma B.1, we can assume that C does not contain either i or j . From Lemma B.2, we assume that the walk ω between i and j is open given C and that every collider section on ω is anterior to C . We transform the walk ω into walk ω ′ by replacing every collider section τ on ω that does not contains a vertex in C with a walk τ ′ between first(τ ) and last(τ ) that is connecting given C . The walk τ ′ is defined as follows: Let ver(τ ) = (v1 , . . . , vn ) and let γc be a shortest anterior walk from a vertex on τ to a vertex c ∈ C . Let the first vertex of γ ′ be vk . We define τ ′ = τ (v1 , vk ) + γc + γc (c, vk ) + τ (vk , vn ). Next we show that ω ′ constructed in this way is a connecting walk given C . Consider any collider section τ on ω that does not contain a vertex in C . Let τ ′ = τ (v1 , vk ) + γc + γc (c, vk ) +τ (vk , vn ) with γc a shortest anterior walk from τ to a vertex c ∈ C . By choosing the shortest anterior walk the only vertex on γ ′ in C is its endpoint c. Thus the only vertex in C on τ ′ is c and it appears only once on the walk. If γc is a semi-directed walk then c is on a collider section of γc + γc (c, vk ) and all other sections of τ ′ are non-collider section on ω ′ due to the fact that the walk τ ′ is strongly out of v1 and vn . Furthermore, none of these sections contain a vertex in C . If γc is an undirected walk then τ ′ is an undirected walk and every vertex on τ ′ is on a collider section that contains a vertex c ∈ C . Thus walk ω ′ constructed in this way is a connecting walk as every collider section contains a vertex in C and no non-collider section contains a vertex in C . B.4. Invertible walk decomposition functions. The decomposition of walks into subwalks will play an important role in proving various results. In this section, we define an invertible walk decomposition. In later section, we define specific walk decompositions. Let W (G) be the set of all possible walks in graph G. A walk decomposition of a walk ω ∈ W (G) with ver(ω) = (v1 , . . . , vn ) is a set of walks decomp(ω) = { γ1 , . . . , γn } such that (1) γi is a subwalk of ω for 1 ≤ i ≤ n, and (2) every edge e(vi , vi+1 ) on ω for 1 ≤ i < n is on some subwalk γj . A walk decomposition function f for a set of walks W ⊆ W (G) is a function f (ω) that maps a walk ω ∈ W to a walk decomposition of ω . If f is a walk decompositionSfunction for a set of walks W we denote the set of possible walk decomposition by f (W) = ω∈W f (ω). A walk decomposition function f for W is invertible if there is a function f −1 from f (W) to W such that for all ω ∈ W it is the case that f −1 (f (ω)) = ω . The function f −1 is a walk composition function for a walk function f . B.5. The maximal walk decomposition and walk equivalence. The maximal walk decomposition of a walk is a walk decomposition into maximal collider walks and maximal treks. A trek is a walk in which all vertices are on non-collider sections. A collider walk γ is a maximal collider walk on ω if γ is a subwalk of ω and there is no longer subwalk of ω that is a collider walk and contains γ . A trek τ is a maximal trek on ω if τ is a subwalk of ω and there is no other trek that is a subwalk of ω and contains τ . The maximal walk decomposition of ω is the walk decomposition decompm (ω) = { τ1 , γ1 , τ2 , . . . , γn−1 , τn } such that (i) γi for 1 ≤ i < n is a non-trivial maximal collider walk of ω , and (ii) τi for 1 ≤ i ≤ n is a maximal trek of ω . The walk decomposition function decompm is invertible due to the fact that a non-collider section of a walk must be a section of a maximal trek and a collider section
32
of a walk must be an internal section of a maximal collider walk. In other words, there is a −1 function decomp−1 m such that decompm (decompm (ω)) = ω . If a pair of walks in a maximal walk decomposition of a walk overlaps then one of the walks is a maximal trek and the other is a maximal collider walk and they share exactly one edge. While the first and last edges of a walk must be part of a maximal trek in a maximal walk decomposition of a walk, they can be part of the same maximal trek if there are no collider sections in the walk. The first and last treks of a maximal walk decomposition are called terminal treks while treks between two collider walks are called internal treks. An internal trek must be into both of its endpoints, a terminal maximal trek with an adjacent maximal collider walk is required to be into one of its endpoints, and the maximal trek of a walk consisting of a single maximal trek is not required to be into either endpoint. For example if walk ω is the walk a — b —≻ c — d ≺—≻ e ≺— f then decompm (ω) = { a — b —≻ c, b —≻ c — d ≺—≻ e ≺— f, e ≺— f }. Next we define the equivalence maximal walk decompositions. Two maximal walk decompositions decomp(γ) ≡ (γ1 , . . . , γn ) and decompw (ω) = (ω1 , . . . , ωm ) are equal if (1) each walk decomposition contains the same number of subwalks (i.e., n = m) and, (2) for 1 ≤ i ≤ n, if i is odd the vertex sequence of γi and ωi are the same (i.e., ver(γi ) = ver(ωi )) and if i is even then γi ≡ ωi . Two walks ω and γ are equivalent (denoted ω ≡ γ ) if decompw (ω) ≡ decompw (γ) or decompw (rev(ω)) ≡ decompw (γ) where rev(ω) is the walk with the same edges as ω but the opposite traversal order. While two equivalent walks are guaranteed to have the same vertex sequence they need not consist of edges with the same endmarks or have the same section sequence. Consider walks a —≻ b — c and a ≺—≻ b —≻ c. These two walks are equivalent due to the fact that each walk decomposition consists of a single maximal trek and these maximal treks have the same vertex sequence. The two walks, however, have different section sequences. Now consider the walks a —≻ b ≺—≻ c and a ≺—≻ b ≺— c. These two walks are also equivalent. Their walk decompositions are of length three, their maximal treks consist of single edges with the same vertex sequence and their maximal collider walks have the same section sequence. B.6. Trisections. The concept of trisections is used in many of the proofs that follow. A walk ω is trisection if its section sequence sec(ω) = (σ1 , σ2 , σ3 ) has three section and the first and last are of length one. We often denote a trisection by (i, σ, j). Trisection subwalks of walks are useful. If σ is an internal section on a walk ω then there is a unique trisection on ω that contains σ . This allows us to select a trisection on a walk using an internal section on that walk. A trisection (i, σ, j) is unshielded in graph G if there is no edge e(i, j) in G and is shielded otherwise. An important fact that is often used in proofs is that a chordless unshielded trisection (i, σ, j) whose section σ is a collider section is a minimal inducing walk. B.7. Decomposing and Composing open walks. In this section, we describe walk decompositions of open walks into open walks and the openness of the composition of open walks. For some decompositions of an open walk into open subwalks we can guarantee termination properties of the subwalks.13 The openness of a walk composed of two open walks also depends on the termination properties of the subwalks. L EMMA B.4. If ω is an open walk given C and b is an internal vertex on a non-collider section of ω then the walks ω(v1 , b) and ω(vn , b) are open given C . Furthermore, at least one of the walk is strongly out of b. 13
The definition of the termination properties of walks is given in Section 2.3.2.
SEPARABLE GRAPHICAL MODELS
33
P ROOF. Let ω is a open walk given C in graph G and b is an internal vertex on a collider section of ω . It must be the case that b ̸∈ C otherwise ω would not be an open walk given C . The walks ω(v1 , b) and ω(vn , b) are both open given C as every collider section on these walks is a collider section on ω and must contain a vertex in Ant(C, G). Furthermore noncollider sections on either of these walk cannot contain a vertex in C otherwise the walk ω would not be open given C . Finally, one of the walks must be strongly out of b otherwise b would be on a collider section of ω . Next we define minimal open walks. The concept of a minimal open walk generalizes the concept of a minimal inducing walk and is essential to describe the compositional properties of open walks. A walk γ is a minimal open walk between i and j given C if γ is an open walk given C and there is no shorter open walk between i and j given C that uses only vertices on γ . One of the important properties of a minimal open walk is that the endpoints of the walk do not appear on internal non-collider sections. This property is proved in the following lemma. L EMMA B.5. If ω is a minimal open walk between i and j given C then neither endpoint of ω appears as an internal vertex on a non-collider section of ω . P ROOF. Let ω be a minimal open walk given C with ver(ω) = (v1 , . . . , vn ). Suppose the lemma is not true. In this case at least one of the endpoints appears on a non-collider section of ω . Without loss of generality, assume that v1 = vj for 1 < j < n. Consider the walk ω ′ = ω(vj , vn ). The walk ω ′ is an open walk between v1 and vn by Lemma B.4. Furthermore, it is strictly shorter than ω and only uses vertices on ω as it is a subwalk on ω . Thus ω is not a minimal open walk given C and we have a contradiction. Thus, neither endpoint can appear as an internal vertex on a non-collider section of a minimal open walk. L EMMA B.6. If ω is a minimal open walk given C with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) and vertex b is on a collider section σi then (i) the walk ω(v1 , first(σi )) is into first(σi ) and is a minimal open walk given Cvn \ first(σi ), and (ii) the walk ω(vn , last(σi )) is into last(σi ) and is a minimal open walk given Cv1 \ last(σi ). P ROOF. Let ω be a minimal open walk given C with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) such that b is on a collider section σi . Let fi = first(σi ). Proof of (i): Consider the walk ω ′ = ω(v1 , fi ). The walk ω ′ must be into fi due to the fact that σi is a collider section. Next we show that ω ′ is open given Cvn \ fi . Every collider section on ω ′ is a collider section on ω , and thus, from ω being open given C , we have that every collider section on ω ′ is anterior to Cvn \ fi . Every non-collider section on ω ′ is a non-collider section on ω except the last section of ω ′ that consists only of the vertex b. From Lemma B.5 and the assumption that ω is a minimal open walk, we know that vn is not on an internal non-collider section of ω ′ . Combining this fact and the fact that ω is open given C , it must be the case that no non-collider section ω ′ contains a vertex in Cvn \ fi . Thus ω ′ is an open walk given Cvn \ fi . Proof of (ii): the proof is analogous to the proof of (i). Next we consider the openness of walks obtained by composing open subwalks. L EMMA B.7. If walk ω between i and j and walk γ between j and k are both minimal open walks given C then ω + γ is open given Cj if and only if both ω and γ are weakly into j.
34
P ROOF. Let walk ω between i and j and walk γ between j and k be minimal open walks given C that are weakly into j . Let ω ′ = ω + γ . For the forward direction, assume ω + γ is open given Cj . Suppose the lemma does not hold and at least one of ω and γ are strongly out of j . This implies that j must be on a non-collider section on ω + γ which implies that the walk is not open given Cj which is a contradiction. For the backward direction, assume both ω and γ are both weakly into j . First from the fact that both walks are open given C , it must be the case that j ̸∈ C . Furthermore, from Lemma B.5, neither ω nor γ contain j on a non-collider section. Next, due to both walks being weakly into j , j must be on a collider section. All other collider sections are anterial to some vertex in C and no non-collider section can contain C or j . Thus the walk is an open walk given Cj . L EMMA B.8. If walk ω between i and j and walk γ between j and k are both open given C and at least one of ω or γ is strongly out of j then ω + γ is open given C . P ROOF. Let ω be a walk between i and j open given C and γ be a walk between j and k given C and that at least one of ω or γ is strongly out of j . Let ω ′ = ω + γ . Suppose that ω ′ is not open given C . First, all sections of ω ′ are sections on ω or γ except possibly the last section of ω and the first section of γ . Furthermore every such section is a collider section on ω ′ if and only if it is a collider section on ω or γ . From the fact that ω and γ are open given C , all such sections are open on ω ′ given C . Next the fact that ω and γ are open given C implies that no vertex in the last section of ω is in C and no vertex in the first section of γ is in C . Thus, the only way that ω ′ is not open given C is if the section containing j on ω ′ is a collider section. This can only happen if both ω and γ are weakly into j which is a contradiction. Thus the lemma must be true. B.8. Properties of anterior and posterior sets. The following proposition of anterior and posterior sets are often used without explicitly referencing the following lemmas. The vertices posterior to a set of vertices A in a graph G is the set Post(A, G) containing all vertices in A and all vertices j ∈ V such that there is an anterior walk from a vertex a ∈ A to j . P ROPOSITION B.9. Ant(A ∪ B, G) ⊇ Ant(A, G) Ant(A ∪ B, G) = Ant(A, G)
(1) if B ⊂ Ant(A, G) (2)
P ROOF. Let G be a graph. Property (1): For every vertex c ∈ Ant(A, G) there must be an anterior walk from c to a vertex in A which implies the existence of an anterior walk from c to a vertex in A ∪ B and thus c ∈ Ant(A ∪ C, G). Property (2): Property (1) proves one direction so we just need to show ant(A ∪ B, G) ⊆ Ant(A, G). For every vertex c ∈ Ant(A ∪ B, G) then there is an anterior walk γ from c to a vertex d in A ∪ B . If d ∈ A we are done. Otherwise d ∈ B . Because d ∈ B ⊆ Ant(A, G) there is a walk γ ′ from d to a vertex in A. The walk γ + γ ′ is an anterior walk from b to a vertex in A which proves the claim. P ROPOSITION B.10. Post(A ∪ B, G) ⊇ Post(A, G) Post(A ∪ B, G) = Post(A, G)
if
(1) B ⊂ Post(A, G) (2)
SEPARABLE GRAPHICAL MODELS
35
P ROOF. Let G be a graph. Property (1): For every vertex c ∈ Post(A, G) there must be an anterior walk from a vertex in A to c which implies the existence of an anterior walk from a vertex in A ∪ B to c and thus c ∈ Post(A ∪ C, G). Property (2): Property (1) proves one direction of the property so we just need to show Post(A ∪ B, G) ⊆ Post(A, G). For every vertex c ∈ Post(A ∪ B) then there is an anterior walk γ from a vertex d in A ∪ B to c. If d ∈ A we are done. Otherwise d ∈ B . Because d ∈ B ⊆ Post(a, G) there is a walk γ ′ from a vertex in A to d. The walk γ + γ ′ is an anterior walk from a vertex in A to d which proves the claim. The proper anterior set of a set of vertices C in graph G is the set PropAnt(C, G) = Ant(C, G) \ C . P ROPOSITION B.11.
If B ⊆ PropAnt(A, G) then B ∪ PropAnt(A ∪ B, G) = PropAnt(A, G).
P ROOF. Assume B ⊆ PropAnt(A, G). B ∪ PropAnt(A ∪ B, G) = B ∪ Ant(A ∪ B, G) \ (A ∪ B) Definition of PropAnt . = Ant(A ∪ B, G) \ A Basic set operations. = Ant(A, G) \ A Lemma B.9 = PropAnt(A, G) Definition of PropAnt .
APPENDIX C: PROOFS RELATED TO THE CHARACTERIZATION OF SEPARABLE GRAPHS AND VERTEX SEPARATION In this section, we provide a proof of theorems appearing in Section 3. In particular, we provide a proof of Theorem 3.2, the characterization of vertex separation, and a proof of Theorem 3.3, the characterization of separable graphs. The following lemma is the contrapositive of Proposition 3.1. L EMMA C.1.
If two vertices are adjacent in a graph then they are not separable.
P ROOF. Let a ∈ Ant(b, G). This implies there is an edge e(a, b) in G and the walk consisting of this single edge is a walk between a and b. There is no separating set C ⊆ V \ { a, b } and thus the two vertices are not be separable. L EMMA C.2.
The endpoints of a self-inducing walk are not separable.
P ROOF. A self-inducing walk ω with ver(ω) = (v1 , . . . , vn ) is an open walk given any vertex set C ⊆ V \ { v1 , vn } and thus the claim then follows from Lemma B.3. An important anterial property of treks is that every internal vertex of treks is anterior to one of its endpoints. L EMMA C.3. For any internal vertex on a trek, there is an anterial subwalk of the trek from the internal vertex to one of the endpoints of the trek.
36
P ROOF. We prove the claim by induction on the number of vertices. For the base case we consider treks of length two. In this case there are no internal vertices and the claim holds vacuously. For the induction case, assume it is true for all treks of length n − 1 and show for treks of length n. Let ω = (e1 , . . . , en ) be a trek of length n with vertex sequence ver(ω) = (v1 , . . . , vn+1 ). The subwalk ω ′ = (e1 , . . . , en−1 ) is a trek of length n − 1 and thus, by the induction hypothesis, there is an anterial subwalk from every internal vertex to either v1 or vn . If edge en has a tail at vn then vn must be anterior to vn+1 and the claim holds. If edge en has an arrowhead at vn then no vertex vi of ω i < n can be connected to vn by a semi-directed walk otherwise ω would have a collider section. This implies that either vn is connected to v1 by and undirected walk or there is a semi-directed walk from vn to v1 . In either case, the claim holds. As the claim holds whether the last edge has an arrowhead or tail at the last internal vertex the claim holds of any trek of length n. The following lemma proves that every vertex on an open walk given C is anterial to the vertex set C or an endpoint of the walk. L EMMA C.4. { i, j }, G).
Every vertex on an open walk between i and j given C is in Ant(C ∪
P ROOF. Let ω be an open walk between i and j given C in a graph G. Every vertex b on ω is on a collider section or a non-collider of ω . Case 1: b is on a collider section. From the fact that ω is open given C , every collider section is anterior to C ∪ { i, j } and thus the every vertex on a collider section must be in Ant(C ∪ { i, j }, G). Case 2: b is on a non-collider section. Every non-collider section is on a maximal trek and, from Lemma C.3, every vertex on a maximal trek is anterior to one of its endpoints. Furthermore, every endpoint of a maximal trek on ω is either an endpoints of the walk or a vertex on a collider section. Thus every vertex on a maximal trek must be in the set Ant(C ∪ { i, j }, G). In either case the vertex must be in the set Ant(C ∪ { i, j }, G) which implies the lemma is true. T HEOREM 3.2 [Pairwise anterior separation] Two vertices i and j are separable in graph G if and only if i ⊥ ⊥G j | Ant({ i, j }, G) \ { i, j }. P ROOF. For the backward direction, assume that i ⊥ ⊥G j | Ant({ i, j }, G) \ { i, j }. In this case, the vertices i and j are separated by Ant({ i, j }, G) \ { i, j } and thus separable. ∖ For the forward direction, we prove the contrapositive. We assume that i ⊥ ⊥ G j | C where C = Ant({ i, j }, G) \ { i, j } and prove that i and j are not separable. From, Lemma B.3 there must be a walk ω between i and j that is open given C . We prove by cases. Case 1: ω contains no collider sections. In this case, all internal vertices are on non-collider sections. If ω contains an internal vertex it must be on a non-collider section and in C which would imply that the walk is not be open given C , so ω has no internal vertices. Thus ω must contain a single edge e(i, j) which, by Lemma C.1, implies that i and j are not separable. Case 2: ω contains a collider sections. From the fact that ω is open given C , every collider section must be anterior to C ∪ { i, j }. Thus, if ω had an internal vertex on a non-collider section, this vertex, by Lemma C.4, would be in C and the walk would be closed given C. This implies that every internal vertex on ω is on a collider section. These facts imply that ω is a self-inducing walk which, by Lemma C.2, implies that i and j cannot be separated. The lemma holds in each of the exhaustive cases and thus the lemma holds.
SEPARABLE GRAPHICAL MODELS
37
L EMMA C.5. If ω is a non-trivial walk between i and j in graph G that is not a selfinducing walk then ω is closed given C = Ant({ i, j }, G) \ { i, j }. P ROOF. Let graph G contain a non-trivial walk ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) such that ω is not a self-inducing walk. The maximal walk decomposition of ω must contain a non-trivial maximal trek because ω is not a self-inducing walk. Let ω(vi , vk ) with i < k be a non-trivial maximal trek. Note that there must be an internal vertex vj with i < j < k on this maximal trek and this vertex is on a non-collider section of ω. We consider three cases. Case 1: Neither vi nor vk are on collider section of ω. In this case i = 1 and k = n and ω is a trek. From the fact that ω is non-trivial it contains an internal vertex on a non-collider section. This vertex must be in C and thus the walk is not open given C. Case 2: Either vi or vk are on collider sections of ω but not both. Without loss of generality, assume vk is on a collider section and thus i = 1. If vk ̸∈ C then there is a collider section on ω that is not anterior to C and thus the walk is not open given C. On the other hand, if vj ∈ C then the internal vertex vj is in C . This implies that there is a non-collider section of ω that contains a vertex in C and the walk is not open given C. Case 3: Both vi and vk are on collider sections of ω. If either vk ̸∈ C or vi ̸∈ C there is a collider section on ω that is not anterior to C and thus the walk is not open given C. On the other hand, if { vi , vk } ⊆ C then the internal vertex vj is in C . This implies that there is a non-collider section of ω that contains a vertex in C and the walk is not open given C. L EMMA C.6. A walk ω between i and j is open given Ant({ i, j }, G) \ { i, j } in graph G if and only if either (i) there is an edge e(i, j) in G, or (ii) there is a self-inducing walk between i and j . P ROOF. This follows from Lemmas C.1, C.2, and C.5. T HEOREM 3.3 A graph is separable if and only if it contains no self-inducing walks. P ROOF. Let G be a graph. For the forward direction, assume that G is separable. Aiming for a contradiction, suppose that G contains a self-inducing walk between i and j . This implies i ̸∈ Adj(j, G) and, from Lemma C.2, that i and j are not separable. Thus we have a contradiction. Thus G must not contain a self-inducing walk. For the reverse direction, assume that G contains no self-inducing walk. Aiming for a contradiction, assume that G is not separable. This implies that there is a pair of vertices i ̸∈ ∖ Adj(j, G) such that i and j are not separable. This implies that i ⊥ ⊥ G j | Ant({ i, j }, G) \ { i, j } which implies that there is a walk ω between i and j that is open given Ant({ i, j }, G) \ { i, j }. From Lemma C.6 and i ̸∈ Adj(j, G), however, this walk ω must be a self-inducing walk. This is a contradiction as G does not contain any self-inducing walks and the lemma must hold. APPENDIX D: PROOFS RELATED TO ESSENTIALLY ACYCLIC AND ANTERIAL GRAPHS In this section we prove results from Section 5. In addition, we prove a set of useful properties of minimal inducing walks and shortest open walks that are used in this section and in later sections of the appendix.
38
D.1. Characterization of minimal inducing walks. L EMMA D.1. An inducing walk in a graph is minimal if and only if any chord on the walk is (i) between two internal vertices and is directed, or (ii) between an internal vertex and an endpoint of the walk and is either undirected or directed with a tail at the internal vertex. P ROOF. Let ω be an inducing walk in graph G with vertex sequence ver(ω) = (v1 , . . . , vn ) and let e(vi , vj ) for j > i + 1 be a chord of the inducing walk. Assume ω is minimal but that the chord does not satisfy condition (i) or (ii). We consider the possible endpoint for e(vi , vj ). First note that there can be no edge between the endpoints v1 and vn as in this case ω would not be an inducing walk. If vi and vj are both two internal vertices of ω then we are in case (i). If there is either an undirected edge or a bidirected edge, however, then the walk ω(v1 , vi ) + (e(vi , vj )) + ω(vj , vn ) would be an inducing walk that uses a subset of the vertices in ω and thus ω is not minimal. This is a contradiction and thus there is no chord violating condition (i). If one of vi and vj is an endpoint and the other is internal then we are in case (ii). If vi = v1 and there is an arrowhead at vj on chord e(vi , vj ) then (e(v1 = vi , vj )) + ω(vj , vn ) would be an inducing walk that uses a subset of the vertices in ω and thus ω is not minimal. If vj = vn and there is an arrowhead at vi on chord e(vi , vj ) then ω(v1 , vi ) + (e(vi , vn = vj )) would be an inducing walk that uses a subset of the vertices in ω . In either case, ω is not minimal. This is a contradiction and there is no chord violating condition (ii). For the other direction, assume ω is an inducing walk such that all of its chords satisfy conditions (i) and (ii). Assume that there is an inducing walk ω ′ between v1 and vn that uses a subset of vertices in ω . In this case, there must be a chord of ω that is on ω ′ . Let e(vi , vj ) with i < j be the first chord, an edge on ω ′ not on ω . If the first edge of ω ′ is a chord it must be v1 = vi and vj ̸= vn as such a chord does not satisfy either (i) or (ii). In this case, the edge has a tail at vj and cannot be on a collider section on ω ′ . This implies that ω ′ is not an inducing walk. If the edge is not the first edge then the vertex vi must be an internal vertex on ω ′ . If vj = vn then there must be a tail at vi on the edge and vi is not on a collider section of ω ′ . Again ω ′ is not an inducing walk. Finally, if both vi and vj are internal vertices on ω ′ then the chord must be directed and thus both vi and vj cannot be a collider section of ω ′ and thus it is not an inducing walk. In each of these cases, we have a contradiction as ω ′ is assumped to be an inducing walk and thus no such ω ′ exists and ω must be a minimal inducing walk. D.2. The minimal inducing walk decomposition. In this section, we decompose minimal inducing walks that are not self-inducing walks into minimal discriminating inducing walks. In order to define minimal discriminating inducing walks, we need a few additional definitions. A section on an inducing walk is discriminated if the section is not anterior to either endpoint of the inducing walk. An inducing walk discriminates a collider section if the section is discriminated by the walk. An inducing walk is a (simple) discriminating inducing walk if it contains exactly one discriminated section and a compound discriminating inducing walk if it contains more than one discriminated section. Note that an inducing walk containing no discriminated sections is a self-inducing walk. A walk decomposition is a minimal inducing walk decomposition if every walk in the decomposition is a minimal discriminating inducing walk. Finally, a minimal inducing walk decomposition function is a walk decomposition function that decomposes a minimal inducing walk that is not a self-inducing walk into a set of minimal discriminating inducing walks. A recursive minimal inducing walk decomposition function decompiw is given in Algorithm 4. We next prove essential properties and the correctness of the algorithm.
SEPARABLE GRAPHICAL MODELS
39
Algorithm 4 The decompiw algorithm Input: A minimal inducing walk ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) and a graph G = (V, E) containing ω. Output: A minimal inducing walk decomposition of ω. if ω is not a minimal inducing walk or is a self-inducing walk then return ∅ else if ω contains only one discriminated section σi then walks = { ω } if ω(v1 , first(σi )) is an inducing walk then walks = walks ∪ decompiw (ω(v1 , first(σi ))) if ω(last(σi ), vn ) is an inducing walk then walks = walks ∪ decompiw (ω(last(σi ), vn )) return walks else Let σi and σj with i < j be two discriminated sections on ω. return decompiw (ω(v1 , first(σj )) ∪ decompiw (ω(last(σi ), vn ))
The first lemma provides sufficient conditions under which a minimal inducing walk contains another minimal inducing walk as a subwalk. L EMMA D.2. If ω is a minimal inducing walk with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) in graph G then (i) if first(σi , G) ̸∈ Adj(v1 , G) then ω(v1 , first(σi , G)) is a minimal inducing walk, and (ii) if last(σi , G) ̸∈ Adj(vn , G) then ω(last(σi , G), vn ) is a minimal inducing walk. P ROOF. Let ω be a minimal inducing walk with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) in graph G. First we prove (i). Assume first(σi , G) ̸∈ Adj(v1 , G). This implies that ω ′ = ω(v1 , first(σi , G)) is an inducing walk. The walk ω ′ is a minimal inducing walk, by Lemma D.1 and the fact that ω is a minimal inducing walk. The proof for (ii) is symmetric to the proof of (i). If a minimal inducing walk contains a discriminated section it must obey certain adjacency properties that are captured in the next lemma. L EMMA D.3. If a minimal inducing walk in graph discriminates a collider section then there is no chord between the endpoints of the minimal inducing walk and a vertex on the discriminated section. P ROOF. Let G be a graph containing a minimal inducing walk ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) that discriminates section σi . Assume the lemma does not hold. Then there must be a chord e(vi , vj ) such i = 1 or i = n − 1 and vj is on σi . Without loss of generality assume i = 1. Case 1: e(vi , vj ) has an arrowhead at vj . In this case, the walk (e(vi , vj )) + ω(vj , vn ) is an inducing walk that uses a subset of the vertices on ω and thus ω is not a minimal inducing walk. This is a contradiction. Case 2: e(vi , vj ) has a tail at vj . In this case, the section is not discriminated by ω which is a contradiction. In either case we have a contradiction and the lemma must hold.
40
The following lemma allows us to decompose a minimal inducing walk that contains two or more discriminated sections into shorter minimal inducing walks. L EMMA D.4. If ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) discriminates two collider sections σi and σj with 1 < i < j < n then the subwalks ω(v1 , first(σj )) and ω(last(σi ), vn ) are minimal inducing walks containing discriminated sections. P ROOF. Let ω be a minimal inducing walk in graph G with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) that discriminates two collider sections σi and σj with 1 < i < j < n. Let ω1 = ω(v1 , first(σj )) and ωn = ω(last(σi ), vn ). Both ω1 and ωn are collider walks. From Lemma D.3 both are inducing walks. Finally, by Lemma D.1 and the fact that ω is a minimal inducing walk, both are minimal inducing walks. L EMMA D.5. sition function.
The function decompiw is an invertible minimal inducing walk decompo-
P ROOF. If ω is a minimal inducing walk that is not a self-inducing walk then it must have a discriminated section. The correctness of the walk decomposition function follows from the fact that each added walk is a discriminating inducing walk and Lemma D.4, which allows us to decompose a walk into minimal inducing walks with fewer discriminated sections. The walk decomposition function decompiw is invertible due to the fact that no internal section on a minimal inducing walk can be repeated. L EMMA D.6. If ω is a minimal inducing walk in a separable graph G then every collider section on ω is discriminated by some discriminating inducing walk in decompiw (ω, G). P ROOF. We prove by induction on the number of collider section on the inducing walk. Let ω be a minimal inducing walk that is not a self-inducing walk in a graph G. It must have a discriminated section σ . For the base case, σ is the only collider section of ω . In this case, the collider section σ must be discriminated by ω and we are done. For the induction case, we assume it is true for walks with n collider sections and show for n + 1 collider sections. First, the collider section σ is discriminated by ω . If there is a collider section σ ′ on ω closer to v1 than σ then the walk ω(v1 , first(σ)) is a collider walk. By Lemma D.3 and the fact that ω is a minimal inducing walk, the subwalk is also a minimal inducing walk. The walk has at most n collider sections and thus, by the induction hypothesis, the walk discriminates σ ′ . If there is a collider section σ ′ on ω closer to vn than σ then the walk ω(last(σ), vn ) is a collider walk. By Lemma D.3 and the fact that ω is a minimal inducing walk, the subwalk is a minimal inducing walk. The walk has at most n collider sections and thus, by the induction hypothesis, the walk discriminate σ ′ . Thus, every collider section of ω is discriminated by some discriminating inducing walk that is a subwalk of ω . D.3. Minimal inducing walks in separable graphs. L EMMA D.7. If walk ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) is a discriminating inducing walk in graph G that discriminates σi then σi is not anterior to σj for j ̸= i.
SEPARABLE GRAPHICAL MODELS
41
P ROOF. Let walk ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) be a discriminating inducing walk in graph G that discriminates σi . Every collider section other than σi is anterior to v1 or vn . Suppose the lemma does not hold and σi is anterior to σj . In this case σi is anterior to v1 or vn and thus σi is not discriminated by ω . This is a contradiction so the lemma must hold. L EMMA D.8. In a separable graph, no internal section on a minimal inducing walk can be anterior to an adjacent section. P ROOF. Let G be a separable graph. Assume the lemma is not true and that ω is a minimal inducing walk that contains a section σi anterior to an adjacent section. From Lemma D.6, there is a discriminating inducing walk ω ′ that discriminates σ . Result then follows from Lemma D.7. L EMMA D.9. In a separable graph, a minimal inducing walk does not have a chord between adjacent sections. P ROOF. Let G be a separable graph and ω be a minimal inducing walk with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) with a chord between vertex vi on section σa and vertex vj on σa+1 . Case 1: 1 < a < m − 1. In this case, the chord is between two internal sections. By Lemma D.1 and minimality, the chord must be directed. Without loss of generality, assume vi —≻ vj . This, however, contradicts Lemma D.8. Case 2: a = 1 ∨ a = m − 1. In this case, the chord is between an internal section and its adjacent terminal section. By Lemma D.1 and minimality, the chord must have a tail at the internal vertex. This, however, contradicts Lemma D.8. In either case we have a contradiction and the lemma must hold. L EMMA D.10. inducing walk.
In a separable graph, there is no chord on a collider section of a minimal
P ROOF. Suppose the lemma is not true. Let G be a separable graph contain a walk ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) such that there is a chord on collider section σa = (vi , . . . , vl ). Let chord e(vj , vk ) on σa be the chord that maximizes |k − j| and i ≤ j < k ≤ l. Case 1: e(vj , vk ) is undirected or bidirected. In this case the walk ω(v1 , vj ) + (e(vj , vk )) + ω(vk , vn ) is an inducing walk that uses a subset of the vertices in ω and thus ω is not a minimal inducing walk. This is a contradiction. Case 2: e(vj , vk ) is directed. Without loss of generality assume that e(vj , vk ) has an arrowhead at vk . In this case, the walk (e(vj , vk )) + ω(vk , first(σa+1 )) is a collider trisection. Furthermore, by Lemma D.9 the walk is unshielded and thus is a minimal inducing walk. Due to the fact that σa is an undirected walk, the collider trisection is also a self-inducing walk which, by Theorem 3.3, contradicts the assumption that G is a separable graph. Both cases lead to contradictions so the lemma must hold. L EMMA D.11. In a separable graph, a minimal inducing walk has no chord between internal sections that are part of a semi-directed circuit.
42
P ROOF. Assume the lemma is not true and let G be a separable graph containing a minimal inducing walk with a chord between internal sections that are part of a semi-directed circuit in G. Let ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) be a shortest minimal inducing walk in G with a chord between internal sections that are part of a semi-directed circuit in G. The chord must be directed otherwise ω would not be a minimal inducing walk. Let chord e(vi , vj ) of ω be the chord between internal sections and on a semi-directed circuit with the largest jump, that is, such that |j − i| is as large as possible. Without loss of generality, assume that i < j and that edge e(vi , vj ) has an arrowhead at vj . Let vi be on σs and vj be on σu . It must be the case that 1 < s < u < m. Let li = last(σi ) and fi = first(σi ). In order for v1 and vn to be separable there must be a discriminated section σt on ω otherwise ω is a self-inducing walk. Case 1: Section σt is not after σs on ω , that is, 1 < t ≤ s. We consider two subcases. First, lt ̸∈ Adj(vn , G). In this case, then the walk ω(lt , vn ) is a minimal inducing walk containing a chord between internal sections that is on a semi-directed circuit that is shorter than ω . This is a contradiction. Second, lt ∈ Adj(vn , G). In this case, by Lemma D.1, the edge e(lt , vn ) must have a tail which implies that σt is not discriminated. Again we have a contradiction. Case 2: Section σt is not before σu on ω , that is, u ≤ t < m. We again consider two subcases. First, ft ̸∈ Adj(v1 , G). In this case, the walk ω(v1 , ft ) is a minimal inducing walk containing a chord between internal sections that is on a semi-directed circuit that is shorter than ω . This is a contradiction. Second, ft ∈ Adj(v1 , G). In this case, by Lemma D.1, the edge e(ft , v1 ) must have a tail at ft which implies σt is not a discriminated section. Again we have a contradiction. Case 3: Section σt is between σs and σu on ω . If there are multiple discriminated section between σs and σu then choose σt to be the closest to σu . We again consider two subcases. First, lt ∈ Adj(vn , G). In this case, the edge e(lt , vn ) must have a tail at lt by Lemma D.1 which implies σt is not a discriminated section. This is a contradiction. Second, lt ̸∈ Adj(vn , G)). In this case, the walk ω(lt , vn ) must be a self-inducing walk as every collider section between σt and σn is not discriminated. This, by Theorem 3.3, contradicts the assumption that G is separable. In each case we have a contradiction. Thus, a minimal inducing walk in a separable graph can have no chord between internal sections that is part of a semi-directed circuit. L EMMA D.12. In a separable graph, any edge on a minimal inducing walk has an exclusive endmark at any endpoint that is internal to the minimal inducing walk. P ROOF. Suppose the lemma is not true. Let G be a separable graph that contains ω minimal inducing walk ω with ver(ω) = (v1 , . . . , vn ) such that not all of the internal endmarks on ω are exclusive. Without loss of generality assume that the edge is e(vi−1 , vi ) for 1 < i ≤ n and the edge does not have an exclusive endpoint at vi . Case 1: i = 2. In this case, the there must be an e′ (v1 , v2 ) with an tail at v2 . This implies that σ2 ⊆ Ant(σ1 , G) which contradicts Lemma D.8. Case 2: i > 2 and e(vi−1 , vi ) is bidirected. In this case, the there must be an e′ (vi−1 , vi ) with a tail at vi . Because the edge is bidirected, the two endpoints are on adjacent sections of ω . These sections are both collider sections on ω . Thus there is an internal section anterial to an adjacent section which contradicts Lemma D.8. Case 3: i > 2 and e(vi−1 , vi ) is undirected. In this case, the there must be an e′ (vi−1 , vi ) with an arrowhead at vi . Because the edge is undirected, the two endpoints are on the same section σa of ω . This implies that the walk (e′ (vi−1 , vi )) + ω(vi , first(σa+1 )) is a collider trisection.
SEPARABLE GRAPHICAL MODELS
43
Furthermore, by Lemma D.9, the trisection is unshielded an thus minimal inducing walk. This implies, however, that the trisection is a self-inducing walk which contradicts Theorem 3.3. In all three cases we have a contradiction and thus the lemma must hold.
D.4. Properties of shortest open walks . Recall that a walk ω is a shortest open walk given C if ω is open given C and there is no shorter walk that is open given C . L EMMA D.13. Every shortest open walk has no chords between vertices of non-collider sections on distinct maximal treks. P ROOF. Let ω be a shortest open walk between a and b given conditioning set C and the walk decomposition of ω be (τ1 , γ1 , τ2 , . . . , γn−1 , τn ) with maximal treks τi open given C and maximal collider walks γi open given C . Assume that the lemma is not true. Let maximal treks τk with ver(τk ) = (a1 , . . . , am ) and τl with ver(τl ) = (b1 , . . . , bn ) be such that there is a chord e(ai , bj ). Let walk ω ′ = ω(a1 , ai ) + e(ai , bj ) + ω(bj , j) be the walk obtained by replacing the subwalk from ai to bj in ω by the chord e(ai , bj ). We show that for any chord between ai and bj the walk ω ′ is a shorter open walk than ω which is a contradiction. If the edge e(ai , bj ) is undirected then there is a section σ on ω ′ that contains both ai and bj . Furthermore, σ must be a non-collider on ω ′ given C and cannot contain a member of C as all vertices on σ are on non-collider sections of ω . In this case, ω ′ is a shorter open walk than ω which is a contradiction. If the edge e(ai , bj ) is directed, we assume, without loss of generality that it is oriented ai —≻ bj . In this, case the section σ of ω ′ containing ai must be an open non-collider section given C . The section σ ′ of ω ′ containing bj need not be a non-collider section. In the case that it is a non-collider section it is open given C and ω ′ is a shorter open walk than ω which is a contradiction. Next we consider the case in which σ ′ is a collider section on ω ′ . In this case, the section containing bj on ω is a non-collider section which, by Lemma C.4, implies that there is an anterior walk γ = (a1 = bj , . . . , an ) from bj to some vertex an ∈ C ∪ { i, j }. In this case, ω ′ must be a shorter open walk than ω , which is a contradiction. If the edge e(ai , bj ) is bidirected, ai and bj are in separate sections on ω ′ . As in the case above, if the sections are non-colliders they must be open and if they are colliders, they must be anterior to C ∪ { i, j }. Thus, in any combination, ω ′ is a shorter open walk than ω , which is a contradiction. Hence, there can be no chord between vertices of non-collider sections on distinct maximal treks. L EMMA D.14. Every maximal collider walk in the walk decomposition of a shortest open walk is a minimal inducing walk. P ROOF. Let γ be a maximal collider walk on a shortest open walk ω . Let τ and τ ′ be the adjacent maximal treks adjacent to γ on ω . The endpoints γ are both on non-collider section of distinct maximal treks of ω . From Lemma D.13, there can be no chord between the endpoints and thus γ must be an inducing walk. Furthermore, the walk γ must be minimal or there would be a shorter open walk than ω . L EMMA D.15. A vertex on a non-collider section of a shortest open walk given C appears only in one non-collider section on the walk.
44
P ROOF. Suppose the lemma is not true. Let G be a graph that contains a walk ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) that is open given C such that there are vertices vi on non-collider section σh and vk on non-collider section σj on ω such that vi = vk . Without loss of generality assume i < k which implies h ≤ j . The walk ω(v1 , vi ) + ω(vj , vn ) is a shorter open walk given C and thus we have a contradiction and the lemma must be true. D.5. Proofs of Theorems 5.1 and 5.3. In order to prove the theorems we prove a series of lemmas relating to the Anterialize algorithm. L EMMA D.16.
The graph Anterialize(G) is a simple graph.
P ROOF. Let G be a graph and let H = Anterialize(G). If there is no edge between a and b in G then there is no edge between a and b in H . If there are one or more edges between i and j in G then only one edge is added to H because the choice of edge endmarks is uniquely determined by the existence of anterior walks between i and j in G. A graph G satisfies the anterial endmark property if the endmarks of every edge e(a, b) in G is such that there is a tail at a on e(a, b) if and only if there is an anterior walk from a to b in G. L EMMA D.17. A simple graph G is an anterial graph if and only if the graph satisfies the anterial endmark property. P ROOF. For the forward direction, suppose G is an anterial graph. Assume that the anterial endmark property does not hold. In this case there is an edge e(a, b) with an arrowhead at b and there is an anterior walk ω from b to a. We consider two cases. First, e(a, b) has an arrowhead at a. In this case, a ≺—≻ b and b ∈ Ant(a, G) which imply that G is not anterial. Second, e(a, b) has a tail at a. In this case, the walk ω + (e(a, b)) is a semi-directed circuit and again G is not anterial. In either case we have a contradiction so the forward direction holds. For the backward direction, let G be a simple graph and assume that the graph satisfies the anterial endmark property but is not anterial. We consider two cases. First there is an edge a ≺—≻ b and an anterior walk ω from b to a in G. In this case, the graph G does not satisfy the anterial endmark property. Second there is an edge a —≻ b and an anterior walk ω from b to a in G. In this case, the graph G does not satisfy the anterial endmark property. In either case we have a contradiction and the backward direction holds. L EMMA D.18.
If G is a graph then Anterialize(G) is an anterial graph.
P ROOF. From Lemma D.16, the graph Anterialize(G) is simple. Graph Anterialize(G) satisfies the anterial endmark property because every edge e(a, b) added to the the graph Anterialize(G) has a tail at a if and only if there is an anterior walk from a to b. Thus, by Lemma D.17, the graph Anterialize(G) is an anterial graph. L EMMA D.19.
The graph G and Anterialize(G) have the same adjacencies.
P ROOF. Let G be a graph and let H = Anterialize(G). The Anterialize algorithm results in a graph Anterialize(G) with the same adjacencies as the input graph G due to the fact that for every edge e(a, b) in G some edge e′ (a, b) is added to H and if there is no edge e(a, b) in G then no edge is added between a and b in H .
SEPARABLE GRAPHICAL MODELS
L EMMA D.20.
45
If there is an edge e(a, b) in G that has a tail at a then there is no edge
e′ (a, b) in graph Anterialize(G) with an arrowhead at a.
P ROOF. Let G be a graph containing an e(a, b) with a tail at a. In this case a ∈ Ant(b, G). This implies that the e′ (a, b) in Anterialize(G) must be either a — b or a —≻ b. L EMMA D.21. There is an anterior walk from v1 to vn in graph G if and only if there is an anterior walk from v1 to vn in Anterialize(G). P ROOF. For the first direction, let γ be an anterior walk from v1 to vn in G. From Lemma D.19, we know that there is a walk ω in Anterialize(G) with the same vertex sequence. Furthermore, from Lemma D.20 the walk ω must also be an anterior walk as every undirected edge in G remains an undirected edge in Anterialize(G) and every directed edge in G is either an undirected or directed edge in Anterialize(G). For the other direction, let ω be an anterior walk in Anterialize(G) with ver(ω) = (v1 , . . . , vn ). Associate with each edge e(vi , vi+1 ) on ω an anterior walk on γi ; one must exist due to the fact that an edge e(vi , vj ) in Anterialize(G) has a tail at vi if and only if there is an anterior walk from vi to vj in G. The walk γ = γ1 + · · · + γn−1 is an anterior walk from v1 to vn in G. L EMMA D.22. If separable graph G contains minimal inducing walk ω then there is a walk ω ′ in Anterialize(G) such that ω ′ ≡ ω . P ROOF. Let graph G contains a minimal inducing walk ω with ver(ω) = (v1 , . . . , vn ) and let G′ = Anterialize(G). From Lemma D.19 there is a walk ω ′ in G′ such that ver(ω ′ ) = (v1 , . . . , vn ). We consider the possible edge types for each edge e(vi , vi+1 ) for 1 ≤ i < n on ω and the corresponding type of edge in ω ′ . Case 1: vi — vi+1 . In this case, the edge must be an internal edge (i.e.,1 < i < n − 1) and the corresponding edge on ω ′ must be undirected as vi ∈ Ant(vj , G) and vj ∈ Ant(vi , G). Case 2: vi —≻ vj . In this case, the edge must be a terminal edge of ω and i = 1 or i = n. By Lemma D.8, the arrowhead at vj must be an arrowhead in the corresponding edge on ω ′ . Case 3: vi ≺—≻ vj . In this case, either vi or vj must be an internal vertex on ω . If either endpoint is an internal vertex on ω , by Lemma D.8, it must have an arrowhead endmark at the vertex in the corresponding edge on ω ′ . In all cases, all internal endmarks of edges on ω are preserved on edges in ω ′ and thus ω ≡ ω′ . L EMMA D.23. If ω with ver(ω) = (v1 , . . . , vn ) is a minimal inducing walk in separable graph G then there is a minimal inducing walk ω ′ with ver(ω ′ ) = (v1 , . . . , vn ) in Anterialize(G). P ROOF. Let graph G contains a minimal inducing walk ω with ver(ω) = (v1 , . . . , vn ) and let G′ = Anterialize(G). From Lemma D.22 there is a walk ω ′ ≡ ω in G′ . Due to the fact that ω is an inducing walk and Lemma D.19, ω ′ must be an inducing walk. Next we show that inducing walk ω ′ is a minimal inducing walk. Suppose that ω ′ is not a minimal inducing walk. In this case, there must be a minimal inducing walk γ ′ that uses a subset of the vertices of ω ′ . Let e′ (vi , vj ) be the first edge on γ ′ that is a chord on ω ′ . Case 1: e′ (vi , vj ) is the first edge of γ ′ .
46
In this case, i = 1 and the edge e′ (vi , vj ) has an arrowhead at vj and there must be an edge e(v1 , vj ) in G with an arrowhead at vj . But this implies that (e(v1 , vj )) + ω(vj , vn ) is a shorter inducing walk using a subset of the vertices on ω . This implies that ω is not a minimal inducing walk which is a contradiction. Case 2: e′ (vi , vj ) is the last edge of γ ′ . In this case j = n and the proof follows as in Case 1. Case 3: e′ (vi , vj ) is an internal edge of γ ′ . In this case vi and vj must both be on collider sections of ω ′ . From the fact that the edge is on a minimal inducing walk it must either be bidirected or undirected. Case 3.1: vi ≺—≻ vj . In this case, there must be an edge vi ≺—≻ vj in G. This, however, implies that ω(v1 , vi ) + (vj ≺—≻ vj ) + ω(vj , vn ) is a shorter inducing walk using a subset of vertices on ω . This implies that ω is not a minimal inducing walk which is a contradiction. Case 3.2: vi — vj . In this case, there must either be an chord vi ≺—≻ vj or a chord with a directed edge between vi and vj in G. As in Case 3.1, a bidirected edge leads to a contradiction. If, however, there is a directed edge in G, from Lemma D.11, we obtain a contradiction. Thus in all cases we have a contradiction and the lemma must hold. L EMMA D.24. If G is a separable graph and ω ′ is a minimal inducing walk in Anterialize(G) then there is a walk ω ≡ ω ′ in G. P ROOF. Let G be a separable graph and let G′ = Anterialize(G) contain a minimal inducing walk ω ′ with ver(ω ′ ) = (v1 , . . . , vn ) and sec(ω ′ ) = (σ ′ 1 , . . . , σ ′ m ). From Lemma D.19 there is a walk ω in G such that ver(ω) = (v1 , . . . , vn ). Suppose the lemma is not true and that ω ̸≡ ω ′ . Because Anterialize only removes arrowheads there is some σk′ with 1 < k < m on ω ′ that contains an edge vl — vl+1 such that the edge e(vl , vl+1 ) on ω either has an arrowhead at vl or vl+1 . Without loss of generality assume that e(vl , vl+1 ) has an arrowhead at vl . Choose σj′ to be the collider section on ω ′ closest to σ1 that contains an edge vi — vi+1 and an edge e(vi , vi+1 ) with an arrowhead at vi on ω . Case 1: ω(v1 , vi+1 ) is a collider walk. By Lemma D.18, G′ is an anterial graph. This implies that there can be no chord ′ ′ e (vi+1 , vh ) for vh on section σj−1 of ω ′ as the chord must be directed due to the fact that ω ′ is a minimal inducing walk and this would imply there is a bidirected edge with anterial endpoints. This implies, by Lemma D.19 and the fact that Anterialize does not add arrowheads, that ω(lj−1 , vi+1 ) with lj−1 = last(σj ) is a minimal inducing walk in G. By Lemma D.23, this would imply that e′ (vi , vi+1 ) on ω ′ has an arrowhead at vi which is a contradiction. Case 2: ω(v1 , vi+1 ) is a not a collider walk. In this case, there must be an edge vl — vl+1 on ω ′ (v1 , vi+1 ) such that the edge e(vl , vl+1 ) has an arrowhead at vl+1 on ω . Choose σf′ to be the collider section on ω ′ closest to and before σj′ that contains an edge vh — vh+1 and an edge e(vh , vh+1 ) with an arrowhead at vh on ω . Again by Lemma D.18, there can be no chord e′ (vh , vl ) for vl on σf′ +1 as the chord must be directed due to the fact that ω ′ is a minimal inducing walk and this would imply the existence of a bidirected edge with anterial endpoints. This implies, by Lemma D.19 and the fact that Anterialize does not add arrowheads, that ω(lj−1 , vi+1 ) with lj−1 = last(σj ) is a minimal inducing walk in G. By Lemma D.23, this would imply that e′ (vh , vh+1 ) on ω ′ has an arrowhead at vh+1 which is a contradiction. In both cases we have a contradiction and thus ω ≡ ω ′ . T HEOREM 5.3 For every graph G, the graph Anterialize(G) is an anterial graph; if G is a separable graph then Anterialize(G) is a separable graph and G ≡ Anterialize(G).
SEPARABLE GRAPHICAL MODELS
47
P ROOF. Let G be a graph and G′ = Anterialize(G). First, by Lemma D.18, the graph G′ is anterial. Next we show that if G is a separable graph then G ≡ G′ . To prove equivalence, from the definition of equivalence and Lemma B.3, we show that G and Anterialize(G) have the same open walks. For the forward direction, let ω with ver(ω) = (v1 , . . . , vn ) be a shortest open walk given C in G. From Lemma D.14, every maximal collider walk on ω is a minimal inducing walk. From Lemma D.22, there is a walk ω ′ in G′ such that ω ≡ ω ′ . From Lemma D.21, ω ′ must be an open walk given C in G′ . For the backward direction, let ω ′ with ver(ω ′ ) = (v1 , . . . , vn ) be a shortest open walk given C in G′ . From Lemma D.14, every maximal collider walk on ω ′ is a minimal inducing walk. From Lemma D.24, there is a walk ω ′ in G′ such that ω ≡ ω ′ . From Lemma D.21, ω ′ must be an open walk given C in G′ . Combining the forward and backward directions we have shown that G ≡ G′ . Finally, if G is a separable graph then the graph G′ must be separable as it is equivalent to separable graph and has the same adjacencies. The next lemma is directly implied by results from [10]. L EMMA D.25.
if G is acyclic then there is an equivalent separable anterial graph.
P ROOF. The result is a consequence of Theorem 3 and Corollary 2 of [10]. T HEOREM 5.1 A graph is essentially separable if and only if the graph is essentially acyclic. P ROOF. For the forward direction, assume G be an essentially separable graph. By definition, there is an equivalent separable graph Gsep . From Theorem 5.3 there is an equivalent separable anterial graph Gant . As Gant is an acylic graph, thus the forward direction is proved. For the backward direction, assume G is essentially acyclic. Thus there is an acyclic equivalent graph Gacyc ≡ G. From Lemma D.25, there is an equivalent separable acyclic graph Gsep ≡ Gacyc . Thus the backward direction is proved. D.6. Proofs related to statistical equivalence. In order to prove Corollaries 5.2 and 5.4 it is useful to define comparison of graph families. The relations ⊆ and = are the standard set theoretic comparison of the sets of graphs that allow for the comparison of graphical expressivity of two graph families. We define ⊑ and ≡ in terms of the independence models of the two graph families. These relations are a comparison of the separation expressivity of graph families and are defined as F ≡H
if
Imodels(F) = Imodels(H)
F ⊑H
if
Imodels(F) ⊆ Imodels(H)
where Imodels(H) = { I(H) | H ∈ H }. The following lemmas related graphical expressivity of graph families to the separational expressivity of graph families and the statistical expressivity of graphical model families. L EMMA D.26.
If F ⊑ H then MF ⊑ MH .
48
P ROOF. The lemma holds due to the fact that equivalent graphs define equivalent independence models (Proposition 2.5) and the set of distributions defined by a graphical model is defined in terms of the independence model of the defining graph and the fixed defining family of distributions. sep . C OROLLARY 5.4 ME(Gsep ) ≡ MGant
sep sep P ROOF. By definition, Gsep ≡ E(Gsep ). Gant = Gant ∩ Gsep and thus Gant ⊆ Gsep which sep sep implies that Gant ⊑ Gsep . From Theorem 5.3, we have that Gsep ⊑ Gant . Combining these sep sep facts we have Gsep ≡ Gant . By transitivity, we have E(Gsep ) ≡ Gant , and, by Lemma D.26, sep . ME(Gsep ) ≡ MGant
C OROLLARY 5.2 ME(Gsep ) ≡ MGacyc . sep sep P ROOF. From Lemma D.25 we have Gacyc ⊑ Gant . From the fact that Gant ⊆ Gacyc we sep sep also have Gant ⊑ Gacyc . This implies that Gacyc ≡ Gant . Using this fact and Corollary 5.4, we sep . have E(Gsep ) ≡ Gacyc . Then, by Lemma D.26, it also follows that ME(Gsep ) ≡ MGant
APPENDIX E: PROOFS RELATED TO INDUCING VERTICES AND GRAPHICAL CHARACTERIZATIONS OF ESSENTIAL GRAPH FAMILIES We prove propositions related to inducing vertices and graphical characterizations of essential graph families presented in Section 6 and that are useful in many of the proofs in subsequent sections. P ROPOSITION 6.1 The induced dependence property holds in any semi-graphoid independence model. P ROOF. Suppose that the induced independence property does not hold in some semigraphoid independence model. Let independence model I = (V, T ) be such a semi-graphoid and let A, B, C, D be disjoint subsets of V such that the induced independence property does not hold. In that case, it must ∖ be the case that (1) A ⊥ ⊥I B | C and (2) A ⊥ ⊥ I B | CD . In order for the property to not hold it must be the case that either A ⊥ ⊥I D | CB or D ⊥ ⊥I B | CA. We consider these two cases. Case 1: (3) A ⊥ ⊥I D | CB . From (1) and (3) and contraction we have (4) A ⊥ ⊥I BD | C . From (4) and weak union we get (5) A ⊥ ⊥I B | CD which contradicts (2). Case 2: (6) D ⊥ ⊥I B | CA. From (1) and (6), symmetry and contraction we have (7) B ⊥ ⊥I AD | C . From (7) and weak union and symmetry we get (8) A ⊥ ⊥I B | CD which contradicts (2). In either case we have a contradiction so the induced independence property must hold in every semi-graphoid independence model. E.1. Proofs related to essentially undirected graphs. In this section we prove Theorem 6.2. An independence model I satisfies the pairwise upward stable property if for all C ⊆ D , if i ⊥ ⊥I j | C ⇒ i ⊥ ⊥I j | D . The following was proved in [20]. T HEOREM E.1. [Corollary 29, Sadeghi 2017] If G is a graph and independence model I is such that I = I(G) then G is essentially undirected if and only if I is a graphoid and both the pairwise upward stability and weak transitivity independence properties hold.
SEPARABLE GRAPHICAL MODELS
49
L EMMA E.2. Graph G is essentially undirected if and only if I(G) satisfies pairwise upward stability. P ROOF. Let G be a graph. From Propositions 2.3 and 2.4, I(G) is a graphoid that satisfies weak-transitivity. The result then follow from Theorem E.1. An independence model I is graphical if there is a graph G such that I = I(G). Note that graphical independence mdoels as defined in [20] is subset of graphical independence models in our paper as [20] only considers acyclic graph. L EMMA E.3. If independence model I is graphical then I satisfies pairwise upward stable if and only if contains no inducing vertices. P ROOF. Let independence model I be graphical. This implies there is a graph G such that I = I(G). From Propositions 2.3 and 2.4, I(G) is a composition graphoid that satisfies weak-transitivity. For the forward direction, assume that I satisfies pairwise upward stability. Aiming for a contradiction, assume that I contains an inducing vertex k for (A, B, C). Thus we have ∖ ∖ ⊥ I B | Ck and composition there is some a ∈ A A⊥ ⊥I B | C and A ⊥ ⊥ I B | Ck . From A ⊥ ∖ and b ∈ B such that a ⊥ ⊥ I b | Ck . From A ⊥ ⊥I B | C and decomposition we have a ⊥ ⊥I b | C . Thus, I does not satisfy pairwise upward stability. This is a contradiction and this direction must hold. For the reverse direction, assume that I contains no inducing vertex. Aiming for a contradiction, assume I does not satisfy pairwise upward stability. In this case there are vertices ∖ i, j and sets C ⊂ D such that i ⊥ ⊥I j | C and i ⊥ ⊥ I j | D . If |D \ C| > 1, we can choose sets ∖ C ′ ⊇ C and D′ ⊆ D such that |D′ \ C ′ | < |D \ C|, i ⊥ ⊥I j | C and i ⊥ ⊥ I j | D . Thus, without loss of generality, we assume |D \ C| = 1. Let k = D \ C . In this case k is an inducing vertex for (i, j, C). This is a contradiction and this direction must hold. T HEOREM 6.2 A graph G is essentially undirected if and only if I(G) contains no inducing vertex. P ROOF. Let G be a graph. For the forward direction, assume G is essentially undirected. By Lemma E.2, I(G) satisfies pairwise upward stability. In addition, I(G) is graphical, thus by Lemma E.3, we have that I(G) has no inducing vertices. For the backward direction, assume that I(G) contains no inducing vertices. By Lemma E.3, we have that I(G) satisfies pairwise upward stability. By Lemma E.2 we have that I(G) must be equivalent to some undirected graph and thus G is essentially undirected. E.2. Proof related to ordering. In Section 6, we defined the concept of an induced preorder ⪅G of a graph G. We consider several ordered independence properties for graphs G and prove two propositions related to ordering; Propositions 6.4 and 6.5. L EMMA E.4. If b ∈ IV(i, j, C, G) then there exists a walk between i and b that is open given Cj and, furthermore, any walk between i and b that is open given Cj is weakly into b. P ROOF. Let G be a graph such b ∈ IV(i, j, C, G). From b ∈ IV(i, j, C, G) we have that ∖ ∖ ∖ i⊥ ⊥G j | C and i ⊥ ⊥ G j | Cb. From Proposition 6.1 we have i ⊥ ⊥ G b | Cj and j ⊥ ⊥ G b | Ci. This implies that the there are walks ωi between i and b that is open given Cj and ωj between j and b that is open given Ci. The walk ωi (i, b) + ωj (b, j) is a walk between i and j and is
50
open given Cb if and only if both ωi and ωj are into b. Suppose that there is a walk ωi′ between i and b open given Cj that is not weakly into b. In this case, the walk ωi′ + ωj is a walk open given C which is a contradiction. Similarly, suppose there is a walk ωj′ between j and b open given Ci that is not weakly into b. In this case, the walk ωi + ωj′ is a walk open given C which is a contradiction. Thus every such walk must be weakly into b. L EMMA E.5.
If b ∈ IV(i, j, C, G) then b ̸∈ Ant({ i, j }, G).
P ROOF. Suppose the proposition is false and that, b ∈ IV(i, j, C, G) and b ∈ Ant({ i, j }, G). From the definition of an inducing vertex and b ∈ IV(i, j, C, G) we know that i ⊥ ⊥G j | C ∖ ∖ and i ⊥ ⊥ G j | Cb. From i ⊥ ⊥ G j | Cb, there is a walk ω between i and j that is a connecting walk given Cb. This implies that b ̸∈ { i, j } otherwise the walks ω would be closed. Thus we have b ∈ Ant({ i, j }, G) \ { i, j }. From i ⊥ ⊥G j | C , ω is not a connecting walk given C . The fact that ω is open given Cb, implies that ω contains no non-collider section with a vertex in Cb. Thus ω must contain one or more collider sections closed given C but open given ∖ Cb. Thus, from i ⊥ ⊥ G j | Cb, each such closed collider sections must contain b. Because b ∈ Ant({ i, j }, G) \ { i, j } there must be an anterior walk from b to a vertex in C ∪ { i, j } in G. Thus, ω is an open walk given C which, by Lemma B.3 implies there is a connecting walk given C which is a contradiction. Therefore, the proposition must be true. An independence model I satisfies ordered upward separation stability property with respect to ⪅ if A ⊥ ⊥I B | C and D ⊆ V⪆ABC \ ABC then A ⊥ ⊥I B | CD . L EMMA E.6.
I(G) satisfies ordered upward separation stability with respect to ⪅G .
P ROOF. Let G be a graph such that, A ⊥ ⊥G B | C , D ⊆ V⪆ABC = Ant(ABC, G) \ ABC . We prove by induction on the size of D For the base case, |D| = 0 we have C = CD and thus the independence A ⊥ ⊥G B | CD holds by assumption. For this induction case we assume that the property holds for all sets D′ ⊂ D (i.e., |D′ | ≤ n − 1) and and show that it holds for |D| = n. Choose a vertex k ∈ D and let E = CD \ { k }. By the induction hypothesis we have A ⊥ ⊥G B | E. Aiming at a contradiction assume that ∖ ∖ ⊥ G j | Ek. A⊥ ⊥ G B | Ek. This implies that there is some i ∈ A and b ∈ B such that i ⊥ From A ⊥ ⊥G B | E we have that i ⊥ ⊥G j | E. Thus we have that k ∈ IV(i, j, E, G). From ∖ Proposition E.5, k ̸∈ Ant({ i, j }, G) and, thus, k ∈ Ant(E \ { i, j }, G). From i ⊥ ⊥ G j | Ek , there is some connecting walk between i and j given Ck in G. Let ω be any such connecting walk. It must be the case that k in not on any non-collider section of ω and every collider section on ω contains a vertex in Ek otherwise ω would not be a connecting walk. Next, from i⊥ ⊥G j | E , there must be on some collider section in ω that does not contain any vertex in E but contains k . This, however, implies that ω is open given E as every such collider section is anterior to E because k ∈ Ant(E \ { i, j }, G). From Lemma B.3, this implies there is a connecting walk between i and j given E which contradicts i ⊥ ⊥G j | E. Thus, we have a contradiction and the lemma must be true. P ROPOSITION 6.3 If D ∈ IS(A, B, C, G) then D ∩ Ant(C ∪ { i, j }, G) ̸= ∅ (or equivalently D ̸⊆ V⪆Cij ). P ROOF. Follows from Lemma E.6. P ROPOSITION 6.4 If b ∈ IV(i, j, C, G) then b ̸∈ Ant(C ∪ { i, j }, G) (or equivalently b ∈ / V⪆Cij ).
SEPARABLE GRAPHICAL MODELS
51
P ROOF. Follows from Lemma E.6. An independence model I satisfies ordered downward separation stability property with respect to ⪅ if A ⊥ ⊥I B | CD and D ∩ V⪆ABC = ∅ then A ⊥ ⊥I B | C . L EMMA E.7.
I(G) satisfies ordered downward separation stability with respect to ⪅G .
P ROOF. Aiming for a contradiction, assume that the claim does not hold for graph G. Choose D to be a smallest set such that there exists A, B, C such that A ⊥ ⊥G B | CD , ∖ D ∩ V⪆ABC = D ∩ Ant(ABC, G) = ∅ and A ⊥ ⊥ G B | C . Due to the fact that D ∩ Ant(ABC, G) = ∅, there exists a subset E ⊆ D such that E ∩ Ant(CD \ E, G) = ∅. From the fact, D is chosen to be a smallest set and D ∩ Ant(ABC, G) = ∅, it must be the case that ∖ A⊥ ⊥ G B | CD \ E . This implies that there is a connecting walk between i ∈ A and j ∈ B given CD \ E in G. Let ω be any such connecting walk. Because ω is a connecting walk given CD \ E , every collider section of ω must contain a member of CD \ E . From the choice of E ∩ Ant(CD \ E, G) = ∅, no collider section containing a vertex in E can contain a vertex in CD \ E. This implies that ω must also be a connecting walk given CD . This is a contradiction so the proposition holds. An important property of vertices in the same equivalence class is that they have the same anterior sets. L EMMA E.8.
If a ≈G b then Ant(a, G) = Ant(b, G).
P ROOF. We assume that a ≈G b in graph G. In this case, there is an anterior walk ωab from a to b in G and an anterior walk ωba from b to a in G. For the first direction, let c ∈ Ant(a, G). This implies that there is an walk ωca from c to a in G. The walk ωca + ωab is an anterior walk from c to b which implies that c ∈ Ant(b, G). The other directions follows by a similar argument. P ROPOSITION 6.5 For any graph G, the inducing vertex equivalence property holds in I(G) with respect to ⪅G . P ROOF. Let graph G be such that a ∈ IV(i, j, C) and b ∈ [a]G ⊥G ≈ . This implies that i ⊥ ∖ j | C and i ⊥ ⊥ G j | Ca. Thus there is an open walk ω between i and j given Ca which implies ω contains no non-collider section that contains a vertex in Ca. Because, i ⊥ ⊥G j | C , there are no non-collider section that is anterior to a but not C . From Lemma E.8, such a section is anterior to b for any b ∈ [a]≈ . This implies that the walk is open given Cb and thus the claim holds. E.3. Proofs related to essentially separable graphs. We next prove Theorem 6.6 A useful equivalence relation for graphs is a ∼G b which holds if there is an undirected walk between a and b. L EMMA E.9.
if G is acyclic and a ≈G b then a ∼G b.
P ROOF. Let G = (V, E) be acyclic, that is, it contains no semi-directed circuit, and let a =G b . Case 1: a = b. In this case, the equality gives a ∼G b.
52
Case 2: a ̸= b. In this case, we have a ̸∈ Ant(b, G) ∧ b ̸∈ Ant(a, G). From that fact that a ̸= b there must be anterior walks from a to b and from b to a. Let γab be an arbitrary anterior walk from a to b and let γba be an arbitrary anterior walk from b to a. If either or both of these walks is not undirected then the walk γab + γba would be a semi-directed circuit and G would not be acyclic. This implies that all anterior walk between a and b are undirected and thus a ∼G b. In either case we have a ∼G b so the lemma holds. L EMMA E.10. respect to ⪅G .
If G is acyclic then I(G) satisfies inducing set equivalence property with
P ROOF. Let G be an acyclic graph. Assume that the inducing set property does not hold. In that case there is a set D such that d ∈ D and D = [d]G ≈ and D ∈ IS(A, B, C, G) and for E , a non-empty subset E ⊆ [d]G we have A ⊥ ⊥ B | CE . From D ∈ IS(A, B, C, G), we G ≈ ∖ ∖ have A ⊥ ⊥I B | C and A ⊥ ⊥ I B | CD . From A ⊥ ⊥ I B | CD there must be a walk ω between i ∈ A and j ∈ B that is connecting given CD . From Lemma C.4, every vertex on ω is in Ant(CDij, G). This implies that no vertex in D can be a non-collider on ω otherwise the walk ω would not be a connecting walk given CD . Note that for every non-empty E ⊂ [d]G ≈ it is the case that Ant(CDij, G) = Ant(CDij, G). This fact implies that ω is also open given CE which is a contradiction. Thus the claim holds. The proof of the following lemma relies on definitions of ordered upward-stability (OUS) and ordered downward-stability (ODS) with respect to ⪅ from [20]. An independence model I satisfies ordered upward-stability (OUS) with respect to ⪅ if i⊥ ⊥I j | C and k ∈ V⪆ij or k ≈ l ∈ C then i ⊥ ⊥I j | Ck . An independence model I satisfies ordered downward-stability (ODS) with respect to ⪅ if i ⊥ ⊥I j | C and k ∈ C is such that k ∈ V \ V>C\k and k ∈ V \ V⪆ij then i ⊥ ⊥ j |C \k L EMMA E.11. If there exists a preeorder ⪅ for V such that independence model I for V satisfies ordered upward separation stability, ordered downward separation stability, and the inducing set equivalence property with respect to ⪅ then OUS and ODS with respect to ⪅ hold for I . P ROOF. Let ⪅ be a preorder for V such that independence model I for V satisfies ordered upward separation stability, ordered downward separation stability, and the inducing set equivalence property with respect to ⪅. First, if I satisfies ordered upward separation stability it satisfies OUS. Next, we show that I must satisfy ODS. Aiming for a contradiction, assume that i ⊥ ⊥I j | C ∖ and k be a vertex such that k ∈ V \ V>C\k and k ∈ V \ V⪆ij but that i ⊥ ⊥ I j | C \ k. Let E = C ∩ [k]≈ and D = C \ E. From ordered downward separation stability (Lemma E.7), we have that i ⊥ ⊥I j | D. We continue by cases. Case 1: i ⊥ ⊥I j | Dk . We consider two sub-cases. Case 1.1: , |E| = 1. In this case, C = Dk , and from the fact that i ⊥ ⊥I j | D , we have i⊥ ⊥I j | C \ k which is a contradiction. ∖ Case 1.2: |E| > 1. In this case, we again have C = DE . From the fact that i ⊥ ⊥I j | C \ k and i ⊥ ⊥I j | D , we have E \ k ∈ IS(i, j, D, I). Thus we have that E ∈ IS(i, j, D, I) and, by ∖ the inducing set equivalence property, we have i ⊥ ⊥ I j | C which is a contradiction. ∖ Case 2: i ⊥ ⊥ j | Dk . In this case, k ∈ IS(i, j, D, G). From the inducing set equivalence ∖ property we have that E ∈ IS(i, j, D, I) and it follows that i ⊥ ⊥ I j | C . Again we have a contradiction. In every case we have a contradiction and thus ODS must hold in I .
SEPARABLE GRAPHICAL MODELS
53
An independence model I is acyclic if there is an acyclic graph G such that I = I(G). Note that in [20], only acyclic graphs are considered so graphical in [20] is equivalent to acyclic in this paper. T HEOREM E.12. [Theorem 17, Sadeghi 2017] If G is an acyclic graph then independence model I = I(G) if and only if I(G) is a compositional graphoid that satisfies weaktransitivity and ⪅G such that I satisfies ordered upward-stability and ordered downwardstability with respect to ⪅G . T HEOREM 6.6 G is essentially separable if and only if I(G) satisfies the inducing set equivalence property with respect to ⪅G . P ROOF. For forward direction, we assume G is essentially separable. By Theorem 5.1, G is essentially acyclic which implies that there is an equivalent acyclic graph H ≡ G. By Proposition E.10, I(G) = I(H) satisfies the inducing set equivalence property with respect to ⪅G . For the other direction, we assume there is a graph G such that I(G) satisfies the inducing set equivalence property with respect to preorder ⪅G . From Propositions 2.3 and 2.4, I(G) is a compositional graphoid that satisfies weak-transitivity. From Lemmas E.6 and E.7, I(G) satisfies ordered upward separation stability and ordered downward separation stability with respect to ⪅G . From Lemma E.11, I(G) satisfies ODS and OUS with respect to ⪅G . Thus we can apply Theorem E.12 to obtain the conclusion that I is acyclic. From the definitions of an acyclic independence model and essentially acyclic and Theorem 5.1, we have that G is essentially separable. APPENDIX F: PROOFS RELATED TO THE CHARACTERIZATIONS OF SEPARATION EQUIVALENCE In this section we prove Theorems 7.1, and 8.2. Each of these theorems provides an alternative equivalent characterization of the equivalence of two separable graphs. In addition, we prove Proposition 8.1 that proves that an edge with an induced arrowhead has an exclusive arrowhead. F.1. Equivalence to same adjacencies and induced arrowheads. L EMMA F.1. Two equivalent separable graphs have the same vertex separability and the same induced arrowheads. P ROOF. Let G and H be two equivalent separable graphs. The properties of vertex separability and induced arrowheads are separational properties and invariant to separation equivalence. That is, these properties are completely determined by the independence and dependence statements true in the graph. As G and H are equivalent they must agree on these properties. L EMMA F.2. Two separable graphs have the same vertex separability if and only if they have the same adjacencies. P ROOF. Let G and H be two separable graph. From the fact that the two graphs are separable, vertex separability corresponds to adjacency. Thus the two graphs have the same adjacency.
54
F.2. Same adjacencies and same induced arrowheads to same minimal inducing walks. L EMMA F.3. If ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) is a minimal discriminating inducing walk that discriminates section σk in a graph G, and d is on σi ̸= σk then for all C ⊆ V it is the case that d ̸∈ IV(v1 , vn , C, G) P ROOF. Let ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) be a minimal discriminating inducing walk that discriminates section σk in a graph G, and d is on σi ̸= σj . Suppose that there is a C ⊆ V such that d ∈ IV(v1 , vn , C, G). Then by Proposition E.5, d ̸∈ Ant({ v1 , vn }, G). This cannot be the case as all sections other than σk must be anterior to the endpoints of ω . Thus we have a contradiction and for all C it is the case that d ̸∈ IV(v1 , vn , C, G). L EMMA F.4. If ω with ver(ω) = (v1 , . . . , vn ) is a minimal discriminating inducing walk that discriminates section σ in a separable graph G, and b ∈ Post(σ, G) then there is a C ⊆ V such that b ∈ IV(v1 , vn , C, G). P ROOF. Let ω with ver(ω) = (v1 , . . . , vn ) be a minimal discriminating inducing walk that discriminates section σ in a separable graph G and b ∈ Post(σ, G). From separability of G we have that v1 ⊥ ⊥G vn | C for C = PropAnt({ v1 , vn }, G). The walk ω is open given b and ∖ thus, by Lemma B.3, v1 ⊥ ⊥ G vn | Cb. Thus b ∈ IV(v1 , vn , C, G). L EMMA F.5. If separable graph G contains a minimal discriminating inducing walk ω with sec(ω) = (σ1 , . . . , σm ) that discriminates σj and edge e(d, b) such that d is on a section σi ̸= σj of ω and b ∈ Post(σj , G) then the edge e(d, b) has an induced arrowhead at b in G. P ROOF. Follows from Lemmas F.3 and F.4. P ROPOSITION 8.1 If an edge e(d, b) in a graph G has an induced arrowhead at b then the edge has an exclusive arrowhead at b in G. P ROOF. Let G be a graph containing an edge e(d, b) that is an induced arrowhead at b. In this case, there are vertices v1 and vn vertex set C such that b ∈ IV(v1 , vn , C, G) and d ̸∈ IV(v1 , vn , C, G). From b ∈ IV(v1 , vn , C, G) and Lemma E.4 there is a vertex set C and connecting walks γ1 between v1 and b open given Cvn and γn between vn and b open given Cv1 both weakly into b such that v1 ⊥ ⊥ G vn | C . Suppose that e(d, b) does not have an exclusive arrowhead at b in G. Let e′ (d, b) be an edge with a tail at b in G. Consider the walk ω ′ = γ1 (v1 , b) + (e′ (d, b), e′ (d, b)) + γn (b, vn ). The walk ω ′ is open given Cd. This however implies that d ∈ IV(i, j, C, G) and we have a contradiction. Thus the edge e(d, b) must have an exclusive arrowhead at b in G. L EMMA F.6. If separable graphs have the same adjacencies and same induced arrowheads then they have the same minimal inducing walks. P ROOF. Let G and G′ be anterial graphs with the same adjacencies and same induced arrowheads. We prove that every minimal inducing walk in G is a minimal inducing walk in G′ by induction on the number of collider sections.
SEPARABLE GRAPHICAL MODELS
55
For the base case, we consider a minimal inducing walk ω with ver(ω) = (v1 , . . . , vn ) and collider section σ = (v2 , vn−1 ) in G. By Lemma F.5, the edge e(v1 , v2 ) on ω has an induced arrowhead at v2 and the edge e(vn−1 , vn ) on ω has an induced arrowhead at vn−1 . This implies the edge e′ (v1 , v2 ) on ω ′ has an induced arrowhead at v2 and the edge e′ (vn−1 , vn ) on ω ′ has an induced arrowhead at vn−1 in G′ . By Proposition 8.1, these edges have arrowheads at v2 and vn−1 . By Lemma D.10, σ is chordless in ω and must also be chordless in ω ′ due to G and G′ having the same adjacencies. Suppose σ is not a collider section on ω ′ in G′ . In this case there must be an edge e′ (vi , vi+1 ) with 1 < i < n − 1 with an arrowhead at either vi or vi+1 . Without loss of generality assume there is an arrowhead at vi . Furthermore choose smallest j > 1 such that there is an edge e′ (vj , vj+1 ) with an arrowhead at vj . In this case the walk ω ′ (v1 , vj+1 ) is an unshielded collider trisection due to Lemma D.9 and the fact that G and G′ have the same adjacencies. This implies that e′ (vj , vj+1 ) has an induced arrowhead at vj which in turn implies that e(vj , vj+1 ) on ω has an induced arrowhead. Finally, by Proposition 8.1, the arrowhead must be exclusive in G and σ is not a collider section which is a contradiction. For the inductive case, we assume that the lemma is true for minimal inducing walks with n collider sections and prove for n + 1 collider section. Let ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) be a minimal inducing walk with n + 1 collider section. ω must discriminate some section σj otherwise it would be a self-inducing walk and that would imply that G is not separable by Theorem 3.3. Let γ ′ with ver(γ ′ ) = (vi , . . . , vk+1 ) be the collider trisection containing σj on ω ′ . In that case, by an argument similar to the base case, the edge e′ (vi , vi+1 ) and the edge e′ (vk , vk+1 ) have arrowheads at their internal vertices and γ(vi+1 , vk ) is a collider section. If i > 2 then by Lemmas D.2 and D.3, ω(v1 , vi+1 ) must be a minimal inducing walk and there must be must be a minimal inducing walk ω ′ (v1 , vi+1 ). Similarly, if k < n−1 then by Lemmas D.2 and D.3, ω(vk , vn ) must be a minimal inducing walk and there must be a minimal inducing walk ω ′ (vk , vn ). Thus, ω ′ (v1 , vn ) is an inducing walk. If ω ′ (v1 , vn ) is not a minimal inducing walk then there must be an edge e((, v)h , vj ) with h < i and vj on σj with an arrowhead at vj or e((, l), vj ) with l > k and vj with an arrowhead at vj . In either case, ω(v1 , vn ) cannot be a minimal inducing walk which is a contradiction. Thus ω ′ (v1 , vn ) is a minimal inducing walk. F.3. Same adjacencies and minimal inducing walks to equivalence. L EMMA F.7. If anterial graphs G and G′ have the same adjacencies and the same minimal inducing walks and ω is a shortest open walk given C in G then there is a walk ω ′ such that ω ≡ ω ′ . P ROOF. Let G and G′ be two anterial graphs with the same adjacencies and same minimal inducing walks. Let walk ω be a shortest open walk given C in G and let ver(ω) = (v1 , . . . , vn ) and decompw (ω) = (τ1 , γ1 , τ2 , . . . , γm−1 , τm ). From G and G′ having the same adjacencies, there is a walk ω ′ in G′ with ver(ω ′ ) = (v1 , . . . , vn ). Suppose that ω ̸≡ ω ′ . In order for this to be the case, the walk decompositions of the two walks must be different. First note that if two walks have different maximal treks they must have different maximal collider walks. Thus there must be a γi on ω such that γi′ on ω ′ is not a maximal collider walk on G′ . From Lemma D.14, every γi on ω must be a minimal inducing walk in G. Anterial graphs are simple graphs and thus every endmark on an edge is exclusive, thus γi ≡ γi′ . Suppose, however, that γi′ is not a maximal collider walk. In this case there must be a subwalk ω ′ (vh , vj )
56
that contains γi′ that is a maximal collider walk on ω ′ . This must be an inducing walk due to Lemma D.13 and the fact that G and G′ have the same adjacencies. In this case, there must be a minimal inducing walk γ ′ between vh and vj that contains a subset of the vertices on ω ′ (vh , vj ) in G′ . Thus there must be a minimal inducing walk γ ≡ γ ′ in G. This however contradicts the assumption that ω is a shortest open walk as the walk ω(v1 , vh ) + γ + ω(vj , vn ) would be a shorter open walk given C . Thus there is no such γi and ω ≡ ω ′ . L EMMA F.8. If the endpoints of a discriminating inducing walk are separable and the walk discriminates section σ then every vertex in Post(σ, G) is an inducing vertex for the endpoints of the walk. P ROOF. Let ω be a discriminating inducing walk between i and j that discriminates section σ in graph G. Because i and j are separable there is some set that separates them. Let C be an arbitrary separating set for i and j , that is, i ⊥ ⊥G j | C . Let v be a arbitrary vertex in Post(σ, G). The walk ω is open given C ∪ { v } and, by Lemma B.3 there is a connecting ∖ walk ω ′ in G and i ⊥ ⊥ G j | Cv . Thus v is an inducing vertex for i and j given C . L EMMA F.9.
Every shortest anterior walk in an anterial graph is chordless.
P ROOF. Let G be an anterial graph and ω be a shortest anterior walk with vertex sequence ver(ω) = (v1 , . . . , vn ). Suppose that there ω has a chord e(vi , vj ) for i < j − 1. If the edge has a tail at bi then there would be a shorter anterior walk γ(v1 , vi ) + e(vi , vj ) + γ(vj , vm ) an thus there must be an arrowhead at vi . However, if vi ≺—≻ vj then there would be a bidirected edge with one endpoint having anterior walk to the other which contradicts G being an anterial graph. Finally, if vi ≺— vj then there would be a semi-directed circuit in G which again contradicts G being an anterial graph. Thus, a shortest anterior walk must be chordless in an anterial graph. L EMMA F.10. In an anterial graph, no internal section on a minimal inducing walk can be anterior to an adjacent section. P ROOF. Let G be an anterial graph. Assume the lemma is not true and that ω with sec(ω) = (σ1 , . . . , σm ) is a minimal inducing walk that contains a section anterior to an adjacent section. Without loss of generality assume that σi is anterior to σi+1 and that there is an anterior walk γ ′ = ver(γ ′ ) = (vp , . . . , vq ) with vp on σi and vq on σj . Let li = last(σi ) and fi+1 = first(σi+1 ) and γ = ω(li , vp ) + γ ′ + ω(vq , fi+1 ). The edge e(li , fi+1 ) on ω must either be li —≻ fi+1 or li ≺—≻ fi+1 . In the first case, the circuit γ + (e(li , fi+1 )) is a semi-directed circuit and G is not an anterial graph. This is a contradiction. In the second case, li ≺—≻ fi+1 has an anterior walk from one endpoint to the other and thus G is not an anterial graph. This is a contradiction. In either case, we have a contradiction and thus the lemma must be true. L EMMA F.11. If two separable anterial graph G and G′ have the same adjacencies and same minimal inducing walks then they are equivalent; that is G ≡ G′ . P ROOF. Let G and G′ be separable anterial graphs with the same adjacencies and same minimal inducing walks. Aiming for a contradiction, assume that G ̸≡ G′ . Let there be a walk between v1 and vn that is connecting given C in one walk but not the other. Without loss of generality, assume ∖ v1 ⊥ ⊥ G vn | C and v1 ⊥ ⊥ G ′ vn | C .
SEPARABLE GRAPHICAL MODELS
57
Choose ω with ver(ω) = (v1 , . . . , vn ) and decompw (ω) = (τ1 , γ1 , τ2 , . . . , γm−1 , τm ) to be a shortest open walk given C in G and let ω ′ be a walk in G′ with ver(ω ′ ) = (v1 , . . . , vn ). ω ′ must not be open given C in G′ due to v1 ⊥ ⊥ G ′ vn | C . From Lemma F.7, we have ω ≡ ω ′ which implies that sec(ω) = sec(ω ′ ). Let sec(ω) = (σ1 , . . . , σp ), fi = first(σi ) and li = last(σi ). Note that sec(ω) = sec(ω ′ ) due to the fact that ω ≡ ω′ . Choose smallest j with 1 < j < p such that ω ′ (v1 , fj+1 ) is not open given C . There must be one otherwise ω ′ (v1 , vl ) would be an open walk given C . Let γd = ω(lh , fj+1 ) be a minimal discriminating inducing walk that discriminates σj on walk ω(v1 , fj+1 ). Note that 1 ≤ h < j . It must be the case that σj is anterior to Cv1 in G otherwise the walk ω would not be open in G. Furthermore, σj is not anterior to C ∪ { v1 , fj+1 } in G′ otherwise the walk ω ′ (v1 , fj+1 ) would be open given C . Let γf = ver(γ ′ ) = (a1 , . . . , aq ) be a shortest anterior walk from fj to a vertex in C ∪ { v1 , fj+1 } in G and let γf′ be the corresponding walk in G′ . By Lemma F.9, γf must be chordless and, thus, by G and G′ having the same adjacencies, γf′ is also chordless. Choose r to be largest such that ar ∈ Post(σj , G′ ) and let s = r + 1 and thus as ̸∈ Post(σj , G′ ). Note that e′ (ar , as ) on γf′ must have an arrowhead at ar . Suppose as ̸∈ Adj(lj−1 , G′ ). In this case the walk ω ′ (lj−1 , fj ) + γf′ (fj , ar ) + (e′ (ar , as )) in G′ must contain a unshielded collider trisection not in G which is a contradiction due to the fact that the two graphs have the same minimal inducing walks. Thus as ∈ Adj(lj−1 , G′ ). Suppose that as ̸∈ Adj(fj+1 , G′ ) and let γl be a shortest anterior walk from lj to ar in G′ . By Lemma F.9, γl′ is chordless. In this case, the walk ω ′ (fj+1 , lj ) + γl′ (lj , ar ) + (e′ (ar , as )) in G′ must contain an unshielded collider trisection not in G which is a contradiction. Thus as ∈ Adj(fj+1 , G′ ). Suppose that ar ̸= fj . In this case, The walk γf′ (fj , as ) must be semi-directed since otherwise σj would be anterior to σj−1 . This implies that the walk γf′ (fj , as ) must contain an unshielded collider trisection not in G. This is a contradiction. Thus ar = fj . Both e(lj−1 , as ) and e(fj+1 , as ) must be into as by Lemma F.8 due to the fact that lj−1 and fj+1 are on sections of discriminating inducing walk γd that discriminates σj . This implies that both e′ (lj−1 , as ) and e′ (fj+1 , as ) must be into as as G and G′ have the same minimal inducing walks and the walk (e(lj−1 , as ), e(fj+1 , as )) is a minimal inducing walk. Case 1: There is no h with 1 ≤ h < j such that lh ≺—≻ as in G′ or lh ̸∈ adj(as , G′ ). In this case, l1 —≻ b and the walk ω(v1 , l1 ) + (e(l1 , as ), e(as , fj+1 )) is an open walk given Cb which is a contradiction. Case 2: There is an h with 1 ≤ h < j such that lh ≺—≻ as in G′ or lh ̸∈ adj(as , G′ ). Choose h be as large as possible such that lh ≺—≻ as in G′ or lh ̸∈ adj(as , G′ ). Case 2.1: lh ≺—≻ as . In this case, the walk ω(v1 , lh ) + (e(lh , as ), e(as , fj+1 )) is an open walk given Cb which is a contradiction. Case 2.2: lh ̸∈ Adj(as , G′ ). In this case, the walk ω ′ (lh , fj ) + γd′ (fj , as ) is a minimal inducing walk. By assumption, this walk must be in G, however, this cannot be the case as as ∈ Ant(ar , G) which leads to a contradiction by Lemma F.10. In all cases, we have a contradiction and thus the lemma holds. L EMMA F.12. If two separable graphs G and G′ have the same adjacencies and same minimal inducing walks then they are equivalent. P ROOF. Let G and G′ be two separable graphs with the same adjacencies and same minimal inducing walks. let H = Anterialize(G) and H ′ = Anterialize(G′ ). By Theorem 5.3 we
58
have that G ≡ H and H is a separable anterial graph, and G′ ≡ H ′ and H ′ is a separable anterial graph. From Lemmas F.1, F.2, and F.6, we have that G and H have the same adjacencies and same minimal inducing walks and H ′ and G′ have the same adjacencies and same minimal inducing walks. Thus we also have that H and H ′ have the same adjacencies and same minimal inducing walks. The conclusion then follows from Lemma F.11 and the transitivity of equivalence. F.4. Minimal inducing walks and minimal discriminating inducing walks. We prove Proposition 7.3 and a lemma relating minimal inducing walks and minimal discriminating inducing walks. P ROPOSITION 7.3 If walk ω between a and b is a discriminating inducing walk that discriminates collider section σ in graph G and C separates a and b in G then every vertex on σ is in IV(a, b, C, G) and every other vertex on ω is not in IV(a, b, C, G). P ROOF. Let ω with ver(ω) = (v1 , . . . , vn ) be a discriminating inducing walk in that discriminates collider section σ on ω and let v1 ⊥ ⊥G vn | C . Neither v1 nor vn is in IV(v1 , vn , C, G). Next consider a vertex vk not on σ with 1 < k < n and i ̸= j . From the definition of discriminating inducing walk, vk ∈ Ant({ v1 , vn }, G). From ordered upward separation stability (Lemma E.6), we have that v1 ⊥ ⊥G vn | Cvk which implies that vk ̸∈ IV(v1 , vn , C, G). Finally consider a vertex vl on σj . In this case, ω is open given Cvl as every collider section is either anterior to an endpoint or a vertex in Cvl . This implies that vl ∈ IV(v1 , vn , C, G). The next lemma relates minimal inducing walks and minimal discriminating inducing walks in separable graphs with the same adjacencies. L EMMA F.13. Two separable graphs with the same adjacencies have the same minimal inducing walks if and only if they have the same minimal discriminating inducing walks. P ROOF. Let G and G′ be two separable graphs that have the same adjacencies. The forward direction follows from the fact that every minimal discriminating inducing walk is a minimal inducing walk. Next we consider the backward direction. Assume the lemma does not hold in the backward direction and let G and G′ be two graph with the same adjacencies and the same minimal discriminating inducing walks but different minimal inducing walks. Without loss of generality, assume there is a minimal inducing walk ω with ver(ω) = (v1 , . . . , vn ) in G such that there is no ω ′ with ver(ω ′ ) = (v1 , . . . , vn ) that is a minimal inducing walk in G′ . Consider the minimal inducing walk decomposition decompiw (ω, G) = { γ1 , . . . , γd } that contains a set of minimal discriminating inducing walks. There must be minimal discriminating induc′ ′ ′ ing walks γi′ in G′ . Next consider the walk ω ′ = decomp−1 iw ({ γ1 , . . . , γd }, G ) created by ′ combining these minimal discriminating inducing walks. ω must be an inducing walk. If ω ′ is a minimal inducing walk then we have a contradiction. If ω ′ is not a minimal inducing ′ in G′ that uses a subset of walk then there must be a shorter minimal inducing walk ωm ′ , G′ ) = { β ′ , . . . , β ′ }. It must be vertices on ω ′ . Consider the decomposition decompiw (ωm e 1 the case that there are minimal discriminating inducing walks βi in G. Consider the walk ωm = decomp−1 iw ({ β1 , . . . , βe }, G). It must be an inducing walk between v1 and vn that uses a subset of the vertices of ω and thus ω is not a minimal inducing walk. This is a contradiction. Thus the backward direction must hold. Both the forward and backward directions hold so the lemma must be true.
SEPARABLE GRAPHICAL MODELS
59
F.5. Characterization theorems. L EMMA F.14. The following statements are equivalent for two separable graphs G and H: (1) G and H are separation equivalent, (2) G and H have the same vertex separability and same induced arrowheads, (3) G and H have the same adjacencies and same minimal inducing walks, and (4) G and H have the same adjacencies and same minimal discriminating inducing walks. P ROOF. The implication (1) =⇒ (2) follows from Lemma F.1. The implication (1) and (2) =⇒ (3) follows from Lemmas F.2 and F.6. The implication (3) =⇒ (1) follows from Lemma F.12. Finally the bi-implication (3) ⇐⇒ (4) follows from Lemma F.13. Thus the lemma is true. T HEOREM 7.1 Two separable graphs are equivalent if and only if they have the same adjacencies and same minimal inducing walks. P ROOF. Follows from Lemma F.14. T HEOREM 7.2 Two separable graphs are equivalent if and only if they have the same adjacencies and the same minimal discriminating inducing walks. P ROOF. Follows from Lemma F.14. T HEOREM 8.2 Two separable graphs are equivalent if and only if they have the same vertex separability and same induced arrowheads. P ROOF. Follows from Lemma F.14. APPENDIX G: PROOFS RELATED REPRESENTING EQUIVALENCE CLASSES OF SEPARABLE GRAPHS In this section we show that the InducedArrowheads function is a canonical projection for separable graphs with respect to separation equivalence and that InducedArrowheads preserves separation equivalence when applied to separable graphs. L EMMA G.1.
The graphs G and InducedArrowheads(G) have the same adjacencies.
P ROOF. The InducedArrowheads algorithm applied to G adds an edge if and only if there is an edge in G and thus the graphs have the same adjacencies. By removing arrowhead at i on the edge e(i, j) we mean turning j ≺—≻ i into j ≺— i or turning j —≻ i into j — i. Removing arrowhead at i and j turns j ≺—≻ i into j — i. This process of removing arrowheads is how the InducedArrowheads algorithm transforms G into InducedArrowheads(G). L EMMA G.2. All internal arrowheads on a minimal inducing walk in a separable graph are induced arrowheads.
60
P ROOF. Consider a minimal inducing walk γ in a separable graph G. We show that all internal arrowheads on γ are induced. Choose an arbitrary internal arrowhead at b on e(b, d) on γ . Denote the section containing b by σ . By Lemma D.6, there is an discriminating inducing walk π that discriminates σ . Denote the endpoints of π by i and j . Because π is a discriminating inducing walk, i ̸∈ Adj(j, G). From Theorem 3.2, we have that i ⊥ ⊥G j | C where C = Ant({ i, j }, G) \ { i, j }. In addition, again due to the fact that π is a discriminat∖ ing inducing walk, i ⊥ ⊥ G j | Cb. These imply that b ∈ IV(i, j, C, G). Since d ∈ C, we also have d ̸∈ IV (i, j, C, G), which then implies that the arrowhead at b on e(b, d) is an induced arrowhead. L EMMA G.3. Assume G is a separable graph. Then a minimal inducing walk in G is an inducing walk in InducedArrowheads(G). P ROOF. Consider a minimal inducing walk γ in separable graph G. From Lemma G.1 there is a walk γ ′ in InducedArrowheads(G) with the same vertex sequence as γ . Again from Lemma G.1, the endpoints of γ ′ are not adjacent. This fact, Lemma G.2, and the fact that the InducedArrowheads algorithm only remove arrowheads that are not induced arrowheads imply that γ ′ is an inducing walk. L EMMA G.4. If G is separable and γ ′ is a minimal inducing walk in the graph InducedArrowheads(G) then there exists a walk γ in G such that γ ′ ≡ γ . P ROOF. Denote the endpoints of γ ′ by i and j . By Lemma G.1 we have that there is walk γ in G with ver(γ) = ver(γ ′ ). If we show that all internal arrowheads on γ are induced arrowheads in G then we are done since InducedArrowheads(G) only removes arrowheads from G. Suppose, for contradiction, that an internal arrowhead on γ at vertex b on e(d, b) is not induced. We note that on γ ′ , the edge e(d, b) is undirected since γ ′ is an inducing walk. Without loss of generality, we assume b is the closest vertex with a removed arrowhead to the endpoint of its section on its side on γ ′ , i.e. b is such that on the subsection between b and an endpoint of the section that do not contain d, the is no arrowhead removed. Consider the endpoint of this section that is close to b by b′ , and denote the vertex on γ ′ outside this section that is adjacent to b′ by d′ . If b = b′ , we choose d′ to be the other adjacent vertex of b than d. Notice that there exists at least a C such that i ⊥ ⊥G j | C because i and j are not adjacent and G is separable. Since the arrowhead at b is not induced, by the contrapositive of the definition of induced arrowheads, we have that, for every i, j, C , such that i ⊥ ⊥G j | C , either ∖ ∖ (i) i ⊥ ⊥G j | Cb or (ii) i ⊥ ⊥ G j | Cb and i ⊥ ⊥ G j | Cd. We show that the arrowhead at b′ on e(b′ , d′ ) is not induced: Since b and b′ are in the same section we have that i ⊥ ⊥G j | Cb ⇐⇒ i ⊥ ⊥G j | Cb′ . This implies that if case (i) holds for ′ b, the analogous of case (i) holds for b . In addition, if case (ii) holds for b then it holds that ∖ i⊥ ⊥ G j | Cb′ . ∖ What is left to show is if case (ii) holds for d then i ⊥ ⊥ G j | Cd′ : Since G is separable, by ′ Lemma G.2, there is an edge between d and d . This edge cannot have an arrowhead at d since otherwise γ ′ is not the shortest self-inducing walk between u and v . Therefore, regardless of whether there is an arrowhead at d′ on e(d, d′ ), if there is a connecting walk between i and j given Cd, there is a connecting walk between i and j given Cd′ . This completes the proof of the arrowhead at b′ on e(b′ , d′ ) is not induced, and consequently, there is no arrowhead at b′ on this edge in InducedArrowheads(G). This is a contradiction since b′ is an endpoint of a section on γ ′ . Therefore, all internal arrowheads on γ are induced.
SEPARABLE GRAPHICAL MODELS
61
L EMMA G.5. Assume G is a separable graph. A minimal inducing walk in G is a minimal inducing walk in InducedArrowheads(G) and vice versa. P ROOF. Let γ be a minimal inducing walk in G. Lemma G.3 shows there is an inducing walk γ ′ ≡ γ in InducedArrowheads(G). Suppose γ ′ is not minimal. This implies that there is another walk ω that is minimal in InducedArrowheads(G). From Lemma G.4, there is an inducing walk in G that uses a subset of the vertices in γ . This contradicts γ being minimal. Thus γ ′ must be minimal inducing walk in InducedArrowheads(G). The other direction is proven with a similar argument.
L EMMA G.6.
If G is separable then InducedArrowheads(G) is separable.
P ROOF. By Theorem 3.3, G does not contain a self-inducing walk, and we need to show that InducedArrowheads(G) does not contain a self-inducing walk. Suppose, for contradiction, that there is a self-inducing walk γ ′ in InducedArrowheads(G). Assume, without loss of generality, that γ ′ is the shortest such walk, and denote the endpoints of γ ′ by u and v . This implies that γ ′ is a minimal inducing walk. We note, by Lemma G.1, that G and InducedArrowheads(G) have the same adjacencies. Hence, each walk ν ′ in InducedArrowheads(G) has a corresponding walk with the same vertices and edges, denoted by ν , in G on which some arrowheads are potentially removed on ν ′ . Also, each internal vertex of γ ′ is an anterior to one of its endpoints. For each vertex w on γ ′ , consider the anterial walk from w to an endpoint of γ ′ , denoted by νw′ , such that νw′ has the fewest number of arrowheads removed among such anterior walks. Consider the subgraph of InducedArrowheads(G) consisting of the vertices of γ ′ and the vertices of all the walks νw′ for every internal vertex w of γ ′ . Call this subgraph K ′ . Below we show that in the induced subgraph K of G with respect to the vertices of K ′ , there exists an arrowhead at b on e(b, d) in K that does not exist in K ′ , but is induced. This leads to a contradiction with the arrowhead not existing in K ′ . Again, we note, by Lemma G.1, that K and K ′ have the same adjacencies, and any arrowhead in InducedArrowheads(G) exists in G. Since γ ′ is a minimal inducing walk, by Lemma G.5, there exists a walk γ in G with the same vetices that is a minimal inducing walk. Since all arrowheads on γ are induced in G, as proven in Lemma G.2, the arrowhead at b must be on an edge in K ′ that is not on γ . If vertices at which the arrowhead is removed are in PropAnt({ u, v }, G) then γ is selfinducing in G, which is not possible. Hence, choose e(b, d) such that the arrowhead at b is removed and b ∈ / PropAnt({ u, v }, G). Consider a vertex i in γ that is an anterior of b in the anterior walk from i to {u, v} in InducedArrowheads(G) (i can be b itself). Denote the section of i on γ by ρ. Let C = PropAnt({u, v}, G) ∪ ver(γ) \ ρ, i.e, be all proper anteriors of u and v and vertices of γ except the vertices in the section that is an anterior of b. First, u ⊥ ⊥G v | C since otherwise i ∈ PropAnt({u, v}, G), which implies that b ∈ PropAnt({u, v}, G). ∖ Secondly, let b be the closest vertex to i. Clearly, u ⊥ ⊥ G v | Cb. Thirdly, let b be the closest vertex to u. The only option where d can be on a connecting walk between u and v given Cd is via the anterior walk from d to u. However d is on a noncollider section in this walk and cannot make a connecting walk. Therefore, u ⊥ ⊥G v | Cd. These imply that the arrowhead at b is indeed induced, which is a contradiction. T HEOREM 9.1 If G is separable then G and InducedArrowheads(G) are equivalent.
62
P ROOF. Since, by Lemma G.6, G and InducedArrowheads(G) are separable, by Theorem 7.1, it is enough to show that G and InducedArrowheads(G) have the same adjacencies and minimal inducing walks. The former is Lemma G.1 and the latter is Lemma G.5.
T HEOREM 9.2 The InducedArrowheads algorithm is a canonical projection for separable graphs with respect to separation equivalence. P ROOF. If two graphs G and G′ are separation equivalent and separable then they must have the same adjacencies and induced arrowheads by Theorem 8.2. This implies that InducedArrowheads(G) = InducedArrowheads(G′ ). If G′ ̸≡ G then, again by Theorem 8.2, they must have different adjacencies or induced arrowheads with implies that InducedArrowheads(G) ̸≡ InducedArrowheads(G′ ). This proves that InducedArrowheads is a canonical representation function for separable graphs. Then, by Lemma G.6 and Theorem 9.1, it follows that InducedArrowheads also a canonical projection function. C OROLLARY 9.3 If G is a separable graph then Largest(G) contains a unique graph which is the graph InducedArrowheads(G). P ROOF. Let G be a separable graph. Every graph in Largest(G) is separable and equivalent to G. Let H, H ′ ∈ Largest(G). By Theorem 8.2, H and H ′ have the same adjacencies and same induced arrowheads. Consider the graph InducedArrowheadsG. It has the same adjacencies and induced arrowheads. Furthermore, all of its arrowheads are induced arrowheads so it must be in Largest(G). If any of the edges in H or H ′ have an arrowhead that is not in InducedArrowheadsG then it is not in Largest(G) thus H = H ′ = InducedArrowheadsG. C OROLLARY 9.4 If G is a separable graph then InducedArrowheads(G) is an anterial graph. P ROOF. Let G be a separable graph. From Lemma G.6, G′ = InducedArrowheads(G) is separable and from Theorem 9.1, G ≡ G′ . From Theorem 5.3, G′′ = Anterialize(G′ ) is an anterial graph equivalent to G′ . Thus we also have, G′′ ≡ G. From the fact that the Anterialize algorithm only removes arrowheads and the fact that these graphs are equivalent it must be the case that G′ = G′′ and thus G′ is an anterial graph. APPENDIX H: PROOFS RELATED TO THE IDENTIFICATION OF ESSENTIALLY SEPARABLE GRAPHS P ROPOSITION 10.1 (Minimal separator implies anterior separator). If C is a minimal separating set for a pair of vertices then C is an anterior separating set for the pair of vertices. P ROOF. From Lemma E.7, if C is a minimal separating set for i and j in graph G then C ⊆ Ant({ i, j }, G). Thus any minimal separating set is an anterior separating set. L EMMA H.1. If an edge e(d, b) has an induced arrowhead at b in graph G then there exist vertices i and j and vertex set C such that b ∈ IV(i, j, C, G) and d ∈ Ant({ i, j }, G).
SEPARABLE GRAPHICAL MODELS
63
P ROOF. let e(d, b) have an induced arrowhead at b in a graph G. From the definition of induced arrowheads, there is some pair of vertices p and q and vertex set D such that b ∈ IV(p, q, D, G) and d ̸∈ IV(p, q, D, G). From b ∈ IV(p, q, D, G), we have that p ⊥ ⊥G q | D ∖ and p ⊥ ⊥ G q | Db. Case 1: d ∈ Ant({ p, q }, G) \ { p, q }. In this case, the lemma holds for vertices i = p and j = q and vertex set C = D and note that using this assignment we have b ∈ IV(i, j, C, G) and d ∈ Ant({ i, j }, G). Thus the lemma holds in this case. Case 2: d ̸∈ Ant({ p, q }, G) \ { p, q }. From d ̸∈ IV(p, q, D, G), it must be the case that p⊥ ⊥G q | Dd. From p ⊥ ⊥G q | D and p ⊥ ⊥G q | Dd, and weak transitivity, it must be the case that p ⊥ ⊥G d | D or d ⊥ ⊥G q | D . Without loss of generality, assume that d ⊥ ⊥G q | D . From p⊥ ⊥G q | D , d ⊥ ⊥G q | D , and composition we have dp ⊥ ⊥G q | D and, by weak union we have ∖ d⊥ ⊥G q | Dp. From p ⊥ ⊥G q | D and p ⊥ ⊥ G q | Db and Lemma E.4, there is a walk γq between b and q open given Dp and weakly into b. In this case, the walk (e(d, b)) + γq is open given ∖ ∖ Dpb which implies that d ⊥ ⊥ G q | Dpb. Thus we have shown d ⊥ ⊥G q | Dp and d ⊥ ⊥ G q | Dpb which implies that b ∈ IV (d, q, Dp, G). In this case, let i = d, j = q and C = Dp and note that using this assignment we have b ∈ IV(i, j, C, G) and d ∈ Ant({ i = d, j }, G). Thus the lemma holds in this case. H.1. Proof of anterior induced adjacency proposition. Next we prove Proposition 10.2 P ROPOSITION 10.2 If a and b are separable in graph G then a ⊥ ⊥G b | C where C = aiAdj(a, b, G). P ROOF. Assume that that claim is not true and that there are separable vertices a and b in ∖ graph G such that a ⊥ ⊥ G b | C where C = iAdj(a, b, G) ∩ Ant(ab, G) = aiAdj(a, b, G). This implies that there is a connecting walk ω with ver(ω) = (v1 , . . . , vn ) with v1 = a and vn = b that is open given C . We consider three possible types of walks for ω . Case 1: ω consist of a single edge e(a, b). In this case, by Lemma C.1, a and b are not separable. This is a contradiction with the assumption that a and b are separable. Case 2: ω is a collider walk. In this case, every collider section on ω must be anterior to the endpoints and thus is a self-inducing walk. This implies, by Theorem C.2, that a and b are not separable. This is again a contradiction. Case 3: ω is not a collider walk. In this case there is some non-trivial maximal trek. let ω(vi−1 , vj+1 ) with i ≤ j be the maximal trek closest to a = v1 on ω . By Lemma C.4, we have that vi ∈ Ant(abC, G). Furthermore, from C = aiAdj(a, b, G) ⊆ Ant({ a, b }, G) we have vi ∈ Ant({ a, b }, G). Next, consider the subwalk ω(a, vi ). The subwalk is a collider walk. From the fact that ω is a connecting walk given C , every collider section on the subwalk contains a vertex of C . From C = aiAdj(a, b, G) ⊆ Ant({ a, b }, G), every collider section is anterior to { a, b } and thus vi ∈ iAdj(a, b, G). Thus vi ∈ C and ω is not a connecting walk as a non-collider section contains a vertex in C . This is a contradiction. In each case we have a contradiction so the claim must hold. H.2. Ordering and separation properties of anterial graphs. Anterial graphs play an essential role in proving the correctness of the SGI algorithm. In this section we show several ordering and separation properties of anterial graphs. Recall that ⪅G is the induced preorder of a graph G from which we define (1) a ≈G b if a ⪅G b and b ⪅G a, (2) a ∥G b if a ̸⪅G b and b ̸⪅G a, (3) a <G b if a ⪅G b and b ̸⪅G a. If a ∥G b we say that a and b are incomparable. If a <G b or b <G a then a and b are strictly ordered. Recall also, the equivalence relations a ∼G b defined to hold if there is an undirected
64
walk between a and b in G or a = b. Note that ≈G need not be equivalent to ∼G in general, but are equivalent if G is an anterial graph due to Lemma E.9. The next lemma shows that in an anterial graph every distinct pair of vertices is either connected by an undirected walk, strictly ordered, or incomparable. L EMMA H.2. If G is an anterial graph and a ̸= b then exactly one of the following properties holds a ∥G b, a <G b, b <G a, a ∼G b. P ROOF. Let G = (V, E) be an anterial graph and for a, b ∈ V it is the case that a ̸= b. Case 1: a ∥G b. In this case, by definition, we have that a ̸∼G b, a ̸<G b, and b ̸<G a and the property is exclusive. Case 2: a ∼G b. First, by definition, we have that a ⋎G b. Next, due the fact that a ∼G b and that G contains no semi-directed cycle, we must have a ̸<G b and b ̸<G a. In this case, the property is exclusive. Case 3: a <G b or b <G a. Without loss of generality, assume a <G b. In this case, by definition, we have that a ⋎G b. It cannot be the case that a ∼G b or b <G a otherwise, in either case, there would be a semi-directed cycle and G contains no semi-directed cycle. In this case, the property is exclusive. Thus exactly one of the following holds for any distinct pair of vertices a, b ∈ V , a ∥G b, a ∼G b, a <G b, and b <G a and thus the proposition holds. The next lemma, first proved in [20], shows that the relationships between adjacent vertices in an anterial graph uniquely determines the edge type between those vertices. L EMMA H.3.
If G is anterial and a ∈ Adj(b, G) then
(i) a ∼G b if and only if a — b, (ii) a ∥G b if and only if a ≺—≻ b, (iii) a <G b if and only if a —≻ b, and (iv) b <G a if and only if b —≻ a. P ROOF. Let G be an anterial graph such that a ∈ Adj(b, G). Case (i): For the forward direction, let a ∼G b. If a —≻ b, or a ≺— b then there would be a semi-directed walk which contradicts G being anterial. Similarly, if a ≺—≻ b, then there would be a bidirected edge with an endpoint anterior to its other endpoint which also contradicts G being anterial. Thus the edge must be oriented a — b. For the other direction, assume a — b. In this case, the walk containing this edge is an undirected walk between a and b and thus a ∼G b. Case (ii): For the forward direction, let a ∥G b. By Lemma H.2, we have that a and b are not ordered which rules out a —≻ b and a ≺— b. Again, by Lemma H.2, we have that a ̸∼G b which rules out a — b. This implies that a ≺—≻ b. For the other direction, let a ≺—≻ b. If either a <G b, b <G a or a ∼G b there would be a bidirected edge with an endpoint anterior to its other endpoint which contradicts G being anterial. Thus a ∥G b. Case (iii): For the forward direction, let a <G b. By Lemma H.2, we have that b ̸<G a and a ̸∼G b which rules out a ≺— b and a — b. If a ≺—≻ b then there would be a bidirected edge with an endpoint anterior to its other endpoint which cannot be the case due to G being anterial. This implies that a —≻ b For the other direction, let a —≻ b. This implies that a <G b . Case (iv): Similar to case (iii).
SEPARABLE GRAPHICAL MODELS
65
Let aAdj(b, G) be the set of anterior adjacent vertices defined to be the set of vertices c ∈ V such that either c —≻ b or c — b in graph G. L EMMA H.4. If G is an anterial graph containing separable vertices a and b such that a ∼G b then a ⊥ ⊥G b | aAdj(a, G). P ROOF. Let G be an anterial graph containing separable vertices a and b such that a ∼G b. ∖ Suppose that the claim does not hold and that a ⊥ ⊥ G b | C where C = aAdj(a, G). This implies that there is a walk ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) where v1 = a and vn = b that is connecting given C . Note that v2 ̸= b, otherwise a and b are not separable. From Lemma H.2, it must be the case that a ̸<G b, b ̸<G a, and a ⋎G b. Case 1: a —≻ v2 or a ≺—≻ v2 . From anterial endmark property, Lemma D.17, we have that v2 ̸∈ Ant(a, G). As a ∼G b we also have v2 ̸∈ Ant(b, G). There must be some collider section σi for 1 < i < m as σ2 ̸∈ Ant(ab, G) and this section cannot contain a vertex in C . This implies that the walk ω is not a connecting walk given C . Case 2: a — v2 or a ≺— v2 . In either case, v2 is on a non-collider section of ω and v2 ∈ C . This implies that the walk ω is not a connecting walk given C . In either case, the walk ω is not a connecting walk given C so the claim holds. L EMMA H.5. If G is an anterial graph containing separable vertices a and b such that b <G a then a ⊥ ⊥G b | aAdj(a, G). P ROOF. Let G be an anterial graph containing separable vertices a and b such that b <G a. ∖ Suppose that the claim does not hold and that a ⊥ ⊥ G b | C where C = aAdj(a, G). This implies that there is a walk ω with ver(ω) = (v1 , . . . , vn ) and sec(ω) = (σ1 , . . . , σm ) where v1 = a and vn = b that is connecting given C . Note that v2 ̸= b, otherwise a and b are not separable. From Lemma H.2, it must be the case that a ̸<G b, a ̸∼G b, and a ⋎G b. We show a ⊥ ⊥G b | aAdj(a, G). Case 1: a —≻ v2 or a ≺—≻ v2 . From the anterial endmark property, Lemma D.17, we have that v2 ̸∈ Ant(a, G). As b <G a and G is anterial, we also have v2 ̸∈ Ant(b, G). There must be some collider section σi for 1 < i < m as σ2 ̸∈ Ant(ab, G) and this section cannot contain a vertex in C . This implies that the walk ω is not a connecting walk given C . Case 2: a — v2 or a ≺— v2 . In either case, v2 is on a non-collider section of ω and v2 ∈ C . This implies that the walk ω is not a connecting walk given C . In either case (1) or (2), the walk ω is not a connecting walk given C so the claim must hold. H.3. Proofs related to the SGI algorithm. L EMMA H.6. ble in G∗ .
If Gf inal = SGI(I(G∗ )) and a ̸∈ Adj(b, Gf inal ) then a and b are separa-
P ROOF. Let Gf inal = SGI(I(G∗ )) and G denote that current graph at various steps of running the SGI algorithm. Initially, G is the complete graph. An edge e(a, b) is removed only if a set C is found and a ⊥ ⊥I(P ∗ ) b | C . This implies that a and b are separable in G∗ . L EMMA H.7.
If Gf inal = SGI(I(G∗ )) then for all a ∈ V , Ant(a, Gf inal ) ⊇ Ant(a, G∗ ).
66
P ROOF. Let Gf inal = SGI(I(G∗ )) and G denote that current graph at various steps of running the SGI algorithm. Initially, G is the complete graph and Ant(i, G) = V \ i so the claim holds. The claim then follows from the soundness of the orientation rule used to add arrowheads to edges (Proposition 8.1). L EMMA H.8.
If Gf inal = SGI(I(G∗ )) then for all a ∈ V , aAdj(a, G∗ ) ⊆ aAdj(a, Gf inal ).
P ROOF. This follows from Lemmas H.6 and H.7. The following lemma shows that every vertex equivalence class of G∗ is a subset of some vertex equivalence class in Gf inal , the output of the SGI algorithm. L EMMA H.9. in Gf inal .
If a ≈G∗ b, and a ∈ Adj(b, Gf inal ) where Gf inal = SGI(I(G∗ )) then a — b
P ROOF. Assume a ≈G∗ b, Gf inal = SGI(I(G∗ )) and a ∈ Adj(b, Gf inal ). Suppose the claim is not true and that the edge e(a, b) in Gf inal has an arrowhead at a, b or both a and b. Without loss of generality, assume there is one at a. The edge must have an induced arrowhead at a in I(P ∗ ). This implies that there exists (i, j, C) such that a ∈ IV (i, j, C, G∗ ). This, however, cannot be the case due to Proposition 6.5. Thus the claim must be true. L EMMA H.10. If ω with ver(ω) = (v1 , . . . , vn ) is a discriminating inducing walk that discriminates collider section σ = (vi , vj ) in G∗ then if SGI removed the edge e(v1 , vn ) then the edge e(vi−1 , vi ) has an arrowhead at vi in Gf inal and the edge e(vj , vj+1 ) has an arrowhead at vj in Gf inal . P ROOF. Let ω with ver(ω) = (v1 , . . . , vn ) be a discriminating inducing walk that discriminates collider section σ = (vi , vj ) in G∗ and assume that SGI removed the edge e(v1 , vn ). The fact that the edge e(v1 , vn ) was removed implies that there is a set C that separates v1 and vn in G∗ that was used by the algorithm to remove the edge. From Proposition 7.3, every vertex on a discriminated section of a discriminating inducing walk is an inducing vertex for the endpoints of the discriminating inducing walk (i.e., in IV(v1 , vn , C, G∗ )) and that every other vertex on ω is not an inducing vertex (i.e., not in IV(v1 , vn , C, G∗ )). This implies that the edge closed to σ on the walk between a and σ has an induced arrowhead at first(σ). This implies that the SGI algorithm will add these arrowheads after removing the edge e(v1 , vn ). The next lemma captures a key algorithmic invariant about the SGI algorithm. In particular, the invariant captures the fact that the current graph G in SGI before and after considering candidate separating sets is an anterial graph. L EMMA H.11. For graph G∗ , before and after considering a candidate separating set, the current graph G of the SGI algorithm applies to G∗ (i.e. a trace of SGI(G∗ )) is an anterial graph. P ROOF. We show this algorithmic invariant inductively on the length of the trace of SGI(G∗ ). For the base case we consider the initial graph. This initial graph is a simple complete undirected graph and thus satisfies the anterial endmark property. By Lemma D.17 the graph is anterial.
SEPARABLE GRAPHICAL MODELS
67
For the inductive case we assume that the current graph is anterial and show that after identifying a separating set C for i and j , removing the edge between i and j and orienting, the resulting graph is again anterial. First note that the resulting graph is simple. Consider the set IV = IV(i, j, C, G∗ ) and D = V \ IV. Any new endmark is at an endpoint of an edge e(c, d) with c ∈ D and d ∈ IV with the new arrowhead at d. The resulting graph satisfies the anterial endmark property as (1) for new endmarks (necessarily arrowheads), every edge between a vertex in D and a vertex in IV has an arrowhead endmark at the vertex in IV and thus there can be no anterior walk violating the anterial endmark property, (2) for old endmarks, the addition of an arrowhead does not create any new anterial walks. Thus, by Lemma D.17 the graph is anterial. The anterior sets of a graph G = (V, E) is the set A(G) = { A ∈ 2V | A = Ant(A, G) }.
Let anterial graph G have anterior sets A(G) = { A1 , . . . , Aa }. The pair (A(G), ⊆) defines a bounded partially ordered set closed under union, that is, a join-semilattice with bottom. The bottom is the empty set ∅ and the top if the set V . The graph G defined to be a —≻ b —≻ c has A(G) = { ∅, { a }, { a, b }, { a, b, c } } which illustrates that A(G) is not necessarily closed under intersection. The following proof uses well-founded induction. An alternative approach is to prove by induction on the number of chain components in the equivalent anterial graph — one must exist by Theorem 5.3. This approach, however, requires defining chain components and yields a proof that is similar to the proof below. L EMMA H.12. If G∗ is essentially separable, a and b are separable in G∗ then a ̸∈ Adj(b, Gf inal ) where Gf inal = SGI(I(G∗ )). P ROOF. Let G∗ be an essentially separable graph, Gf inal = SGI(I(P ∗ )). let G be a separable anterial graph such that G ≡ G∗ ; one exists due to the fact that G∗ has an equivalent separable graph and Theorem 5.3. First we recast the lemma in terms of separation completeness. A graph Gf inal is separation complete with respect to graph G and vertex set A ⊆ V if for all pairs of distinct vertices a, b ∈ A, if a ̸∈ Adj(b, G) then a ̸∈ Adj(b, Gf inal ). Thus the lemma holds if we can show that Gf inal is separation complete with respect to G and V . Next, note that (A(G), ⊆) is well-founded as A(G) is a finite set and ⊆ is a partial order over A(G). We prove the claim by well-founded induction on A(G) with respect to ⊂. In particular, we prove that Gf inal is separation complete with respect to G and Aj under the induction hypothesis that Gf inal is separation complete with respect to G and all Ai ⊂ Aj . Define max(A) = { a ∈ A | ∀b ∈ A, b ⪅G a }. Let Ai = Aj \ max(Aj ). The set Ai is an ancestral set, that is, Ai ∈ A(G). By induction assumption, all edges between separable vertices in Ai have been removed. Thus we need only consider pairs of vertices a, b ∈ Aj that are separable in G and such that at least one of the vertices is in the set max(Aj ). Without loss of generality, assume a ∈ max(Aj ). Case 1: a ≈G b. In this case, from Lemmas H.8 and H.5 we know that aAdj(a, Gf inal ) and aAdj(b, Gf inal ) separate a and b and at least one of them must be smaller then SepSetBound(Gf inal ). Case 2: a <G b or b <G a. Without loss of generality, assume b <G a. In this case, from Lemmas H.8 and H.4 we know that aAdj(a, Gf inal ) separates a and b and that the set is smaller then SepSetBound(Gf inal ).
68 G Case 3: a ∥G b. Let Ab = Aj \ [a]G ≈ and Aa = Aj \ [b]≈ . In this case we have that b ∈ Ab , a ∈ Aa , Aa ⊂ Aj , Ab ⊂ Aj , Aa ∈ A(G), and Ab ∈ A(G). From Proposition 10.2, we know that a ⊥ ⊥G b | C when C = aiAdj(a, b, G) and when C = aiAdj(b, a, G). Without loss of generality, we show that aiAdj(a, b, Gf inal ) ⊇ aiAdj(a, b, G). Suppose that this is not the case and there is a vertex d ∈ aiAdj(a, b, G)\ aiAdj(a, b, Gf inal ). Case 3.1: d = b. This cannot be the case as there would be a self-inducing walk between a and b and a and b would not be separable. Case 3.2: d ∈ aAdj(a, G). In this case, by Lemma H.8, we have that aAdj(a, Gf inal ) ⊆ aAdj(a, G) so this cannot be the case. Case 3.3: d ∈ aiAdj(a, b, G) \ aAdj(a, G). In this case, there must be an inducing walk between a and d that is open given b in G. Let ω be a minimal inducing walk between a and d in G that is open given b. There is a walk ω ′ in Gf inal with the same vertex sequence. We show that ω ′ is an inducing walk open given b in Gf inal . From Lemma H.9, we know that every collider section on ω corresponds to an undirected walk on ω ′ . From Lemma C.4, every vertex is anterior to either a or b and thus every vertex on ω is in Aj as, From Lemma D.6, every collider section on ω is discriminated by some discriminating inducing walk that is a subwalk of ω . Consider a discriminating inducing walk between vi and vk on ω that discriminates a section σ and let Aik = Ant({ vi , vk }, G). Clearly the set is an anterior set in G (i.e., Aik ∈ A(G)). We know that σ ∩ Aik = ∅. This implies that Aik ⊆ Aj . From the induction hypothesis, the edge between vi and vj has been removed. By Lemma H.10, The arrowheads into σ on ω are oriented in ω ′ . This implies that ω ′ is an inducing walk in Gf inal . Finally, by Lemma H.7, d ∈ aiAdj(a, b, Gf inal ). This implies that aiAdj(a, b, Gf inal ) ⊆ aiAdj(a, b, G). From this it must be the case that the edge between a and b must be removed in Gf inal as there is a subset of aiAdj(a, b, G) which will be found as socs ≥ SepSetBound(Gf inal ) > |aiAdj(a, b, G)|.
T HEOREM 10.4 If G∗ is essentially separable then SGI(I(G∗ )) ≡ G∗ and if G ≡ G∗ is separable then SGI(I(G∗ )) = InducedArrowheads(G). P ROOF. Assume G∗ is an essentially separable graph. Let G∗sep ≡ G∗ be a separable graph equivalent to G∗ , GSGI = SGI(I(G∗ )) and GIN D = InducedArrowheads(G∗sep ). We show SGI(I(G∗ )) = InducedArrowheads(G∗sep ), that is, GSGI = GIN D . First we show that GSGI and GIN D have the same adjacencies. From Lemma H.6 we have ADJ(GSGI ) ⊇ ADJ(G∗sep ) and from Lemma H.12 we have ADJ(GSGI ) ⊆ ADJ(G∗sep ). Thus GSGI and G∗sep have the same adjacencies. Next, GIN D and G∗sep have the same adjacencies and minimal inducing walks by Theorems 9.2 and 7.1. Combining these facts we have that GSGI and GIN D have the same adjacencies. Second, we show that GSGI and GIN D have the same arrowheads. We identify the arrowheads in GIN D with induced arrowheads in G∗sep . By construction, GIN D has an arrowhead at b on edge e(d, b) if and only if e(d, b) has an induced arrowhead at b in G∗sep . Next we identify the arrowheads in GSGI with induced arrowheads in G∗sep . Every arrowhead in GSGI is to due to an induced arrowhead in I(G∗ ), or equivalently, I(G∗sep ). Next we show that if edge e(d, b) has in induced arrowhead at b in G∗sep then there
SEPARABLE GRAPHICAL MODELS
69
is an edge with e′ (d, b) in GSGI with an arrowhead at b. From the argument above, there must be an edge e′ (d, b) in GSGI . From Lemma H.1, there exist vertices i and j and vertex set D such that b ∈ IV(i, j, D, G∗sep ) and d ∈ Ant({ i, j }, G). At some stage, the SGI algorithm will identify a minimal separating set C for i and j . After identifying the set C that separates i and j the algorithm will add the arrowhead at b on edge e′ (d, b) due to the fact that it will, determine that d ̸∈ IV(i, j, GSGI ) by testing i ⊥ ⊥G∗ j | Cd which must hold by Lemma E.6. This implies that in GSGI there is an arrowhead at b on edge e(d, b) if and only if e(d, b) has an induced arrowhead at b in G∗sep . This implies that GSGI and GIN D have the same arrowheads. From the fact that GSGI and GIN D are simple graphs, have the same adjacencies and same arrowheads we have that GSGI = GIN D . C OROLLARY 10.5 If G∗ is essentially separable and P ∗ provides perfect testing for G∗ with respect to SGI then the SGI algorithm identifies the equivalence class of G∗ . P ROOF. Assume G∗ ∈ E(Gsep ) is an essentially separable graph and that I(P ∗ ) provides perfect testing with respect to G∗ . Let G∗sep ≡ G∗ be a separable graph equivalent to G∗ , GSGI = SGI(I(P ∗ )) and GIN D = InducedArrowheads(G∗sep ). From perfect testing, we have SGI(I(P ∗ )) = SGI(I(G∗sep )). From Theorem 10.4, we have SGI(I(P ∗ )) = InducedArrowheads(G∗sep ). From Theorem 9.2, for all separable graphs G, G′ it is the case that SGI(I(G)) = SGI(I(G′ )) if and only if G ≡ G′ . Thus if G∗ ∈ E(Gsep ) then SGI identifies the equivalence class [G∗ ]E(Gsep ) under perfect testing. T HEOREM 10.6 If G∗ is essentially separable and P ∗ provides perfect testing for G∗ then the SGI algorithm requires O(|V |SepSetBound(G)+1 ) independence tests where G = Largest(G∗ ) is the representation of the equivalence class of G∗ . P ROOF. Let G∗ be separable and P ∗ provide perfect testing for G∗ . Let Gf inal = SGI(I(P ∗ )) and note that G = Gf inal = InducedArrowheads(G∗ ) by Corollary 10.5. In this case, the algorithm terminates when socs ≥ SepSetBound(Gf inal ). This implies that we consider at most O(|V |SepSetBound(G) ) independence tests to guarantee that edges between separable pairs of vertices have been removed. In addition, the determination of the set of inducing vertices for a separated pair of vertices is bounded by O(|V |). Thus the total number of independence tests is bounded by O(|V |SepSetBound(G)+1 ).