# Structural Learning about Directed Acyclic Graphs from Multiple Databases

Authors: Qiang Zhao
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

We propose an approach for structural learning of
directed acyclic graphs from multiple databases. We first learn a local structure
from each database separately, and then we combine these local structures
together to construct a global graph over all variables. In our approach, we
do not require conditional independence, which is a basic assumption in most
methods.


---

## Body

## 1.  Introduction

Graphical models including independence graphs, directed acyclic graphs (DAGs), and Bayesian networks have been applied widely to many fields, such as data mining, pattern recognition, artificial intelligence, complex systems, and causal discovery [1–4]. Graphical models can be used to cope with uncertainty for a large system with a great number of variables. Structural learning of graphical models from data is an important and difficult problem and has been discussed by many authors [1–5]. There are two main kinds of structural learning methods. One is constraint-based learning and the other is score-based learning. Most of the structural learning approaches deal with only one database with completely observed data. With the development and popularity of computers, various databases have been built, which may contain different sets of variables and overlap with each other. For example, in medical research, a researcher collects data of these variables, another researcher may collect data of other variables, and they have some common variables.In this paper, we discuss how to learn the structures of DAGs from multiple databases with different and overlapped variables. In our approach, we first learn a local structure from each database separately, and then we combine these structures together to construct a global graph over all variables. Several theoretical results are shown for the validity of our algorithm. Our approach can validly discover DAGs from multiple databases. In our approach, we only need a weaker condition than conditional independence, which is a basic assumption in most methods [1–5]. This approach can also utilize the prior knowledge of conditional independencies to reduce the number of variables in each conditional set.Section2 gives notation and definitions. In Section 3, we show how to construct the DAG with multiple databases. We give an example in Section 4 to illustrate our approach for recovering a DAG. Finally a discussion is given in Section 5.


## 2. Notation and Definitions

LetG→V=(V,E→V) denote a DAG where V is a set of n vertices {a,b,…} and E→V⊆V×V is a set of directed edges. A directed edge from a vertex a to another vertex b is denoted by 〈a,b〉, and we say that a is a parent of b and b is a child of a. We denote the set of all parents of a vertex b by pa(b). A path l between the two distinct vertices a and b is a sequence of distinct vertices that starts with a, ends with b, and two consecutive vertices are connected by an edge; that is, l=(c0=a,c1,…,cn-1,cn=b), where 〈ci-1,ci〉 or 〈ci,ci-1〉 is contained in E→V, for i=1,…,n (n≥1), and ci≠cj, for all i≠j. We say that a is an ancestor of b and b is a descendant of a if there is a path from a to b in G→V and all edges on this path point at the direction toward b. Denote the set of ancestors of b as an(b). A path l is said to be separated by a set of vertices Z if and only if there exists at least one i∈{1,2,…,k-1}, such that ci∈Z. And l is said to be d-separated by Z if and only if (1)
lcontains a “chain” i→m→j or a “fork” i←m→j such that the middle vertex m is in Z, or(2)
l contains an “inverted fork” i→m←j such that the collision vertex m is not in Z and no descendant of m is in Z.Two setsA and B of vertices are separated (d-separated) by a set C if C separates (d-separates) every path from any vertex in A to any vertex in B, and we say C is a separator (d-separator) of A and B. If a→c←b, 〈a,b〉∉E→V and 〈b,a〉∉E→V in a DAG G→V, then the triple (a,c,b) is called an immorality and a and b are called two parents of the immorality.Note that the two vertexesa and b of the DAG are nonadjacent if and only if they are d-separated by some subset S⊂V{a,b}. Though this is obvious the case by taking S to be either pa(a) or pa(b) for DAGs, there are certain types of graphs in which nonadjacency is not sufficient for separability, for example, the ancestral graph in [6].Example 2.1.
Consider a DAGG→V=(V,E→V) in Figure 1, where V={a,…,j} and E→V={〈a,b〉,〈a,c〉,〈a,d〉,〈b,e〉,〈c,e〉,〈c,f〉,〈d,f〉,〈f,h〉,〈g,e〉,〈g,h〉,〈g,i〉,〈h,j〉}. In this DAG, we have pa(e)={b,c,g} and that (c,e,b), (b,e,g), (c,e,g), (c,f,d), and (f,h,g) are immoralities. The path l=(a,c,f,h) between a and h is d-separated by {c} or {f}, while the path l'=(a,b,e,g) between a and g is d-separated by the empty set. Vertex a is an ancestor of h and h is a descendant of a. The sets A={a} and B={e,f,g,h,i,j} are d-separated by the set C={b,c,d}.Figure 1
A directed graphG→V.Letn vertices {a,b,…} in a DAG G→V denote n variables {X1,…,Xn}. If a joint distribution or density of variables X1,…,Xn satisfies
(2.1)P(x1,…,xn)=∏i=1n‍P(xi∣pai),
where P(xi∣pai) is the conditional probability or density of Xi given pa(Xi)=pai, then DAG G→V and the distribution P are said to be compatible [3] and P obeys the global directed Markov property of G→V [2]. We use the notation in [7] to denote independence. Let X⫫Y denote the independence of X and Y and X⫫Y|Z the conditional independence of X and Y given Z for any variables or sets of variables X, Y, and Z. Since in our discussion we always think the joint distribution corresponds to an underlying DAG, we do not differentiate the usage of letters as X,  Y,  Z,  A,  B,  C to denote variables or vertexes; however, we will make an obvious reference if the context is not clear.As pointed out by [3], if sets X and Y are d-separated by Z, then X is independent of Y conditionally on Z in every distribution that is compatible with G→V. In this paper, we assume that all the distributions are compatible with G→V. We also assume that all independencies of a probability distribution of variables in V can be checked by d-separation of G→V, called the faithfulness assumption in [4]. The faithfulness assumption means that all independencies and conditional independencies among variables can be represented by G→V. For a distribution which obeys the faithfulness assumption, we can learn the underlying DAG by checking the pairwise conditional independence X⫫Y∣Z, where X and Y are two random variables and Z is a subset of variables.A hypergraph is a collection of vertex sets [8, 9]. Multiple databases 𝒞={C1,…,CH} are depicted as a hypergraph, where a hyperedge Ch is an observed variable set in a database and ∪h=1HCh=V [5, 10]. A database with an observed variable set Ch is treated as a sample from a marginal distribution of the variable set Ch. Let Dh=Ch∩(∪k≠hCk), which is the intersection of Ch and the other sets. Given a collection of databases 𝒞, there is no information on higher interactions over different databases.Example 2.2.
Let𝒞={C1={1,2,3,4},C2={1,3,5,6},C3={4,6,7}} be a hypergraph, as shown in Figure 2. We can get that D1={1,3,4}, D2={1,3,6}, and D3={4,6}.Figure 2
A hypergraph.


