# Local Structure Recovery of Chain Graphs after Marginalization

Authors: Qiang Zhao; Panpan Luo; Qing Xi
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

This paper discusses
local structure recovery of chain graphs (CGs) when there exist unobserved
or latent variables or after marginalization over observed variables.
Under a condition presented in this paper, it is explained which edges
and directions of edges in local structure can be recovered validly
and which cannot after marginalization.


---

## Body

## 1. Introduction

Graphical models, also known as Markov networks and Bayesian networks, including independence graphs, directed acyclic graphs (DAGs), and chain graphs (CGs) have been applied widely to many fields, such as stochastic systems, data mining, pattern recognition, artificial intelligence, and causal discovery. Chain graphs (CGs) are widely used to represent independence, conditional independence, and causal relationships among the random variables [1–5]. Structure recovery of CGs has been discussed by many authors [4–6]. A statistical conclusion may be reversed after marginalization over some variables, which is called Yule-Simpson paradox [7, 8]. For sampling design, prior knowledge or assumptions on models are necessary for valid structural learning of CGs and parameter estimates since some variables may be unobserved, such as the faithfulness assumption [4, 5] and collapsibility [9, 10]. On the other hand, for data analysis, conditions are necessary for marginalizing over some observed variables. Various conditions have been presented for avoiding a statistical conclusion reversion about association and parameters of linear models [10–14]. Collapsibility of parameter estimates for undirected graphical models over some variables has been discussed in [9, 15–17], and that of DAGs has been discussed in [18, 19].In this paper, we discuss local structure recovery for a CG when there exist unobserved or latent variables or after marginalization over observed variables. Suppose that there is an unknown true CG with a large number of variables but we may be interested in construction of a local structure of the CG from a marginal distribution of a subset of variables. We present a condition for this localized recovery and explain which edges and directions of edges in local structure can be recovered validly from the marginal distribution and which edges may be spurious. We say that an edge or a direction is recovered validly from the marginal distribution if it is the same as that recovered from the joint distribution. The condition is useful for both sampling design and data analysis. This localization of structure recovery is related to identification and collapsibility.Section2 gives notation and definitions. In Section 3, we present theoretical results on local structure recovery. Finally a discussion is given in Section 4.


## 2. Notation and Definitions

