• Home Page
• Documentation
• Examples
• Research Notes
• Small Simulation Studies
• Bayesian Network Repository

• About the Author

info & code

data & R code

data & R code

Whitelists and blacklists in structure learning

The first step in learning a Bayesian network is structure learning, that is, using the data to determine which arcs are present in the graph that underlies the model. Often, we would like for that to be a purely data-driven process—for the purposes of exploring the data, in benchmarking learning algorithms, or just because we do not know much about the phenomenon we are trying to model. However, in some contexts we have prior knowledge on what the structure of the network should look like and we would like to incorporate such knowledge in the structure learning process. One way to do that is to use whitelists and blacklists. Both are implemented as follows in bnlearn.

1. Arcs in the whitelist are always included in the network.
2. Arcs in the blacklist are never included in the network.
3. Any arc whitelisted and blacklisted at the same time is assumed to be whitelisted, and is thus removed from the blacklist. In other words, the whitelist has precedence over the blacklist.

These general rules are applied in slightly different ways to different classes of structure learning algorithms, because the latter search for the optimal model in different spaces and in different ways. For instance, score-based learning algorithms operate on the space of DAGs, and therefore cannot deal with whitelisted undirected arcs.

Both whitelists and blacklists can be specified using:

1. a matrix with two columns, optionally labelled from and to, which the labels of the nodes the arcs are incident on;

   > wl = matrix(c("A", "B", "B", "C"), ncol = 2, byrow = TRUE,
   +        dimnames = list(NULL, c("from", "to")))
   > wl
   

        from to 
   [1,] "A"  "B"
   [2,] "B"  "C"
   

2. a data frame with the same structure;

   > wl = data.frame(from = c("A", "B"), to = c("B", "C"))
   > wl
   

     from to
   1    A  B
   2    B  C
   

3. in the case of a single arc, just a character vector with the labels of the two tail and the head nodes of the arc.

   > wl = c("A", "B")
   

Both the whitelist and the blacklist used in learning a network are stored in the bn object returned by the learning algorithm, and can be recovered using the whitelist() and blacklist() functions. Note that both are stored after preprocessing and sanitization, so they may not necessarily coincide with the original provided by the user.

Undirected arcs are specified by including both directions of in the whitelist or in the blacklist (e.g. A → B and B → A).

Constraint-based structure learning algorithms

Constraint-based algorithms learn the structure of the network by first learning its skeleton; so they accept both directed and undirected arcs in the whitelist and in the blacklist.

> library(bnlearn)
> plot(inter.iamb(learning.test))

An arc can be blacklisted in one direction (i.e. A → B is in the blacklist but B → A is not), leaving the algorithm free to include the same arc but in the opposite direction if it is supported by the data. This is useful in setting the direction of arcs which would otherwise be undirected because of score equivalence, as A – B in the network above.

> plot(inter.iamb(learning.test, blacklist = c("A", "B")))

An arc can also be blacklisted in both directions, which prevents the learning algorithm from connecting the two corresponding nodes either with an undirected arc (i.e. A – B) or with a directed arc (i.e. A → B or B → A). This is because we are effectively blacklisting the undirected arc in the skeleton in the early stages of the learning algorithm, since undirected arcs are represented as a pair of directed arcs in opposite directions.

> bl = matrix(c("A", "B", "B", "A"), ncol = 2, byrow = TRUE)
> plot(inter.iamb(learning.test, blacklist = bl))

Conversely, an arc can be whitelisted in only one direction (i.e. A → F is in the whitelist but F → A is not). This implies that the arc incident on the same nodes but in the other direction cannot be present in the graph, and therefore it is added to the blacklist.

> cpdag = inter.iamb(learning.test, whitelist = c("A", "F"))
> whitelist(cpdag)

     from to 
[1,] "A"  "F"

> blacklist(cpdag)

     from to 
[1,] "F"  "A"

> plot(cpdag)

An arc can also be whitelisted in both directions (i.e. both A → F and F → A are in the whitelist). In this case, the two nodes the arc is incident are guaranteed to be connected by an arc in the graph; the direction (if any) is left for the learning algorithm to decide.

