# On seeded subgraph-to-subgraph matching: The ssSGM Algorithm and matchability information theory

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

## Key facts

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

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

- [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)

## Abstract (arXiv)

The subgraph-subgraph matching problem is, given a pair of graphs and a positive integer K, to find K vertices in the first graph, K vertices in the second graph, and a bijection between them, so as to minimize the number of adjacency disagreements across the bijection; it is ``seeded" if some of this bijection is fixed. The problem is intractable, and we present the ssSGM algorithm, which uses Frank-Wolfe methodology to efficiently find an approximate solution. Then, in the context of a generalized correlated random Bernoulli graph model, in which the pair of graphs naturally have a core of K matched pairs of vertices, we provide and prove mild conditions for the subgraph-subgraph matching problem solution to almost always be the correct K matched pairs of vertices.