In this section, we briefly introduce terminologies and notations on graph theory. Readers can refer to [3, 20] for more details.LetGV=(V,EV) be a graph with a vertex set V and an edge set EV. We say that there is an undirected edge, or a line, between vertex v and vertex u (denoted as v-u), if v,u∈EV and u,v∈EV; and there is a direct edge, or an arrow, from vertex v to u (denoted as v→u), if v,u∈EV and u,v∉EV. Chain components of GV are obtained by removing all arrows in GV and taking the connectivity components of the remaining undirected graph. A chain graph with only undirected edges is known as an undirected graph (UG). A chain graph with only directed edges and without any directed cycles is known as a directed acyclic graph (DAG).Ifv→u, then we call v a parent of u and u a child of v. In general, we use paG(u) and chG(u) to represent the collection of parents and children of u, respectively. If v-u, then we call v a neighbour of u. We use neG(u) to represent the set of neighbours of vertex u in GV. If there is an edge between the vertices v and u, then we say that v and u are joined or adjacent. The family of u contains u and its parents, which is denoted as faG(u). For a set A⊆V, we can define similarly paG(A)=∪u∈Apa(u)∖A, chG(A)=∪u∈Ach(u)∖A, and faG(A)=A∪paG(A). The boundary of u is the set of neighbours and parents of u, which is denoted as bdG(u). What is more, the boundary of a set A⊆V is defined as bdG(A)=(paG(A)∪neG(A))∖A. In case that the underlying CG is clearly specified, the subscript G is often ignored to simplify the notations.If there is a sequence of the verticesu0,u1,…,uk-1,uk, k≥0, with ui-1,ui∈EV or ui,ui-1∈EV, for all 1≤i≤k, then we call it a route and u0 and uk the ends of the route. Furthermore if for all 1≤i≤k there is ui-1,ui∈EV, we say the route is descending and use v↦u to denote a descending route from vertex v to u. If the vertices in a route are all distinct from each other, then we call the route a path. If there is a descending path from vertex v to u, then we call v an ancestor of vertex u and u a descendant of vertex v, which are denoted as an(u) and de(v), respectively. Similarly, the ancestral set of a set B⊆V is defined as an(B)=∪u∈Ban(u)∖B, and the descendant set is defined as de(B)=∪u∈Bde(u)∖B. Furthermore, we define An(b)=an(b)∪{b}. A vertex v without any children in GV is called a terminal. Besides, if deG(A)=⌀, we call A a terminal set. We call a route a pseudocycle if it satisfies u0=uk. Besides, it is called a cycle if it also satisfies k≥3 and u0,u1,…,uk-1 are distinct vertices. A cycle or pseudocycle is directed if it is descending and has uj,uj-1∉EV for some jϵ{1,…,k-1,k}. Finally, if graph GV does not contain any directed cycles or directed pseudocycles, we will call it a CG (chain graph).A sectionσ of a route ρ=(u0,u1,…,uk-1,uk) in CGGV means any maximum undirected subroute σ in ρ, for example, uj-⋯-ui with 0≤j≤i≤k. We call uj and ui the two ends of the section. Besides, if there is uj-1→uj in ρ for some j>0 (or ui←ui+1 in ρ for some i<k), then we call uj (or ui) a head-terminal, or else we call it a tail-terminal. The head-to-head section in reference to route ρ is the section which has two head-terminals, and a non-head-to-head section if it has one head-terminal at most. We use {uj,…,ui} to denote the set of vertices of a section σ. If {uj,…,ui}∩S=⌀ with S⊆V, then we consider that section σ is outside of the set S. If {uj,…,ui}∩S≠⌀, then we consider that σ is hit by set S.Another important concept inCG is complex κ. A complex κ in CGGV is an especial path u0,u1,…,uk-1,uk, k≥2, with u0→u1, uj-uj+1(1≤j≤k-2), and uk-1←uk in GV, where there is no extra edge among vertices on the path. The vertices u0 and uk are called the parents of complex κ, denoted as par(κ), and {u1,u2,…,uk-2,uk-1} is called the region of κ. What is more, the complex with vertex x as one of its parents is denoted by κxϵpar(κ). At last, the Markov Blanket of vertex x is defined as MB(x)=x∪ch(x)∪ne(x)∪pa(x)∪par(κxϵpar(κ)).Next, we give the definition ofc-separation in CGGV. If a section σ1 of route ρ satisfies the following two presentations, (1) if σ1 is a head-to-head section in reference to ρ and σ1 is outside of set S, or (2) σ1 is not a head-to-head section in reference to ρ and σ1 is hit by set S, then we say that ρ is c-separated by the set S⊆V in GV. What is more, we say that the disjoint set A,B⊆V in GV is c-separated by the disjoint set S⊆V if every route ρ between A and B is c-separated by S, and A,B,S form a c-separation which is denoted by 〈A,B∣S〉GVsep.If twoCGs share the same c-separation patterns over the same set of vertices, then we say that they areMarkov equivalent. All chain graphs, which are Markov equivalent with each other, form equivalent class, which is known asMarkov equivalent class. It is well known that two CGs areMarkov equivalent if and only if they share the identical global skeleton and complexes [20].If a probability distributionP over X1,X2,…,Xn-1,Xn permits the following factorization [3], (1)Px=∏τϵT‍Pxτ∣xpa(τ),where T is the collection of chain components of CGGV and after given xpa(τ), the conditional probability distribution of xτ is denoted as P(xτ∣xpa(τ)); then we say that P is a compatible probability distribution in reference to GV. It is easy to check that if  P  is a compatible probability distribution in reference to CGGV, we have (2)A,B∣SGVsep⟹XA⫫XB∣XS,where XA⫫XB∣XS represents the conditional independence between XA and XB given XC in P. If the condition is strengthened to (3)A,B∣SGVsep⟺XA⫫XB∣XS,then we say that P is faithful to GV. Let M(GV) be the family of compatible probability distributions in reference to CGGV. A chain graph model is defined as T=(GV,P), where P is a family of probability distributions that are compatible with GV.Example 1.
Consider aCGGV=(V,EV) in Figure 1, where V={a,…,j} and EV={a,b,a,c,a,d,b,e,c,e,c,f,d,f,e,g,f,h, g,e,g,h,h,j,i,g,j,h}. We have pa(g)={i}, ch(g)={h}, ne(g)={e}, fa(g)={g,i}, bd(g)={i,e}, an(g)={a,b,c,e,i}, de(g)={h,j}, and MB(g)={e,i,h,f}. κ=(b,e,g,i) and κ′=(g,h,f) are complexes, where par(κ)={b,i} and par(κ′)={g,f}, respectively. The path l=(a,c,f,h) between a and h is c-separated by {c} or {f}, while the path l′=(a,b,e,g,i) between a and g is c-separated by the empty set. The sets A={a} and B={e,f,g,h,i,j} are c-separated by the set C={b,c,d}, and A,B,S form a c-separation 〈A,B∣S〉GVsep.Figure 1
A chain graphGV.


