Online Program Home
  My Program

All Times EDT

Abstract Details

Activity Number: 69 - Network Analysis
Type: Contributed
Date/Time: Monday, August 3, 2020 : 10:00 AM to 2:00 PM
Sponsor: Section on Statistical Learning and Data Science
Abstract #313388
Title: Graph Matching via Mutual Nearest Neighbors
Author(s): Zihuan Qiao* and Daniel L Sussman
Companies: Boston University and Boston University
Keywords: graph matching; networks; mutual nearest neighbor; noisy prior information

The graph matching problem seeks to find the vertex correspondence between two observed graphs that best preserves the topological structure and has applications in the de-anonymization of social networks, PPI networks alignment in bioinformatics, and pattern recognition. We propose a mutual nearest neighbor graph matching algorithm that starts with a partial correspondence between a subset of node pairs allowing for noise. Our algorithm corrects erroneous matches and expands the match to the rest of the graphs. The intuition here is that a pair of nodes that have the most matched neighboring pairs among all the other candidates for both nodes is a promising match. Under a flexible model for correlated random graphs, we provide assumptions on the graph structure and the initial match for accomplishing self-correction and conditions for achieving high precision. Our approach is fast and scalable to matching very large graphs and the time complexity for each iteration is O(n^2). Lastly, we demonstrate the effectiveness of our algorithm in matching large-scale graphs in terms of both accuracy and running time using synthesized and real data experiments.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2020 program