Seeded Graph Matching

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 article, 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.

Paper

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

Source Codes:

Matlab codes for Figs 6, 8, 10.
R codes for Figs 1~5, 7, 9, 11.

Data

name	# obs	feature	idm	label	graph, etc.
Enron	184 nodes, 187 weeks	.	.	.	enron.mat See here
C.elegans	279 nodes 170 nodes	.	.	included in the Rd files ("vcols"): 1: mortor neurons, 2: interneurons, 3: seonsory neurons	elegansGraph.mat elegansGraph_male.mat herm_Graph.Rd (R format) See here
Wiki	1382	English Algebraic Geometry WCH French Algebraic Geometry WCH See here for more detail	GE, GF TE, TF See here for more detail Ming's Data	6 classes: 1. people, 2. places, 3. dates, 4. things, 5. math things, 6. categories	agdata.tar See here agxml.tgz See here wiki_adj.mat See here

Last Modified by YP: