Spectral Graph Matching

Event time: 
Friday, October 4, 2019 - 11:00am
Rm 107, 24 Hillhouse Ave.
Harry Zhou
Speaker affiliation: 
Henry Ford II Professor of Statistics and Data Science, Yale University
Event description: 

Theory Seminar

Abstract: We’ll discuss some recent work with Yihong Wu and Jiaming Xu on the “graph matching” problem of identifying the vertex matching between two graphs with correlated edges. We propose a simple spectral algorithm, which is related to a popular convex relaxation approach for this problem and also to the behavior of eigenvector moment flows for random matrices. We’ll describe a theoretical result establishing conditions under which this algorithm exactly recovers the vertex matching between two correlated Erdos-Renyi random graphs, and discuss some of the ideas of its proof and some open questions.