# Seeded Graph Matching

**Department of Applied Mathematics and Statistics**

**Human Language Technology Center of Excellence**

**Johns Hopkins University**

and

**Raytheon BBN Technologies**

Donniell E. Fishkind, Sancar Adali, Heather G. Patsolic, Lingyao Meng, Vince Lyzinski, C.E. Priebe, “Seeded Graph Matching,” Pattern Recognition, vol 87, pp 203-215, 2019.

## Abstract

Given two graphs, the graph matching problem is to align the two vertex sets so as to minimize the number of adjacency disagreements between the two graphs. The seeded graph matching problem is the graph matching problem when we are first given a partial alignment that we are tasked with completing. In this paper, we modify the state-of-the-art approximate graph matching algorithm “FAQ” of Vogelstein et al. (2015) to make it a fast approximate seeded graph matching algorithm, adapt its applicability to include graphs with differently sized vertex sets, and extend the algorithm so as to provide, for each individual vertex, a nomination list of likely matches. We demonstrate the effectiveness of our algorithm via simulation and real data experiments; indeed, knowledge of even a few seeds can be extremely effective when our seeded graph matching algorithm is used to recover a naturally existing alignment that is only partially observed.

## Codes and Experiments

### Required `R`

packages

To reproduce the figures in the paper, following packages are required:

`igraph`

`VN`

- and some other utility packages for plotting (
`reshape2`

, `ggplot2`

, etc).

There is a sister package for SGM developed by one of our collegues called `iGraphMatch`

, which contains several more extensions, e.g., evaluation of goodness of matching, more flexible initialization methods, etc., but it was not used in this paper.

`R`

Codes and Data

To run the experiments in the paper, please download this zip file. Once uncompressed, you will find folders named by figure numbers, e.g., `fig01`

, `fig11a`

, etc. Each folder contains reproducible `R`

files along with necessary data files in `RData`

format. The saved figures as well as data tables are also included.

*prepared by [email protected] on Thu Mar 7 07:51:37 2019*