## 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. Normally, 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**.

- Arcs in the whitelist are always included in the network.
- Arcs in the blacklist are never included in the network.
- 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 differently to different classes of structure learning aglorithms, 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 blacklist can be specified using:

- 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"

- 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

- 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 aglorithm, 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) forces the algorithm to pick one of the
directions. This is done globally on the whole whitelist, essentially calling `cextend()`

.
This means that in the end the whitelist only contains directed arcs, and the corresponding arcs in
the opposite directions are added to the blacklist.

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

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

> blacklist(dag)

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

> plot(dag)

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.

`Tue Nov 14 16:14:35 2017`

with **bnlearn**

`4.3-20171001`

and `R version 3.0.2 (2013-09-25)`

.