  In many application domains, such as computational biology, the goal of
graphical model structure learning is to uncover discrete relationships between
entities. For example, in our problem of interest concerning HIV vaccine
design, we want to infer which HIV peptides interact with which immune system
molecules (HLA molecules). For problems of this nature, we are interested in
determining the number of nonspurious arcs in a learned graphical model. We
describe both a Bayesian and frequentist approach to this problem. In the
Bayesian approach, we use the posterior distribution over model structures to
compute the expected number of true arcs in a learned model. In the frequentist
approach, we develop a method based on the concept of the False Discovery Rate.
On synthetic data sets generated from models similar to the ones learned, we
find that both the Bayesian and frequentist approaches yield accurate estimates
of the number of non-spurious arcs. In addition, we speculate that the
frequentist approach, which is non-parametric, may outperform the parametric
Bayesian approach in situations where the models learned are less
representative of the data. Finally, we apply the frequentist approach to our
problem of HIV vaccine design.
