# Vertex nomination schemes for membership prediction

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2013.

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

- [Spectral clustering under degree heterogeneity: a case for the random walk Laplacian](https://mlsanity.com/paper/2105.00987/) (2021)
- [Hypothesis Testing for Equality of Latent Positions in Random Graphs](https://mlsanity.com/paper/2105.10838/) (2021)
- [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)
- [The Klarna Product Page Dataset: Web Element Nomination with Graph Neural Networks and Large Language Models](https://mlsanity.com/paper/2111.02168/) (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)
- [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 a graph is realized from a stochastic block model where one of the blocks is of interest, but many or all of the vertices' block labels are unobserved. The task is to order the vertices with unobserved block labels into a ``nomination list'' such that, with high probability, vertices from the interesting block are concentrated near the list's beginning. We propose several vertex nomination schemes. Our basic - but principled - setting and development yields a best nomination scheme (which is a Bayes-Optimal analogue), and also a likelihood maximization nomination scheme that is practical to implement when there are a thousand vertices, and which is empirically near-optimal when the number of vertices is small enough to allow comparison to the best nomination scheme. We then illustrate the robustness of the likelihood maximization nomination scheme to the modeling challenges inherent in real data, using examples which include a social network involving human trafficking, the Enron Graph, a worm brain connectome and a political blog network.