> wl = matrix(c("A", "F", "F", "A"), ncol = 2, byrow = TRUE)
> plot(inter.iamb(learning.test, whitelist = wl))

Note that the whitelist should not introduce directed cycles in the graph, but undirected or partially directed cycles are allowed; the learning algorithm will take care of resolving them and producing an acyclic graph.

> wl = matrix(c("A", "B", "B", "C", "C", "A"), ncol = 2, byrow = TRUE)
> plot(inter.iamb(learning.test, whitelist = wl))

## Error: this whitelist does not allow an acyclic graph.

> wl = matrix(c("A", "B", "B", "A", "B", "C", "C", "B",
+        "C", "A", "A", "C"), ncol = 2, byrow = TRUE)
> plot(inter.iamb(learning.test, whitelist = wl))

Score-based structure learning algorithms

Score-based algorithms work in the space of directed arcs, so they have no concept of undirected arcs. Blacklisting an arc in one direction (i.e. A → B is in the blacklist but B → A is not) leaves the algorithm free to include the same arc but in the opposite direction as before.

> plot(hc(learning.test, blacklist = c("A", "B")))

Blacklisting an arc in both directions (i.e. A → B and B → A) still prevents any arc between the nodes (i.e. A and B) from being present in the network. The end result is again the same as for constraint-based algorithms.

> bl = matrix(c("A", "B", "B", "A"), ncol = 2, byrow = TRUE)
> plot(hc(learning.test, blacklist = bl))

Similarly, whitelisting an arc in one direction (i.e. A → F is in the whitelist but F → A is not) again forces that arc to be in the network in that particular direction, and adds the arc in the opposite direction to the blacklist.

> dag = hc(learning.test, whitelist = c("A", "F"))
> whitelist(dag)

     from to 
[1,] "A"  "F"

> blacklist(dag)

     from to 
[1,] "F"  "A"

> plot(dag)

Whitelisting an arc in both directions (i.e. both A → F and F → A are in the whitelist) is not allowed, because score-based algorithms operate in the space of directed acyclic graphs and have no concept of undirected arcs. As was the case for constraint-based algorithms, checks are in place to prevent the whitelist from introducing cycles in the graph.

Local search learning algorithms

Local search algorithms such as Chow-Liu and ARACNE operate on the space of undirected graphs. Therefore, any arc in the blacklist is treated as an undirected arc.

> bl = matrix(c("A", "F", "F", "A"), ncol = 2, byrow = TRUE)
> blacklist(aracne(learning.test, blacklist = bl))

     from to 
[1,] "A"  "F"
[2,] "F"  "A"

> bl = matrix(c("A", "F"), ncol = 2, byrow = TRUE)
> blacklist(aracne(learning.test, blacklist = bl))

     from to 
[1,] "A"  "F"
[2,] "F"  "A"

The same is true for arcs in the whitelist.

> wl = matrix(c("A", "F", "F", "A"), ncol = 2, byrow = TRUE)
> whitelist(aracne(learning.test, whitelist = wl))

     from to 
[1,] "A"  "F"
[2,] "F"  "A"

> wl = matrix(c("A", "F"), ncol = 2, byrow = TRUE)
> whitelist(aracne(learning.test, whitelist = wl))

     from to 
[1,] "A"  "F"
[2,] "F"  "A"

Note that undirected cycles in the whitelist are fine in aracne() but not in chow.liu(), since the latter must return a tree (which by definition cannot contain cycles).

> wl = matrix(c("A", "B", "B", "C", "C", "A"), ncol = 2, byrow = TRUE)
> aracne(learning.test, whitelist = wl)
> chow.liu(learning.test, whitelist = wl)

## Error: this whitelist does not allow an acyclic graph.

Hybrid structure learning algorithms

The behaviour of hybrid algorithms depends on the specific algorithms used in the restrict and maximize phases. The whitelist and the blacklist stored in the bn object are those from the algorithm used in the maximize phase.