## 3. Local Structure Recovery after Marginalization

LetA, B, and C be a partition of all variables in V. In this section, we assume that A⫫B∣C and suppose that variables in B are omitted or unobservable. The assumption of conditional independence has been discussed as one of conditions for collapsibility of parameter estimates over unobserved variables [9–12, 14, 18, 19]. Collapsibility of parameter estimates further requires another condition that the separator C is a complete subgraph in the moral graph. A decomposition approach of structural learning proposed in [21] also requires the condition of a complete separator. In this section, we show under the assumption of conditional independence but without the condition of a complete separator that the local structure of CGGV over A∪C can be partially recovered from the marginal distribution of observed variables in A∪C. In many practical applications, the conditional independence A⫫B∣C can be judged with domain or prior knowledge, such as Markov chain, chain graphical models, and dynamic or temporal models [1]. When all variables in the full set V are observed, we can first construct an undirected independence graph G- over V from the observed data; then we find a set C which separates A and B in the undirected graph G-, and thus we have that A⫫B∣C holds [2, 3].TwoCGs have the same Markov property if and only if they have the same skeleton (i.e., an undirected version of GV) and the same complexes [20]. Thus for recovering the structure of a CG, we can only learn the skeleton and complexes from a distribution of observed variables. A marginal distribution obtained from the distribution P with the Markov property of GV may not obey the Markov property of any CG. Although the class of CGs is not closed under marginalization in this sense, we show that local structure of a CG may be partially recovered under some conditions. First we discuss which edges of local structure over A∪C can be recovered validly and which cannot from a marginal distribution of A∪C.Theorem 2.
Two vertices inA are c-separated by a subset of V if and only if they are c-separated by a subset of A∪C.Proof.
The sufficiency is obvious sinceV⊇A∪C. For the necessity, let a and a′ be two vertices in A that are c-separated by S(⊆V). Thus there is no edge connecting a and a′ in CGGV. Since a and a′ are contained in A, bd(a) and bd(a′) are contained in A∪C, otherwise A⫫B∣C. Without loss of generality, suppose that a is not an ancestor of a′. Thus we have that bd(a)(⊆A∪C)c-separates a and a′.From Theorem2, we can see that the existence of edges falling into A can be determined validly from the marginal distribution of A∪C.Theorem 3.
Leta and c be two vertices in A and C, respectively. Then a and c are c-separated by a subset of  V if and only if they are c-separated by a subset of A∪C.Proof.
The sufficiency is trivial. For the necessity, we show below thatS=[(An(a)∪An(c))∩(A∪C)]∖{a,c} can c-separate every route connecting a and c. We consider the following two cases separately:(1)
a route is contained inAn(a)∪An(c),(2)
a route is not completely contained inAn(a)∪An(c).
We first discuss case (1). Letρ=(a,u,v,…)⊆An(a)∪An(c). Note that u must not be the vertex c since there is no edge between a and c, but v may be c. Further we consider two subcases:(1.1)
u is not contained in any head-to-head section,(1.2)
u is contained in some head-to-head section.
For subcase (1.1), we haveu∈A∪C for a∈A and thus u∈S for ρ⊆An(a)∪An(c). So the path ρ is c-separated by node u.
For subcase (1.2), let us suppose the head-to-head section on routeρ is a→u-v-⋯-b1←b, where b is the other parent of this head-to-head section. Since ρ is contained in An(a)∪An(c), then b1∈An(a)∪An(c); thus we have the fact that the node b must not be c. Otherwise, b1∈ch(c) and b1∈de(a), which is contradictory to b1∈An(a)∪An(c). Because A⫫B∣C and a∈A, we have that b∉B. Thus b∈A∪C and then b∈S=[(An(a)∪An(c))∩(A∪C)]∖{a,c}. Thus we have that the route ρ is c-separated by node b.
Now we consider case (2) and show first that such a route contains a head-to-head section. Letρ=(a,…,m,u,…,v,n,…,c) such that m and n are contained in An(a)∪An(c) but no vertices from u to v are contained in An(a)∪An(c) since ρ is not completely contained in An(a)∪An(c). We know that the arrows must be oriented as m→u and n→v since m,n∈An(a)∪An(c) and u,v∉An(a)∪An(c). Then there must be a head-to-head section between m and n on ρ, and none of its descendants is in An(a)∪An(c). Thus vertices on the region of this head-to-head section and its descendants are not in S=[(An(a)∪An(c))∩(A∪C)]∖{a,c}, and we obtain that ρ is c-separated by S. We proved this theorem.According to Theorem3, the existence of edges crossing A and C can also be determined validly from the marginal distribution of A∪C.Example
1 (continued). Consider again the CG in Figure 1. Let A={e,f,g,h,i,j}, B={a}, and C={b,c,d}. We have A⫫B∣C. Thus according to Theorems 2 and 3, we can obtain a local skeleton from the marginal distribution of A∪C, which may have spurious edges, as shown in Figure 2. Similarly, suppose that variables in {a,b,c,d} are observed but those in {e,…,j} are not observed. Then we obtain the local skeleton from the marginal distribution of {a,b,c,d}, as shown in Figure 3. Note that the edges (b,c), (b,d), and (c,d) falling into C are spurious in Figure 2, but they are absent in Figure 3.Figure 2
A local skeleton recovered from the marginal distribution of{b,…,j}.Figure 3
A local skeleton recovered from the marginal distribution of{a,b,c,d}.Next we discuss recovery of complexes from a marginal distribution ofA∪C. We say that a complex (a,a1,…,ak,c) (k≥1) can be determined validly from the marginal distribution of A∪C if the marginal distribution has the following two conditions: (1) a⫫c∣S for some S⊆(A∪C) and (2) a⫫c∣S∪{a1} and a⫫c∣S∪{ak}. Below we discuss which complexes of local structure can be determined validly from the marginal distribution and which cannot. The following two theorems show conditions for determining complexes and for validity of determined complexes, respectively.Theorem 4.
If at most one vertex of a complex is not contained inA, then the complex can be determined from the marginal distribution of A∪C.Proof.
Let(a,a1,…,ak,c) (k≥1) be a complex where a and c are the parents of this complex and at most one of these vertices is not contained in A. It follows from A⫫B∣C that {a,a1,…,ak,c}⊆A∪C. From Theorems 2 and 3, we can validly determine the presence of edges (a,a1),(a1,a2),…,(ak,c) and find a subset S of A∪C that c-separates a and c and does not contain the vertices from a1 to ak. Thus this complex (a,a1,…,ak,c) can be determined from the marginal distribution of (A,C).Theorem 5.
If two parents of a complex are contained inA, then the directions of the complex can be determined from the marginal distribution of A∪C.Proof.
Let(a,a1,a2,…,c2,c1,c) be a complex where a and c are the parents of this complex and {a,c}⊆A. It follows from A⫫B∣C that {a1,c1}⊆A∪C (a1 and c1 may be the same vertex). Rewrite this complex as (a,a1,…,ai,…,cj,…,c1,c), where (a,a1,…,ai)∪(cj,…,c1,c)⊆A∪C and (ai+1,cj+1)⊆B. Then we can determine the presence of edge (ai,cj) from the marginal distribution of (A,C). From Theorems 2 and 3, we can validly determine the presence of edges (a,a1),(a1,a2),…,(ai-1,ai),(cj,cj-1),…,(c2,c1),(c1,c) as well as finding a subset S of A∪C that c-separates a and c and does not contain the vertex a1 nor c1. Thus the directions of this complex, a→a1 and c→c1, can be determined from the marginal distribution of (A,C).According to Theorem4, from the marginal distribution of A∪C, we can determine all complexes in the local structure which have at most one vertex in C. When two parents of a complex are contained in C, it may not be determined since the two parents may not be c-separated by any subset of A∪C. From Theorem 5, however, if a complex is determined from the marginal distribution of A∪C whose two parents are contained in A, the directions of the complex must be valid. A complex who has more than one vertex fall into C may be a spurious complex since the edges falling into C may be spurious.From Theorems2 to 5, we can get an approach for local structure recovery, in which edges can be recovered according to Theorems 2 to 3, and then directions can be determined according to Theorems 4 and 5. Suppose that we are interested in the local structure recovery of a CG over a set A of variables. Then we must find a set C to be observed based on the domain or prior knowledge such that C is large enough to c-separate A from the set B of unobserved variables.Example
1 (continued). Now we search complexes in Figures 2 and 3. For Figure 2, suppose that variable {a} is not observed. According to Theorem 4, three complexes (b,e,g,i), (c,e,g,i), and (f,h,g) can be found from the marginal distribution of A∪C, as shown in Figure 4. The complexes (c,f,d) and (b,e,c) cannot be found since there exist spurious edges between their parents, although the directions of b,e and c,e are oriented with other complexes. For Figure 3, there is no complex in this local structure because variables b,c, and d are conditional independent given variable a.Figure 4
A partially oriented local structure over{b,…,j}.If variable{a} is omitted or unobservable, we only obtain the local structure in Figure 4, in which all directions and all edges not falling into C are valid, but edges falling into C (here (b,c), (b,d), and (c,d)) may be spurious.


## 4. Discussion

We showed that the conditional independenceA⫫B∣C is a sufficient condition for local structure recovery when there exist unobserved or latent variables or after marginalization over observed variables. The conditional independence is an important prior knowledge for local structure recovery. This prior may hold in many cases, such as Markov chain, chain graphical models, and dynamic or temporal models [1]. Suppose that we are interested in the local structure of a CG over a set A of variables. We must find a set C which is large enough to separate A from the set B of unobserved variables. Based on the conditional independence A⫫B∣C, we explained which edges and directions of edges in local structure can be recovered validly and which cannot after marginalization.Based on the theoretical results presented in this paper, we can efficiently recover local structures of aCG. Domain or prior knowledge of conditional independencies can be utilized to facilitate the structural recovery. The theoretical results can also be used for an observational study design and a split questionnaire survey sampling [22, 23].



---

*Source: 982495-2015-03-15.xml*