Seeded Graph Matching

• Activity Number: 402
• Type: Contributed
• Date/Time: Tuesday, August 5, 2014 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Vince Lyzinski*+
• Companies: Johns Hopkins University
• Keywords: graph matching ; pattern recognition ; multidimensional scaling ; machine learning ; computing methodologies

Abstract

Given two graphs, the graph matching problem seeks to find a correspondence (i.e. "matching") between the vertex sets that best preserves structure across the graphs. In the seeded graph matching paradigm, we assume that we are further provided a partial correspondence between subsets of the vertex sets and leverage this information to find the correspondence for the remaining unseeded vertices. I'll present a robust algorithm for approximately solving the seeded graph matching problem, highlighting along the way applications of our methodology in connectomics and a natural extension of our methodology to vertex classification. This is joint work with Sancar Adali, Youngser Park, Carey Priebe and Joshua Vogelstein.