Online Program Home
My Program

Abstract Details

Activity Number: 3 - Recent Developments in Network Testing
Type: Invited
Date/Time: Sunday, July 28, 2019 : 2:00 PM to 3:50 PM
Sponsor: IMS
Abstract #300186 Presentation
Title: A Full-Rank Spectral Algorithm for Graph Matching
Author(s): Zhou Fan* and Cheng Mao and Jiaming Xu and Yihong Wu
Companies: Yale University and Yale University and Duke Fuqua School of Business and Yale University
Keywords: Spectral algorithms; Random matrix theory; Network analysis

Given two unlabeled, edge-correlated graphs on the same set of vertices, we study the "graph matching" problem of identifying the unknown mapping from vertices of the first graph to those of the second. We propose a simple new method for this problem, which computes eigen-decompositions of the two graph adjacency matrices and returns a matching based on the pairwise alignments between all eigenvectors of the first graph with all eigenvectors of the second. Each alignment is inversely weighted by the distance between the corresponding eigenvalues. We show that for a correlated Erdos-Renyi model, this algorithm can return the exact matching with high probability if the graphs differ by at most a 1/polylog(n) fraction of edges, both for dense graphs and for sparse graphs with at least polylog(n) average degree.

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

Back to the full JSM 2019 program