# Vertex Nomination Via Seeded Graph Matching

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2017.

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

- [Graph Matching via Optimal Transport](https://mlsanity.com/paper/2111.05366/) (2021)
- [Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labels](https://mlsanity.com/paper/2208.08638/) (2022)
- [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)

Consider two networks on overlapping, non-identical vertex sets. Given vertices of interest in the first network, we seek to identify the corresponding vertices, if any exist, in the second network. While in moderately sized networks graph matching methods can be applied directly to recover the missing correspondences, herein we present a principled methodology appropriate for situations in which the networks are too large for brute-force graph matching. Our methodology identifies vertices in a local neighborhood of the vertices of interest in the first network that have verifiable corresponding vertices in the second network. Leveraging these known correspondences, referred to as seeds, we match the induced subgraphs in each network generated by the neighborhoods of these verified seeds, and rank the vertices of the second network in terms of the most likely matches to the original vertices of interest. We demonstrate the applicability of our methodology through simulations and real data examples.