# On consistent vertex nomination schemes

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Nov 2017.

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

- [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)
- [Adversarial contamination of networks in the setting of vertex nomination: a new trimming method](https://mlsanity.com/paper/2208.09710/) (2022)

## Abstract (arXiv)

Given a vertex of interest in a network G1, the vertex nomination problem seeks to find the corresponding vertex of interest (if it exists) in a second network G2. A vertex nomination scheme produces a list of the vertices in G2, ranked according to how likely they are judged to be the corresponding vertex of interest in G2. The vertex nomination problem and related information retrieval tasks have attracted much attention in the machine learning literature, with numerous applications to social and biological networks. However, the current framework has often been confined to a comparatively small class of network models, and the concept of statistically consistent vertex nomination schemes has been only shallowly explored. In this paper, we extend the vertex nomination problem to a very general statistical model of graphs. Further, drawing inspiration from the long-established classification framework in the pattern recognition literature, we provide definitions for the key notions of Bayes optimality and consistency in our extended vertex nomination framework, including a derivation of the Bayes optimal vertex nomination scheme. In addition, we prove that no universally consistent vertex nomination schemes exist. Illustrative examples are provided throughout.