## 3. Structural Learning of DAGs

In this section, we propose an approach for structural learning of DAGs. In our approach, we first learn a local structure from each database, and then we combine these local structures together to construct a global graph over all variables.Note that for a distribution obeying the faithfulness assumption with respect to a certain DAGG→V, there may not exist a DAG which can fully represent all the conditional independencies in the marginal distribution; see [6] for more discussion on this issue. Though this fact implies that we may not expect to learn a DAG for each database, it will be shown that under a certain condition a marginal structure could be learned which partially reflects the original true structure.We consider a joint distribution on a set of variablesV which satisfies the faithfulness assumption and denote by G→V=(V,E→V) the DAG which can fully represent the conditional independencies in this joint distribution. We consider the problem of structure recovery from multiple databases. To facilitate our discussion, we first give the definition of the local structure.Definition 3.1.
For a DAGG→V=(V,E→V) and a subset V′⊂V, we define the local structure G-V' to be an undirected graph G-V'=(V',E') where the edge set E'={(u,v):u,v∈E'andu⫫v∣Sfor all S⊂V'∖{u,v}}.From the definition, it is known that to judge whetheru and v are adjacent in the local structure G-V', we need only to search for a d-separator S from all possible variable subsets S⊂V' such that two variables u and v are independent conditionally on S. With the faithfulness assumption, this is equivalent to test whether u and v are independent conditionally on S and this can be done by using data observed on V' only. Note that the edges in the local structure may be spurious in the sense that its two vertexes are not adjacent in the original DAG; we call these edges spurious edges. However, in the section below, we show that such learned local structure could be used to identify part of the true structure of the original DAG under one additional condition. We give a lemma to be used in proofs of theorems.Lemma 3.2.
Ifu is not an ancestor of v, then u and v are d-separated by a subset of V if and only if they are d-separated by pa(u).Proof.
See [2].The following two theorems show the relationship between the local structure and the true structure of the original DAG.Theorem 3.3.
LetA, B, and C be a partition of V. If A and B are separated by C, then two vertices in A are d-separated by a subset of V if and only if they are d-separated by a subset of A∪C.Proof.
The necessity is obvious sinceV⊇A∪C. For the sufficiency, let u and v be two vertices in A that are d-separated by S  (⊆V). Thus there is no edge connecting u and v in G→V. Since u and v are contained in A and A and C are separated by B, pa(u) and pa(v) are contained in A∪C. Without loss of generality, suppose that u is not an ancestor of v. From Lemma 3.2 we have that pa(u)  (⊆A∪C)  d-separates u and v.From Theorem3.3, we can see that two vertexes in A are adjacent in the DAG G→V if and only if they are adjacent in the local structure G-A∪C. This means that with the faithfulness assumption, the existence of edges falling into A can be determined validly from the marginal distribution of A∪C.Theorem 3.4.
SupposeA, B, and C is a partition of V and A and B are separated by C. Let u∈C and v∈A∪C. If u and v are d-separated by a subset of A∪C, then they are d-separated by a subset of V.Proof.
The result is obvious sinceA∪C⊆V.According to Theorem3.4, we can see that u  (∈C) and v  (∈A∪C) are not adjacent in the DAG G→V if they are not adjacent in the local structure G-A∪C. This means that we may get spurious edges in the local structure G-A∪C.According to the two Theorems above, we can get that an edge whose two vertices are contained only by one databaseCh can be determined by using the marginal distribution of Ch without requirement of the other databases. Those edges crossing Ch∖Dh and Dh or falling into Dh may be spurious. Their existence must be determined according to multiple databases.Now we give the algorithm for structural learning of directed acyclic graphical models.Algorithm 3.5.
Construct a DAG from Multiple Databases(1)
Input: Multiple databases𝒞={C1,…,CH}.(2)
Construct a local structureG-h from database Ch separately for each h:
(a)
InitializeG-h as a complete undirected graph;(b)
Delete edge(x,y) from G-h if there exists a subset Z of Ch such that x and y are conditional independent given Z.(3)
Construct the global undirected graphG-V:
(a)
Initialize the edge setE of G-V as the union of all edge sets of G-h for h=1,…,H;(b)
For an edge(x,y), which falls into some Dh, delete it from G-V if it is absent in some other G-h'.(4)
Delete spurious edges to construct the global skeleton:
(a)
For an edge(x,y) with x in some Ch∖Dh and y in Dh, delete it from G-V if there exists a subset Z of ne(y) such that x and y are conditional independent given Z;(b)
For an edge(x,y), which fall in some Dh, delete it from G-V if there exists a subset Z of ne(x)∖{y} or ne(y)∖{x} such that x and y are conditional independent given Z.(5)
Construct the equivalence class:
(a)
Orient the local skeletonx-z-y as x→z←y if x and y are not adjacent in G-V and z∉Z;(b)
Orient other edges if each opposite of them creates either a directed cycle or a new immorality.(6)
Output: The equivalence class of DAGs.Note thatne(y) at step 4 denotes all the vertices that are adjacent with vertex y. According to Theorems 3.3 and 3.4, the equivalence class constructed by the above algorithm is valid.


