# Vertex nomination: The canonical sampling and the extended spectral nomination schemes

arXiv: https://arxiv.org/abs/1802.04960 · HTML: https://mlsanity.com/paper/1802.04960/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2018.

## Built on by (most cited first, 6 of 6)

- [Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labels](https://mlsanity.com/paper/2208.08638/) (2022)
- [Leveraging semantically similar queries for ranking via combining representations](https://mlsanity.com/paper/2106.12621/) (2021)
- [Subgraph nomination: Query by Example Subgraph Retrieval in Networks](https://mlsanity.com/paper/2101.12430/) (2021)
- [Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding](https://mlsanity.com/paper/2312.11054/) (2023)
- [Maximum a Posteriori Inference of Random Dot Product Graphs via Conic Programming](https://mlsanity.com/paper/2101.02180/) (2021)
- [Adversarial contamination of networks in the setting of vertex nomination: a new trimming method](https://mlsanity.com/paper/2208.09710/) (2022)

## Abstract (arXiv)

Suppose that one particular block in a stochastic block model is of interest, but block labels are only observed for a few of the vertices in the network. Utilizing a graph realized from the model and the observed block labels, the vertex nomination task is to order the vertices with unobserved block labels into a ranked nomination list with the goal of having an abundance of interesting vertices near the top of the list. There are vertex nomination schemes in the literature, including the optimally precise canonical nomination scheme~LC and the consistent spectral partitioning nomination scheme~LP. While the canonical nomination scheme LC is provably optimally precise, it is computationally intractable, being impractical to implement even on modestly sized graphs. With this in mind, an approximation of the canonical scheme---denoted the it canonical sampling nomination scheme LCS---is introduced; LCS relies on a scalable, Markov chain Monte Carlo-based approximation of LC, and converges to LC as the amount of sampling goes to infinity. The spectral partitioning nomination scheme is also extended to the it extended spectral partitioning nomination scheme, LEP, which introduces a novel semisupervised clustering framework to improve upon the precision of LP. Real-data and simulation experiments are employed to illustrate the precision of these vertex nomination schemes, as well as their empirical computational complexity. Keywords: vertex nomination, Markov chain Monte Carlo, spectral partitioning, Mclust MSC[2010]: 60J22, 65C40, 62H30, 62H25