  Given a pair of graphs $G_1$ and $G_2$ and a vertex set of interest in $G_1$,
the vertex nomination (VN) problem seeks to find the corresponding vertices of
interest in $G_2$ (if they exist) and produce a rank list of the vertices in
$G_2$, with the corresponding vertices of interest in $G_2$ concentrating,
ideally, at the top of the rank list. In this paper, we define and derive the
analogue of Bayes optimality for VN with multiple vertices of interest, and we
define the notion of maximal consistency classes in vertex nomination. This
theory forms the foundation for a novel VN adversarial contamination model, and
we demonstrate with real and simulated data that there are VN schemes that
perform effectively in the uncontaminated setting, and adversarial network
contamination adversely impacts the performance of our VN scheme. We further
define a network regularization method for mitigating the impact of the
adversarial contamination, and we demonstrate the effectiveness of
regularization in both real and synthetic data.