## 4. Illustration of Structural Learning

In this section, we illustrate our algorithm using the ALARM network in Figure3 that is often used to evaluate structural learning algorithms [4, 11, 12]. The ALARM network in Figure 3 describes causal relations among 37 variables in a medical diagnostic system for patient monitoring. Using the network, some researchers generate continuous data from normal distributions and others generate discrete data from multinomial distributions [4, 12]. Our approach is applicable for both continuous and discrete data. Since the validity of our algorithm can be ensured by Theorems 3.3 and 3.4, the algorithm is illustrated by using conditional independencies from the underlying directed acyclic graph in Figure 3 rather than conditional independence tests from simulated data.Figure 3
The ALARM network and multiple databases.Suppose that we have three databases as depicted by the hypergraph in Figure3. Database C1 contains variables {1,2,3,4,5,6,7,8,11,27,28}, database C2 contains variables {8,9,28,29,30,31,32}, and database C3 contains variables {9,10,11,12,13,14,15,16,18,19,20,22,23,24,25,26,33,34,35,36,37}. Thus D1={8,11,28}, D2={8,9,28}, and D3={9,11}. Note that C1∖D1 and V∖C1 are not conditional independent givenD1. At Step  2, the local structures are obtained separately from the three databases, as shown in Figures 4(a), 4(b), and 4(c), respectively, for example, the undirected edge (6,27) because 6 is independent of 27 conditional on {5}.Local structures for all databases.
(a)
The local structureG-1 for database C1
(b)
The local structureG-2 for database C2
(c)
The local structureG-3 for database C3At step 3, we combine three local structures together to construct the global undirected graph, as shown in Figure5. At step 4, we delete the spurious edges to get the global skeleton, which is the undirected version of Figure 6. For example, the spurious edge (8,11) can be deleted since variables 8 and 11 are conditional independent given {7,10}.Figure 5
The global undirected graph.Figure 6
The partially directed acyclic graph.At step 5, we determine immoralities and orient edges as much as possible. For example, the direction of the undirected edge(1,2) is determined as 〈2,1〉 by 〈4,2〉 so as not to create a new v-structure, and the direction of the undirected edge (16,23) is determined as 〈16,23〉 by 〈16,20〉 and 〈20,23〉 so as not to create a cycle. At last we obtain the equivalence class in Figure 6, in which all directed edges are oriented correctly, except that four undirected edges (5,27), (10,33), (21,34), and (35,37) cannot be oriented because any of their orientation leads to a Markov equivalent DAG.


## 5.  Discussion

In this paper, we presented an approach for structural learning of directed acyclic graphs from multiple databases. In our approach, we require thatCh∖Dh and V∖Ch are separated by Dh, which is a weaker condition than the condition that Ch∖Dh and V∖Ch are d-separated by Dh. This condition can be judged with experts’ prior knowledge of associations among variables, such as Markov chains, chain graphical models, and time series.There are several obvious advantages of our approach for structural learning. First we do not require conditional independence, which is a basic assumption in most methods. Second we searchd-separators in Ch or ne(x), which is much smaller than V. At last, the theoretical results proposed in this paper can be applied to scheme design of multiple databases. Without loss of information on structural learning of DAGs, a joint data set can be replaced by a group of incomplete data sets based on the prior knowledge.



---

*Source: 579543-2012-12-27.xml*