Is there a way to prevent certain edges from occurring in structure learning?

[BKAmos]

A quick question,

Is there a way to prevent edges from being considered in the final predicted structure? I see there is a way to specify mandatory edges but not a way to disregard edges.

Best,
Kirtley

[BKAmos]

Thanks, Alberto,

This is good news and I'm glad that you responded so quickly.

That said, I'm having a hard time understanding this:

This replaces the max-min parent-children step of MMHC, whose output is a cpc (candidate parent-children). However, you can combine the both of them by running mmpc first to restrict the search space, set the forbidden edges to 0, and running hc on the cpc.

Are you saying that I can run mmpc to set the skeleton of the graph, while also setting the use.cpc to an n x n matrix to restrict edges? Then, take the output structure cpc and perform the learning of a directed structure using hc. That is essential mmhc broken down into components, yes?

Maybe a quick snippet of code would be helpful.

Best,
Kirtley

[albertofranzin]

Hello,

I checked better and my previous answer was not entirely correct, so I deleted it to avoid further confusion. There was also a bug I had to fix. Sorry for that.

In short, yes, you can forbid edges from appearing in the final network. This is done using the initial.cpc parameter in learn.network, and it works for both mmhc and sm. This parameter takes a n x n matrix, where each element cpc[i,j] if 1 if there may be an edge from node i to node j, and 0 if such an edge is forbidden.

MMHC is a two-step procedure. The first part is the MMPC (max-min parent-children) it computes the CPC (candidate parents and children), the (symmetric) matrix containing the Markov blanket for each node, so the set of possible edges in the final network. Then, a Hill Climbing heuristic is performed on the CPC, and the outcome is the set of directed edges that compose the final structure. So, if an edge does not appear in the CPC, if will not appear in the final network either.

In other words, the CPC restricts the search space for the HC. If you omit it, HC will operate on the whole matrix.

If you provide an initial CPC to MMHC, the MMPC step is not performed, so learn.network(dataset, algo="mmhc", initial.cpc=cpc) is equivalent to learn.network(dataset, algo="hc", initial.cpc=cpc).

However, you can combine the two steps (MMPC and injection of prior knowledge via initial.cpc) manually. The practical detail to remember is that since the CPC is not a DAG, it will be stored in wpdag (weighted partial DAG, the undirected adjacency matrix we use also when using bootstrap). Here below some examples (output omitted for the sake of brevity).

library(bnstruct)
a <- asia()
n <- learn.network(a)

is equivalent to

library(bnstruct)
a <- asia()
mb <- learn.network(a, algo="mmpc")
n <- learn.network(a, algo="hc", initial.cpc=wpdag(mb)) # you can omit the algorithm here

You can verify this by plotting the network. Now, suppose you want to forbid the edge that from "Asia" goes to "Smoke". You can do

library(bnstruct)
a <- asia()
mb <- learn.network(a, algo="mmpc")
initcpc <- wpdag(mb)
initcpc[1,3] <- 0
n <- learn.network(a, initial.cpc=initcpc)

and you will see that the final network is different.

You can entirely omit the MMPC step, but in this case the search space is potentially much larger.

library(bnstruct)
a <- asia()
initcpc <- matrix(1, nrow=8, ncol=8)
initcpc[1,3] <- 0
n <- learn.network(a, initial.cpc=initcpc)

The SM algorithm performs a complete search instead. You can restrict its search space by providing an initial CPC in the same way.

library(bnstruct)
a <- asia()
initcpc <- matrix(1, nrow=8, ncol=8)
initcpc[1,3] <- 0 
n <- learn.network(a, algo="sm", initial.cpc=initcpc)

or, combining both the MMPC and your knowledge, as

library(bnstruct)
a <- asia()
mb <- learn.network(a, algo="mmpc")
initcpc <- wpdag(mb)
initcpc[1,3] <- 0 
n <- learn.network(a, algo="sm", initial.cpc=initcpc)

There were a couple of bugs I had to fix, so please use the latest version here on GitHub. When I have more time I'll update the documentation and send the package to the CRAN.